張晶晶 石劍君 高玉金 計(jì)衛(wèi)星

(北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京 100081)

基于K-最短路徑的大規(guī)模函數(shù)調(diào)用關(guān)系分析

張晶晶 石劍君 高玉金 計(jì)衛(wèi)星

(北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京 100081)

函數(shù)調(diào)用關(guān)系反映了軟件系統(tǒng)中函數(shù)之間的依賴關(guān)系，在軟件分析、軟件測(cè)試與軟件維護(hù)等眾多軟件工程領(lǐng)域都有著廣泛的應(yīng)用。但在大型復(fù)雜軟件中搜索兩個(gè)函數(shù)之間的調(diào)用關(guān)系時(shí) ，由于函數(shù)數(shù)量眾多、函數(shù)之間調(diào)用關(guān)系復(fù)雜，使得搜索所需時(shí)間較長。為了獲得任意兩個(gè)函數(shù)之間的調(diào)用路徑，提出使用K-最短路徑算法，并對(duì)K-最短路徑算法進(jìn)行并行化優(yōu)化，減少搜索時(shí)間，為用戶分析函數(shù)調(diào)用關(guān)系提供方便。通過對(duì)Linux內(nèi)核3.19(包含40多萬個(gè)函數(shù)結(jié)點(diǎn)和110多萬調(diào)用關(guān)系)進(jìn)行分析，實(shí)驗(yàn)結(jié)果表明通過并行化優(yōu)化，并行加速比一般可達(dá)5～6倍。

函數(shù)調(diào)用關(guān)系 K-最短路徑 路徑搜索 Linux內(nèi)核

0 引 言

隨著軟件技術(shù)的快速發(fā)展，軟件應(yīng)用遍及各行各業(yè)，人們對(duì)于軟件各項(xiàng)功能的要求也越來越高，隨之而來的是軟件代碼規(guī)模日益增大,代碼量達(dá)到了百萬行乃至數(shù)千萬行。例如，最流行的開源操作系統(tǒng)Linux 內(nèi)核的代碼量已經(jīng)從1萬多行代碼增長到2 000多萬行。對(duì)于大型軟件系統(tǒng)而言，由于代碼規(guī)模龐大、自身邏輯復(fù)雜、說明文檔匱乏等特點(diǎn)，使得代碼分析工作越來越困難。

函數(shù)調(diào)用關(guān)系一般以一種有向圖的形式表示，是程序理解、程序分析中重要的研究內(nèi)容。在程序理解中，一個(gè)函數(shù)一般代表一個(gè)具體功能或者問題求解的實(shí)現(xiàn)，函數(shù)調(diào)用關(guān)系反映了軟件系統(tǒng)中函數(shù)間的依賴關(guān)系。大型程序一般都是通過對(duì)函數(shù)的組織和調(diào)用來實(shí)現(xiàn)整個(gè)程序的功能要求，掌握函數(shù)之間的調(diào)用關(guān)系對(duì)理解程序是非常有幫助的。

除此之外，在軟件工程的其他領(lǐng)域函數(shù)調(diào)用關(guān)系也有著廣泛的應(yīng)用，例如集成測(cè)試、回歸測(cè)試[3]、逆向工程、編譯優(yōu)化、軟件測(cè)試與維護(hù)等。在編譯優(yōu)化技術(shù)中，一方面通過分析程序的調(diào)用關(guān)系，使得沒有調(diào)用鏈關(guān)聯(lián)的函數(shù)的局部變量共享全局存儲(chǔ)單元，降低程序運(yùn)行時(shí)對(duì)內(nèi)存的需求，并提高相應(yīng)存儲(chǔ)單元的利用率[1]；另一方面也可以根據(jù)建立的函數(shù)調(diào)用關(guān)系，分析函數(shù)調(diào)用關(guān)系中每個(gè)函數(shù)的寄存器使用集合，估算出每個(gè)函數(shù)調(diào)用點(diǎn)進(jìn)行上下文保存所需要的最小訪存集合，從而減少函數(shù)調(diào)用點(diǎn)所保存的上下文，消除冗余訪存操作，同時(shí)也能提升性能[2]。在路徑集成測(cè)試[4]中，對(duì)于大型程序進(jìn)行完全路徑測(cè)試幾乎是不可能完成的，所以如果將路徑測(cè)試級(jí)別上升到函數(shù)組件的級(jí)別，根據(jù)函數(shù)調(diào)用關(guān)系再結(jié)合判斷循環(huán)分支結(jié)構(gòu)生成組件的控制流圖，然后再結(jié)合路徑測(cè)試方法，最后構(gòu)造出組件繼承測(cè)試模型，這樣可以大大減少測(cè)試的復(fù)雜度。

