在C++中，迭代器（Iterator）是一种用于遍历容器中元素的对象（如数组、向量、列表等）。它提供了一种统一的访问容器元素的方式，无论容器的类型和实现细节如何，比如list，vector，map等虽然实现不同，但最终都可以通过迭代器来访问和操作容器中的元素。
迭代器的工作方式类似于指针，它可以指向容器中的特定位置，并允许你在容器中前进或后退。通过使用迭代器，你可以遍历容器中的所有元素，执行读取、修改或删除操作。
1. Range-Base-For形式
2. 直接迭代器形式
3. 循环形式
Vector失效
首先先来介绍一下Vector的结构，Vector 是C++标准程序库中的一个类，可视为会自动扩展容量的数组，以循序（Sequential）的方式维护变量集合。
图片来源：参考链接[4]
1. 失效原因：容器发生内存重分配后，或者有删除或者插入操作。
2. 失效前提：有删除或者插入操作。
3. 失效情况：
-
容器内存经过push_back 后重新分配，迭代器的指针还是指向原来的内存，导致迭代器、引用、指针都失效。如果是插入且没有重新分配，只会使后面的元素失效。
如下代码，定义了一个Vector，并对其进行循环迭代。
![关于C++ 迭代器失效特性的研究]( "关于C++ 迭代器失效特性的研究")
在运行完两个push_back进行元素的添加后，此时Vector的内存：
![关于C++ 迭代器失效特性的研究]( "关于C++ 迭代器失效特性的研究")
然后在进行迭代时，对其进行元素添加，超过其容量导致空间重分配。[*]的位置就是Vector的首地址，可以清楚看见此时的地址已经为重新分配后的地址了，原地址已经被释放。然后在运行输出语句后导致UAF。
![关于C++ 迭代器失效特性的研究]( "关于C++ 迭代器失效特性的研究")
-
容器内元素erase后，在其后面的元素都会往前移，导致其后面的元素都失效。（不可利用）
代码案例如下：
![关于C++ 迭代器失效特性的研究]( "关于C++ 迭代器失效特性的研究")
这是一个Vector失效的案例，例子中有一个Range For base的迭代，但是在这个循环中，对迭代器的范围进行了push_back操作，如果此时因为这个push_back操作导致容器的地址重分配，就会导致UAF。
Fix：
修复是对这个容器进行深拷贝，这样在push_back的时候不会对正在访问的容器进行操作，而是把数据拷贝到新的容器里，然后再返回这个新容器。
Deque失效
Deque虽然也是序列式容器，但是他跟Vector 差距还是挺大的。Deque是一种支持向两端高效地插入数据、支持随机访问的容器。其内部实现原理如下：双端队列的数据被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外容器还需要维护一个存放这些数组首地址的索引数组。参见下图：
图片来源：参考链接[2]
由于分段数组的大小是固定的，并且它们的首地址被连续存放在索引数组中，因此可以对其进行随机访问。
-
向两端加入新元素时，如果这一端的分段数组未满，则可以直接加入；如果这一端的分段数组已满，只需创建新的分段数组，并把该分段数组的地址加入到索引数组中即可。无论哪种情况，都不需要对已有元素进行移动，因此在双端队列的两端加入新的元素都具有较高的效率。
-
当删除双端队列容器两端的元素时，由于不需要发生元素的移动，效率也是非常高的。
-
双端队列中间插入元素时，需要将插入点到某一端之间的所有元素向容器的这一端移动，因此向中间插入元素效率较低，而且往往插入位置越靠近中间，效率越低。删除队列中元素时，情况也类似，由于被删元素到某一端之间的所有元素都要向中间移动，删除的位置越靠近中间，效率越低。
注意: 在除了首尾两端的其他地方插入和删除元素，都有可能导致元素的任何pointers、references、iterators失效。
1. 失效原因：容器发生内存重分配后，或者有删除或者插入操作。
2. 失效前提：有删除或者插入操作。
3. 失效情况：
-
容器内存经过push_back 后Map索引重新分配，迭代器的指针还是指向原来的内存，导致迭代器、引用、指针都失效。如果是插入且没有重新分配，只会使后面的元素失效。
-
容器内元素erase后，在其后面的元素都会往前移，导致其后面的元素都失效。（不可利用）
案例分析
以下代码分配了一个deque实例，首先往里面添加足够多的元素，然后在迭代的时候，直接往容器里面添加元素当到Map达一定的阈值后，造成UAF。
Fix：
同Vector，只需要在迭代之前，将容器进行深拷贝。
List失效
List 由双向链表（doubly linked list）实现而成，元素也存放在堆中，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载。但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。
图片来源：参考链接[5]
如果想要两个Node之间再增加一个Node元素，使用push_back 或者emplace API将插入两端的指针指向新插入的元素就可以，如下图所示：
图片来源：参考链接[5]
1. 失效原因：元素删除导致的当前被erase元素失效。
2. 失效条件：删除元素。
3. 失效情况：容器内元素erase后，当前元素会在链表中取下来，然后被释放，就不能再用它了
案例分析
下列代码定义了一个list容器，然后往里面添加2个int 元素，然后在对其进行迭代的时候，erase其中一个元素后，由于当前元素被erase后，从链中被取下来，随后被释放掉，最终导致UAF。
Fix：
建议的修复是在erase 后，迭代一次，使迭代器指向下一个合法元素。
MapSet失效
Set容器内的元素会被自动排序，Set 与 Map 不同，Set 中的元素即是键值又是实值，Set 不允许两个元素有相同的键值。不能通过 Set 的迭代器去修改 Set 元素，原因是修改元素会破坏 Set 组织。当对容器中的元素进行插入或者删除时，操作之前的所有迭代器在操作之后依然有效。
图片来源：参考链接[6]
Map 由红黑树实现，其元素都是 “键值/实值” 所形成的一个对组（key/value pairs）。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。
Map主要用于资料一对一映射的情况，Map 内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以在 Map 内部所有的数据都是有序的。比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。
图片来源：参考链接[6]
图片来源：参考链接[7]
1. 失效原因：元素删除导致的当前被erase 元素失效。
2. 失效条件：删除元素。
3. 失效情况：容器内元素erase后，当前元素会在红黑树中取下来，然后被释放，就不能再用它了
-
下列代码定义了一个Map，然后往里面添加2个元素，然后在对其进行迭代的时候，erase其中一个Node后，由于当前Node被erase后，从树中被取下来，随后被释放掉，最终导致UAF。
![关于C++ 迭代器失效特性的研究]( "关于C++ 迭代器失效特性的研究")
Fix: 同list一样，在Node 被取消释放后，迭代到下一个有效的Node 就可以。
案例分析：Potential use after free in CPDFSDK_FormFillEnvironment::ClearAllFocusedAnnots (XFA)
如下是chromium中的Map迭代失效。在ClearAllFocusedAnnots 函数里，有一个KillFocusAnnot调用，但是这个KillFocusAnnot最终有条路径可以走到CXFA_Node::ProcessEvent，ProcessEvent可以自定义JS代码，起到了回调作用，可以通过别处的m_PageMap.Clear() 把Map的节点全部清空释放，在后面迭代的时候就会造成UAF。
本文总结了C++迭代器失效的几种情况，总之，迭代器失效就是在迭代器迭代的过程中，容器或者容器内元素发生变化，导致的内存损坏等影响。
[3] 知乎问答
[5] C++ list容器
[6] Standard Associative Containers
[7] C++ map用法总结（整理）
【版权说明】
本作品著作权归Lime所有
未经作者同意，不得转载
Lime
天工实验室安全研究员
专注于浏览器漏洞挖掘与利用
原文始发于微信公众号（破壳平台）：关于C++ 迭代器失效特性的研究
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论