LLVM 之 Clang 静态分析器篇（4）：程序缺陷诊断——除零错误

Author: stormQ

Created: Friday, 23. April 2021 07:39PM

Last Modified: Sunday, 30. May 2021 10:32AM

摘要

本文基于release/12.x版本的 LLVM 源码，研究了 Clang 静态分析器中除零错误检查器的工作原理。从而，有助于按照自身需求修改或扩展 Clang 静态分析器。

研究过程

需要订阅哪些程序点

实现缺陷诊断代码逻辑

如何调试

除零错误检查器的源码实现目录如下：

源文件为clang/lib/StaticAnalyzer/Checkers/DivZeroChecker.cpp

需要订阅哪些程序点

在 Clang 静态分析器中，检查器类DivZeroChecker用于实现程序缺陷——除零错误的诊断功能，其源码实现如下（定义在 clang/lib/StaticAnalyzer/Checkers/DivZeroChecker.cpp 文件中）：

25 namespace {
26 class DivZeroChecker : public Checker< check::PreStmt<BinaryOperator> > {
// 省略 ...
33 };
34 } // end anonymous namespace

从上面的代码可以看出，该检查器类仅订阅了程序点clang::ento::check::PreStmt<BinaryOperator>。

由于除零错误只可能在除法或取模运算时发生。因此，需要在识别出二元运算时通知检查器。

在 Clang 生成的抽象语法树中，表示二元运算的节点为clang::BinaryOperator类。并且，二元运算属于表达式，而表达式又属于语句。

因此，需要订阅的候选程序点有两种：clang::ento::check::PreStmt<BinaryOperator>和clang::ento::check::PostStmt<BinaryOperator>。前者表示在分析器引擎处理二元运算语句之前调用检查器，后者表示在分析器引擎处理二元运算语句之后调用检查器。

Clang 静态分析器中所实现的检查器订阅的是前者。那么，如果订阅后者是否可行呢？

我们可以实现一个自定义的检查器core.DivideZeroV2进行验证。该检查器的不同之处在于订阅程序点clang::ento::check::PostStmt<BinaryOperator>，其他基本保持不变。

注：关于实现自定义检查器的详细过程，可参考笔者的另一篇文章：《LLVM 之 Clang 静态分析器篇（2）：如何扩展 Clang 静态分析器》。

经过实际测试发现，对于同一个测试程序div-zero-1.cpp而言，这两种检查器的缺陷诊断结果是相同的，如下所示。

div-zero-1.cpp 的内容如下：

int func(int a) {
  return a ? 0 : 1;
}

int div_zero_ts_1(int a) {
  if (a)
    return a % func(a);
  return a / func(a);
}

int div_zero_ts_2(int a) {
  return a / (a - a);
}

int div_zero_ts_3(int a) {
  return 1 / (a ? 1 : 0);
}

Clang 原有检查器core.DivideZero的缺陷诊断结果：

$ clang -cc1 -w -analyze -analyzer-checker=core.DivideZero div-zero-1.cpp
div-zero-1.cpp:7:14: warning: Division by zero [core.DivideZero]
    return a % func(a);
           ~~^~~~~~~~~
div-zero-1.cpp:12:12: warning: Division by zero [core.DivideZero]
  return a / (a - a);
         ~~^~~~~~~~~
div-zero-1.cpp:16:12: warning: Division by zero [core.DivideZero]
  return 1 / (a ? 1 : 0);
         ~~^~~~~~~~~~~~~
3 warnings generated.

自定义检查器core.DivideZeroV2的缺陷诊断结果：

$ clang -cc1 -w -analyze -analyzer-checker=core.DivideZeroV2 div-zero-1.cpp
div-zero-1.cpp:7:14: warning: Division by zero [core.DivideZeroV2]
    return a % func(a);
           ~~^~~~~~~~~
div-zero-1.cpp:12:12: warning: Division by zero [core.DivideZeroV2]
  return a / (a - a);
         ~~^~~~~~~~~
div-zero-1.cpp:16:12: warning: Division by zero [core.DivideZeroV2]
  return 1 / (a ? 1 : 0);
         ~~^~~~~~~~~~~~~
3 warnings generated.

因此，对于测试程序div-zero-1.cpp而言，检查器类DivZeroChecker订阅程序点clang::ento::check::PostStmt<BinaryOperator>也可以实现相同的缺陷诊断效果。

需要注意的是，《Clang Static Analyzer: A Checker Developer's Guide》(Artem Degrachev) 中提到：订阅程序点check::PostStmt<T>时，如果模板参数T是表达式，那么可能存在回调函数被调用时其子表达式已经被移除的情况。其原文如下：

