基于K-最短路徑的大規模函數調用關系分析

張晶晶 石劍君 高玉金 計衛星

(北京理工大學計算機學院 北京 100081)

基于K-最短路徑的大規模函數調用關系分析

張晶晶 石劍君 高玉金 計衛星

(北京理工大學計算機學院 北京 100081)

函數調用關系反映了軟件系統中函數之間的依賴關系，在軟件分析、軟件測試與軟件維護等眾多軟件工程領域都有著廣泛的應用。但在大型復雜軟件中搜索兩個函數之間的調用關系時 ，由于函數數量眾多、函數之間調用關系復雜，使得搜索所需時間較長。為了獲得任意兩個函數之間的調用路徑，提出使用K-最短路徑算法，并對K-最短路徑算法進行并行化優化，減少搜索時間，為用戶分析函數調用關系提供方便。通過對Linux內核3.19(包含40多萬個函數結點和110多萬調用關系)進行分析，實驗結果表明通過并行化優化，并行加速比一般可達5～6倍。

函數調用關系 K-最短路徑 路徑搜索 Linux內核

0 引 言

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

函數調用關系一般以一種有向圖的形式表示，是程序理解、程序分析中重要的研究內容。在程序理解中，一個函數一般代表一個具體功能或者問題求解的實現，函數調用關系反映了軟件系統中函數間的依賴關系。大型程序一般都是通過對函數的組織和調用來實現整個程序的功能要求，掌握函數之間的調用關系對理解程序是非常有幫助的。

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

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

1 相關工作

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

文獻[6] 提出一個基于RTL的函數調用圖生成工具CG-RTL，其核心模塊數據預處理是從編譯中間結果中提取函數定義以及靜態函數調用關系等信息。在CG-RTL的基礎上[7]提出了基于內核跟蹤的動態函數調用圖生成工具DCG-RTL，使用S2E作為獲取動態函數調用數據的工具，記錄運行時的函數調用和返回信息，分析跟蹤信息得到動態和靜態函數調用關系。

基于數據庫的在線函數調用圖工具DBCG-RTL[8]采用動態靜態結合的方式從編譯過程中提取函數定義、函數間調用信息，以及模塊與函數間的調用關系，然后存入數據庫。

K-最短路徑問題是最短路徑問題的另外一種形式，可以最大程度地滿足用戶對不同路徑的需求。K-最短路徑問題在其他領域中也有廣泛的應用[19]，如路徑規劃、物流規劃、GPS導航、生物醫學、社交網絡、基于位置的服務(LBS)等。文獻[22]中提出通過K-最短路徑求不含環路的所有負荷供電路徑來計算負荷停電概率和停電風險值。

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

2 基于K-最短路徑函數調用關系分析與可視化

2.1 K-最短路徑算法

隨著軟件代碼規模的日益增大，函數調用關系也越來越復雜，某兩個函數之間的調用關系也不止一條。在大規模軟件代碼中比如Linux 內核，其代碼量現在已經增長到2 000多萬行。Linux內核3.19的源碼中有約40 000多個源文件，源碼解析結果中有約40多萬個函數結點，110多萬條函數調用關系。毫無疑問，Linux內核是一個復雜的系統，獲取兩個函數之間的調用關系路徑也就更加困難。

在分析函數調用關系時，理論上有必要對所有的可達路徑進行分析，通過連接查詢可以得到函數之間的調用關系。但是搜索兩個結點的所有函數調用關系問題是一個NP問題[23]，如果對所有的函數之間的可達路徑都進行分析，不僅搜索花費的時間很長，而且在很多應用中并無必要。因此，出于對性能的考慮，可以選擇只獲取兩個函數之間的K條漸次短函數調用路徑。

K-最短路徑算法是最短路徑問題的推廣，該算法能得到兩個結點之間的K條漸次短路徑[9]。在許多領域用戶除了希望得到最短路徑以外，還希望得到K條漸次短路徑。自1971年以來，有大量的文獻對K條次短路徑進行了研究和探索，本文使用Yen路徑算法[9]對Linux內核的函數調用關系進行了分析，并且通過設置不同的K值來測試路徑搜索時間，確定最優的K值。

基于函數調用的K條漸次短路徑搜索方法的實現主要包括兩部分：第一部分是通過初始化建立一個可以表達函數之間調用關系的有向圖，第二部分再用K-最短路徑算法獲取兩個函數之間的前K條漸次短調用關系路徑。

構建有向圖之后調用Yen算法，獲得K條漸次短路徑。Yen算法采用遞推法中偏離路徑算法思想，適用于非負權邊的有向圖結構[10]。假定通過初始化建立有向圖G，s和t是圖G的兩個結點，用P表示從s到t的路徑，Pj(j≤K)表示第j條次短路徑。其算法的核心思想是利用已求得的前K-1條漸次短路徑P1，P2，…，Pk-1來求第K條最短路徑，最短路徑可以用標準求解最短路徑算法得到，比如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．append(totalPath)；15 A[k]←B[0]；16 returnA；

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

