Clang Static Analyzer 介绍

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 检查 openmalloc 等 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 检查 strcpystrcat 的使用
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) 所示。其中声明使用 clangclang::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 函数的调用进行检查。