基于状态图的航天器测试用例设计

（北京空间飞行器总体设计部，北京 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值设置转化为程控可调电阻的阻值设置。现阶段航天器电性能测试使用自动化测试平台，平台支持基于脚本的测试用例编辑方式，脚本编辑区包含航天器测试的函数库、当前型号的指令库和参数库，对于事件序列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