基于狀態(tài)轉(zhuǎn)移圖的箭載軟件時(shí)序控制測(cè)試用例生成方法

汪冬瑾，張 舒

(1.宇航智能控制技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，北京 100854；2.北京航天自動(dòng)控制研究所，北京 100854)

0 引言

箭載軟件是航天系統(tǒng)的運(yùn)行基礎(chǔ)，其失效會(huì)直接導(dǎo)致發(fā)射的失敗進(jìn)而危及人員的安全，因此軟件研制質(zhì)量極為重要，現(xiàn)常采用人工設(shè)計(jì)專用測(cè)試用例的方式來驗(yàn)證軟件功能、性能及極限情況下的故障處理能力，從而保證軟件的可靠性[1-2]。然而如今型號(hào)種類增加、研制周期縮短、軟件規(guī)模擴(kuò)大、結(jié)構(gòu)層次復(fù)雜卻受限于型號(hào)的定制化需求，無法直接沿用已有軟件，相應(yīng)的軟件測(cè)試工作必不可少。

人工設(shè)計(jì)用例方式受人為因素影響較大且日益不能滿足現(xiàn)有需求，因此針對(duì)軟件功能中的時(shí)序控制功能，本文提出了一種基于狀態(tài)轉(zhuǎn)移圖的測(cè)試用例自動(dòng)生成算法設(shè)計(jì)方法，以期實(shí)現(xiàn)時(shí)序控制功能測(cè)試用例自動(dòng)生成，提升測(cè)試效率和質(zhì)量，為軟件自動(dòng)化測(cè)試提供一定的借鑒。本文首先分析時(shí)序控制特性，其次選取狀態(tài)轉(zhuǎn)移圖來表征，自定義所需圖元屬性以及圖元關(guān)系、觸發(fā)條件全面性與一致性的約束條件從而保證模型合理性；再次采用基路徑覆蓋、轉(zhuǎn)移對(duì)覆蓋、條件元覆蓋3種覆蓋準(zhǔn)則相結(jié)合方式實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成；最后以某箭上軟件全飛行周期時(shí)序控制為例，驗(yàn)證了上述基于狀態(tài)轉(zhuǎn)移圖的測(cè)試用例自動(dòng)生成方法的有效性和穩(wěn)定性。

1 時(shí)序控制特性分析

飛行控制軟件是火箭控制系統(tǒng)實(shí)現(xiàn)的載體，軟件將連續(xù)的控制系統(tǒng)分成離散的控制周期，以定時(shí)中斷的方式近似的實(shí)現(xiàn)。時(shí)序控制承載軟件的動(dòng)態(tài)特征，時(shí)序切換對(duì)軟件功能和運(yùn)行結(jié)果的影響貫穿整個(gè)軟件生命周期[3]。

飛行控制軟件一般會(huì)分為幾個(gè)飛行段，在不同的飛行段中有不同的時(shí)序，軟件中實(shí)現(xiàn)的特點(diǎn)為[4]：

1)軟件中的某一個(gè)時(shí)序，在軟件動(dòng)態(tài)運(yùn)行時(shí)一般不會(huì)重復(fù)進(jìn)入兩次，已經(jīng)切換到其它時(shí)序，則通常不會(huì)再回來；

2)時(shí)序切換的條件一般為邏輯組合，且判定條件經(jīng)常需要多種條件共同滿足，如：到達(dá)一定時(shí)間、某一計(jì)算功能得到的結(jié)果達(dá)到某一范圍等；

3)某個(gè)時(shí)序可能切換到不同的后續(xù)時(shí)序中(主時(shí)序和多個(gè)備保時(shí)序)，其切換路徑取決于系統(tǒng)滿足不同的邏輯組合；

4)時(shí)序切換會(huì)伴隨特定的軟件動(dòng)態(tài)行為和輸出；

5)時(shí)序切換會(huì)伴隨軟件功能和運(yùn)行參數(shù)的變化。

通常對(duì)時(shí)序控制功能的考核點(diǎn)包括：

1)用邊界值的測(cè)試方法考核時(shí)序切換判定邏輯組合實(shí)現(xiàn)的正確性；

