陳泓旭

(上海交通大學(xué)軟件學(xué)院，上海 200240)

0 引言

分析影響程序關(guān)注點(diǎn)的程序片段在程序分析上具有基礎(chǔ)性作用。

在軟件開(kāi)發(fā)過(guò)程中，往往僅關(guān)心程序的某特定關(guān)注點(diǎn)，為此可通過(guò)靜態(tài)分析找出影響該關(guān)注點(diǎn)的程序片段，在代碼理解、程序除錯(cuò)上意義重大。

近年來(lái)符號(hào)執(zhí)行工具［1-3］在現(xiàn)實(shí)程序排錯(cuò)及測(cè)試覆蓋率上取得了令人矚目的結(jié)果。但現(xiàn)有符號(hào)執(zhí)行工具仍然會(huì)因?yàn)槌绦蛞?guī)模擴(kuò)大導(dǎo)致?tīng)顟B(tài)爆炸。根據(jù)程序的影響分析削減不相關(guān)程序，可以減少符號(hào)執(zhí)行過(guò)程中的狀態(tài)，從而在一定程度上減少狀態(tài)爆炸帶來(lái)的性能瓶頸。本文根據(jù)減小符號(hào)執(zhí)行程序規(guī)模這一需求，首先對(duì)程序關(guān)注點(diǎn)部分進(jìn)行了影響性分析。

LLVM(Low Level Virtual Machine，底 層 虛 擬機(jī))［4，11］是一個(gè)編譯框架，提供了類(lèi)似 RISC(Reduced Instruction Set Computing，精簡(jiǎn)指令集計(jì)算機(jī))指令的中間形式，可進(jìn)行編譯時(shí)期、鏈接時(shí)期、執(zhí)行時(shí)期以及閑置時(shí)期的優(yōu)化。任何語(yǔ)言(C/C++，Java字節(jié)碼等)只需通過(guò)LLVM編譯器前端轉(zhuǎn)化為L(zhǎng)LVM的中間形式(Intermediate Representation，IR)，就可以使用LLVM框架進(jìn)行轉(zhuǎn)化，故在中間代碼上的研究具有普遍意義。

本文的實(shí)現(xiàn)依賴(lài)于LLVM提供的應(yīng)用程序接口，實(shí)現(xiàn)準(zhǔn)確的指向分析、變量修改信息、調(diào)用圖、過(guò)程間可達(dá)性分析及過(guò)程間程序切片算法，定位程序中對(duì)關(guān)注點(diǎn)的有影響的程序片段，削減不相關(guān)的程序代碼。最終經(jīng)過(guò)LLVM的本地代碼生成工具，得到經(jīng)過(guò)削減的可執(zhí)行文件。

1 靜態(tài)分析技術(shù)

1.1 指向分析

指向分析用于建立指針類(lèi)型變量和它可以指向的變量地址之間關(guān)系。精確的指向分析的開(kāi)銷(xiāo)很大，廣泛使用的是上下文不敏感和流不敏感的Andersen算法［5］和 Steensgaard 算法［6］。前者基于子集的指向集求解，更為精確;后者基于類(lèi)型系統(tǒng)上的等價(jià)類(lèi)劃分，時(shí)間復(fù)雜度低。

1.2 調(diào)用圖

調(diào)用圖是一種表征主調(diào)函數(shù)和被調(diào)函數(shù)之間關(guān)系的有向多圖。不同的程序輸入會(huì)帶來(lái)不同的調(diào)用圖。對(duì)于靜態(tài)分析，在給定了程序的起始執(zhí)行函數(shù)之后，需要建立包含所有可能被調(diào)函數(shù)的調(diào)用關(guān)系，不同精度的指向分析結(jié)果會(huì)得到不同的調(diào)用圖。

1.3 可達(dá)性分析

可達(dá)性分析研究程序中的節(jié)點(diǎn)是否可以通過(guò)某種方式執(zhí)行到另一節(jié)點(diǎn)。過(guò)程內(nèi)的可達(dá)性可以規(guī)約到控制流圖上的圖可達(dá)問(wèn)題。過(guò)程間的可達(dá)性建立在控制流圖和函數(shù)調(diào)用圖之上，與過(guò)程內(nèi)分析不同，需要區(qū)分每個(gè)調(diào)用點(diǎn)前后的程序可達(dá)性情況。

