赛博空间，攻防之战，此起彼伏
矛与盾的对决，攻与守的碰撞
在这里，我们一起来看
道德黑客使用了哪些杀手锏
正义蓝军如何见招拆招
-
本文描述的静态程序分析是基于Java来描述的；
-
有现成的Fortify等工具可以使用，为啥还要学习这个？因为想要“知其然”，而且挖洞过程中，很多时候需要自己挖Gadget，Fortify是满足不了滴；
-
本文主要粗略的讲解了静态程序分析的概念，最后通过两个开源项目（GI 和 ByteCodeDL）讲解静态程序分析理论的落地实践；
-
本文假设读者对Java有一定的熟悉；
-
本文目的：帮助对静态程序分析（或者说自动化代码审计）感兴趣的小伙伴快速入门；
-
文笔粗糙，学识短浅，如有遗漏或者错误，烦请多多指教。
推荐学习路线和资料如下：
-
现存的唯一的系统学习课程：南京大学的《静态软件分析》课程；上B站搜一下就能搜到公开课；
-
GadgetInspector：使用Java ASM模拟JVM堆栈，实现调用图分析、污点传播分析；
-
Datalog引擎souffle：https://souffle-lang.github.io/tutorial；
-
neo4j图数据库：https://www.cnblogs.com/ljhdo/p/5516793.html ；
-
ByteCodeDL：使用soot生成fact，使用souffle作为datalog引擎，最后使用neo4j进行可视化，实现了多种程序分析算法；
-
ByteCodeDL
discussions：https://github.com/BytecodeDL/ByteCodeDL/discussions ；
-
Doop介绍：https://y4er.com/posts/doop-1/ ；
-
Doop Issus：https://bitbucket.org/yanniss/doop/issues/27 ；
-
Tabby：基于soot生成代码属性图，应用案例比较多：https://github.com/wh1t3p1g/tabby；
-
静态程序分析相关论文：https://yanniss.github.io/ ；
-
pascal实验室公开论文（李樾、谭添老师所在的实验室）：https://pascal-group.bitbucket.io/code.html 。
IR（Intermediate Representation）
IR即“中间表示”，通常IR的表现形式为三地址码（3AC，3 Adress Code），静态程序分析通常会将IR转换为CFG（Controll Flow Graph）进行下一步分析；
三地址码（3AC）的特征：一条指令的右侧最多有一个运算符，每一个3AC最多包含3个address，每种类型的指令都有对应的3AC；
例如如下语句：
t2 = a + b + 3可以转换成对应的三地址码：
t1 = a + b
t2 = t1 + 3通常IR就是把源代码转换成对应的3AC，例如如下代码：
do i = i+1; while(a[i]<v);将上面的代码转换成对应的IR，具体形式如下：
IR的特点如下：
-
low-level并且贴合机器码（和汇编很像）；
-
通常不依赖于语言（由此便可以使用不同的前端，把不同的Source Code翻译成统一的IR）；
-
结构比较紧凑和均匀；
-
包含控制流信息；
-
通常被认为是静态程序分析的基础；
在实际应用中，我们常见到的IR有soot生成的Jimple，也是3AC的格式，例如如下Java代码：
public static void main( String[] args )throws Exception{
App app = new App();
// source, new taint
String exp = app.source();
// taint arg -> ret
exp = app.addSuffix(exp);
// transform taint arg to ret
exp = app.transform(exp);
app.sink(exp);
app.sink(app.bak);
}
使用soot生成Jimple如下：
public static void main(java.lang.String[]) throws java.lang.Exception
{
org.example.App $stack3, app#_10;
java.lang.String $stack7, exp#_12, exp_$$A_1#_14, exp_$$A_2#_17;
java.lang.String[] args#_0;
args#_0 := @parameter0: java.lang.String[];
$stack3 = new org.example.App;
specialinvoke $stack3.<org.example.App: void <init>()>();
app#_10 = $stack3;
exp#_12 = specialinvoke app#_10.<org.example.App: java.lang.String source()>();
exp_$$A_1#_14 = specialinvoke app#_10.<org.example.App: java.lang.String addSuffix(java.lang.String)>(exp#_12);
exp_$$A_2#_17 = specialinvoke app#_10.<org.example.App: java.lang.String transform(java.lang.String)>(exp_$$A_1#_14);
specialinvoke app#_10.<org.example.App: void sink(java.lang.String)>(exp_$$A_2#_17);
$stack7 = app#_10.<org.example.App: java.lang.String bak>;
specialinvoke app#_10.<org.example.App: void sink(java.lang.String)>($stack7);
return;
}
下文，我们的程序分析基本都是围绕Jimple这种3AC来进行分析。
SSA（Static Single Assignment）
SSA即为“静态单一分配”，SSA中的所有赋值都有不同名称的变量，详细解释如下：
-
每个定义需要给定一个新的名字；
-
将新名称传播给后续使用；
-
每个变量都只有一个定义。
例如如下即为3AC和SSA的对比：
一般生成SSA要比3AC慢很多（慢是真的慢，而且吃内存，类似泛微这种项目，一天一夜都生成不完），但是有时可以利用SSA来提高非敏感数据流分析的精度。
CFG（Control Flow Graph）
-
通常所有的控制流分析（Control Flow Analysis）指的就是创建控制流图（Control Flow Graph）；
-
CFG是静态程序分析的基本结构；
-
CGF中的节点可以是单独的3AC，或者（通常）是基本块（BB，Basic Block）；
一个将3AC转换成CFG的示例如下：
上面的CFG中，存在两个特殊的节点：Entry和Exit，这两个节点的性质如下：
-
它们不对应于可执行的 IR；
-
Entry存在一条Edge指向一个BB，这个BB包含整个IR的第一条指令，也就是这个BB是整个程序的第一个BB；
-
某个BB存在一条Edge指向Exit，这个BB包含整个IR的最后一条指令，也就是这个BB是整个程序的最后一个BB。
Data Flow Analysis
Data Flow Analysis即数据流分析，数据流分析可以概括为：How Data Flows on CFG？也就是：How Application-specific Data Flows through the Nodes(BBs/statements) and Edges(control flows) of CFG(a program)？
-
这里的Application-specific Data指的就是我们静态分析时关注的抽象（Abstraction）数据，例如进行污点分析时，我们关注的就是污点对象；
-
Node通常通过转换函数（Transfer functions）进行分析处理，例如函数调用（Method Call），形参到返回值的转换处理；
-
Edge的分析也就是Control-flow处理，例如GOTO等指令的处理；
-
不同的数据流分析存在不同的抽象数据（data abstraction）、不同的safe-approximation策略、不同的tranfer functions以及不同的control-flow handings。
例如，如果我们关注程序变量的正负等状态，那么此时的Application-specific Data指的就是表示变量状态的一些抽象符号；Transfer functions指的就是各种加减乘除运算；Control-flow handing指的就是merges处的符号合并。
Input and Output States
-
每一个IR的执行，都会将input state转换成output state；
-
input(output) state和statement之前(之后)的program point相关；
-
在每个数据流分析应用中，我们在每个program point处都关联了一个data-flow value，这个数据流值代表了可以在该点观察到的所有可能程序状态的集合的抽象；
-
数据流分析就是，对于程序中的所有IN[s]和OUT[s]，需要找到一个方法去解析一系列的safe-approximation约束规则；这些约束规则基于语句的语义（transfer functions）或者控制流（flows of control）。
图示如下：
Transfer Function’s Constraints
-
Transfer Function’s Constraints即基于转换函数的约束规则，主要分为两种，一种是Forward Analysis，另外一种就是Backward Analysis；
-
对于Forward Analysis来讲，IN[s]经过转换函数fs的处理，可以得到OUT[s]；
-
对于Backward Analysis来讲，OUT[s]经过转换函数fs的处理，可以得到IN[s]。
图示如下：
Control Flow’s Constraints
-
Control Flow’s Constraints即基于控制流的约束规则，主要体现在BB之间以及BB之内；
-
对于
IN[Si+1] = OUT[Si]，要说明的含义其实就是，对于每一个statement，后一个statement的输入就是前一个statement的输出；因为BB中的statement不能存在分叉啥的，所以能这么认为；
-
对于
IN[B] = IN[S1]以及OUT[B] = OUT[Sn]，要说明的含义其实就是，对于每一个BB，其输入就是第一个statement的输入，其输出就是最后一个statement的输出。
Interprocedural Analysis
Interprocedural Analysis即为过程间（程序间）分析，前面讲到数据流分析等都是程序内的分析，是不处理方法调用的，如果遇到了函数调用，对于过程间的分析如何处理？过程间分析会沿着过程间的控制流edges进行数据流传播。
一个简单的图示如下：
为了更方便的进行过程间分析，我们通常还需要构造Call Graph。
Caller & Callee & Receiver
为了方便后续的讲解，先在此处说明下caller、callee和receiver的概念，它们的具体图示如下：
Call Graph
Call Graph即为调用图，也就是程序中调用关系的表示。本质上，call graph是一组从call-sites到他们的目标方法的调用边（call edges），call-sites的目标方法称为（callees）。
一个Call Graph图示如下：
call graph是过程间分析的基础，对于创建call graph的几种比较有代表性的算法如下，越往上，速度越快，但是精度越低，越往下速度越慢，但是精度越高。
Method Calls（Invocations） in Java
对于Java程序而言，总共分为三种函数调用：Static Call、Special Call、Virtual Call；其中主要关注的就是Virtual Call，Virtual Call也是Java多态的关键体现，对于Virtual Call，调用的目标方法（callee）只能在运行时确定，对于静态程序分析而言，确定callee就成了一个难点。
Method Dispatch of Virtual Calls
对于Virtual Call，其callee只能在运行时才能确定，callee的确定（或者说Dispatch）取决于 ：
-
receiver object的true type；
-
call site的方法描述（Descriptor）；
我们暂且认为方法签名和方法描述是由如下部分组成：
Signature = class type + method name + descriptor
Descriptor = return type + parameter types图示如下（实际上Doop中的soot-fact-generator生成的方法前面就是这种格式）：
最后我们可以定义一个 Dispatch(c, m) 方法来模拟运行时call-site具体方法的调用；算法如下：
大概含义就是，寻找true type为c，调用的方法为m的真实目标方法（因为Java多态问题，Virtual Call需要计算运行时真实调用的方法），如果c类中存在一个非抽象的方法m’，其方法名和方法签名和要寻找的m一样，则m’即为我们需要找的真实方法；否则从类c的父类中去寻找m；
一个示例如下：
CHA（Class Hierarchy Analysis）
-
CHA即为类层次结构分析算法，对于这种算法，它需要知道程序中类的继承结构信息（hierarchy information），例如需要知道某个类的父类和子类有哪些；
-
CHA的主要思想就是在一个call site中，根据receiver variable的desclared type计算virtual call；
-
CHA假设变量a可以指向类A以及类A的所有子类的对象，所以CHA计算目标方法的过程就是查询类A的整个继承结构来查询目标方法；
-
CHA算法是1995年在ECOOP会议上首次发表出来的。
CHA中推导实际调用的目标方法的算法如下，其中的cs指的是call site：
一个计算案例如下：
CHA的优势是速度快，原因如下：
-
只考虑call site中receiver variable的declared type和它的继承结构；
-
忽略数据流和控制流信息。
CHA的劣势是精度较低，原因如下：
-
容易引入虚假目标方法；
-
没有使用指针分析。
Call Graph Construction
即通过CHA算法生成Call Graph，步骤如下：
-
从入口方法开始（例如对于Java而言的main方法）；
-
对于每一个可达方法m，在方法m中通过CHA算法为每一个call site计算目标方法；
-
重复这个过程直到没有新的方法被发现。
图示如下：
具体的算法如下：
一个使用CHA算法构建Call Graph的图示如下：
Pointer Analysis
Pointer Analysis即指针分析；如果我们使用CHA创建CallGraph，我们知道CHA仅仅考虑Class Hierarchy（类继承关系），那么正对如下程序分析，因为Number存在三个子类，那么调用 n.get() 方法的时候，就会产生三条调用边，其中有两条是假的调用边，导致最终分析的结果是一个不准确的结果：
而如果通过指针分析，那么就可以清楚地知道变量n指向的对象，由此只会产生一条调用边，此时分析的结果就是一个precise（精确）的结果：
-
指针分析是静态程序分析的基础，用于计算一个指针可以指向的内存；
-
对于OO语言而言，用于计算一个变量或者对象的field可以指向哪个对象；
-
可被认为是一个may-analysis：在over-approximation的约束下，计算一个指针可能指向的对象集合；
-
拥有超过40多年的研究历史，并且至今还是一个热门研究领域。
Pointer Analysis and Alias Analysis
两者很相关，但是又有如下不同：
-
Pointer Analysis：分析一个指针可以（may）指向那些对象；
-
Alias Analysis：分析两个指针是否能指向同一个对象；
-
Alias信息可以从指针指向关系中推导出。
如下程序中，变量p和q指向相同的对象，则称p和q是alias，但是x和y不是alias：
p = new C();
q = p;
x = new X();
y = new Y();Key Factors in Pointer Analysis
指针分析是一个复杂的系统，许多因素会影响指针分析的精度和效率，各种影响因素如下：
Heap Abstraction
-
Heap Abstraction即堆抽象，需要解决的一个问题就是：如何对程序中的Heap Memory进行建模；
-
在动态执行时，程序会因为循环和递归等产生无穷无尽的对象（heap object）；
-
使用静态程序分析时，因为模拟动态执行会产生无穷无尽的对象，程序分析无法终止，所以就引出一种堆抽象技术，把无穷无尽的对象抽象成有限个数的对象；
例如使用堆抽象技术，把左边无穷无尽的对象，抽象成右边有限个数的对象：
堆抽象有很多分支，下文会详细讲解Allocation sites（调用点的抽象）这个分支：
Allocation-Site Abstraction
-
是目前使用最广泛的堆抽象技术；
-
通过程序中的allocation sites进行对象建模；
-
通过程序中的每个创建点（allocation site）构建一个抽象对象。
如下示例中，通过创建点构建堆抽象，把三次循环的对象抽象成一个allocation site抽象对象：
Context Sensitivity
Context Sensitivity即上下文敏感，需要解决的一个问题就是：如何构建调用构建上下文（calling context）；
当使用上下文不敏感的指针分析时，不同位置的相同函数调用，会被merge成一个数据流，从而造成精度丢失，但是如果使用上下文敏感的指针分析，对于不同位置的相同函数调用会根据不同的调用上下文（calling context）进行区分，然后分别分析每个context，图示如下：
Flow Sensitivity
Flow Sensitivity即流敏感，需要解决的一个问题就是：如何构建控制流；
所谓流敏感，就是在分析过程中，会遵循程序的执行流，即会遵循程序中语句的执行顺序，在程序的每一个statement都会维护当前程序指针指向的关系映射，而流非敏感则是相反的；如下图所示，左边蓝色的是流敏感分析的结果，右边是流非敏感的分析结果，会产生一个false positive：
Analysis Scope
Analysis Scope即分析范围，需要解决的一个问题就是：分析程序中的哪一部分；
这个概念比较好理解，要么分析全部，要么分析程序中我们感兴趣的部分。
Concerned Statement
Concerned Statement即需要关心的Statement，现代程序语言中，有很多类型的statements，比如 if-else ， switch-case ， for/while/do-while 等等，但是对于指针分析，我们并不用关心全部类型的statements，那些不会直接影响指针的statements会被忽略；我们只关注那些影响指针的statements；
值得一提是，对于数组元素的指针处理，我们一般会忽略数组的索引，把整个数组抽象为一个整体的、单独的对象；
Java中可以影响指针的5种Statement如下，后续的很多指针分析算法都是围绕着这几个Statement进行处理：
现阶段常见的静态程序分析流程：soot生成fact→编写datalog规则→datalog引擎（常用souffle）执行datalog规则得出结果；
所以在进入程序分析算法这步之前，还需要了解Datalog；
Datalog主要用于描述关系，是一种声明式逻辑编程语言，目前最常见的一种实现Souffle：https://souffle-lang.github.io/ 。
Predicates
-
本质上，谓词就是一个数据表；
-
一个Fact代表一个特定的元组（也就是数据表的某一行）属于某一个Relation（也就是某一个表），即它代表一个谓词对于特定的值组合为真；
-
在datalog中，一个谓词（或者说关系，Relation）是一系列特定值组合的集合；
例如如下表中，Age就是一个谓词（或者说关系），它表明了所有person的age，从而得出 Age("C0m3ct",3) 是真，而 Age("P1n93r",6) 为假。
|
Predicate / Relation：Age |
|
|
person |
age |
|
C0m3ct |
3 |
|
P1n93r |
18 |
Atoms
-
主要分为两种原子：关系型原子（Relational atom）和算术型原子（arithmetic atom）；
-
例如
Age("C0m3ct",3)就是一个关系型原子，而age>18则是一个算术型原子。
Datalog Rules
-
Rule是逻辑表达式推理的一种方式；
-
Rule还用于指定如何推断事实（fact）；
-
Rule的格式为：
H :- B1,B2,…,Bn.；这个Rule表明，如果H为真，则B1,B2,…,Bn也必须为真；
-
如果一条Rule为：
H :- B1,B2,…,Bn.，那么我们称H为header，则B1,B2,…,Bn称为body；
-
Rule的body中，逗号
,表示逻辑与的关系，封号;表示逻辑或；
-
例如通过前面的
Age(person,age)关系可以推导出Audit(person) :- Age(person,age),age >= 18.
Souffle是一款常用的datalog的引擎，这里主要简单介绍一下souffle。
注释和预处理器
souffle支持两种注释：
// 这是注释
/* 这是注释 */souffle支持C预处理器（比如定义宏）：
#include "myprog.dl"
#denfine MYPLUS(a,b) (a+b)关系声明
关系的声明就是前面说到的datalog的谓词，用于定义一系列特定的元组存在的某种关系，例如如下的关系定义/声明：
// 定义了一个关系edge，代表一系列特定元组 (a, b) 存在edge这个关系，a和b的类型都是symbol，这是一种类似strings的类型
.decl edge(a:symbol, b:symbol)I/O指令
编写dl文件的时候，我们可以使用IO指令进行fact的加载和输出，这些指令分别为：
-
.input <relation-name>指令：从<relation-name>.facts中加载facts，默认使用tab符号进行数据分隔；
-
.out <relation-name>指令：默认情况下，将分析得出的facts写出到<relation-name>.csv文件中；
-
.printsize <relation-name>指令：在控制台中打印给定关系的facts数量。
语法糖
为了减少代码编写工作量，可以在一条规则中编写多个head，如下所示，左边是使用了语法糖的情况，右边是没有使用语法糖的情况：
类似的，也可以在规则体中使用析取（disjunction），如下所示，左边是使用了语法糖的情况，右边是没有使用语法糖的情况（规则推导中的封号代表逻辑或）：
原始类型
souffle存在两种原始数据类型：
-
symbol：它包含所有的字符串，它的内部实现是一个ordinal number；
-
number：和 int 类似。
算术表达式
souffle支持的算术函子如下：
-
加法：
x+y；
-
减法：
x-y；
-
除法：
x/y；
-
乘法：
x*y；
-
模数：
a%b；
-
幂运算：
a^b；
-
计数器：
autonic()；
-
位操作：
x band y、x bor y、x bxor y和bnot x。
-
逻辑操作：
x land y、x lor y和lnot x；
souffle支持如下算术约束：
-
小于：
a < b；
-
小于或等于：
a <= b；
-
等于：
a = b；
-
不等于：
a != b；
-
大于或等于：
a >= b；
-
大于：
a > b。
数字编码
写规则的时候，可以在源码中使用十进制、二进制和十六进制，但是在facts文件中，只支持十进制：
.decl A(x:number)
A(4711).
A(0b101).
A(0xaffe).简单例子
例如如下 example.dl 文件内容：
// 声明一个Predicate: edge
.decl edge(x:number, y:number)
// 表明需要从磁盘中读取一个edge.facts文件，这里是从文件中读取facts，也可以直接在本dl中定义facts
.input edge
// 声明一个Predicate: path
.decl path(x:number, y:number)
// 表明运行结束会生成一个path.facts文件
.output path
// rule推导
path(x, y) :- edge(x, y).
path(x, y) :- path(x, z), edge(z, y).然后创建一个 edge.facts 文件，内容如下，这个就表明了edge这个Relation：
1 2
2 3然后直接运行如下命令，得到推导出来的path结果，其中， -F 指定了facts所在的目录，而 -D 制定了输出目录， example.dl 为datalog文件：
P1n93r@bogon example % ll
total 16
drwxr-xr-x 4 P1n93r staff 128B 4 28 19:20 .
drwxr-xr-x 3 P1n93r staff 96B 4 28 19:15 ..
-rw-r--r-- 1 P1n93r staff 8B 4 28 19:20 edge.facts
-rw-r--r-- 1 P1n93r staff 336B 4 28 19:19 example.dl
P1n93r@bogon example % souffle -F. -D. example.dl
P1n93r@bogon example % ll
total 24
drwxr-xr-x 5 P1n93r staff 160B 4 28 19:20 .
drwxr-xr-x 3 P1n93r staff 96B 4 28 19:15 ..
-rw-r--r-- 1 P1n93r staff 8B 4 28 19:20 edge.facts
-rw-r--r-- 1 P1n93r staff 336B 4 28 19:19 example.dl
-rw-r--r-- 1 P1n93r staff 12B 4 28 19:20 path.csv
P1n93r@bogon example % cat path.csv
1 2
1 3
2 3关于作者：
p1n93r：吴钩实验室安全研究员，主要研究方向为攻防技术、自动化漏洞挖掘。
原文始发于微信公众号（青藤智库）：自动化漏洞挖掘：静态程序分析入门【上】