2)當(dāng)被考查時(shí)序可能切換到多個(gè)后續(xù)時(shí)序時(shí)，考查每一種邏輯組合分別滿足時(shí)，時(shí)序的切換是否與需求一致；考查多個(gè)切換邏輯組合同時(shí)滿足時(shí)，系統(tǒng)能否切換到一個(gè)確定后續(xù)時(shí)序中而不發(fā)生沖突；

3)考查時(shí)序切換伴隨的軟件動(dòng)態(tài)行為和輸出是否正確；

4)時(shí)序切換導(dǎo)致的飛行控制軟件功能或計(jì)算參數(shù)的變化是否滿足預(yù)期要求，以及隨著參數(shù)和功能變化進(jìn)行相應(yīng)的初始化或過度處理。

2 狀態(tài)轉(zhuǎn)移圖設(shè)計(jì)

狀態(tài)轉(zhuǎn)移圖適合描述動(dòng)態(tài)特征，即運(yùn)行狀態(tài)切換、應(yīng)激反應(yīng)等內(nèi)容[5]。為了適用于本文應(yīng)用環(huán)境，對(duì)狀態(tài)圖內(nèi)容進(jìn)行了一些擴(kuò)展和自定義：在狀態(tài)轉(zhuǎn)移圖中融入一些必要的測(cè)試信息；借鑒活動(dòng)圖的表達(dá)特點(diǎn)，使?fàn)顟B(tài)圖能夠表達(dá)具有原子性和瞬時(shí)性的軟件功能；借鑒正則語言形式化特點(diǎn)，為狀態(tài)圖設(shè)置嚴(yán)格的語法約束，使?fàn)顟B(tài)圖的語義滿足全面性和一致性要求，以避免在測(cè)試需求分析過程引入錯(cuò)誤。

2.1 圖元屬性定義

狀態(tài)轉(zhuǎn)移圖的圖元主要包括狀態(tài)起點(diǎn)、狀態(tài)節(jié)點(diǎn)、狀態(tài)終點(diǎn)和狀態(tài)轉(zhuǎn)移連線，如圖1所示[6-7]。狀態(tài)起點(diǎn)為軟件運(yùn)行至該狀態(tài)圖上的初始狀態(tài)節(jié)點(diǎn)；狀態(tài)節(jié)點(diǎn)宏觀上用于表示軟件運(yùn)行過程中的階段、時(shí)序，微觀上表示軟件運(yùn)行過程中的某個(gè)操作進(jìn)程或處理流程，設(shè)置其屬性包括名稱、關(guān)聯(lián)狀態(tài)、動(dòng)作列表、內(nèi)嵌模型列表、描述等5個(gè)方面，如表1所示。

圖1 狀態(tài)轉(zhuǎn)移圖示意圖

表1 WUL結(jié)果及解算時(shí)間統(tǒng)計(jì)

狀態(tài)終點(diǎn)為狀態(tài)轉(zhuǎn)移的最后狀態(tài)節(jié)點(diǎn)，理論上，一個(gè)狀態(tài)圖可以沒有狀態(tài)終點(diǎn)(軟件可以很長(zhǎng)甚至無限的生命周期)，也可以有多個(gè)狀態(tài)終點(diǎn)(一個(gè)終點(diǎn)對(duì)應(yīng)軟件運(yùn)行的某種結(jié)果)。然而軟件運(yùn)行過程中的狀態(tài)圖支持在自身的狀態(tài)節(jié)點(diǎn)中嵌套另一個(gè)狀態(tài)圖。如果子狀態(tài)圖沒有狀態(tài)終點(diǎn)，則導(dǎo)致軟件可能永久停滯在上層狀態(tài)圖的父狀態(tài)節(jié)點(diǎn)中，產(chǎn)生語義錯(cuò)誤；并且航天工程軟件受硬件資源影響，運(yùn)行壽命受限，因此設(shè)置狀態(tài)圖中必須至少有一個(gè)狀態(tài)終點(diǎn)，且軟件運(yùn)行最終必會(huì)到達(dá)一個(gè)狀態(tài)終點(diǎn)。

