基于合约逐级求解的系统测试用例生成

曹 源，刘 杰+，肖安洪，吴志强，陈 智，曾 辉

(1.南华大学 计算机学院，湖南 衡阳 421001；2.中国核动力研究设计院 核反应堆系统设计技术重点实验室，四川 成都 610041)

0 引 言

为保障核电DCS软件系统可靠性[1]，降低人力成本，提升系统研发效率，研究测试用例自动生成方法。核电DCS软件系统在高安全性应用开发环境SCADE(safety-critical application development environment)平台上，基于基础组件开发，由SCADE平台自动生成系统的源代码。源代码将被烧录到芯片中，在软件系统使用、维护过程中，未按照标准操作，会使模型与代码之间偏离[2]。导致软件系统未能实现模型预期功能。为此需要对源代码生成的软件系统进行测试。常用的方法是根据反映整个系统行为特征的系统合约模型的求解[3,4]，生成系统的测试用例。但合约模型应用到工程软件系统时，存在求解难度大、耗时多的问题。

针对此类问题，本文提出通过分析组件间依赖关系，得到组件处理顺序，从而逐级计算组件合约的方法。具有如下优势：①软件系统模型基于具备可靠性的基础组件组装，结合合约模型可以实现在无源码的情况下生成测试用例集，方法适用范围广。②方法采用逐级计算基础组件合约的方法，依照组件计算顺序逐级求解，规避了系统合约求解NP难问题。③方法应用于核电厂DCS软件的系统级的测试用例生成，降低当前人工设计测试用例由于个人因素制约产生的测试充分性影响，降低测试人员负担，且增加了自动化测试程度。将方法应用于核电反应堆堆芯测量系统，验证方法的可行性。

1 基于合约的测试用例生成方法

1.1 应用背景概述

核电DCS软件系统在SCADE平台上，采用基于组件的开发方法进行开发。SCADE的基础组件是实现数据和信号处理的基本单位，如量程转换组件MRC，就完成了对满足界定上限和下限的输入信号进行线性转换，并按参数要求限值输出的工作。这些组件包括输入信号、输出信号以及模块设定参数等输入输出接口，例如MRC的输入信号确定了实际信号输入并进行故障设定，输出信号确定了实际信号输出并监测信号值域等，参数确定了量程转换组件的工作模式。

组件被正确执行的特征可通过组件的前置条件、后置条件及不变式予以限定[5]。调用方按照前置条件生成合法输入。执行方依照后置条件保证输出数据符合预期要求。不变式是系统生命周期中应始终满足的条件。这些前置条件、后置条件及不变式与组件合约存在对应关系。组件合约即为反应组件正确执行时输入信号、输出信号及参数接口的逻辑关系。逻辑关系采用的是命题逻辑公式进行描述。根据软件系统模型生成组件合约，通过对命题逻辑公式的求解，从而得到正确的输入样例和期望输出值，即测试用例。根据测试用例验证源代码生成后的软件系统是否存在错误。在前期的研究过程中分析软件系统模型生成了基础组件的合约模型[6]。

完整的DCS软件系统模型是由这些基础组件通过连接组件间的输入、输出等信号线搭建而成。通过基础组件间连接信号变量的映射转换，可由基础组件合约构建出完整的系统合约。当组件间存在依赖关系时，则合约关系更为复杂，命题逻辑公式求解难度增大[7]。如果系统由成百上千个基础组件构成，则系统合约公式巨大，求解是一个NP完全问题。因此一个有效的方法就是依据信号处理过程，逐级分析基础组件合约，计算单个组件的期望输入输出，最后得到系统的输入输出。逐级分析组件的基本要求就是要不违背组件的依赖关系。DCS软件系统的组件依赖就是对组件信号处理的先后次序。如在第3章的反应堆堆芯测量系统中的计算“温差值”的SUM组件执行，需要求最大值组件MAX和求最小值组件MIN。这说明SUM组件依赖组件MAX和组件MIN。

