基于模塊單子語(yǔ)義的程序切片技術(shù)研究.pdf

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

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

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

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

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