發(fā)布時(shí)間：2022-01-01 17:11

　　軟件模型檢測(cè)是一種使用形式化方法驗(yàn)證軟件可靠性的重要技術(shù)方法。根據(jù)采用方法逼近方向的不同,軟件模型檢測(cè)可以分為上逼近方法和下逼近方法。本文中所研究的抽象-精煉方法,是對(duì)上下逼近方法的融合,它涵蓋了上逼近方法和下逼近方法并具有更好的性質(zhì)。傳統(tǒng)的軟件模型檢測(cè)根據(jù)所使用的程序狀態(tài)模型的不同,分別使用上逼近和下逼近方法進(jìn)行分析,因此與相應(yīng)模型緊密耦合的算法也常具有較大區(qū)別。這種內(nèi)在的區(qū)別使得軟件模型檢測(cè)算法之間難以復(fù)用,同時(shí)算法輸出的結(jié)果間也難以相互使用。近年來(lái),一些關(guān)于軟件模型檢測(cè)的上下逼近融合方法研究開始興起,通過設(shè)計(jì)狀態(tài)融合的操作運(yùn)算,使得上下逼近方法的狀態(tài)得以混合,在一定程度上做到了結(jié)果相互使用,但是這種使用依然是淺層的。不同范式的軟件模型檢測(cè)方法沒有做到深入地融合,其根本原因在于缺少一個(gè)統(tǒng)一的對(duì)軟件抽象狀態(tài)進(jìn)行描述的模型�，F(xiàn)有的模型多是基于不同形式的邏輯建立的狀態(tài)存儲(chǔ)和推理系統(tǒng),其本身是依附于具體狀態(tài)之上,著重描述程序的分立狀態(tài),缺乏對(duì)程序整體結(jié)構(gòu)信息的描述和分析。針對(duì)以上問題,本文的具體研究?jī)?nèi)容如下:（1）從軟件模型檢測(cè)中的下逼近方法入手,以有界模型檢測(cè)作為切入點(diǎn),分析了有界模型檢... 

【文章來(lái)源】：北京交通大學(xué)北京市 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：124 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

具有無(wú)環(huán)有限狀態(tài)機(jī)的圖靈機(jī)Figure6-2Turingmachinewithacyclicfinitemachine

平坦的LVV格結(jié)構(gòu)

梢鑰闖觶?絳蛑蔥惺倍??箍??傻慕詰慊岬賈魯絳蜃刺?占淶睦?大，其中造成這種生成的最直接的原因就是循環(huán)的展開。循環(huán)結(jié)構(gòu)在程序語(yǔ)言的語(yǔ)法中是由條件語(yǔ)句和前向跳轉(zhuǎn)組成，因此如果一個(gè)層在條件節(jié)點(diǎn)處發(fā)生分裂，那么它將有可能變成一個(gè)無(wú)限層。因此，阻止LVV格變成無(wú)限狀態(tài)的模型只需要阻止條件節(jié)點(diǎn)的完全展開。通過對(duì)節(jié)點(diǎn)展開的合理抑制就可以得到一個(gè)有限狀態(tài)的模型，這種抑制展開的技術(shù)在模型檢測(cè)領(lǐng)域通常被稱為惰性的（Lazy）展開方法。根據(jù)這個(gè)原理和前面對(duì)程序模型的分析可以將圖6-3程序的LVV格模型進(jìn)一步地表示成圖6-5的樣子。圖6-5惰性LVV格結(jié)構(gòu)Figure6-5LazyLVVlattice在這個(gè)改造后的LVV格結(jié)構(gòu)中，原本的三層分層在分支處分裂成更多子層，這些子層反映了程序的動(dòng)態(tài)特性�？梢宰⒁獾�，在圖6-5各層的垂直排列上即采取了圖6-4中按照抽象的包含順序進(jìn)行，同時(shí)它也是按照動(dòng)態(tài)生成的順序進(jìn)行。這種排列方式更容易分辨出層間的動(dòng)態(tài)生成關(guān)系。其中綠色的關(guān)系代表分支判斷時(shí)具體的執(zhí)行方式，而其對(duì)應(yīng)的黑色關(guān)系則是相應(yīng)的抽象執(zhí)行方式。為了使得程序的分支展開得以進(jìn)行，這些綠色的執(zhí)行是需要從抽象中進(jìn)行展開的。這個(gè)惰性的LVV結(jié)構(gòu)從執(zhí)行上對(duì)程序的行為進(jìn)行了描述。從另一個(gè)角度來(lái)講，圖中的節(jié)點(diǎn)i<3是自由變量i的限定版本，形式上可以被描述為}}{{3CTii<，但是可以發(fā)現(xiàn)在圖6-4的相同關(guān)系卻使用}}{{3MPii<來(lái)描述。這就意味著在特定的情況下，CT和MP可以互相轉(zhuǎn)換。如果單純從原本幾何的角度來(lái)理解，對(duì)于相互正交的關(guān)系來(lái)講，本來(lái)不應(yīng)該存在線性的相關(guān)性，因此這種關(guān)系的存在暗示了這種表面上的正交關(guān)系存在更為深刻的聯(lián)系。在后續(xù)的討論中可以發(fā)現(xiàn)，這種相互可轉(zhuǎn)換性是普遍存在的，

【參考文獻(xiàn)】：
期刊論文
[1]Automated coverage-driven testing: combining symbolic execution and model checking[J]. Ting SU,Geguang PU,Weikai MIAO,Jifeng HE,Zhendong SU.  Science China（Information Sciences）. 2016(09)



本文編號(hào)：3562471