因此组件测试用例生成需要确认组件的测试顺序。对于复杂系统的测试顺序确认已经有许多的研究方案，张艳梅等[8]提出基于图论和基于搜索两大类别的测试顺序确认方法。基于图论的方法是通过分析依赖关系生成有向结构图，再对图中的节点进行排序，进而生成测试顺序的过程。其中一个重要的研究方向就是针对有向结构图中存在的闭环问题，进行破除环路的处理，再进一步进行测试顺序确认[9]。Zhang等[10]提出，删除弱依赖关系破除环路的处理方案。其中基于搜索的方法是制定期望测试顺序标准，通过智能优化算法，不断进化初始种群，进而得到测试顺序的过程。这两类测试顺序确认方法被广泛的应用于各个领域。现今大多数研究方向是针对于复杂的软件系统，通过减少测试桩数目及降低测试桩复杂度来降低测试成本。而开发测试桩本身耗费大量成本，且开发过程中桩模块可能会产生新的错误。

核电DCS软件系统的组件模型具有线性化、无环性、参数控制等特点。对于测试顺序确认问题，设计出一种本身具备简洁、高效、省时特点，并能够保证测试顺序准确无误的基于拓扑的组件计算顺序算法。

因此针对核电厂DCS系统，提出了一种基于组件合约的自动化测试用例生成方法。主要内容包括组件间的依赖关系分析及组件计算顺序确认算法，逐级结合基础组件合约要求，生成部分符合前置条件的测试用例输入、及正确的参数，按照组件计算顺序执行生成符合方法后置条件的期望输出，通过判定是否满足不变式，约简测试用例，从而自动化生成符合所有合约的测试用例集。

1.2 测试用例生成流程

DCS软件系统的设计图通过组件定义系统功能实现。组件是一些独立、可重用的功能的模块[11]。设计图可以得到由组件定义的DCS软件系统的结构模型。

DCS软件系统的设计图描述了系统功能通过基础组件实现的基本结构。由此可以分析出，组件之间的依赖关系。这些依赖关系决定了，测试用例生成的顺序关系。组件计算顺序结合单个组件的基础合约，使用组合测试工具(PICT)生成初始数据，逐步计算出系统的测试用例。测试用例生成流程如图1所示。

图1 测试用例生成流程

定义1 结构模型由<组件集合，组件依赖图>构成。组件集合构造系统的基本功能模块集合，组件依赖图说明组件调用依赖关系。

定义2 组件是一个<组件接口集，组件参数集，组件合约集>三元组。

(1)组件接口集::<输入接口集，输出接口集>，每个组件存在一个组件接口集，组件接口集中存在若干个输入接口和输出接口。

输入/输出参数::，组件接口集中存在若干个输入、输出参数，其中value表示其值，可以是浮点数模拟量，也可以是二进制值量；state表示状态，有且只有无故障和有故障两种状态。

(2)组件参数集：每个组件存在一个组件参数集，参数集内的不同参数值协助划分组件不同的工作模式。如在第3章给出的报警信号跳变阈值SVAL，取值 {190,40,50,300}, 当组件THC接收组件SUM输出值value后，可根据value与SVAL值进行比较，确认温差是否超越阈值，能否产生报警信号。

(3)组件合约集::<参数合约，值合约，状态合约>，每个组件具备一个组件合约集，组件合约集中有参数合约、值合约、状态合约3种合约。

参数合约是组件参数值(value)及组件参数间的约束条件；值合约是组件接口输入数据、输出数据值(value)的约束条件；状态合约是组件接口输入数据、输出数据状态(state)的约束条件。

本文采用合约化理验证组件执行的正确性。通过求解合约的命题逻辑公式得到期望测试用例集。组件合约集与前置条件、后置条件及不变式存在对应关系。其中前置条件对应输入值合约及输入状态合约及参数合约中的参数值合约部分，输入值合约通常将数据同参数值比较、或数值相互比较决定当前数据满足何种工作模式；后置条件对应输出值合约及输出状态；不变式条件通常对应参数合约中的参数值及参数间合约部分，组件合约对应关系如图2所示。

图2 组件合约对应关系

软件系统中各组件成员间存在关系，当组件需要借助另一个组件提供服务时，称组件间存在依赖关系[12]。组件之间的依赖关系导致信号变化产生连锁反应，系统稳定性受到组件间依赖关系的制约[13]。

定义3 组件依赖：设CA、CB分别是DCS软件系统中的两个组件，CB依赖于CA，组件CA必须在组件CB前执行，称为存在组件依赖关系，则组件CA存在输出接口OA，组件CB存在输入接口IB。接口IB会接收到由接口OA中传递的信号，并对信号进行处理。前后组件主要传递两种类型的信号：

