支持局部調(diào)用圖生成的指針分析

萬志遠(yuǎn)，周 波

（浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州310027）

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

現(xiàn)代面向?qū)ο缶幊陶Z言大量使用動(dòng)態(tài)分配（dynamic dispatch），程序中調(diào)用點(diǎn)的目標(biāo)方法由調(diào)用點(diǎn)接收對(duì)象（receiver）的運(yùn)行時(shí)類型（runtime type）決定.由于程序的任意部分可構(gòu)造接收對(duì)象，大部分靜態(tài)程序分析工具和框架均采用基于全程序分析［3-8］（whole-program analysis）的 調(diào) 用 圖 生 成 方法.在文獻(xiàn)［9］的實(shí)驗(yàn)中，基于全程序分析生成的調(diào)用圖中，平均有超過50%的頂點(diǎn)為Java標(biāo)準(zhǔn)庫中的方法，對(duì)于實(shí)驗(yàn)中大部分的被分析程序，這一數(shù)字甚至超過80%.事實(shí)上，許多軟件工程應(yīng)用并不關(guān)注調(diào)用圖中庫方法間的調(diào)用關(guān)系.對(duì)于現(xiàn)代面向?qū)ο蟪绦蛘Z言，全程序分析的可擴(kuò)展性問題嚴(yán)重阻礙了其在實(shí)際中的應(yīng)用，庫和框架規(guī)模的日益增長(zhǎng)加劇了這一問題.這些庫包括程序語言標(biāo)準(zhǔn)庫（如：Java程序語言的J2SE、C＋＋語言的STL）、領(lǐng)域相關(guān)的方法庫（如：圖像處理和線性代數(shù)）以及可擴(kuò)展的框架和中間件.本研究統(tǒng)一使用“庫”一詞來表示程序所依賴的所有庫方法.

分析實(shí)際應(yīng)用程序可以發(fā)現(xiàn)，與程序中庫的代碼量相比，應(yīng)用部分的代碼量規(guī)模較小.對(duì)于許多Web應(yīng)用程序而言，庫代碼在靜態(tài)分析時(shí)甚至不可用，因?yàn)閼?yīng)用部分依賴的庫在實(shí)際部署時(shí)才能確定（如：Servlet容器）.因此，本研究不分析庫部分代碼，以提升調(diào)用圖生成方法的性能.

本研究提出一種指針分析方法，用于生成完整且精確的應(yīng)用部分局部調(diào)用圖.該指針分析方法僅分析應(yīng)用部分代碼以及應(yīng)用部分所引用的庫部分代碼中的方法簽名、類的域和類層次結(jié)構(gòu)（class hierarchy）.該方法對(duì)標(biāo)準(zhǔn)指針分析進(jìn)行擴(kuò)展，構(gòu)建混合堆模型（heap model），以區(qū)分應(yīng)用部分及庫部分的抽象內(nèi)存位置.方法為程序中的每一變量維護(hù)一個(gè)混合指針指向集合（points-to set）.此外，該方法構(gòu)建一系列規(guī)則對(duì)應(yīng)用部分和庫部分的交互行為進(jìn)行建模，并利用這些規(guī)則推導(dǎo)庫部分的指針信息.該方法使用庫的混合指針指向集合解析調(diào)用圖中的庫回調(diào)邊，并限制回流進(jìn)入應(yīng)用部分指針指向集合的抽象對(duì)象.本研究在Soot程序分析框架上實(shí)現(xiàn)該方法，并在14個(gè)Java基準(zhǔn)程序上對(duì)該方法的性能及生成調(diào)用圖的完整性和精確性進(jìn)行評(píng)估.

1 研究背景

1.1 調(diào)用圖生成技術(shù)

對(duì)于面向?qū)ο缶幊陶Z言，程序中調(diào)用點(diǎn)的目標(biāo)方法由動(dòng)態(tài)分配決定.對(duì)于調(diào)用點(diǎn)v.m（…），目標(biāo)方法由調(diào)用的接收對(duì)象v 的運(yùn)行時(shí)類型決定.運(yùn)行時(shí)類型可通過指針分析獲取，通常存儲(chǔ)于指針指向集合中.文獻(xiàn)中［3］、［4］中的調(diào)用圖生成技術(shù)通常采用On-the-fly方法構(gòu)建程序的調(diào)用圖.一方面，On-thefly方法對(duì)于被分析程序中的調(diào)用點(diǎn)v.m（…），使用變量v的指針指向集合確定調(diào)用點(diǎn)的目標(biāo)方法，逐步構(gòu)建調(diào)用圖.另一方面，逐步構(gòu)建的調(diào)用圖為指針分析提供過程間指針信息，進(jìn)一步構(gòu)造指針指向集合.在On-the-fly調(diào)用圖生成方法中，指針指向集合的構(gòu)造和調(diào)用圖的生成同時(shí)進(jìn)行，直至指針指向集合或調(diào)用圖中沒有變化產(chǎn)生.

