关于 C++ 迭代器失效特性的研究

一、前言

在C++中，迭代器（Iterator）是一种用于遍历容器中元素的对象（如数组、向量、列表等）。它提供了一种统一的访问容器元素的方式，无论容器的类型和实现细节如何，比如list，vector，map等虽然实现不同，但最终都可以通过迭代器来访问和操作容器中的元素。

迭代器的工作方式类似于指针，它可以指向容器中的特定位置，并允许你在容器中前进或后退。通过使用迭代器，你可以遍历容器中的所有元素，执行读取、修改或删除操作。

二、迭代器的几种常见使用方式

Range-Base-For形式
```
for(auto& it : its_){ 
  [...]
}
```
直接迭代器形式
```
auto it = its_.begin()
it.next()
```

循环形式

for(it = its_.begin();it！= its_.end();it++){
  [...]
}

三、序列式容器

3.1 Vector失效

首先先来介绍一下Vector的结构，Vector 是C++标准程序库中的一个类，可视为会自动扩展容量的数组，以循序（Sequential）的方式维护变量集合。

图片来源：参考链接[4]

失效原因：容器发生内存重分配后，或者有删除或者插入操作
失效前提：有删除或者插入操作。

失效情况：

容器内存经过push_back 后重新分配，迭代器的指针还是指向原来的内存，导致迭代器、引用、指针都失效。如果是插入且没有重新分配，只会使后面的元素失效。

如下例，定义了一个Vector，并对其进行循环迭代。

std::vector<int> vec_;
vec_.push_back(1);
vec_.push_back(2);
for(auto & it : vec_){
    vec_.push_back(3);
    std::cout<<it<<std::endl;
}

在运行完两个push_back进行元素的添加后，此时Vector的内存：

std::vector<int> vec_;
vec_.push_back(1);
vec_.push_back(2);
---------------------
vec_:
0x7fffffffdcc0: 0x0000602000000030[start]      0x0000602000000038[finish]
0x7fffffffdcd0: 0x0000602000000038[end]      0x00007ffff7f953f8
----------------------

然后在进行迭代时，对其进行元素添加，超过其容量导致空间重分配。[*]的位置就是Vector的首地址，可以清楚看见此时的地址已经为重新分配后的地址了，原地址已经被释放。然后在运行输出语句后导致UAF。

for(auto & it : vec_){
    vec_.push_back(3);
    ----------------------------
    0x7fffffffdcc0: 0x0000602000000050[*]      0x000060200000005c
    0x7fffffffdcd0: 0x0000602000000060      0x00007ffff7f953f8
    //原先的内存被释放，重新申请新空间。此时迭代器it 引用的地址
    //pwndbg> p &it
    //$9 = (int *) 0x602000000030
    ----------------------------
    std::cout<<it<<std::endl;
    ----------------------------
    ==2386378==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000030 at pc 0x5555556329fe bp 0x7fffffffdc90 sp 0x7fffffffdc88
    READ of size 4 at 0x602000000030 thread T0
    -----------------------------
}

容器内元素erase后，在其后面的元素都会往前移，导致其后面的元素都失效。（不可利用）

std::vector<std::string> vec_;
vec_.push_back("1");
vec_.push_back("2");
vec_.push_back("3");
vec_.push_back("4");
int times = 1;
for(auto &it : vec_){
    if(times==1){
        vec_.erase(++vec_.begin());
        times--;
    }
    std::cout<<it<<std::endl;
}
-----------------------------
Output:
1
3
4

案例分析：Security: UAF in MultiplexEncoderFactory

这是一个Vector失效的案例，例子中有一个Range For base的迭代，但是在这个循环中，对迭代器的范围进行了push_back操作，如果此时因为这个push_back操作导致容器的地址重分配，就会导致UAF。

