嵌入式軟件運行剖面建模及測試用例生成

航天應用中的大部分軟件都是嵌入式軟件，可靠性要求很高，因此，對其進(jìn)行充分測試顯得尤為重要。但是，嵌入式軟件運行環(huán)境同硬件有著(zhù)密切的關(guān)系，使得嵌入式軟件測試過(guò)程非常復雜，目前存在的一些測試工具偏重于白盒測試且價(jià)格昂貴，針對黑盒測試，目前還是以人工測試為主。由于軟件的復雜程度越來(lái)越高，導致人為設計測試用例數量巨大且無(wú)法保證測試充分性。而對航天軟件來(lái)說(shuō)，是否滿(mǎn)足任務(wù)要求是軟件的重點(diǎn)，因此，從用戶(hù)的角度對軟件運行剖面進(jìn)行數學(xué)建模，對系統是怎樣的以及它會(huì )怎樣被使用做出一個(gè)定量描述，根據這些量值可以對軟件中至關(guān)重要的、生命攸關(guān)的、關(guān)系到系統成敗的部分給與充分的測試。通過(guò)任務(wù)剖面模型可獲取測試用例和測試數據的等價(jià)類(lèi)信息，自動(dòng)生成測試用例，大大減輕測試人員的工作量，提高了測試工作的效率和質(zhì)量。本文中采用帶標記的Markov鏈對軟件運行剖面進(jìn)行描述，并據此生成測試用例。

　　1．軟件運行剖面

　　軟件運行剖面是用來(lái)描述軟件的實(shí)際使用情況的。1993年，MUSA在IEEE發(fā)表了一篇題為《軟件可靠性工程中的運行剖面》的文章，開(kāi)創(chuàng )了軟件運行剖面的研究，文中MUSA給出了實(shí)施軟件運行剖面的一般步驟。MUSA（參考文章[1]）對軟件分析的原則，不僅適用于嵌入式軟件，對一般的應用軟件也適用。首先對軟件的使用者進(jìn)行分類(lèi)，不同類(lèi)型的使用者可能以不同的方式來(lái)使用軟件，根據對使用者的劃分將軟件劃分成不同的模式剖面。其次，模式剖面又可以劃分為不同的功能剖面，即每個(gè)模式下都有許多不同的功能。最后，每一個(gè)功能又由許多運行組成。這些運行的集合便構成了運行剖面。上述的每一次劃分都是依據概率發(fā)生的，這些概率估計主要是基于如下幾個(gè)方面： ① 從現有系統收集到的數據， ② 與用戶(hù)的交談或對用戶(hù)進(jìn)行觀(guān)察獲得的信息， ③ 原型使用與試驗分析的結果， ④ 相關(guān)領(lǐng)域專(zhuān)家的意見(jiàn)。定義使用概率的最佳方法是使用實(shí)際的用戶(hù)數據，如來(lái)自原型系統、前一版本的使用數據；其次是由該軟件應用領(lǐng)域的用戶(hù)和專(zhuān)家提供的預期使用數據。軟件的運行剖面是定量描述用戶(hù)實(shí)際使用軟件方式的有效方法。MUSA的軟件劃分原則簡(jiǎn)單且容易實(shí)施，只要按照步驟逐步實(shí)行就可以得出軟件的比較準確的運行剖面。但是，也要看到，MUSA的軟件分析原則只是提供了一個(gè)分析軟件的方法，在特定的應用中，有些步驟可以簡(jiǎn)化處理，根據具體的實(shí)際情況，靈活運用。

　　2．運行剖面的構造過(guò)程

　　2.1 運行的表示方法

　　首先來(lái)定義兩種圖，第一種圖用來(lái)描述分解后的運行，即運行圖，定義為T(mén)F={P1，P2，……Pn}，其中，P1，P2……Pn表示構成運行的各個(gè)狀態(tài)，Pi的下一個(gè)狀態(tài)為Pi+1，Pi的上一個(gè)狀態(tài)為Pi-1，這些狀態(tài)表示的是一個(gè)任務(wù)從開(kāi)始到結束的一個(gè)過(guò)程，即P1-〉P2……-〉Pn。我們可以用這個(gè)圖來(lái)描述經(jīng)分析得到的運行。當運行圖中某個(gè)狀態(tài)中可以有幾種不同的路徑到達下一個(gè)狀態(tài)時(shí)，僅用運行圖就不能準確表達該運行，此時(shí)，就要用到狀態(tài)細化圖，狀態(tài)細化圖用來(lái)描述運行圖中狀態(tài)的內部細節，定義為一個(gè)三元組DTF= ，其中，sequence={Bi|Bi=TFi}， i=1……n。start為此細化圖的公共開(kāi)始節點(diǎn)，end為此細化圖的公共終止節點(diǎn)。被測軟件中所有的運行，只要劃分的足夠細，都可以由上面兩種圖準確的表示出來(lái)。