(1)组件转换状态：接口IB接收到接口OA中传递的信号后，仅发生状态传递，由组件CA运行至组件CB，则称发生组件转换状态。

(2)数据传递状态：组件CB中存在方法P，接口IB接收到接口OA中传递的信号，其中包含方法P所需要使用的数据，则称发生数据传递状态。

根据这种依赖关系中的两种状态，结合系统设计图进行静态分析，构建组件依赖图。根据组件依赖图使用基于拓扑的组件计算顺序算法，来进行组件计算顺序确认。

根据软件系统模型的静态分析生成基础组件合约模型。基础组件合约模型提供了系统需要满足的合约。依照组件合约对应关系，给出包括组件输入接口需要满足的前置条件，组件输出接口需要满足的后置条件，以及在整个系统测试过程中需要满足的不变式条件。

通过确认的组件计算顺序来依次判定测试用例是否符合接口合约。使用PICT工具依照合约需求中的前置条件生成部分测试用例输入及组件参数值。针对每个组件，依次根据满足不同输入接口前置条件的输入数据，选择不同工作模式，对应不同输出接口后置条件计算输出值。再对测试用例进行不变式条件判定，不满足不变式条件则约简测试用例，即从表中删除该组测试用例，均满足则保留测试用例，并执行至测试顺序中下一个组件，直至执行至最后一个组件。最终获得满足所有合约的测试用例集。

1.3 测试用例覆盖准则

测试覆盖准则是对软件测试充分性的度量[14]。由于基于合约化理论生成测试用例集，因此采用合约覆盖率作为测试充分性的度量标准。组件的工作模式由前置条件的输入值合约部分，结合组件参数进行划分，工作模式与后置条件存在一一对应关系，因此将后置条件的覆盖情况作为测试用例覆盖标准能够很好反映出软件系统工作模式的覆盖情况，给出合约覆盖率作为测试用例覆盖准则：

定义4 合约覆盖率CC

(1)

2 组件合约逐级求解技术

合约逐级求解技术可分为两大部分工作。第一部分是组件计算顺序生成算法，根据分析得到的组件依赖图，使用组件计算顺序算法对组件进行排序处理，最终得到组件计算顺序；第二部分是合约逐级求解测试用例生成算法，分为组件初始数据生成算法和组件处理算法，组件初始数据生成算法依照合约需求中的前置条件生成具有非数据传递状态的输入值、输入状态及组件参数值；组件处理算法则通过前置条件、后置条件和不变式条件按照组件计算顺序，对组件逐级处理，求解输出值，约简测试用例，最终生成满足所有合约的测试用例集。

2.1 组件计算顺序生成算法

为了确保SCADE系统组件间生成的测试数据的准确性，需要对组件的测试顺序进行确认。根据所构建的组件依赖图，来对组件计算顺序进行排序。针对组件依赖图为有向无环图的情况下进行讨论。拓扑排序能够由集合中的偏序得到全序。而有向无环图能够表示具有依赖关系的顶点集。有向无环图通过拓扑排序能够生成一组序列。我们仅保证具有依赖关系的组件，被依赖的组件需在依赖组件前执行，由此提出一种基于拓扑的组件计算顺序算法。

设G(C，E) 为某有向无环图，图中一个顶点代表一个组件， C={C1，C2，…Cn}，E={e1，e2，…em}， 某个顶点的出度表示该组件的输入接口共连接了多少个组件(组件数≥0)的输出接口，表明这个组件所依赖的组件数量。某个顶点的入度表示该组件的输出接口共连接了多少个组件(组件数≥0)的输入接口，表明这个组件被依赖数量。顶点CA，CB∈C， 若存在有向边ek=， 则表示组件CA与组件CB存在组件依赖关系，组件CA必须在组件CB前执行。

具体流程如下：

(1)输入所有组件对象及组件依赖图G；

(2)建立数组deg记录图中每个组件节点出度数；

(3)建立队列que添加出度数为0的组件节点；

(4)建立空序列order，在队列不为空时从队列中取出头节点放入序列末尾，并将此组件节点的后继节点出度数均减1；

(5)后继节点出度数为0时，排入队列末尾，等待序列召唤，直至将所有组件计算顺序排列完毕，输出组件计算顺序。算法伪代码如下：

