基于狀態圖的航天器測試用例設計

（北京空間飛行器總體設計部，北京 100094）

1 引言

航天器綜合測試作為驗證航天器設計的主要階段，在航天器研制過程中占據著重要地位，而測試用例設計的優劣，對綜合測試的效率起著決定性作用。目前，綜合測試的測試用例設計方法是：設計人員依據用戶需求、測試大綱、測試要求等文件，分析待測的功能，結合自身工程經驗，設計測試用例。這種基于文檔的設計方法耗時長，易出錯，測試用例的質量對測試人員的經驗依賴程度高。隨著航天器復雜度的不斷增大，目前的用例設計方法將難以適應未來航天器的測試需求，而基于模型的測試用例設計方法提供了一種由模型自動生成測試用例的新的思路，主要包括建模、覆蓋準則選取、生成算法設計、用例轉化4 個步驟。相比于基于文檔的用例設計方法，新設計方法要求首先建立一個被測系統行為模型，從而精確、無歧義地描述系統行為，并且模型的可執行性提供了仿真驗證環境，有利于在設計早期發現錯誤，減少后期隱患。同時，根據覆蓋準則對測試用例覆蓋率進行準確衡量，算法生成用例減少了用例設計時間，穩定了用例質量。

基于模型的測試有若干種，文獻［1］中對若干種模型進行了分類，包括Petri網、馬爾科夫鏈、狀態圖等，并就各類模型的適用系統類型進行了分析。由于航天器測試的原理是依靠遙測、遙控，對系統施加激勵信號，獲得其響應信號，通過對激勵信號和響應信號進行分析得出測試結論［2］，故本文采取適用于描述復雜反應系統的狀態圖模型。文獻［3-4］介紹了狀態圖理論以及Stateflow 平臺下的狀態圖建模、仿真方法。對基于狀態圖測試的用例生成問題，劉攀［5］等人在原有的覆蓋準則基礎上提出了最小測試成本遷移覆蓋算法，實現了無冗余測試序列的自動生成。然而，該算法不能找到具有歐拉路徑狀態圖的最簡遷移路徑，并且其生成的測試序列不是由初態開始，其算法效率及有效性均不理想。

本文首先介紹了狀態圖的建模理論，重點對測試用例生成算法進行研究，通過狀態圖的結構分類，提出了優化遷移覆蓋算法，以自主熱控功能測試為實例，驗證了新測試用例設計方法的可行性和優越性。

2 狀態圖建模簡介

狀態圖是一種針對復雜事件響應系統的形式化模型，可實現系統的行為描述和仿真，其形式化表述為四元組：

式中：S表示狀態集；T表示遷移集；V表示變量集；Ⅰ表示初始狀態格局，Ⅰ?S∪V。

狀態圖在有限狀態機（FSM）的基礎上進行拓展，增加了以下3方面的內容：

（1）層次深度，狀態內部允許嵌套多層子狀態，有利于多層次結構表述；

（2）并發性，當前活動狀態除了以“或”形式存在，還允許以“與”形式存在，即允許并行狀態；

第三種是風險分攤效應。新產品開發團隊樂于創新，并勇于承擔采用新技術和新觀點可能帶來的風險后果，可以縮短從新產品思路產生到商品化之間的時間間隔。

（3）廣播機制，并行狀態間的通信機制，通過遷移動作或狀態動作隱性觸發。

遷移可具體表示為

式中：s表示遷移的源狀態；s′表示遷移的目標狀態；e代表事件，如外部信號、其他遷移產生的信號等，未標注e時，根據c值決定遷移是否被采納；c是守衛參數，為布爾變量，c為真時，遷移被采納，未標注c時，默認其為真；a為遷移動作，描述狀態遷移后的結果，如狀態值的更新、新產生的事件等。遷移中有一類不需要任何遷移標注，為默認遷移，指向第一個被激活的狀態。

除了遷移動作外，還存在entry、exit、throughout三個動作。entry動作在每次遷移進入該狀態時被執行；exit動作在每次遷移離開該狀態時被執行，理想狀態下，這兩個動作與遷移同時發生，是瞬時動作。throughout動作是指每次該動作所屬的狀態被激活時，動作將在狀態中持續不斷地運行。此外，還包括一類特殊的圖形對象，它只能用于具有層次狀態的內部，能夠保存父層狀態退出活動狀態時當前活動的子狀態，當父狀態再次激活時，歷史節點能夠恢復記錄的子狀態。

