跳到主要内容

技术研究：基于静态单赋值（SSA）的 YakSSA 程序分析

· 阅读需 6 分钟
Yak ProjectYak Project

数据流分析是什么

在程序分析之前，我们从数据流开始谈起。

首先来看这段代码：

var a = func1()
var c = 1
c += a
var target = func2(c)

在这段代码中，我们提出以下两个问题：

  • target 受到哪些变量的影响呢？

答案应该是c, 如果更加准确一些，应该要考虑到c +=a这样的语句，那么答案是c,a。

  • target 受到哪些值的影响呢？

答案应该是：func1,1,func2 这两个值，获得这样的答案应该是没问题的吧，

在我们读出这样的信息的时候，其实是在下意识的追踪传入到func2的这个c的数据流。**

ok，我们来讨论两个问题：

1、传入到func2的这个c，是指什么？

在原本的代码中，c这个变量：

  • 两处赋值的位置，分别为：c = 1, c = c+a，
  • 有两处使用的位置，分别为：c = c + a, sink(c)，

对于数值来说：c这个变量中保存了两个数值：

  • 数值：1， 这个值赋值给了c，然后在c = c + a的时候被使用。
  • 数值1+a， 这个值通过c = c(1) + a赋值给了c， 在func2(c)的时候被使用。

我们将两个不同值的变量c通过后缀进行区分，于是我们得到这样的代码：

var a = func1()
var c1 = 1
c2 = c1 +  a
var target = func2(c2)

此时，我们可以简单地解释，什么是传入到func2中的c，也就是c2。

2、数据流是什么

基于上面的这个例子，我们发现通过将重新赋值的变量拆分，我们可以直接让每一个变量都表示单独的一个值，那么进一步，为什么还需要变量呢？

如果去掉变量仅仅保留值之间的关系，我们将会得到以下这张图：

可以看到，这张图里，每一个节点都是值，函数本身是一个值，像这里的函数f和函数func1、func2，常量、运算、函数调用都是值。

数据流是通过有向图的形式表达值之间的使用和被使用的关系。

在这里呢，我们隐去了很多编译相关的前置知识，用这样一个例子展示了下数据流和基于数据流的程序分析，这其实是非常符合我们在分析一段代码时的逻辑的。

在编译领域的程序分析

首先 编译过程的概述图如下：

值得注意的有两点：

  • 多前端，通过统一的中间表示抽象出来编译中端，将多种前端进行整合，并将可通用的分析方案在编译中端进行。
  • 中端的多层级表示：中间代码表示一般会采用多种设计，从高级到低级会一层层转换，并在每一层都进行分析，最后通过最后一级最低的IR产生可执行代码。

在编译领域中，经常进行的分析有以下三种：

  • 基于抽象语法树(AST)的分析：

  • 基于三地址码形式的中间代码表示

  • 基于静态单赋值格式(SSA)的中间代码表示(IR)

编译领域的程序分析：SSA格式的IR​

编译领域程序分析的总览：

编译领域的程序分析​

在安全领域的程序分析

在安全领域的程序分析，在程序分析本身的要求上，应该有以下一些需求：

安全领域的程序分析：需求​

现状：

在现有的工具中，我们可以了解到：

  1. soot的传统数据流分析不能直接通过数据流图进行分析，并且这套方案维护复杂，很多基于soot的工具也只能在此基础上增加规则而非修改数据流分析方案。
  2. CodeQL的用户接口设计优秀，但基于AST的方案导致不同的语言API和分析方案基本都是特化的，甚至某些概念在不同语言中结构都不一致。

对于安全领域程序分析的一些探索：

需要一个强大的基于图的数据流分析方案，同时尽量保证其通用性，在不同语言中只需要前端接入，即可实现分析能力。

基于图的SSA格式IR的分析：这是各种编译器内部已经做的，从SSA这个概念提出、到LLVM中大量的使用、再到目前的绝大多数编译器都会保留这一设计，甚至目前的很多编译器中端设计中尽力保持SSA格式贯穿分析过程，这一分析思路已经在编译领域反复验证。

但同时，多语言的抽象和统一问题，传统SSA设计上的太过于底层以及内存操作指令 都导致在安全领域的实践中存在较大的差距。

YakSSA HIR

YakSSA的使用如下：通过简单的API即可进行：

  • ssaapi.Parse 进行程序的解析
  • 通过prog.Ref进行在数据流图上某个值的提取
  • 通过GetTopDefs进行对于该值的数据流分析。

可以看到在这一个例子中，和我们文章开头的例子一致，得到了一致的结果。

在以下的例子中，可以看到YakSSA在过程内的分析能力：

分析Yaklang语言，跨过程分析演示：

分析Java语言，左侧是代码，右侧是YakSSA测试以及结果，可以看到类之间的跨过程分析能力：

YakSSA效果演示：跨类分析 java 访问静态方法​

分析Java语言，跨越类对类成员的访问能力：

这是一个反例，可以发现对类成员的追踪的精准性。

本文首发于 Yak Project 公众号，阅读原文。