1.2 局部調(diào)用圖生成技術(shù)

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

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

另一種構(gòu)建局部調(diào)用圖的解決方案既考慮方法本身的可擴(kuò)展性，也兼顧構(gòu)建的調(diào)用圖的精確性和完整性.該方案通過對(duì)庫代碼進(jìn)行預(yù)分析，計(jì)算庫方法的方法摘要（procedure summary），摘要描述庫方法的指針信息.當(dāng)應(yīng)用部分調(diào)用庫中的某方法時(shí)，該方案直接使用被調(diào)用方法的方法摘要，從而避免對(duì)該庫方法的重復(fù)分析.這一方案也存在問題：在生成和使用方法摘要時(shí)，需要面臨抽象表達(dá)及算法設(shè)計(jì)等諸多技術(shù)挑戰(zhàn)，無縫使用方法摘要需額外的基礎(chǔ)結(jié)構(gòu)支持［9］.

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

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

1.3 全局調(diào)用圖和局部調(diào)用圖

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

1）應(yīng)用調(diào)用邊（application call graph edge）的源方法與目標(biāo)方法均為應(yīng)用部分的方法，如圖2（b）中的指示線①所示.

2）庫調(diào)用邊（library call graph edge）的源方法屬于應(yīng)用部分，目標(biāo)方法屬于庫部分，如圖2（b）中的指示線②和③所示.在進(jìn)行實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)時(shí)，當(dāng)應(yīng)用部分的某方法一次或多次調(diào)用庫部分方法時(shí)，僅向局部調(diào)用圖中添加一條庫調(diào)用邊.

3）庫回調(diào)邊（library call back edge）的源方法屬于庫部分，目標(biāo)方法屬于應(yīng)用部分，如圖2（b）中的指示線④所示.

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

2 指針分析方法

2.1 方法特征

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

堆模型（heap model）是指針分析中重要的設(shè)計(jì)要素.最常見堆模型將任一個(gè)靜態(tài)內(nèi)存分配點(diǎn)（allocation site）視為單一的抽象內(nèi)存位置.該方法不分析庫代碼的方法體，庫中的內(nèi)存分配點(diǎn)不可知.因此，該方法使用混合堆模型以區(qū)分應(yīng)用部分和庫部分的內(nèi)存位置：使用內(nèi)存分配點(diǎn)表示應(yīng)用代碼所生成的抽象對(duì)象，使用類名表示庫代碼所生成的抽象對(duì)象.

通常，利用指針分析計(jì)算程序中的指針指向關(guān)系，即將每一個(gè)指針變量映射到運(yùn)行時(shí)可能指向的對(duì)象的超集.典型的指針指向關(guān)系通過變量的指針指向集合表示.對(duì)任一變量v，其對(duì)應(yīng)的指針指向集合中的每一個(gè)抽象對(duì)象o 均滿足（v，o）這一指針指向關(guān)系.

混合堆模型將單一指針指向集合擴(kuò)展為混合指針指向集合.混合指針指向集合包含2部分：應(yīng)用指針指向集合和庫指針指向集合.

定義1 （應(yīng)用指針指向集合）對(duì)于被分析程序中的變量v，定義應(yīng)用指針指向集合為PtA（v），該集合包含應(yīng)用部分代碼創(chuàng)建的抽象對(duì)象，由內(nèi)存分配點(diǎn)表示.

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

2.2 集合及概念

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

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

集合O 表示程序代碼創(chuàng)建的抽象對(duì)象集合.其中應(yīng)用代碼創(chuàng)建的對(duì)象集合為OA，庫代碼創(chuàng)建的對(duì)象集合為OL，OA∪OL＝O.

表1 基本語句及其對(duì)應(yīng)的指針賦值圖實(shí)體Tab.1 Elementary statements and corresponding pointer assignment graph entities

2.3 程序表示

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

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

2.4 庫模型

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

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

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

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

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

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

針對(duì)不同類型的基本語句定義如下規(guī)則，以推測(cè)庫部分創(chuàng)建的抽象對(duì)象集合及變量的庫指針指向集合.

