检测迭代器失效的CodeQL方案
迭代器定义
迭代器是C++中遍历容器内容的标准方式，支持两种基本操作：解引用获取元素和递增获取下一个元素的迭代器。例如：
1
2
3
4
|
std::vector<int> vec{1, 2, 3, 4, 5};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
|
C++11引入了更简洁的语法：
1
2
3
|
for (auto i : vec) {
std::cout << i << " ";
}
|
迭代器失效问题
当容器发生修改（如添加/删除元素）时，迭代器会失效。使用失效迭代器将导致未定义行为。例如：
1
2
3
4
5
6
7
8
9
|
void zone_manager::deserialize(JsonIn &jsin) {
jsin.read(zones);
for(auto it = zones.begin(); it != zones.end(); ++it) {
if(!has_type(it->get_type())) {
zones.erase(it); // 迭代器在此失效
debugmsg("Invalid zone type");
}
}
}
|
在libstdc++中，vector迭代器是指向其缓冲区的指针。erase操作会使后续指针左移，当vector只有一个元素时，vec.end()将与vec.begin()相同，导致后续迭代访问非法内存。
CodeQL技术
CodeQL是GitHub开发的静态分析框架，使用类SQL语法查询代码库。其特点包括：
- 面向对象的类系统
- 支持递归和全局数据流分析
- 可扩展的标准库
- 支持构建几乎所有可编译代码的数据库
迭代器失效检测
检测迭代器失效的主要挑战：
- 失效可能嵌套在多层函数调用中
- 迭代器声明和失效可能发生在循环外部
- 需要支持自定义可迭代类型
Itergator解决方案：
- 构建潜在失效函数调用图
- 定义核心类：
Iterator：存储迭代器的变量Iterated：被迭代的集合Invalidator：可能导致失效的函数调用Invalidation：直接使迭代器失效的调用
示例：析构函数的失效定义
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())
}
}
|
复杂案例解析
Google正则表达式库中的深层失效案例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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); // 导致splices重新分配
continue; // 跳过迭代器重新初始化
}
// 后续使用可能失效的迭代器
}
}
|
该案例中，失效跨越三个循环迭代，通过stk的重新分配间接导致splices迭代器失效。
实际应用成果
Itergator在LLVM链接器中发现的深层失效（12层函数调用）：
- 链接器处理未定义符号
- 经过11层函数调用链
- 最终在
std::vector::push_back导致迭代器失效
- 触发AddressSanitizer报错：heap-use-after-free
结论
Itergator能够有效检测各种复杂度的迭代器失效问题，其优势包括：
- 处理任意规模代码库
- 可扩展的自定义规则
- 直观的结果展示
- 结合数据流分析追踪深层问题
该方法虽然会产生一定误报，但通过模式过滤和重要性评分机制，使结果审查变得可行。