Modeling and Discovering Vulnerabilities with Code Property Graphs

Modeling and Discovering Vulnerabilities with Code Property Graphs：S&P(A) 2014, Fabian Yamaguchi et al.

Abstract

本文提出了一种基于代码属性图CPG的源代码漏洞检测方法。代码属性图是包括抽象语法树AST、控制流图CFG和程序依赖图PDG的一个联合数据结构。本文通过图的遍历（graph traversals）来进行漏洞检测，检测的漏洞类别包括缓冲区溢出（buffer overflows），整数溢出（integer overflows），内存泄漏（memory disclosures），格式化字符串漏洞（format string vulnerabilities）。本文使用一个图数据库来实现该方案，并在Linux内核源代码中识别了18个以前未知的漏洞，证明了该方案的有效性。

Introduction

img

以上图为示例代码，介绍一下AST、CFG、PDG的含义。

  • AST

AST的全名为抽象语法树，是代码解析器或者编译器产生的一种代码的中间表示形式，是很多其它代码表示基础。AST非叶子节点表示运算或赋值操作，叶子节点表示常量或标识符，表达了代码的表达式和语句嵌套生成程序的方式。AST蕴含着丰富的代码语法信息，但缺乏控制流和数据依赖等信息，示例代码的AST如下图(a)所示。

  • CFG

CFG的全名为控制流图，表示了每条代码语句的执行顺序以及需要满足的条件分支，CFG的每个结点表示1条代码语句，结点之间通过有向边连接表示执行的顺序和分支。AST可以经过2个步骤变成CFG：首先用if, while, for等控制语句建立初步的CFG，然后用goto，break等语句来对CFG图进行修正。CFG可以用在许多安全应用上，比如检测已知恶意代码的变种以及指导模糊测试的工具，示例代码的CFG如下图(b)所示。

  • PDG

PDG的全名为程序依赖图，最初用于程序切片任务中，PDG同时包含数据依赖和控制依赖，数据依赖指的是变量的使用语句与变量的定义或赋值语句存在数据依赖；控制依赖指的是一条语句的执行与否依赖于另一条语句执行的结果，则称这两条语句控制依赖。示例代码的PDG如下图©所示。

img

上文所述每种程序表示（AST，CFG，PDG）都是从不同的角度表示程序，而CPG就是要结合这几种表示，属性图在许多图数据库（ArangoDB，Neo4J，OrientDB）中是结构化数据的基础表示。

img

一个简单的属性图如上图所示，每个节点的属性key均为k，而属性value有x和w两个值，获取属性图的特征信息的主要方式是graph traversals（图的遍历）。

img

图的遍历有以上3种方式，分别是获取邻接节点，获取类别为l的边的可达节点，以及获取类别为l的边且属性为k和s的可达节点。

img

上图就是一个CFG的完整实例，其中包括AST,CFG,PDG的边，包含语法和语义信息，控制依赖和数据依赖

  • 与AST对比，整个函数的AST被切分成4个语句的AST，并用CFG和PDG的边串起
  • 与CFG对比，每个语句用它的AST来表示而不仅仅是token序列，并且多了PDG的边
  • 与PDG对比, 每个语句用它的AST来表示而不仅仅是token序列，并且多了CFG的边

本文的贡献点：

  • CPG：一种结合了AST,CFG,PDG三种程序表示的综合图表示
  • CPG遍历检测漏洞：常见类型的漏洞可以被建模为代码属性图的遍历，并生成有效的漏洞检测模板
  • 高效执行：将CPG导入到图数据库中后，可以高效的处理大型代码库

Method

下面，使用下图的C代码举例，展示本文是如何通过CPG图的遍历来检测4种代码漏洞的。

img

