车如流水马如龙,花月正春风

静态分析学习笔记

静态分析学习笔记

想学静态分析已经很久了但是一直没有系统的学习过，中间看过asm字节码技术、gadgetinspector、tabby、codeql的原理分析但依然对于静态分析不了解，最近感觉也快离开学校了想在离开学校之前学会这个技术

program analysis

程序分析01_1.jpg

Compilers and Static Analyzers

编译器将source code 转换为machine code 其中流程图如下图所示

FI_KA39SJY32Q_LEO_4_3HQ.png

![M5_45`QM_V__CAWWZB_W2UG.png](https://img.le1a.com/2023/01/17/5168adfe73eaa.png)

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
2
3
4
5
3AC        | SSA
p = a + b    p1 = a + b
q = p - c    q1 = p1 - c
p = q * d    p2 = q1 * d
q = p + q    q2 = p2 + q1

OS_LE_8_UV5FCCR01TI93_I.png

Basic Blocks (BB)

  • 96G6H7BZ@@3~___~XPPLRUX.png

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

  • O21_@_F`B`_AU_8_@EH_VVB.png

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