嵌入式軟件運(yùn)行剖面建模及測(cè)試用例生成

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

　　1．軟件運(yùn)行剖面

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

　　2．運(yùn)行剖面的構(gòu)造過(guò)程

　　2.1 運(yùn)行的表示方法

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

　　2.2 將由運(yùn)行圖、狀態(tài)細(xì)化圖表示的運(yùn)行剖面轉(zhuǎn)化為Markov鏈表示

　　將以上兩種圖描述的運(yùn)行剖面轉(zhuǎn)化成Markov鏈描述主要基于以下考慮：

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

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

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

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

　　對(duì)每一個(gè)運(yùn)行圖，調(diào)用以下算法：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　每一個(gè)運(yùn)行經(jīng)算法作用后，都表示為一Markov鏈，根據(jù)算法，可以看出，該Markov鏈之包含了運(yùn)行中的帶有輸入的節(jié)點(diǎn)以及其中的一些關(guān)鍵節(jié)點(diǎn)，該Markov鏈綜合了每個(gè)運(yùn)行的運(yùn)行圖以及其狀態(tài)細(xì)化圖，以下的程序處理都基于此Markov鏈。

　　3. 測(cè)試用例自動(dòng)生成

　　測(cè)試用例是根據(jù)運(yùn)行剖面隨機(jī)生成的。在運(yùn)行剖面中已經(jīng)規(guī)定了每個(gè)輸入變量的取值類(lèi)型以及取值范圍，并且認(rèn)為變量在取值范圍內(nèi)均勻分布或分段均勻分布（由于很難確定變量的具體分布，這里假設(shè)為均勻分布）。軟件可靠性測(cè)試是一種隨機(jī)測(cè)試，測(cè)試用例的選取方式是隨機(jī)選取。因此，根據(jù)隨機(jī)測(cè)試的原則，在運(yùn)行剖面給定的輸入變量的取值區(qū)間內(nèi)任意抽取一個(gè)變量的實(shí)際取值。將各個(gè)變量按順序組合起來(lái)便生成了測(cè)試用例。用于軟件可靠性測(cè)試的測(cè)試用例可以定義為：根據(jù)運(yùn)行剖面生成的、完成對(duì)某一功能進(jìn)行測(cè)試的、按順序輸入到被測(cè)軟件的一系列輸入變量的有序組合。

　　嵌入式系統(tǒng)中，輸入可能為硬件信號(hào)或者人機(jī)接口，這就需要在標(biāo)示測(cè)試輸入類(lèi)型時(shí)進(jìn)行特殊標(biāo)記，這里，可采用兩種方法，一是軟件模擬硬件信號(hào)，即當(dāng)需要硬件信號(hào)時(shí)，由軟件模擬此硬件信號(hào)，來(lái)保證測(cè)試的執(zhí)行。二是對(duì)需要的硬件信號(hào)進(jìn)行標(biāo)示，當(dāng)需要硬件信號(hào)時(shí)，系統(tǒng)會(huì)提示需要某個(gè)硬件信號(hào)的觸發(fā)。

　　根據(jù)運(yùn)行剖面生成測(cè)試用例的過(guò)程為：運(yùn)行剖面由一系列變量的取值區(qū)間和該運(yùn)行發(fā)生的概率組成。

　　首先，要隨機(jī)抽取一個(gè)運(yùn)行來(lái)實(shí)現(xiàn)對(duì)某一功能的一次測(cè)試。抽取運(yùn)行的過(guò)程如下：

　　① 將運(yùn)行剖面｛OPi｜OPi=＜Oi,Pi＞，i=1,2,…，N｝中所有運(yùn)行發(fā)生的概率Pi求前j項(xiàng)和，形成一個(gè)數(shù)列｛Sj｝，Sj=∑Pi，其中，i=1,…j，j=1,2,…，N；N為軟件運(yùn)行剖面中運(yùn)行總數(shù)，規(guī)定S0=0,并有S1=P1,Sn=1.0,Sj-Sj-1=Pj。這里運(yùn)行相互獨(dú)立。

　　② 任給一個(gè)隨機(jī)數(shù)η∈(0,1.0)，觀察η落在哪個(gè)區(qū)間，若η滿(mǎn)足Sj-1＜η≤Sj，則該隨機(jī)數(shù)η與Pj這個(gè)概率值對(duì)應(yīng)，那么這次隨機(jī)抽到的運(yùn)行為Oj。

　?、?確定了抽到的運(yùn)行為Oi后，就可以確定該運(yùn)行的輸入情況，假設(shè)該運(yùn)行有m個(gè)輸入，每個(gè)輸入的可選值分別為I1,I2…Im，將其排列為一個(gè)二進(jìn)制串，若I1有m1個(gè)可選輸入，I2有m2個(gè)可選輸入Im有mm個(gè)可選輸入，則二進(jìn)制串為(00…0) (00…0)……(00…0)，其中，第一個(gè)括號(hào)內(nèi)的0有m1個(gè)，第二個(gè)括號(hào)中的0有m2個(gè)，第m個(gè)括號(hào)中的0有mm個(gè)，構(gòu)造一個(gè)布爾類(lèi)型的數(shù)組，數(shù)組的大小為2(I1+I2+…+Im)，數(shù)組的初始值均為false，每次產(chǎn)生一個(gè)測(cè)試用例時(shí)，從m個(gè)輸入的I1,I2…Im中每一個(gè)輸入的可選值中各選一個(gè)，并把二進(jìn)制串中的相應(yīng)位置1，m個(gè)輸入都選好后，把對(duì)應(yīng)的標(biāo)記數(shù)組置為true。生成一個(gè)測(cè)試用例后，首先判斷對(duì)應(yīng)的標(biāo)記數(shù)組，若為true，則需要重新生成一個(gè)用例。

