jywhy6's blog
0%

Clang Static Analyzer 介绍

Posted on Edited on In
Symbols count in article: 9.4k Reading time ≈ 16 mins.

Clang Static Analyer是一个开源的源代码分析工具，它以一些程序分析研究论文为基础，设计了名字-内存区域-值的三元内存模型、基于函数内联的过程间分析方法，综合了抽象语法树分析、控制流图分析、符号执行等漏洞扫描技术，可以高效地发现C、C++和Objective-C程序中的复杂漏洞，并提供可视化的触发漏洞的具体程序执行路径。

目前Clang Static Analyer可以作为命令行工具使用，也可以被集成在Xcode等集成开发环境中使用；在编译构建代码库时，可以调用Clang Static Analyer命令行工具对源代码进行漏洞检测；像Clang项目的其他部分一样，Clang Static Analyer被实现成一个C++的库的形式，使得它能被其他的工具和应用使用。

参考资料

学术论文

会议视频

官方文档

其他文档

Clang Static Analyzer的数据结构

Clang Static Analyzer以源代码为起点，将源代码转换为Clang AST (Clang的抽象语法树结构) ，然后生成Clang CFG (Clang的控制流图结构) ；随着程序的模拟执行，Clang的符号执行引擎会生成Exploded Graph (扩展图) ，详细记录程序的执行位置和程序当前状态信息；最后，在各个Checker (Clang Static Analyzer中可自定义的漏洞检查器) 回调函数检测到漏洞产生时，将基于Exploded Graph中的数据生成带漏洞触发路径的漏洞报告。Clang Static Analyzer各个数据结构之间的关系如下图所示。

Clang AST

Clang AST是Clang使用的抽象语法树结构。Clang AST的节点对应源代码中的语句 (statement) 、声明 (declaration) 、类型等，并且包含了源代码行数列数等详细信息；Clang AST的边表示一种包含关系，即子节点在程序语法结构上是父节点的一部分。Clang AST的示意图和实例如下所示。

Clang CFG

Clang CFG是Clang使用的控制流图结构。Clang CFG的节点代表一个基本块，基本块内的有序排列的基本元素对应Clang AST中的语句；Clang CFG的边则是对程序执行位置先后顺序的表示。值得注意的是，Clang Static Analyzer为了尽可能地保留源代码中的语法解构和语义信息，Clang CFG的基本元素并不是被用于编译的、剔除了大量语法语义信息的LLVM IR (LLVM编译器后端的三地址码的中间表示形式) 。Clang CFG的示意图如下所示。

Exploded Graph

Exploded Graph是Clang Static Analyzer在模拟执行程序时使用的记录符号执行过程的图状数据结构。Exploded Graph中的节点可以由程序点和程序状态组成的二元组表示，其中程序点可以是Clang CFG中任意两个相邻语句之间的程序执行位置，程序状态记录了符号执行到当前程序点为止经过的所有语句所造成的影响 (内存区域变化、符号执行环境变化、Checker注册的状态等) ；Exploded Graph中的边表示在两个程序点之间的语句执行并对程序状态造成影响。Clang Static Analyzer的Exploded Graph示意图如下所示。

Clang Static Analyzer的符号执行

Clang Static Analyzer中的符号执行流程如下图所示：首先使用编译器前端，将源代码转换为基于Clang AST语句节点的Clang CFG中间表示；然后运行符号执行引擎，基于Clang CFG模拟执行程序，生成Exploded Graph，并在触发漏洞条件时产生漏洞报告。

工作列表算法

Clang Static Analyzer的符号执行使用工作列表 (worklist) 算法，访问Clang CFG的各个基本块，根据基本块内语句性质更新程序状态，如下图所示。

工作列表算法伪代码中的各个变量与函数的含义如下：

  • start是起始基本块。一般使用Clang CFG中无入边的基本块集合作为起始基本块。
  • worklist是可以增删单个元素的数据结构的实例对象。使用push成员函数新增单个元素，使用pop成员函数取出单个元素。
  • execute函数接受一个基本块作为参数，传递给符号执行引擎以模拟执行该基本块、产生新的Exploded Node节点，并根据程序状态返回接下来可能到达的基本块。

