代码分析属性图 CPG 介绍

2023-12-02 23:34:22

代码分析工具层出不穷，编译器本身也内置了大量的静态检查，但分析的数据源较为单一。而本文要介绍的，是集众之所长的代码分析属性图 CPG，在漏洞分析上很有帮助。

1、定义

代码属性图(code property graph，简称 CPG) 是一种数据结构，用来通过 DSL(domain-specific language) 查询语句来挖掘代码漏洞。

它的主要思想如下：

CPG 将多个程序表示(program representations)整合成一个
CPG 数据被存储在图数据库中
通过 DSL 在图数据库中遍历和查询 CPG 数据

2、用处

CPG 整合了 AST(abstract syntax trees)、CFG(control flow graphs)、PDG(program dependence graphs) 到一种数据结构当中。

这种综合的数据表示，使得我们在图遍历当中，可以优雅地组织漏洞扫描的模版。

可以用来分析缓冲区溢出、整型溢出、格式字符串漏洞、内存泄漏等。

2.1、局限性

1、纯静态分析，缺乏对运行时信息的组织(比如数据争用)

2、解决的是通用的潜在漏洞，难以挖掘特定场景下的漏洞

3、暂时缺乏对 IR 层面的分析(待扩展)

3、结构

结合了下面三种不同的表示:

整合成一种表示 - Code Property Graph:

CPG 就是属性图，它包含以下组成部分：

节点及其类型。节点代表程序的组成部分，包含有底层语言的函数、变量、控制结构等，还有更抽象的 HTTP 终端等。每个节点都有一个类型，如类型 METHOD 代表是方法，而 LOCAL 代表是一个局部变量。
有向边及标签。节点之间的边代表它们之间的关系，而标签则是关系的说明。比如一个方法 CONTAINS 包含了一个局部变量。
键值对。节点带有键值对，即属性，键取决于节点的类型。比如一个方法至少会有一个方法名和一个签名，而一个局部变量至少有名字和类型。

4、概念

4.1、CPG (Code Property Graph)

4.1.1、property graph

定义基本的有向图数据结构 G = (V, E, λ, μ)，即 graph = (点的集合，有向边的集合，边上标签的计算函数，属性)

Σ 代表字母表，λ : E → Σ

K 代表属性键 key 的集合，而 S 代表属性值 value 的集合，μ : (V ∪ E) × K → S

4.1.2、traversal

遍历函数是 T : P(V) → P(V)，P 是 V 的幂集，即 V 中所有子集构成的集合，实际上是把一系列节点映射为另一系列的节点。

还可以获取有向边的输入：

4.2、AST (Abstract Syntax Trees)

抽象语法树 AST，这棵树的编码信息，表达了语句(statements)和表达式(expressions)是如何嵌套组合来生成程序代码的。

AST 是有序的树，它的内部节点代表了运算符操作(如加法或赋值)，而叶子节点则关联到操作数(如常量或标识符)。

4.3、CFG (Control Flow Graph)

控制流图 CFG，描述了代码语句(statements)执行的顺序，以及某一执行路径上的某处的状态。在图中，语句(statements)和判断(predicates)用节点来表示，而这些节点用有向边来连接，表示控制的转换。每条边需要标上 true、false、空的标签。

CFG 可以用 AST 来生成：首先，结构化的控制语句(如 if、while、for)先用来构建初始的 CFG；然后，添加上非结构化的控制语句(如 goto、break、continue)，来逐步修正这个初始的 CFG。

4.4、PDG (Program Dependence Graphs)

PDG 用来找出会影响某条语句上的变量值的所有语句和判断。PDG 展现了语句和判断之间的依赖关系。一般该图以两种类型的边来构造：数据依赖边(data dependency edges)表示会影响某语句的变量；控制依赖边(control dependency edges)表示判断语句对于变量值的影响。

PDG 的边可以从 CFG 计算得来，通过先判断已定义的变量的集合、每条语句使用到的变量的集合，然后计算每条语句和判断的定义在哪。

5、转换工具 llvm2cpg

llvm2cpg - 将 LLVM bitcode 格式转换成 CPG 图

$ clang -S -emit-llvm -g -O1 main.c -o main.ll 
$ llvm2cpg -output=/tmp/cpg.bin.zip main.ll

下面的 bitcode (IR)内容：

define i32 @sum(i32 %a, i32 %a) {   
    %r = add nsw i32 %a, %b   
    ret i32 %r 
}

可以转换成更高级抽象的形式：

i32 sum(i32 a, i32 b) {   
    i32 r = add(a, b);   
    return r; 
}

5.1、实现细节

当要用 LLVM 来支持 CPG，首先的问题就是：我们要怎么把 bitcode 映射为 CPG？

5.1.1、指令语义

我们可以把一些 LLVM 的指令转换成 CPG 的运算符。比如：