3 測試用例生成

測試用例的生成，即從狀態圖中選擇滿足給定模型覆蓋準則的有限輸入信號（事件、參數等）序列的過程［6］，輸入信號序列選擇過程是算法執行的，狀態圖的覆蓋準則一般為結構覆蓋，故文中采取有向圖遍歷的思想進行算法設計。本節探討的測試用例是針對狀態圖模型的抽象用例。

3.1 覆蓋準則選取

模型覆蓋準則是測試用例生成的條件標準，某一覆蓋準則的覆蓋率可以定量衡量測試的充分程度，從而幫助測試人員作出終止測試的判斷，覆蓋率的表達公式［7］如下：

式中：C為覆蓋率；fr為已測試執行的特定特征數目；f為被測試系統的特定特征總數，特定特征是指模型中特定組成元素，不同元素對應不同覆蓋準則，對于狀態圖，由于其具有圖像化的特點，于是提出了以下兩種基本的圖形覆蓋準則［8］。

（1）狀態覆蓋：測試用例集至少覆蓋狀態圖中所有的狀態一次。

（2）遷移覆蓋：測試用例集至少覆蓋狀態圖中所有的遷移一次。

遷移覆蓋的約束條件要強于狀態覆蓋，滿足遷移覆蓋也滿足了狀態覆蓋。由于狀態圖輸入信號為事件，而事件直接驅動遷移的執行，因此文中采取遷移覆蓋準則。該準則下，算法生成一組遷移序列T＝＜t1，t2…tn＞，進而得出一組事件序列E＝＜e1，e2…en＞，事件序列就是狀態圖測試用例?？紤]到測試用例的有效性，將生成的遷移序列限定為從初始狀態出發，并稱之為遷移路徑。

3.2 算法設計

測試用例生成算法，通過有向圖遍歷實現狀態圖中遷移路徑搜索。算法設計時，忽略狀態圖中的遷移標注，使遷移為邊（E），忽略狀態內動作，使狀態為頂點（V），將同一層次的狀態邏輯關系轉化為有向圖，并用鄰接矩陣G＝［VE］表示［9］，為減少用例冗余，文中補充了兩個算法指標：①最簡性，即單個遷移路徑長度盡可能大；②非重復性，即不同遷移路徑應避免非必要重復遷移覆蓋。按照有向圖的結構特點，可以將有向圖分為以下3類：

（1）強連通圖，有向圖內任意的兩個頂點是相互可達的。當回路中所有頂點的出度和入度相等，或圖中僅有兩個點是奇度時，有向圖為歐拉圖，即存在一條路徑可以一次且僅一次遍歷所有邊。

（2）樹形有向圖，有向圖是連通的但不存在回路。

（3）混合型，即強連通分支（SCC）數介于1與頂點數之間。此類圖的遍歷需要先求出SCC，將SCC縮減為單個頂點，將原圖轉化為無回路樹形有向圖G′，先分別求各SCC內的遷移路徑Pi，再求G′的遷移路徑Ptree，再將Ptree和Pi整合，生成完整的遷移路徑Pc。

歐拉圖的遍歷問題已形成許多成熟的算法，文中的Euler算法采用套圈法［9］，在此不做贅述。對一般強連通圖以及樹形有向圖的遍歷問題，本文中以最簡性和非重復性兩個算法指標為約束條件，設計了相關算法TransCov。首先考慮算法指標①，采用無回溯深度優先搜索（DFS），即對最新到達的頂點，若還存在以此為頂點而未被探測的邊，則沿此邊繼續探測下去，直至該頂點為葉節點，返回初始頂點重新搜索，循環搜索直到所有的邊均被遍歷。在搜索時會重復遍歷某些邊，為滿足算法指標②，DFS過程中優先探索未訪問過的頂點，當所有頂點均被訪問后，再優先遍歷訪問次數少的邊。

算法運行結果表明，上述算法設計仍存在缺陷：對于自循環邊，算法會陷入死循環；遍歷過程中容易提早返回初始頂點，導致多次重復后才能遍歷至較“深”的邊；對到達葉節點的邊重復遍歷。故對原算法采取以下方法改進：①自循環邊遍歷一次后刪除該邊；②抑制搜索返回初始頂點的邊，遍歷時該類邊的選擇優先級最低，若選擇了此類邊，遍歷后刪除；③對到達葉節點的邊，若已遍歷過，則刪除該邊，刪除后若產生新的葉節點，則繼續刪除到達新葉節點，并已遍歷過的邊。TransCov算法偽代碼見圖1。