1.4 程序切片

程序切片根據(jù)給定的程序關(guān)注點(diǎn)，找出影響該關(guān)注點(diǎn)的程序子集［12］。程序關(guān)注點(diǎn)包含單個(gè)變量及該變量在程序中的位置，在控制流圖上根據(jù)數(shù)據(jù)依賴(lài)及控制依賴(lài)關(guān)系，采用不動(dòng)點(diǎn)迭代求解［14-15］。

2 實(shí)現(xiàn)細(xì)節(jié)

實(shí)現(xiàn)時(shí)以流不敏感、上下文不敏感的Andersen指向分析為基礎(chǔ)，根據(jù)外部配置信息，構(gòu)建準(zhǔn)確的調(diào)用圖并削減未被調(diào)用函數(shù)，在編譯單元上計(jì)算對(duì)關(guān)注點(diǎn)過(guò)程間的可達(dá)性片段，最終以關(guān)注點(diǎn)為切片準(zhǔn)則進(jìn)行切片。流程如圖1所示，其中程序切片對(duì)可達(dá)性分析的依賴(lài)關(guān)系是可選的。

圖1 實(shí)現(xiàn)流程依賴(lài)

2.1 關(guān)注點(diǎn)配置

出于程序除錯(cuò)的要求［7，10］，目前僅將關(guān)注點(diǎn)局限于C語(yǔ)言中的assert宏中的條件變量，在LLVM的IR上需定位特定的_assert_fail(由assert宏擴(kuò)展而來(lái))調(diào)用點(diǎn)，找到所有前驅(qū)基本塊(basic block)的終結(jié)指令的條件變量。一般而言程序中的assert調(diào)用不止一處，需要根據(jù)程序的debug信息來(lái)定位指定的調(diào)用點(diǎn)。這一定位操作可細(xì)化為“由源文件的配置信息在中間形式上添加元數(shù)據(jù)”及“由元數(shù)據(jù)解析得到中間形式中的關(guān)注點(diǎn)信息”。

2.2 調(diào)用圖的構(gòu)建

LLVM使用“定義使用”的方法計(jì)算調(diào)用圖，下例說(shuō)明這樣得到的結(jié)果(如圖2所示)是粗糙的。

圖2 LLVM的基本調(diào)用圖

該程序中main函數(shù)存在函數(shù)指針，需要將func1和func2都作為它的直接被調(diào)函數(shù);同時(shí)populate_array采用指針傳遞調(diào)用了getNextRandomValue。準(zhǔn)確的調(diào)用圖如圖3所示。指定的基本塊”這一問(wèn)題可退化為通過(guò)深度優(yōu)先(或廣度優(yōu)先)搜索算法求解圖可達(dá)問(wèn)題。下節(jié)將說(shuō)明不能將過(guò)程內(nèi)的可達(dá)性分析直接用于削減。

2.4.2 過(guò)程間可達(dá)性

由于所關(guān)注的語(yǔ)句所在函數(shù)可能被調(diào)用多次，在同一函數(shù)內(nèi)對(duì)同一條語(yǔ)句過(guò)程內(nèi)可達(dá)集合是過(guò)程間可達(dá)的子集。以下面的程序?yàn)槔f(shuō)明其差異性。

圖3 準(zhǔn)確的調(diào)用圖

準(zhǔn)確調(diào)用圖的生成算法如下:

Step1 遍歷整個(gè)編譯單元，當(dāng)遇到調(diào)用點(diǎn)，轉(zhuǎn)至step2。

Step2 若該調(diào)用處的值為函數(shù)常量，則將該主調(diào)函數(shù)和被調(diào)函數(shù)對(duì)加入directCaller2CalleeMap中;若該調(diào)用點(diǎn)為間接調(diào)用，通過(guò)指向分析找出該變量指向的所有可能值，將主調(diào)函數(shù)和這些值成對(duì)加到directCaller2CalleeMap中。同時(shí)，將被調(diào)函數(shù)和調(diào)用點(diǎn)信息記錄到directCallee2CSMap中。

