装备软件接口测试自动化研究＊

孙 宁 刘 丹

（1.海军装备研究院 北京 100161）（2.中电科技（北京）有限公司 北京 100083）

1 引言

现代战争中，装备战斗力的70%是由软件实现的。美军F22战机的软件已经超过2500万行源代码，福特级航母和朱姆沃尔特级驱逐舰及新型攻击型核潜艇的软件远远超过5000万行源代码。如此庞大的源代码要是没有严格的检测措施，可想而知出错率是相当高的。同样，随着各类信息化装备不断装备部队，我军装备软件正呈现出多样化、复杂化和智能化等特点，其质量直接影响着军事指挥和武器装备作战效能的发挥［1］。

装备软件测试主要包括功能测试、接口测试、性能测试、强度测试、余量测试等。接口测试在装备软件测试中占重要地位。以舰艇指控系统为例，与外部通过以太网交联的设备包括武器、传感器、通信设备及其他系统，达三十几种外部接口，接口实现的正确与否直接影响了装备指挥控制流程和各系统之间的协调一致。本文的接口测试特指的是接口测试，接口测试是验证接口数据的正确性和协调性，也就是验证网络中的报文数据满足接口协议规定的内容。

本文针对接口数据各字段间存在的控制或数据依赖关系，提出了一种利用符号执行约简测试用例空间的算法。给出了基于控制流图的程序参数依赖关系定义；在此基础上，根据输入参数变量在程序执行时的信息流，提出了一种参数依赖关系的动态分析算法。

本文根据上述方案设计实现了一个接口自动测试工具，通过利用符号执行约简测试用例空间的算法设计出输入域数据，采用XML语言实现数据的自动化描述和比对。在实际应用中，提高了接口测试数据设计的完备性［9］，提高了装备软件接口测试的工作效率和质量。

2 接口测试数据的设计

接口测试除了对数据包头、结束位、校验位、标志位的验证，重点内容是对各个字段的验证。在测试数据设计时，往往采用等价类划分的方法对每个字段选取有限集合，然后对所有字段进行穷举组合的方式，这种方式对少量字段的组合似乎可行，但是对复杂字段的测试数据设计来说往往是灾难性的，其数据量是设计和实施都无法接受的。以某导航信息接口为例，如果按照等价类划分后穷举组合的方法，对一个接口的测试用例数据共有6×1023组，对一型装备来说类似的接口有300个左右的规模，可见采用有效等价类划分后穷举组合和方式其成本和进度是装备软件测试无法接受的，但是测试质量得不到保证同样是无法接受的。如何使测试设计和执行在时间和成本资源的约束下成为可能，而且使测试质量得到充分保证是困扰和制约软件测试的一个亟待解决的问题［2，5］，装备软件测试对接口测试的要求更加严格，时间和成本制约更为明显。

接口数据各个字段之间并不是完全独立的，有些字段之间存在着较强的逻辑关系，而有些字段之间没有关系。通过对一些程序源代码以及可信软件栈（Tcg Software Stack，TSS）［3，6］进行深入分析，发现测试函数的部分参数变量相对独立，不存在与其他变量的依赖关系。因此，可利用符号执行的方法将独立的变量分离出来，达到将参数空间动态分区的效果，即其相应的取值空间因相互组合而成的指数关系会化简为线性关系。这一方面降低了测试用例的取值规模，额外的测试用例无法检测更多的程序行为，另一方面不会因此降低测试的原有检错能力。

基于代码的分析和测试都需要对代码进行抽象，进而建立一种中间模型，控制流图（Control Flow Graph，CFG）是一种常用的中间模型［10］。

定义1（控制流图） 控制流图是以基本块（basic block）为节点的有向图。所谓基本块，是程序中具有唯一入口和唯一出口的语句序列，其中不包含条件转移语句。基本块中语句在程序执行过程中要么全都执行，要么全都不执行。形式化地说，控制流图是一个有向图G＝〈X，L，op，E〉。其中，X为变量集合，子集x0⊂x为输入向量；L代表程序基本块节点的集合，l0∈L为特定的开始结点；函数op表示l0∈L中块节点的基本操作｛halt｜abort｜x：＝e｜if（x）thenl′elsel″｝，其中，halt为程序正常中止，abort为程序错误退出，赋值语句x∶＝e，x∈X且e是X上的运算表达式，条件语句if（x）thenl′elsel″，x∈X且l′，l″∈L；E⊂L＊L表示两个节点之间的转移，N（l）为唯一的邻居节点。

控制流图是所有依据程序推演依赖关系的基础，形象地展示了信息是如何沿着语句流进行传播的。为影响计算结果，程序的每个语句都必须（至少潜在地）以某种方式影响信息流，因此变量间可能存在某种控制或数据上的依赖关系。

定义2（后支配关系） 对于控制流图上的两个节点l，l′∈L，如果每条从l到lhalt的路径上都包含l′，则l′是l的后支配节点。当满足以下条件时，l′是l的直接后支配节点，记做l′＝idom（l）：1）l′≠l；2）l′是l的后支配节点；3）对于l的每个后支配节点l″，同时也是l′的后支配节点。控制流图上每个节点都有唯一的直接后支配节点［4］，因此函数idom（l）对于每个l≠lhalt的节点是良构的。

定义3（前支配关系） 对于控制流图上的两个节点l，l′∈L，如果每条从lroot到l的路径上都包含l′，则l′是l的前支配节点。当满足以下条件时，l′是l的直接前支配节点：1）l′≠l；2）l′是l的前支配节点；3）对于l的每个前支配节点l″，同时也是的前支配节点。