狀態(tài)轉(zhuǎn)移連線表示軟件運(yùn)行階段的切換行為，設(shè)置其屬性包括名稱和觸發(fā)條件，其中觸發(fā)條件定義為條件元或邏輯表達(dá)式，為狀態(tài)轉(zhuǎn)移發(fā)生的前提條件?？紤]到被測(cè)軟件狀態(tài)節(jié)點(diǎn)可能存在瞬時(shí)特性，因此定義觸發(fā)條件可缺省，即當(dāng)軟件運(yùn)行至該狀態(tài)節(jié)點(diǎn)時(shí)，執(zhí)行進(jìn)入動(dòng)作后直接進(jìn)入連線所指的下一狀態(tài)節(jié)點(diǎn)。

2.2 語法約束

為了保證測(cè)試模型語義合理性[5,7]，本文還對(duì)圖元關(guān)系、觸發(fā)條件的全面性與一致性進(jìn)行了約束。

2.2.1 基本圖元關(guān)系約束

狀態(tài)轉(zhuǎn)移圖圖圖元間應(yīng)滿足以下幾項(xiàng)：

1)狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)名稱唯一不可重復(fù)；

2)一個(gè)狀態(tài)必須且只能關(guān)聯(lián)一個(gè)狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)；

3)一幅狀態(tài)轉(zhuǎn)移圖有且僅有一個(gè)狀態(tài)起點(diǎn)，至少有一個(gè)狀態(tài)終點(diǎn)；

4)狀態(tài)起點(diǎn)只能與狀態(tài)轉(zhuǎn)移連線首端相連，狀態(tài)終點(diǎn)只能與狀態(tài)轉(zhuǎn)移連線末端相連，狀態(tài)起點(diǎn)和狀態(tài)終點(diǎn)不能直接通過狀態(tài)轉(zhuǎn)移連線相連；

5)狀態(tài)轉(zhuǎn)移連線首尾必須連接其它圖元，可連接同一個(gè)狀態(tài)節(jié)點(diǎn)。當(dāng)指向同一個(gè)狀態(tài)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移連線上的出發(fā)條件滿足時(shí)，系統(tǒng)重新執(zhí)行一次該節(jié)點(diǎn)的進(jìn)入動(dòng)作。

2.2.2 觸發(fā)條件全面性與一致性約束

為便于表述，定義觸發(fā)條件全面性與一致性約束前，首先定義一些數(shù)學(xué)符號(hào)：

1)符號(hào)“is_True()”表示返回邏輯表達(dá)式的真假值，即當(dāng)前情況下邏輯表達(dá)式所述內(nèi)容是否發(fā)生，例如對(duì)任意邏輯表達(dá)式(Cond)，其真假值表示為：is_True(Cond)，且is_True(φ)==False。

2)對(duì)任意的一個(gè)沒有定義轉(zhuǎn)移觸發(fā)條件的狀態(tài)轉(zhuǎn)移連線，模型系統(tǒng)自動(dòng)認(rèn)定它含有一個(gè)觸發(fā)條件表達(dá)式(Cond_Def)，且is_Ture(Cond_Def)==True。

以圖2為例，示意了觸發(fā)條件全面性與一致性約束說明。

圖2 觸發(fā)條件全面性與一致性約束示意

a)觸發(fā)條件全面性約束規(guī)定了軟件動(dòng)態(tài)運(yùn)行時(shí)不能出現(xiàn)永遠(yuǎn)停滯在某一個(gè)狀態(tài)節(jié)點(diǎn)的情況，并考慮到狀態(tài)轉(zhuǎn)移連線首尾與一個(gè)狀態(tài)節(jié)點(diǎn)連接的情況。即對(duì)任意的狀態(tài)節(jié)點(diǎn)(Node)，如果從該節(jié)點(diǎn)出發(fā)有n條指向別處的狀態(tài)轉(zhuǎn)移連線，它們的轉(zhuǎn)移觸發(fā)條件分別為(Cond1,Cond2,…,CondN)。則要求滿足：is_True(Cond1∨Cond2∨...∨CondN) != False。

b)觸發(fā)條件一致性約束規(guī)定對(duì)任意的狀態(tài)節(jié)點(diǎn)(Node)，如果從該節(jié)點(diǎn)出發(fā)有n條狀態(tài)轉(zhuǎn)移連線，對(duì)其中任意的一組觸發(fā)條件(Condi和Condj(i≠j，如果有))，需滿足：is_True(Condi∧Condj)==False。以圖2中狀態(tài)節(jié)點(diǎn)A為例，如果CondiB∧CondiC的值不為False，當(dāng)CondiB∧CondiC條件滿足時(shí)，模型無法確定軟件將進(jìn)入狀態(tài)C或者狀態(tài)D，出現(xiàn)二義性。

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