考慮到函數(shù)調(diào)用關(guān)系在各個(gè)方面的廣泛應(yīng)用，如何能夠準(zhǔn)確地獲取反應(yīng)實(shí)際程序執(zhí)行時(shí)兩個(gè)函數(shù)之間真正的調(diào)用關(guān)系，一直是大家關(guān)注的熱點(diǎn)。對(duì)于大規(guī)模項(xiàng)目而言，查詢兩個(gè)函數(shù)之間的全部調(diào)用路徑可以通過連接查詢，但是時(shí)間復(fù)雜度卻很高。因此，出于對(duì)性能的考慮，查詢兩個(gè)函數(shù)之間的所有調(diào)用路徑幾乎是不可能的。本文提出基于K-最短路徑算法查找兩個(gè)函數(shù)之間的調(diào)用路徑的方法，首先解析源碼存儲(chǔ)所有函數(shù)之間的調(diào)用關(guān)系，然后通過Yen算法來獲得函數(shù)之間前K條調(diào)用路徑，最后再得到函數(shù)之間調(diào)用關(guān)系。K-最短路徑問題是典型的NP[23]問題[10]，復(fù)雜度高，通過對(duì)Yen算法并行化優(yōu)化，降低了時(shí)間復(fù)雜度，提高了搜索性能。

1 相關(guān)工作

目前，國內(nèi)外關(guān)于靜態(tài)分析函數(shù)調(diào)用關(guān)系的工具很多。文獻(xiàn)[5]中提到三種函數(shù)調(diào)用關(guān)系靜態(tài)分析方法，分別是使用正則表達(dá)式提取、使用開源軟件ctags[24]和cscope[25]提取、構(gòu)建抽象語法樹獲取函數(shù)調(diào)用關(guān)系。使用正則表達(dá)式提取調(diào)用關(guān)系是最簡單的辦法，通過掃描每一個(gè)源碼文件，匹配源碼中所有函數(shù)定義、存儲(chǔ)函數(shù)名、參數(shù)列表、所在文件等信息。然后再對(duì)源碼進(jìn)行第二次掃描，進(jìn)行匹配函數(shù)中調(diào)用的函數(shù)，再將函數(shù)調(diào)用關(guān)系存儲(chǔ)起來。Ctags是一個(gè)開源的工具，可以從源程序代碼樹產(chǎn)生索引文件，通過解析索引文件產(chǎn)生函數(shù)之間的依賴關(guān)系。Cscope是一個(gè)C語言的瀏覽工具，可以找到函數(shù)或者變量定義位置、被調(diào)用函數(shù)位置等信息。通過Yacc和Lex實(shí)現(xiàn)C構(gòu)建抽象語法樹來提取函數(shù)調(diào)用關(guān)系。

