使用CodeQL检测迭代器失效：深入解析Itergator工具

本文详细介绍了如何使用CodeQL静态分析框架检测C++中的迭代器失效问题。通过Itergator工具，开发者可以识别潜在的迭代器失效漏洞，包括复杂的控制流分析和数据流追踪，有效减少未定义行为和安全风险。

使用CodeQL检测迭代器失效

迭代器失效是C++中一类常见且隐蔽的bug，通常会导致可利用的漏洞。在今年夏天的Trail of Bits实习期间，我开发了Itergator，这是一组用于分析和发现迭代器失效的CodeQL类和查询。

结果易于审计人员解释，提供诸如迭代器获取位置、失效位置以及指示误报可能性的重要性级别等信息。Itergator已用于在真实代码中发现bug，并且查询易于扩展以进行进一步分析。

迭代器定义

迭代器是C++中遍历容器内容的标准方式。迭代器对象至少支持两种操作：解引用以获取容器中的底层对象；以及递增以获取下一个元素的迭代器。

例如，以下代码将输出1 2 3 4 5：

1
2
3
4
5

std::vector<int> vec{1, 2, 3, 4, 5};

for (std::vector<int>::iterator it = vec.begin(), end = vec.end(); it != end; ++it) {
    std::cout << *it << " ";
}

这是一个如此常见的代码模式，以至于C++11引入了简化语法：

1
2
3

for (auto i : vec) {
    std::cout << i << " ";
}

虽然等同于之前的代码，但所有迭代器操作现在都由编译器生成。迭代的细节对开发人员是隐藏的。

迭代器失效

在对容器进行某些修改（例如添加或擦除元素）后，迭代器会失效。根据标准，使用失效的迭代器是未定义行为。换句话说，发生的情况是特定于实现的，可能不好。

例如，在以下代码中（由Itergator在Cataclysm: Dark Days Ahead中发现），对zones.erase的调用使迭代器it失效：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void zone_manager::deserialize( JsonIn &jsin )
{
    jsin.read( zones );
    for( auto it = zones.begin(); it != zones.end(); ++it ) {
        const zone_type_id zone_type = it->get_type();
        if( !has_type( zone_type ) ) {
            zones.erase( it );
            debugmsg( "Invalid zone type: %s", zone_type.c_str() );
        }
    }
}

libstdc++中向量的迭代器是指向向量后备缓冲区的指针。erase方法将所有超过擦除迭代器的指针向左移动一位，覆盖擦除的对象，并递减向量的末尾。

如果向量只包含一个元素，vec.end()变得与vec.begin()相同。在示例失效中，在第一个循环迭代结束时，迭代器递增到vec.begin()之后的地址。这意味着继续条件it != zones.end()成立，因此我们进入循环，迭代器引用堆上后备缓冲区之后存在的任何内存！由于Cataclysm的复杂性，堆布局和崩溃不是确定性的，但适当修改的游戏保存经常导致解引用无效地址的分段错误。

虽然这是一个相对良性的例子，但这类问题带来的威胁并非理论上的；高价值目标中的迭代器失效bug之前已被武器化。

CodeQL

CodeQL是GitHub开发的一个静态分析框架，允许您使用类似SQL的语法查询代码库。它有一个面向对象的类系统，其中谓词定义逻辑属性和关系。标准库提供了一组全面的类，允许查询各种代码属性和模式。

可以为几乎所有编译的代码构建CodeQL数据库。GitHub在lgtm.com维护了一个他们从公共仓库构建的数据库索引，可以在他们的站点上或使用CodeQL CLI本地查询。还有一个Visual Studio Code扩展用于检查查询结果。

Itergator包括查询和库，允许审计人员在他们自己的查询中使用Itergator的类。

检测迭代器失效

使用静态分析检测迭代器失效提出了几个挑战。上面的例子很简单，但失效可能嵌套在许多函数调用深处，周围有复杂的逻辑。一些迭代器在循环外声明和失效，导致流检测成本高昂，且没有大量误报。查询的可扩展性也很重要：代码库通常有自己的可迭代类型，需要检测其失效约束。

CodeQL的全局数据流库和对递归的支持使复杂的控制流分析易于编写。Itergator能够构建所有可能失效函数调用的图（那些可能导致调用失效函数的调用，如std::vector::push_back）并定义用于查询的类：

  • Iterator：存储迭代器的变量
  • Iterated：集合被迭代的位置，例如vec在vec.begin()中
  • Invalidator：迭代器范围内的可能失效函数调用
  • Invalidation：直接使迭代器失效的函数调用

InvalidationFlows查询通过数据流关联这些类以定位可能的失效。要查询非标准迭代类型，您只需扩展PotentialInvalidation类，该类作为抽象类，定义为其子类的并集。例如，这里是析构函数的失效定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class PotentialInvalidationDestructor extends PotentialInvalidation {
    PotentialInvalidationDestructor() {
        this instanceof MemberFunction
        and this.getName().matches("~%")
    }

    override predicate invalidates(Iterated i) {
        i.getType().refersTo(this.getParentScope())
    }
}

这些子类可以在您的查询或导入的库中的任何地方定义；STL类的定义已包含在Itergator中。Itergator中的一个实用查询IteratedTypes标识了要指定失效约束的类型。