　?、?其中，要進(jìn)行第二次抽樣來(lái)確定運(yùn)行中每個(gè)輸入的取值區(qū)間將取到的實(shí)體（即具體取值）。實(shí)體的確定將按照輸入變量的屬性分兩種情況進(jìn)行：

　　① 對(duì)于連續(xù)型輸入變量，運(yùn)行剖面給出的是該變量的取值區(qū)間的上下限［I.down,I.up］。抽樣時(shí)將根據(jù)輸入變量的數(shù)據(jù)類(lèi)型，在區(qū)間［I.down,I.up］內(nèi)隨機(jī)抽取一個(gè)滿(mǎn)足輸入變量數(shù)據(jù)類(lèi)型的具體值，作為該輸入變量的實(shí)體。

　　② 對(duì)于可選離散型輸入變量，運(yùn)行剖面給出的是一組離散點(diǎn)Ii,i=1,2,…,mi;mi為離散點(diǎn)的個(gè)數(shù)。抽樣時(shí)將在［1,mi］內(nèi)隨機(jī)抽取一個(gè)整數(shù)j，以確定選哪一個(gè)離散點(diǎn)作為該輸入變量的實(shí)體，并將該實(shí)體轉(zhuǎn)化為該輸入變量的數(shù)據(jù)類(lèi)型。

　?、?通過(guò)對(duì)運(yùn)行和各個(gè)實(shí)體兩個(gè)步驟的抽樣，完成一個(gè)測(cè)試用例的生成。

　　應(yīng)用測(cè)試用例可以進(jìn)行軟件可靠性測(cè)試： 圖1 測(cè)試系統(tǒng)

　　系統(tǒng)負(fù)責(zé)根據(jù)以上算法策略等產(chǎn)生測(cè)試用例，輸入到整個(gè)測(cè)試系統(tǒng)中，執(zhí)行可靠性測(cè)試，測(cè)試系統(tǒng)根據(jù)某種判斷策略，來(lái)決定此用例是否通過(guò)測(cè)試，若在規(guī)定的時(shí)間內(nèi)，規(guī)定的輸入條件下，所有用例均通過(guò)測(cè)試，則測(cè)試完成，若其中有測(cè)試用例沒(méi)有通過(guò)測(cè)試，只需要對(duì)被測(cè)軟件進(jìn)行修改，消除其中的錯(cuò)誤，再次進(jìn)行測(cè)試，而整個(gè)測(cè)試系統(tǒng)不需要任何改動(dòng)，大大的提高了測(cè)試的效率和靈活性。這種測(cè)試是統(tǒng)計(jì)測(cè)試，測(cè)試完全根據(jù)各個(gè)運(yùn)行所發(fā)生的概率以及運(yùn)行的權(quán)重來(lái)進(jìn)行的，在測(cè)試中, 優(yōu)先測(cè)試那些最重要或最頻繁使用的功能，釋放和緩解最高級(jí)別的風(fēng)險(xiǎn)，有助于盡早發(fā)現(xiàn)那些對(duì)可靠性有最大影響的故障。

　　4．結(jié)束語(yǔ)

　　本文完全從工程應(yīng)用的角度出發(fā)，根據(jù)被測(cè)軟件的需求規(guī)格說(shuō)明書(shū)，通過(guò)和軟件使用人員充分的交流，由測(cè)試人員構(gòu)造出軟件的運(yùn)行剖面，并用文中定義的運(yùn)行圖來(lái)描述，經(jīng)過(guò)算法轉(zhuǎn)化為帶標(biāo)記的 Markov鏈描述，依據(jù)該Markov鏈，可以自動(dòng)生成測(cè)試用例。配合相應(yīng)的測(cè)試環(huán)境，進(jìn)行自動(dòng)化的可靠性測(cè)試，可以極大的提高測(cè)試的效率，被測(cè)嵌入式系統(tǒng)的可靠性也可以進(jìn)行更加充分的驗(yàn)證。

　　今后的工作主要是輸入模型的提取與識(shí)別以及重組，從本文的前面，可以看出，系統(tǒng)的輸入還是比較繁瑣的，如果能夠直接讀取被測(cè)軟件的UML圖，從圖中提取各種信息，從而自動(dòng)構(gòu)造軟件的運(yùn)行剖面，則可以使整個(gè)過(guò)程更加高效，符合軟件測(cè)試的發(fā)展趨勢(shì)。此外，支撐測(cè)試環(huán)境的搭建，也需要認(rèn)真的研究。

　　本文作者創(chuàng)新點(diǎn)：

　　1．傳統(tǒng)的軟件測(cè)試都是根據(jù)軟件的源代碼進(jìn)行測(cè)試，本文則根據(jù)軟件的需求規(guī)格說(shuō)明書(shū)進(jìn)行測(cè)試，大大提高了測(cè)試的效率和靈活性。

　　2．用帶標(biāo)記的Markov鏈對(duì)軟件運(yùn)行剖面建模，為自動(dòng)產(chǎn)生測(cè)試用例打下了基礎(chǔ)。

　　3．能對(duì)產(chǎn)生的測(cè)試用例情況進(jìn)行標(biāo)記，避免產(chǎn)生相同的測(cè)試用例，提高了測(cè)試的效率。