c++-STL容器逆向学习

lyfff 发表于 2022-11-30 14:08

本帖最后由 lyfff 于 2022-11-30 14:13 编辑

# c++-STL容器逆向学习
## 前言

在比赛中遇到了利用stl容器嵌套的ctf题目，能力有限做不出来，只好赛后跟着大佬的wp复现，顺便学习相关知识

## string

主要结构是由一个指针ptr和字符串长度string_length构成。当字符串长度小于0x10时，会在栈上分配一个长度为0x10的缓冲区用于存放字符串，且此时指针指向该缓冲区；当字符串长度大于等于0x10时，会将字符串存放到堆空间中

测试代码

```cpp
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
// 15
string s1 = "aaaaaaaaaaaaaaa";
// 16
string s2 = "bbbbbbbbbbbbbbbb";
// 17
string s3 = "ccccccccccccccccc";
            // 5
            string s4 = "ddddd";
return 0;
}
```

内存布局，可以发现字符串长度小于0x10时是储存在栈上的，且始终会分配16个字节给字符串，大于等于0x10时会将字符串存在堆上。

## ****deque****

deque主要由三部分构成。第一部分是描述map的指针及map大小，第二部分是指向开头的迭代器，第三部分是指向结尾的迭代器。

首先，map用于存放指针，指向真正存放数据的空间的首地址，实现整体连续的效果。如果需要增加储存空间，便会申请一段新的内存，同时在map数组的开头或者结尾添加对应的指针。

此外，因为数据实际上存放在了多段不连续的空间，所以迭代器必须满足以下条件：

1. 迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置；
2. 迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。

所以，迭代器包含了4个指针，用于实现上述功能

- cur：指向当前正在遍历的元素；
- first：指向当前连续空间的首地址；
- last：指向当前连续空间的末尾地址；
- node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。

测试代码

```cpp
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//创建10个值为5的deque
std::deque<int> d0(10,5);
std::deque<string> d1(10,"aaaaaa");
// cout << s1 << " " << s2 << " " << s3 << " " << endl;
for (auto i = d0.begin(); i < d0.end(); i++) {
   cout << *i << " ";
}
cout<<endl;
for (auto i = d1.begin(); i < d1.end(); i++) {
   cout << *i << " ";
}
return 0;
}
```

## rb_tree

一般节点由颜色，parent，left，right和所存放的数据构成，其中color红色为0，黑色为1。header的末尾会有node_count来计算当前树的节点个数。

STL中的set，map都是由红黑树实现，下面以map为例进行测试

```cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
   map<int, string> mapTemp;
   mapTemp.insert({ 5,"55555" });
   mapTemp.insert({ 3, "333333"});
   mapTemp.insert({ 4, "44444" });
   map<int, string>::iterator it;
   for (it = mapTemp.begin(); it != mapTemp.end(); it++)
   {
            printf("%d,%s\n", (*it).first, (*it).second.c_str());
   }
   return 0;
}
```

刚开始，树没有节点，故header的parent为0，left和right都为他本身

插入第一个节点后（即5，“55555”），parent指向根节点，left和right分别指向最左和最右的节点（此时仍为根节点）

根节点如下，且left和right都为0，数据(5,”55555”)直接存放在最后

再插入3，“333333”后，发现header和根节点的left都指向新的节点

插入（4，“4444”）后发现根节点变为了（4，“4444”），再此不做详细叙述

## hashtable

哈希表是unordered_map和unordered_set的底层实现。会申请一段空间用来储存链表的头指针，储存数据的链表称之为桶。每个桶都有对应的编号，一般最开始bucket_count=13，之后如果负载因子过大，会增加桶的数量，重新进行哈希。

测试代码如下

```cpp
#include<string>
#include<iostream>
#include<unordered_map>
using namespace std;

int main()
{
   unordered_map<int, string>dict; // 声明unordered_map对象
   dict.insert({ 30, "44444" });
   dict.insert({ 13, "666" });
   dict.insert({ 14, "11" });
dict.insert({ 15,"55555" });
   dict.insert({ 16, "333333"});
   dict.insert({ 17, "22"});
   dict.insert({ 18, "7777777"});
   // dict.insert({ 19, "88888888"});
   // dict.insert({ 20, "999999999"});
   // dict.insert({ 21, "aaa"});
   // dict.insert({ 22, "bbb"});
   // dict.insert({ 23, "ccc"});
   // dict.insert({ 24, "ddd"});
   // cout<<dict<<endl;
   return 0;
}
```

如下图，0x0D是当前桶的数量，7是当前储存的节点数量。field_1始终指向上一个插入的键值对的地址

