CodeQL C++ 范围分析演进：SimpleRangeAnalysis 对无符号乘法、常量乘法的扩展与自定义规则机制

• 静态分析
• SAST
• 应用安全
• 漏洞扫描
• 代码质量

本文围绕 CodeQL 仓库中 C++ 查询库的一次重要变更记录展开：SimpleRangeAnalysis范围分析库新增了对无符号数乘法、常量乘法、引用类型函数参数、不等比较收窄范围以及if (x)布尔判零等语言构造的支持，并且首次开放了通过SimpleRangeAnalysisExpr抽象类注入自定义范围规则的扩展点。读完本文，你将理解这些能力背后的格（lattice）抽象解释原理、widening 终止性设计，并能参考仓库中的现成示例为自己的查询添加范围分析扩展。

1. 变更概览：五项新语法支持与自定义规则能力

该变更记录（2020-09-29-range-analysis-rollup.md）面向 lgtm 与 codescanning 两个平台，其核心内容可以概括为两部分：

第一部分：新支持的语言构造。SimpleRangeAnalysis库在此前不支持五类 C++ 语言构造，本次变更全部补齐：

1. 无符号数的乘法（multiplication of unsigned numbers）；
2. 与常量相乘（multiplication by a constant）；
3. 引用类型的函数参数（reference-typed function parameters）；
4. 用“变量不等于其值域端点”的比较收窄范围——例如x != c且c是x的当前下界时，可将下界向前推进一格；
5. 用if (x)或if (!x)这类布尔上下文测试“是否等于零”。

变更说明同时指出，这些改进主要影响三个查询：cpp/constant-comparison、cpp/comparison-with-wider-type和cpp/integer-multiplication-cast-to-long。

第二部分：可扩展性。库从此可以接受用户自定义规则，官方示例存放在变更记录所列的cpp/ql/src/experimental/semmle/code/cpp/rangeanalysis/extensions/目录下。需要说明的是，在当前的仓库结构中，这些示例已经迁移到了cpp/ql/lib/experimental/semmle/code/cpp/rangeanalysis/extensions/，而抽象接口则位于cpp/ql/lib/experimental/semmle/code/cpp/models/interfaces/。

2. 原理基础：在 QL 中实现范围分析的三个关键设计

要理解这次变更的价值，先看 SimpleRangeAnalysis.qll 文件头部注释对算法本身的描述。范围分析通常是对“值域格”的抽象解释——每个表达式的抽象值是一对浮点数(lowerBound, upperBound)。直接用格求最小不动点会遇到收敛过慢的问题，文件注释中给出的经典反例是：

int count = 0; for (; p; p = p->next) { count = count + 1; }

count的值域从(0,0)出发，每轮不动点迭代只向上推进一格的边界：(0,1)、(0,2)……直到maxInt，格的高度几乎无界。

库给出的对策有三点，全部可以直接在源码中验证：

1. 固定 widening 边界集。当某个定义“递归地依赖自身”（通过defDependsOnDef的传递闭包检测，见 SimpleRangeAnalysis.qll 中的defDependsOnDefTransitively与isRecursiveDef），就把它的边界舍入到一个固定集合。下界集合是2, 1, 0, -1, -2, -8, -16, -128, -256, -32768, -65536, typeLowerBound, -Inf，上界集合是对称的-2, -1, 0, 1, 2, 7, 15, 127, 255, 32767, 65535, typeUpperBound, +Inf（wideningLowerBounds / wideningUpperBounds）。注释明确说这与抽象解释中的 widening 技术类似，但因为 QL 无法查看上一轮迭代的边界，精度略低——例如 widening 可能推出下界-11，而这里只能近似为-16。
2. 用浮点数表示边界。注释解释了动机：浮点不会溢出回绕，且可以通过“边界落在类型可表示范围之外”直接检测正/负溢出（getTruncatedLowerBounds与getTruncatedUpperBounds分别处理了这种不可表示边界的截断，见 SimpleRangeAnalysis.qll）。
3. 先收集边界集合、后聚合。由于 QL 不允许在递归子表达式上做聚合（aggregate），递归阶段为每个表达式产生“一组下界”和“一组上界”，最小下界与最大上界在递归结束后才计算。这条限制还引出了一个性能护栏：BoundsEstimate模块在分析前估计边界数量，一旦超过2^29的上限（getBoundsLimit，SimpleRangeAnalysis.qll）就提前启用 widening，注释说明该阈值是“经验性地选取到足以避免在特定客户数据库上超时”的值。

理解这三点后，本次变更的五项新支持就不再是“功能列表”，而是格上每一类算术/控制流算子的边界传播规则被逐一补全的过程。

3. 新支持语法逐一对照源码

3.1 无符号数乘法：下界相乘、上界相乘

