基于节点层网络关键等级的嵌入式软件集成测试序列生成方法

李腾飞 石磊

摘要：增量法是应用于集成测试的方法，合适的增量集成策略能够降低测试成本、保障测试的充分性、提高测试效率。针对目前嵌入式软件集成测试增量方法不明确、对于函数调用关系验证不充分等问题，通过参考集成测试相关国家标准并结合嵌入式软件的特点进行深入分析，提出一种新的集成测试序列生成方法。该方法从集成测试函数调用关系的充分性入手，按照以“层间集成”为主、“层内关键系数集成”为辅的设计思路，将嵌入式软件中的函数基于节点层和关键系数以集成的先后顺序划分，得到经粗调和微调后的增量集成序列。该方法能简单、高效地解决集成测试增量集成问题，具备工程实践应用意义。

关键词：嵌入式软件;软件集成测试;增量法;关键系数;节点层网络

An Embedded Software Integration Test Order Method

Based on the Node Layer Net Criticality

LI Teng fei，SHI Lei

（Luoyang Photoelectric Technology Development Center， Luoyang 471000，China）

Abstract：Incremental Integration strategy is applied to integration testing and appropriate incremental Integration strategy could be used to reduce high cost， ensure sufficiency and increase efficiency to a large extent. Aimed to solving problems of insufficiency of function calling testing and unclear of increasing methods， a novel method of node layer net for generating integration testing sequence by deeply analyzing National Military Standard and characteristic of embedded software is presented. By combining outer layer and inner layer factors to generate integration testing sequence， the sufficiency of interface testing between different function could be guaranteed. In conclusion， the method can solve the problems of incremental integration in integration test simply and efficiently， and has engineering practice and application significance.

Key Words：embedded software; software integration testing;increasing method;critical coefficient;node layer net

0 引言

嵌入式软件作为软件应用领域的重要分支，在日新月异的科技发展中也发生着快速变革。软件复杂度的提高、功能多样性的增强，以及接口调用丰富性的完善对传统测试提出了更高的技术要求。集成测试采用增量法对函数调用关系进行验证，保障软件产品质量[1 2]。

近年来，许多增量集成测试序列生成方法被提出并应用于工程化实践，取得了较好的应用效果[3 5]。基于复杂网络的类间集成测试序列生成方法将类抽象成节点，建立复杂网路模型，解决了面向对象的集成测试序列生成问题[6 7]。嵌入式软件功能路径测试用例自动生成方法结合了嵌入式软件的功能特点，使集成测试用例生成更加便捷、高效[8]。基于软件节点重要性的集成测试序列生成方法引进了软件节点重要程度的评估方案，保障测试桩复杂度的约束前提，让重要节点优先集成测试[9]。

函数内外关系交错是提升集成复杂度的重要因素。復杂性高的函数引入错误的概率相对较大，在进行测试时需要重点关注[10]。对复杂程度高、出错概率大和发生错误后传播范围广的函数优先测试，能有效规避错误风险。

本文提出基于节点层网络关键等级的嵌入式软件集成测试序列生成方法。该方法充分考虑函数接口调用对软件集成测试的影响程度，采用自上而下的集成策略，让复杂程度高、关键性强的函数优先被集成、验证。在相同的测试条件下该方法既保障了集成测试效率，又提高了集成测试的充分性、保证了嵌入式软件产品质量。

1 方法建模

1.1 基于节点层网络的层间集成模型

嵌入式软件调用关系分为静态和动态两种类型。动态调用关系依据代码动态执行路径获取，路径随着初始化变量条件的变化而产生较大差别。静态调用不实际执行代码，仅仅依赖对代码中非系统函数的静态扫描实现对函数静态调用关系的全覆盖。通常静态调用关系图能够涵盖所有的动态调用，故静态集成测试方案也将适用于动态集成。本节将基于静态函数调用关系网络，建立该软件的节点层模型[11 14]。

定义1 静态调用图：以main函数作为开始节点，静态扫描该节点函数代码中所有非系统函数，将扫描结果作为静态调用图第二层。依次类推进行迭代，直至将所有代码文件扫描完毕后形成函数静态调用关系层次图。

定义2 节点层：函数静态调用关系网络模型中的所有叶子节点同属于一个节点层。