定义4（控制依赖） 如果控制流图上存在某条执行路径l0…l…l′，并且idom（l′）并不存在于l′与l之间的路径上，则认为l控制依赖于l′。

定义5（节点间数据依赖） 如果满足以下条件，则认为节点B数据依赖于节点A：

1）节点A写入某个变量V（或者更一般地说，写入部分程序状态），随后该变量V被节点B读取；

2）在控制流图上至少有一条从A至B的路径，在该路径上V没有被其他任何节点所更新。

定义6（输入变量间的数据依赖） 给定表达式e和程序的输入变量集合X，Use（e）用于表示e中包含输入变量的集合，对于两个变量x，y∈X，如果存在一条到节点l的路径，op（l）：x＝e且y∈Use（e），则认为变量x数据依赖于变量y。

利用符号执行的方法分析输入参数变量间的依赖关系，并对参数空间进行划分的基本思想是［7］：1）将程序的输入参数空间按所有变量相互独立的假设进行初始分区；2）在使用符号变量依次代替各参数变量执行的过程中，如果发现来自于不同分区的输入变量之间存在依赖关系，则将相应的分区合并；3）经过反复合并后，最终形成的分区之间是相互独立的，不同分区的参数变量之间不存在信息流的流动。

为此，首先就输入参数空间的分区提出以下定义：

定义7（分区集） 输入变量集合X的分区集H（X）是集合X的若干不相交子集的集合X＝∪Y∈H（x）Y；分区集中的每个子集称为该分区集的块（block）；对于变量x∈X，H（X）［x］用于表示包含变量x的块。

定义8（分区合并） 给定1个分区集H（X）和该分区集中若干块的子集合Y⊆H（X），在子集合Y合并为1个块后，分区集H（X）为Merge（H（X），Y）＝（H（X）－Y）∪｛∪a∈Ya｝

本文提出算法用于分析输入参数间的依赖关系，从而对输入空间进行划分［8］，输入参数依赖关系分析算法如下：

算法中的输入为程序P、输入参数集合X的初始分区H0（X）。算法中的数据结构包括：局部变量Hcur记录由于控制或数据的依赖关系而更新的“现行”输入分区，初始值为H0（X）；局部变量Hold，用于检查在一轮执行中是否对输入分区进行了修改，初始值为空集。映射关系（flow map）是用于存储依赖关系的关键数据结构，将每一个输入变量x∈X映射到当前输入分区块集上flow：X→2H。形象地说，flow（x）表示所有影响（数据或控制依赖）变量x的输入块的集合。

在每一轮循环中，调用Generate函数针对现行分区中的每块I（I∈Hcur）进行测试。将块I中的变量作为符号变量，而I之外分区的变量取随机的初始值，将两个部分的合并作为程序的输入。

算法中的主循环Generate函数的主要功能是：使用符号执行的方法在遍历程序内部的可执行路径的过程中，收集动态依赖信息，并由此更新输入映射关系flow（x）。最终，该映射关系用于合并Hcur中的块，从而得到一个新的分区。新合并后的分区是初始分区｛Hcur［x］｝的粗糙分区。当某一轮输入分区不再发生变化时，循环停止Generate函数的输入为程序P、输入分区H、映射关系flow、分区中的块I、I之外分区的初始输入input和一个路径索引last，Generate函数用于跟踪最近一次访问的程序分支。Generate函数采用深度优先的遍历算法，将通路条件中的约束条件从后向前依次求反，选择新的可执行路径。

通过应用该算法，接口测试数据量大大降低，共计算出6万条测试数据组合，达到了将指数关系化简为线性关系的显著效果，且用例的规模是可以接受的，可以工程化实现的，但是付出的代价是依赖于对源代码的进行数据流分析。

3 结语

实验结果表明：该方法在约简测试用例空间上具有较强的实用性，同时不会降低测试原有的检错能力，通过自动化的筛选和比较大大提高了接口测试的效率和质量。

［1］李晓莉，龙翔，刘超，等.军用软件测试现状及对策［J］.装甲兵工程学院学报，2008，22（5）：66－69.

［2］MYERS G J.The art of software testing［M］.New Jersey：John Wiley ＆Sons，1979：12－15.

［3］Trusted Computing Group.TCG software stack（TSS）specification，version 1.2［EB／OL］. （2005－06－10）［2009－09－30］.https：www.trustedcomputinggroup.org.

［4］MUCHN ICK S.Advanced compiler design and implementation［M］.San Francisco：Morgan Kaufmann，1997：256－263.

［5］Berndt D J，Fisher J，Johnson L，et al.Breeding software test case with genetic algorithms［C］／／Proceedings of the 36th Hawaii international conference on system science（HICSS－36），Hawaii，January 2003.

［6］Berndt D J，Watkins A.Investigating the performance of genetic algorithm－based software test case generation［C］／／Proceedings of the 8th IEEE international symposium on high assurance systems engineering（HASE'04），University of South Florida；march 25－26，2004：261－2.

［7］Wegener J，Baresel A，Sthamer H.Suitability of evolutionary algorithms for evolutionary testing［C］／／Proceedings of the 26th annual international computer software and application conference，Oxford，England，August 26－29，2002.

［8］Hermadi I.Genetic algorithm based test data generator［D］.Saudi Arabia：Department of Information and Computer science，King Fahd University of Petroleum and Minerals，2004.

［9］Hamlet D.Foundation of software testing：dependability theory［D］.Protland：Portland University，1994.

［10］Edvardsson J.A Survey on automatic test data generation［C］／／proceedings of 2nd conference on computer science and engineering，Linkoping：ESCEL；October 1999.P.21-8.