算法1：组件计算顺序算法

输入：组件依赖图G

输出：组件计算顺序

(1)建立新图G

(2)建立数组初始化

(3)for依赖图中组件对象间存在信号输入do

(4) CA:=被依赖组件

(5) CB:=当前组件

(6) If组件CA、CB存在有向边ekthen:

(7) 组件CB的出度数+1

(8) end if

(9)end for

(10)建立队列

(11)建立空序列

(12)while队列不为空do

(13) 从队列中取出头结点(出度为0的节点)CA添加至序列末尾

(14) for CA存在后继节点CBdo

(15) 数组中后继结点CB出度-1

(16) if 后继结点CB出度为0 then

(17) 队列队尾添加CB

(18) end if

(19) end for

(20)end while

(21)return 输出组件计算顺序 end

2.2 合约逐级求解测试用例生成算法

根据得到的组件计算顺序，进行合约逐级求解工作，具体流程如下：

(1)根据系统设计图的分析确认需要测试的内容及基础组件合约模型，通过基础组件合约模型得到需要满足的合约；

(2)根据前置条件预先生成部分组件的输入数据及组件参数，根据数据名称和值建立映射表；

(3)按照确认的组件计算顺序依次处理组件，每次从表中取出组件的输入数据，或获取被依赖组件(上一个组件)的输出值，作为当前组件的输入参数名与值添加进映射表并进行前置条件判定，符合前置条件，根据结果内容及映射表计算对应输出值，并根据后置条件确定输出状态；

(4)最后进行一次不变式条件判定，抛弃不符合条件的测试用例，将符合条件的输出值及状态存入合法数据表中，得到最终满足所有合约的测试用例集。组件处理伪代码如下：

算法2：组件初始数据生成算法

输入：组件序列，组件参数组合，组件合约

输出：组件初始输入数据

(1)For 前置条件 do:

(2) If 条件满足 then:

(3) 生成部分组件的输入数据及组件参数，根据数据名称和值建立映射表

(4) End if

(5)End for

算法3：组件处理算法

输入:组件计算顺序，组件合约，组件初始输入数据

输出:合法测试用例

(1)For 每组参数组合输入数据 do:

(2) For 组件 in 组件序列:

(3) For 引用输入 do:

(4) 获取被依赖组件(上一个组件)的输出值，将它作为输入参数名与值添加进映射表

(5) End for

(6) For 前置条件 do:

(7) If 条件满足 then:

(8) 根据对应后置条件结合结果内容及映射表计算得到输出值和状态

(9) End if

(10) End for

(11) For 该组件不变式条件 do:

(12) If条件不满足 then:

(13) Goto 1

(14) End if

(15) End for

(16) 将输出值与状态写入合法数据表

(17) End for

(18) 输出合法测试用例

3 应用研究

针对使用合约化理论的基于基础组件组装的系统，构建了一个自动化生成测试用例的工具。工具开发平台为PyCharm，采用Python语言编译，并使用开发框架QT进行设计，运行界面如图3所示。

图3 测试用例生成工具运行界面

反应堆堆芯测量系统是对堆芯温度进行检测，保证防止由于堆内温度热分布不平衡产生的安全性事故。反应堆堆芯测量系统将堆芯分为4个区域，每个区域都设置了不同数量的温度传感器。反应堆堆芯测量系统的报警功能实现过程是由每个区域的温度测量信号到报警信号的转换过程。区域内通过对采样信号进行去噪处理后对最大最小温度值求差，再通过对温度信号与报警信号阈值的比较，从而产生报警信息，分为温度信号去噪、温度值求差、阈值检测三阶段工作，以区域P1内温度值求差及阈值检测阶段工作过程为例说明基于合约的组件集成自动化测试用例集生成过程。

温度值求差：通过温度信号去噪阶段传递而来的温度数值信号，使用组件MAX、MIN分别求出5个温度传感器的最大、最小温度值，再使用MUL组件分别对最大、最小温度值进行符号设定及数值补偿，再通过SUM组件求温度差，此过程共使用5个组件。

阈值检测：通过温度值求差子系统传递而来的温差信号，使用THC组件检查阈值以产生报警信号。此过程中共使用1个组件。

