静态分析学习笔记
想学静态分析已经很久了但是一直没有系统的学习过,中间看过asm字节码技术、gadgetinspector、tabby、codeql的原理分析但依然对于静态分析不了解,最近感觉也快离开学校了想在离开学校之前学会这个技术
program analysis
Compilers and Static Analyzers
编译器将source code 转换为machine code 其中流程图如下图所示

Intermediate Representation
看上图得知在translator层将decorated AST 翻译为生成三地址码这样的中间表示形式(Intermediate Representation)并对其做静态分析,也就是说静态分析基于IR,通常IR的表现形式为三地址码(3AC,Three-Adress Code),静态程序分析通常会将IR转换为CFG(Controll Flow Graph)进行下一步分析
Three-Address Code(3AC)
3AC是一种IR,在每个指令的右边至多有一个操作符,每一语句最多有三个“地址”,地址可以是名称,变量,常量(编译器生成的临时变量 Compiler-generated Temporary: t1, t2)
常见的3AC如下
x = y bop z:双目运算并赋值,bop = binary operator
x = uop z:单目运算并赋值,uop = unary operator
x = y:直接赋值
goto L:无条件跳转,L = label
if x goto L:条件跳转
if x rop y goto L:包含了关系运算的条件跳转,rop = relational operator
在soot中的3AC如下
@parameter
:函数参数$x
:临时变量<method signature>
:类+返回值类型+方法名+函数参数类型<init>
:构造函数<clinit>
:类初始化函数(静态变量初始化等)invokespecial
:调用构造函数、父类方法、私有方法invokevirtual
:实例方法调用(virtual dispatch)invokeinterface
:不能优化、调用接口、检查接口实现invokestatic
:调用静态方法invokedynamic
:运行其他动态语言
Static Single Assignment(SSA)
静态单赋值(SSA),就是让每次对变量x赋值都重新使用一个新的变量xi,并在后续使用中选择最新的变量传递到接下来的使用当中,每个变量有唯一的定义,优点是但缺点也很明显,就是因为会引入过多的变量还有phi function,优点也是因为变量唯一而唯一的变量名可以间接体现程序流信息,简化分析过程
- Give each definition a fresh name
- Propagate fresh name to subsequent uses
- Every variable has exactly one definition
1 | 3AC | SSA |
Basic Blocks (BB)
basic blocks是一个最长的语句序列,并保证入口只能在最开始指令且出口只能在最后一个指令,实际操作为将程序的若干个三地址码分为几个basic blocks,每个bb都满足上图的要求,下面将程序标注为p 如何去构建这些bb的算法为
INPUT: A sequence of three-address instructions of P
OUTPUT: A list of basic blocks of P
METHOD:
(1) Determine the leaders in P
- The first instruction in P is a leader
- Any target instruction of a conditional or unconditional jump is a leader
- Any instruction that immediately follows a conditional or unconditional jump is a leader
(2)build bb :A BB consists of a leader and all its subsequent instructions until the next leader
Control Flow Graphs
Control Flow Graphs的主体就是basic blocks,我们对basic blocks添加块到块的边,添加的规则是块 A 和块 B 之间有一条边,
1、基本块A的结尾有跳转指令跳转到基本块B
2、原始指令序列中,B紧跟着A,且A的结尾不是无条件跳转。
除了这两个添加规则以外,我们还需要添加两个额外的节点entry和exit,所以刚才图片构成的bb画成cfg图应该如下图所示
<<<<<<< HEAD
=======
81841d6924b6b29513f63a397204312cda445246