Static Analysis

学习目标：增强软件分析技能，争取研究明白java反序列化等安全漏洞自动化分析流程

学习网站：

https://www.bilibili.com/video/BV1zE411s77Z/?spm_id_from=333.788&vd_source=f558cd4ae6450e7fb80e7e92d161aee5

https://tai-e.pascal-lab.net/lectures.html

https://oj.pascal-lab.net/

年轻且优秀的授课老师，思路清晰，听了不会枯燥。

开始study

Introduction

Static Analysis Purpose

Static analysis analyzes a program P to reason about its behaviors and

determines whether it satisfies some properties before running P.

Does P contain any private information leaks?

Does P dereference any null pointers?

Are all the cast operations in P safe?

Can v1 and v2 in P point to the same memory location?

Will certain assert statements in P fail?

Is this piece of code in P dead (so that it could be eliminated)?

and so on.

但是，不存在完美的软件分析，可以给出确切的“Yes或No”的分析答案，一般目前的分析结果都符合sound或complete的范畴

Sound：可以理解为过拟合，查全率，他包含所有正确答案，但也有判断错误的结果，但宁可错杀不可漏掉，最重要

complete：他类似于欠拟合，查准率，他只找到不全的正确答案，虽然正确率高但效率不高

考虑更多的情况非常重要，尽可能多的考虑不同的分支，尽可能的soundness，不漏掉任何出错的可能。

最优秀的方案：兼顾二者，集效率和准确性一体

Abstraction：将一系列数据函数抽象为类似符号表达

Over-approximation-Transfer Functions：传递函数用于定义估算不同的抽象值之间的状态计算

example：通过符号化具体数值，定义他们之间的状态关系，可得出不同运算下的可行性，进而发现一系列潜在的问题

Over-approximation-Control Flows：在现实情况下，不可能列举所有分支的情况，所以引入控制流，将不同的分支情况merge

Intermediate Representation

contents

1. Compilers and Static Analyzers
2. AST vs. IR
3. IR: Three-Address Code (3AC)
4. 3AC in Real Static Analyzer: Tai-e
5. Static Single Assignment (SSA) 重点
6. Basic Blocks (BB)
7. Control Flow Graphs (CFG) 重点

compiler（编译器）主体框架

1、源码通过扫描器（Scanner）做词法分析（Lexical Analysis）：根据正则表达式（Regular Expression）检查输入字符是否合法（例如如果是翻译一个英语句子，就是检查字符是否是英文的，单词是否正确/合法），如果通过了词法分析，每个单词就会生成Tokens，给下一步进行分析。
2、Tokens通过解析器（Parser）做语法分析（Syntax Analysis）：通过语法规则（上下文无关文法，Context-Free Grammar）检查语法，通过就转换成抽象语法树AST
3、AST通过类型检查（Type Checker）做语义分析（Semantic Analysis）：根据属性语法（Atrribute Grammar）检查语义（期望实现的是识别在英语中的例如Apple eats you，这样语法正确但是语义不对的句子，但是实际上实现的是，例如String的值除以int 这种类型不匹配的错误）如果通过，就生成Decorated AST
4、为了进行静态分析优化，要将Decorated AST转换为中间表示(IR)，这里的IR一般为三地址码，再进行静态分析，最后通过代码生成器将优化后的代码生成机器码传给机器。

    实际上，静态分析就是做code优化的，静态分析器在IR的基础上进行分析。

AST与IR比较

重点区别如下：AST依赖编程语言，IR更通用

IR通常采用3地址码（3AC）

三地址码的特性

1. 简洁性：每条三地址码通常只包含三个操作数（两个操作数和一个结果），这使得它比高级语言的语法更简单，更接近底层机器代码。
2. 易于优化：三地址码结构简单，便于进行各种优化，如常量折叠、死代码消除、代码移动等。
3. 独立于目标机器：三地址码不依赖于特定的机器架构，因此可以在代码生成前进行各种优化和变换。
4. 易于生成目标代码：由于其简单的结构，生成最终的机器代码或汇编代码变得更加直接和高效。