文獻(xiàn)[6] 提出一個(gè)基于RTL的函數(shù)調(diào)用圖生成工具CG-RTL，其核心模塊數(shù)據(jù)預(yù)處理是從編譯中間結(jié)果中提取函數(shù)定義以及靜態(tài)函數(shù)調(diào)用關(guān)系等信息。在CG-RTL的基礎(chǔ)上[7]提出了基于內(nèi)核跟蹤的動(dòng)態(tài)函數(shù)調(diào)用圖生成工具DCG-RTL，使用S2E作為獲取動(dòng)態(tài)函數(shù)調(diào)用數(shù)據(jù)的工具，記錄運(yùn)行時(shí)的函數(shù)調(diào)用和返回信息，分析跟蹤信息得到動(dòng)態(tài)和靜態(tài)函數(shù)調(diào)用關(guān)系。

基于數(shù)據(jù)庫的在線函數(shù)調(diào)用圖工具DBCG-RTL[8]采用動(dòng)態(tài)靜態(tài)結(jié)合的方式從編譯過程中提取函數(shù)定義、函數(shù)間調(diào)用信息，以及模塊與函數(shù)間的調(diào)用關(guān)系，然后存入數(shù)據(jù)庫。

K-最短路徑問題是最短路徑問題的另外一種形式，可以最大程度地滿足用戶對(duì)不同路徑的需求。K-最短路徑問題在其他領(lǐng)域中也有廣泛的應(yīng)用[19]，如路徑規(guī)劃、物流規(guī)劃、GPS導(dǎo)航、生物醫(yī)學(xué)、社交網(wǎng)絡(luò)、基于位置的服務(wù)(LBS)等。文獻(xiàn)[22]中提出通過K-最短路徑求不含環(huán)路的所有負(fù)荷供電路徑來計(jì)算負(fù)荷停電概率和停電風(fēng)險(xiǎn)值。

但在實(shí)際應(yīng)用中所需處理的數(shù)據(jù)規(guī)模很大，使得算法非常復(fù)雜，因此，求解算法的選擇是解決問題的關(guān)鍵。文獻(xiàn)[10]中提出K-最短路徑問題分為一般K-最短路徑問題和限定無環(huán)K-最短路徑問題，并闡述了兩類問題的求解算法。

2 基于K-最短路徑函數(shù)調(diào)用關(guān)系分析與可視化

2.1 K-最短路徑算法

隨著軟件代碼規(guī)模的日益增大，函數(shù)調(diào)用關(guān)系也越來越復(fù)雜，某兩個(gè)函數(shù)之間的調(diào)用關(guān)系也不止一條。在大規(guī)模軟件代碼中比如Linux 內(nèi)核，其代碼量現(xiàn)在已經(jīng)增長到2 000多萬行。Linux內(nèi)核3.19的源碼中有約40 000多個(gè)源文件，源碼解析結(jié)果中有約40多萬個(gè)函數(shù)結(jié)點(diǎn)，110多萬條函數(shù)調(diào)用關(guān)系。毫無疑問，Linux內(nèi)核是一個(gè)復(fù)雜的系統(tǒng)，獲取兩個(gè)函數(shù)之間的調(diào)用關(guān)系路徑也就更加困難。

在分析函數(shù)調(diào)用關(guān)系時(shí)，理論上有必要對(duì)所有的可達(dá)路徑進(jìn)行分析，通過連接查詢可以得到函數(shù)之間的調(diào)用關(guān)系。但是搜索兩個(gè)結(jié)點(diǎn)的所有函數(shù)調(diào)用關(guān)系問題是一個(gè)NP問題[23]，如果對(duì)所有的函數(shù)之間的可達(dá)路徑都進(jìn)行分析，不僅搜索花費(fèi)的時(shí)間很長，而且在很多應(yīng)用中并無必要。因此，出于對(duì)性能的考慮，可以選擇只獲取兩個(gè)函數(shù)之間的K條漸次短函數(shù)調(diào)用路徑。

