[發(fā)明專(zhuān)利]基于程序行為切片的測(cè)試案例約減方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310479195.8
• 申請(qǐng)日: 2013-10-14
• 公開(kāi)（公告）號(hào): CN103559122A
• 公開(kāi)（公告）日: 2014-02-05
• 發(fā)明（設(shè)計(jì)）人: 管曉宏;鄭慶華;劉烴;王海軍;俞樂(lè)晨;黃小龍
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安交通大學(xué)
• 主分類(lèi)號(hào): G06F11/36
• 分類(lèi)號(hào): G06F11/36
• 代理公司: 西安通大專(zhuān)利代理有限責(zé)任公司 61200
• 代理人: 蔡和平

技術(shù)領(lǐng)域

本發(fā)明涉及可信軟件及軟件測(cè)試領(lǐng)域，特別涉及模型檢驗(yàn)和程序控制流分析技術(shù)中測(cè)試案例約減方法。

背景技術(shù)

軟件測(cè)試是用來(lái)保證軟件質(zhì)量的基本手段，并且也是軟件開(kāi)發(fā)過(guò)程中最耗費(fèi)人力和物力的過(guò)程。在正常情況下，程序的輸入空間往往很大甚至不能窮盡，測(cè)試人員不可能運(yùn)行完所有的測(cè)試用例。因此選擇和生成有效的具有代表性的測(cè)試案例集，是軟件測(cè)試中最基礎(chǔ)的需求和問(wèn)題。傳統(tǒng)的挑選測(cè)試案例的方法根據(jù)其測(cè)試標(biāo)準(zhǔn)主要包括代碼覆蓋、分支覆蓋和路徑覆蓋。

基于代碼覆蓋和分支覆蓋的測(cè)試案例生成方法在工業(yè)上應(yīng)用廣泛，但是這兩種方法在發(fā)現(xiàn)程序錯(cuò)誤方面并沒(méi)有比隨機(jī)案例生成方法具有統(tǒng)計(jì)意義上的優(yōu)勢(shì)。

路徑覆蓋測(cè)試案例生成方法在這幾年得到了大力發(fā)展，各種工具也不斷出現(xiàn)，比如JPF-SE,Concolic，KLEE等等，但都面臨程序狀態(tài)空間爆炸的問(wèn)題。這些路徑覆蓋的測(cè)試案例生成工具都是基于符號(hào)執(zhí)行實(shí)現(xiàn)的。符號(hào)執(zhí)行是20世紀(jì)70年代提出的一種程序驗(yàn)證方法，是一種基于符號(hào)化的模型檢驗(yàn)方法。廣泛用于符號(hào)調(diào)試，測(cè)試案例生成等。其核心思想是使用符號(hào)值代替具體的變量輸入，并使用符號(hào)表達(dá)式來(lái)表示程序中各變量的值。最終，程序的輸出值被轉(zhuǎn)化為一個(gè)以符號(hào)值作為輸入的函數(shù)。符號(hào)執(zhí)行將程序抽象為符號(hào)執(zhí)行樹(shù)，其中順序語(yǔ)句對(duì)應(yīng)著樹(shù)的計(jì)算節(jié)點(diǎn)，分支語(yǔ)句對(duì)應(yīng)著分支節(jié)點(diǎn)，而對(duì)于循環(huán)語(yǔ)句，將其按循環(huán)次數(shù)展開(kāi)為語(yǔ)義上等價(jià)的分支語(yǔ)句。一般，一條循環(huán)語(yǔ)句對(duì)應(yīng)一組分支節(jié)點(diǎn)。可以認(rèn)為，在符號(hào)執(zhí)行過(guò)程中，程序只有順序和分支兩種結(jié)構(gòu)。符號(hào)執(zhí)行的過(guò)程本質(zhì)上是路徑條件的構(gòu)造過(guò)程。路徑條件指的是對(duì)于執(zhí)行該路徑的測(cè)試案例，程序輸入值所需要滿(mǎn)足的數(shù)學(xué)約束條件。因而一個(gè)路徑條件唯一地對(duì)應(yīng)一條執(zhí)行路徑。一個(gè)路徑條件由一組子條件（sub-condition）組成，每一個(gè)被執(zhí)行分支的條件作為一個(gè)子條件。在初始時(shí)路徑條件為true，在探索程序的過(guò)程中，每遇到一個(gè)分支語(yǔ)句，就更新路徑條件，將被執(zhí)行分支的條件加入到路徑條件中，公式為PC=PC^new?sub-condition。由于每一個(gè)分支語(yǔ)句都對(duì)應(yīng)著true和false兩個(gè)分支，而符號(hào)執(zhí)行基于靜態(tài)分析，變量沒(méi)有具體的數(shù)值，因而無(wú)法確定執(zhí)行哪一條分支。所以對(duì)兩條分支都進(jìn)行探索（搜索順序可按需定義，深度優(yōu)先，廣度優(yōu)先等），即分別以?xún)蓚€(gè)分支的條件作為子條件來(lái)更新路徑條件。這樣就得到了兩個(gè)新的路徑條件，對(duì)應(yīng)兩條不同的執(zhí)行路徑。之后，繼續(xù)對(duì)這兩條路徑分別進(jìn)行探索。符號(hào)執(zhí)行實(shí)現(xiàn)了對(duì)程序的全路徑探索。當(dāng)程序探索結(jié)束時(shí)就得到了被測(cè)程序所有執(zhí)行路徑的路徑條件。最后，檢查所有得到的路徑條件，如果路徑條件是無(wú)法被滿(mǎn)足的，則說(shuō)明該路徑是一條不可執(zhí)行路徑，如果路徑條件可以被滿(mǎn)足，則說(shuō)明該路徑是一條可執(zhí)行路徑。將路徑條件輸入約束求解器即可解出對(duì)應(yīng)的測(cè)試案例。

