支持局部調用圖生成的指針分析

萬志遠，周 波

（浙江大學 計算機科學與技術學院，浙江 杭州310027）

調用圖（call graph）是一種描述軟件程序中方法間調用關系的有向圖［1］，通常表示為G＝（V，E）.其中，頂點集V 表示程序中的程序單元（如方法、過程）集合，有向邊集合E 表示程序中程序單元的調用關系集合.調用圖用途廣泛，是編譯器、軟件驗證工具和程序理解工具進行過程間分析（interprocedural analysis）的先決條件［2］.

現代面向對象編程語言大量使用動態分配（dynamic dispatch），程序中調用點的目標方法由調用點接收對象（receiver）的運行時類型（runtime type）決定.由于程序的任意部分可構造接收對象，大部分靜態程序分析工具和框架均采用基于全程序分析［3-8］（whole-program analysis）的 調 用 圖 生 成 方法.在文獻［9］的實驗中，基于全程序分析生成的調用圖中，平均有超過50%的頂點為Java標準庫中的方法，對于實驗中大部分的被分析程序，這一數字甚至超過80%.事實上，許多軟件工程應用并不關注調用圖中庫方法間的調用關系.對于現代面向對象程序語言，全程序分析的可擴展性問題嚴重阻礙了其在實際中的應用，庫和框架規模的日益增長加劇了這一問題.這些庫包括程序語言標準庫（如：Java程序語言的J2SE、C＋＋語言的STL）、領域相關的方法庫（如：圖像處理和線性代數）以及可擴展的框架和中間件.本研究統一使用“庫”一詞來表示程序所依賴的所有庫方法.

分析實際應用程序可以發現，與程序中庫的代碼量相比，應用部分的代碼量規模較小.對于許多Web應用程序而言，庫代碼在靜態分析時甚至不可用，因為應用部分依賴的庫在實際部署時才能確定（如：Servlet容器）.因此，本研究不分析庫部分代碼，以提升調用圖生成方法的性能.

本研究提出一種指針分析方法，用于生成完整且精確的應用部分局部調用圖.該指針分析方法僅分析應用部分代碼以及應用部分所引用的庫部分代碼中的方法簽名、類的域和類層次結構（class hierarchy）.該方法對標準指針分析進行擴展，構建混合堆模型（heap model），以區分應用部分及庫部分的抽象內存位置.方法為程序中的每一變量維護一個混合指針指向集合（points-to set）.此外，該方法構建一系列規則對應用部分和庫部分的交互行為進行建模，并利用這些規則推導庫部分的指針信息.該方法使用庫的混合指針指向集合解析調用圖中的庫回調邊，并限制回流進入應用部分指針指向集合的抽象對象.本研究在Soot程序分析框架上實現該方法，并在14個Java基準程序上對該方法的性能及生成調用圖的完整性和精確性進行評估.

1 研究背景

1.1 調用圖生成技術

對于面向對象編程語言，程序中調用點的目標方法由動態分配決定.對于調用點v.m（…），目標方法由調用的接收對象v 的運行時類型決定.運行時類型可通過指針分析獲取，通常存儲于指針指向集合中.文獻中［3］、［4］中的調用圖生成技術通常采用On-the-fly方法構建程序的調用圖.一方面，On-thefly方法對于被分析程序中的調用點v.m（…），使用變量v的指針指向集合確定調用點的目標方法，逐步構建調用圖.另一方面，逐步構建的調用圖為指針分析提供過程間指針信息，進一步構造指針指向集合.在On-the-fly調用圖生成方法中，指針指向集合的構造和調用圖的生成同時進行，直至指針指向集合或調用圖中沒有變化產生.

1.2 局部調用圖生成技術

大部分靜態程序分析工具和框架均采用基于全程序分析的調用圖生成方法.然而，基于全程序分析的調用圖生成方法無法滿足應用領域的實際需求.首先，基于全程序分析的調用圖生成方法資源消耗大.由于程序應用部分大量使用庫代碼，即使在分析規模相對較小的程序時，基于全程序分析的調用圖生成方法運行也會消耗大量硬件資源.如圖1所示，Spark 框 架（運 行 環 境：Intel Core 2 2.33 GHz E6550CPU，2GB RAM）在對該程序進行全程序分析生成調用圖時，運行時間超過40s，內存消耗超過250 M.其次，全程序分析生成的調用圖中大多數調用邊為庫方法的調用關系.以圖1為例，經Spark產生的調用圖中，共有101 229條調用邊，其中應用部分內部的調用邊僅25條.然而，許多應用領域并不關注全局調用圖中庫方法間的調用關系，因此，應用部分的局部調用圖比全局調用圖更具實際意義.

