LLVM符合代码属性图

代码属性图（CPG）是一种数据结构，旨在通过特定于域的查询语言为编程模式的实例挖掘大型代码库。它是在2014年IEEE安全和隐私会议（出版物，PDF）的会议记录中首次引入的，涉及C系统代码（尤其是Linux内核）中的漏洞发现。该方法的核心思想如下：

Ocular-专有的代码分析工具，支持Java，Scala，C＃，Go，Python和JavaScript语言

本文介绍了ShiftLeft的llvm2cpg的开源实现，该工具是一个独立的工具，为Joern提供了LLVM Bitcode支持。

CPG的核心思想是将不同的经典程序表示形式合并为一个属性图，即一个单一的数据结构，其中包含有关程序的语法，控制和过程内数据流的信息。

void foo（）{int x = source（）;如果（x＆lt; MAX）{int y = 2 * x;下沉（y）; }}

属性图存储在图数据库中，并可以通过领域特定语言（DSL）访问，以基于DSL识别图遍历的编程模式。查询语言允许在原始代码表示形式之间进行无缝转换，从而可以从这些表示形式提供的不同视图中组合代码的各个方面。

代码属性图的主要接口之一是称为Joern的工具。它提供了上述DSL，并允许查询CPG以发现程序的特定属性。以下是Joern DSL的一些示例：

琼恩＆gt; cpg .typeDecl .name .p List [字符串] =列表（＆＃34; ANY＆＃34;，＆＃34; int＆＃34;，＆＃34; void＆＃34;）joern＆gt; cpg .method .name .p List [字符串] =列表（＆＃34; foo＆＃34;，＆＃34;＆lt; operator＆gt; .multiplication＆＃34;，＆＃34; source＆＃34;，＆＃34; ＆lt; operator＆gt; .lessThan＆＃34;，＆＃34;＆lt; operator＆gt; .assignment＆＃34;，＆＃34; sink＆＃34;）joern＆gt; cpg .method（＆＃34; foo＆＃34;）.ast .isControlStructure .code .p List [字符串] =列表（＆＃34; if（x＆lt; MAX）＆＃34;）joern＆gt; cpg .method（＆＃34; foo＆＃34;）.ast .isCall .map（c =＆gt; c .file .name .head +＆＃34;：＆＃34; + c .lineNumber .get +＆＃ 34;＆＃34; + c .name +＆＃34 ;:＆＃34; + c .code）.p列表[字符串] =列表（＆＃34; main.c：2＆lt; operator＆gt; .assignment： x = source（）＆＃34;，＆＃34; main.c：2 source：source（）＆＃34;，＆＃34; main.c：3＆lt; operator＆gt; .lessThan：x＆lt; MAX＆＃ 34;，main.c：4＆lt; operator＆gt; .assignment：y = 2 * x＆＃34;，＆＃34; main.c：4＆lt; operator＆reg; .multiplication：2 * x＆＃34; ，＆＃34; main.c：5 sink：sink（y）＆＃34;）

除了DSL之外，Joern还带有一个数据流跟踪器，该跟踪器支持更复杂的查询，例如“程序中是否存在用户控制的malloc？”。

DSL比示例中的功能强大得多，但这超出了本文的范围。请参考文档以了解更多信息。

这一部分分为两个较小的部分：第一部分覆盖了一些实现细节，第二部分显示了如何使用llvm2cpg的示例。如果您对实现不感兴趣-向下滚动:)

当我们决定添加对CPG的LLVM支持时，第一个问题是：如何将位码表示形式映射到CPG？

我们采用了一种简单的方法-假设SSA表示只是一个简单的源程序。换句话说，以下位码

定义i32 @sum（i32％a，i32％a）{％r =添加nsw i32％a，％b ret i32％r}