不难看出：当worklist是栈时，该算法本质上是对Clang CFG的深度优先搜索；当worklist是队列时，该算法本质上是对Clang CFG的广度优先搜索；worklist还可以是优先级队列，可以设置队列元素的优先级，此时该算法本质上是对Clang CFG的启发式搜索。

Clang Static Analyzer符号执行引擎会记录Clang CFG中各个基本块的模拟执行次数，并给模拟执行次数较少的基本块更高的优先级，以扩大符号执行覆盖率、找到更短的漏洞触发路径。

工作列表算法伪代码中的execute函数代表了Clang Static Analyzer符号执行引擎模拟程序执行的具体方式。符号执行引擎读入基本块，按顺序执行基本块内的各个语句，更新程序状态，生成Exploded Graph节点。

Clang Static Analyzer符号执行引擎会根据语句的类别和作用，更新对应的程序状态。由符号执行引擎管理的程序状态包括Store (存储) 、Expressions (表达式) 、Ranges (取值范围) 三类，其中：

  • Store存储变量名或内存区域到值的映射，对变量进行赋值的语句会改变程序状态的Store
  • Expressions存储活跃表达式到值的映射，语句中的表达式求值部分会改变程序状态的Expressions
  • Ranges存储符号到取值范围的映射，与符号相关的分支语句会改变程序状态的Ranges

符号执行引擎会定期执行活跃性分析，清除Store、Expressions、Ranges中不会被使用的项目。

过程间分析

Clang Static Analyzer符号执行引擎支持过程间分析 (interprocedural analysis) 。过程内分析 (intraprocedural analysis) 仅在函数层级进行分析，无法正确模拟函数调用的行为；过程间分析在整个程序层级进行分析，能较好地模拟函数调用行为，分析精度较高。

Clang Static Analyzer符号执行引擎在读取程序源代码后，首先根据函数间的调用者与被调用者关系，构造函数调用图 (Call Graph) ，然后基于拓扑顺序对函数调用图中的各个函数逐个进行分析。在遭遇函数调用时，符号执行引擎会试图将被调用函数内联到当前的Clang CFG中。

但是，基于内联的过程间分析存在函数调用路径指数级增长、函数递归调用次数未知等问题。因此，Clang Static Analyzer符号执行引擎提供了一系列规则，对内联进行一定程度的限制，若出现下列情形，会导致函数无法被内联：

  • 被调用函数的函数体无法被找到
  • 当前函数内联调用栈过深
  • 被调用函数的Clang CFG过于复杂 (基本块过多)

当被调用函数无法被内联时，Clang Static Analyzer符号执行引擎认为被调用函数的行为是未知的，对函数调用语句进行保守估计，例如：被调用函数的返回值未知，因此生成 (conjure) 符号代表函数的返回值；被调用函数可能修改全局变量，因此使用新的符号代表非常量的全局变量；按引用或指针传递的参数对应的内存区域可能被修改，生成符号替换Store中原内存区域绑定的值。

Clang Static Analyzer的应用

直接使用Clang Static Analyzer

Clang Static Analyzer提供了丰富的命令行参数选项，能输出触发漏洞的详细路径，以及符号执行使用的Clang CFG和Exploded Graph。本小节将以Clang Static Analyzer中的符号执行流程图左侧的代码片段为素材 (存储为example.c) ，介绍Clang Static Analyzer的使用方法。

使用clang -cc1 -analyze -analyzer-checker core -analyzer-output html example.c命令，即可使用核心漏洞检查器对example.c进行漏洞扫描，并生成.html格式的漏洞报告文档，其中详细展示了漏洞触发的原因，如下图所示。

使用clang -cc1 -analyze -analyzer-checker=debug.ViewCFG example.c命令即可生成.dot格式的Clang CFG，如下图所示。

使用clang -cc1 -analyze -analyzer-checker core -analyzer-dump-egraph=example_egraph.dot example.c命令即可生成.dot格式的Exploded Graph，再使用Clang源码树下的utils/analyzer/exploded-graph-rewriter.py脚本可以生成可视化的.html文件，如下图所示 (其中右侧分支触发了漏洞)。

Clang Static Analyzer的Checker

