专题解读 ｜ 代码图概念与应用

1. 简介

图是由两个部分组成的数据结构：节点和边。在生活中，图数据无处不在。在研究社交网络、分子网络、交通网络、互联网络、引文网络等问题的时候都可以使用图来建模。在软件代码中，“模块”、“代码包“、”类“、”变量“、”函数“等各部分之间相互依赖，例如”变量“和“函数”在“类”内，“模块”中会包含多个“类”等等，每个部分可以看成一个节点，各个部分之间的关系可以看成节点间的关系，所以对于代码的内容，我们也可以使用图来进行建模，用代码图解决相关的问题。本文我们聚焦两项进行代码图建模和代码图应用的研究：使用代码属性图建模和发现漏洞(Modeling and Discovering Vulnerabilities with Code Property Graphs) 和 利用代码知识图谱通过双向注意力进行BUG定位 (Exploiting Code Knowledge Graph for Bug Localization via Bi-directional Attention)

2. Modeling and Discovering Vulnerabilities with Code Property Graphs (IEEE symposium on security and privacy)

如今大部分的软件安全问题都是由于软件代码漏洞导致的，所以挖掘出软件中的漏洞显得至关重要，本文提出了一种新的代码表示方法——代码属性图，并使用这种新的建模方式进行软件漏洞的挖掘。

2.1 代码的表示

在代码表示方面，人们已经开发了各种不同的代码表示形式，其中三种比较经典的表示形式是：抽象语法树、控制流图、程序依赖图。抽象语法树(AST)以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构(图a)；控制流程图(CFG)描述了代码语句的执行顺序以及要采取的特定执行路径需要满足的条件。语句和谓词由节点表示，节点通过有向边连接来指示控制权的转移(图b)；程序依赖图（PDG）表示了语句和谓词之间的依赖关系(图c)。针对图1给出的代码，三种表示方法的表示如图2所示：

2.2 代码属性图建模

上述的每一种图都有侧重点的表示了代码，本文提出了综合上述三种表示方法的代码属性图，我们使用   表示，其中 是一组节点， 是一组有向边， 是边标记函数，将 中的标签分配给每条边， 可以将属性分配给图中的节点和边， 表示属性的键， 表示属性的值。要从三种表示方法中构建代码属性图，需要先把他们建模为属性图，再合并为一个图。

抽象语法树： ，其中 表示树的节点， 表示所对应的抽象语法树的边，为每个节点分配属性代码，以便属性值对应于节点表示的运算符和操作数，最后为每个节点分配一个顺序来表示树的有序结构，

控制流程图：，节点 对应于AST中的语句和谓词，我们额外定义了一个边标记函数， 他将集合中的标签分配给属性图中的所有边

程序依赖图：因为该图表示语句和谓词的数据和控制的依赖关系，所以节点与CFG的节点相同， 只需要定义一组新的边和相应的边标记函数 来表示为属性图 其中 对应于控制和数据的依赖

最后一步，我们只用三种图的结合来表示代码属性图

2.3 使用代码属性图进行代码漏洞发现

代码属性图提供了一种全面表示代码的方式，使得我们可以有效地挖掘代码中的漏洞。通过图遍历技术，我们可以模拟常见的漏洞模式，并在大规模源代码中识别潜在的安全漏洞。

A. 漏洞模式建模

代码属性图允许我们以图遍历的形式表达多种编程模式，但关键在于如何利用它来发现漏洞。

动机示例：考虑一个在SSH实现中发现的缓冲区溢出漏洞，该漏洞影响了多个Apple iOS应用程序。通过正则表达式，可以发现漏洞代码模式，但这种方法存在局限性，因为它无法描述攻击者对变量的控制，也无法模拟变量的宽度。

为了解决这个问题，我们需要覆盖以下几个方面：

1. 敏感操作：能够描述安全敏感操作，例如调用受保护的功能、复制到缓冲区或分配内存等。
2. 类型使用：许多漏洞与程序中使用的数据类型密切相关。
3. 攻击者控制：能够表达哪些数据源处于攻击者的控制之下。
4. 净化处理：许多漏洞仅在程序缺乏对攻击者控制数据的适当净化时才会出现。

B. 语法限定的漏洞描述

代码属性图暴露了抽象语法树中的所有信息，这足以描述攻击者控制的源、敏感操作和净化器，但无法捕获语句之间的相互作用。

示例：考虑一个缓冲区溢出漏洞，其关键属性是分配函数的参数中直接进行了求和操作。我们可以使用以下遍历来描述这种模式：

• MATCHp(V)：该遍历从节点集合V中的所有AST根开始，遍历AST中的所有节点，并根据谓词p(v)进行过滤。

例如，要找到所有调用分配函数的节点，可以使用MATCH遍历，其中V是所有函数节点的集合，p(v)为v是分配函数调用的真值。

C. 控制流限定的漏洞描述

通过使用代码属性图的控制流，我们可以模拟更多的漏洞，因为我们可以模拟语句执行顺序。

示例：

