形狀分析符號(hào)執(zhí)行引擎中的狀態(tài)合并.pdf

1、C語(yǔ)言以其對(duì)底層機(jī)器操控的靈活性，在操作系統(tǒng)、嵌入式軟件、底層驅(qū)動(dòng)等要求高效的軟件設(shè)計(jì)領(lǐng)域得到廣泛應(yīng)用。然而出于靈活性和效率的考慮，C語(yǔ)言賦予程序員對(duì)計(jì)算機(jī)完全掌控的能力同時(shí)，犧牲了一定的安全性:非法指針解引用、內(nèi)存泄漏、緩沖區(qū)溢出等內(nèi)存安全問題在C語(yǔ)言程序中尤其突出。
　　提高軟件的可靠性一直是軟件開發(fā)過程中所追求的目標(biāo)之一。程序動(dòng)態(tài)測(cè)試、程序靜態(tài)分析和程序驗(yàn)證是目前確保軟件安全質(zhì)量的主要方法。程序驗(yàn)證作為保證程序正確性的最嚴(yán)格

2、的手段，通過形式化方法對(duì)程序的各種性質(zhì)給出嚴(yán)格的數(shù)學(xué)證明，從而保證了程序的可靠性;然而程序驗(yàn)證目前還未實(shí)現(xiàn)自動(dòng)化證明，需要大量的人工證明，因此未能在工業(yè)界得到廣泛的應(yīng)用。程序動(dòng)態(tài)測(cè)試的測(cè)試結(jié)果依賴于給定的測(cè)試集，面對(duì)復(fù)雜的軟件系統(tǒng)測(cè)試集很難做到代碼的高覆蓋率，而且動(dòng)態(tài)測(cè)試的成本和風(fēng)險(xiǎn)較高。程序靜態(tài)分析在程序運(yùn)行之前對(duì)代碼進(jìn)行分析，可以較早并且低成本地發(fā)現(xiàn)代碼中可能存在的缺陷。
　　符號(hào)執(zhí)行技術(shù)以其良好的精度控制和代碼覆蓋率，被廣泛

3、用于程序靜態(tài)分析之中。對(duì)一個(gè)程序進(jìn)行分析時(shí)，符號(hào)執(zhí)行引擎以模擬真實(shí)的程序執(zhí)行過程的方式，分析程序的數(shù)據(jù)流和控制流信息，并檢查程序執(zhí)行過程中可能出現(xiàn)的所有狀態(tài)，得到程序的分析結(jié)果。高精度和高覆蓋率要求對(duì)程序狀態(tài)描述具體而完備，這會(huì)導(dǎo)致符號(hào)執(zhí)行過程中常見的狀態(tài)爆炸問題，使得符號(hào)執(zhí)行技術(shù)的可伸縮性（Scalability）較差。筆者所在項(xiàng)目組基于符號(hào)執(zhí)行技術(shù)實(shí)現(xiàn)了一個(gè)帶形狀分析功能的C程序分析工具，該工具同樣存在路徑爆炸、可伸縮性較差的問題，

4、本文的主要工作是設(shè)計(jì)和實(shí)現(xiàn)狀態(tài)合并功能及其優(yōu)化，主要貢獻(xiàn)有:
　　針對(duì)帶形狀分析的符號(hào)執(zhí)行引擎，設(shè)計(jì)并實(shí)現(xiàn)了狀態(tài)合并的算法，這其中主要的難點(diǎn)在于如何確保狀態(tài)合并的引入不會(huì)造成程序分析結(jié)果精度的下降，尤其是在引入形狀分析之后，在特定的狀態(tài)抽象規(guī)則之上，如何判定狀態(tài)是否可以合并，以及合并規(guī)則對(duì)分析精度的保證。
　　根據(jù)狀態(tài)合并在符號(hào)執(zhí)行引擎中的實(shí)際效果，考慮約束求解器的求解能力以及求解時(shí)間開銷，引入了約束求解器求解代價(jià)驅(qū)動(dòng)的優(yōu)化