channelp->exit_signal =LIBSSH2_ALLOC(session, namelen +1);这行代码种namelen是用户输入的变量，所以可能会导致漏洞，本文从以下几个方面分析漏洞：

  • Sensitive operations：敏感操作包括调用受保护的函数，缓冲区复制数据，比如示例中的算数表达式就需要特别关注，需要检查AST
  • Type usage：同时变量类型也需要进行关注，如果namelen是16位而不是32位变量就不会出现漏洞，该类型也需要检查AST
  • Attacker control：检测哪些data source处于用户控制之下很重要，这个示例中，_libssh2_ntohu32的返回值就是用户可控的，可以借助PDG中的数据依赖来建模
  • Sanitization：许多程序由于缺乏数据校验而导致漏洞，在示例中，如果对namelen进行校验，确保它的值在合适范围内，那么漏洞不会发生，此时需要检查CFG

下面以3种漏洞为例，介绍分析代码属性图提供的不同视图如何有助于构建成功的图遍历以发现漏洞。

  1. Syntax-Only Vulnerability：在CPG中，语句内部的问题可以通过AST解决，而语句之间的依赖关系则需要CFG和PDG来处理。AST层面主要有如下问题：

  • Insecure arguments：不安全的参数，主要出自函数调用参数，比如格式化字符串漏洞(printf)，其中格式化字符串的一个必须满足的条件就是传递的第一个参数不是常量（比如%s）。

  • Integer overflows：整数溢出常常发生在内存分配（malloc）的算术运算中（+，*），比如LIBSSH2_ALLOC (session, namelen + 1);的第二个参数。所以在遍历AST时需重点访问malloc类函数调用中的算术运算结点。

  • Integer type issues：问题主要出现在赋值操作中，左边的数据类型宽度要小于右边的宽度（比如左边short，右边int），这在遍历AST的时候可能分别需要遍历赋值运算符的左右子树。

  • Control-Flow Vulnerability：引入CFG可以对更多的漏洞类型建模，通过使用代码属性图的控制流边，可以建模语句的执行顺序，从而可以访问更大范围的漏洞，比如：

  • Resource leaks：当资源被分配（allocate）但并没有被释放的时候，会导致系统爆内存，进而使得无法被外部访问。在CFG中，从分配内存空间的函数调用（malloc）开始，到释放这个指针的函数（free）构成一个路径，如果只有malloc没有free，则说明出现了内存泄露。

  • Failure to release locks：虽然在一般情况下并发问题很难检测到，但可以使用简单的控制流分析来检测在错误路径上没有释放锁的情况。

  • Use-after-free vulnerabilities：内存被释放后没有置为NULL，导致可能被再次利用，简单的控制流分析就足以在一个函数中识别这类漏洞。

  • Taint-Style Vulnerability：结合语法、控制和数据流信息对漏洞进行建模，与只使用语法和控制流的漏洞分析相比，加上PDG可以使用数据流边建模额外的代码漏洞，比如：

  • Buffer overflow vulnerabilities：缓冲区溢出漏洞大多由没有对输入数据进行校验导致，在许多linux内核代码中，当系统从get_user读取外部输入数据作为第3个参数传递给copy_from_user或者memcpy函数时会触发该漏洞。所以遍历的时候需要检查get_user的第一个参数和copy_from_user(memcpy)的第3个参数。

  • Code injection vulnerabilities：在C语言中，注入类漏洞通常在CPG中存在从recv第2个参数到system第1个参数的路径，并且中间没有对字符串进行校验和检查。

  • Missing permission checks：web应用程序和内核代码通常都需要在执行操作之前检查用户权限，这类漏洞没有对用户可控数据进行检查，确保他们有足够的权限。

Experiment

为了进行评估，我们基于代码属性图的遍历过程实现了一个静态代码漏洞检测系统。针对不同的漏洞类型使用不同的代码表示来处理，如下图所示。

img

本文使用对CPG图遍历的方式在Linux内核源代码中识别了18个以前未知的漏洞，证明了该方案的有效性。

img

Conclusion

本文提出了一种基于代码属性图CPG的源代码漏洞检测方法，基于一种新颖的源代码表示形式，即代码属性图CPG，通过对图的遍历来对常见漏洞进行建模于检测。使用CPG图遍历的方式，本文对缓冲区溢出、格式字符串漏洞和内存地址泄漏等漏洞进行了建模与分析检测。此外，本文还审计了一个Linux内核代码库，并在源代码中确定了18个以前未知的漏洞，这些漏洞由供应商确认并修复。