基于狀態(tài)圖的航天器測試用例設(shè)計

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

1 引言

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

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

本文首先介紹了狀態(tài)圖的建模理論，重點(diǎn)對測試用例生成算法進(jìn)行研究，通過狀態(tài)圖的結(jié)構(gòu)分類，提出了優(yōu)化遷移覆蓋算法，以自主熱控功能測試為實(shí)例，驗(yàn)證了新測試用例設(shè)計方法的可行性和優(yōu)越性。

2 狀態(tài)圖建模簡介

狀態(tài)圖是一種針對復(fù)雜事件響應(yīng)系統(tǒng)的形式化模型，可實(shí)現(xiàn)系統(tǒng)的行為描述和仿真，其形式化表述為四元組：

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

狀態(tài)圖在有限狀態(tài)機(jī)（FSM）的基礎(chǔ)上進(jìn)行拓展，增加了以下3方面的內(nèi)容：

（1）層次深度，狀態(tài)內(nèi)部允許嵌套多層子狀態(tài)，有利于多層次結(jié)構(gòu)表述；

（2）并發(fā)性，當(dāng)前活動狀態(tài)除了以“或”形式存在，還允許以“與”形式存在，即允許并行狀態(tài)；

第三種是風(fēng)險分?jǐn)傂?yīng)。新產(chǎn)品開發(fā)團(tuán)隊(duì)樂于創(chuàng)新，并勇于承擔(dān)采用新技術(shù)和新觀點(diǎn)可能帶來的風(fēng)險后果，可以縮短從新產(chǎn)品思路產(chǎn)生到商品化之間的時間間隔。

（3）廣播機(jī)制，并行狀態(tài)間的通信機(jī)制，通過遷移動作或狀態(tài)動作隱性觸發(fā)。

遷移可具體表示為

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

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

3 測試用例生成

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

3.1 覆蓋準(zhǔn)則選取

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

式中：C為覆蓋率；fr為已測試執(zhí)行的特定特征數(shù)目；f為被測試系統(tǒng)的特定特征總數(shù)，特定特征是指模型中特定組成元素，不同元素對應(yīng)不同覆蓋準(zhǔn)則，對于狀態(tài)圖，由于其具有圖像化的特點(diǎn)，于是提出了以下兩種基本的圖形覆蓋準(zhǔn)則［8］。

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

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

遷移覆蓋的約束條件要強(qiáng)于狀態(tài)覆蓋，滿足遷移覆蓋也滿足了狀態(tài)覆蓋。由于狀態(tài)圖輸入信號為事件，而事件直接驅(qū)動遷移的執(zhí)行，因此文中采取遷移覆蓋準(zhǔn)則。該準(zhǔn)則下，算法生成一組遷移序列T＝＜t1，t2…tn＞，進(jìn)而得出一組事件序列E＝＜e1，e2…en＞，事件序列就是狀態(tài)圖測試用例。考慮到測試用例的有效性，將生成的遷移序列限定為從初始狀態(tài)出發(fā)，并稱之為遷移路徑。

3.2 算法設(shè)計

測試用例生成算法，通過有向圖遍歷實(shí)現(xiàn)狀態(tài)圖中遷移路徑搜索。算法設(shè)計時，忽略狀態(tài)圖中的遷移標(biāo)注，使遷移為邊（E），忽略狀態(tài)內(nèi)動作，使?fàn)顟B(tài)為頂點(diǎn)（V），將同一層次的狀態(tài)邏輯關(guān)系轉(zhuǎn)化為有向圖，并用鄰接矩陣G＝［VE］表示［9］，為減少用例冗余，文中補(bǔ)充了兩個算法指標(biāo)：①最簡性，即單個遷移路徑長度盡可能大；②非重復(fù)性，即不同遷移路徑應(yīng)避免非必要重復(fù)遷移覆蓋。按照有向圖的結(jié)構(gòu)特點(diǎn)，可以將有向圖分為以下3類：

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

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

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

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

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

圖1 TransCov算法Fig.1 Algorithms of TransCov

在此基礎(chǔ)上，設(shè)計優(yōu)化路徑搜索算法（IPSA），算法流程如圖2所示。

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

4 用例設(shè)計舉例

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

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

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

目前，對加熱器遙控功能和自控功能（TH1、TH2）檢查的測試用例共發(fā)送12 條指令。其中自控功能檢查，每次將加熱回路切換至禁止?fàn)顟B(tài)，設(shè)置熱敏電阻等效器溫度，使其高于或低于閾值，再切換回使能狀態(tài)，查看加熱器開關(guān)狀態(tài)是否做出相應(yīng)變化，由模型仿真結(jié)果可知，現(xiàn)有測試用例單次測試狀態(tài)下（忽略切機(jī)遷移t20），主備份加熱回路測試重復(fù)覆蓋遷移t9、t10各3次，共產(chǎn)生6條冗余遷移，并且未能覆蓋熱敏電阻等效器溫度在閾值內(nèi)的情況（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節(jié)中的算法進(jìn)行用例設(shè)計，得到圖3的遷移路徑為T＝＜t1，t3，t11，t12，t13，t14，t19，t15，t16，t17，t18，t10，t7，t8，t5，t6，t20，t9，t4，t2＞由遷移路徑得到對應(yīng)事件序列E。其中，t14、t15、t19的觸發(fā)事件為圖4中的遷移條件動作，將條件動作所在的遷移與其動作觸發(fā)的遷移進(jìn)行等價替換，得到新的遷移序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需要在主份狀態(tài)內(nèi)進(jìn)行4 次循環(huán)；同理，覆蓋t25、t26、t27需要在備份狀態(tài)內(nèi)進(jìn)行3 次循環(huán)。為覆蓋所有遷移，對應(yīng)參數(shù)設(shè)置需滿足如下條件：狀態(tài)循環(huán)1：t1＜tp＜t2；狀態(tài)循環(huán)2：tp＞t2；狀態(tài)循環(huán)3：tp＜t1；狀態(tài)循環(huán)4：tp持續(xù)下降，t3＜tp＜t1；狀態(tài)循環(huán)5：tp＜t3；狀態(tài)循環(huán)6：tp＞t2。

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

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

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

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

5 結(jié)束語

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

（References）

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

［2］王慶成.航天器電測技術(shù)［M］.北京：中國科學(xué)技術(shù)出版社，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 邏輯系統(tǒng)建模［M］.西安：西安電子科技大學(xué)出版社，2007 Zhang Wei.Stateflow logical system modeling［M］.Xi’an：University of Xi’an Electronic Science and Technol-ogy Press，2007（in Chinese）

［5］劉攀，繆淮扣，曾紅衛(wèi)，等.確定性有限狀態(tài)機(jī)的最小測試成本遷移覆蓋準(zhǔn)則［J］.軟件學(xué)報，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］繆淮扣，陳圣波，曾紅衛(wèi).基于模型的Web 應(yīng)用測試［J］.計算機(jī)學(xué)報，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］.計算機(jī)科學(xué)，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］劉攀，繆淮扣，曾紅衛(wèi)，等.基于FSM 的測試?yán)碚摗⒎椒霸u估［J］.計算機(jī)學(xué)報，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.算法導(dǎo)論［M］.潘金貴，顧鐵成，李成法，譯.北京：機(jī)械工業(yè)出版社，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