Tai-e框架解析三地址码

先搭建好实验环境https://tai-e.pascal-lab.net/intro/setup.html

class Assign {

    int assign(int a, int b, int c) {
        int d = a + b;
        b = d;
        c = a;
        return b;
    }
}

红框处设置好要测试的类

可以得到由Tai-e得到的三地址码

第一段初始化可以理解所有类都继承Object,第二段为赋值情况

public class Method3AC {
    String foo(String p1,String p2){
        return p1+" "+p2;
    }
    public static void main(String[] args) {
        Method3AC m = new Method3AC();
        String result = m.foo("hello", "world");
    }
}

JVM中主要的方法调用：

invokespecial：用于调用实例构造器()方法、私有方法和父类中的方法
invokevirtual：调用非私有实例方法，比如 public 和 protected，大多数方法调用属于这一种，在调用的过程中会进行派生(vitual dispatch)
invokeinterface：调用接口方法，会检查实现这个接口的对象，但是调用的时候不能做一些优化
invokestatic：调用静态方法

静态单赋值(Static Single Assignment, [SSA]

1、SSA里每个变量是不同的名称

2、如果同一个变量在不同的分支，会引入 Φ函数，如下图所示，在引入x2 等于这个 Φ 函数，后续使用x2。这个Φ(x0，x1)会根据流的路径来选择是x0 还是x1然后赋值给x2

SSA的优点：

• 程序流信息可以间接体现在不同的变量名上，通过不同的变量名，流的信息被间接地合并到唯一的变量名中
• 可能有助于提供一些更简单的分析，例如，流不敏感分析通过SSA定义和使用对显式获得流敏感分析的部分精度。（因为流敏感度分析精度虽然高，但是太耗时了，而流不敏感分析就相当于上下文无关的分析，通过单一赋值制就可以获得很久之前就定义过的信息，知道是具体用了那边信息，就相当于获取到了上下文信息。）
• Define-and-Use pairs（定义-使用对）明确
• 在一些按需任务中启用更有效的数据事实存储和传播。
• 一些优化任务在SSA上表现更好（例如，条件常数传播，全局值编号）。

SSA的缺点：

• 如果程序有太多分叉，则会引入太多变量和Φ函数，
• 在最后还要转为机器码执行，在转换回去的时候由于过多的赋值操作产生性能方面的影响

重点！！！Control Flow Analysis

如何构建BB？

Basic Blocks（BB）是连续的、满足以下性质的、最大长度的 三地址指令的组成单元：

• 这个Block的入口只有一个，就是第一个指令，不能从其他地方进来。
• Block的出口只有一个，就是最后一条指令，不能从其他地方出去。

INPUT: 一个三地址指令序列 P
OUTPUT: P 的Basic Block列表

Method:

​ (1) 确定 P 的入口 (leaders)
​ · P 的第一句是一个入口
​ · 任何一个跳转的目标指令，是一个入口
​ · 任何一个跳转的下一条指令，是一个入口
​ (2) 建立BBs for P
​ · 每个入口到下一个入口之间就是一个BB

根据上述算法，可划分出不同的BB

并且由于BB的定义导致跳转目标必定是某个BB的入口指令，所以可以将跳转目标的指令标签的形式，换成BB的编号。如下图所示，将原本的跳转到指令标签(7)替换为跳转到基本块 B4

最后我们需要将不同的BB之间连线，遵循以下规则：

A--->B 是跳转过去的，则A到B 建立一个边，B5->B2
A--->B 是有条件跳转，B2->B4
B2--->B4 建立一条边（if goto）
B2--->B3(A紧接着的下一条指令 B) 也需要建立一条边（条件jump block 天然有两出口）
A->B 无条件跳转，对于紧挨着A的下一条指令

B5->B2建立一条边

B5->B6不建立边

以上是第二节课IR的总结，未完待续。。。