1）實(shí)例載入

規(guī)則1 對(duì)于語句v2＝v1.f，非靜態(tài)域f在cls∈ClsL中聲明：

StaticType（f）∈OL；

StaticType（f）∈PtL（v2）.

其中，StaticType（v）表示變量v的靜態(tài)類型.

2）靜態(tài)載入

規(guī)則2 對(duì)于語句v＝cls.f，cls∈ClsL：

StaticType（f）∈OL；

StaticType（f）∈PtL（v）.

3）靜態(tài)方法調(diào)用

考慮應(yīng)用部分代碼中的靜態(tài)方法調(diào)用，假設(shè)目標(biāo)方法為靜態(tài)方法m，該方法在某庫類中聲明.

規(guī)則3 對(duì) 于 語 句vR＝cls.m（v1，…，vj），X∈ClsL：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

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

4）實(shí)例方法調(diào)用

考慮某一個(gè)應(yīng)用部分的方法存在一個(gè)實(shí)例方法調(diào)用，該方法調(diào)用的目標(biāo)方法為實(shí)例方法m，該方法在某庫類中聲明.

規(guī)則4 對(duì) 于 語 句vR＝v0.m（v1，…，vj），v0∈V：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

考慮庫方法中一個(gè)實(shí)例方法調(diào)用，假設(shè)目標(biāo)方法為實(shí)例方法m，該方法在某庫類中聲明并被某應(yīng)用類的方法重寫，它也是某條庫回調(diào)邊的目標(biāo)方法.

規(guī)則5 對(duì)于語句Library.m（v1，…，vk）：

StaticType（this）∈OL；

StaticType（this）∈PtL（this）；

StaticType（vi）∈OL；

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

2.5 虛函數(shù)調(diào)用的處理

定義3 CallGraph為程序應(yīng)用部分的局部調(diào)用圖，CallGraph是由調(diào)用邊組成的有限集合.調(diào)用邊定義為三元組（m1，m2，c），其中m1，m2∈｛mL｝∪Method，且c∈｛cL｝∪C，調(diào)用邊連接調(diào)用點(diǎn)和調(diào)用點(diǎn)對(duì)應(yīng)的目標(biāo)方法.

對(duì)于應(yīng)用部分的方法M 中的虛擬函數(shù)調(diào)用點(diǎn)v.m（…），依照以下2條規(guī)則，使用PtA（v）和PtL（v）解析調(diào)用點(diǎn)c∈C 的目標(biāo)方法，并構(gòu)建調(diào)用邊.

規(guī)則6 對(duì)于抽象對(duì)象o∈PtA（v），存在StaticLookup（StaticType（o），m）＝m′：

（M，m′，c）∈CallGraph.

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

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

對(duì)于庫部分代碼中的虛擬函數(shù)調(diào)用點(diǎn)，定義如下規(guī)則，利用PtA（Library）解析調(diào)用點(diǎn)cL的目標(biāo)方法，構(gòu)建庫回調(diào)邊.

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

3 實(shí) 驗(yàn)

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

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

2）調(diào)用圖完整性方面，除缺失2條庫調(diào)用邊，本文提出方法生成的調(diào)用圖覆蓋基準(zhǔn)程序動(dòng)態(tài)調(diào)用圖中所有調(diào)用邊，該結(jié)果與Averroes相同.

3）調(diào)用圖精確性方面，與全程序分析調(diào)用圖生成方法Spark相比，本文方法額外產(chǎn)生中位值22條應(yīng)用調(diào)用邊、中位值2 條庫調(diào)用邊以及中位值23條庫回調(diào)邊.相較于Spark 產(chǎn)生的調(diào)用圖中調(diào)用邊的總量，本文方法生成的調(diào)用圖中額外調(diào)用邊數(shù)量可忽略不計(jì).

3.1 實(shí)驗(yàn)準(zhǔn)備

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

3.2 方法實(shí)現(xiàn)

