基于狀態轉移圖的箭載軟件時序控制測試用例生成方法

汪冬瑾，張 舒

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

0 引言

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

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

1 時序控制特性分析

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

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

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

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

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

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

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

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

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

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

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

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

2 狀態轉移圖設計

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

2.1 圖元屬性定義

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

圖1 狀態轉移圖示意圖

表1 WUL結果及解算時間統計

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

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

2.2 語法約束

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

2.2.1 基本圖元關系約束

狀態轉移圖圖圖元間應滿足以下幾項：

1)狀態轉移節點名稱唯一不可重復；

2)一個狀態必須且只能關聯一個狀態轉移節點；

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

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

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

2.2.2 觸發條件全面性與一致性約束

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

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

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

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

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

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

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

3 測試用例自動生成算法

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

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

3.1 基路徑覆蓋準則

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

3.2 轉移對覆蓋準則

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

3.3 路徑相關的狀態轉移條件判斷

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

圖4 路徑相關的狀態轉移判定

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

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

3.4 條件元覆蓋

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

4 算法結果驗證

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

圖5 某型號軟件動態特征狀態轉移圖

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

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

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

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

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

5 結束語

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