在Clang Static Analyzer中，Checker (漏洞检查器) 是根据可自定义的规则，通过在符号执行引擎注册回调函数，在符号执行过程中不断检查漏洞是否触发，并生成漏洞报告的模块。

可以使用clang -cc1 -analyzer-checker-help命令在终端打印Clang Static Analyzer的所有内置Checker，也可以查看官方文档以阅读详细的Checker说明和代码样例。本节将介绍Clang Static Analyzer中较为重要的core系列、unix系列、security系列Checker。

core系列Checker对语言核心功能进行建模，包含了许多泛用型的漏洞检查器，能检查除零错误、空指针解引用、未初始化值的使用等典型漏洞，如下表所示。

名称 功能
core.CallAndMessage 检查函数调用中的空函数指针等逻辑漏洞
core.DivideZero 检查除零错误
core.NonNullParamChecker 检查参数为引用或nonnull的函数被传入空指针
core.NullDereference 检查空指针解引用
core.StackAddressEscape 检查栈空间逃逸
core.UndefinedBinaryOperatorResult 检查二元运算符的未定义行为
core.VLASize 检查可变长度数组的声明是否合法
core.uninitialized.ArraySubscript 检查是否使用未初始化变量作为数组下标
core.uninitialized.Assign 检查是否使用未初始化变量进行赋值
core.uninitialized.Branch 检查是否使用未初始化变量作为分支条件
core.uninitialized.CapturedBlockVariable 检查未初始化变量是否被block捕获
core.uninitialized.UndefReturn 检查是否使用未初始化变量作为返回值

unix系列Checker对POSIX/Unix系列函数使用的正确性进行检查，如下表所示。

名称 功能
unix.API 检查open、malloc等POSIX/Unix函数的参数是否合法
unix.Malloc 检查内存泄漏、二重释放、释放后使用等漏洞
unix.MallocSizeof 检查sizeof作为malloc参数时类型是否匹配
unix.MismatchedDeallocator 检查是否混用C/C++的动态内存分配释放语法
unix.Vfork 检查vfork函数的使用是否正确
unix.cstring.BadSizeArg 检查字符串处理函数的长度参数是否合法
unix.cstrisng.NullArg 检查字符串处理函数的缓冲区参数是否为空指针

security系列Checker对安全标准中禁止使用的危险函数和操作等进行检查，如下表所示。

名称 功能
security.FloatLoopCounter 检查浮点数作为循环计数器
security.insecureAPI.UncheckedReturn 检查敏感函数的返回值是否被处理
security.insecureAPI.bcmp 检查bcmp函数的使用
security.insecureAPI.bcopy 检查bcopy函数的使用
security.insecureAPI.bzero 检查bzero函数的使用
security.insecureAPI.getpw 检查getpw函数的使用
security.insecureAPI.gets 检查gets函数的使用
security.insecureAPI.mkstemp 检查是否正确使用mkstemp函数
security.insecureAPI.mktemp 检查mktemp函数的使用
security.insecureAPI.rand 检查较差的随机数生成函数的使用
security.insecureAPI.strcpy 检查strcpy、strcat的使用
security.insecureAPI.vfork 检查vfork函数的使用
security.insecureAPI.DeprecatedOrUnsafeBufferHandling 检查memcpy等危险的缓冲区函数

Checker的编写方法

本节参考NoQ撰写的 Checker编写教程，基于一个简单的Checker编写案例，介绍Checker的编写方法。本节的Checker代码使用Clang 10的Checker开发接口。

该Checker将检查源代码中违反C/C++标准的情形：程序内不应存在对main函数的调用。main函数不应是直接或间接递归的，否则会产生未定义行为。直觉上看，似乎简单的基于正则表达式的字符串匹配就能完成检查这一漏洞的工作，但C/C++语言中函数指针实际上为函数提供了别名，可以存在函数名称不同但实际调用了main函数的情形，如代码片段main_call.cpp所示。因此，我们仍需要使用符号执行技术对main函数调用漏洞进行检查。

1
2
3
4
5
6
7
// main_call.cpp
using main_t = int (*)(int , char **);
int main (int argc , char **argv) {
    main_t foo = main;
    int exit_code = foo(argc, argv); // actually calls main ()!
    return exit_code;
}