符號(hào)執(zhí)行存在兩個(gè)阻礙，使得其難以大規(guī)模使用。1）符號(hào)執(zhí)行是一種基于搜索的遍歷算法，需要對(duì)程序的所有分支進(jìn)行遍歷，雖然可以通過(guò)一些附加的剪枝條件進(jìn)行優(yōu)化，但其算法的復(fù)雜度非常高，為O(2n)，其中n為被測(cè)程序中條件語(yǔ)句（包括分支，循環(huán)，邏輯運(yùn)算）的數(shù)目；2）符號(hào)執(zhí)行不能很好地解決測(cè)試案例集更新的問(wèn)題，每次代碼進(jìn)行修改后，只能重新遍歷一次符號(hào)執(zhí)行樹(shù)來(lái)生成一個(gè)新的測(cè)試案例集。由前面的分析可知，重新生成一個(gè)測(cè)試案例集的時(shí)間開(kāi)銷(xiāo)比較大，而且一個(gè)軟件可能會(huì)頻繁變更，如果每次變更之后都通過(guò)符號(hào)執(zhí)行生成一個(gè)新的測(cè)試案例集，測(cè)試的效率就會(huì)受到影響。

如果一種測(cè)試案例生成方法能夠和全部路徑覆蓋同樣的程序行為并且避免列舉全部程序路徑將能大大提高程序的測(cè)試效率。

發(fā)明內(nèi)容：

本發(fā)明提出一種基于程序行為切片的測(cè)試案例約減方法，在無(wú)需對(duì)全部程序路徑進(jìn)行掃描的情況下，生成可以覆蓋全部程序行為的測(cè)試案例集，緩解程序測(cè)試面臨的狀態(tài)空間爆炸問(wèn)題。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

基于程序行為切片的測(cè)試案例約減方法，包括如下步驟：

S1)根據(jù)輸入的待測(cè)程序，利用靜態(tài)程序分析方法，分析待測(cè)程序的控制流和信息流，提取待測(cè)程序的控制依賴(lài)和數(shù)據(jù)依賴(lài)；

S2)根據(jù)待測(cè)程序的控制依賴(lài)和數(shù)據(jù)依賴(lài)，計(jì)算待測(cè)程序的潛在依賴(lài)；

S3)根據(jù)待測(cè)程序的控制依賴(lài)、數(shù)據(jù)依賴(lài)和潛在依賴(lài)，在程序控制流圖上構(gòu)建程序的組合依賴(lài)；

S4)利用符號(hào)執(zhí)行方法隨機(jī)生成一條初始路徑，并將對(duì)應(yīng)初始路徑的測(cè)試案例存入有效測(cè)試案例集；