一種構建局部調用圖的解決方案是提升方法的可擴展性，只分析應用部分代碼，完全排除庫中代碼產生的影響.這種方法被用于靜態分析框架WALA中［3］.該方法在分析中完全排除庫代碼產生的影響，導致生成的調用圖不完整.具體原因在于：1）調用圖缺少從庫到應用部分的回調邊，因而缺失對回調邊目標方法的分析；2）該方法忽略庫與應用部分的交互，包括方法調用語句和STORE／LOAD語句，因而缺失庫與應用部分之間的抽象對象交換信息.

另一種構建局部調用圖的解決方案既考慮方法本身的可擴展性，也兼顧構建的調用圖的精確性和完整性.該方案通過對庫代碼進行預分析，計算庫方法的方法摘要（procedure summary），摘要描述庫方法的指針信息.當應用部分調用庫中的某方法時，該方案直接使用被調用方法的方法摘要，從而避免對該庫方法的重復分析.這一方案也存在問題：在生成和使用方法摘要時，需要面臨抽象表達及算法設計等諸多技術挑戰，無縫使用方法摘要需額外的基礎結構支持［9］.

圖1 局部調用圖的Java示例程序說明Fig.1 Sample Java program for illustration of partial call graphs

以上2種解決方案各有利弊，本文選取第3種解決方案，不分析庫的具體行為從而保證調用圖生成方法的可擴展性，并對庫的指針信息進行假設，從而保證調用圖的完整性及精確性.該解決方案將被分析程序的庫部分視為黑盒，不分析庫中方法的調用關系.

1.3 全局調用圖和局部調用圖

如圖2所示分別為由Spark和本研究方法構建的調用圖分支.圖1中示例程序的全局調用圖2（a）和局部調用圖2（b）的2個分支.局部調用圖中包含3種類型的調用邊.

1）應用調用邊（application call graph edge）的源方法與目標方法均為應用部分的方法，如圖2（b）中的指示線①所示.

2）庫調用邊（library call graph edge）的源方法屬于應用部分，目標方法屬于庫部分，如圖2（b）中的指示線②和③所示.在進行實驗數據統計時，當應用部分的某方法一次或多次調用庫部分方法時，僅向局部調用圖中添加一條庫調用邊.

3）庫回調邊（library call back edge）的源方法屬于庫部分，目標方法屬于應用部分，如圖2（b）中的指示線④所示.

圖2 由Spark和本文方法生成的調用圖分支Fig.2 Two branches of call graphs generated by Spark and proposed approach

2 指針分析方法

2.1 方法特征

本研究提出的指針分析方法為流不敏感、上下文不敏感、域敏感的Andersen風格［10］指針分析方法，采用On-the-fly調用圖生成方法.輸入為Java類集合，該集合稱為應用類.應用類依賴于其他Java類，被依賴的Java類集合稱為庫類.該指針分析方法分析完整的應用部分代碼，但不分析庫代碼的方法體（method body），僅分析庫代碼中方法的簽名、類的域以及類的層次結構.

堆模型（heap model）是指針分析中重要的設計要素.最常見堆模型將任一個靜態內存分配點（allocation site）視為單一的抽象內存位置.該方法不分析庫代碼的方法體，庫中的內存分配點不可知.因此，該方法使用混合堆模型以區分應用部分和庫部分的內存位置：使用內存分配點表示應用代碼所生成的抽象對象，使用類名表示庫代碼所生成的抽象對象.

通常，利用指針分析計算程序中的指針指向關系，即將每一個指針變量映射到運行時可能指向的對象的超集.典型的指針指向關系通過變量的指針指向集合表示.對任一變量v，其對應的指針指向集合中的每一個抽象對象o 均滿足（v，o）這一指針指向關系.

混合堆模型將單一指針指向集合擴展為混合指針指向集合.混合指針指向集合包含2部分：應用指針指向集合和庫指針指向集合.

