静态程序分析(一)
1 前言
1.1 静态程序的定位
静态程序分析在编程语言中的应用级别下是一个细分区域，这是非常重要的核心内容。在理论部分中，我们考虑了诸如如何设计语言的语法和语义，如何设计语言的类型系统等问题；使用语言的语法，语义和类型系统，我们需要支持该语言的操作。因此，在环境部分中，有必要考虑如何为运行程序提供运行时环境。如何设计编译器，在运行时需要什么支持（例如内存分配管理）等；该应用程序零件重点是确保用语言编写的程序的效率，安全性和可靠性，并主要考虑如何分析，验证和综合程序（如何自动合成程序）。
一词中，总结静态分析：平衡精度和速度，同时确保准确性。
1.2 静态程序分析的应用
提高计划的可靠性空指针参考和内存泄漏等。
提高程序安全性
隐私信息泄漏：主要存在于移动应用程序安全性中
注射攻击
汇编优化
消除代码：在编译器与机器无关的优化过程中，将删除不会影响程序执行结果的代码（即死亡代码）。
循环不变代码运动：在编译器的机器独立优化过程中，循环中的特定语句在循环外移动而不会影响程序执行结果，以便减少程序中执行的语句数量。
帮助程序理解
帮助集成开发环境的功能：当您使用VS/IDEA/CLION/ECLIPSE/ANDROID Studio和其他IDE时，将鼠标悬停在代码上。 IDE可以动态分析并提示您了解有关盘旋对象的相关信息。其背后使用的技术是静态程序分析。
1.3 Sound Complete
上面是静态程序分析希望做的一些事情，但实际上，静态分析已经发展到今天，无法完美地解决上述问题。R.E.语言是不可决定的。
用一种语言为递归可枚举（递归枚举），任何程序行为的non-trivial属性都是不可解释的。non-trivial property是指与程序操作行为有关的那些属性。
——Rice’s Theorem换句话说，赖斯理论告诉我们，世界上没有完美的静态分析的事情可以完美地解决上述问题。
从上图，我们可以直观地看到这三个是包容性的，完美的程序分析是中间的事实，这种情况既声音又完整，而我们的正常程序分析只能获得声音或完整的结果，这是有用的结果。
简而言之，声音是一个过多的输出，它会输出所有真实错误和一些错误的错误。虽然完成了，这会输出所有实际错误，但错误的错误比真相更少。
从以上，我们可以看到，在实际使用场景中，我们自然希望输出是合理的，这意味着可以有误报，但没有遗漏的报告。
1.4 静态程序分析的核心
1.4.1 抽象：Abstract
以符号分析为例，要分析的特定变量值抽象为：正，负，零，未知和误差。未知意味着，如果由于变量的变化，当前值将出现在不同的状态中，则将其定义为未知。
未定义是指数字或字符除以0，该数字或字符确定不符合INT的定义，例如数字或字符除以0。
1.4.2 近似：Over-approximation
1.4.2.1 转移函数：Transfer function
在静态分析中，近似的核心是定义传输函数。传输功能定义了程序中每个语句的抽象值的转换规则。
转移功能规则是根据分析的特定问题和程序语义定义的。
如上图所示：这是由符号分析定义的部分的转换函数，前五和八分之一是清晰的，不会解释。
第六是因为除数为0，因此结果不确定。第七是因为我们定义的转换函数是抽象的，并且操作的目标也是抽象的，因此添加结果未知。例如，即使我的正数为1000，我的负数为-1，在抽象后，然后通过转换函数进行处理，结果仍然未知，这也是声音的反映。
根据上述转换功能，可以分析程序语句，最终结果如下。
1.4.2.2 控制流：Control Flow
实际上，在程序分析过程中，必须在近似过程中考虑程序的控制流。
右图是左图的操作流程显示。在不同的情况下，y将具有一个值，并且根据声音原理，最后一步中的y值只能是未知的。
在程序分析中，不可能枚举所有路径，因此流动合并（控制流的收敛）是一种近似值，并且非常常用于静态分析中。
2 中间表示：Intermediate Representation
2.1 编译器与静态分析器
首先，让我们介绍编译器与静态分析仪之间的关系：
编译器的主要目的是将程序员编写的源代码转换为计算机可以理解的机器代码，并在转换过程中的时间报告错误。这是英语中语法规则的示例。
第一步是通过扫描仪扫描输入，并根据正则表达式（正则表达式）进行词汇分析。它主要分析每个字母和单词输入是否是法律字母和单词，然后将检测到的内容转换为令牌并将其传递给下一步。
第二步是通过解析器扫描令牌并基于无上下文语法（语法分析）执行语法分析，该分析主要分析几个单词的组合是否符合语法结构规则。然后，以抽象语法树（AST）的形式将检测到的内容传递到下一步中。使用与上下文无关的语法进行分析是为了加快分析效率。
第三步是通过类型检查器基于属性语法进行语义分析。理想的目的是识别诸如苹果之类的情况，以正确的语法结构饮食，但语义不正确。但是，实际的编译器只能识别类型错误，例如“不能用字符串除以INT”，因此此步骤称为类型检测。生成进一步处理的AST并将其传递到下一步。
步骤4：为了执行静态分析和优化，应将AST装饰的AST转换为中间表示（IR），通常将其转换为三个地址代码，然后进行静态分析。最后，优化的代码生成机器代码通过代码生成器传递给机器。
2.2 IR
010-1011以周期为例，以说明AST和IR之间的差异。 AST是一种语法树形式，一种高级形式，更接近程序的源代码，与语言相关，适用于快速类型检测，但缺少了控制流信息。IR是中间表示。图中表示三个地址代码。它是一种低级形式，靠近机器编码，独立于语言，紧凑的结构，包含了控制流信息，因此更适合静态分析。
ast
高级并封闭语法结构
通常依赖语言
适用于快速类型检查
缺乏控制流量信息
ir
低水平并关闭机器代码
通常是独立语言的
紧凑而均匀
包含控制流信息
通常被认为是静态分析的基础
因此，IR更适合静态分析
IR没有固定的定义，常用的三个地址代码
2.2.1 AST vs. IR
没有三个地址代码的正式定义。一般而言，这三个地址代码是一个表达式，最多有三个地址（地址），因此，每三个地址代码最多只有一个操作员。
在Java中，烟灰工具可用于生成三个地址代码，在烟灰中称为Jimple。让我们以DO-wilile循环为例，以分析其三个地址代码。
1
2
3
4
5
6
7
8
9
10
软件包nju.sa.example;
公共类dowhileloop3ac {
公共静态void main（string [] args）{
int [] arr=new int [10];
int i=0;
做{
i=i + 1;
} while（arr 10）;
}
}
转换后的三个地址代码是：
以方法调用为示例，以在对象环境中介绍以下三个地址代码。
1
2
3
4
5
6
7
8
9
10
软件包nju.sa.example;
公共类MethodCall3ac {
字符串foo（字符串para1，string para2）{
返回para1 +'' + para2;
}
公共静态void main（string [] args）{
MethodCall3ac mc=new MethodCall3ac（）;
字符串结果=mc.foo（'Hello'，'world'）;
}
}
与Java中的Invoke指令相对应的方法调用：
InvokeSpecial:呼叫构造函数，呼叫超类方法，呼叫私人方法
InvokeVirtual:实例方法调用
InvokeInterface:无法优化，检查接口实现
Indokestatic:呼叫静态方法
2.3 三地址码
控制流分析通常是指构建控制流图（CFG）并使用CFG作为静态分析的基础架构的过程。2.4 控制流分析
通常用于执行控制流分析的表示控制流程图可用于表示控制流的结构
控制流程图的节点可以是单个三个地址代码，但通常是基本块（BB），如下所示。
2.4.1 控制流图
BASIC BLOCK是一个块单元，由三个地址代码组成，为以下属性和最大长度：仅从块的第一个指令输入。
您只能从块的最后指令中离开。
如何构建基本块：
P的第一个指示是基本的块领导者
跳跃目标指令是基本的块领导者
跳跃指令的下一个指令也是基本的块领导者
一个基本块是基本块的领导者，也是下一个基本块领导的所有指令。
2.4.2 Basic Block
除了基本块外，CFG中还会有块边缘。且仅当块B之间有一个边缘：在A结束时，有一个指向B的跳跃指令。
A的结尾紧随B的开始，A的结尾不是无条件的跳跃指令。
请注意，每个基本块都与开始指令的标签唯一对应，因此自然需要将跳跃指令的目标更改为基本块的标签而不是指令标签:
通过这些定义，我们可以理解一些概念：
如果A -B，那么我们说A是B和B的前身。
除了构建的基本块外，我们还将添加两个其他节点，“输入”和“退出”
这两个节点与任何IR不符
入口有一个指向IR中的第一个指示的边缘
如果基本块的最后一个指令导致程序离开此IR，则基本块将具有指向出口的边缘。
这完成了控制流程图的构建。
2.4.3 边的生成
3 数据流分析
近似解决方案1：忽略程序的条件判断，并相信所有分析均可达到该程序可以被视为**状态（数据）和状态之间的传输（控制）是两个部分，因为状态传输的条件被忽略，核心分析部分是传输过程中状态数据的变化，因此称为数据流量分析。
近似解决方案2：不要在路径末端合并，在控制流收敛的所有位置都会提前合并。
数据流量分析必须确保安全- 抗氧化，也就是说：
5月分析:过度评价
必须分析:不受欢迎
简而言之，不同的数据流量分析具有不同的数据抽象方法（不同的应用程序），不同的安全- 附属策略以及不同的传输函数和控制流聚合方法。
3.1 相关概念
每个红外线的执行将从输入状态更改为新的输出状态。输入/输出状态与语句之前和之后的program point关联。
在数据流分析中，我们将每个程序点与数据流量值相关联，代表可以在该点观察到的抽象程序状态。数据流分析的目的是基于控制流和转换功能的所有语句的输入和输出函数找到一组安全近似约束解决方案。
3.1.1 输入输出状态
有两种类型的分析数据流：向前和向后：
3.1.2 转移函数
每个语句S将更改程序状态。 B的输出自然是多次转换后通过其输入获得的状态。必须根据数据流分析的要求处理B的输入。向后分析也是如此。
3.1.2 控制流约束
3.2 应用
3.2.1 到达定值分析：Reaching Definitions Analysis
假设X具有固定值d（definition），如果有一个路径从d紧接的点到达某个点P的路径，并且在此路径上没有其他固定值，则在此路径上没有其他固定值，则x ress x ress x ress x ress（reaching）。如果此路径上还有X的其他固定值，我们说变量X的固定值D被杀死（killed）
固定值可用于分析未定义的变量。例如，我们在程序条目中为每个变量引入一个虚拟固定值。当程序导出的变量的固定值仍然是虚拟的时，我们可以假设该变量未定义。
对于分配语句D: v=x op y，该语句生成了V的固定值D，并杀死了程序中变量V定义的其他固定值。
基本概念
数据流量值：程序中所有变量的固定值。
它可以使用位向量定义，并且与分配语句一样多。
d是定义，可以表示为：d：v=x op y
d可以视为三个地址代码的行，并做两件事：
生成了定义D
在保持其他传入程序的同时，杀死程序中可变V的其他定义
传输方程和控制流：
在上一篇文章中，u代表联合，与d代表的d相结合，我们可以知道，的输入等于out [p1]和out [p2]，这意味着只要有可以达到的路径，就可以认为可以达到。
理解到达定值分析
这是一种经典的迭代算法：
首先，让所有BB和入口的出口为空。因为您不知道BB中生成了哪些固定值。
当出现任何变化时，分析的常数值可能需要继续向下流动，因此需要修改每个BB的进出。
首先处理，然后根据转移更新输出。
在u（in -kill）中，