開題報(bào)告基于程序切片軟件安全測試

1、開題報(bào)告基于程序切片軟件安全測試 南京郵電大學(xué)畢業(yè)設(shè)計(jì)(論文)開題報(bào)告 題 目 基于程序切片的軟件安全測試 學(xué)生姓名 專業(yè) 信息安全 一、 對課題任務(wù)的學(xué)習(xí)與理解 1. 課題產(chǎn)生背景 隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，紛繁眾多的計(jì)算機(jī)應(yīng)用對人們工作和生活的影響越來越大。但是，軟件規(guī)模的日益龐大以及繁瑣的分工使得軟件產(chǎn)品的質(zhì)量往往難以得到保證，從而帶來了日益嚴(yán)重的軟件安全問題和安全隱患。因此，發(fā)掘軟件中的潛在漏洞和脆弱點(diǎn)，診斷已發(fā)生的攻擊行為并及時(shí)采取措施，都能在很大程度上降低軟件受到惡意攻擊的風(fēng)險(xiǎn)，減少攻擊所造成的破壞和損失。 軟件測試是保證軟件質(zhì)量的一個重要環(huán)節(jié)，在現(xiàn)代軟件工程中，軟件測試在整個軟件

2、生命周期中所處的地位越來越高。隨著軟件規(guī)模和復(fù)雜性的不斷提高，采用傳統(tǒng)的軟件測試技術(shù)發(fā)現(xiàn)和定位軟件中的錯誤也越來越難。 程序切片技術(shù)是一種分析和理解程序的技術(shù)，具有可以簡化問題，縮小目標(biāo)范圍的特點(diǎn)。程序切片技術(shù)已被實(shí)踐證明是一種能有效發(fā)掘軟件漏洞、診斷軟件攻擊的技術(shù)，受到了研究者們的重視。因此，探討一種利用程序切片技術(shù)來對軟件進(jìn)行高效安全分析的手段，有著很現(xiàn)實(shí)的意義。 2. 課題實(shí)現(xiàn)目標(biāo) 本課題要求通過實(shí)際具體的 C 程序分析工具，獲取相應(yīng)的程序依賴圖并對其進(jìn)行安全測試研究。具體的成果形式包括： （1）給出基于 C 程序源碼切片的安全測試方法； （2）提交畢業(yè)設(shè)計(jì)報(bào)告及其相關(guān)電子文檔。 二、

3、文獻(xiàn)調(diào)研綜述 1. 程序切片技術(shù)的概述 M. Weiser 博士首先在 1979 年定義了程序切片的概念：程序中的某個輸出只與這個程序的部分相關(guān)語句以及控制謂詞有關(guān)系，因此如果刪除其他的語句或者控制謂詞將對這個輸出沒有任何影響。也就是說，對于一個特定的輸出，源程序和對于刪除不相關(guān)的語句和控制謂詞后所得的程序是作用相同的。其形式化定義如下： 把滿足如下兩個條件的切片稱為 M. Weiser 切片：第一，一個程序切片需要對應(yīng)一個切片準(zhǔn)則，用表示，其中 n 指程序中的某個興趣點(diǎn)，一般指一條語句，V 表示在這條 語句使用的變量的集合。第二，程序 P 的切片 s 可以通過在 P 中刪除零條或者多條語句后

4、得到，且保證程序 P 和所得的切片 S 關(guān)于切片準(zhǔn)則的作用是相同的。 當(dāng)時(shí)，M. Weiser 博士把只與某個輸出相關(guān)聯(lián)的語句和控制謂詞構(gòu)成的程序稱之為源程序的靜態(tài)切片。由此可見，一個程序的切片大多數(shù)是源程序的一個子集，這個概念準(zhǔn)確的說其實(shí)就是程序切片的一個核心思想。 后來隨著研究的發(fā)展，研究者們對 M. Weiser 博士程序切片的概念進(jìn)行了擴(kuò)展，由于程序切片不一定都是可執(zhí)行的，因此又包含了不可執(zhí)行的切片思想，這也是一種靜態(tài)切片，這樣就豐富和發(fā)展了程序切片的內(nèi)涵。隨后，Korel 和 Laski 又提出了動態(tài)切片的概念，它只考慮程序的某個特定執(zhí)行情況，程序中的信息如數(shù)組、指針和循環(huán)依賴關(guān)系都