定義1 （應用指針指向集合）對于被分析程序中的變量v，定義應用指針指向集合為PtA（v），該集合包含應用部分代碼創建的抽象對象，由內存分配點表示.

定義2 （庫指針指向集合）對于被分析程序中的變量v，定義庫指針指向集合為PtL（v），該集合包含庫部分代碼創建的抽象對象，由類名表示.

2.2 集合及概念

被分析程序的類集合為Cls，應用部分代碼所聲明的類集合為ClsA，庫部分代碼所聲明的類集合表示為ClsL.Cls定義的方法集合為Method.類cls∈ClsA，聲明的域由集合fields（cls）＝｛f0，f1，…，fq-1｝表示.域包含非靜態域集合F 以及靜態域集合SF.本研究將靜態域視為特殊形式的全局變量，通過引入一個人工構造域［］表示數組中的元素.

通常，方法m∈M 具有參數列表、本地變量及由語句序列組成的方法體.應用部分的變量集合由V 表示.本地變量vi∈V.任一方法m 具有k 個參數，參數依次表示為p0，p1，…，pk-1.對于非靜態方法，p0表示參數this.Java編程語言中參數可被視為一種特殊形式的本地變量，即pi∈V.方法m 的方法體由語句序列組成，不同類型語句組成語句集合Statement.如表1所示，本研究關注指針操作相關的基本語句，并假設所有復雜的語句及表達式均可拆分為基本語句.表1中的基本語句類型可表達Java編程語言中的大部分語義.本指針分析方法為流不敏感，因此不考慮分支語句和循環語句.CALL語句和RETURN 語句處理過程間控制流，每個CALL語句對應于一個調用點（call site），應用代碼中的調用點由集合C 表示.

集合O 表示程序代碼創建的抽象對象集合.其中應用代碼創建的對象集合為OA，庫代碼創建的對象集合為OL，OA∪OL＝O.

表1 基本語句及其對應的指針賦值圖實體Tab.1 Elementary statements and corresponding pointer assignment graph entities

2.3 程序表示

本指針分析構造指針賦值圖（pointer assignment graph，PAG）［11］用于表示被分析程序的指針信息.PAG 由3類節點組成，分別是內存分配節點（allocation node）、變量節點（variable node）和域解引用節點（field dereference node）.內存分配節點表示抽象對象，是對應用代碼的內存位置建模，集合為OA.變量節點表示程序中的本地變量、方法參數、返回值及靜態域.域解引用節點表示域訪問的表達式，通過對變量節點的參數化，表示解引用操作.PAG 的節點由4類邊相連，包含new／newarray、assign、store和load，反映了抽象對象的流動方向.

本方法遍歷被分析程序的語句序列，根據基本語句與PAG 實體的對應關系創建PAG 實體，逐步構造PAG.表1 顯示了不同類型的基本語句與PAG 實體的對應規則，其中v、vi、vR、cls.f 和this為變量節點，o為內存分配節點，vi.f 為域解引用節點.在處理過程間數據流時，每一個方法m 的形式參數都在PAG 中存在相應節點，此外，還存在一個特殊節點retm，表示m 的返回值.對于方法m 中的每一個調用點c，在實際參數和形式參數對應的節點間添加assign邊，并在調用m 的方法中被賦值的變量對應的節點和retm間添加assign 邊.PAG 中每一個節點n都擁有一個指針指向集合，集合中包含所有可能被該節點引用的抽象對象，這些抽象對象沿PAG 邊傳播.

2.4 庫模型

2.4.1 定義 本研究不分析庫代碼的方法體，提出以下模型表示程序的庫部分信息.

變量 定義Library為庫代碼中的任意變量.

方法 定義mL為庫代碼中的任意方法.

指針指向集合 庫部分存在唯一指針指向集合Pt（Library），該指針指向集合包含2 部分.其一為PtL（Library），包含抽象對象o∈OL，這些對象被庫代碼引用.假設庫部分代碼能創建及引用任意庫類的對象，因此，PtL（Library）隱式地包含庫部分所有類的對象，這些對象由對應的類名表示.其二為PtA（Library），包含抽象對象o∈OA，這些對象在應用部分創建，并被庫代碼引用.

調用點 cL為庫部分代碼中的任意調用點，可調用庫類中的任意可見方法和非靜態應用類cls中的方法m，該方法重寫庫方法.此外，存在抽象對象o∈PtA（Library），StaticType（o）為cls的本身或者cls的子類.StaticType（o）表示對象o的靜態類型.