暂时忽略温度信号去噪阶段VSB组件与温度值求差阶段MAX、MIN组件之间存在的数据传递状态，仅考虑MAX、MIN组件与MUL组件、MUL组件与SUM组件、SUM组件与THC组件之间存在数据传递状态。静态分析组件间的依赖关系，生成组件依赖如图4所示。

根据组件依赖图，使用算法1中组件计算顺序算法进行排序，生成组件计算顺序。

使用微软公司开发的组合测试工具(PICT)，结合二维组合覆盖准则，根据合约模型的前置条件使用算法2中组件初始数据生成算法，生成满足逻辑公式的MAX、MIN组件的测试用例输入、状态及MUL_1-2、THC的参数值，即进行布尔表达式判别，生成满足布尔表达式为“真”时的数据，并根据数据名称和值建立映射表。

根据组件计算顺序，使用算法3中组件处理算法来对组件进行处理，依次取出映射表中存储的组件初始输入数据，及接收的被依赖组件传递而来的数据，对组件逐级计算求解。

图4 温度值求差阶段及阈值检测阶段组件依赖

首先获取MAX组件映射表中的测试用例输入及状态，输入数据见表1。

根据不同的前置条件划分不同工作模式，即进行布尔表达式的判别，获取布尔表达式为“真”时对应的工作模式。此处判别5个接口，接收到温度信号去噪阶段，5个组件传递而来的数据中(此处使用PICT模拟生成)，哪个接口接收到的数据，是状态为无故障前提条件下的最大温度，MAX组件前置条件见表2。

MIN组件结构类于MAX组件，得到输出O2(最小温度)，此处不再赘述。

MUL_1组件接口见表3，具备参数G1(模拟信号、最大温度增幅)，输入接口I1获取被依赖组件MAX的输出值及状态，并作为自己的输入数据，即最大温度添加进映射表。根据不同工作模式，对应后置条件输出增幅后的最大温度，MUL_1组件前置及后置条件见表4。

MUL_2组件结构类似于MUL_1组件，具备参数G2(模拟信号、最小温度增幅)得到输出O2_min(增幅后的最小温度)，此处不再赘述。

SUM组件在接收MUL_1、2组件传递的数据及状态后，作为输入添加进映射表，并计算温差，其中SUM输入数据见表5。

THC组件接口见表6，具备参数SVAL(模拟信号、报警信号跳变阈值)、参数HYST(模拟信号、迟滞参数)，组件参数见表7。输入接口I1获取被依赖组件SUM组件传递来的温差值及状态，作为输入添加进映射表，并从映射表中取出PICT生成的SVAL及HYST的参数值。根据当前不同工作模式，选择输出不同信号。例，当输入数据值大于SVAL，则超出阈值上限，信号从“0”跳变至“1”，输出报警信号。并根据不变式条件，约简布尔表达式为“假”时的测试用例，最终得到满足所有合约的测试用例集，THC组件条件见表8。

表2 MAX组件前置条件

表3 MUL_1组件接口

表4 MUL_1组件前置条件及后置条件

表5 SUM组件输入数据

表6 THC组件接口

表7 THC组件参数

表8 THC组件条件

根据测试用例生成方法生成测试用例实例，见表9。

在满足组件合约的情况下使用生成了15组测试数据，测试用例覆盖率见表10。

测试用例平均覆盖率达到97.27%。在解决了问题的同时保证了较高的合约覆盖率。

4 结束语

核电厂DCS软件的系统级的测试用例生成，与系统的性质特征密切相关。目前还没有通用的自动化测试用例生成方法，通常根据有经验的测试人员来进行人工设计测试用例，并结合自动化测试工具进行测试，效率较低。受到人员经验、习惯等人为因素的制约，测试充分度会产生一定的影响，导致生成的测试用例不具备足够的客观性与通用性；且复杂的DCS软件系统求解系统合约是一个NP难问题，在进行测试用例分析设计时成本高、难度大。因此提出一种基于合约的组件逐级测试用例生成方法。这种自动化测试用例生成方法可以使用组合测试策略生成充分多的符合组件合约的测试用例集。根据实验结果表明，生成的测试用例的合约覆盖度达到97.27%。后续工作应加强算法对难覆盖节点的处理，实现工作模式的全覆盖。

表9 测试用例实例

表10 测试用例覆盖率