Step3 重復(fù)上述2步至遍歷完成，將所有直接調(diào)用映射directCaller2CalleeMap傳遞給間接調(diào)用映射Caller2CalleeMap。

經(jīng)過(guò)該算法得到的調(diào)用圖仍存在外部節(jié)點(diǎn)，它可能是外部庫(kù)函數(shù)或未使用的函數(shù)聲明。庫(kù)函數(shù)不會(huì)調(diào)用該程序編譯單元中的函數(shù)，故對(duì)后續(xù)分析沒(méi)有影響;未使用的函數(shù)聲明可通過(guò)2.3節(jié)中的方法消除。

2.3 未調(diào)用函數(shù)削減

因?yàn)榫幾g單元中的函數(shù)有可能不會(huì)被調(diào)用，給定程序的入口函數(shù)entry后可以簡(jiǎn)化調(diào)用圖。步驟如下:

Step1 遍歷編譯單元中的函數(shù)表，若該函數(shù)不在Caller2CalleeMapentry中，則將該函數(shù)的函數(shù)體置空，并標(biāo)記為待刪除函數(shù)。

Step2 遍歷待刪除函數(shù)集合，逐一從編譯單元中刪除。

該過(guò)程同時(shí)解決了2.2節(jié)中的函數(shù)聲明帶來(lái)的外部節(jié)點(diǎn)問(wèn)題。本操作的必要性將在2.4.2節(jié)提及。

2.4 可達(dá)性分析

2.4.1 過(guò)程內(nèi)分析

LLVM IR顯式給出了每個(gè)函數(shù)的控制流圖，因此“判定函數(shù)中任意基本塊是否通過(guò)某種執(zhí)行達(dá)到

若以函數(shù)foo中的if分支的return語(yǔ)句作為關(guān)注點(diǎn)，過(guò)程內(nèi)可達(dá)性分析認(rèn)為else分支不能通過(guò)任何路徑達(dá)到該點(diǎn)。然而在main函數(shù)中存在一條“在foo2中執(zhí)行了foo中else分支、而在foo執(zhí)行了if分支”的可行路徑，故在過(guò)程間分析中else分支語(yǔ)句需被計(jì)入可達(dá)關(guān)注點(diǎn)的集合中。

另一方面，foo1調(diào)用了foo，調(diào)用點(diǎn)處的語(yǔ)句可以達(dá)到關(guān)注點(diǎn);然而foo1沒(méi)有被入口函數(shù)調(diào)用，實(shí)際上不會(huì)執(zhí)行到關(guān)注點(diǎn)。這需要通過(guò)2.3節(jié)削減未調(diào)用函數(shù)的方法將foo1從編譯單元中刪除。

在函數(shù)調(diào)用前后的可達(dá)性是截然不同的，過(guò)程間的分析必須特殊對(duì)待函數(shù)調(diào)用點(diǎn)。算法實(shí)現(xiàn)如下:

Step1 將每個(gè)基本塊以函數(shù)調(diào)用點(diǎn)為界限劃分為多個(gè)“子基本塊”。標(biāo)記所有子基本塊為不可達(dá)且未訪(fǎng)問(wèn)。

Step2 對(duì)當(dāng)前關(guān)注點(diǎn)計(jì)算過(guò)程內(nèi)可達(dá)性，更新該當(dāng)前子基本塊為可達(dá)。將可達(dá)調(diào)用點(diǎn)的所有“至少有一個(gè)調(diào)用點(diǎn)未被訪(fǎng)問(wèn)”的被調(diào)函數(shù)及該被調(diào)函數(shù)的所有未完全被訪(fǎng)問(wèn)的被調(diào)函數(shù)(Caller2CalleeMap)的全部基本塊都更新為可達(dá)，標(biāo)記所有的被調(diào)函數(shù)的所有調(diào)用點(diǎn)為已訪(fǎng)問(wèn)。

Step3 根據(jù)directCallee2CSMap得到關(guān)注點(diǎn)所在函數(shù)的所有未被訪(fǎng)問(wèn)的被調(diào)用點(diǎn)。

Step4 將所有未被訪(fǎng)問(wèn)的調(diào)用點(diǎn)作為新關(guān)注點(diǎn)，重復(fù)Step2，Step3中的操作直至所有函數(shù)中的調(diào)用點(diǎn)都被訪(fǎng)問(wèn)過(guò)。