2.4.2 抽象對象推測 由于應用部分和庫部分交互，部分抽象對象從應用部分逃逸至庫部分，反之亦然.通過分析應用部分和庫部分的交互行為，可推測出創建于庫部分的抽象對象集合OL，更新應用部分代碼中變量的庫指針指向集合.

針對不同類型的基本語句定義如下規則，以推測庫部分創建的抽象對象集合及變量的庫指針指向集合.

1）實例載入

規則1 對于語句v2＝v1.f，非靜態域f在cls∈ClsL中聲明：

StaticType（f）∈OL；

StaticType（f）∈PtL（v2）.

其中，StaticType（v）表示變量v的靜態類型.

2）靜態載入

規則2 對于語句v＝cls.f，cls∈ClsL：

StaticType（f）∈OL；

StaticType（f）∈PtL（v）.

3）靜態方法調用

考慮應用部分代碼中的靜態方法調用，假設目標方法為靜態方法m，該方法在某庫類中聲明.

規則3 對 于 語 句vR＝cls.m（v1，…，vj），X∈ClsL：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

其中，vi表示實際參數，retm表示方法cls.m 的返回值.

4）實例方法調用

考慮某一個應用部分的方法存在一個實例方法調用，該方法調用的目標方法為實例方法m，該方法在某庫類中聲明.

規則4 對 于 語 句vR＝v0.m（v1，…，vj），v0∈V：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

考慮庫方法中一個實例方法調用，假設目標方法為實例方法m，該方法在某庫類中聲明并被某應用類的方法重寫，它也是某條庫回調邊的目標方法.

規則5 對于語句Library.m（v1，…，vk）：

StaticType（this）∈OL；

StaticType（this）∈PtL（this）；

StaticType（vi）∈OL；

StaticType（vi）∈PtL（vi）∧1≤i≤k.

2.5 虛函數調用的處理

定義3 CallGraph為程序應用部分的局部調用圖，CallGraph是由調用邊組成的有限集合.調用邊定義為三元組（m1，m2，c），其中m1，m2∈｛mL｝∪Method，且c∈｛cL｝∪C，調用邊連接調用點和調用點對應的目標方法.

對于應用部分的方法M 中的虛擬函數調用點v.m（…），依照以下2條規則，使用PtA（v）和PtL（v）解析調用點c∈C 的目標方法，并構建調用邊.

規則6 對于抽象對象o∈PtA（v），存在StaticLookup（StaticType（o），m）＝m′：

（M，m′，c）∈CallGraph.

規則7 對于抽象對象cls∈PtL（v），存在StaticLookup（cls，m）＝m′：（M，m′，c）∈CallGraph.

以上規則中，StaticType（o）表示對象o的靜態類型，StaticLookup（cls，m）表示通過靜態查詢獲得聲明于類cls中簽名為m 的方法.

對于庫部分代碼中的虛擬函數調用點，定義如下規則，利用PtA（Library）解析調用點cL的目標方法，構建庫回調邊.

規則8 對于每一抽象對象o∈PtA（Library），方法m 聲明于cls∈ClsA，并且滿足cls∈｛Static-Type（o）｝∪SuperTypes（StaticType（o）），方法m重寫庫類方法：（mL，m，cL）∈CallGraph.Super-Types（cls）表示類cls超類型的集合.

3 實 驗

實驗旨在驗證本研究提出方法的可擴展性、生成調用圖的完整性及精確性.實驗中將本文提出的方 法 與Spark［11］和Averroes［12］方 法 進 行 對 比.Spark指針分析框架構建在Soot分析框架之上，采用全程序分析方法生成調用圖.Averroes為當前最新的局部調用圖生成方法，分析程序的庫方法以生成字節碼級別的占位庫（placeholder library），通過Spark及其他全程序分析框架分析應用部分代碼和占位庫，構建局部調用圖.實驗結果表明：

2）性能方面，本文方法平均分析時間為32s，比Averroes的平均分析速度快4.9倍，比Spark的平均分析速度快13.7倍.

2）調用圖完整性方面，除缺失2條庫調用邊，本文提出方法生成的調用圖覆蓋基準程序動態調用圖中所有調用邊，該結果與Averroes相同.