从高级的角度来看，该方法很简单，但是我们必须克服一些微小的细节。 我们可以将一些LLVM指令映射回内部CPG操作。 这里有些例子： getelementptr-＆gt; 取决于GEP操作数的基础类型，＆lt; operator＆gt; .pointerShift，＆lt; operator＆gt; .indexAccess和＆lt; operator＆gt; .memberAccess的组合 这些大多数“操作符”具有特殊的语义，这在Joern和Ocular内置数据流跟踪器中起着至关重要的作用。 不幸的是，并不是每个LLVM指令在CPG中都有相应的运算符。 在这些情况下，我们不得不退回到函数调用，例如： atomicrmw添加i32 *％ptr，i32 1转换为atomicrmwAdd（ptr，1）（与任何其他atomicrmw运算符相同） 我们无法映射到CPG的唯一指令是phi：CPG没有Phi节点概念。我们不得不使用reg2mem机制消除phi指令。

定义i32 @sum（i32％0，i32％1）{％3 = alloca i32，对齐4％4 = alloca i32，对齐4存储i32％0，i32 *％3，对齐4存储i32％1，i32 *％ 4，对齐4％5 =加载i32，i32 *％3，对齐4％6 =加载i32，i32 *％4，对齐4％7 =添加nsw i32％5，％6 ret i32％7}

定义i32 @sum（i32％0，i32％1）{％3 =添加nsw i32％1，％0 ret i32％3}

通常，这不是问题，但是它会为数据流跟踪器增加更多的复杂性，并且不必要地增加图形的大小。考虑的因素之一是在为位代码发出CPG之前进行优化。最终，我们还是决定将这项工作分给最终用户：如果您希望使用更少的指令，则在发布CPG之前手动应用优化。

另一个问题与LLVM处理类型的方式有关。如果在相同上下文中的两个模块使用具有相同名称的相同结构，则LLVM重命名另一个结构以防止名称冲突。例如

我们希望对这些类型进行重复数据删除，以获得更好的用户体验，并且只在最终图形中发出Point。

显而易见的解决方案是考虑两个具有“相似”名称和相同布局的结构是相同的。但是，我们不能依赖llvm :: StructType :: isLayoutIdentical，因为尽管有名称，但它会产生误导性的结果。

根据llvm :: StructType :: isLayoutIdentical，结构Point和Pair具有相同的布局，但PointWrap和PairWrap没有。

;这两个具有相同的布局％Point =类型{i32，i32}％Pair =类型{i32，i32};这两个布局不相同％PointWrap =类型{％Point}％PairWrap =类型{％Pair}

发生这种情况是因为llvm :: StructType :: isLayoutIdentical根据指针确定相等性。也就是说，如果所有的struct元素都相同，那么布局是相同的，这也意味着我们不能使用这种方法来比较来自不同LLVM上下文的类型。我们不得不推出基于Tree Automata的自定义解决方案来解决此问题。

细节很少，但是本文的篇幅越来越长。因此，让我们看一下如何将llvm2cpg与Joern结合使用。

$ cat main.cextern int MAX; extern int source（）; extern void sink（int）; void foo（）{int x = source（）;如果（x＆lt; MAX）{int y = 2 * x;下沉（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中，并查找是否有从源函数到接收器的流：

$ joernjoern＆gt; importCpg（＆＃34; /tmp/cpg.bin.zip"）joern＆gt; run.ossdataflowjoern＆gt; def source = cpg.call（＆＃34; source＆＃34;）joern＆gt; def sink = cpg.call（＆＃34; sink＆＃34;）.argumentjoern＆gt; sink.reachableByFlows（源）.pList [String] =列表（＆＃34;＆＃34;＆＃34; _____________________________________________________ |跟踪的| lineNumber |方法|文件| | ============== ===================================== | |来源| 5 | foo | main.c | | |＆lt; operator＆gt; .assignment | 5 | foo | main.c | |＆lt; operator＆gt; lessThan | 6 | foo | main.c | |＆lt; operator＆gt; .shiftLeft | 7 | foo | main.c | | ＆lt; operator＆gt; .shiftLeft | 7 | foo | main.c | |＆lt; operator＆gt; .assignment | 7 | foo | main.c | | sink | 8 | foo | main.c |＆＃34;＆＃34; ＆＃34;）

总而言之，让我们概述LLVM Bitcode隐含的一些优点和约束：

LLVM语言的“表面”比C和C ++小 必须编译该程序，从而限制了可以使用Joern分析的程序范围 如果您有任何疑问，请随时在Twitter上ping Fabs或Alex，或者更好地进行Joern聊天。