现在的逆向C++题越来越多，经常上来就是一堆容器、标准模板库，这个系列主要记录这些方面的逆向学习心得

本文主要介绍std::vector，因为逆向题中的C++代码可能会故意写的很绕，比如输入一个数组，直接给vector赋值即可，但是也可以用稍微费解的方法连续push_back()，也算是一种混淆的手段，文章中的示例会逆向一些故意写的繁琐的程序

vector

内存布局

仍然用vs调试，观察内存布局

vector a的第一个字段是size 大小第二个字段是capacity 容量

和std::string差不多

当size>capacity也就是空间不够用时

首先配置一块新空间，然后将元素从旧空间一一搬往新空间，再把旧空间归还给操作系统

内存增长机制

测试代码：

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char** argv) {
    std::vector<int> a;
    int num[16];
    for (int i = 0; i < 100; i++) {
        a.push_back(i);
        std::cout << "size : " << i+1 << "\t" << "capacity : " << a.capacity() << std::endl;
    }
    system("pause");
    return 0;
}
//visual studio 2019 x64

运行结果：

可以看到，后面的增长速度和std::string一样是1.5倍扩容，一开始有点差别，分析一下源码

else if (max_size() - size() < _Count)
    //可以申请的最大容量也不够用，抛出异常_THROW(length_error, "vector<T> too long");
    _Xlen();
else if (_Capacity < size() + _Count){//空间不足，需要扩容   
    _Capacity = max_size() - _Capacity / 2 < _Capacity
        ? 0 : _Capacity + _Capacity / 2;    // 尝试扩容1.5倍
    if (_Capacity < size() + _Count)//扩容1.5倍后依然不够用，则容量等于当前数据个数加上新增数据个数
        _Capacity = size() + _Count;
    pointer _Newvec = this->_Alval.allocate(_Capacity);//申请新空间
    pointer _Ptr = _Newvec;
    _TRY_BEGIN
        _Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
            _Newvec);   //move原先的数据
    _Ptr = _Ucopy(_First, _Last, _Ptr); //copy新增的数据到新内存之后
    _Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr);  
    _CATCH_ALL
        _Destroy(_Newvec, _Ptr);
    this->_Alval.deallocate(_Newvec, _Capacity);//释放原来申请的内存
    _RERAISE;
    _CATCH_END
...

详见注释，注意这句扩容1.5倍后依然不够用，则容量等于当前数据个数加上新增数据个数，也就解释了一开始的增长是1 2 3 4的原因

调试

具体调试一下，当push_back(0)和(1)时：

注意一开始的内存窗口，每次动态扩容时确实已经改变了存储空间的地址

再F5执行到断点，内存窗口的红色说明这块内存刚动过，已经被操作系统回收了，vector中的元素也已经改变了存放地址

accumulate

上次写西湖论剑easyCpp的探究时有朋友说再举一些std::accumulate的例子...

关于用std::accumulate + lambda反转vector，在上一篇文章已经写过了

西湖论剑初赛easyCpp探究

在这边就算是补个例子

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;

int main(int argc, char** argv) {
    std::vector<int> v(5);
    for (int i = 0; i < 5; i++) {
        std::cin >> v[i];
    }
    int sum = std::accumulate(v.begin(), v.end(), 0,
        [](int acc, int _) {return acc + _; });
    std::cout << sum;
    return 0;
}
//visual studio 2019 x64

std::accumulate对一个容器进行折叠，并且是左折叠，对其进行一元操作，实例中为lambda +

因为迭代器可以看作是容器与算法的中间层，这也是STL的设计哲学，因此传入的是vector的begin()和end()

在"循环"的内部，通过判断当前迭代器是否到达末尾得到是否结束循环的信息，形如：

for(vector<int>::const_iterator iter=ivec.begin();iter!=ivec.end();++iter){
    /*...*/ 
}

IDA视角

IDA中打开，因为是windows下vs编译的，看不出vector和accumulate和lambda的特征了