void  checkPostStmt(const T *S, CheckerContext &C) const;

This callback template is similar to check::PreStmt<T>, and the only difference is that it fires after the statement has been modeled. 
If S is an expression, this callback allows to obtain the symbolic value of S itself; however, values of sub-expressions might have been already removed from the environment.

那么，在回调函数被调用时子表达式已经被移除的程序是怎样的呢？【遗留问题】

返回上一级

实现缺陷诊断代码逻辑

程序缺陷——除零错误的诊断代码逻辑是在类DivZeroChecker的成员函数checkPreStmt()内实现的。接下来，逐行分析其源码实现。

step 1： 判断二元运算的操作符

DivZeroChecker.cpp 中第 59~64 行的代码如下：

59   BinaryOperator::Opcode Op = B->getOpcode();
60   if (Op != BO_Div &&
61       Op != BO_Rem &&
62       Op != BO_DivAssign &&
63       Op != BO_RemAssign)
64     return;

类clang::BinaryOperator中的成员函数getOpcode()的作用为：获取二元运算的操作符。

注：这里直接给出了结论，具体研究过程可参考笔者的另一篇文章：《LLVM 之 Clang 源码分析篇（10）：clang::BinaryOperator 类》。

因此，上述代码的代码逻辑为：如果二元运算的操作符不是/（除）、%（取模）、/=（除等于）、%=（取模等于）中的任意一个，则结束诊断。这样做，是因为除零错误只可能在除法或取模运算时发生。

step 2： 判断右操作数的类型

DivZeroChecker.cpp 中第 66~67 行的代码如下：

66   if (!B->getRHS()->getType()->isScalarType())
67     return;

需要注意的是， 类clang::QualType通过重载运算符->（重载函数的返回值类型为const Type *），从而调用类clang::Type中的成员函数。

类clang::Type中的成员函数isScalarType()的作用为：判断是否为标量类型。

注：这里直接给出了结论，具体研究过程可参考笔者的另一篇文章：《LLVM 之 Clang 源码分析篇（11）：clang::Type 类》。

因此，上述代码的代码逻辑为：如果二元运算的右操作数不是标量类型，则结束诊断。更准确地讲，这里判断的是二元运算中右操作数的求值结果是否为标量类型。

需要注意的是， 虽然 C++ 语言中可以重载运算符/（除）、%（取模）、/=（除等于）、%=（取模等于）。但如果出现重载这些运算符的情况，其二元运算表达式的整体类型为clang::CXXOperatorCallExpr类而不是clang::BinaryOperator类，意味着不会调用除零错误检查器。

另外，在 C/C++ 语言中，浮点数除法运算的分母为零是合法的，并且浮点数不支持取模运算。

那么，如果仅判断右操作数的的求值结果是否为整型，是否可行呢？如果不可以这样做，那么会带来哪些问题呢？【遗留问题】

类clang::Type中的成员函数isIntegerType()用于判断是否为整型。其源码实现如下（定义在 clang/include/clang/AST/Type.h 文件中）：

6971 inline bool Type::isIntegerType() const {
6972   if (const auto *BT = dyn_cast<BuiltinType>(CanonicalType))
6973     return BT->getKind() >= BuiltinType::Bool &&
6974            BT->getKind() <= BuiltinType::Int128;
6975   if (const EnumType *ET = dyn_cast<EnumType>(CanonicalType)) {
6976     // Incomplete enum types are not treated as integer types.
6977     // FIXME: In C++, enum types are never integer types.
6978     return IsEnumDeclComplete(ET->getDecl()) &&
6979       !IsEnumDeclScoped(ET->getDecl());
6980   }
6981   return isExtIntType();
6982 }

step 3： 判断右操作数的符号

DivZeroChecker.cpp 中第 69~75 行的代码如下：

69   SVal Denom = C.getSVal(B->getRHS());
70   Optional<DefinedSVal> DV = Denom.getAs<DefinedSVal>();
71 
72   // Divide-by-undefined handled in the generic checking for uses of
73   // undefined values.
74   if (!DV)
75     return;

Clang 静态分析器的符号执行引擎中所使用的符号（由clang::ento::SVal类表示）主要可以分为以下四种：

已定义的符号，由clang::ento::DefinedSVal类表示。
未定义的符号，由clang::ento::UndefinedSVal类表示。
已知的符号，由clang::ento::KnownSVal类表示。
未知的符号，由clang::ento::UnknownSVal类表示。

因此，上述代码的代码逻辑为：如果二元运算的右操作数的求值结果不是已定义的符号，则结束诊断。

