静态程序分析(二)
1 调用图：Call Graph Construction
1.1 概念
本质上是，呼叫图是从呼叫点到目标方法（CALLEE）的一系列调用边。
程序呼叫图是过程间分析的基础，可用于程序优化，理解，调试，测试等。
1.2 分类
呼叫图有许多不同的构造方法，本文将来将解释两个极端：最准确和最快。
呼叫图构造主要作用于面向对象的语言，即Java代表的面向对象的语言。通常，使用四种算法如图所示，其中CHA是最快的，指针分析K-CHA是最准确的。本文主要包括CHA，随后的文章将讨论指针分析。
1.3 Java 中的方法调用形式
指令：指Java的IR 中的指令接收器对象：方法调用的相应实例对象（静态方法调用不需要相应的实例）。
目标方法：指示IR 指令到被调用目标方法的映射关系目标方法：调用可能被调用的目标方法的数量。虚拟呼叫与动态绑定和多态性实现有关，并且可以对应于多个对象下的重写方法。因此，Virtual call 的可能对象可能超过 1 个。
确定性：指确定该调用的相应方法何时确定。虚拟呼叫与多态性有关，只能决定在运行时呼叫的哪种特定方法。其他两种呼叫与多态性机制无关，并且可以确定汇编时间。
1.4 Virtual Call的方法调度函数 (Dispatch)
虚拟呼叫是几个呼叫中最复杂的调用，因此首先，重点是。动态运行时，虚拟呼叫确定基于两个点呼叫的特定方法：虚拟呼叫返回内容的接收对象：c方法签名：m在呼叫点签名=类Type +方法+方法名称+描述符
描述符=返回类型+参数类型
本文中的方法签名定义如下：
定义调度（C，M）函数来描述函数之间的分布关系：Java中的调度机制确定称为哪种方法，C是类名称，M是一种方法。如果您可以在此类中找到与名称和描述符一致的方法，请调用C的方法，否则在父类中搜索。
一个示例：调度关注接收器对象，即新的B（）和方法签名：a.foo（）
2 Class Hierarchy Analysis (CHA)
2.1 定义
您需要首先获得整个程序的类继承关系图通过接收变量的声明类型来解析虚拟调用
接收变量的示例：在A.Foo（）中，A正在接收变量
假设接收变量可以指向A或A的所有子类
2.2 具体过程
以下描述了解析呼叫的算法。重新解析（CS）函数定义为：要通过CHA算法找到与程序呼叫点相对应的可能的目标函数实体。
呼叫站点（CS）是呼叫语句，M（方法）是相应的函数签名。
将发现的结果保存在T集合中
这三个如果分支对应于前面提到的Java中的三种呼叫类型。
静态通话
特别电话
虚拟呼叫
2.2.1 static call
班级名称是在调用静态方法之前编写的，并且在调用静态方法之前编写变量或指针名称。静态方法调用不需要依赖性实例。因此，静态方法调用的分析结果非常简单。显然，当前类的方法被调用，因此直接添加到集合T。
2.2.2 special call
特殊呼叫主要分为三种情况。上图是使用超级类的第一个调用方法。尽管FOO（）是在当前类中定义的，但实际上使用了父类的foo（），因此有必要使用调度函数。 FOO（）的签名m由编译器返回，可以称为B。然后，获得Foo（）的返回值的C也指向B，这等同于在父类中查看。
为什么需要使用调度函数来处理超级呼叫？如果没有调度函数，在下图中所示的情况下，无法正确解析C类的super.foo调用：
私有实例方法和构造函数（必须由类实现或具有默认构造函数），全部在此类的实现中给出。使用调度函数可以包括所有三个情况以简化代码。
2.2.3 virtual call
最后，这是处理虚拟呼叫，这是CHA和其他算法之间的主要区别。该算法将对所有C和子集的子集的所有子集和子集子集进行此方法和调度（C'，M）进行调度（C，M）。直观地，它可以分为两个步骤。第一步是自己派遣自己，看看当前类中是否有foo（）。如果没有，请在父类中递归搜索；第二步是在当前类的所有子集中找到所有foo（），然后在第一步中添加所有这些foos。
一个例子：
通常用于IDE，为用户提供提示。例如，编写一小部分测试代码，以查看B.FOO（）可以调用哪些功能签名。可以看出，在CHA分析中，据信B.Foo（）可以在A，C和D中称为FOO（）方法。
2.3 CHA 的特征
仅考虑类继承结构，因此很快由于忽略了数据流和控制流的信息，因此不太准确2.4 调用图构建
分为三个步骤：从入口方法输入通常是主要方法
对于每个可访问方法M
对于每个M（和新添加的M'），请迈出第二步，知道找不到新方法
用于构建呼叫图的算法如下：
需要处理的工作清单记录方法
呼叫图是需要构建的目标，它是通话边缘的集合
到达方法（RM）是已处理的目标。当工作清单中采用新的目标时，无需处理已经在RM中的目标。
一个例子：
3 过程间的控制流图：Interprocedural Control-Flow Graph
ICFG=CFGS +call return edges呼叫边缘：从呼叫点呼叫站点到称为Callee的入口返回边缘：从Callee返回语句到呼叫站点下一句
该图是过程之间的控制流程图。 ICFG本质上是CFG，应由由三个地址代码组成的基本块组成。但是，为了进行清晰的分析，BB仍被分开和分析。
4 过程间数据流分析：Interprocedural Data-Flow Analysis
4.1 定义与比较
还有一个额外的调用返回边缘和相应的传输功能，用于过程间分析。
调用边缘传输：将参数从呼叫者传递到callee
返回边缘传输：Callee将退货值传递给呼叫者
节点传输：基本上与上一篇文章中提到的传输功能相同，但是还有一个额外的属性。对于每个呼叫（例如，B=FOO（A）），方程左侧的值将被杀死，然后将在下一步中重新分配返回边缘传输函数。当返回值与原始值不同时，此操作可以防止数据冲突。
4.2 示例
本段的必要性？
如果本节不可用，则变量a需要记住在调用函数的整个分析中的值，这将在程序运行时浪费大量内存。
此外，请记住在呼叫声明中杀死表达式左侧的价值，否则结果将不准确：