3）調用圖精確性方面，與全程序分析調用圖生成方法Spark相比，本文方法額外產生中位值22條應用調用邊、中位值2 條庫調用邊以及中位值23條庫回調邊.相較于Spark 產生的調用圖中調用邊的總量，本文方法生成的調用圖中額外調用邊數量可忽略不計.

3.1 實驗準備

實驗 的 運 行 環 境 為Intel Core 2 2.13 GHz p7450CPU 及2 GB RAM.實驗使用DaCapo v.2006-10-MR2基準程 序［13］和SPEC jvm 98 基 準 程序［14］，采用與文獻［12，15］相同的配置.實驗中分析JDK 1.4Java標準庫（jre 1.4.2＿11）.實驗中選取的基準程序具體信息如表2所示.

3.2 方法實現

在Soot［4］框架2.5.0 版本上實現所提出的指針分析方法（PtaPCG），通過Spark［11］指針分析框架驅動方法的執行.實驗中對Soot進行配置，將分析的范圍限定在程序的應用部分，實現基于PAG 節點工作隊列，該隊列中PAG 節點PtA／L存在更新.對于每隊列中的每一個個PAG 節點，將PtA／L中的抽象對象傳播至相鄰節點的指針指向集合中.抽象對象的傳播同時會引起：1）應用部分新的可達方法被發現；2）新發現的可達方法引起實際參數和形式參數、返回值以及本地變量間的PAG 邊的創建；3）應用部分和庫部分的指針指向集合間抽象對象的流動.

當不存在未處理的可達方法并且PAG 節點的工作隊列為空時，算法將終止.實現擴展Spark標準指針分析，包括創建庫指針指向集合、傳遞庫指針指向集合中的抽象對象以及使用庫指針指向集合解析調用點.此外，還對以下方面進行了優化.

1）數組.由于Soot程序分析框架將所有的數組元素建模成數組引用域［］，代碼實現中將數組中每個元素的指針指向集合進行合并，從而形成該數組引用的指針指向集合.

2）反射和動態類加載機制.反射和動態類加載機制在Java程序中廣泛使用.然而，由反射機制引起的類和方法的訪問無法通過靜態分析確定.實現中利用TamiFlex［16］收集的動態運行信息，確定由反射產生的程序行為.

3）標準庫.通過分析發現，許多傳入標準庫代碼的抽象對象并未被其他庫方法引用，如傳入類java.lang.Object構造器的對象.代碼實現中對這些標準庫方法進行特殊處理，當這些方法被調用時，不將抽象對象傳入庫部分的指針指向集合中.

3.3 性 能

如圖3 所 示 為PtaPCG、Averroes和Spark 的運行時間.PtaPCG 的運行性能良好，平均運行時間為32s.與Averroes相比，PtaPCG 平均分析時間快4.9倍（最小為1.9倍，最大為33.9倍，幾何平均為4.9倍），與Spark 相 比，PtaPCG 平 均 分 析 時 間 快13.7倍（最小為3.3倍，最大為131.2倍，幾何平均為13.7倍）.

實驗結果表明，PtaPCG 顯著提升了Spark 的性能.性能提升的原因在于生成調用圖時PtaPCG未對庫部分的方法體進行分析，Averroes的運行時間分為2個部分：1）預分析時間：Averroes生成占位庫所使用的時間，圖3中顯示為AverroesPlaceholder；2）分析時間，Spark使用Averroes占位庫進行全程序分析生成調用圖的運行時間，圖3 中顯示為AverroesAnalysis.分析發現，Averroes的運行時間大部分為預分析時間.

表2 本實驗使用的基準程序信息Tab.2 Information of benchmarks used in proposed experiment

圖3 PtaPCG、Averroes和Spark分析基準程序的運行時間對比Fig.3 Comparison of time taken by PtaPCG，Averroes and Spark for each benchmark program

3.4 調用圖完整性