Itergator开发的大部分需要在GitHub上找到固定的迭代器失效bug并尝试复现它们。Google的一个正则表达式库中一个特别棘手的bug体现了这个项目的挑战：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct Frame {
  Frame(Regexp** sub, int nsub)
      : sub(sub),
        nsub(nsub),
        round(0) {}

  Regexp** sub;
  int nsub;
  int round;
  std::vector<Splice> splices;
  int spliceidx;
};

int Regexp::FactorAlternation(Regexp** sub, int nsub, ParseFlags flags) {
  std::vector<Frame> stk;
  stk.emplace_back(sub, nsub);

  for (;;) {
    ...
    auto& splices = stk.back().splices;
    auto& spliceiter = stk.back().spliceiter;

    if (splices.empty()) {
      round++;
    } else if (spliceiter != splices.end()) {
      stk.emplace_back(spliceiter->sub, spliceiter->nsub);
      continue;
  } else { ... }

    switch (round) { ... }

    if (splices.empty() || round == 3) {
      spliceiter = splices.end();
    } else {
      spliceiter = splices.begin();
    }
  }
}

此函数声明stk，一个帧的向量，每个帧有一个splices向量和一个spliceiter迭代器。迭代器开始时未初始化，仅在循环第一次迭代结束时分配值（第32-36行）。失效发生的位置不明显；它不是对splices的直接操作，而是第26行添加到stk的元素。如果stk的后备缓冲区已满，它会被重新分配，并且Frame对象被复制，导致每个splices向量重新分配。由于continue语句，spliceiter从未重新初始化，并且在下一个循环迭代中使用失效的迭代器。

此失效发生在循环的三次迭代中：首先初始化迭代器，然后失效，最后使用。失效函数调用是在存储在向量中的对象的成员上执行的；确认这是迭代器引用的相同向量将极其复杂。跨所有三次执行跟踪控制流是可能的但成本高昂，并且查询在大型代码库上运行变得不切实际。

我对这些问题的解决方案是搜索失效必要但不充分的条件。例如，我验证了相同的变量——而不是值——可以流向迭代和失效的位置。虽然这引入了大量误报，但基于重复模式的自动过滤和添加“重要性”值使得搜索结果非常易于管理，同时仍然识别复杂的失效，如上面的例子。

CodeQL的缓存和优化也意味着Itergator可以查询大型代码库，如Apple的Swift LLVM分支，并找到深度失效。Itergator识别了以下bug，该bug在几个月前无意中在上游修复，其中失效深度为12个函数调用。InvalidationFlows为我们提供了迭代和失效位置；然后，经过进一步调查，包括自定义路径查询，我们可以识别必要的控制流：

然后我们可以构建一个复现：

步骤1：使用未定义符号和引用链接器脚本的延迟加载位码运行LLVM链接器。

1

./ld.lld --no-threads --undefined asdf --undefined fawef --start-lib ~/lib.bc --end-lib ~/a.o

步骤2到13：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

handleUndefined
lld::elf::Symbol::fetch() const
lld::elf::LazyObjFile::fetch()
lld::elf::parseFile(lld::elf::InputFile*)
doParseFile<llvm::object::ELFType<1, true> >
void lld::elf::BitcodeFile::parse<llvm::object::ELFType<1, true> >()
addDependentLibrary
lld::elf::LinkerDriver::addFile(llvm::StringRef, bool)
lld::elf::readLinkerScript(llvm::MemoryBufferRef)
readLinkerScript
readExtern
std::vector<llvm::StringRef>::push_back(llvm::StringRef&&)

步骤14：获利。

1
2
3
4
5
6
7
8
9

==332005==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000004160 at pc 0x556f81e36288 bp 0x7ffd14c663f0 sp 0x7ffd14c663e0
READ of size 16 at 0x603000004160 thread T0
    #0 0x556f81e36287 in void 
lld::elf::LinkerDriver::link<llvm::object::ELFType<(llvm::support::endianness)1, true> >(llvm::opt::InputArgList&) (/home/kmh/llvm-project/build/bin/lld+0x1d53287)
    #1 0x556f81ddaa10 in lld::elf::LinkerDriver::main(llvm::ArrayRef<char const*>) /home/kmh/llvm-project/lld/ELF/Driver.cpp:514
    #2 0x556f81ddc3b6 in lld::elf::link(llvm::ArrayRef<char const*>, bool, llvm::raw_ostream&, llvm::raw_ostream&) /home/kmh/llvm-project/lld/ELF/Driver.cpp:111
    #3 0x556f8186cda8 in main /home/kmh/llvm-project/lld/tools/lld/lld.cpp:154
    #4 0x7f1f70d1b151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
    #5 0x556f8186861d in _start (/home/kmh/llvm-project/build/bin/lld+0x178561d)

结论

Itergator是一个强大的工具，用于检测任何大小代码库中的复杂迭代器失效。使用CodeQL的声明式查询语言非常棒，尽管偶尔有引擎bug，因为它结合了我已经熟悉的概念，使静态分析易于上手。总会有改进和更多bug要猎取，但我对我的结果非常满意。

最后，我要感谢我的导师Josh和Trail of Bits的其他人，使这个夏天变得美好。我可以明确地说，Trail of Bits是我工作过的最好的地方！如果您有任何问题，或只是想聊天，请在Twitter @themalwareman上给我发消息。

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次