【转帖】C++逆向学习(二) vector

默小白 发表于 2019-4-29 11:57

转自：https://xz.aliyun.com/t/4933

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

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

# vector

## 内存布局

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163211-7499cc22-666b-1.png)

```
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;
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
```

运行结果：

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163223-7c0161be-666b-1.png)

可以看到，后面的增长速度和`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)时：

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163231-805902bc-666b-1.png)

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

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163235-82c2277c-666b-1.png)

## accumulate

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

> 关于用`std::accumulate + lambda`反转`vector`，在上一篇文章已经写过了
>
> [西湖论剑初赛easyCpp探究](https://xz.aliyun.com/t/4880)

在这边就算是补个例子

```
#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;
}
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`的特征了

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163243-876f150a-666b-1.png)

分析一下，开了一块内存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; }
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 != 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*b`，最后判断`result`中的每个数是否符合要求

> 注意，`vector b`大小一定要超过`vector a`，从参数中也可以看出来，`b`只传入了`begin()`
>
> 如果`vector b`较小，后面的内存存放的是未知的数据
>
> 会造成未定义行为 UB

### IDA视角

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163252-8d3ed948-666b-1.png)

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163258-90c9841e-666b-1.png)

跟进`std::transform`

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163303-93a99c46-666b-1.png)

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

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163408-ba1a5c6c-666b-1.png)

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163413-bd5c1de8-666b-1.png)

算法很简单，只要输入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下观察内存结构

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163418-c06286bc-666b-1.png)

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

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

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

### IDA视角

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

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163426-c525b4a8-666b-1.png)

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

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

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

输出部分：

!(https://xzfile.aliyuncs.com/media/upload/picture/20190424163431-c7efae32-666b-1.png)

稍微有些不理解，看起来两个内层`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`

shelly1314 发表于 2019-4-29 13:07

感谢楼主分享

武胜造纸农 发表于 2019-4-29 13:32

感谢分享，学习了

一叶知夏 发表于 2019-4-29 14:05

五一抽空跟楼主学习一下

wei059098 发表于 2019-4-29 14:39

{:1_908:}大佬大佬看天书一样

rickw 发表于 2019-4-29 15:12

这种如果是静态链接编译的，库函数代码和程序代码就容易混在一起了。

LjeA 发表于 2019-4-29 21:00

精品好文！！！

92013 发表于 2019-4-29 21:41

楼主很厉害啊谢谢分享

wang19940311 发表于 2019-5-1 07:20

学习学习学习重要的事情说三遍

学士天下 发表于 2019-5-1 08:07

顶一下，精品干货学习啦！！！

页: [1] 2

吾爱破解 - 52pojie.cn's Archiver

【转帖】C++逆向学习(二) vector