這里忽略特殊的函數(shù)調(diào)用對(duì)可達(dá)性的影響:例如exit()函數(shù)調(diào)用處于某個(gè)基本塊中間，或 setjmp/longjmp函數(shù)調(diào)用等。

2.4.3 基于可達(dá)性的削減

不適當(dāng)?shù)南鳒p會(huì)導(dǎo)致程序不可執(zhí)行，因此并非所有的不可達(dá)語(yǔ)句均可削減。實(shí)現(xiàn)時(shí)將這些分支的內(nèi)容轉(zhuǎn)換為使得程序立即終止的特殊函數(shù)調(diào)用:

Step1 對(duì)編譯單元中的每一個(gè)基本塊計(jì)算其到關(guān)注點(diǎn)的可達(dá)性，將不可達(dá)節(jié)點(diǎn)放入不可達(dá)集合中，并將不可達(dá)節(jié)點(diǎn)所在的終結(jié)指令替換成LLVM IR的Unreachable指令。

Step2 遍歷不可達(dá)集合中的基本塊:若未被用，則將該塊內(nèi)容置空，并將該塊從編譯單元中刪除;若其仍被使用，則將該塊內(nèi)容替換成exit(1)的函數(shù)調(diào)用。

2.5 程序切片

程序切片比基于可達(dá)性的削減更為精確，后者的削減結(jié)果僅包含實(shí)際可執(zhí)行至關(guān)注點(diǎn)的語(yǔ)句，而前者進(jìn)一步剔除那些可達(dá)到關(guān)注點(diǎn)，但并不影響關(guān)注點(diǎn)結(jié)果的語(yǔ)句。與可達(dá)性分析不同，這里的分析用于LLVM的指令層次。切片算法采用了Mark Weiser提出的基于控制流圖的過(guò)程內(nèi)分析和過(guò)程間調(diào)用點(diǎn)傳遞的方式［8，13］。細(xì)節(jié)上有如下改變:

(1)由于部分LLVM的IR中的指令的結(jié)果本身為變量(如LoadInst/CastInst)，迭代求解程序相關(guān)集時(shí)并不區(qū)分語(yǔ)句和變量。

(2)經(jīng)典切片算法不涉及程序內(nèi)存相關(guān)指令，為此首先使用LLVM的mem2reg這一轉(zhuǎn)換，消除程序中部分內(nèi)存讀寫(xiě)指令。在每個(gè)讀(或?qū)?內(nèi)存的操作上，指針變量的指向的元素添加入“使用集”或“定義集”;并在函數(shù)的調(diào)用處將該函數(shù)調(diào)用可能修改的變量加入至“定義集”中。

(3)LLVM的IR要求每個(gè)基本塊必須以終結(jié)指令結(jié)束，故必須保留分支跳轉(zhuǎn)語(yǔ)句。

程序切片是基于不動(dòng)點(diǎn)的算法，每一次程序相關(guān)集的改變都需要重新修改整個(gè)編譯單元的相關(guān)集，代價(jià)是巨大的。在基于可達(dá)性削減之后的程序上進(jìn)行切片可以大大減少分析的開(kāi)銷(xiāo)。

3 實(shí)驗(yàn)與分析

本實(shí)驗(yàn)使用 Coreutils 6.10［9］中的9個(gè)含有關(guān)注點(diǎn)配置信息的完整程序作為測(cè)試用例，經(jīng)過(guò)llvm-gcc 4.2轉(zhuǎn)換為L(zhǎng)LVM的IR，影響性分析基于LLVM 2.9。結(jié)果參見(jiàn)表1，選用assert調(diào)用作為關(guān)注點(diǎn)，選取main作為入口函數(shù)。編譯單元大小為經(jīng)過(guò)鏈接之后的LLVM IR大小;削減所需時(shí)間為基于未調(diào)用函數(shù)的削減、可達(dá)性削減和程序切片的時(shí)間總和。

表1 程序削減結(jié)果