在上述第2章節(jié)狀態(tài)轉(zhuǎn)移圖的圖元和語法約束設(shè)計(jì)基礎(chǔ)上，采用基路徑覆蓋、轉(zhuǎn)移對(duì)覆蓋、條件元覆蓋3種覆蓋準(zhǔn)則結(jié)合來考核軟件時(shí)序控制功能，從而實(shí)現(xiàn)軟件測(cè)試用例自動(dòng)生成[8]，流程圖如圖3所示。首先使用基路徑覆蓋準(zhǔn)則生成基本的測(cè)試用例；其次對(duì)狀態(tài)圖中的入度大于1的狀態(tài)節(jié)點(diǎn)用轉(zhuǎn)移對(duì)覆蓋準(zhǔn)則進(jìn)行用例的補(bǔ)充和擴(kuò)展；最后對(duì)狀態(tài)圖中由邏輯表達(dá)式構(gòu)成觸發(fā)條件使用條件元覆蓋準(zhǔn)則進(jìn)行用例擴(kuò)展。

圖3 測(cè)試用例生成算法設(shè)計(jì)流程圖

3.1 基路徑覆蓋準(zhǔn)則

采用深度優(yōu)先的算法尋找基路徑，并對(duì)訪問過的路徑進(jìn)行標(biāo)記以避免重復(fù)，對(duì)于狀態(tài)轉(zhuǎn)移圖中存在的循環(huán)，算法保證每個(gè)循環(huán)路徑在測(cè)試用例集中最多出現(xiàn)一次。生成的用例個(gè)數(shù)為狀態(tài)圖的圈復(fù)雜度：V(G)=e-n+2p。

3.2 轉(zhuǎn)移對(duì)覆蓋準(zhǔn)則

以每個(gè)狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)為驗(yàn)證對(duì)象，設(shè)該狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)的入度為m，出度為n，則按照每一種流入該狀態(tài)節(jié)點(diǎn)的轉(zhuǎn)移連線和從該狀態(tài)節(jié)點(diǎn)留出的轉(zhuǎn)移連線的組合，生成m*n個(gè)測(cè)試用例。

3.3 路徑相關(guān)的狀態(tài)轉(zhuǎn)移條件判斷

對(duì)于描述軟件應(yīng)激行為的狀態(tài)轉(zhuǎn)移圖，其狀態(tài)切換除與外界激勵(lì)相關(guān)外，還可能與之前經(jīng)歷過的狀態(tài)路徑相關(guān)，一個(gè)典型的例子如圖4所示，省略了大部分的轉(zhuǎn)移條件，僅保留與轉(zhuǎn)移路徑相關(guān)的條件。

圖4 路徑相關(guān)的狀態(tài)轉(zhuǎn)移判定

為了使模型能夠表述此類觸發(fā)條件，可以引入一種特殊的條件元，即is_in_Path(State)，該條件元也具有一個(gè)布爾返回值。圖4中由A轉(zhuǎn)C的觸發(fā)條件可以用is_in_Path(B)表示，由A轉(zhuǎn)D的觸發(fā)條件則用is_in_Path(B)和is_in_Path(C)表示。

生成測(cè)試用例時(shí)，算法應(yīng)自動(dòng)替換不會(huì)發(fā)生的狀態(tài)轉(zhuǎn)移路徑。按照基路徑生成方法可能會(huì)生成的測(cè)試用例考查的路徑為：“A-D”、“A-B-D”、“A-C-D”、“A-C-B-D”，這些都是非法的，應(yīng)被自動(dòng)剔除，唯一合法的測(cè)試路徑為“A-B-C-D”。

3.4 條件元覆蓋

在基路徑覆蓋的基礎(chǔ)上，對(duì)于在每一處轉(zhuǎn)移連線上的條件元或邏輯表達(dá)式，按照上一節(jié)所述的方法生成考查狀態(tài)轉(zhuǎn)移邏輯判定的測(cè)試用例，用例同時(shí)考查轉(zhuǎn)移路徑和轉(zhuǎn)移行為的正確性。

