基于模塊單子語義的程序切片技術研究.pdf

1、程序切片是一種重要的程序分析理解方法，用于從源程序中抽取對程序中特定點上的特定變量有影響的語句和謂詞，組成新的程序(稱作切片)，然后通過分析切片來分析源程序的行為。二十多年來，人們對它進行了廣泛而深入的研究，取得了許多研究成果，使得它在軟件調試、測試、維護、度量、程序變換、軟件逆向工程與再工程等方面得到廣泛應用，受到了廣大軟件研究和開發(fā)人員的高度重視。 論文主要工作包括：(1)將程序切片這類計算抽象成獨立于具體語言的切片單子轉換

2、器，據此提出一種新型的形式化程序切片方法－模塊單子切片，相應切片算法將具有較強的可重用性和程序語言適應性；(2)通過這種新型的形式化切片方法研究過程間程序和含指針程序的切片；(3)實現(xiàn)模塊單子切片算法，開發(fā)相應的模塊單子切片器。 論文工作的主要成果表現(xiàn)在以下幾個方面： ·設計了一種切片單子轉換器SliceT。我們將程序切片這類計算抽象成獨立于具體語言的實體：切片單子轉換器，以此來統(tǒng)一描述切片計算。SliceT不僅提供了一

3、種抽象化表示程序切片的能力，而且還允許人們訪問其低層語義的細節(jié)部分。切片單子轉換器可與其它(表示某種程序特性)的單子轉換器或單子組合，并通過提升函數lift與這些不同程序特性進行交互，從而可計算具有不同特性的程序切片。 ·提出了模塊單子切片概念，并給出了一種高精度的動態(tài)切片方法——模塊單子動態(tài)切片。它是一種隨著程序的執(zhí)行同時計算動態(tài)切片的正向切片方法，無需記錄程序執(zhí)行歷史，從而將追蹤的信息量減少到最低。我們還證明了該單子切片算法

4、所得結果是精確的，即算法可捕獲對應PDG中可達信息，且算法結果中不含多余的依賴信息。該算法的平均每個變量單子切片的時間復雜度是線性的，空間復雜度與程序執(zhí)行的長度無關。 ·此基礎上提出了模塊單子靜態(tài)切片算法。它可直接在抽象語法結構上計算切片，無需顯示地構造諸如PDG的中間結構。此外，切片單子轉換器的模塊化抽象機制使得單子切片算法具有很強的可擴展性和重用性。 ·為求過程間程序切片，提出了基于回填待定標號的兩階段單子切片算法。

5、該算法可求按值、結果、值－結果調用的過程間程序切片，且可避免上下文調用問題。與基于SDG兩階段掃描算法相比，因其無需構造PDG和SDG，故可避免由于程序復雜、SDG過于龐大而難以理解、實現(xiàn)時內存空間緊張等問題。 ·通過將指向分析融入到已有的模塊單子切片，提出了一種改進的單子切片方法以處理含指針的程序。不同于將指向分析與切片計算分開的傳統(tǒng)切片方法，改進的單子切片方法將程序正向切片思想與數據流迭代分析相結合，可同時進行切片計算和指向