5、可以在程序執(zhí)行時(shí)動態(tài)確定。因此，動態(tài)切片與靜態(tài)切片相比結(jié)果更加的準(zhǔn)確。 2. 程序切片的發(fā)展歷程 圖 1 程序切片技術(shù)的發(fā)展歷程 第一個階段是基于數(shù)據(jù)流方程的切片階段，這其實(shí)就是 M. Weiser 博士提出切片概念的階段，主要使用了基于控制流圖的數(shù)據(jù)流方程來計(jì)算程序切片。 第二個階段是基于依賴圖的程序切片階段，這一階段產(chǎn)生了對程序切片提出了很多新的概念和算法。首先，Ottenstein 等人在提出了基于程序依賴圖的圖可達(dá)性算法，并可以計(jì)算過程內(nèi)后向程序切片，接著又提出了前向切片的概念和算法，以及基于依賴圖的兩步遍歷圖的可達(dá)性算法。最后 Korel 和 Laski 提出了動態(tài)切片的概念和算法。

6、 第三個階段是面向?qū)ο蟮某绦蚯衅A段，這一階段是伴隨著面向?qū)ο蟮母呒壋绦蛘Z言的發(fā)展而產(chǎn)生，在 1996 年 M.J.Horrald 等人首次使用類依賴圖來擴(kuò)展系統(tǒng)依賴圖，從而表示面向?qū)ο蟮?C+程序，并通過改進(jìn)的兩步遍歷圖可達(dá)性算法來計(jì)算程序的切片。隨后Christon Steindl 在 1999 年通過對各種數(shù)據(jù)流以及控制流的計(jì)算，提出了面向?qū)ο蟪绦蚯衅?jì)算的解決方法，起到了很重要的作用。 最后一個階段是程序切片變體階段，這一階段出現(xiàn)了各種程序切片的變體形式，例如砍片、削片、層次切片等等，這些都極大地促進(jìn)了程序切片技術(shù)的迅速發(fā)展。 3. 程序切片的分類 自程序切片提出以來，伴隨著各自領(lǐng)域的

7、發(fā)展出現(xiàn)了許多略有不同的定義，相關(guān)的切片準(zhǔn)則以及計(jì)算切片的算法。按照切片準(zhǔn)則的不同，程序切片可分為靜態(tài)切片和動態(tài)切片、前向切片和后向切片（或過程內(nèi)切片和過程間切片）、面向?qū)ο笄衅约皸l件切片、分解切 片等其他切片。 4. 程序依賴圖和系統(tǒng)依賴圖 程序依賴圖（PDG）：PDG 是程序的一種圖形表示，它把控制依賴和數(shù)據(jù)依賴包含在單個的結(jié)構(gòu)中。如果給定程序中的語句 X 和 Y，則 X 和 Y 可以通過控制流或者數(shù)據(jù)流彼此關(guān)聯(lián)。如果從 Y 至少可以引出兩條路徑，其中一條總會導(dǎo)致 X 的執(zhí)行，而另一條可能導(dǎo)致X 不執(zhí)行，則成為語句 X 控制依賴于語句 Y；如果有一條從 Y 到 X 的路徑，且存在一個在Y

8、 點(diǎn)定義在 X 點(diǎn)使用的變量，且該變量在沿從 Y 到 X 的路徑上其他任何地方?jīng)]有被重新定義，則稱語句 X 數(shù)據(jù)依賴于語句 Y。PDG 的形式定義是由一個控制依賴子圖，一個控制流圖和一個數(shù)據(jù)依賴子圖組成。其中 CDG 包含了程序中的控制依賴；CFG 描述了一個程序的控制流，它類似于正常情況下的流圖；DDG 是一個程序中語句之間所有數(shù)據(jù)依賴的集合。CDG 包含幾種類型的結(jié)點(diǎn)，即語句結(jié)點(diǎn)表示程序中的語句；域結(jié)點(diǎn)概括了域中語句間的控制依賴；謂詞結(jié)點(diǎn)（由此可以引出兩條邊）表示程序中的策略和分支條件。CDG 中的域結(jié)點(diǎn)可以用相同的控制依賴來集合語句。DDG 包含語句間的數(shù)據(jù)依賴?？赏ㄟ^在 CDG 的結(jié)點(diǎn)