add, fadd -> <operator>.addition
bitcast -> <operator>.cast
fcmp eq, icmp eq -> <operator>.equals
urem, srem, frem -> <operator>.modulo
getelementptr -> 组合 <operator>.pointerShift, <operator>.indexAccess, 和 <operator>.memberAccess 依赖于 GEP 操作数的类型

但有一种指令我们无法映射为 CPG 的，那就 phi 指令，在 CPG 中没有 phi 节点的概念，所以我们需要用 reg2mem 的运算方法把 phi 指令去掉。

5.1.2、冗余

Clang 默认会生成大量的冗余指令。

define i32 @sum(i32 %0, i32 %1) {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %4, align 4
  %7 = add nsw i32 %5, %6
  ret i32 %7
}

而不是更加精简的版本：

define i32 @sum(i32 %0, i32 %1) {
  %3 = add nsw i32 %1, %0
  ret i32 %3
}

一般情况下，这不是什么问题，但它增加了数据流追踪的复杂度，而且很没必要地增加了图的大小。一个可以解决的方法是，先对 bitcode 跑一下优化。但最终 LLVM 还是把这种选择权交给用户来决定。

5.1.3、类型等价判断

在我写的一篇译文里有相关更具体的介绍和解决方案《【译】LLVM 类型相等判断》，或者可以直接看原文。下面简单地介绍下问题：

如果有相同结构相同名字的两个模块，被加载到同一上下文，LLVM 会重命名其中一个来避免命名冲突。

; Module1
%struct.Point = type { i32, i32 }

和

; Module 2
%struct.Point = type { i32, i32 }

当加载到同一个上下文时：

%struct.Point = type { i32, i32 }
%struct.Point.1 = type { i32, i32 }

我们需要对这些类型进行去重，以保证最终生成的图中，只会有一个 Point 的节点。这就需要我们判断两个类型是否是等价的。

5.2、总结

用 LLVM bitcode 的方式有以下的优点和局限性：

LLVM 语言的接口比 C 和 C++ 更轻量
很多抽象层的细节，在 IR 层不会有体现
程序需要被编译，因此会限制了程序的语言扩展范围

6、相关产品

现在，CPG 已经被以下几个工具支持了：

Ocular- 支持 Java, Scala, C#, Go, Python, 和 JavaScript 语言
Joern- Ocular 的开源部分，支持 C 和 C++
Plume- 开源工具，支持 Java Bytecode

6.1、Joern

Joern 有以下几个重要特性:

Fuzzy Parsing of C/C++. 模糊解析，用于在编译环境和部分文件的缺失的情况下，进行解析。
Code Property Graphs. 模糊解析的结果会被存储到 CPG 格式的数据库当中。
Search Queries. 提供了基于 Gremlin-Scala 扩展的查询语言。
Extendable via CPG passes. 支持自定义扩展来添加或消费数据信息。

Joern 可以为 C/C++ 代码创建以下几种中间表示:

Abstract Syntax Trees (AST)
Control Flow Graphs (CFG)
Control Dependence Graphs (CDG)
Data Dependence Graphs (DDG)
Program Dependence graphs (PDG)
Code Property Graphs (CPG14)

6.1.1、Joern 使用例子

有了 Joern 和 llvm2cpg，就可以愉快地玩耍了：

转换程序为 LLVM Bitcode
生成 CPG
加载 CPG 到 Joern 当中，然后进行分析

$ cat main.c
extern int MAX;
extern int source();
extern void sink(int);
void foo() {
  int x = source();
  if (x < MAX) {
    int y = 2 * x;
    sink(y);
  }
}
$ clang -S -emit-llvm -g -O1 main.c -o main.ll
$ llvm2cpg -output=/tmp/cpg.bin.zip main.ll

现在我们已经把 CPG 保存到 /tmp/cpg.bin.zip ，之后就能加载到 Joern，然后尝试分析是否有从 source 函数到 sink 函数的流：

$ joern
joern> importCpg("/tmp/cpg.bin.zip")
joern> run.ossdataflow
joern> def source = cpg.call("source")
joern> def sink = cpg.call("sink").argument
joern> sink.reachableByFlows(source).p
List[String] = List(
  """_____________________________________________________
| tracked               | lineNumber| method| file   |
|====================================================|
| source                | 5         | foo   | main.c |
| <operator>.assignment | 5         | foo   | main.c |
| <operator>.lessThan   | 6         | foo   | main.c |
| <operator>.shiftLeft  | 7         | foo   | main.c |
| <operator>.shiftLeft  | 7         | foo   | main.c |
| <operator>.assignment | 7         | foo   | main.c |
| sink                  | 8         | foo   | main.c |
"""
)

参考

论文《Modeling and Discovering Vulnerabilities with Code Property Graphs》
LLVM meets Code Property Graphs：https://blog.llvm.org/posts/2021-02-23-llvm-meets-code-property-graphs/
llvm2cpg：https://github.com/ShiftLeftSecurity/llvm2cpg
Joern Documentation：https://docs.joern.io/home/

码农公寓