本文介绍了Trail of Bits开发的Itergator工具，一个基于CodeQL的静态分析框架，专门用于检测C++中的迭代器失效问题。迭代器失效是C++中常见的隐蔽错误，可能导致安全漏洞。Itergator通过定义Iterator、Iterated、Invalidator和Invalidation等CodeQL类，能够追踪迭代器的生命周期及其可能失效的函数调用。该工具克服了失效嵌套、循环外失效和自定义类型支持等检测挑战，并通过实际案例证明了其在游戏、正则表达式库和LLVM链接器中发现bug的有效性。尽管存在误报，但其高效的结果审查机制使其成为检测此类复杂问题的强大工具。

🎯 **迭代器失效的本质与危害**：迭代器是C++遍历容器的标准方式，但当容器内容发生改变（如增删元素）时，迭代器可能失效。使用失效的迭代器会导致未定义的行为，这在实际开发中是难以察觉但潜在危险的，常被利用于制造安全漏洞。

💡 **Itergator工具的CodeQL实现**：Itergator是一个利用CodeQL静态分析框架开发的工具集，它定义了Iterator、Iterated、Invalidator和Invalidation等核心CodeQL类。通过这些类，可以追踪迭代器的使用、被迭代的集合以及可能导致其失效的函数调用，从而构建失效函数调用图。

🚀 **应对复杂检测挑战**：Itergator能够有效应对迭代器失效检测中的多重挑战，包括失效可能嵌套在多层函数调用中、迭代器在循环外声明和失效，以及需要支持自定义的可迭代类型。CodeQL的全局数据流分析和递归查询能力是实现这些功能的基础。

🏆 **实际应用与成效**：Itergator在多个真实项目（如Cataclysm游戏、Google正则表达式库、LLVM链接器）中发现了多种迭代器失效bug，包括多层嵌套和深度函数调用链中的失效。这证明了该工具在复杂场景下的强大检测能力，尽管存在少量误报，但通过优化配置可实现高效审查。

使用CodeQL检测迭代器失效问题

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

迭代器基础

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

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

迭代器失效问题

当容器发生修改（如添加或删除元素）后，迭代器会失效。使用失效迭代器会导致未定义行为。例如：

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);  // 迭代器在此失效        }    }}

CodeQL解决方案

CodeQL是GitHub开发的静态分析框架，使用类SQL语法查询代码库。Itergator包含查询和库，允许审计人员在自己的查询中使用Itergator的类：

Iterator：存储迭代器的变量Iterated：被迭代的集合Invalidator：可能导致迭代器失效的函数调用Invalidation：直接使迭代器失效的函数调用

检测挑战与解决方案

检测迭代器失效面临多个挑战：

失效可能嵌套在多层函数调用中迭代器可能在循环外声明和失效需要支持自定义可迭代类型

通过CodeQL的全局数据流库和递归支持，Itergator能够构建潜在失效函数调用图。对于非标准迭代类型，只需扩展PotentialInvalidation抽象类。

实际案例

Itergator发现了多个现实项目中的bug，包括：

Cataclysm游戏中的简单失效案例Google正则表达式库中的复杂三层循环失效LLVM链接器中12层函数调用深的失效

结论

Itergator是检测复杂迭代器失效问题的强大工具。尽管存在一些误报，但通过自动过滤和"重要性"值设置，结果审查变得非常高效。CodeQL的声明式查询语言使得静态分析易于上手。

"Trail of Bits是我工作过的最好的地方！" —— Kevin Higgs