基于扩展有限状态机的SCA符合性测试方法研究

伍旭东，唐 麒，张 伟，张 健，魏急波，王一军

1.中南大学 计算机学院，长沙410083

2.国防科技大学 电子科学学院，长沙410073

3.中南大学 自动化学院，长沙410083

软件无线电（Software Definition Radio，SDR）[1-2]的基本思想是以一个通用的硬件平台为依托，通过软件编程来实现电台所需的各种功能，因此具有很强的灵活性和开放性。软件无线电系统运行在各种不同的硬件平台上，使用的软件产品可能存在差异，不同系统之间难以实现信息交互。为了解决这个问题，联合战术网络中心发布了软件通信体系结构（Software Communication Architecture，SCA）[3-4]标准。SCA标准提供了应用程序接口要求及组件定义和聚合要求，通过定义设备组件对底层的硬件进行屏蔽，实现上层的软件应用和底层硬件相互分离，使得软件应用能够控制不同的硬件设备，提高软件应用的通用性[5]。

SCA标准是组件功能需求的总集，组件产品的符合性测试应根据其功能定位，从需求集中选取相应的子集，根据子集对具体组件进行测试[6]，其目的是验证实际的组件是否满足SCA标准中的组件定义，保证系统能够对这些应用进行统一的管理，实现软件应用的通用性和跨平台性[7-9]。

在SCA符合性测试方面，联合战术网络中心开发了R-Check SCA测试工具，它是现阶段主流的SCA项目测试工具，采用的是静态测试的方法进行符合性测试，能够对C++/C源代码进行解析，寻找系统中存在的错误，但使用该工具要求测试人员具有较高的编程水平，并且测试结果存在一定的波动性[10]。Botella等人提出了基于模型的SCA符合性测试用例生成方法，构建了一个测试生成系统，根据组件的UML（Unified Modeling Language）和OCL（Object Constraint Language）模型，预测待测系统的预期行为，对测试用例进行集成[11]。Springer等人在R-Check SCA的基础上提出了基于模型的SCA开发工具MBDEs（Model-Based Development Environments）。MBDEs将模型的概念扩展到开发阶段，允许开发人员使用模型构造系统[12]。与之相似的还有NordiaSoft公司开发的SCA开发软件组，皆采用基于模型开发的概念，从开发端去解决标准符合性的问题。

扩展有限状态机（Extended Finite State Machine，EFSM）模型是一种常用软件测试模型，被广泛应用于通信协议、软件嵌入式系统等测试建模。Ilie等人提出了关于EFSM的缩减算法，能够有效地减小模型的规模[13]。在此基础上，Kelly等人提出了不定向切片技术，能够针对特定问题对模型进行裁剪[14]。Ramalingom等人基于EFSM模型，提出采用控制分析技术生成测试序列，能够很好地保证测试的覆盖度。张涌等人针对测试冗余问题，提出了R-Wp方法，减少模型中不可行迁移，从而提高测试序列生成的效率[15]。

国内外目前对于SCA符合性测试的研究还处于起步阶段，主要是采取静态分析的方法进行测试，其效果具有波动性，其次是缺乏自动化的测试方法，测试过程需要人工参与，对于规模庞大的通信系统，很容易造成错捡或者漏检。针对目前存在的问题，结合EFSM原理，以及已存在的EFSM方面的研究，根据SCA符合性测试的情况进行改进，提出一种基于EFSM的SCA符合性测试模型，该模型能够对不同需求测试之间的依赖关系进行有效的分析，并基于该模型提出测试序列的自动化构建方法，为实现符合性测试自动化提供支撑。

1 基于EFSM的SCA符合性测试模型

基于EFSM的SCA符合性测试模型由一个六元组组成，表示为：

其中，S={s0,s1,…,sn}为状态集，是测试过程存在的所有状态的集合；s0表示测试的初始状态，s0∈S；V为测试过程中所需要用到的变量的集合，在SCA符合性测试中存在的变量有载荷数、组件连接数等，变量可作为测试是否可执行的判断指标；I和O表示测试系统的输入和输出集合；T为测试系统中状态之间的迁移集合[12-13]。

T中的每个元素t又由一个五元组组成，表示为：

其中，source(t)和target(t)分别表示迁移t的源状态和目标状态；condition(t)为t迁移触发的前置条件，当前置条件不满足时，迁移不能进行触发；event(t)、action(t)分别表示t触发的事件和执行的操作。event(t)、condition(t)和action(t)共同组成了t的标签，其表达式为event[condition]/action。

SCA标准是由大量的组件功能需求构成的，每个需求都有对应的测试用例，分析各需求测试的前置条件，以及执行该测试对组件的影响，将其转换成标签为event[condition]/action的迁移和执行测试抵达的末状态。任意组件的符合性测试是根据其功能定位和具体要求，从SCA标准中选择相应的子集进行测试。测试时，用户根据组件功能需求进行输入，系统从需求全集中抽取需求子集，根据下述规则进行连接：