圖1 TransCov算法Fig.1 Algorithms of TransCov

在此基礎上，設計優化路徑搜索算法（IPSA），算法流程如圖2所示。

圖2 IPSA 流程圖Fig.2 IPSA flow charts

4 用例設計舉例

以某航天器綜合電子分系統自主熱控功能的測試為例，通過Simulink／Stateflow（SL／SF）軟件［10］實現狀態圖建模，Stateflow 是內嵌于Simulink 環境下的基于狀態圖理論的建模平臺，平臺添加了遷移標簽新元素：條件遷移動作，條件滿足時該動作立即執行，而不需整個遷移通路有效，表達式為｛ConditionAct｝，同時，平臺支持流程圖建模，即圖中不包含任何狀態，僅有節點以及遷移，適合條件判斷邏輯的表達。建立的SL／SF模型如圖3和 圖4所示，圖中對所有非默認遷移進行了標注。

模型實現以下功能需求：①中央管理單元（CMU）首次加電時，須由遙控指令激活熱控軟件，在地面系統測試時，可以發軟件禁止指令退出。但衛星在軌飛行時禁止發出該指令，計算機切機或重啟后，自動激活熱控軟件，切機、重啟后各回路狀態與操作前一致；②加熱回路包括自控“使能”和“禁止”狀態，以指令實現切換，缺省配置中加熱回路為使能；③回路自控禁止時，通過遙控指令控制加熱器開關；④回路自控使能時，通過對熱敏電阻溫度連續3次采樣與閾值的比較進行溫控，當三次采樣均超過閾值，則自動實現加熱器的開關控制，當溫度在閾值范圍內時，則保持加熱器狀態。正常情況下僅主份加熱器工作，當主份加熱器損壞，備份自動接替工作，備份的控溫閾值下限低于主份。

圖3中，各層次狀態按照需求自頂向下劃分，狀態間的事件流代表狀態間切換指令和相應操作，圖4為狀態“判斷1”和狀態“判斷2”內的流程圖，表示溫度自動控制邏輯。

目前，對加熱器遙控功能和自控功能（TH1、TH2）檢查的測試用例共發送12 條指令。其中自控功能檢查，每次將加熱回路切換至禁止狀態，設置熱敏電阻等效器溫度，使其高于或低于閾值，再切換回使能狀態，查看加熱器開關狀態是否做出相應變化，由模型仿真結果可知，現有測試用例單次測試狀態下（忽略切機遷移t20），主備份加熱回路測試重復覆蓋遷移t9、t10各3次，共產生6條冗余遷移，并且未能覆蓋熱敏電阻等效器溫度在閾值內的情況（t21、t25）以及備份自動接替主份的工作情況（t24），遷移覆蓋率僅為88.46%，測試效率較低。

圖3 Thermal control模塊框圖Fig.3 Block diagrams of therrmal control

圖4 溫控邏輯流程圖模型Fig.4 Flow charts model of temperature control logic

采用3.2節中的算法進行用例設計，得到圖3的遷移路徑為T＝＜t1，t3，t11，t12，t13，t14，t19，t15，t16，t17，t18，t10，t7，t8，t5，t6，t20，t9，t4，t2＞由遷移路徑得到對應事件序列E。其中，t14、t15、t19的觸發事件為圖4中的遷移條件動作，將條件動作所在的遷移與其動作觸發的遷移進行等價替換，得到新的遷移序T′＝＜t1，t3，t11，t12，t13，t21／t22／t23，t24，t25／t26／t27，t16，t17，t18，t10，t7，t8，t5，t6，t20，t9，t4，t2＞T′中覆蓋t21、t22、t23、t24需要在主份狀態內進行4 次循環；同理，覆蓋t25、t26、t27需要在備份狀態內進行3 次循環。為覆蓋所有遷移，對應參數設置需滿足如下條件：狀態循環1：t1＜tp＜t2；狀態循環2：tp＞t2；狀態循環3：tp＜t1；狀態循環4：tp持續下降，t3＜tp＜t1；狀態循環5：tp＜t3；狀態循環6：tp＞t2。