buckets如下

当我们查看第一个桶的内容时，你以为存放的是(14，“11”)，但是实际上存放的是(13，“666”)

此外，当哈希冲突时，会在桶中利用头插法插入节点，如(30, "44444”)和(17, "22”)，都位于编号为4的桶内

## cppmaster

动态调试找到输入函数，查看第二个参数如下，可以看出这是一个deque，跟进qword_55BD1608BF30，即存放的第一个元素，可以发现其中存放了两个红黑树，继续跟进可以看到数的节点存放的是一个哈希表，哈希表中有两个桶存放着deque数组……

可以推测出，我们需要输入下标，最后得到的取值要与"8850a16d-e427-446e-b4df-5f45376e20e4”相等。通过对输入函数的交叉引用可以看到，共需要我们输入28次，也就是共有28层嵌套，可以手动搜索字符串从下往上提取数据，注意搜索时按照大端序搜索十六进制字符，可以找到

之后再搜索此地址，逐层往上排查即可。

不过手动搜索的方式未免有点丢人，费时费力，寻找代替方法。看到有大佬用idapython，照搬却跑不起来，尝试选择用frida代替，脚本如下

```python
import frida
device = frida.get_local_device()
def on_message(message, data):
global bruteforce_index
global bruteforce_success
# print(bruteforce_index)
# print(message['payload'])
# print("[%s] => %s" % (message, data))
# print(message['payload'],m)
# if((message['payload']) == m):
#       bruteforce_success = True
print("[%s] => %s" % (message, data))

handle = open("printf.js", "r",encoding='utf-8')
script_code = handle.read()
handle.close()
moduleName = 'cppmaster'
pid = device.spawn ( './'+moduleName,stdio='pipe')
print("pid, ", pid)
session = frida.attach(pid)
script = session.create_script(script_code)
script.on('message', on_message)
script.load()
device.resume(pid)
device.input(pid,b'1111')
input()
```