4 算法結(jié)果驗(yàn)證

為驗(yàn)證上述基于狀態(tài)轉(zhuǎn)移圖的測(cè)試用例生成算法的合理性、全面性和完備性，以實(shí)際某箭上軟件的全周期時(shí)序控制為例，首先建立狀態(tài)轉(zhuǎn)移圖(見圖5)。

圖5 某型號(hào)軟件動(dòng)態(tài)特征狀態(tài)轉(zhuǎn)移圖

其次依據(jù)狀態(tài)轉(zhuǎn)移圖的描述，依據(jù)基路徑覆蓋準(zhǔn)則生成基于路徑分析的測(cè)試用例4個(gè)，即1)等待命令→尋找→準(zhǔn)備追趕→追趕→追上；2)等待命令→尋找→準(zhǔn)備追趕→追趕→追趕失敗→等待命令→尋找→準(zhǔn)備追趕→追趕→追上；3)等待命令→尋找→準(zhǔn)備追趕→尋找→準(zhǔn)備追趕→追趕→追上；4)等待命令→尋找→尋找失敗→等待命令→尋找→準(zhǔn)備追趕→追趕→追上。

再次依據(jù)轉(zhuǎn)移對(duì)覆蓋準(zhǔn)則對(duì)生成用例進(jìn)行擴(kuò)展，補(bǔ)充了1個(gè)用例，即等待命令→尋找→準(zhǔn)備追趕→尋找→尋找失敗→等待命令→尋找→準(zhǔn)備追趕→追趕→追上。

最后根據(jù)條件元覆蓋進(jìn)行轉(zhuǎn)移條件的定義和擴(kuò)充，即1)由“尋找→尋找失敗”需有3個(gè)考察轉(zhuǎn)移條件的用例；2)由“準(zhǔn)備追趕→尋找”需有2個(gè)考察轉(zhuǎn)移條件的用例；3)由“追趕→追趕失敗”需有2個(gè)考察轉(zhuǎn)移條件的用例。最終生成的測(cè)試用例如表2所示，實(shí)測(cè)生成時(shí)間為4 s。

表2 自動(dòng)生成用例算法生成的測(cè)試用例

其中，1、2、4、5、6、7、8均與同人工設(shè)計(jì)測(cè)試用例相同。試驗(yàn)結(jié)果表明自動(dòng)生成測(cè)試用例軟件可穩(wěn)定自動(dòng)生成，測(cè)試用例可完全覆蓋軟件動(dòng)態(tài)特征功能和性能需求，覆蓋性等于或高于人工設(shè)計(jì)的測(cè)試用例，且縮短用例生成時(shí)間至4 s。

5 結(jié)束語

本文提出了一種基于狀態(tài)轉(zhuǎn)移圖的測(cè)試用例自動(dòng)生成算法設(shè)計(jì)方法，以期實(shí)現(xiàn)時(shí)序控制功能測(cè)試用例自動(dòng)生成，提升測(cè)試效率和質(zhì)量，為軟件自動(dòng)化測(cè)試提供一定的借鑒。本文首先分析時(shí)序控制特性，其次選取狀態(tài)轉(zhuǎn)移圖來表征，自定義所需圖元屬性以及圖元關(guān)系、觸發(fā)條件全面性與一致性的約束條件從而保證模型合理性；再次采用基路徑覆蓋、轉(zhuǎn)移對(duì)覆蓋、條件元覆蓋3種覆蓋準(zhǔn)則相結(jié)合方式實(shí)現(xiàn)測(cè)試用例的自動(dòng)生成；最后以某箭上軟件全飛行周期時(shí)序控制為例，經(jīng)以具備較復(fù)雜邏輯的被測(cè)軟件測(cè)試用例生成結(jié)果表明，軟件可穩(wěn)定自動(dòng)生成覆蓋率較高的測(cè)試用例，測(cè)試用例可完全覆蓋軟件動(dòng)態(tài)特征功能和性能需求，從而驗(yàn)證了上述方法的有效性和穩(wěn)定性。相較與原人工設(shè)計(jì)用例方式，該方法還提升了測(cè)試用例生成效率。