使用CodeQL检测迭代器失效 - Trail of Bits博客
迭代器失效是C++中常见且微妙的一类错误，通常会导致可利用的漏洞。在我今年夏天的Trail of Bits实习期间，我开发了Itergator，这是一组用于分析和发现迭代器失效的CodeQL类和查询。
结果易于审计人员解读，提供诸如迭代器获取位置、失效位置以及指示误报可能性的重要性级别等信息。Itergator已用于在真实代码中发现错误，并且查询易于扩展以进行进一步分析。
迭代器定义
迭代器是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的复杂性，堆布局和崩溃不是确定性的，但适当修改的游戏保存经常导致解引用无效地址的分段错误。
虽然这是一个相对良性的例子，但这类问题带来的威胁不是理论上的；高价值目标中的迭代器失效错误以前已被武器化。
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上找到固定的迭代器失效错误并尝试重现它们。Google的一个正则表达式库中一个特别棘手的错误例证了这个项目的挑战：
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识别了以下错误，该错误在几个月前无意中在上游修复，其中失效深度达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的声明性查询语言非常棒，尽管偶尔有引擎错误，因为它结合了我已经熟悉的概念，使静态分析易于上手。总会有改进和更多错误需要寻找，但我对我的结果非常满意。
最后，我要感谢我的导师Josh和Trail of Bits的其他人，使这个夏天变得美好。我可以明确地说，Trail of Bits是我工作过的最好的地方！如果您有任何问题，或只是想聊天，请在Twitter @themalwareman上给我发消息。
如果您喜欢这篇文章，请分享：
Twitter
LinkedIn
GitHub
Mastodon
Hacker News