规则1若任意需求测试A的前置条件condition依赖于另一需求测试B的执行动作action，则需求测试A为需求测试B的后继。

规则2若任意数量需求测试的前置条件condition相同，并且这些需求测试的执行动作并不会使得该条件不成立，则这些需求测试为双向互通的；任意需求测试的执行动作使得该条件不成立，则其他需求测试对其为单向测试。

图1 为根据现阶段SCA符合性测试较为常用的基本组件部分需求集所构造的EFSM模型。表1是图1各个状态之间的迁移的描述，表中Num为模型中的迁移编号，source和target分别表示迁移的起始状态和末状态，condition为迁移触发的条件，action为执行迁移后系统变量产生的改变，Req表示迁移对应的需求测试在SCA标准中的需求编号。

表1 模型迁移描述Table 1 Transition description of model

图1 基于EFSM的SCA符合性测试模型Fig.1 SCA compliance testing model based on EFSM

符合性测试过程中，需求的测试会对组件的状态造成改变，在模型中使用变量来表示当前组件的状态。该模型中存在3个变量，分别是initialized、started和connected，而迁移表示某项需求测试，如SCA7的描述是连接使用端口操作，应根据输入的端口连接参数建立与对应组件的连接，在模型中由t7表示；SCA10的描述是断开连接端口操作，应根据输入的端口断开连接参数断开与对应组件的连接，在模型中由t8表示。迁移均有标签event[condition]/action，其标签可能为空，模型根据当前的变量值对迁移标签上的condition进行判断，选取当前符合条件的测试，在执行测试后对变量进行实时的改变，从而保证了构成测试序列的可行性。

2 测试序列自动生成

该测试序列生成方法的总体流程如图2所示。首先输入需要进行测试的需求集，根据该需求集构造测试模型，测试系统将对模型进行反复遍历，随机生成测试路径，直到已生成的测试序列集满足覆盖要求并到达设置的最小规模。此时生成的测试序列集存在很强的随机性，集合中可能存在冗余，影响测试效率，因此采用基于集合的贪心算法对测试序列集进行挑选，减少测试序列集中的冗余，提高测试效率，并返回最终的结果。

图2 测试序列生成流程Fig.2 Test sequence generation process

需求集总是包含多个需求，并且需要对这些需求进行反复的测试。这些需求测试之间存在相互影响，因此在实际的测试过程中为保证测试的覆盖度，要对组件进行反复的初始化、释放。如图1中，构成任一由组件初始状态S0最终抵达组件释放状态released的迁移集称为一条测试序列：

式（3）为测试序列表达公式，一条测试序列由测试模型中多个迁移构成。式（4）中wpathi是测试序列pathi的执行时间，为构成该序列的所有测试时间的和；wpathij表示具体测试所需的测试时间。系统通过不断地生成测试序列，加入到测试序列集中，构造初始测试序列集S：

式（6）中reqs表示需要进行测试的需求集，即生成的测试序列集应保证能够覆盖到所有的需求测试，保证测试的可靠性。由于构造初始测试序列集的测试序列是随机生成的，可能会存在冗余或者测试效率较低的测试序列个体，这将造成测试时间的增加。在保证测试覆盖度的基础上，为提高测试效率，减少测试用时，采用一种基于集合覆盖的贪心算法[16]对测试序列进行选取。该算法的核心思想是构建每次从初始集合中选择n个集合，这n个包含的未被覆盖的元素个数最多，反复迭代，直到完全覆盖。将其与符合性测试的需求相结合并进行改进，为保证每次选择的收益最大化，需要设置一个适应度函数，评估测试序列的优劣，该适应度函数如下。

式（7）中，Wi为测试序列的适应度，wpathi是测试序列的执行时间，reqi为该序列覆盖到的测试需求集，C为当前已被覆盖的测试需求集。以测试序列个体能为测试集合增加的覆盖需求数量和造成的时间开销来评估测试序列的优劣，因为选择目标是测试用时最短，故将适应度函数取反。每次从初始序列集中选择n条序列，这n条个体的总适应度为：

每次选取的n条序列应使得式（8）中的W最大，将这n条序列加入到新集合中，直到产生的新集合能够对需求集实现全覆盖。算法如下：

算法第1~5行中，Reps表示需要覆盖的需求集，P表示当前已生成的可覆盖需求集的测试序列集，n为算法的选择参数，S为当前挑选出的测试序列集合，C为当前集合所包含的需求集。

3 实验分析

实验将需求集输入到根据此测试序列生成方法搭建的系统中，根据需求集构造测试模型，使用经改进的贪心算法生成测试序列。为保证该方法的通用性，采用三个不同需求数量的基础需求集，分别为1#、2#、3#需求集。1#需求集为SCA符合性测试中基本组件的较为常用的部分基础功能需求集，该需求集包含9个功能需求，主要用于保证组件拥有初始化、配置属性、查询属性、连接等基础功能的测试；2#需求集为完备的基本组件功能测试需求集，该需求集在1#需求集的基础上增加了错误处理、日志输出、生产事件等功能的测试，总共包含33个需求测试；3#需求集为可管理应用组件的组件功能需求集，可管理应用组件是基本组件的扩展组件，因此该需求集需要包含2#需求集，并增加访问文件系统、组件注册等功能测试，总共包含39个需求测试。各需求集如表2所示。