K-最短路徑算法是最短路徑問題的推廣，該算法能得到兩個(gè)結(jié)點(diǎn)之間的K條漸次短路徑[9]。在許多領(lǐng)域用戶除了希望得到最短路徑以外，還希望得到K條漸次短路徑。自1971年以來，有大量的文獻(xiàn)對(duì)K條次短路徑進(jìn)行了研究和探索，本文使用Yen路徑算法[9]對(duì)Linux內(nèi)核的函數(shù)調(diào)用關(guān)系進(jìn)行了分析，并且通過設(shè)置不同的K值來測(cè)試路徑搜索時(shí)間，確定最優(yōu)的K值。

基于函數(shù)調(diào)用的K條漸次短路徑搜索方法的實(shí)現(xiàn)主要包括兩部分：第一部分是通過初始化建立一個(gè)可以表達(dá)函數(shù)之間調(diào)用關(guān)系的有向圖，第二部分再用K-最短路徑算法獲取兩個(gè)函數(shù)之間的前K條漸次短調(diào)用關(guān)系路徑。

構(gòu)建有向圖之后調(diào)用Yen算法，獲得K條漸次短路徑。Yen算法采用遞推法中偏離路徑算法思想，適用于非負(fù)權(quán)邊的有向圖結(jié)構(gòu)[10]。假定通過初始化建立有向圖G，s和t是圖G的兩個(gè)結(jié)點(diǎn)，用P表示從s到t的路徑，Pj(j≤K)表示第j條次短路徑。其算法的核心思想是利用已求得的前K-1條漸次短路徑P1，P2，…，Pk-1來求第K條最短路徑，最短路徑可以用標(biāo)準(zhǔn)求解最短路徑算法得到，比如Dijkstr算法。

Yen算法的偽代碼如下：

Input：G(V，E)：weighteddirectedgraph，withsetof verticesVandsetofdirectededgesE； s：thesourcenode； t：thedestinationnode；K：thenumberofshortestpathstofind；1 A[0]←Dijkstr(G，s，t)；2 B←[]；3 fork=1toK：4 fori=0tosize(A[k？1])-2：5 vNode←A[k-1]．node(i)；6 rootPath←A[k-1]．nodes(0，i)；7 foreachpathp∈A：8 ifrootPath==p．nodes(0，i)：9 G．remove(p．edge(i，i+1))；10 foreachnode∈rootPathexceptvNode：11 G．remove(rootPathNode)；12 spurPath←Dijkstra(G，vNode，t)；13 totalPath←rootPath+spurPath；14 B．a(chǎn)ppend(totalPath)；15 A[k]←B[0]；16 returnA；

算法的主要過程是將路徑Pk-1中除了終止結(jié)點(diǎn)t之外的其他結(jié)點(diǎn)作為偏離結(jié)點(diǎn)v，計(jì)算每個(gè)偏離結(jié)點(diǎn)v到終止結(jié)點(diǎn)t的最短路徑；然后再與Pk-1中起始結(jié)點(diǎn)s到偏離結(jié)點(diǎn)v的路徑拼接，構(gòu)造成候選路徑；最后在所有候選路徑中選擇一條最短路徑即為Pk。其中，B是一個(gè)Treeset 集合，每次添加路徑都會(huì)根據(jù)路徑的權(quán)重值排序，使得路徑根據(jù)權(quán)重值按升序排列。

在Linux內(nèi)核3.19中，搜索函數(shù)metronomefb_probe與mac_address_string之間的調(diào)用路徑，通過統(tǒng)計(jì)得到不同K值時(shí)所需時(shí)間如圖1所示。

圖1 不同K值下搜索兩個(gè)函數(shù)間的路徑關(guān)系所需時(shí)間

實(shí)驗(yàn)中機(jī)器配置如下：64位windows7操作系統(tǒng)， 4.00 GHz的Intel(R) Core(TM) i7-4790K處理器，8 GB內(nèi)存。由圖1可以看出K值為10時(shí)，所需搜索時(shí)間將近達(dá)到70秒，搜索性能比較差，并行化是一個(gè)降低時(shí)間復(fù)雜度的好方法，因此，本文對(duì)Yen算法進(jìn)行了并行化優(yōu)化。