由實(shí)驗(yàn)結(jié)果可知，本方法可以高效削減程序中的不相關(guān)部分(最長(zhǎng)時(shí)間不超過(guò)121ms)。由于Coreutils使用了大量指針、全局變量，削減后的程序仍可能較大，大部分剩余程序片段大小為原大小的47% ～63%。對(duì)于程序用例rm，程序關(guān)注點(diǎn)接近入口函數(shù)故削減了大部分程序;而用例factor中由于幾乎所有語(yǔ)句均對(duì)給定關(guān)注點(diǎn)有影響故保留了大量程序片段。

對(duì)于削減結(jié)果的正確性使用如下方法評(píng)估:

Step1 使用llvm-lit測(cè)試框架及LLVM自帶的FileCheck工具，在給定程序關(guān)注點(diǎn)配置信息和特定代碼轉(zhuǎn)換方式的條件下，驗(yàn)證轉(zhuǎn)化后的LLVM中間形式滿(mǎn)足:

(1)應(yīng)該被削減的變量不再存在。

(2)應(yīng)該被保留的變量繼續(xù)存在。

Step2 給定能執(zhí)行到關(guān)注點(diǎn)的特定程序輸入，使用LLVM中間指令解釋器lli分別對(duì)削減前后的IR求解，確保削減后的程序可執(zhí)行，并與原有程序得到同樣的輸出。

實(shí)驗(yàn)結(jié)果表明削減后的程序均通過(guò)了上述2項(xiàng)測(cè)試，可認(rèn)為是正確的。

4 結(jié)束語(yǔ)

基于LLVM框架實(shí)現(xiàn)了對(duì)指定程序關(guān)注點(diǎn)的影響分析，進(jìn)而在保證程序可執(zhí)行的前提之下削減不必要程序片段。實(shí)驗(yàn)結(jié)果表明，可以通過(guò)靜態(tài)分析的方法正確、高效削減實(shí)際程序中的不相關(guān)語(yǔ)句。未來(lái)的工作將進(jìn)一步優(yōu)化削減算法，并提供對(duì)特殊函數(shù)調(diào)用的支持。

［1］ Cadar C，Dunbar D，Englar D R.KLEE:Unassisted and automatic generation of high-coverage tests for complex system programs［C］//Proceedings of the 8th USENIX Con-ference on Operating Systems Design and Implementation.2008:209-224.

［2］ Chipounov V，Kuznetsov V，Candea G.S2E:A platform for in-vivo multi-path analysis of software systems［C］//Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems.2011:265-278.

［3］ Cui H，Hu G，Wu J，et al.Verifying system rules using ruledirected symbolic execution［C］//Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems.2013:329-342.

［4］ LLVM.The LLVM Compiler Infrastructure［EB/OL］.http://llvm.org/，2013-12-12.

［5］ Andersen L O.Program Analysis and Specialization for the C Programming Language［D］.University of Copenhagen，DIKU，1994.

［6］ Steensgaard B.Points-to analysis in almost linear time［C］//Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.1996:32-41.

［7］ Openrefactory.Openrefactory Homepage［EB/OL］.http://openrefactory.org/，2013-12-12.

［8］ Weiser M.Program slicing［C］//Proceedings of the 5th International Conference on Software Engineering.1981:439-449.

［9］ GNU.GNU Coreutils［EB/OL］.http://www.gnu.org/software/coreutils/，2013-12-12.

［10］Munawar Hafiz，Auburn A L.OpenRefactory/C:An infrastructure for developing program transformations for C programs［C］//Proceedings of the 3rd Annual Conference on Systems，Programming，and Applications:Software for Humanity.2012:27-28.

［11］ Chris Lattner.LLVM:An Infrastructure for Multi-Stage Optimization［D］.University of Illinois at Urbana-Champaign.2002.

［12］ Susan Horwitz，Thomas Reps，David Binkley.Interprocedural slicing using dependence Graphs［C］//Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation.1988:35-46.

［13］ Frank Tip.A survey of program slicing techniques［J］.Journal of Programming Languages，1995，3(3):121-189.

［14］ Agrawal H，Horgan J.Dynamic program slicing［C］//Proceedings of PLDI’90.1990:246-256.

［15］ Sridharan M，F(xiàn)ink S J，Bodik R.Thin slicing［C］//Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.2007:112-122.