實驗中通過對存在于由＊J［17］工具記錄的動態調用圖、缺失于由靜態工具生成的靜態調用圖的調用邊數量進行統計，評估PtaPCG、Averroes 和Spark產生的調用圖的完整性.動態調用圖是＊J工具通過觀察和記錄基準程序的動態運行得到的.實驗結果如表3 所示，“Dynamic”行顯示了基準程序的動態調用圖中應用部分調用邊的數量，“Dynamic＼PtaPCG”行、“Dynamic＼Averroes”行和“Dynamic＼Spark”行分別顯示了PtaPCG、Averroes和Spark生成的靜態調用圖中缺失的動態調用邊數量.實驗結果表明，PtaPCG 和Averroes生成的調用圖中缺少lusearch和xalan基準程序中的2條庫調用邊.分析發現，lusearch基準程序在動態運行時拋出一個NullPointerException 異常，動態調用圖中包含對該異常類構造器的調用，而xalan基準程序在動態運行時調用了java.lang.ref.Finalizer.register方法.調用邊的缺失是由于PtaPCG 和Averroes均未對Java虛擬機的行為進行完整的建模.

此外，“Dynamic＼Spark”行顯示Spark 生成的調用圖中缺失相當數量的調用邊，這是由于這些基準程序大量使用反射機制，而Spark未對反射機制進行完整的處理.PtaPCG 和Averroes 則利用TamiFlex收集的動態信息對反射進行處理.

3.5 調用圖精確性

實驗中通過比較PtaPCG、Averroes和Spark生成調用圖中3種類型調用邊的數量，來評估方法所生成調用圖的精確性.Spark 通過全程序分析生成調用圖，而PtaPCG 和Averroes均不分析庫類中的方法體而生成局部調用圖.因此，PtaPCG 和Averroes生成的調用圖與Spark 生成的調用圖相似度越高，表明其生成的調用圖精確性越高.

對調用圖完整性進行評估，發現PtaPCG、Averroes和Spark生成的靜態調用圖都存在一定程度的不完整性，為防止完整性與精確性的評估結果產生混淆，在進行調用圖精確性評估前，先將這些缺失的調用邊加入到靜態調用圖中.表4～6 中的“PtaPCG＼Spark”行和“Averroes＼Spark”行分別表示與Spark相比PtaPCG 和Averroes生成的3 種類型額外的調用邊數量.

3.5.1 應用調用邊 如表4 所示，對于基準程序luindex、compress、db、jess和raytrace，PtaPCG 能夠精確地產生調用圖中的應用調用邊.對于所有基準程序而言，與Spark相比，PtaPCG 產生中位值22條額外的應用調用邊（最小為0，最大為1 821，中位值為22）.該中位值為Spark產生調用圖中應用調用邊中位值的0.49%.這些額外的調用邊主要存在于基準程序bloat、hsqldb和xalan的調用圖中.通過分析可知，這些基準程序中存在實現庫接口的大規模子系統，這些接口分別是java.util.＊、JDBC和XML.與Averroes相比，PtaPCG 產生的額外應用調用邊中位值比Averroes的中位值23略小.實驗結果表明，對于應用調用邊而言，PtaPCG 比Averroes生成更加精確的調用圖.

表3 PtaPCG、Averroes和Spark生成調用圖的完整性對比Tab.3 Comparison of completeness of call graphs generated by PtaPCG，Averroes and Spark

3.5.2 庫調用邊 如表5所示，對于基準程序antlr、luindex、compress和raytrace，PtaPCG 能夠產生精確的庫調用邊.對于所有基準程序而言，與Spark相比，PtaPCG 產生中位值為2的額外庫調用邊（最小為0，最大為112，中位值為2）.該中位值僅為Spark生成庫調用邊中位值的0.55%.與Averroes相比，PtaPCG 額外庫調用邊中位值比Averroes的中位值3略小.實驗結果表明，對于庫調用邊而言，PtaPCG 比Averroes生成更加精確的調用圖.

3.5.3 庫回調邊 如表6所示為庫回調邊精確性的評估結果.對于所有基準程序而言，與Spark 相比，PtaPCG 產生額外庫回調邊的中位值為23（最小為1，最大為645，中位值為22.5），該中位值占Spark生成庫回調邊中位值的31.69%.與Averroes相比，PtaPCG 產生額外庫回調邊的中位值比Averroes的中位值5大.引起庫回調邊不精確的原因包含以下2個方面.

1）PtaPCG對＜clinit＞的處理方法.PtaPCG 在3種情況下把對＜clinit＞的隱式調用構建為庫回調邊：當某靜態方法被調用時、當某靜態域被訪問時以及當某個對象或某個對象數組初始化時.然而，Spark則把對＜clinit＞的隱式調用構建為應用調用邊.實驗結果中，由PtaPCG產生的調用圖中大部分額外的庫回調邊的目標方法均為靜態初始化塊＜clinit＞.

