Lingze's blog Lingze's blog
timeline
about
friends
categories
tags

lingze

bin不是垃圾桶的意思!
timeline
about
friends
categories
tags
  • ssa
lingze
2024-05-09
目录

探索程序分析:以静态单赋值(SSA)格式为基础的YakSSA

# 摘要

本文从一段Golang代码示例出发,通过剖析变量与值的数据流向,解释了数据流分析的核心逻辑。

进一步探讨编译领域中的程序分析技术(AST、三地址码、SSA IR),对比其优缺点,并重点介绍安全领域对程序分析的需求与挑战。

最后,提出基于统一图结构SSA中间表示(YakSSA HIR) 的创新方案,展示其在多语言跨过程、跨类精准分析中的实践能力。


# 数据流分析是什么

在程序分析之前,我们从数据流开始谈起。 首先来看这段代码:

var a = func1()
var c = 1
c += a
var target = func2(c)
1
2
3
4

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

  • 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)
1
2
3
4

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

# 2. 数据流是什么

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

为什么还需要变量呢?

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

数据流图示意图

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

数据流是值之间的使用和被使用的关系。

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

# 在编译领域的程序分析

首先 编译过程的示意图如下:

编译过程示意图

需要注意的有两点:

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

对照编译过程示意图,在编译领域中,经常进行的分析有以下三种:

# 基于抽象语法树(AST)的分析:

  • 优点:和源码关系密切,可以非常细节地和源码相对应
  • 缺点:难以进行有效的数据流分析

# 基于三地址码形式的IR

  • 优点:创建和转换三地址码非常简单。并且和机器码类似,三地址码可以进行针对不同后端的机器码的优化。
  • 缺点:仍然没有办法直接分析数据流,而且相对于AST距离源码也有较大的差距。

# 基于静态单赋值格式(SSA)的IR

  • 优点:该指令的设计上就直接引出了使用-被使用的值的关系,天然可以进行数据流分析。
  • 缺点:SSA专注于值的关系追踪,需结合其他机制处理变量作用域,并且产生SSA格式需要额外的计算

# 编译领域程序分析的总览:

# 在安全领域的程序分析

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

# 现有的方案的现状

  1. soot的传统数据流分析不能直接通过数据流图进行分析,并且这套方案维护复杂,很多基于soot的工具也只能在此基础上增加规则而非修改数据流分析方案。

  2. CodeQL的用户接口设计优秀,但基于AST分析,尽管通过部分统一接口缓解差异,但部分语言特性仍导致分析逻辑特化。

# 我们的一些探索

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

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

但同时:

  • 编译器SSA在设计上通常忽略高级语义,而安全分析需保留更多语义信息。
  • 编译器SSA在工程实践上通常针对对应的语言,甚至和语言特性耦合,在多语言的抽象和统一问题上存在问题。

都导致在安全领域的实践中存在较大的差距。

# YakSSA HIR

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

  • ssaapi.Parse 进行程序的解析
  • 通过prog.Ref进行在数据流图上某个值的提取
  • 通过GetTopDefs进行对于该值的数据流分析。 可以看到在这一个例子中,和我们文章开头的例子一致,的到了一致的结果。

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

分析Yaklang语言,跨过程分析演示:

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

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

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

上次更新: 6/24/2025, 5:07:55 AM
Theme by Vdoing | Copyright © 2019-2025 lingze | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式