分析一下，开了一块内存0x14字节，也就是对应我们的5个int

依次输入赋值，最后用一个指针++遍历这个地址

获得累加和并输出

transform

换个稍复杂的std::transform的例子，保留特征，用g++编译

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;

int main(int argc, char** argv) {
    std::vector<int> a = { 1,2,3,4,5};
    std::vector<int> b(5);
    std::vector<int> result;
    for (int i = 0; i < 5; i++) { std::cin >> b[i]; }
    std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(result),
        [](int _1, int _2) { return _1 * _2; });

    for (int i = 0; i < 5; i++) {
        if (result[i] != 2 * (i + 1)) {
            std::cout << "You failed!" << std::endl;
            exit(0);
        }
    }
    std::cout << "You win!" << std::endl;
    return 0;
}
//g++ main.cpp -o test -std=c++14

用std::transform同时对两个列表进行操作，输入5个数存入vector b中，然后vector result分别是a[i]*b[i]，最后判断result中的每个数是否符合要求

注意，vector b大小一定要超过vector a，从参数中也可以看出来，b只传入了begin()

如果vector b较小，后面的内存存放的是未知的数据

会造成未定义行为 UB

IDA视角

IDA打开可以看到vector相关代码，但是命名很乱，根据std::transform二元操作符的特征我们可以更改一下变量名

我们定义的vector{1,2,3,4,5}在内存中如下

跟进std::transform

一眼注意到最关键的lambda，其他都是operator* = ++等重载的迭代器相关的操作符

熟悉transform的话显然没有需要我们关注的东西

lambda中也只是我们实现的简单乘法运算

算法很简单，只要输入5个2就会得到win了

vector存vector

这个程序写的有点...没事找事，用于再深入分析一下

比如输入10个数，分别放入size为1 2 3 4的四个vector，并且把4个vector一起放在一个vector中,再进行运算
虽然正常程序不会这么写，但是作为逆向的混淆感觉效果不错

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;

int main(int argc, char** argv) {
    std::vector<std::vector<int>> a;
    a.push_back(std::vector<int>{1, 2, 3});
    a.push_back(std::vector<int>{6, 7});
    for (auto v : a) {
        for (auto n : v) {
            std::cout << n << "\t";
        }
        std::cout << std::endl;
    }
    return 0;
}
//g++ main.cpp -std=c++14 -o test

内存结构

为了方便说明，仍然在vs下观察内存结构

一开始纠结了很久，因为vector开的内存必定是连续的，也就是说{1,2,3}是连续的，{6,7}也是连续的

那么外层vector如果把{1,2,3},{6,7}存在一起，那么当内层vector扩容时，一定会影响到外层vector

最后才明白，外层vector只是存了内层vector的数据结构，而不是直接存了{1,2,3},{6,7}

IDA视角

IDA打开g++编译过后的程序，便于学习演示

结合注释和变量的重命名，逻辑比较清晰

vector_vector<vector<int> >.push_back(&vec1)

可以理解为外层vector存了内层vector的"指针"

输出部分：

稍微有些不理解，看起来两个内层vector的迭代器之间有一些优化

vec1 = end(vec2_addr)，这一句没怎么看懂，因为上传附件经常丢失...没有上传例程，通过源码编译比较简单，大佬们有兴趣可以试着逆一下逻辑

不过主线还是清晰的

外层vector的迭代器operator ++和operator !=
双层循环，内层循环分别得到每个内层vector的*iterator，通过ostream输出

小总结

vector中连续内存里存的是类型的数据结构，比如int的数据结构，vector<int>的数据结构

但无论如何，每个vector用于存数据的内存都是连续的

比如 {1,2,3},vector<int>{1,2},vector<int>{3,4,5}这两个vector

vector

内存布局

内存增长机制

调试

accumulate

IDA视角

transform

IDA视角

vector存vector

内存结构

IDA视角

小总结

目录