獲得兩個(gè)結(jié)點(diǎn)間的第K條最短路徑主要是將第K-1條路徑上除了終止結(jié)點(diǎn)之外的每個(gè)結(jié)點(diǎn)作為偏離結(jié)點(diǎn)，再計(jì)算偏離結(jié)點(diǎn)到終止結(jié)點(diǎn)之間的最短路徑。即將Pk-1中除了終止結(jié)點(diǎn)t之外的任何結(jié)點(diǎn)作為偏離結(jié)點(diǎn)v，計(jì)算每個(gè)偏離結(jié)點(diǎn)v到終止結(jié)點(diǎn)t的最短路徑。根據(jù)分析，在求解第K條最短路徑的過程中，每次求解偏離結(jié)點(diǎn)到終止結(jié)點(diǎn)的過程是兩個(gè)相對(duì)獨(dú)立的過程。因此本文使用多線程并行計(jì)算一條路徑中的每個(gè)偏離結(jié)點(diǎn)到終止結(jié)點(diǎn)間的最短路徑，這樣可以充分利用多核CPU的并行優(yōu)勢(shì)，提高搜索性能。并行優(yōu)化后的Yen算法的偽代碼：

Input：G(V，E)：weighteddirectedgraph，withsetof verticesVandsetofdirectededgesE； s：thesourcenode； t：thedestinationnode； K：thenumberofshortestpathstofind；1 A[0]←Dijkstr(G，s，t)；2 B←[]；3 fork=1toK：4 fori=0tosize(A[k-1])-2：5 pool．execute(YenCandidatesPath(A，i，k，t，G，B))；6 ifalltaskshavecompleted：7 A[k]←B[0]；8 returnA；YenCandidatesPath(A，i，k，t，G，B)：1 graph=G．clone()；2 vNode←A[k-1]．node(i)；3 rootPath←A[k-1]．nodes(0，i)；4 foreachpathp∈A：5 ifrootPath==p．nodes(0，i)：6 graph．remove(p．edge(i，i+1))；7 foreachnode∈rootPath：8 ifnode！=vNode：9 graph．remove(rootPathNode)；10 spurPath←Dijkstra(graph，vNode，t)；11 totalPath←rootPath+spurPath；12 synchronized(obj)：13 B．a(chǎn)ppend(totalPath)；

算法主要思想基本是將第K-1條路徑上每個(gè)偏離結(jié)點(diǎn)提交一個(gè)任務(wù)(偽代碼中第4～5行)，計(jì)算其到終止結(jié)點(diǎn)的最短路徑。等到所有任務(wù)執(zhí)行完畢，再從當(dāng)前所有候選路徑中選擇一條最短的路徑，即為第K條最短路徑。

計(jì)算每個(gè)偏離結(jié)點(diǎn)到終止結(jié)點(diǎn)的過程中主要的數(shù)據(jù)共享有：A、B、t、G。A：此表用于存儲(chǔ)前K-1條漸次短路徑。B：用于存儲(chǔ)候選路徑的列表。t：終止結(jié)點(diǎn)。G：可以表示函數(shù)之間調(diào)用關(guān)系的有向圖，由于每次計(jì)算都需要沒有刪除過任何邊的圖G，所以在并行化中每次計(jì)算之前要將圖G做深度復(fù)制。

2.2 函數(shù)調(diào)用關(guān)系分析及可視化