需要注意的是， Clang 静态分析器目前（即release/12.x版本）所实现的除零错误检查器，只判断了右操作数是否为已定义的符号的情况。然而，笔者发现这样的做法是存在缺陷的，即无法诊断出某些除零错误程序缺陷。

step 4： 判断右操作数的值

DivZeroChecker.cpp 中第 77~86 行的代码如下：

77   // Check for divide by zero.
78   ConstraintManager &CM = C.getConstraintManager();
79   ProgramStateRef stateNotZero, stateZero;
80   std::tie(stateNotZero, stateZero) = CM.assumeDual(C.getState(), *DV);
81 
82   if (!stateNotZero) {
83     assert(stateZero);
84     reportBug("Division by zero", stateZero, C);
85     return;
86   }

类clang::ento::ConstraintManager中的成员函数assumeDual()的作用为：用于假设符号在当前状态下的执行环境中的值。其函数行为如下：

如果符号的值为true的假设不成立，则返回ProgramStatePair((ProgramStateRef)nullptr, State)，表示符号的值为false。
否则，如果符号的值为false的假设不成立，则返回ProgramStatePair(State, (ProgramStateRef)nullptr)，表示符号的值为true。
否则，返回ProgramStatePair(StTrue, StFalse)，表示不确定符号的值是true还是false。

注：这里直接给出了结论，具体研究过程可参考笔者的另一篇文章：《LLVM 之 Clang 源码分析篇（7）：clang::ento::RangedConstraintManager 类》。

因此，上述代码的代码逻辑为：在当前状态下的执行环境中，如果二元运算的右操作数的求值结果为 0（对应地，局部变量stateNotZero的值为nullptr），则一定存在除零错误并报告该程序缺陷。

需要注意的是， 类clang::ento::ConstraintManager中的成员函数assumeDual()只能对已定义的符号的值进行假设。这一点从其函数声明——ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond)可以看出。

step 5： 判断符号是否被污染

DivZeroChecker.cpp 中第 88~93 行的代码如下：

88   bool TaintedD = isTainted(C.getState(), *DV);
89   if ((stateNotZero && stateZero && TaintedD)) {
90     reportBug("Division by a tainted value, possibly zero", stateZero, C,
91               std::make_unique<taint::TaintBugVisitor>(*DV));
92     return;
93   }

命名空间clang::ento::taint中的函数isTainted()的作用为：检查符号在给定状态下是否被污染。

因此，上述代码的代码逻辑为：在当前状态下的执行环境中，如果不确定二元运算的右操作数的求值结果是否为 0，并且右操作数所对应的符号被污染了，则可能存在除零错误并报告该程序缺陷。

step 6： 扩展可达程序图

DivZeroChecker.cpp 中第 95~97 行的代码如下：

95   // If we get here, then the denom should not be zero. We abandon the implicit
96   // zero denom case for now.
97   C.addTransition(stateNotZero);

类clang::ento::CheckerContext中的成员函数addTransition(ProgramStateRef, const ProgramPointTag *)的作用为：以当前节点作为前继节点扩展可达程序图。如果成功，则返回新创建的节点，并且符号执行引擎可以继续探索该执行路径；否则，返回当前节点。

注：这里直接给出了结论，具体研究过程可参考笔者的另一篇文章：《LLVM 之 Clang 源码分析篇（6）：clang::ento::CheckerContext 类》。

因此，上述代码的代码逻辑为：以当前节点作为前继节点创建一个新节点，并且该新节点的程序状态中包含：二元运算的右操作数的值不是 0。从而，其后继节点可以获知这一信息。

需要注意的是， 执行上述代码时，如果实参stateNotZero的值为当前节点的程序状态，那么实际上不会真正地扩展可达程序图。

step 7： 报告程序缺陷

DivZeroChecker.cpp 中第 43~56 行的代码如下：

43 void DivZeroChecker::reportBug(
44     const char *Msg, ProgramStateRef StateZero, CheckerContext &C,
45     std::unique_ptr<BugReporterVisitor> Visitor) const {
46   if (ExplodedNode *N = C.generateErrorNode(StateZero)) {
47     if (!BT)
48       BT.reset(new BuiltinBug(this, "Division by zero"));
49 
50     auto R = std::make_unique<PathSensitiveBugReport>(*BT, Msg, N);
51     R->addVisitor(std::move(Visitor));
52     bugreporter::trackExpressionValue(N, getDenomExpr(N), *R);
53     C.emitReport(std::move(R));
54   }
55 }

报告程序缺陷可以分为两类：1）报告程序缺陷（比如：内存泄露）后，分析器引擎可以继续探索该执行路径；2）报告程序缺陷（比如：解引用空指针）后，分析器引擎终止探索该执行路径。前者会用到clang::ento::CheckerContext::addTransition()函数，后者会用到clang::ento::CheckerContext::generateSink()或clang::ento::CheckerContext::generateErrorNode()函数。