2）PtaPCG 對庫部分代碼引用的對象進行保守假設，即認為調用庫方法傳入庫中的對象會被庫中其他的方法引用.實際上，其中的一些庫方法并不會將對象泄露給其他庫代碼.正是由于這一假設，擴大了庫指針指向集合的規模，從而引入額外的庫回調邊.此外，由于應用部分與庫部分的交互，這些對象會污染應用部分變量的指針指向集合，進一步影響其他類型調用邊的精確性.

表4 比較PtaPCG、Averroes和Spark生成的調用圖中應用調用邊的精確性對比Tab.4 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to application call graph edges

表5 PtaPCG、Averroes和Spark生成的調用圖中庫調用邊的精確性對比Tab.5 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to library call graph edges

表6 PtaPCG、Averroes和Spark生成的調用圖中庫回調邊的精確性對比Tab.6 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to library call back edges

4 相關工作

4.1 全程序分析調用圖生成方法

Dean等［5］提出了類層次結構分析法（class hierarchy analysis，CHA），方法中假設接收對象的運行時類型可以是其聲明類型的任意子類型.Bacon等［6］提出 了 快 速 類 型 分 析 法（rapid type analysis，RTA），方法將運行時類型限制在程序可達部分已經創建實例的類中.Diwan等［7］提出了Modula-3的調用圖生成算法，為每一個本地變量維護一個不同的運行時類型集合.Sundaresan等［8］提出了變量類型分析法（variable type analysis，VTA），通過創建類型傳播圖來表示由賦值引起的類型傳播，并通過傳播類型計算變量的指針指向集合.Tip等［18］設計了一個基于集合的統一框架，描述不同類型的指針分析方法，并在此框架上提出了一系列指針分析算法（CTA、MTA、FTA 和XTA），這些算法的不同之處在于使用了不同粒度的指針指向集合.

4.2 局部調用圖生成方法

局部調用圖生成方法面臨的主要挑戰在于對未分析部分代碼做出精確且完整的假設.Tip等［18］將所有傳入庫代碼中的對象集結成一個特殊的指針指向集合SE，并利用該指針指向集合確定庫代碼的目標方 法.Grothoff等［19］提 出 名 為Kacheck／J 的 工具，用以推測Java程序中的局限屬性（confinement properties）.局限屬性定義如下：若某個類及其子類的實例均封裝在同一個包（package）內，那么就稱這個類及其子類是被局限的.該方法用于識別庫部分與應用部分之間的逃逸對象，從而對庫部分指針指向集合中的對象進行精確的假設.Andersen［10］提出一種名為CGC的調用圖生成方法，依賴分離編譯假設，創建應用部分的局部調用圖.該方法使用一個指針指向集合摘要，表示庫中所有變量的指針指向信息，在不分析庫部分代碼的前提下，對應用部分可能的行為進行推導.Rountev等［20］提出創建一個占位方法main，通過分析所有實現庫接口或擴展庫抽象類的應用類生成代表未知代碼的占位方法.該占位方法包含各種類型語句，以模擬未知代碼的潛在行為.然而，占位方法改變了應用部分代碼原本的邏輯，致使精確性降低.Ali等［12］提出了Averroes工具，基于分離編譯假設［15］生成占位庫，占位庫中包含了對庫代碼行為的估計，包括Spark在內的全程序分析框架能夠通過直接分析占位庫來生成局部調用圖.

本研究和Zhang 等［21］的工作存在關聯，文獻［21］的研究目標在于創建精確的應用部分調用圖，通過對庫部分代碼進行深入分析，達到對庫回調邊的目標方法進行精確解析的目的，這與本研究的初衷不同.

5 結 語

本文提出了一種指針分析方法，在不分析庫部分語句的前提下，創建Java程序應用部分的局部調用圖.該方法使用混合堆模型，區分應用部分及庫部分的抽象內存位置.為應用部分和庫部分的交互構建形式化模型，推測庫中創建的抽象對象.本研究在Soot程序分析框架上實現了該方法，通過與Spark 及Averroes進行比較，評估該方法的性能及生成調用圖的完整性和精確性.實驗結果表明：本文方法能高效地創建精確且完整的局部調用圖.今后的工作包括為庫中不同代碼部分定義多個不同的指針指向集合，對反射機制、靜態初始化和異常處理機制進行更加完整和精確地建模，以提高構建調用圖的精確性.