在Linux內核3.19中，搜索函數metronomefb_probe與mac_address_string之間的調用路徑，通過統計得到不同K值時所需時間如圖1所示。

圖1 不同K值下搜索兩個函數間的路徑關系所需時間

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

獲得兩個結點間的第K條最短路徑主要是將第K-1條路徑上除了終止結點之外的每個結點作為偏離結點，再計算偏離結點到終止結點之間的最短路徑。即將Pk-1中除了終止結點t之外的任何結點作為偏離結點v，計算每個偏離結點v到終止結點t的最短路徑。根據分析，在求解第K條最短路徑的過程中，每次求解偏離結點到終止結點的過程是兩個相對獨立的過程。因此本文使用多線程并行計算一條路徑中的每個偏離結點到終止結點間的最短路徑，這樣可以充分利用多核CPU的并行優勢，提高搜索性能。并行優化后的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．append(totalPath)；

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

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

2.2 函數調用關系分析及可視化

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

Echarts[11]中力導圖可以清晰的顯示各個結點之間的關系，KernelGraph利用力導圖這一特點顯示函數和函數之間的調用關系,如圖2所示。

圖2 函數之間的路徑搜索結果及其可視化表示

圖2顯示了函數metronomefb_probe與mac_address_string之間的函數調用路徑的搜索結果，圖中清晰地表達了函數之間的調用關系。

3 實驗結果分析

在獲取函數調用關系的過程中，首先我們使用 Doxygen[12]來解析Linux內核3.19[13]的源碼。Doxygen可以在內核代碼的預處理過程中，從每個源文件中提取代碼結構并輸出一個XML文件。這些XML是源碼的結構化數據，包含函數之間的調用關系。然后通過提取XML中關于源碼的函數，以及函數之間的調用關系，得到可以表達函數之間調用關系的link文件。

解析Linux內核3.19得到的 link文件中有40多萬個結點，110多萬條邊，結點表示函數，邊表示兩個函數之間的調用關系。獲取兩個函數之間的前K條漸次短路徑，需要設定一個合理的K值。本文針對函數結點metronomefb_probe與mac_address_string之間的調用關系，統計在設定不同的K值下搜索所需的時間，實驗結果如圖3所示。

圖3 不同K值路徑搜索所需時間

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

為了獲得一個合理的K值，首先解析了Linux內核源碼中的Kernel文件夾，得到一個可以表示Kernel文件夾中函數之間調用關系的link文件，文件中包含5 850個結點，10 940個邊。再通過分析5 850個結點中每個結點與其他結點之間的調用關系，最后統計出在Kernel文件夾中所有調用路徑條數的可能值，如圖4所示。

圖4 Kernel文件夾中兩個函數之間調用關系的路徑條數的數量

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

通過對Yen算法并行優化之后，搜索所需時間顯著降低。通過對Linux內核3.19進行實驗統計，分別設置K值為1～10，搜索函數結點metronomefb_probe與mac_address_string之間的路徑，得出實驗數據如圖5所示。

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

由于K值為1時，直接調用Dijkstr算法獲得最短路徑，所以不論算法優化之前還是優化之后，搜索所需時間一樣。

4 結 語

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

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

[2] 時磊，王紅梅. 基于調用鏈分析的訪存優化技術[J]. 微電子學與計算機，2012，29(7)：32-34.

[3] 鄭錦勤，牟永敏. 基于函數調用路徑的回歸測試用例選擇排序方法研究[J].計算機應用研究，2016，33(7)：2063-2067.

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

[5] 江夢濤，荊琦. C語言靜態代碼分析中的調用關系提取方法[J]. 計算機科學，2014，41(S1)：442-444.

[6] 孫衛真，杜香燕，向勇，等. 基于RTL的函數調用圖生成工具CG·RTL[J]. 小型微型計算機系統，2014，35(3)：555-559.

[7] 向勇，湯衛東，杜香燕，等. 基于內核跟蹤的動態函數調用圖生成方法[J].計算機應用研究， 2015， 32(4)：1095-1099.

[8] 賈狄，向勇，孫衛真，等. 基于數據庫的在線函數調用圖工具[J].小型微型計算機系統, 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]. 計算機工程與設計，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] 張素智，張琳，曲旭凱．基于最短路徑的加權屬性圖聚類算法研究[J]．計算機應用與軟件，2016，33(11)：212-214,281.

[16] 丁德武. Linux內核函數調用關系的復雜網絡分析[J]. 池州學院學報，2012(6)：1-3.

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

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

[19] 張鐘. 大規模圖上的最短路徑問題研究[D].中國科學技術大學，2014.

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

[21] 苗磊，陳莉君. 基于靜態分析的函數調用關系研究[J].計算機與數字工程，2014，42(9)：1653-1656.

[22] 王增平，姚玉海，張首魁，等. 基于k最短路徑算法的負荷停電風險在線評估[J]. 電力自動化設備, 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。張晶晶，碩士生，主研領域：代碼分析可視化。石劍君,博士生。高玉金,講師。計衛星,副教授。

TP3

A

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