taibeihacker
Moderator
静态程序分析(二)
1 调用图：Call Graph Construction
1.1 概念
本質上來說，一個調用圖就是從調用點到目標方法(callee)的一系列调用边。
程序調用圖是過程間分析的基礎，可以用於程序優化、理解、調試、測試等。
1.2 分类
Call Graph 有很多種不同的構造方法，本文接下來會講解兩個極端：最準確的和最快速的。
調用圖構造主要作用於面向對象語言，即以Java 為代表的，面向對象的語言。一般用到如圖四種算法，其中CHA 是最快的，指針分析K-CHA 是最準的，本文主要將CHA，後面的文章會講指針分析。
1.3 Java 中的方法调用形式
Instruction：指Java 的IR 中的指令Receiver objects：方法調用對應的實例對象（static 方法調用不需要對應實例）。
Target methods：表示IR 指令到被调用目标方法的映射关系Num of target methods：call 對應的可能被調用的目標方法的數量。 Virtual call 與動態綁定和多態實現有關，可以對應多個對像下的重寫方法。所以Virtual call 的可能对象可能超过 1 个。
Determinacy：指什麼時候能夠確定這個call 的對應方法。 Virtual call 與多態有關，只能在運行時決定調用哪一個具體方法的實現。其他兩種call 都和多態機制不相關，編譯時刻就可以確定。
1.4 Virtual Call的方法调度函数 (Dispatch)
Virtual call 是幾種調用中最為複雜的一種，首先重點討論它。在動態運行時，Virtual call 基於兩點決定調用哪個具體方法：virtual call 返回內容的接收對像是誰：c調用點處的方法签名：mSignature=class type + method name + descriptor
Descriptor=return type + parameter types
本文中的方法簽名定義如下：
定義Dispatch(c,m) 函數來描述函數間的分配關係：Java 中Dispatch 機制決定具體調用哪個方法，c 是類名，m 是一個方法。如果能在本類中找到name 和descriptor 一致的方法，則調用c 的方法，否則到父類中尋找。
一個示例：Dispatch 關注Receiver Object 即new B() 和方法簽名：A.foo()
2 Class Hierarchy Analysis (CHA)
2.1 定义
需要首先獲得整個程序的類繼承關係圖通過接收變量的聲明類型來解析Virtual call
接收變量的例子：在a.foo() 中，a 就是接收變量
假設一個接收變量能夠指向A 或A 的所有子類
2.2 具体过程
下面介紹解析調用的算法。定義Reslove(cs) 函數為：通過CHA 算法尋找到某個程序調用點對應的可能的目標函數實體。
call site(cs) 就是調用語句，m(method) 就是對應的函數簽名。
T 集合中保存找到的結果
三個if 分支分別對應之前提到的Java 中的三種call 類型
Static call
Special call
Virtual call
2.2.1 static call
靜態方法調用前寫的是類名，而非靜態方法調用前寫的是變量或指針名。靜態方法調用不需要依賴實例。因此靜態方法調用的分析結果十分簡單，很明顯調用的就是當前類的方法，所以直接加到集合T 中。
2.2.2 special call
special call 主要分為三種情況。上圖是第一種使用super 類的調用方法。 foo() 雖然在當前類有定義，但是實際使用的是父類的foo()，因此需要使用Dispatch 函數，其中的foo() 的簽名m 由編譯器返回信息可以知道是B 的，那麼獲取foo() 返回值的c 也指向B，也就相當於在父類中尋找了。
為什麼處理super 調用需要使用Dispatch 函數？在下圖所示情況中沒有Dispatch 函數時無法正確解析C 類的super.foo 調用：
而Private instance method 和Constructor（一定由類實現或有默認的構造函數）都會在本類的實現中給出，使用Dispatch 函數能夠將這三種情況都包含，簡化代碼。
2.2.3 virtual call
最後是處理virtual call，這也是CHA 區別於其他算法的主要之處。該算法會對此方法做一個Dispatch(c,m) 並將c 的所有子集以及子集的子集全都做一次Dispatch(c', m)。直觀來看，可以分為兩步，第一步是對本身做一次Dispatch，看看當前類中是否有foo()，沒有的話就到父類中遞歸地找；第二步是在當前類地所有子集中找到所有的foo()，然後將這些foo 同第一步找到的foo 全都加入T 中。
一個例子：
常用於IDE 中，給用戶提供提示。比如寫一小段測試代碼，看看b.foo() 可能會調用哪些函數簽名。可以看出CHA 分析中認為b.foo() 可能調用A、C、D 中的foo() 方法。
2.3 CHA 的特征
只考慮類繼承結構，所以很快因為忽略了數據流和控制流的信息，所以不太准确2.4 调用图构建
分為三步：從入口方法進入，一般是main 方法
對於每個可到達的方法m，通過CHA 算法找出點調用的方法m' 的調用位置
對於每個m (以及新加入的m') 都進行第二步，知道不再有新的方法被發現
構造調用圖的算法如下：
Worklist 記錄需要處理的methods
Call graph 是需要構建的目標，是call edges 的集合
Reachable method (RM) 是已經處理過的目標，在Worklist 中取新目標時，不需要再次處理已經在RM 中的目標
一個例子：
3 过程间的控制流图：Interprocedural Control-Flow Graph
ICFG=CFGs +call return edges調用邊：從調用點call site 到被調方法callee 的入口返回邊：從callee 的返回語句到call site 的下一句
圖示便是過程間的控制流圖，ICFG 本質還是CFG，應該用三地址碼構成的Basic Block 構成，但是此處為了清晰分析，所以還是將BB 拆開來分析。
4 过程间数据流分析：Interprocedural Data-Flow Analysis
4.1 定义与比较
過程間分析多了一個調用返回邊及對應的傳遞函數。
Call edge transfer：從調用者向被調用者傳遞參數
Return edge transfer：被調用者向調用者傳遞返回值
Node transfer：與前面文章提到的傳遞函數基本一樣，但是多了一個性質，對於每次調用(例如b=foo(a)) 會將等式左側的數值kill 掉，然後在下一步中有返回邊傳遞函數重新賦值。這個操作可以在返回值與原值不同時防止數據衝突。
4.2 示例
這一段存在的必要性？
如果沒有這一段，那麼變量a 在分析被調用函數的全程中都需要記住a 的值，這在程序運行時會浪費大量內存。
此外，要記得在調用語句處kill 掉表達式左邊的值，否則會造成結果的不准確：