在Soot［4］框架2.5.0 版本上實(shí)現(xiàn)所提出的指針分析方法（PtaPCG），通過Spark［11］指針分析框架驅(qū)動(dòng)方法的執(zhí)行.實(shí)驗(yàn)中對(duì)Soot進(jìn)行配置，將分析的范圍限定在程序的應(yīng)用部分，實(shí)現(xiàn)基于PAG 節(jié)點(diǎn)工作隊(duì)列，該隊(duì)列中PAG 節(jié)點(diǎn)PtA／L存在更新.對(duì)于每隊(duì)列中的每一個(gè)個(gè)PAG 節(jié)點(diǎn)，將PtA／L中的抽象對(duì)象傳播至相鄰節(jié)點(diǎn)的指針指向集合中.抽象對(duì)象的傳播同時(shí)會(huì)引起：1）應(yīng)用部分新的可達(dá)方法被發(fā)現(xiàn)；2）新發(fā)現(xiàn)的可達(dá)方法引起實(shí)際參數(shù)和形式參數(shù)、返回值以及本地變量間的PAG 邊的創(chuàng)建；3）應(yīng)用部分和庫部分的指針指向集合間抽象對(duì)象的流動(dòng).

當(dāng)不存在未處理的可達(dá)方法并且PAG 節(jié)點(diǎn)的工作隊(duì)列為空時(shí)，算法將終止.實(shí)現(xiàn)擴(kuò)展Spark標(biāo)準(zhǔn)指針分析，包括創(chuàng)建庫指針指向集合、傳遞庫指針指向集合中的抽象對(duì)象以及使用庫指針指向集合解析調(diào)用點(diǎn).此外，還對(duì)以下方面進(jìn)行了優(yōu)化.

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

2）反射和動(dòng)態(tài)類加載機(jī)制.反射和動(dòng)態(tài)類加載機(jī)制在Java程序中廣泛使用.然而，由反射機(jī)制引起的類和方法的訪問無法通過靜態(tài)分析確定.實(shí)現(xiàn)中利用TamiFlex［16］收集的動(dòng)態(tài)運(yùn)行信息，確定由反射產(chǎn)生的程序行為.

3）標(biāo)準(zhǔn)庫.通過分析發(fā)現(xiàn)，許多傳入標(biāo)準(zhǔn)庫代碼的抽象對(duì)象并未被其他庫方法引用，如傳入類java.lang.Object構(gòu)造器的對(duì)象.代碼實(shí)現(xiàn)中對(duì)這些標(biāo)準(zhǔn)庫方法進(jìn)行特殊處理，當(dāng)這些方法被調(diào)用時(shí)，不將抽象對(duì)象傳入庫部分的指針指向集合中.

3.3 性 能

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

實(shí)驗(yàn)結(jié)果表明，PtaPCG 顯著提升了Spark 的性能.性能提升的原因在于生成調(diào)用圖時(shí)PtaPCG未對(duì)庫部分的方法體進(jìn)行分析，Averroes的運(yùn)行時(shí)間分為2個(gè)部分：1）預(yù)分析時(shí)間：Averroes生成占位庫所使用的時(shí)間，圖3中顯示為AverroesPlaceholder；2）分析時(shí)間，Spark使用Averroes占位庫進(jìn)行全程序分析生成調(diào)用圖的運(yùn)行時(shí)間，圖3 中顯示為AverroesAnalysis.分析發(fā)現(xiàn)，Averroes的運(yùn)行時(shí)間大部分為預(yù)分析時(shí)間.

表2 本實(shí)驗(yàn)使用的基準(zhǔn)程序信息Tab.2 Information of benchmarks used in proposed experiment

圖3 PtaPCG、Averroes和Spark分析基準(zhǔn)程序的運(yùn)行時(shí)間對(duì)比Fig.3 Comparison of time taken by PtaPCG，Averroes and Spark for each benchmark program

3.4 調(diào)用圖完整性

實(shí)驗(yàn)中通過對(duì)存在于由＊J［17］工具記錄的動(dòng)態(tài)調(diào)用圖、缺失于由靜態(tài)工具生成的靜態(tài)調(diào)用圖的調(diào)用邊數(shù)量進(jìn)行統(tǒng)計(jì)，評(píng)估PtaPCG、Averroes 和Spark產(chǎn)生的調(diào)用圖的完整性.動(dòng)態(tài)調(diào)用圖是＊J工具通過觀察和記錄基準(zhǔn)程序的動(dòng)態(tài)運(yùn)行得到的.實(shí)驗(yàn)結(jié)果如表3 所示，“Dynamic”行顯示了基準(zhǔn)程序的動(dòng)態(tài)調(diào)用圖中應(yīng)用部分調(diào)用邊的數(shù)量，“Dynamic＼PtaPCG”行、“Dynamic＼Averroes”行和“Dynamic＼Spark”行分別顯示了PtaPCG、Averroes和Spark生成的靜態(tài)調(diào)用圖中缺失的動(dòng)態(tài)調(diào)用邊數(shù)量.實(shí)驗(yàn)結(jié)果表明，PtaPCG 和Averroes生成的調(diào)用圖中缺少lusearch和xalan基準(zhǔn)程序中的2條庫調(diào)用邊.分析發(fā)現(xiàn)，lusearch基準(zhǔn)程序在動(dòng)態(tài)運(yùn)行時(shí)拋出一個(gè)NullPointerException 異常，動(dòng)態(tài)調(diào)用圖中包含對(duì)該異常類構(gòu)造器的調(diào)用，而xalan基準(zhǔn)程序在動(dòng)態(tài)運(yùn)行時(shí)調(diào)用了java.lang.ref.Finalizer.register方法.調(diào)用邊的缺失是由于PtaPCG 和Averroes均未對(duì)Java虛擬機(jī)的行為進(jìn)行完整的建模.