定义3 关键性等级：用以表征网络中层和节点的关键程度（重要程度），通常分为层间关键性等级和层内关键性等级，层间的关键性等级高于层内关键性等级。网络中所有关键性等级之和构成了整个网络的关键性等级。网络节点属性和结构固定，关键性将保持不变。

定理1 同一节点层的节点在静态调用图中有相同的层间关键性等级。

证明： 对于多层网络构建节点层模型，节点集合N={N 1，N 2，N 3，…，N M} ，叶子节点集合Y={Y 1，Y 2，Y 3，…，Y P}，满足YN且P≤M。Y i∈Y可以构建两层网络N-{Y i}→{Y i}，使N-{Y i}和Y i具有不同的关键性等级，即K N-{Y i}≠K {Y i} 且满足K N-{Y i}>K {Y i}，K N=K N-{Y i}+K Y i。当M1时，K N-{Y i}K Y i可知K N=K N-{Y i}，进而得到K N-{Y i}=K N-{Y j}，K i=K j，（0≤i≠j≤P）。

静态调用图和节点层网络在分层上存在较大差别。静态调用图的同层节点基于自上而下的调用关系得到，而节点层网络模型是通过自下而上的方式得到的，因同一节点层的节点在静态调用图中有相同的层间关键性等级，从而使函数层间模型划分更加合理。

基于静态调用图可以得到节点层网络模型。从静态调用图中迭代删除所有叶子节点，直至所有函数节点被覆盖完毕。不同层的网络节点具备不同的关键性等级，从main函数开始的第一层计算，节点层的关键性等级随着网络层的递增而降低。为了保障层间关键性等级的绝对主导，要求节点层间的关键性大于该层内任意节点的关键性。用 L i（i=1，2，…，N）表征不同层的关键性等级，F ij表征第i层第j个函数的节点关键性系数。通常要求L i ≥max （F ij）。具体节点层划分算法流程如图1所示。

1.2 基于节点关键等级的层内集成模型

《GJBZ102A-2012军用软件安全性设计指南》对嵌入式软件安全性设计进行了说明，并对影响嵌入式软件代码品质的因素进行了列举和解释，其中扇入数、扇出数、代码行数、静态调用次数均为常见的影响代码品质的因素，基于上述因素，创建关键节点的层内集成模型[15 17]。

定义4 品质因素矩阵：以节点为行，节点属性值扇入数、扇出数、代码行数和静态调用次数为列构成的矩阵表示形式。

设函数节点的扇入数为RR（单位：个），函数节点的扇出数为RC（单位：个），函数节点的代码行数为DH，函数节点被调用次数为DN，关键函数量化指标用GJ标识。

不考虑同层节点之间的耦合关系，并假设RR、RC、DH和DN在函数调用关系图中相互独立[18]。因此可得：

其中： α，β，γ，δ为任意常数，i，j表示节点网络层的第i层第j 个节点。假设RR、RC、DH、DN和other两两独立，简化得：

令GJ ij∝GJ ij，GJ ij表示函数节点关键性系数，进而得：

约束条件：α+β+γ+δ=1，0<α，β，γ，δ<1，k为任意常数。

基于品质因素矩阵，利用上述公式可以计算出同节点层函数的关键性系数，从而得到该嵌入式软件节点层等级的层内集成模型。该模型充分考虑函数节点关键性影响因素，创建可靠的层内集成模型，保障了层内集成的合理性和有效性。

1.3 评价指标

1.3.1 运算效率指标

基于节点层网络关键等级的嵌入式软件集成测试算法的计算复杂度，由节点关键性计算复杂度和排序复杂度组成，分别用 P computer和P rank表示。對于有m个节点的第M个节点层，依据二分法排序复杂度计算公式（假设单个节点层内和层间关键系数计算复杂度相同，即P inner=P outer），得到节点层的计算复杂度和排序复杂度如下：

从而得到第M层计算效率的调和平均结果：

其中β 为任意常数。

有N个节点层网络的节点关键性计算复杂度为：

其中m i 表示第i层网络节点个数。

1.3.2 充分性指标