• 资源泄漏：如果从分配资源的语句到函数末尾的路径没有经过释放资源的语句，则可能存在资源泄漏。
• 未释放锁：如果在错误路径上没有释放锁，则可能导致并发问题。
• 使用后释放漏洞：如果在释放内存后再次访问已释放的内存区域，则可能导致任意代码执行。

这些漏洞都与控制流图中的特定路径相关联。例如，资源泄漏与从分配内存的语句到函数末尾的路径相关联，前提是分配函数返回指向分配内存的指针。

2.4 实验效果

通过在Linux内核的代码属性图上运行这些遍历，本文发现了18个以前未知的漏洞(如图4)，这些漏洞后来都被内核开发人员确认并修复。

这表明了代码属性图和图遍历非常适合发现常见的漏洞类型，并且可以很好地定制以识别特定于代码库的漏洞。通过改进遍历，分析人员可以完全控制误报和漏报率，允许在分析的发现阶段制定模糊的遍历，并精确地描述已知漏洞类型的实例。

3. Exploiting Code Knowledge Graph for Bug Localization via Bi-directional Attention (ICPC 2020)

随着软件项目的规模不断扩大，软件缺陷或错误（bug）的定位成为了开发过程中一项耗时且复杂度较高的任务。为了减轻开发者的负担，研究者们一直在探索自动化的bug定位技术。本文介绍了一种基于代码知识图谱和双向注意力机制的bug定位方法。

3.1 代码知识图谱

代码知识图谱是一种用于表示软件项目中各种实体及其相互关系的方法。在代码知识图谱中，节点代表代码实体（如类、方法、属性），边代表实体间的各种关系（如继承、调用、依赖）。

A. 知识图谱的构建

构建代码知识图谱的第一步是识别代码中的实体和关系。这通常通过解析源代码来完成，例如使用抽象语法树（AST）来识别类和方法，然后使用静态分析来识别它们之间的关系。

实体识别：通过解析源代码，可以识别出类、方法、属性等代码实体。

关系识别：识别实体之间的语义关系，如一个类继承自另一个类，或者一个方法调用了另一个方法。

图谱构建：将识别出的实体和关系构建成图谱，每个实体作为一个节点，每条关系作为一条边。

B. 知识图谱的嵌入

为了利用代码知识图谱进行bug定位，需要将图谱中的实体和关系嵌入到向量空间中，以便可以进行数学运算和机器学习建模。

实体嵌入：将每个代码实体映射到一个高维空间中的点。 ，其中 是实体 的嵌入向量。

关系嵌入：将实体间的关系也映射到向量空间中，以便可以计算实体间的相似度或关联度。 ，其中 是实体 和 之间关系的嵌入向量。

嵌入训练：通过训练数据来优化嵌入向量，使得在语义上相关的实体在向量空间中也相近。 其中 是训练数据集， 是损失函数， 是模型参数。

3.2 双向注意力机制

双向注意力机制是一种用于匹配源代码和bug报告的方法，它可以帮助模型更好地理解源代码与bug报告之间的语义关联。

A. 注意力机制的原理

注意力机制是一种资源分配策略，它允许模型在处理信息时对不同的部分分配不同的处理权重。

bug-specific注意力：模型会根据bug报告的内容，对源代码中与bug相关的部分给予更多的关注。 其中 是第 个代码实体的bug-specific注意力权重， 和 分别是bug报告和代码实体的嵌入向量。

code-specific注意力：模型也会根据源代码的内容，对bug报告中与代码相关的部分给予更多的关注。 其中 是第 个bug报告实体的code-specific注意力权重。

B. 双向注意力的实现

实现双向注意力机制需要设计一个神经网络模型，该模型能够学习源代码和bug报告之间的交互特征。

编码器：使用神经网络（如LSTM或CNN）对源代码和bug报告进行编码，生成它们的特征表示。 其中 是输入 的编码表示， 是编码器的参数。

注意力层：在编码器的基础上添加注意力层，使模型能够学习源代码和bug报告之间的交互特征。 其中 是加权后的编码表示。

优化目标：通过定义一个损失函数来优化模型参数，使得模型能够更好地匹配源代码和bug报告。 其中 是损失函数， 是模型参数。

3.3 实验效果

通过在多个开源软件项目的bug报告和源代码数据集上进行实验，验证了基于代码知识图谱和双向注意力机制的bug定位方法的有效性。

总结

随着软件系统的复杂性不断增加，代码图作为软件工程领域的一项重要技术，其应用前景越来越广阔。本文通过对代码图概念的深入探讨和实际应用案例的分析，揭示了代码图在自动化漏洞发现和bug定位中的巨大潜力。

引用

• Yamaguchi, F., Golde, N., Arp, D., & Rieck, K. (2014, May). Modeling and discovering vulnerabilities with code property graphs. In 2014 IEEE symposium on security and privacy (pp. 590-604). IEEE.
• Zhang, J., Xie, R., Ye, W., Zhang, Y., & Zhang, S. (2020, July). Exploiting code knowledge graph for bug localization via bi-directional attention. In Proceedings of the 28th International Conference on Program Comprehension (pp. 219-229).