std::vector<SdpVideoFormat> MultiplexDecoderFactory::GetSupportedFormats()
    const {
  std::vector<SdpVideoFormat> formats = factory_->GetSupportedFormats();
  for (const auto& format : formats) {
    if (absl::EqualsIgnoreCase(format.name, kMultiplexAssociatedCodecName)) {
      SdpVideoFormat multiplex_format = format;
      multiplex_format.parameters[cricket::kCodecParamAssociatedCodecName] =
          format.name;
      multiplex_format.name = cricket::kMultiplexCodecName;
      formats.push_back(multiplex_format); //<---- realloc: crash
    }
  }
  return formats;
}

Fix：

修复是对这个容器进行深拷贝，这样在push_back的时候不会对正在访问的容器进行操作，而是把数据拷贝到新的容器里，然后在返回这个新容器。

std::vector<SdpVideoFormat> MultiplexDecoderFactory::GetSupportedFormats()
     const {
   std::vector<SdpVideoFormat> formats = factory_->GetSupportedFormats();
+  std::vector<SdpVideoFormat> augmented_formats = formats;
   for (const auto& format : formats) {
     if (absl::EqualsIgnoreCase(format.name, kMultiplexAssociatedCodecName)) {
       SdpVideoFormat multiplex_format = format;
       multiplex_format.parameters[cricket::kCodecParamAssociatedCodecName] =
           format.name;
       multiplex_format.name = cricket::kMultiplexCodecName;
-      formats.push_back(multiplex_format);
+      augmented_formats.push_back(multiplex_format);
     }
   }
-  return formats;
+  return augmented_formats;
 }

3.2 Deque失效

Deque虽然也是序列式容器，但是他跟Vector 差距还是挺大的。Deque是一种支持向两端高效地插入数据、支持随机访问的容器。其内部实现原理如下：双端队列的数据被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外容器还需要维护一个存放这些数组首地址的索引数组。参见下图：

图片来源：参考链接[2]

由于分段数组的大小是固定的，并且它们的首地址被连续存放在索引数组中，因此可以对其进行随机访问。

向两端加入新元素时，如果这一端的分段数组未满，则可以直接加入；如果这一端的分段数组已满，只需创建新的分段数组，并把该分段数组的地址加入到索引数组中即可。无论哪种情况，都不需要对已有元素进行移动，因此在双端队列的两端加入新的元素都具有较高的效率。
当删除双端队列容器两端的元素时，由于不需要发生元素的移动，效率也是非常高的。
双端队列中间插入元素时，需要将插入点到某一端之间的所有元素向容器的这一端移动，因此向中间插入元素效率较低，而且往往插入位置越靠近中间，效率越低。删除队列中元素时，情况也类似，由于被删元素到某一端之间的所有元素都要向中间移动，删除的位置越靠近中间，效率越低。

注意: 在除了首尾两端的其他地方插入和删除元素，都有可能导致元素的任何pointers、references、iterators失效。

失效原因：容器发生内存重分配后，或者有删除或者插入操作。
失效前提：有删除或者插入操作。
失效情况：
1. 容器内存经过push_back 后Map索引重新分配，迭代器的指针还是指向原来的内存，导致迭代器、引用、指针都失效。如果是插入且没有重新分配，只会使后面的元素失效。
  以下代码分配了一个deque实例，首先往里面添加足够多的元素，然后在迭代的时候，直接往容器里面添加元素当到Map达一定的阈值后，造成UAF。
```
std::deque<int> myDeque = {1};
    for(int i=0;i<0x1000;i++){
        myDeque.emplace_back(2);
    }
    for(auto it : myDeque){
        myDeque.emplace_back(2);
    }
-----------------------
==3331485==ERROR: AddressSanitizer: heap-use-after-free on address 0x6160000001f0 at pc 0x0000004c9a6b bp 0x7ffec6f450f0 sp 0x7ffec6f450e8
READ of size 8 at 0x6160000001f0 thread T0
```
  Fix: 同Vector，只需要在迭代之前，把容器进行深拷贝。
2. 容器内元素erase后，在其后面的元素都会往前移，导致其后面的元素都失效。（不可利用）

四、链表式容器

4.1 List失效

List 由双向链表（doubly linked list）实现而成，元素也存放在堆中，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载。但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。

