[發明專利]基于改進系統依賴圖的LLVM IR程序切片方法

在審

• 申請號: 201610098877.8
• 申請日: 2016-02-23
• 公開（公告）號: CN105700893A
• 公開（公告）日: 2016-06-22
• 發明（設計）人: 張迎周;徐晨晨;吳寄語;閆麗;尹秀;陳星昊;王星;趙蓮
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06F9/45;G06F11/36
• 代理公司: 南京知識律師事務所 32207
• 代理人: 汪旭東

技術領域

本發明涉及軟件分析技術領域，特別針對一種程序切片方法。

背景技術

當今的時代是一個計算機技術迅猛發展的時代，人們的生產和生活都離不開眾多的軟件 系統，軟件系統的數量與規模在不停壯大的同時，復雜程度也伴隨著軟件系統的進步而越來 越高。許多傳統的程序分析手段已經不能滿足我們的需求，我們需要更多了技術與工具來幫 助我們完成程序分析的工作。所以，程序分析已經成為了軟件領域中非常重要的組成部分， 我們需要更多的人投身于程序分析的研究工作中。

在眾多的程序分析技術中，程序切片技術是其中一項非常重要組成部分。程序切片是一 種程序分解技術，即一種重要的程序分析理解方法。程序切片這種程序分析方法在實際的生 產和研究方面已經得到非常廣泛的應用。程序切片技術在對程序的分析理解、調試和測試等 領域都非常多的應用，不僅如此，程序切片技術在軟件系統的維護和度量等方面也提供技術 上的支持。

MarkWeiser等人曾發現，程序的某一個輸出只與源程序中部分語句有關，刪除其它的語 句并不影響該輸出的結果。他們把這種只與某個輸出有關的語句構成的程序稱為源程序的一 種靜態切片，并提出了基于控制流圖(CFG，ControlFlowGragh)的程序切片算法。Ottenstein 等人引入了基于程序依賴圖(PDG,ProcedureDependenceGraph)的圖形可達性算法，以此來計 算過程內程序切片。Horwitz等人隨后提出了基于系統依賴圖(SDG，SystemDependence Graph)的兩階段圖形可達性算法(簡記為HRB算法)。信息流分析方法是一種重要的程序 分析方法，它在程序優化、程序靜態分析、程序測試等許多方面都有著重要的應用，應用領 域的不同，分析數據的屬性也不同。1985年，Bergeretti和Carre定義了一系列程序內部信 息流關系，這些信息流關系可以用來對程序進行切片，且切片結果比較精確。二十多年來， 人們對程序切片進行了廣泛而深入的研究，取得了許多研究成果，使得它在軟件調試、測試、 維護、度量、程序并行化、軟件逆向工程與再工程等方面得到廣泛應用，因而也受到了廣大 軟件研究、開發人員的高度重視。

雖然人們已提出了多種程序切片方法，但是，切片的對象一般都是C、C++、Python等 某種特定語言編寫的程序，通用性不強。如今的編程語言不斷趨于簡單化和人性化，在功能 性方面越來越強大，而復雜程度也變得更高。為了適應編程語言的不斷進步，程序切片技術 也應該不斷的提高。

發明內容

針對上述問題，本發明對LLVMIR進行基于改進系統依賴圖的程序切片。LLVMIR是 一種介于c語言和匯編語言的格式，既有高級語言的可讀性，又能比較全面地反映計算機底 層數據的運算和傳輸的情況，精煉而又高效。任何一種編程語言都可以轉化成LLVMIR， LLVMIR也可以轉化為任何一種編程語言，從這里可以看出LLVMIR的通用性非常強。并 且，本發明對HRB的構建系統依賴圖的方法進行改進，以使切片的時間復雜度大大降低。

基于改進系統依賴圖的LLVMIR程序切片方法，包括以下步驟：

步驟1、構建程序依賴圖；

步驟2、對單個程序語句進行過程內切片；

步驟3、利用XX方法構建系統依賴圖；

步驟4、利用兩階段圖形可達性算法對系統依賴圖進行遍歷，完成對多個程序的切片。

步驟1的具體過程為：

S101、給程序添加節點，

S101-1、添加入口節點；

S101-2、給入口節點加輸入形參節點和輸出形參節點；

S101-3、給最后一條語句中的每一個變量v添加最后使用FinalUse(v)節點；

S101-4、為調用語句添加輸入實參節點、輸出實參節點；

S102、增加控制依賴邊，

S102-1、找出程序的入口節點、控制謂詞節點以及不依賴于任何謂詞節點的節點；

S102-2、添加從所述入口節點到所述不依賴于任何謂詞節點的節點的控制依賴邊；

S102-3、找出程序中依賴于謂詞節點的節點；

S102-4、添加從相應的所述謂詞節點到依賴該謂詞節點的節點的控制依賴邊；

S102-5、添加從所述入口節點分別到輸入形參節點和輸出形參節點的控制依賴邊；