對(duì)于大型復(fù)雜軟件，通過傳統(tǒng)的文本閱讀來理解復(fù)雜的函數(shù)調(diào)用關(guān)系比較困難，而可視化工具在代碼分析的基礎(chǔ)之上，形成了對(duì)代碼的部分抽象表示，可以加速程序員對(duì)代碼的理解。我們已經(jīng)實(shí)現(xiàn)一個(gè)內(nèi)核的可視化工具——KernelGraph，KerneGraph參照在線地圖服務(wù)，是利用可視化技術(shù)實(shí)現(xiàn)的一個(gè)大規(guī)模代碼理解工具。KernelGraph既可以從全局顯示模塊之間的關(guān)系，以及已有模塊中含有bug的百分比，也可以進(jìn)行函數(shù)、變量搜索，函數(shù)調(diào)用路徑搜索等。函數(shù)調(diào)用路徑搜索是KernelGraph的一個(gè)重要功能。

Echarts[11]中力導(dǎo)圖可以清晰的顯示各個(gè)結(jié)點(diǎn)之間的關(guān)系，KernelGraph利用力導(dǎo)圖這一特點(diǎn)顯示函數(shù)和函數(shù)之間的調(diào)用關(guān)系,如圖2所示。

圖2 函數(shù)之間的路徑搜索結(jié)果及其可視化表示

圖2顯示了函數(shù)metronomefb_probe與mac_address_string之間的函數(shù)調(diào)用路徑的搜索結(jié)果，圖中清晰地表達(dá)了函數(shù)之間的調(diào)用關(guān)系。

3 實(shí)驗(yàn)結(jié)果分析

在獲取函數(shù)調(diào)用關(guān)系的過程中，首先我們使用 Doxygen[12]來解析Linux內(nèi)核3.19[13]的源碼。Doxygen可以在內(nèi)核代碼的預(yù)處理過程中，從每個(gè)源文件中提取代碼結(jié)構(gòu)并輸出一個(gè)XML文件。這些XML是源碼的結(jié)構(gòu)化數(shù)據(jù)，包含函數(shù)之間的調(diào)用關(guān)系。然后通過提取XML中關(guān)于源碼的函數(shù)，以及函數(shù)之間的調(diào)用關(guān)系，得到可以表達(dá)函數(shù)之間調(diào)用關(guān)系的link文件。

解析Linux內(nèi)核3.19得到的 link文件中有40多萬個(gè)結(jié)點(diǎn)，110多萬條邊，結(jié)點(diǎn)表示函數(shù)，邊表示兩個(gè)函數(shù)之間的調(diào)用關(guān)系。獲取兩個(gè)函數(shù)之間的前K條漸次短路徑，需要設(shè)定一個(gè)合理的K值。本文針對(duì)函數(shù)結(jié)點(diǎn)metronomefb_probe與mac_address_string之間的調(diào)用關(guān)系，統(tǒng)計(jì)在設(shè)定不同的K值下搜索所需的時(shí)間，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同K值路徑搜索所需時(shí)間

通過實(shí)驗(yàn)數(shù)據(jù)表明，在串行算法和并行算法中搜索時(shí)間與K值都是成線性比例關(guān)系。K值過大，需要搜索時(shí)間過長，影響用戶體驗(yàn)，K值過小，又無法得到用戶所需的調(diào)用路徑。因此設(shè)定一個(gè)合理的K值顯得尤為重要。

為了獲得一個(gè)合理的K值，首先解析了Linux內(nèi)核源碼中的Kernel文件夾，得到一個(gè)可以表示Kernel文件夾中函數(shù)之間調(diào)用關(guān)系的link文件，文件中包含5 850個(gè)結(jié)點(diǎn)，10 940個(gè)邊。再通過分析5 850個(gè)結(jié)點(diǎn)中每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)之間的調(diào)用關(guān)系，最后統(tǒng)計(jì)出在Kernel文件夾中所有調(diào)用路徑條數(shù)的可能值，如圖4所示。

圖4 Kernel文件夾中兩個(gè)函數(shù)之間調(diào)用關(guān)系的路徑條數(shù)的數(shù)量

