汪冬瑾，張 舒

(1.宇航智能控制技術國家級重點實驗室，北京 100854；2.北京航天自動控制研究所，北京 100854)

0 引言

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

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

1 時序控制特性分析

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

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

1)軟件中的某一個時序，在軟件動態(tài)運行時一般不會重復進入兩次，已經(jīng)切換到其它時序，則通常不會再回來；

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

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

4)時序切換會伴隨特定的軟件動態(tài)行為和輸出；

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

通常對時序控制功能的考核點包括：

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

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

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

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

2 狀態(tài)轉移圖設計

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

2.1 圖元屬性定義

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

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

表1 WUL結果及解算時間統(tǒng)計

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

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

2.2 語法約束

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

2.2.1 基本圖元關系約束

狀態(tài)轉移圖圖圖元間應滿足以下幾項：

1)狀態(tài)轉移節(jié)點名稱唯一不可重復；

2)一個狀態(tài)必須且只能關聯(lián)一個狀態(tài)轉移節(jié)點；

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

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

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

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

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

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

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

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

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

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

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

3 測試用例自動生成算法

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

圖3 測試用例生成算法設計流程圖

3.1 基路徑覆蓋準則

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

3.2 轉移對覆蓋準則

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

3.3 路徑相關的狀態(tài)轉移條件判斷

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

圖4 路徑相關的狀態(tài)轉移判定

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

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

3.4 條件元覆蓋

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

4 算法結果驗證

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

圖5 某型號軟件動態(tài)特征狀態(tài)轉移圖

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

再次依據(jù)轉移對覆蓋準則對生成用例進行擴展，補充了1個用例，即等待命令→尋找→準備追趕→尋找→尋找失敗→等待命令→尋找→準備追趕→追趕→追上。

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

表2 自動生成用例算法生成的測試用例

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

5 結束語

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