关键性等级高的节点出错概率更高，应被优先集成测试，对于该类节点的验证也应更加充分。在增量集成测试中，通过动态执行测试用例实现接口验证，若测试用例先被执行，则被动态执行的次数也就更多。基于此构建该算法的充分性指标模型，将充分性量化成节点参与集成验证的次数 N i，其中i∈（1，2，3，…，m），m 为节点总数，即：

其中K为节点的关键性等级集合，K i为第i个节点的关键性等级系数，即：N i∝K i。

2 算法实现

基于层间、层内增量集成模型，形成基于节点层网络关键等级的嵌入式软件集成测试序列生成算法。具体实施步骤如下：

步骤1： 利用嵌入式软件C代码，生成函数（系统函数除外）的静态调用图和嵌入式软件的品质影响因素矩阵Q。

步骤2：依据静态调用图构建节点层网络的层间集成模型，共生成M个节点层，节点的层间关键性系数用L i（i=1，2，3，…，m）表示。

步骤3：将品质影响因素矩阵Q按照层内的关键性等级计算公式分别计算各层节点的层内关键性系数F ij（第i层的第j个节点）。

步骤4：计算节点层网络的关键系数。在M层N个节点的节点层网络中，C ij（i<M，j<N）表示第i层，第j个节点的关键系数。故：

为计算方便，通常取 L i =max（ F ij ），代入式（9）可得：

将层内节点的关键性系数计算公式代入式（11）：

步骤5：对同层 C ij 进行二分法排序，输出嵌入式软件集成测试的增量集成序列[19 21]。

3 测试实例

本节应用基于节点层网络关键等级的嵌入式软件集成测试序列生成方法，对复杂的嵌入式软件进行增量测试序列生成和结果分析。选取嵌入式工程软件进行实验，统计发现该软件共包含172个非系统函数单元（为了简化后续描述，对软件基于函数单元进行编号，共生成编号1-172）。单个函数的最长代码行数达到291行、最大调用频率高达48次，最大扇入数14，最大扇出数30。基于上述统计信息，绘制该软件经排序后的属性图，如图3所示。

经分析可知，该软件函数调用交联复杂，层内调用和层间调用交错，单次调用与多次调用并存，直接进行系统级增量集成序列生成研究相对困难。为此，本文引进系统论思维，对自上而下的静态调用关系参考节点层模型进行自下而上的层间关系划分，将属性相似的节点进行归类，得到层间集成模型，接着引入层内关键系数因素影响，实现增量集成序列生成。

该算法通过自下而上的方式进行节点层划分，每删除一层叶子节点就会产生新的叶子节点，减少节点总数。通过多次迭代，共生成12层网络节点层，不同层之间的节点组如表1所示，因为删除了连续的叶子节点，故同层节点层间关键性等级相同，实现了对函数集成顺序的粗略排序。

建立节点关键等级的层内集成模型，并结合表1对同节点层函数按照关键性等级大小进行排序，排序结果采用自上而下的集成方式进行连接，函数序列集成如图4所示。

4 测试结果分析

4.1 运算效率

节点层网路采用分层算法，将总节点依据节点相似性原则进行分类、生成相应节点层，而非节点层网络不存在节点层划分，将所有节点等层看待。基于上述逻辑，本文分别计算相同网络条件下的节点层和非节点层算法得到的集成测试增量模型效率，如表2所示。

比较可知，与非节点层网络相比，节点层网络进行增量集成可提升16%的运算效率。

4.2 测试充分性

进一步量化层间关键性系数，取下层节点关键系数集合的最大值作为该层间关键性系数，即 L i =max （F ij） ，层内节点关键系数与该值相加，得到该节点的网络关键性等级系数。

通常增量集成测试的充分性和节点被动态执行的次数正相关，动态执行次数越多，测试充分性越高。每增加一个函数集成点，就需要集成网络动态验证一次。受網络调用关系约束，新加入节点在一次动态执行中将至少被执行一次。为了计算方便，设该网络动态执行一层能够实现对所有调用接口的全覆盖。从而可以得到整个网络函数的关键系数随着网络增量集成次数变化的曲线。

从图5中可知，节点关键系数随着集成次数依次衰减。关键系数越大则节点接口相对越复杂，在集成测试中被动态执行的次数就越多，节点接口验证更充分;关键系数越小则节点相对简单，在集成测试中被动态执行的次数越少，节点接口验证更合理，从而有效提升了集成测试对接口验证的充分性。