（

）：

［1］GROVE D，CHAMBERS C.A framework for call graph construction algorithms［J］.ACM Transactions on Programming Languages and Systems，2001，23（6）：685-746.

［2］LHOTáK O.Comparing call graphs［C］∥Proceedings of the 7th ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering.San Diego：ACM，2007：37-42.

［3］T.J.Watson libraries for analysis（WALA）［EB／OL］.［2014-03-21］.http：∥wala.sourceforge.net.

［4］VALLéE-RAI R，GAGNON E，HENDREN L J，et al.Optimizing Java bytecode using the soot framework：is it feasible？［C］∥Proceedings of the 9th International Conference on Compiler Construction.Berlin：Springer，2000：18-34.

［5］DEAN J，GROVE D，CHAMBERS C.Optimization of object-oriented programs using static class hierarchy analysis［C］∥Proceedings of the 9th European Conference on Object-Oriented Programming.London：Springer，1995：77-101.

［6］BACON D F，SWEENEY P F.Fast static analysis of C＋＋virtual function calls［C］∥Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.San José：ACM，1996：324-341.

［7］DIWAN A，MOSS J，MCKINLEY K S.Simple and effective analysis of statically-typed object-oriented programs［C］∥Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.San José：ACM，1996：292-305.

［8］SUNDARESAN V，HENDREN L，RAZAFIMAHEFA C，et al.Practical virtual method call resolution for Java［C］∥Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming，Systems，Languages and Applications.Minneapolis：ACM，2000：264-280.

［9］YAN D，XU G，ROUNTEV A.Rethinking Soot for summary-based whole-program analysis［C］∥Proceedings of ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis.Beijing：ACM，2012：9-14.

［10］ANDERSEN L O.Program analysis and specialization for the C programming language［D］.Denmark：University of Copenhagen，1994：6-35.

［11］LHOTáK O，HENDREN L.Scaling Java points-to analysis using SPARK ［C］∥Proceedings of the 12th International Conference on Compiler Construction.Warsaw：Springer，2003：153-169.

［12］ALI K，LHOTáK O.Averroes：whole-program analysis without the whole program ［C］∥Proceedings of the 27th European Conference on Object-Oriented Programming.Montpellier：Springer，2013：378-400.

［13］BLACKBURN S M，GARNER R，HOFFMAN C，et al.The DaCapo benchmarks：Java benchmarking development and analysis［C］∥Proceedings of the 21st Annual ACM SIGPLAN International Conference on Object-Oriented Programing，Systems，Languages and Applications.Portland：ACM，2006：169-190.

［14］Standard Performance Evaluation Corporation：SPEC JVM98benchmarks［EB／OL］.［2014-03-21］.http：∥www.spec.org／jvm98.

［15］ALI K，LHOTáK O.Application-only call graph construction［C］∥Proceedings of the 26th European Conference on Object-Oriented Programming. Beijing：Springer，2012：688-712.

［16］BODDEN E，SEWE A，SINSCHEK J，et al.Taming reflection：aiding static analysis in the presence of reflection and custom class loaders［C］∥Proceedings of the 33rd International Conference on Software Engineering.Honolulu：ACM，2011：241-250.

［17］DUFOUR B，HENDREN L，VERBRUGGE C.＊J：a tool for dynamic analysis of Java programs［C］∥Proceedings of Companion of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages，and Applications.Anaheim：ACM，2003：306-307.

［18］TIP F，PALSBERG J.Scalable propagation-based call graph construction algorithms［C］∥Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.Minneapolis：ACM，2000：281-293.

［19］GROTHOFF C，PALSBERG J，VITEK J.Encapsulating objects with confined types［C］∥Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.Tampa Bay：ACM，2001：241-255.

［20］ROUNTEV A，MILANOVA A，RYDER B G.Fragment class analysis for testing of polymorphism in Java software［J］.IEEE Transactions on Software Engineering，2004，30（6）：372-387.

［21］ZHANG W，RYDER B G.Automatic construction of accurate application call graph with library call abstraction for Java［J］.Journal of Software Maintenance and Evolution：Research and Practice，2007，19（4）：231-252.