编写Checker的第一步是包含 (include) Clang Static Analyzer提供的Checker模块头文件，如代码片段MainCallChecker.cpp (Part 1)所示。其中BugType.h提供了与漏洞报告相关的类的声明，Checker.h提供了Checker类的定义和各类漏洞检查接口的声明，BugType.h提供了路径敏感的Checker所需的上下文信息类的声明，CheckerRegistry.h提供了将Checker编译成Clang Plugin (Clang编译器插件) 的接口声明。

1
2
3
4
5
// MainCallChecker.cpp (Part 1)
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h"

编写Checker的第二步是确定Checker要对程序中的哪些语法元素进行检查，如代码片段MainCallChecker.cpp (Part 2)所示。其中声明使用clang和clang::ento两个命名空间，以便使用命名空间内声明的各个类和接口；在匿名命名空间内，继承Checker<check::PreStmt<CallExpr>>类，声明MainCallChecker类及其成员变量和成员函数。从基类类型和回调函数checkPreStmt可以看出，该Checker是在符号执行引擎模拟执行到函数调用语句前触发回调函数，并检测是否存在所关心的漏洞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// MainCallChecker.cpp (Part 2)
using namespace clang;
using namespace clang::ento;

namespace {
class MainCallChecker : public Checker<check::PreStmt<CallExpr>> {
  mutable std::unique_ptr<BugType> BT_maincall;

public:
  void checkPreStmt(const CallExpr *CE, CheckerContext &C) const;

private:
  void emitError(CheckerContext &C, const Expr *Callee) const;
};
}

编写Checker的第三步是编写回调函数逻辑和错误报告函数逻辑，如代码片段MainCallChecker.cpp (Part 3)所示。其中回调函数checkPreStmt逻辑较为简单，获取被调用函数对象，从Checker上下文中取出函数声明，若函数名标识符为main，则调用emitError函数报告错误；emitError函数则在Exploded Graph中生成一个表示漏洞触发的新节点，构造PathSensitiveBugReport (路径敏感的漏洞报告) 对象，并调用Checker上下文的emitReport接口产生漏洞报告。

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
// MainCallChecker.cpp (Part 3)
void MainCallChecker::checkPreStmt(const CallExpr *CE,
                                   CheckerContext &C) const {
  const Expr *Callee = CE->getCallee();
  const FunctionDecl *FD = C.getSVal(Callee).getAsFunctionDecl();
  if (!FD)
    return;
  IdentifierInfo *II = FD->getIdentifier();
  if (!II)
    return;
  if (II->isStr("main")) {
    emitError(C, Callee);
  }
}
void MainCallChecker::emitError(CheckerContext &C, const Expr *Callee) const {
  ExplodedNode *N = C.generateNonFatalErrorNode();
  if (!N)
    return;
  if (!BT_maincall)
    BT_maincall = std::make_unique<BugType>(this, "Potential call to main",
                                            "beta.MainCallChecker");
  auto report = std::make_unique<PathSensitiveBugReport>(
      *BT_maincall, BT_maincall->getDescription(), N);
  report->addRange(Callee->getSourceRange());
  C.emitReport(std::move(report));
}

编写Checker的最后一步是编写回调函数逻辑和错误报告函数逻辑，如代码片段MainCallChecker.cpp (Part 4)所示。其中定义了clang_registerCheckers接口函数和clang_analyzerAPIVersionString常量，在指定的Clang Static Analyzer版本中注册名称为beta.MainCallChecker的Checker。

1
2
3
4
5
6
7
8
// MainCallChecker.cpp (Part 4)
extern "C" void clang_registerCheckers(CheckerRegistry &registry) {
  registry.addChecker<MainCallChecker>(
      "beta.MainCallChecker", "Disallows calls to main function", "", true);
}

extern "C" const char clang_analyzerAPIVersionString[] =
    CLANG_ANALYZER_API_VERSION_STRING;

使用CMake编译MainCallChecker.cpp生成MainCallChecker.so后，可以使用clang -cc1 -load MainCallChecker.so -analyze -analyzer-checker core,beta main_call.cpp命令加载并应用该Checker，对源代码中main函数的调用进行检查。