无符号乘法之所以值得单独建模，是因为它的边界传播比有符号乘法更简单——两个操作数都非负，所以“下界×下界、上界×上界”就是精确答案，不存在符号翻转问题。源码中UnsignedMulExpr类要求结果类型是IntegralType且无符号，并刻意排除已按常量乘处理的表达式以避免重叠（SimpleRangeAnalysis.qll）：

private class UnsignedMulExpr extends MulExpr { UnsignedMulExpr() { this.getType().(IntegralType).isUnsigned() and // Avoid overlap. It should be slightly cheaper to analyze // `MulByConstantExpr`. not this instanceof MulByConstantExpr } }

对应地，getLowerBoundsImpl对UnsignedMulExpr取xLow * yLow，getUpperBoundsImpl取xHigh * yHigh（SimpleRangeAnalysis.qll 与 L1352-L1357）。x *= y形式的UnsignedAssignMulExpr也按同样规则处理。变更前后对比的意义在于：此前遇到unsigned乘法时表达式会落入“不可分析”分支，下界直接退化为exprMinVal、上界退化为exprMaxVal，所有依赖精确边界的下游判断都会失效；现在这条路径能给出真实边界。

3.2 与常量相乘：把符号与量级分离处理

“乘以一个常量”被拆成了四个协作的谓词/类，核心思想是：乘正数与乘负数对上下界的作用是相反的，必须分开传播。

• MulByConstantExpr（SimpleRangeAnalysis.qll）：恰好一个操作数是常量的乘法表达式，暴露出常量值getConstant()与非常量操作数getOperand()；
• effectivelyMultipliesByPositive/effectivelyMultipliesByNegative（SimpleRangeAnalysis.qll）：除直接乘法外，还覆盖“等效”乘常量的情形——一元+x（乘 1）、一元-x（乘 -1）、逗号表达式取右操作数、StmtExpr取结果表达式，这些是真实 C/C++ 代码里常见的惯用法；
• AssignMulByConstantExpr及其正/负子类的划分，用于处理x *= c。

边界传播规则体现在getLowerBoundsImpl/getUpperBoundsImpl中：乘正数时，下界 = 常量 × 操作数下界，上界 = 常量 × 操作数上界；乘负数时上下界交换来源（用操作数的上界算下界、下界算上界）。这套规则同样是x *= c复合赋值语句的基础。

3.3 引用类型函数参数

变更记录列出的第三项是“引用类型函数参数”的支持。从当前源码结构看，范围分析统一经由 SSA 信息工作：变量访问e只要能在RangeSsaDefinition中找到对应定义（e = def.getAUse(v)，即 analyzableExpr 中“允许变量访问，前提是它有 SSA 信息”这一分支），就可以通过getDefLowerBounds/getDefUpperBounds拿到边界。引用类型参数在底层同样有 SSA 定义，可以推断该项改进正是让这类定义进入可分析集合的结果——具体到边界传播，与按值参数走的是同一套规则。

3.4 “不等于端点”收窄范围：不等比较的 phi 节点

第四项“比较变量不等于其值域端点，从而把范围收窄一格”对应源码中的isNEPhi机制。getPhiLowerBounds中有一段精确实现了这个语义（SimpleRangeAnalysis.qll）：

exists(VariableAccess access, float neConstant, float lower | isNEPhi(v, phi, access, neConstant) and lower = getTruncatedLowerBounds(access) and if lower = neConstant then result = lower + 1 else result = lower )

含义是：如果在某个分支上已知x != c，而该分支入口处x的下界恰好就是c，那么在这个分支里x的下界可以推进到c + 1。上界方向对称处理。这正是“narrowing the range by one”的出处，它对循环不变量、数组下标验证这类场景尤为有用。

3.5if (x)/if (!x)的判零语义

第五项支持的是布尔上下文中“非零即真”的语义。C/C++ 中if (x)、!x、逻辑运算、(bool)x都隐式测试x == 0。实现位于boolConversionLowerBound/boolConversionUpperBound（SimpleRangeAnalysis.qll）：

• 下界：若expr的值域覆盖 0，下界为 0；若能证明值域不含 0（下界 > 0 或上界 < 0），下界为 1；若类型非算术类型（如指针），下界保守取 0；
• 上界：若值域可能为 0，上界取 0 与 1 都可能；只有能证明“永远非零”（下界 > 0 或上界 < 0）时上界才确定为 1，反之能证明“永远为零”时上界为 0。

exprIsUsedAsBool谓词（SimpleRangeAnalysis.qll）先把“会被当作布尔用”的表达式集合圈定下来——逻辑运算的子表达式、一元逻辑操作数、条件表达式条件、bool转换——以避免对无关表达式做无谓的边界计算。这个机制让分析器能理解“进入if (x)分支意味着x != 0、进入if (!x)分支意味着x == 0”，并据此在分支内收窄后续表达式。

4. 自定义规则扩展机制：SimpleRangeAnalysisExpr 与官方示例

本次变更的另一半是开放扩展点。抽象接口定义在 SimpleRangeAnalysisExpr.qll：

/** * An expression for which a range can be deduced. Extend this class to add * functionality to the range analysis library. */ abstract class SimpleRangeAnalysisExpr extends Expr { /** Gets the lower bound of the expression. */ abstract float getLowerBounds(); /** Gets the upper bound of the expression. */ abstract float getUpperBounds(); /** * Holds if the range this expression depends on the definition `srcDef` * for StackVariable `srcVar`. ... */ predicate dependsOnDef(RangeSsaDefinition srcDef, StackVariable srcVar) { none() } /** * Holds if this expression depends on the range of its unconverted * subexpression `child`. ... * For example, when modeling a function call whose return value depends on * all of its arguments, implement this predicate as * `child = this.getAnArgument()`. */ abstract predicate dependsOnChild(Expr child); }

实现一个扩展规则需要：

1. 让自定义类同时继承SimpleRangeAnalysisExpr和具体的Expr子类（如FunctionCall、SubExpr），用类匹配条件圈定要建模的表达式；
2. 覆写getLowerBounds()/getUpperBounds()，其中对子表达式取边界时必须通过getFullyConvertedLowerBounds/getFullyConvertedUpperBounds递归（注释明确要求）；
3. 覆写dependsOnChild(Expr child)声明依赖了哪些未转换子表达式的范围——注释特别强调：不声明周期依赖会导致“简单情况能跑、复杂代码上无限循环”。

主库 SimpleRangeAnalysis.qll 在上下界计算的最后一支统一调用SimpleRangeAnalysisExpr的getLowerBounds()/getUpperBounds()，且内置的边界传播规则明确以not expr instanceof SimpleRangeAnalysisExpr收尾，即用户扩展优先于内置规则，且不同扩展类之间互不干扰。

变更记录中提到的示例目录（现路径为 extensions 目录）给出了两个可以直接参照的最小实现：

• StrlenLiteralRangeExpr.qll：对字面量字符串的strlen调用返回精确常量范围——getLowerBounds与getUpperBounds都等于字符串字面量长度，dependsOnChild返回none()，因为范围不依赖任何子表达式；
• SubtractSelf.qll：匹配x - x（要求两侧显式转换后是同一个变量的访问，排除myInt - (unsigned char)myInt这类类型不同的情形），上下界都返回 0。

该目录还有ConstantBitwiseAndExprRange.qll、ConstantShiftExprRange.qll、RangeNode.qll等更多示例，覆盖了“子表达式为常量时结果可精确推断”这一最常见的扩展模式。

5. 对下游查询的影响与验证路径

变更记录说明这些改进“主要影响”三个查询，它们在仓库中的位置与当前状态可以逐一核对：

• cpp/comparison-with-wider-type：实现在 ComparisonWithWiderType.ql（@id与@name见文件头 L1-L15），直接import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis（L20）。窄类型与宽类型在循环条件中比较的问题，其判定质量直接取决于范围分析能否给出循环变量的精确边界；
• cpp/integer-multiplication-cast-to-long：对应 IntMultToLong.ql，同样构建在SimpleRangeAnalysis之上。整数乘法结果转换到long是否安全的判断，本质上是“乘法上界是否落在 long 可表示范围内”的范围判断——无符号乘法与常量乘法的支持使这类判断从保守退化变为精确；
• cpp/constant-comparison：比较双方是否恒为常量（或恒定大小关系）的判定，依赖上下界是否收敛为同一点，因此五项新支持全部都会提升它的判定率。

除这三个查询外，当前仓库中SnprintfOverflow.ql、OverflowStatic.ql、ImproperArrayIndexValidation.ql、InconsistentLoopDirection.ql等也都在SimpleRangeAnalysis之上构建，属于同一能力的受益面。库本身的回归测试位于 SimpleRangeAnalysis_tests.cpp，可作为理解每类构造预期边界的参考。

6. 小结：这次变更解决的核心问题

回到变更记录本身：它解决的其实是两个层面的问题。第一层是精度——无符号乘法、常量乘法、引用参数、NE 收窄、布尔判零这五类构造补全后，C++ 代码中大量原本落入“不可分析→边界退化为类型全范围”的表达式开始产生精确边界，直接改善了三个核心查询的查全率与查准率。第二层是可扩展性——SimpleRangeAnalysisExpr把“我知道这个表达式的范围”从库的内置知识变成可注入的领域知识，扩展者只需回答三个问题：这个表达式是什么、它的上下界是多少、它依赖哪些子表达式的范围。对基于 CodeQL 编写 C++ 自定义查询的开发者而言，这套机制是向范围分析库贡献项目特有算术语义的标准入口。

• 静态分析
• SAST
• 应用安全
• 漏洞扫描
• 代码质量