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ā)生的概率。每一個(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è)輸入變量的取值類型以及取值范圍，并且認(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è)試輸入類型時(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ū)間，若η滿足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è)布爾類型的數(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è)用例。