上述參數中，tp代表熱敏電阻溫度，［t1，t2］、［t3，t2］分別為主備份熱敏電阻控溫閾值TH1、TH2。按照狀態循環條件設置tp范圍，使得模型運行到自控狀態內，自動進行6次循環，而不必退出自控狀態，并由T′得出事件序列E′，tp和E′即為所建SL／SF模型的測試用例。

將新設計的測試用例輸入SL／SF 模型中仿真，并就測試結果與原始測試用例對比，如表1所示，可見新測試用例在規模、冗余約簡、遷移覆蓋率3個方面都有了明顯改善。

表1 原始用例與新測試用例對比表Table 1 Contrast between original test case and new test case

SL／SF模型的測試用例是抽象測試用例，還需要對其進行工程轉化。實際測試中，運用熱敏電阻等效器代替真實的熱敏電阻，抽象用例中的tp值設置轉化為程控可調電阻的阻值設置?，F階段航天器電性能測試使用自動化測試平臺，平臺支持基于腳本的測試用例編輯方式，腳本編輯區包含航天器測試的函數庫、當前型號的指令庫和參數庫，對于事件序列E′可轉化為平臺腳本代碼，編寫時在函數庫、指令庫、參數庫中選擇與抽象信號對應的實際信號，形成工程可用測試用例。

5 結束語

本文提出了一種基于狀態圖的航天器測試用例設計方法，相較于基于文檔的用例設計方法，其用被測系統的形式化模型替代了測試大綱等文件，有利于在研制早期發現錯誤，并且設計的用例算法是可控的，易于優化，可適應未來航天需求。仿真測試對比結果顯示，運用新方法生成的用例的測試效率有了明顯改善。

（References）

［1］Utting M，Legeard B.Practical model-based testing：a tools approach［M］.San Francisco：Morgan Kaufmann Publications，Elsevier Inc.，2007

［2］王慶成.航天器電測技術［M］.北京：中國科學技術出版社，2005 Wang Qingcheng.Electrical test technology of spacecraft［M］.Beijing：China Science and Technology Press，2005（in Chinese）

［3］Harel D.Statecharts：A visual formalism for complex systems［J］.Science of Computer Programming，1987，8：231-274

［4］張威.Stateflow 邏輯系統建模［M］.西安：西安電子科技大學出版社，2007 Zhang Wei.Stateflow logical system modeling［M］.Xi’an：University of Xi’an Electronic Science and Technol-ogy Press，2007（in Chinese）

［5］劉攀，繆淮扣，曾紅衛，等.確定性有限狀態機的最小測試成本遷移覆蓋準則［J］.軟件學報，2011，22（7）：1457-1474 Liu Pan，Miu Huaikou，Zeng Hongwei，et al.DFSMbased minimum test cost transition coverage criterion［J］.Journal of Software，2011，22（7）：1457-1474（in Chinese）

［6］繆淮扣，陳圣波，曾紅衛.基于模型的Web 應用測試［J］.計算機學報，2011，34（6）：1012-1026 Miao Huaikou，Chen Shengbo，Zeng Hongwei.Modelbased testing for Web applications［J］.Chinese Journal of Computers，2011，34（6）：1012-1026（in Chinese）

［7］張瑤，白曉穎，張任偉，等.一種基于模型的測試充分性評估方法［J］.計算機科學，2013，40（2）：153-158 Zhang Yao，Bai Xiaoying，Zhang Renwei，et al.Modelbased approach for software test adequacy analysis［J］.Computer Science，2013，40（2）：153-158（in Chinese）

［8］劉攀，繆淮扣，曾紅衛，等.基于FSM 的測試理論、方法及評估［J］.計算機學報，2011，34（6）：966-984 Liu Pan，Miao Huaikou，Zeng Hongwei，et al.FSMBased testing：theory，method and evaluation［J］.Chinese Journal of Computers，2011，34（6）：966-984（in Chinese）

［9］Thomas H，Cormen E.算法導論［M］.潘金貴，顧鐵成，李成法，譯.北京：機械工業出版社，2006 Thomas H，Cormen E.Introduction to algorithms［M］.Pan Jingui，Gu Tiecheng，Li Chengfa，translated.Beijing：China Machine Press，2006（in Chinese）

［10］Jack Little.Documentation for MathWorks products，R2009a［EB／OL］.［2014-06-13］.http：／／www.mathworks.com