　　2.2 將由運行圖、狀態(tài)細化圖表示的運行剖面轉化為Markov鏈表示

　　將以上兩種圖描述的運行剖面轉化成Markov鏈描述主要基于以下考慮：

　　1．Markov鏈的特點(diǎn)是下一個(gè)狀態(tài)只和當前狀態(tài)有關(guān)，而與歷史狀態(tài)無(wú)關(guān)，在這里就是軟件的當前狀態(tài)只和上一狀態(tài)有關(guān)，與更早的歷史狀態(tài)無(wú)關(guān)，若上一狀態(tài)正確，則在正確的輸入下，軟件的當前狀態(tài)一定正確，否則，軟件一定存在缺陷，這對于定位軟件測試中的錯誤是十分方便的，通過(guò)Markov鏈中狀態(tài)轉移概率，還能直觀(guān)的認識到軟件中各個(gè)功能的使用頻率，給出一個(gè)定量的描述。

　　2．這里的Markov鏈描述相當于編譯中的中間語(yǔ)言，即程序的所有處理都是基于Markov鏈的。使用中間語(yǔ)言便于程序內部處理。

　　3．當某個(gè)節點(diǎn)內部有需要細化的分支時(shí)，Markov鏈會(huì )綜合內部分支，給出一個(gè)整體的綜合表述。這對于產(chǎn)生測試用例非常方便。

　　4.算法1：圖描述轉化為Markov鏈描述算法：該算法的輸入為運行圖、以及狀態(tài)細化圖，將運行圖進(jìn)行化簡(jiǎn)、并綜合其中的狀態(tài)細化圖，將每一個(gè)運行都表示為一Markov鏈。

　　對每一個(gè)運行圖，調用以下算法：

　　1．首先，插入一個(gè)開(kāi)始狀態(tài)，讀入第一個(gè)節點(diǎn)

　　2．對該節點(diǎn)進(jìn)行以下判斷：

　　3.1.1 該節點(diǎn)是否為分支節點(diǎn)，若是則對該節點(diǎn)調用分枝遍歷算法

　　2.1 其次判斷該節點(diǎn)是否有輸入，若有則插入一個(gè)新?tīng)顟B(tài)，并設置新?tīng)顟B(tài)的相關(guān)屬性，并生成一條消息從當前狀態(tài)指向新插入的狀態(tài)

　　4．若還有其他節點(diǎn)，則進(jìn)入下一個(gè)節點(diǎn)，重復步驟2，否則，算法結束

　　5. 算法2：分支遍歷算法：

　　1．讀入一個(gè)分支的第一個(gè)節點(diǎn)

　　1．1對該節點(diǎn)進(jìn)行以下判斷：

　　1．1.1判斷該節點(diǎn)是否為分支節點(diǎn)，若是則調用分支遍歷算法

　　2．1.1判斷該節點(diǎn)是否有輸入，若有則插入一個(gè)新?tīng)顟B(tài)，設置新?tīng)顟B(tài)的相關(guān)屬性，并生成一條消息從當前狀態(tài)指向新插入的狀態(tài)

　　2．1若還有其他節點(diǎn)，則進(jìn)入下一個(gè)節點(diǎn)，重復步驟1.1

　　3．1進(jìn)行以下判斷：

　　1.3.1若當前處理完的為第一個(gè)分支，則插入一個(gè)新的狀態(tài)，并使最后一個(gè)節點(diǎn)指向這個(gè)新插入的節點(diǎn)

　　2.3.1若不是第一個(gè)分支，則使最后一個(gè)節點(diǎn)指向第一個(gè)分支的最后一個(gè)節點(diǎn)

　　4.1將當前節點(diǎn)置為算法開(kāi)始時(shí)傳入的節點(diǎn)，即分支的父節點(diǎn)，進(jìn)行判斷：

　　1.4.1當前父節點(diǎn)是否有超過(guò)1個(gè)的子分支，若有則進(jìn)行判斷：若超過(guò)一個(gè)子分支的下一個(gè)節點(diǎn)都是第一個(gè)分支的最后一個(gè)節點(diǎn)，則將這些子分支合并成一個(gè)子分支，即由父狀態(tài)指向第一個(gè)分支的最后一個(gè)節點(diǎn)，概率為各個(gè)子分支的和

　　2．若還有其他分支，則進(jìn)入其他分支，并設置當前分支為算法開(kāi)始時(shí)傳入的父節點(diǎn)，重復步驟1

　　經(jīng)以上算法作用后，運行剖面可以表示為｛OPi｜OPi=＜Oi,Pi＞，i=1,2,…，N｝，其中Oi表示組成這個(gè)運行剖面的其中一個(gè)運行，Pi表示這個(gè)運行發(fā)生的概率。