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

1．軟件運行剖面

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

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

2.1 運行的表示方法

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

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

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

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

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

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

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

對每一個運行圖，調(diào)用以下算法：

1．首先，插入一個開始狀態(tài)，讀入第一個節(jié)點

2．對該節(jié)點進行以下判斷：

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

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

4．若還有其他節(jié)點，則進入下一個節(jié)點，重復步驟2，否則，算法結(jié)束

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

1．讀入一個分支的第一個節(jié)點

1．1對該節(jié)點進行以下判斷：

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

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

2．1若還有其他節(jié)點，則進入下一個節(jié)點，重復步驟1.1

3．1進行以下判斷：

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

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

4.1將當前節(jié)點置為算法開始時傳入的節(jié)點，即分支的父節(jié)點，進行判斷：

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

2．若還有其他分支，則進入其他分支，并設置當前分支為算法開始時傳入的父節(jié)點，重復步驟1

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

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

3. 測試用例自動生成

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

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

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

首先，要隨機抽取一個運行來實現(xiàn)對某一功能的一次測試。抽取運行的過程如下：

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

② 任給一個隨機數(shù)η∈（0，1.0），觀察η落在哪個區(qū)間，若η滿足Sj-1＜η≤Sj，則該隨機數(shù)η與Pj這個概率值對應，那么這次隨機抽到的運行為Oj。

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

④ 其中，要進行第二次抽樣來確定運行中每個輸入的取值區(qū)間將取到的實體（即具體取值）。實體的確定將按照輸入變量的屬性分兩種情況進行：

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

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

③ 通過對運行和各個實體兩個步驟的抽樣，完成一個測試用例的生成。

應用測試用例可以進行軟件可靠性測試： 圖1 測試系統(tǒng)

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

4．結(jié)束語

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

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

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

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

2．用帶標記的Markov鏈對軟件運行剖面建模，為自動產(chǎn)生測試用例打下了基礎。

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

責任編輯：ct