由圖4可以得到，在Kernel文件夾中，函數(shù)之間的調(diào)用路徑條數(shù)分別為6和12時(shí)，數(shù)量值急速下降。因此，在設(shè)置K值，一般推薦值為6或者12，或者選擇相近值作為查找路徑的上限。

通過對(duì)Yen算法并行優(yōu)化之后，搜索所需時(shí)間顯著降低。通過對(duì)Linux內(nèi)核3.19進(jìn)行實(shí)驗(yàn)統(tǒng)計(jì)，分別設(shè)置K值為1～10，搜索函數(shù)結(jié)點(diǎn)metronomefb_probe與mac_address_string之間的路徑，得出實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

圖5 獲取前K條漸次短路徑并行算法加速比

由于K值為1時(shí)，直接調(diào)用Dijkstr算法獲得最短路徑，所以不論算法優(yōu)化之前還是優(yōu)化之后，搜索所需時(shí)間一樣。

4 結(jié) 語

隨著軟件技術(shù)的發(fā)展，軟件代碼規(guī)模日益增大,函數(shù)調(diào)用關(guān)系也越來越復(fù)雜。為保證用戶可以獲得大型復(fù)雜系統(tǒng)中兩個(gè)函數(shù)之間的調(diào)用關(guān)系，本文使用并行化優(yōu)化后的K-最短路徑算法，對(duì)函數(shù)調(diào)用關(guān)系進(jìn)行分析，并且將函數(shù)調(diào)用關(guān)系用Echarts中的力導(dǎo)圖做可視化展示，使得用戶可以得到兩個(gè)函數(shù)之間前K條漸次短路徑的簡潔直觀圖。當(dāng)然，目前的工作還有一些需要改進(jìn)的部分，比如源碼解析中，Doxygen不能完全解析出所有函數(shù)調(diào)用關(guān)系。主要是由于大量的預(yù)處理指令沒有被Doxygen正確識(shí)別和處理，例如宏定義和條件編譯。經(jīng)過分析Linux內(nèi)核3.19的trace動(dòng)態(tài)運(yùn)行結(jié)果得到大約有9 000多個(gè)(已識(shí)別的函數(shù)調(diào)用關(guān)系有110多萬)函數(shù)調(diào)用關(guān)系丟失。在將來工作中，我們將使用特殊的預(yù)處理程序和工業(yè)級(jí)的編譯器配合完成源代碼的解析，獲取在不同預(yù)處理?xiàng)l件下函數(shù)之間的關(guān)系。

[1] 蔣湘濤，胡志剛，賀建飚. 基于調(diào)用鏈分析的低功耗編譯優(yōu)化[J]. 吉林大學(xué)學(xué)報(bào)(工)，2009，39(1)：145-149.

[2] 時(shí)磊，王紅梅. 基于調(diào)用鏈分析的訪存優(yōu)化技術(shù)[J]. 微電子學(xué)與計(jì)算機(jī)，2012，29(7)：32-34.

[3] 鄭錦勤，牟永敏. 基于函數(shù)調(diào)用路徑的回歸測(cè)試用例選擇排序方法研究[J].計(jì)算機(jī)應(yīng)用研究，2016，33(7)：2063-2067.

[4] 馮國堯. 基于函數(shù)調(diào)用的路徑集成測(cè)試模型研究[J]. 電子世界,2015(20):19-20.

[5] 江夢(mèng)濤，荊琦. C語言靜態(tài)代碼分析中的調(diào)用關(guān)系提取方法[J]. 計(jì)算機(jī)科學(xué)，2014，41(S1)：442-444.

