前言
在比赛中遇到了利用stl容器嵌套的ctf题目，能力有限做不出来，只好赛后跟着大佬的wp复现，顺便学习相关知识
string
主要结构是由一个指针ptr和字符串长度string_length构成。当字符串长度小于0x10时，会在栈上分配一个长度为0x10的缓冲区用于存放字符串，且此时指针指向该缓冲区；当字符串长度大于等于0x10时，会将字符串存放到堆空间中
测试代码
#include
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时会将字符串存在堆上。
Untitled.png (46.3 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
deque
deque主要由三部分构成。第一部分是描述map的指针及map大小，第二部分是指向开头的迭代器，第三部分是指向结尾的迭代器。
首先，map用于存放指针，指向真正存放数据的空间的首地址，实现整体连续的效果。如果需要增加储存空间，便会申请一段新的内存，同时在map数组的开头或者结尾添加对应的指针。
此外，因为数据实际上存放在了多段不连续的空间，所以迭代器必须满足以下条件：
[ol]
[/ol]
所以，迭代器包含了4个指针，用于实现上述功能
Untitled 1.png (41.86 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
测试代码
#include
#include
using namespace std;
int main(int argc, const char * argv[]) {
//创建10个值为5的deque
std::deque d0(10,5);
std::deque d1(10,"aaaaaa");
// cout
Untitled 2.png (68.23 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
rb_tree
一般节点由颜色，parent，left，right和所存放的数据构成，其中color红色为0，黑色为1。header的末尾会有node_count来计算当前树的节点个数。
Untitled 3.png (34.65 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
STL中的set，map都是由红黑树实现，下面以map为例进行测试
#include
#include
#include
using namespace std;
int main()
{
map mapTemp;
mapTemp.insert({ 5,"55555" });
mapTemp.insert({ 3, "333333"});
mapTemp.insert({ 4, "44444" });
map::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都为他本身
Untitled 4.png (18.87 KB, 下载次数: 0)
下载附件
2022-11-30 14:01 上传
插入第一个节点后（即5，“55555”），parent指向根节点，left和right分别指向最左和最右的节点（此时仍为根节点）
Untitled 5.png (25.33 KB, 下载次数: 0)
下载附件
2022-11-30 13:58 上传
根节点如下，且left和right都为0，数据(5,”55555”)直接存放在最后
Untitled 6.png (27.8 KB, 下载次数: 0)
下载附件
2022-11-30 13:58 上传
再插入3，“333333”后，发现header和根节点的left都指向新的节点
Untitled 7.png (29.49 KB, 下载次数: 0)
下载附件
2022-11-30 14:01 上传
Untitled 8.png (22.2 KB, 下载次数: 0)
下载附件
2022-11-30 13:58 上传
插入（4，“4444”）后发现根节点变为了（4，“4444”），再此不做详细叙述
hashtable
哈希表是unordered_map和unordered_set的底层实现。会申请一段空间用来储存链表的头指针，储存数据的链表称之为桶。每个桶都有对应的编号，一般最开始bucket_count=13，之后如果负载因子过大，会增加桶的数量，重新进行哈希。
Untitled 9.png (39.21 KB, 下载次数: 0)
下载附件
2022-11-30 14:01 上传
测试代码如下
#include
#include
#include
using namespace std;
int main()
{
unordered_map 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
如下图，0x0D是当前桶的数量，7是当前储存的节点数量。field_1始终指向上一个插入的键值对的地址
Untitled 10.png (27.82 KB, 下载次数: 0)
下载附件
2022-11-30 13:58 上传
buckets如下
Untitled 11.png (32.96 KB, 下载次数: 0)
下载附件
2022-11-30 14:01 上传
当我们查看第一个桶的内容时，你以为存放的是(14，“11”)，但是实际上存放的是(13，“666”)
Untitled 12.png (26.9 KB, 下载次数: 0)
下载附件
2022-11-30 13:58 上传
Untitled 13.png (24.9 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
此外，当哈希冲突时，会在桶中利用头插法插入节点，如(30, "44444”)和(17, "22”)，都位于编号为4的桶内
Untitled 14.png (23.84 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
Untitled 15.png (24.82 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
cppmaster
动态调试找到输入函数，查看第二个参数如下，可以看出这是一个deque，跟进qword_55BD1608BF30，即存放的第一个元素，可以发现其中存放了两个红黑树，继续跟进可以看到数的节点存放的是一个哈希表，哈希表中有两个桶存放着deque数组……
Untitled 16.png (25.43 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
Untitled 17.png (42.08 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
可以推测出，我们需要输入下标，最后得到的取值要与"8850a16d-e427-446e-b4df-5f45376e20e4”相等。通过对输入函数的交叉引用可以看到，共需要我们输入28次，也就是共有28层嵌套，可以手动搜索字符串从下往上提取数据，注意搜索时按照大端序搜索十六进制字符，可以找到
Untitled 18.png (38.66 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
之后再搜索此地址，逐层往上排查即可。
不过手动搜索的方式未免有点丢人，费时费力，寻找代替方法。看到有大佬用idapython，照搬却跑不起来，尝试选择用frida代替，脚本如下
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'][bruteforce_index],m[bruteforce_index])
# if((message['payload'][bruteforce_index]) == m[bruteforce_index]):
# 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()
// 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[value_key] = 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[index] = 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]
运行py结果如下
Untitled 19.png (110.16 KB, 下载次数: 0)
下载附件
2022-11-30 13:57 上传
最后在得到的表中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
