動(dòng)態(tài)符號(hào)執(zhí)行約束求解優(yōu)化設(shè)計(jì)與實(shí)現(xiàn).pdf

1、從上個(gè)世紀(jì)至今，計(jì)算機(jī)的各個(gè)領(lǐng)域都取得了長足的進(jìn)步，軟件作為存儲(chǔ)和管理信息的工具，已廣泛深入到現(xiàn)實(shí)社會(huì)的各個(gè)領(lǐng)域，成為整個(gè)社會(huì)的支柱產(chǎn)業(yè)之一，正是因?yàn)檐浖闹匾匀找嫣嵘?，軟件漏洞可能帶來的損失也越來越大，特別是在對(duì)軟件漏洞比較敏感的領(lǐng)域，例如：金融、瓦斯檢測、航天等行業(yè)，任何一個(gè)不易察覺的漏洞都可能引災(zāi)難性事故。程序分析技術(shù)和軟件測試技術(shù)的目的在于，確保待分析程序的正確性、一致性以及確保程序在安全狀態(tài)下運(yùn)行。軟件測試的發(fā)展過程中，出現(xiàn)

2、了一系列的測試技術(shù)，從最初的靜態(tài)代碼分析技術(shù)到曾經(jīng)被廣泛使用的糊測試技術(shù)，軟件測試技術(shù)也隨著現(xiàn)代計(jì)算機(jī)水平的進(jìn)步和軟件行業(yè)對(duì)安全需求的提升而不斷地發(fā)展。
　　符號(hào)執(zhí)行技術(shù)于上世紀(jì)70年代被提出，受限于當(dāng)時(shí)的軟硬件條件未被廣泛應(yīng)用，隨著近些年計(jì)算機(jī)技術(shù)的發(fā)展，符號(hào)執(zhí)行技術(shù)被再一次重視起來。動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)是一種衍生于傳統(tǒng)符號(hào)執(zhí)行的新技術(shù)，采用符號(hào)與具體值相結(jié)合的方式，有著代碼覆蓋率高、可以自動(dòng)生成測試用例等特點(diǎn)。動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)一經(jīng)

3、提出就受到了眾多軟件公司和研究人員的重視，在學(xué)術(shù)界和產(chǎn)業(yè)界均取得了較大的進(jìn)步，并且形成了了一系列工具，在實(shí)際應(yīng)用中有著較好的效果。但是，目前為止，動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)還存在一些難以解決的問題，例如，路徑爆炸以及面對(duì)應(yīng)用領(lǐng)域復(fù)雜性和程序設(shè)計(jì)語言復(fù)雜性時(shí)所受到的局限等等。
　　本文著眼于動(dòng)態(tài)符號(hào)執(zhí)行的約束求解優(yōu)化問題，提出一種針對(duì)約束集合的基于線性規(guī)劃技術(shù)的優(yōu)化方法，通過此優(yōu)化方法可以降低約束集合中約束條件的復(fù)雜性，降低后續(xù)求解生成測試用

4、例過程的計(jì)算復(fù)雜度，從一定程度上提升了約束求解過程的效率，本文選擇KLEE作為研究對(duì)象，為其約束求解部分增加一個(gè)LP_OP模塊，在該模塊中實(shí)現(xiàn)了線性規(guī)劃優(yōu)化過程，以達(dá)到提高動(dòng)態(tài)符號(hào)執(zhí)行約束求解過程效率的目的。
　　為驗(yàn)證LP_OP模塊對(duì)KLEE約束求解效率的提升，本文選擇幾個(gè)常用工具作為分析對(duì)象，使用KLEE對(duì)這些程序進(jìn)行程序分析并生成相應(yīng)的測試用例。通過對(duì)比加入LP_OP模塊前后約束求解過程消耗的時(shí)間和整個(gè)KLEE執(zhí)行過程消耗的