[6] 孫衛(wèi)真，杜香燕，向勇，等. 基于RTL的函數(shù)調(diào)用圖生成工具CG·RTL[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2014，35(3)：555-559.

[7] 向勇，湯衛(wèi)東，杜香燕，等. 基于內(nèi)核跟蹤的動(dòng)態(tài)函數(shù)調(diào)用圖生成方法[J].計(jì)算機(jī)應(yīng)用研究， 2015， 32(4)：1095-1099.

[8] 賈狄，向勇，孫衛(wèi)真，等. 基于數(shù)據(jù)庫的在線函數(shù)調(diào)用圖工具[J].小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(3):422-427.

[9] Hershberger J, Maxel M, Suri S. Finding the k Shortest Simple Paths: A New Algorithm and its Implementaton[J]. ACM, 2007， 3(4)：45.

[10] 徐濤，丁曉璐，李建伏. K最短路徑算法綜述[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2013，34(11)：3900-3906.

[11] Echarts[DB/OL].2016. http://echarts.baidu.com.cn/.

[12] Doxygen[DB/OL].2016. http://www.doxygen.org/.

[13] Linux kernel archives[DB/OL].2016. https://www.kernel.org/.

[14] The interactive map linux kernel[DB/OL].April 2016. http://www.makelinux.com/kernel_map/intro.

[15] 張素智，張琳，曲旭凱．基于最短路徑的加權(quán)屬性圖聚類算法研究[J]．計(jì)算機(jī)應(yīng)用與軟件，2016，33(11)：212-214,281.

[16] 丁德武. Linux內(nèi)核函數(shù)調(diào)用關(guān)系的復(fù)雜網(wǎng)絡(luò)分析[J]. 池州學(xué)院學(xué)報(bào)，2012(6)：1-3.

[17] 邱釗. K最短路徑算法及其應(yīng)用研究[D].電子科技大學(xué)， 2014.

[18] 于汶雨. K最短路徑問題的研究與應(yīng)用[D].南京郵電大學(xué)，2016.

[19] 張鐘. 大規(guī)模圖上的最短路徑問題研究[D].中國科學(xué)技術(shù)大學(xué)，2014.

[20] 趙禮峰，于汶雨. 求解k最短路徑問題的混合遺傳算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2016，26(10)：32-35

[21] 苗磊，陳莉君. 基于靜態(tài)分析的函數(shù)調(diào)用關(guān)系研究[J].計(jì)算機(jī)與數(shù)字工程，2014，42(9)：1653-1656.

[22] 王增平，姚玉海，張首魁，等. 基于k最短路徑算法的負(fù)荷停電風(fēng)險(xiǎn)在線評(píng)估[J]. 電力自動(dòng)化設(shè)備, 2016，36(1)：1-5.

[23] George H Polychronopoulos．Stochastic Shorten Path Problems with Recourse[J]. Networks, 1996, 27(2):133-143.

[24] Ctags[DB/OL],2016. http://ctags.sourceforge.net/.

[25] Cscope[DB/OL].2016.http://cscope.sourceforge.net/.

ANALYSYSOFLARGE-SCALEFUNCTIONCALLRELATIONBASEDONK-SHORTESTPATH

Zhang Jingjing Shi Jianjun Gao Yujin Ji Weixing

(SchoolofComputerScienceandTechnology,BeijingInstituteofTechnology,Beijing100081,China)

The function call relationship reflects the dependency between the functions in software system, and has been widely used in much software engineering fields, such as software analysis, software testing and software maintenance. However, in large complex software search between the two functions of the call relationship, due to the large number of functions, calls between the complex relationships, making the search takes longer. In order to obtain the calling path between any two functions, we proposed to use K-shortest path algorithm and optimize the K-shortest path algorithm to reduce the search time, which was convenient for users to analyze the function call relationship. Through the analysis of Linux kernel 3.19 (including more than 400,000 function nodes and 110 million call relationships), the experimental results showed that through the parallel optimization, parallel speed was 5～6 times than the average.

Function call relationship K-shortest Path search Linux kernel

2017-03-05。張晶晶，碩士生，主研領(lǐng)域：代碼分析可視化。石劍君,博士生。高玉金,講師。計(jì)衛(wèi)星,副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.12.005