大家好，我是TeddyBe4r，今天为大家带来CHA，ICFG和一些有关于过程间分析的内容。

大纲如下所示，该篇笔记主要解释 CHA 的构建算法，ICFG数据流分析方法，以及基础的 Call edge，Return edge，Call-to-Return edge 的一些概念和Transfer Node 在常量传播中的一些经典处理手法，详细精准的定义可以看图片中的内容，对于大白话方便理解的我在关键的地方都精炼成一句话方便大家理解。

Motivation

到目前位置我们学习的都是过程内分析的。我们一般假设都是 Safe-approximation
这样的话就会损失精度。为了提升精度我们需要进行过程间的数据流分析。

过程间分析就会顺着边来传递数据流。

为了更好的精度我们需要利用 call graph

调用图就是一个程序调用关系的表示，他是一个调用边的集合。

调用图的用途

调用图是一个非常重要的程序信息。

Static call

Special call

Virtual call (最难处理的)

Instruction

invoke static

invoke special

invoke interface

invoke virtual

Receiver Objects

NO

YES

YES

Target Methods

#Target Methods

1

1

>= 1(polymorphism)

Determinacy

complie-time

complie-time

runtime

对于OOP语言的调用处理最难的是虚方法。

对于虚方法而言通常是通过方法分发来进行操作的。该操作基于

可以通过设置Dispatch 函数来模仿这个动态分发的过程

值得注意的是这里的 m必须是一个非抽象的方法，如果c没有这个方法则需要往c的父类去寻找直到找到一个非抽象方法。这里我们辅佐以图来理解Dispatch的过程

DIspatch 例子

这里有一点值得注意的是 对于Special call的处理我们需要处理以下三种情况

一定要记住这里的T集合是包含当前类及其他的子类

给出一个例子帮助理解

值得注意的是对于 B b = ...; b.foo(); 做Dispatch 是包含A C D的因为 对B做Dispatch 的时候会

回溯到A类的 A.foo() 上面去。且一定记住CHA算法只考虑声明类型不考虑右值的实际类型

即便 B b = new B(); b.foo(); 也只和左值的类型有关。

经常会在IDE里面看到这种CHA方法。

本质上就是从入口方法开始递归的处理方法到方法的边，并且将这个边放到集合中去，直到没有一个新方法被发现。

例子

可以跟着该例子推导一下该算法。

在ICFG中有两种类型的边

ICFG = CFGs + call & return edges

ICFG例子

不过在这里我们需要注意，有了Call Edges和 Return Edges之后依旧需要保留原来基本块的CFG edges。

过程间常量传播分析例子

[培训]Windows内核深度攻防：从Hook技术到Rootkit实战！