9、之間插入數(shù)據(jù)依賴邊來構(gòu)造 DDG。同樣 PDG 不允許過程間分析，它也沒有能力表示繼承、多態(tài)性和動態(tài)性定連等重要的面向?qū)ο蟮奶匦浴?系統(tǒng)依賴圖（SDG）：SDG 是程序的一種語法分析樹表示。結(jié)點(diǎn)表示程序構(gòu)造，輸入輸出參數(shù)和調(diào)用位置等。邊表示與之相連的結(jié)點(diǎn)之間的各種依賴（例如數(shù)據(jù)依賴，控制依賴和聲明等）。程序依賴圖通常是為單個的過程間程序來定義的。由于現(xiàn)實(shí)世界的程序一般由多個過程組成的，所以必須考慮使用一種與現(xiàn)實(shí)世界程序匹配的表示方法，于是 Horwitz等人提出了系統(tǒng)依賴圖。SDG 是一顆經(jīng)過裝飾的表示程序的語法分析樹。形式地說，SDG是由一個程序依賴圖和一組過程依賴圖（PrDG）構(gòu)成的有向、

10、帶標(biāo)記的多重圖。PDG 模型化軟件系統(tǒng)中的主程序，PrDG 模型化軟件系統(tǒng)中的多個過程體。SDG 可以用來處理過程間的數(shù)據(jù)流和控制流，并能表示參數(shù)傳遞。SDG 允許過程間分析，但面向?qū)ο蟪绦蜻h(yuǎn)不是一些過程或方法的簡單組合，所以 SDG 提供的機(jī)制還不足以描述這些面向?qū)ο蟮母拍睢?5. 編譯器架構(gòu) LLVM LLVM 是一種應(yīng)用廣泛的開源編譯器架構(gòu)，該架構(gòu)采用模塊化設(shè)計(jì)，能夠輕松地新增對編程語言和處理器架構(gòu)的支持。 LLVM 支持各種各樣的編程語言和前端，其中包括 C/C+、Objective-C、Fortran、Ada、Haskell、Java bytecode、Python、Ruby、Act

11、ionScript、GLSL 以及 Rust。LLVM 是 Illinois 大學(xué)發(fā)起的一個開源項(xiàng)目。從字面上看，它是一個虛機(jī)系統(tǒng)，然而這又和之前為大家所熟知的 JVM 以及 . Runtime 這樣的虛機(jī)不同，它提供了一套中立的中間代碼和編譯基礎(chǔ)設(shè)施，并圍繞這些設(shè)施提供了一套全新的編譯策略（使得優(yōu)化能夠在編譯、連接、運(yùn)行環(huán)境執(zhí)行過程中，以及安裝之后以有效的方式進(jìn)行）和其他一些非常有意思的功能。 LLVM 的三階段設(shè)計(jì)： 圖 2 LLVM 的三階段 主要 _： 1 Weiser M. Program slicing. IEEE Transactions on Software Engineer

12、ingM，1984，16(5)： 498-509. 2 Binkley D.， Gallagher K. B. Program slicing. Advances in ComputersM，1996， 43： 1-50. 3 李必信. 程序切片技術(shù)及其應(yīng)用M. 北京：科學(xué)出版社,xx. 4 陳振強(qiáng). 基于依賴性分析的程序切片技術(shù)研究D.東南大學(xué)， xx. 5 The LLVM Compiler Infrastructure. ：/.llvm . 6 李娟. 基于故障注入的軟件安全測試技術(shù)研究D.國科學(xué)技術(shù)大學(xué)， xx 7 王越凡. 基于源碼分析的軟件安全測試技術(shù)研究D.北京郵電大學(xué)，xx 三、 實(shí)施方案 認(rèn)真了解程序切片相關(guān)知識完成開題報(bào)告 2 周 深入理解現(xiàn)有