5 结语

函数调用关系复杂，以函数整体为对象进行集成测试增量技术研究，会带来测试成本较高、测试不充分等问题。基于层间节点层划分和层内节点关键等级排序结合的方法有效解决了以上问题。首先，通过自下而上的节点层划分算法实现对函数节点集成顺序的粗略划分;再采用自上而下的策略，完成对不同层内节点关键性等级的计算;最后，将节点关键性等级在网络结构内进行量化和动态排序，实现了对节点的增量集成以及增量集成序列的生成。关键性等级高的函数集成顺序靠前，进行集成测试时被验证次数较多，验证也更加充分;关键性等级低的函数，接口调用相对简单、集成顺序靠后，验证次数较少。通过该集成算法，可让整个增量集成方式更加合理、有效。

参考文献：

[1] GJB/Z 141-2004，军用软件测试指南[S].北京：总装备部军标出版发行部，2004.

[2] 蔡建平.嵌入式软件测试实用技术[M].北京：清华大学出版社， 2010.

[3] 单锦辉，姜瑛，孙萍.软件测试研究进展[J].北京大学学报：自然科学版，2005，41（1）：134 145.

[4] 王艳青，于海洋.计算机软件测试技术综述[J].电子技术与软件工程，2017（22）：47 48.

[5] 陆春.软件集成测试解析[J].信息化研究，2014（1）：10 12.

[6] 赵玉丽，王莹，于海，等.基于复杂网络的类间集成测试序列生成方法[J].东北大学学报：自然科学版，2015，36（12）：1696 1700.

[7] ZHANG Y， JIANG S， WANG X， et al. An optimization algorithm applied to the class integration and test order problem[J]. Soft Computing， 2018：1 15.

[8] 胡燕京，张毅坤，朱伟，等.嵌入式软件功能路径测试用例自动生成研究[J].微电子学与计算机，2010，27（1）：81 85.

[9] 王莹，于海，朱志良.基于软件节点重要性的集成测试序列生成方法[J].计算机研究与发展，2016，53（3）：517 530.

[10] MUNSON J C， KHOSHGOFTAAR T M. The detection of fault prone programs[J]. IEEE Transactions on Software Engineering， 1992，18（5）：423 433.

[11] 赵磊，伦立军，徐士华.基于软件体系结构的测试路径生成方法[J].微电子学与计算机，2008，25（1）：177 180.

[12] 徐炜珊，于磊，冯俊池，等.基于软件层次化模型的软件测试数据生成[J].计算机应用，2016，36（12）：3454 3460.

[13] 樊鑫，郑巍，杨丰玉.基于UML模型集成测试工具的建模与设计[J].计算机测量与控制，2015，23（12）：4210 4213.

[14] 郭旺.嵌入式软件覆盖测试综述[J].软件导刊，2017，16（3）：179 181.

[15] ABDURAZIK A， OFFUTT J. Using coupling based weights for the class integration and test order problem[J]. Computer Journal， 2009，52（5）：557 570.

[16] ZHOU Y， LEUNG H. Empirical analysis of object oriented design metrics for predicting high and low severity faults[J]. IEEE Transactions on Software Engineering， 2006，32（10）：771 789.

[17] GJB/Z 102A 2012，軍用软件安全性设计指南[S].北京：总装备部军标出版发行部，2012.

[18] 姜淑娟，张艳梅，李海洋，等.一种基于耦合度量的类间集成测试序的确定方法[J].计算机学报，2011，34（6）：1062 1074.

[19] ZHOU Y， XU B， LEUNG H， et al. An in depth study of the potentially confounding effect of class size in fault prediction[J]. Acm Transactions on Software Engineering & Methodology， 2014，23（1）：1 51.

[20] CONCAS G， MARCHESI M， PINNA S， et al. Power laws in a large object oriented software system[J]. IEEE Transactions on Software Engineering， 2007，33（10）：687 708.

[21] 张妙，姜淑娟，张艳梅.多目标优化类集成测试序列确定问题研究进展[J].小型微型计算机系统，2017，38（8）：1772 1777.