图片来源：参考链接[5]

如果想要两个Node之间再增加一个Node元素，使用push_back 或者emplace API将插入两端的指针指向新插入的元素就可以，如下图所示：

图片来源：参考链接[5]

失效原因：元素删除导致的当前被erase元素失效。
失效条件：删除元素。
失效情况：容器内元素erase后，当前元素会在链表中取下来，然后被释放。就不能在用它了。

案例分析

下列代码定义了一个list容器，然后往里面添加2个int 元素，然后在对其进行迭代的时候，erase其中一个元素后，由于当前元素被erase后，从链中被取下来，随后被释放掉，最终导致UAF。

std::list<int> vec_;
vec_.push_back(1);
vec_.push_back(2);
for (auto it = vec_.begin(); it != vec_.end(); ) {
    vec_.erase(it);
    std::cout<<*it<<std::endl;
}
-----------------------
==2387140==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000050 at pc 0x558fe2416a0e bp 0x7ffd5b1fa870 sp 0x7ffd5b1fa868
READ of size 4 at 0x603000000050 thread T0

Fix: 建议的修复是在erase 后，迭代一次，使迭代器指向下一个合法元素。

std::list<int> vec_;
vec_.push_back(1);
vec_.push_back(2);
for (auto it = vec_.begin(); it != vec_.end(); it++) {
    vec_.erase(it++);
    std::cout<<*it<<std::endl;
}

五、关联式容器

5.1 Map/Set失效

Set容器内的元素会被自动排序，Set 与 Map 不同，Set 中的元素即是键值又是实值，Set 不允许两个元素有相同的键值。不能通过 Set 的迭代器去修改 Set 元素，原因是修改元素会破坏 Set 组织。当对容器中的元素进行插入或者删除时，操作之前的所有迭代器在操作之后依然有效。

图片来源：参考链接[6]

Map 由红黑树实现，其元素都是 “键值/实值” 所形成的一个对组（key/value pairs）。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。

map主要用于资料一对一映射的情况，Map 内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以在 Map 内部所有的数据都是有序的。比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。

图片来源：参考链接[6]

图片来源：参考链接[7]

失效原因：元素删除导致的当前被erase 元素失效。
失效条件：删除元素。

失效情况：

容器内元素erase后，当前元素会在红黑树中取下来，然后被释放，就不能在用它了。

std::map<int,int> vec_;
vec_.emplace(1,0);
vec_.emplace(2,0);
for (auto it = vec_.begin(); it != vec_.end(); it++) {
    vec_.erase(it);
    std::cout<<it->first<<std::endl;
}
-------------------------------
==2387781==ERROR: AddressSanitizer: heap-use-after-free on address 0x6040000000b0 at pc 0x557252362d0e bp 0x7ffe42db7d10 sp 0x7ffe42db7d08
READ of size 4 at 0x6040000000b0 thread T0

-------------------------------
std::map<int,int> vec_;
vec_.emplace(1,0);
vec_.emplace(2,0);
auto it = vec_.begin();
vec_.erase(it);
std::cout<<it->first<<std::endl;
------------------------------
==2398643==ERROR: AddressSanitizer: heap-use-after-free on address 0x6040000000b0 at pc 0x5564da9f3bee bp 0x7ffca5911fb0 sp 0x7ffca5911fa8
READ of size 4 at 0x6040000000b0 thread T0

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。

void CPDFSDK_FormFillEnvironment::ClearAllFocusedAnnots() {
    for (auto& it : m_PageMap) {
        if (it.second->IsValidSDKAnnot(GetFocusAnnot()))
        KillFocusAnnot(0);
    }
}

CPDFSDK_FormFillEnvironment::KillFocusAnnot ->
CPDFSDK_AnnotHandlerMgr::Annot_OnKillFocus ->
CPDFSDK_XFAWidgetHandler::OnKillFocus ->
CXFA_FFDocView::SetFocus ->
CXFA_FFWidget::OnSetFocus ->
CXFA_Node::ProcessEvent