此外，“Dynamic＼Spark”行顯示Spark 生成的調(diào)用圖中缺失相當(dāng)數(shù)量的調(diào)用邊，這是由于這些基準(zhǔn)程序大量使用反射機(jī)制，而Spark未對(duì)反射機(jī)制進(jìn)行完整的處理.PtaPCG 和Averroes 則利用TamiFlex收集的動(dòng)態(tài)信息對(duì)反射進(jìn)行處理.

3.5 調(diào)用圖精確性

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

對(duì)調(diào)用圖完整性進(jìn)行評(píng)估，發(fā)現(xiàn)PtaPCG、Averroes和Spark生成的靜態(tài)調(diào)用圖都存在一定程度的不完整性，為防止完整性與精確性的評(píng)估結(jié)果產(chǎn)生混淆，在進(jìn)行調(diào)用圖精確性評(píng)估前，先將這些缺失的調(diào)用邊加入到靜態(tài)調(diào)用圖中.表4～6 中的“PtaPCG＼Spark”行和“Averroes＼Spark”行分別表示與Spark相比PtaPCG 和Averroes生成的3 種類型額外的調(diào)用邊數(shù)量.

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

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

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

3.5.3 庫回調(diào)邊 如表6所示為庫回調(diào)邊精確性的評(píng)估結(jié)果.對(duì)于所有基準(zhǔn)程序而言，與Spark 相比，PtaPCG 產(chǎn)生額外庫回調(diào)邊的中位值為23（最小為1，最大為645，中位值為22.5），該中位值占Spark生成庫回調(diào)邊中位值的31.69%.與Averroes相比，PtaPCG 產(chǎn)生額外庫回調(diào)邊的中位值比Averroes的中位值5大.引起庫回調(diào)邊不精確的原因包含以下2個(gè)方面.

1）PtaPCG對(duì)＜clinit＞的處理方法.PtaPCG 在3種情況下把對(duì)＜clinit＞的隱式調(diào)用構(gòu)建為庫回調(diào)邊：當(dāng)某靜態(tài)方法被調(diào)用時(shí)、當(dāng)某靜態(tài)域被訪問時(shí)以及當(dāng)某個(gè)對(duì)象或某個(gè)對(duì)象數(shù)組初始化時(shí).然而，Spark則把對(duì)＜clinit＞的隱式調(diào)用構(gòu)建為應(yīng)用調(diào)用邊.實(shí)驗(yàn)結(jié)果中，由PtaPCG產(chǎn)生的調(diào)用圖中大部分額外的庫回調(diào)邊的目標(biāo)方法均為靜態(tài)初始化塊＜clinit＞.

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

表4 比較PtaPCG、Averroes和Spark生成的調(diào)用圖中應(yīng)用調(diào)用邊的精確性對(duì)比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生成的調(diào)用圖中庫調(diào)用邊的精確性對(duì)比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生成的調(diào)用圖中庫回調(diào)邊的精確性對(duì)比Tab.6 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to library call back edges

4 相關(guān)工作

4.1 全程序分析調(diào)用圖生成方法

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

4.2 局部調(diào)用圖生成方法

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

本研究和Zhang 等［21］的工作存在關(guān)聯(lián)，文獻(xiàn)［21］的研究目標(biāo)在于創(chuàng)建精確的應(yīng)用部分調(diào)用圖，通過對(duì)庫部分代碼進(jìn)行深入分析，達(dá)到對(duì)庫回調(diào)邊的目標(biāo)方法進(jìn)行精確解析的目的，這與本研究的初衷不同.

5 結(jié) 語

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

（

）：

［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.