LLVM 遇见 代码属性图
代码属性图（CPG）是一种数据结构，旨在通过特定领域查询语言，从大型代码库中挖掘编程模式的实例。它首次在 2014 年 IEEE 安全与隐私会议论文中提出（出版物，PDF），特别是在 C 系统代码和 Linux 内核中发现漏洞的背景下。该方法的核心思想如下
- CPG 将几种程序表示组合成一个
- CPG 存储在图数据库中
- 图数据库带有一个 DSL，允许遍历和查询 CPG
目前，CPG 基础设施由几种工具支持
- Ocular - 一款支持 Java、Scala、C#、Go、Python 和 JavaScript 语言的专有代码分析工具
- Joern - Ocular 的开源对应工具，支持 C 和 C++
- Plume - 一款支持 Java 字节码的开源工具
本文介绍了 ShiftLeft 的 llvm2cpg 开源实现 - 一个独立的工具，为 Joern 带来了 LLVM Bitcode 支持。但在我们深入细节之前，让我们再多说几句关于 CPG 和 Joern。
代码属性图
CPG 的核心思想是，不同的经典程序表示被合并成一个属性图，这是一个单一的数据结构，它保存了关于程序语法、控制流和过程内数据流的信息。
从图形上来说，以下代码片段
void foo() {
int x = source();
if (x < MAX) {
int y = 2 * x;
sink(y);
}
}
组合了这三种不同的表示
成一个单一的表示 - 代码属性图
Joern
属性图存储在图数据库中，并通过特定领域语言 (DSL) 提供访问权限，以便根据用于图遍历的 DSL 识别编程模式。查询语言允许在原始代码表示之间无缝转换，从而可以将来自不同视图的代码方面组合起来，而这些视图提供了这些表示方法。
代码属性图的主要接口之一是名为 Joern 的工具。它提供了提到的 DSL，并允许查询 CPG 以发现程序的特定属性。以下是 Joern DSL 的一些示例
joern> cpg.typeDecl.name.p
List[String] = List("ANY", "int", "void")
joern> cpg.method.name.p
List[String] = List(
"foo",
"<operator>.multiplication",
"source",
"<operator>.lessThan",
"<operator>.assignment",
"sink"
)
joern> cpg.method("foo").ast.isControlStructure.code.p
List[String] = List("if (x < MAX)")
joern> cpg.method("foo").ast.isCall.map(c => c.file.name.head + ":" + c.lineNumber.get + " " + c.name + ": " + c.code).p
List[String] = List(
"main.c:2 <operator>.assignment: x = source()",
"main.c:2 source: source()",
"main.c:3 <operator>.lessThan: x < MAX",
"main.c:4 <operator>.assignment: y = 2 * x",
"main.c:4 <operator>.multiplication: 2 * x",
"main.c:5 sink: sink(y)"
)
除了 DSL 之外，Joern 还提供了一个数据流跟踪器，它可以进行更复杂的查询，例如“程序中是否有用户控制的 malloc？”
DSL 比示例中强大得多，但这超出了本文的范围。请参阅 文档 了解更多信息。
LLVM 和 CPG
本部分分为两个小部分：第一部分介绍了一些实现细节，第二部分展示了如何使用 llvm2cpg 的示例。如果您对实现不感兴趣，请向下滚动 :)
实现细节
当我们决定为 CPG 添加 LLVM 支持时，第一个问题是：我们如何将 bitcode 表示映射到 CPG 上？
我们采取了一种简单的方法 - 假装 SSA 表示只是一个扁平的源程序。换句话说，以下 bitcode
define i32 @sum(i32 %a, i32 %a) {
%r = add nsw i32 %a, %b
ret i32 %r
}
可以看作一个 C 程序
i32 sum(i32 a, i32 b) {
i32 r = add(a, b);
return r;
}
从高层次的角度来看，这种方法很简单，但我们必须克服一些小细节。
指令语义
我们可以将一些 LLVM 指令映射回内部 CPG 操作。以下是一些示例
add,fadd-><operator>.additionbitcast-><operator>.castfcmp eq,icmp eq-><operator>.equalsurem,srem,frem-><operator>.modulogetelementptr-> 根据 GEP 操作数的底层类型，组合了<operator>.pointerShift、<operator>.indexAccess和<operator>.memberAccess
大多数这些 <operator>.* 具有特殊的语义，这在 Joern 和 Ocular 的内置数据流跟踪器中起着至关重要的作用。
不幸的是，并非所有 LLVM 指令在 CPG 中都有相应的运算符。在这些情况下，我们不得不回退到函数调用。例如
select i1 %cond, i32 %v1, i32 %v3变成了select(cond, v1, v2)atomicrmw add i32* %ptr, i32 1变成了atomicrmwAdd(ptr, 1)（对于任何其他atomicrmw运算符也是如此）fneg float %val变成了fneg(val)
我们无法映射到 CPG 的唯一指令是 phi：CPG 没有 Phi 节点概念。我们必须使用 reg2mem 机制消除 phi 指令。
冗余
对于一个小型的 C 程序
int sum(int a, int b) {
return a + b;
}
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 生成 CPG 之前运行优化。不过，最后我们决定将这项工作交给最终用户：如果你想要更少的指令，那么在生成 CPG 之前手动应用优化。
类型等价
另一个问题与 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。
显而易见的解决方案是将两个名称“相似”且布局相同的结构体视为相同。但是，我们无法依赖 llvm::StructType::isLayoutIdentical，因为尽管有这个名字，它还是会产生误导性的结果。
根据 llvm::StructType::isLayoutIdentical，结构体 Point 和 Pair 布局相同，但 PointWrap 和 PairWrap 不同。
; these two have identical layout
%Point = type { i32, i32 }
%Pair = type { i32, i32 }
; these two DO NOT have identical layout
%PointWrap = type { %Point }
%PairWrap = type { %Pair }
这是因为 llvm::StructType::isLayoutIdentical 根据指针确定等价性。也就是说，如果所有结构体元素都相同，那么布局相同。这也意味着我们无法使用这种方法来比较来自不同 LLVM 上下文的类型。我们必须根据 树自动机 推出我们自己的自定义解决方案来解决这个问题。
还有一些细节，但本文篇幅过长。因此，让我们看看如何在 Joern 中使用 llvm2cpg。
示例
安装好 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
现在您将在 /tmp/cpg.bin.zip 中获得保存的 CPG，您可以将其加载到 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 |
"""
)
它确实存在！
结论
最后，让我们概述一下 LLVM Bitcode 带来的某些优点和限制
- LLVM 语言的“表面”比 C 和 C++ 小
- 许多高级细节在 IR 级别不存在
- 程序必须经过编译，因此限制了可以使用 Joern 分析的程序范围
这里 您可以找到更多教程和信息。