上述代码的代码逻辑为：使用PathSensitiveBugReport报告程序缺陷代码是什么及其所在位置。另外，可以选择性使用BugReporterVisitor用于报告其他信息。

检查器core.DivideZeroV中报告程序缺陷的地方共两处。

1）第 1 处报告程序缺陷的地方

84     reportBug("Division by zero", stateZero, C);

上述代码实际只用了PathSensitiveBugReport而未用到BugReporterVisitor。这里因为，此处报告的程序缺陷——除零错误是确定发生的，并且PathSensitiveBugReport中包含的信息（程序缺陷代码是什么及其所在位置）已经足够了。

2）第 2 处报告程序缺陷的地方

90     reportBug("Division by a tainted value, possibly zero", stateZero, C,
91               std::make_unique<taint::TaintBugVisitor>(*DV));

上述代码不仅用到了PathSensitiveBugReport而且也用到了BugReporterVisitor。这里因为，此处报告的程序缺陷——除零错误是可能发生的，前者用于提供程序缺陷代码是什么及其所在位置，而后者用于提供其他信息（这里的taint::TaintBugVisitor会打印符号如何被污染的相关信息）。

返回上一级

如何调试

step 1： gdb 调试

1） gdb 调试文件

plugin.divzero.gdb 的内容如下：

file /usr/local/bin/clang
set args -cc1 -w -load ~/git-projects/llvm-project/build_ninja/lib/DivZeroCheckerPlugin.so -analyze -analyzer-checker=plugin.core.DivideZero div-zero-2.cpp
set listsize 20
set breakpoint pending on

start
b clang/lib/Analysis/plugins/CheckerDivZero/DivZeroChecker.cpp:88

注：为了提高编译和调试效率，本文调试分析的plugin.core.DivideZero检查器是作为插件实现的，其代码逻辑与原有的core.DivideZero检查器完全一致。

2）如何启动

$ gdb -q -x plugin.divzero.gdb

step 2： 辅助调试的 Clang API

Clang API	示例	作用
clang::Stmt::dump()	命令：p B->getRHS()->dump() 注：B 的数据类型为 const clang::BinaryOperator *	打印表达式的抽象语法树
clang::Type::getScalarTypeKind()	命令：p B->getRHS()->getType()->getScalarTypeKind() 注：B 的数据类型为 const clang::BinaryOperator *	打印表达式求值结果的标量类型
clang::ento::SVal::dump()	命令：p Denom.dump() 注：Denom 的数据类型为 clang::ento::SVal	打印符号
clang::ento::SVal::getRawKind()	命令：p Denom.getRawKind() 注：Denom 的数据类型为 clang::ento::SVal	打印符号的类型（包括基本类型和子类型）
clang::ento::SVal::getBaseKind()	命令：p Denom.getBaseKind() 注：Denom 的数据类型为 clang::ento::SVal	打印符号的基本类型
clang::ento::SVal::getSubKind()	命令：p Denom.getSubKind() 注：Denom 的数据类型为 clang::ento::SVal	打印符号的子类型
clang::Stmt::getStmtClass()	命令：p S->getStmtClass() 注：S 的数据类型为 clang::Stmt *	打印语句的类型
clang::ento::ExprEngine::ViewGraph()	命令：p C.Eng.ViewGraph(0) 注：C 的数据类型为 clang::ento::CheckerContext &	生成当前的可达程序图

step 3： 其他命令

1）生成可达程序图

$ clang -cc1 -w -analyze -analyzer-checker=debug.ViewExplodedGraph <-analyzer-checker=other-checker> <source-file>

使用示例：

$ clang -cc1 -w -analyze -analyzer-checker=debug.ViewExplodedGraph div-zero-2.cpp

2）可达程序图格式转换

将可达程序图从.dot转换为.png格式的命令如下：

$ dot -Tpng <dot-file> -o <png-file>

使用示例：

$ dot -Tpng /tmp/ExprEngine-0f1c65.dot -o ExprEngine-0f1c65.png

返回上一级

研究结论

Clang 静态分析器中除零错误检查器的工作原理为：识别非重载的除法和取模二元运算，并推导二元运算中右操作数的求值结果是否为 0。前者主要依赖于生成的抽象语法树，后者主要依赖于路径敏感的符号执行引擎。

References

下一篇：LLVM 之 Clang 静态分析器篇（5）：程序缺陷诊断——fopen 和 fclose API 误用

上一篇：LLVM 之 Clang 静态分析器篇（3）：检查器的整体工作机制

首页