表2 需求集Table 2 Set of requirements

表2 中Num表示需求集的编号，Reqs表示对应需求集包含的测试需求在SCA标准中的需求编号，Count表示该需求集包含的需求总数量。

为了说明该测试方法的工作原理，给出实验的具体过程，以1#需求集为例进行分析。需要输入的数据如表3所示，Req表示需求的具体编号，Test Time表示对应的需求测试所需要的平均时间。根据SCA标准的要求，部分需求要求进行重复多次的测试，因此需要对测试的执行次数进行设置，即Repeat Times。

表3 输入需求集Table 3 Set of requirements for input

将这些数据输入到测试系统中，测试系统根据前文所述的规则1以及规则2构造对应的EFSM模型。根据该需求集所构造的测试模型如图1所示。测试系统不断地生成由S0到released的测试序列，构造测试序列集，直到满足测试覆盖要求和各需求的重复次数要求或者达到指定最小规模，如表4所示。将贪心算法中的参数设置为2，使用该算法对表4所显示的测试序列集进行挑选，最终结果如表5所示。

表4 初始测试序列集Table 4 Initial set of test sequences

表5 最终测试序列集Table 5 Final set of test sequences

表4 和表5中，Path为由系统生成的测试序列的编号，Transition表示测试序列的迁移组成，Req表示该测试路径所覆盖到的需求编号，需求编号后的括号内的数字表示需求测试重复的次数，如7（2）表示需求SCA7的测试在测试序列中重复进行了2次，Time为测试路径的总用时。对比表5和表4可以看出，由该方法生成的测试序列集共包含4条测试序列，能够满足需求测试的覆盖要求和重复测试要求，采用该测试序列集进行测试所需的测试时间为91.1 s。

再将2#和3#需求集分别输入到测试系统中，具体步骤相同，得到最终的实验结果如表6所示。

表6 实验结果Table 6 Experimental results

实验结果表明生成的测试序列集均能对测试需求集进行完整的覆盖。但采用该方法解决实际的问题时，最终生成的测试序列集的测试用时可能受到两个因素的影响，一是设定的最小初始测试序列规模，二是贪心算法参数。为进一步分析这两个因素对于最终结果的影响，采用2#需求集进行实验。将2#需求集输入到测试序列生成系统中，系统根据需求集构造测试模型，在保证测试覆盖度的基础上对初始的测试序列集规模进行限定。系统首先生成相应大小的测试序列集，然后进行选择，最后返回最终的测试序列集。实验结果如图3所示。

图3 初始测试序列集规模和测试用时的关系Fig.3 Relationship between size of initial test sequence set and test time

图3 中横坐标为系统生成的初始测试序列集规模，纵坐标为初始测试序列集经挑选后产生的最终测试序列集的执行时间。结果表明，随着初始测试序列集的规模增大，生成的测试序列集的执行时间变短，最终收敛于一个较优值。为保证结果的优越性，应设置合适的初始测试序列集规模。

将初始测试序列集规模设置为250，分别设置贪心算法的参数为1至5，最终生成的测试序列集的执行时间如图4所示。

图4 贪心算法参数和测试用时的关系Fig.4 Relationship between size of greedy algorithm parameters and test time

实验表明参数设置越大，经该方法生成的测试序列集效果越好。参数设置为1时，其效果等同于传统贪心算法，当参数设置为2时，提升最为显著，参数继续增大时，最终结果提升比较微弱，但算法的时间复杂度上升较快。在解决实际问题时，应根据具体的测试需求进行参数设置。

4 结束语

随着软件无线电技术的不断发展，越来越多的厂家都投入到软件无线电产品的生产中，符合性测试是这些产品可移植性、可配置性及互操作性的重要保障。任一组件产品的符合性测试都是由SCA标准中多个需求的测试构成的，各需求测试之间存在相互影响，如何构造合理的测试序列，保证符合性测试的可行性，针对该问题提出了一种基于EFSM的SCA符合性测试模型以及测试序列自动生成方法。在模型中以迁移表示需求测试，测试会对组件状态进行实时的改变，通过对组件的当前状态进行判断来选取后续可行的需求测试，保证测试序列的可行性。为保证测试的覆盖度，并且提高测试效率，通过随机生成可行测试序列的方式保证需求的全覆盖，采用改进的贪心算法对测试序列集进行挑选，降低测试用时。实验证明，该方法能够很好地保证测试的覆盖度，有效地减少测试的总用时，弥补了目前国内对SCA符合性测试研究的空缺，为后续的测试自动化提供了有效的支撑。

该方法目前阶段主要是针对单个组件的符合性测试生成有效的测试序列，保证测试的可行性，提高测试效率。下一阶段的工作将致力于多组件的交互测试，在多个组件存在相互影响的情况下，如何组织测试，保证测试的可行性。