```jsx
// Find base address of current imported jvm.dll by main process fledge.exe
var moduleName = 'cppmaster'
var baseAddr = Module.findBaseAddress(moduleName);
console.log(moduleName + ' baseAddr: ' + baseAddr);
var size_table = {
   'rb_tree' : 48,
   'deque' : 80,
   'string' : 32,
   'hashtable' : 16,
}
var types_ordered = ["deque","rb_tree","hashtable","deque","rb_tree","rb_tree","hashtable",
                     "hashtable","rb_tree","rb_tree","hashtable","rb_tree","rb_tree","deque",
                     "deque","rb_tree","rb_tree","rb_tree","rb_tree","rb_tree","rb_tree",
                     "rb_tree","rb_tree","rb_tree","rb_tree","rb_tree","deque","deque","string"];

var monitorFuncAddr = resolveAddress('0x1e470'); // Here we use the function address as seen in our disassembler
function resolveAddress(addr) {
   var idaBase = ptr('0x0'); // Enter the base address of jvm.dll as seen in your favorite disassembler (here IDA)
   var offset = ptr(addr).sub(idaBase); // Calculate offset in memory from base address in IDA database
   var result = baseAddr.add(offset); // Add current memory base address to offset of function to monitor
   console.log('[+] New addr=' + result); // Write location of function in memory to console
   console.log(Memory.readU64(ptr(parseInt(result))));
   console.log(Memory.readByteArray(ptr(parseInt(result)+1),64));
   return result;
}

function dump_rbtree_node(addr) {
   return {
         'color' : Memory.readU64(ptr(addr)),
         'parent' : Memory.readU64(ptr(parseInt(addr) + 8)),
         'left' : Memory.readU64(ptr(parseInt(addr) + 16)),
         'right' : Memory.readU64(ptr(parseInt(addr) + 24)),
   }
}

function dump_rbtree_map(addr){
   var key = Memory.readU64(ptr(addr));
   var node_addr = parseInt(addr) + 8;
   var node_num = Memory.readU64(ptr(parseInt(addr)+40));
   var result = {};
   function visit(node){
         var info = dump_rbtree_node(node);
         var value_key = Memory.readU64(ptr(parseInt(node)+32));
         var data_addr = parseInt(node) + 40;
         result = data_addr;
         if(info["left"]!=0){
            visit(info["left"]);
         }
         if(info["right"]!=0){
            visit(info["right"]);
         }
   }
   var d = dump_rbtree_node(node_addr);
   visit(d['parent']);
   return result;
}

function dump_deque_iterator(addr){
   var a = {
         'cur' : Memory.readU64(ptr(addr)),
         'first' : Memory.readU64(ptr(parseInt(addr) + 8)),
         'last' : Memory.readU64(ptr(parseInt(addr) + 16)),
         'map' : Memory.readU64(ptr(parseInt(addr) + 24))
   };
   return a;
}

function dump_deque(addr,delta){
   var deque_map = Memory.readU64(ptr(addr));
   var map_size = Memory.readU64(ptr(parseInt(addr) + 8));
   if(map_size!=8){
         console.log("[+] map_size Wrong!");
   }
   // console.log(addr);
   var start = dump_deque_iterator(parseInt(addr) + 16);
   var finish = dump_deque_iterator(parseInt(addr) + 16 + 32);
   var ptr1 = start['cur'];
   var index = 0;
   var result = {};
   while(ptr1!=finish['cur']){
         result = ptr1;
         index += 1;
         ptr1 += delta;
   }
   return result;
}

function dump_string(addr){
   var data = Memory.readU64(ptr(addr));
   var length = Memory.readU64(ptr(parseInt(addr) + 8));
   return Memory.readCString(ptr(data),length);
}

function dump_hashtable_map(addr){
   var addrs = [];
   var hash_table = Memory.readU64(ptr(addr));
   var table_num = Memory.readU64(ptr(parseInt(addr) + 8));
   for(var i=0;i<table_num;i++){
         var link_list = Memory.readU64(ptr(parseInt(hash_table) + 8*i));
         if(link_list == 0){
            continue;
         }
         var ptr1 =Memory.readU64(ptr(link_list));
         while(ptr1 != 0){
            addrs.push(ptr1);
            ptr1 = Memory.readU64(ptr(ptr1));
         }
   }
   var result = {};
   for(var i=0;i<addrs.length;i++){
         result)+8))] = parseInt(addrs) + 16;
   }
   return result;
}

function dump_dfs(depth,addr){
   var stl_type = types_ordered;
   var tmp = {};
   if(stl_type == "rb_tree"){
         tmp = dump_rbtree_map(addr);
   }
   else if(stl_type == "hashtable"){
         tmp = dump_hashtable_map(addr);
   }
   else if(stl_type == "deque"){
         var next_type = types_ordered
         tmp = dump_deque(addr, size_table);
   }
   else if(stl_type == "string"){
         var a = dump_string(addr);
         // console.log(a);
         return a;
   }
   var node = {};
   for (var i in tmp)
   {
         var v = tmp;
         node = dump_dfs(depth + 1, v);
   }
   // console.log(node);
   return node
}
Interceptor.attach(monitorFuncAddr, { // Intercept calls to our SetAesDecrypt function

   // When function is called, print out its parameters
   /*
   其他API 用法
   https://frida.re/docs/javascript-api/
   */
   onEnter: function (args) {
         console.log('[+] Called monitorFuncAddr' + monitorFuncAddr);
         console.log('[+] Argv1: ' + args); // a1
         var result = dump_dfs(0, args);
         console.log("result:");
         var str = "";
         str = JSON.stringify(result);
         console.log(str);
   }
});

```

运行py结果如下

最后在得到的表中dfs即可

参考文章：

本文部分文字图片摘自下列文章，侵删

(https://bbs.pediy.com/thread-275133.htm#msg_header_h1_3)

(https://nese.team/posts/n1ctf/)

(http://c.biancheng.net/view/6908.html)

(http://c.biancheng.net/view/7235.html)

(https://blog.csdn.net/tjcwt2011/article/details/127729271)

lyfff 发表于 2022-11-30 18:20

cao777 发表于 2022-11-30 17:29
写的不错楼主用的是什么编译器
但是没有#include string头文件能正常编译吗?
用的是gcc version 12.2.0，当时还真没注意到，不过是没问题的

cao777 发表于 2022-11-30 17:29

写的不错楼主用的是什么编译器
但是没有#include string头文件能正常编译吗?

xiaoliang0011 发表于 2022-11-30 21:48

有点深度了，难

鹤舞九月天 发表于 2022-12-1 08:12

谢谢分享

78zhanghao87 发表于 2022-12-1 09:36

学习了学习了，很棒的代码解析

dofu05jj7uu 发表于 2022-12-1 14:25

感谢分享谢谢！

gotolala 发表于 2022-12-1 15:41

感谢分享！

ytfrdfiw 发表于 2022-12-1 18:05

感谢分享！

lfordch 发表于 2022-12-3 02:02

感谢分享，收藏学习

页: [1] 2 3

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

c++-STL容器逆向学习