一种基于扩展接口自动机模型的嵌入式组件建模与测试方法

摘要

一种基于扩展接口自动机模型的嵌入式组件建模与测试方法，涉及软件测试与基于模型的测试自动化领域，所述方法适用于嵌入式组件的测试，针对组件接口操作、数据和行为，采用带有约束条件的自动机模型进行描述，基于图搜索和约束求解技术生成测试用例集合。方法包括两个方面：（1）建立嵌入组件的扩展接口自动机模型；（2）基于自动机模型，定义测试覆盖率目标，并生成满足测试覆盖率目标的正常功能测试用例以及鲁棒性测试用例。

说明书

技术领域：

本发明涉及计算机软件领域，特别涉及基于模型的测试自动化领域。

背景技术：

嵌入式系统已经广泛地应用在了航空、航天、电子、机械等各个领域 。针对嵌入式软件规模大幅度增长、开发周期缩短、质量要求提升的 发展趋势，近年来，提出了嵌入式组件的开发方法，通过功能的分解 、组件接口的封装、标准组件的重用技术，提高开发效率和质量，降 低成本，提高系统的可维护性。

嵌入式组件是构成嵌入式系统的基本单元，是系统构造、开发、组装 、验证、评估、和维护的基本单位，组件的可信性是系统可信性的基 础。组件是独立开发的模块，通常采用黑盒的提供方法，隐藏了数据 和实现方法，内部实现对使用者不可见；具有良好定义的外部特性和 行为，通常遵照接口规范对外提供服务；可通过特定的方式集成，通 过标准的接口协议与其他组件和系统进行交互和协作。在嵌入式系统 中，通常采用软硬件一体的组件，包括硬件、操作系统软件和应用软 件。例如智能传感器系统通常包括信号处理、网络控制软件等部件， 通过稳定的标准化的通信网络接口，提供输出信号。在将嵌入式组件 构建成复杂系统的过程中，通常需要对CNI接口的时域和值域进行详细 、精确的定义。在新的系统集成环境中，确认组件的前置条件以保证 操作的鲁棒性，并对组件进行充分测试。这个精确的接口规约是组件 测试和确认的依据。

美国University of California, Berkeley的Luca de Alfaro和 Thomas A. Henzinger于2001年提出了一种轻量级的嵌入式软件组件 接口模型：接口自动机模型（Interface Automata，IA）。IA基于状 态机模型，可针对组件接口、组件行为和组件间的组合行为进行描述 ，并支持不同组件接口模型之间的可组合性和相容性检查。

基本的接口自动机中，缺乏对组件接口之间约束和依赖关系的描述， 如两个接口操作之间输入、输出数据之间的依赖关系，以及接口操作 前置/后置条件约束等。本发明扩展了接口自动机模型，引入接口参数 定义和约束定义，为描述、理解、和分析组件提供更丰富的行为语义 信息，并给出基于扩展的接口自动机模型的测试自动生成方法。本发 明供包括两部分：（1）扩展的接口自动机定义；（2）基于扩展的接 口自动机模型的测试生成方法。

测试是嵌入式组件质量保证的重要方法，扩展的接口自动机模型可辅 助嵌入式组件分析理解，基于模型的测试自动化技术可提高嵌入式组 件测试的效率和质量，对嵌入式系统基于组件的开发方法研究具有重 要意义。

发明内容

本发明采用基于模型的软件测试技术，基于带约束的自动机理论，给 出一种嵌入式组件的接口操作、数据、以及行为的建模方法；基于图 搜索和约束求解理论，给出一种基于模型的测试自动生成方法。方法 针对目前广泛应用的嵌入式系统，要求嵌入式系统满足以下条件：（ 1）采用基于组件的嵌入式系统开发方法；（1）具有明确的嵌入式组 件接口定义。

本发明方法针对嵌入式组件E，依据以下步骤进行建模与测试：

步骤（1） 系统初始化

输入：嵌入式组件的接口定义，其中包括：接口操作、操作的输入/输 出参数、操作的前置/后置条件以及组件的预期行为信息.

步骤（2） 按以下步骤建立嵌入式组件上的扩展接口自动机模型：

步骤（2.1）构建状态集合S_E，并定义其中的初始状态集合，且。

步骤（2.2）构建接口操作数据和变量集合V_E，且，其中，、、分 别表示输入数据、输出数据和包括有全局和局部变量的内部数据。

步骤（2.3）构建接口操作集合A_E，且，其中，、、分别表示输入 行为、输出行为和中间行为，对于任意一接口行为a∈A_E，用a(v)表示 接口操作及其参数，v∈V_E。

步骤（2.4）构建对应于每个状态的前置条件/后置条件的约束集合C_E，前置条件用preCond、后置条件postCond表述，每条约束采用逻辑表 达式描述，用于判定布尔取值。

步骤（2.5）构建状态转移关系的集合τ=S_E×A_E×S_E，对任意一个状 态转移的关系τ有：，表示组件E若满足前置条件preCond，由状态s ₁会通过操作a(v)，转移到状态s₂，且满足后置条件postCond，再完成 相应的更新update处理。

步骤（3）根据步骤（2）的结果，按以下步骤生成测试用例：

步骤（3.1）定义扩展接口自动机模型的测试覆盖率目标以定量度量软 件测试用例集合的充分程度，采用基于状态转移的覆盖率定义，用全 状态测试的覆盖准则表示。

步骤（3.2）采用图搜索的算法，按以下步骤生成上述测试覆盖率目标 的抽象测试用例集合T_E={tc_i}：

每个测试用例定义为一组接口操作序列，tc_i=<a_i,1,a_i,2,…,a_i,k,..>，i为 测试用例的序号，k每一个操作的序号，k=1,2,…,k,…K，K为操作数 目；

对于所述测试用例中的每一个操作a_i,k∈A_E，存在两个状态：s_i,k∈S_E和 s_i,k+1∈S_E, s_i,k为在序号为i的测试用例tc_i第k个操作a_i,k前的系统状态， s_i,k+1为在序号为i的测试用例tc_i第k个操作a_i,k后的系统状态，即满足转移 关系(s_i,k,a_i,k,s_i,k+1)；

对于测试用例中的任意一个连续的操作子序列<a_i,1,a_i,2,…,a_i,m,…,a_i,M>， 存在一组状态转移集合{(s_i,1,a_i,1,s_i,2),(s_i,2,a_i,2,s_i,3),…..,(s_i,m,a_i,m,s_i,m+1),… ..,(s_i,M-1,a_i,M,s_i,M)}，则对应为扩展接口自动机状态转移用的一条路径， m为操作变化的序号，m=1,2,…,m,…M，M是本序列中操作的个数。

步骤（3.3）从初始状态开始，组合所述状态转移图中的各条路径，构 建一个满足全状态覆盖的抽象测试用例集合。

步骤（3.4）对步骤（3.2）所得到的每一条路径，提取该路径上所有 状态转移上的约束表达式集合，获得下述两类测试用例的数据集：

对于满足约束条件的数据，添加到所述测试用例集合，构成功能测试 用例集合；

对于不满足约束条件的数据，添加到所述抽象测试用例集合，构成异 常测试也称为鲁棒性测试用例集合。

步骤（4）根步骤（3.4）中产生的两类测试用例集合在被测试系统上 执行，以检测被测嵌入式组件接口功能的正确性。

该方法是一种组件接口测试的黑盒测试方法，与基于代码的测试方法 有效互补，着重从用户角度，检测嵌入式组件对外提供功能的正确性 ，可用于组件模块测试和集成测试，是建立在组件内部单元测试之上 的系统测试方法。尤其适用于基于组件组装方式开发的大规模嵌入式 系统的集成过程。

附图说明

图1示出本发明方法的主要结构和步骤；

图2示出本发明方法中扩展接口自动机建模的主要结构和步骤；

图3示出本发明方法中测试用例生成的主要结构和步骤；

图4示出本发明方法中的主要步骤；

图5给出本发明方法的一个实例。

具体实施方式

如附图1所示，本发明主要针对嵌入式组件建立带数据及约束的接口自 动机模型，通过状态机图搜素和约束求解技术，根据模型生成接口测 试用例集合，包括合法输入的正常功能测试以及异常输入的鲁棒性测 试。所述方法采取以下步骤进行：

步骤（1）初始化

嵌入式组件是构成嵌入式系统的基本单元，是功能相对完整的软件模 块，具有明确的功能与通讯接口。初始化过程获取嵌入式组件的接口 定义，包括接口操作、操作的输入/输出参数、操作的前置后置条件、 组件的预期行为等信息。

步骤（2）建立扩展接口自动机模型

如图2所示，需要从以下几个方面构建嵌入式组件E的扩展接口自动机 模型:

步骤（2.1）构建状态集合。如图5所示实例中，包括初始状态，以及 A、B、C、D四个状态。

步骤（2.2）构建数据集合。如图5所示实例中，识别参数数据包括输 入数据v₁和v₂，以及输出数据v₃和v₄。

步骤（2.3）构建接口操作集合。如图5所示实例中，包括两个输入操 作?Op₁和?Op₂，以及两个输出操作!Op₃和!Op₄。各个操作分别带有输 入和输出参数，即?Op₁ (v₁)、?Op₂ (v₂)、?Op₃ (v₃)以及?Op₄  (v₄)。

步骤（2.4）约束集合。如图5所示实例中，状态B的前置条件preCond 以及后置条件postCond。

步骤（2.5）构建状态转移关系。如图5所示实例中，存在转移关系in it→A、init→C、A→B、A→C、C→D以及B→D。进一步识别转移关系 的操作、数据、和约束条件，如。

步骤（3）基于扩展接口自动机模型，生成测试用例

如图3所示，生成测试用例的步骤如下：

步骤（3.1）定义扩展接口自动机模型的测试覆盖率目标。

覆盖率定量度量软件测试集的充分程度。传统的覆盖率主要有基于代 码的覆盖率指标和基于需求的。基于代码的充分性评估适用于白盒测 试中，通过在测试过程中观测程序的语句、分支、路径等的执行情况 ，来评估测试覆盖的充分程度。基于功能的充分性评估，常用于黑盒 测试中，以评估软件系统对于功能需求的覆盖程度。

本方法中采用基于模型的覆盖率标准，模型覆盖准则，是针对元模型 的特征定义的，用于评估测试用例集对模型的覆盖充分程度的一组规 则，它可以应用于任何基于元模型的实例。模型覆盖准则应用于特定 的测试模型，可以得到该模型的一组关于模型元素（状态、转移、事 件等）或是模型元素组合的测试结果。状态机模型使用的典型的测试 覆盖准则如下：

●全状态覆盖(All-States)：测试用例集覆盖状态机的每个状态。

●全转移覆盖(All-Transitions)：测试用例集覆盖状态机的每种状态 转移。

●全事件覆盖(All-Events)：测试用例集覆盖每个状态转移的触发事 件。

●n深度覆盖(Depth-n)：从初始状态出发，对任意不大于长度n的运行 序列，至少存在一个测试用例包含以这个运行序列为子集的序列。

●所有n深度转移覆盖(All-n-Transitions)：从任意一个状态s出发， 对于每个不超过长度n的运行序列，至少有一个测试用例包含以这个运 行序列为子集的序列。所有0深度转移覆盖即是全状态覆盖。

●全路径覆盖(All-Paths)：测试用例集覆盖状态机中所有可能的状态 转移序列。

步骤（3.2）根据测试覆盖率目标，搜索状态转移图的路径。

这可以转化为典型的搜索问题，常用的搜索算法包括爬山算法、模拟 退火算法、遗传算法和蚁群算法等。本方法中可采用图搜索技术，根 据测试覆盖率目标，定义搜索优化的目标函数，通过搜索过程获得满 足覆盖率目标的路径集合。例如，为满足全转移覆盖标准，可得到以 下路径集合：

<(init,?Op₂,A),(A,?Op₁,B),(B,!Op₄,D)>

<(init,?Op₂,A),(A,?Op₂,B),(B,!Op₃,D)>

<(init,?Op₁,C),(C,?Op₃,D)>

步骤（3.3）构建抽象测试用例集合。

由步骤（3.2）中所得到的每一条路径即可对应为一个测试用例，由操 作序列构成。例如，与满足权转移覆盖的路径集合相对应的测试用例 集合为：

<?Op₂,?Op₁,!Op₄>

<?Op₂,?Op₂,!Op₃>

<?Op₁,!Op₃>

步骤（3.4）约束求解测试数据。

如图3所示，针对步骤（2）中所得到的每一个路径，提取该路径上所 有状态转移上的约束表达式集合，通过约束求解技术，获得测试用例 的数据集。测试用例可分为两类：满足约束条件的正常功能测试，以 及违背约束条件的异常测试（也成为鲁棒性测试）。

例如，假设图5实例中，转移约束条件如下所示：

，

则对于路径<(init,?Op₂,A),(A,?Op₁,B),(B,!Op₄,D)>的测试用例<?O p₂,?Op₁,!Op₄>，其输入数据需满足以下约束条件：

$\left(\begin{array}{c}{v}_1+v_2>200\\ v_1+v_2\le 400\\ v_1\ge 0\\ v_2\ge 0\end{array}\right)$

采用边界值方法设计测试数据，则产生一组满足约束测试数据和测试 用例，例如：

｛v₁=201，v₂=0｝，即测试用例<?Op₂(0),>Op₁(201),!Op₄(v₄)>

｛v₁=400，v₂=0｝，即测试用例<?Op₂(0),>Op₁(400),!Op₄(v₄)>

｛v₁=0，v₂=400｝，即测试用例<?Op₂(400),>Op₁(0),!Op₄(v₄)>

｛v₁=0，v₂=201｝，即测试用例<?Op₂(201),>Op₁(0),!Op₄(v₄)>

并可产生一组不满足约束的鲁棒性测试数据和测试用例，例如：

｛v₁=200，v₂=0｝，即测试用例<?Op₂(0),>Op₁(200),!Op₄(v₄)> 

｛v₁=401，v₂=0｝，即测试用例<?Op₂(0),>Op₁(401),!Op₄(v₄)>

｛v₁=0，v₂=101｝，即测试用例<?Op₂(401),>Op₁(0),!Op₄(v₄)>

｛v₁=0，v₂=200｝，即测试用例<?Op₂(200),>Op₁(0),!Op₄(v₄)>

步骤（4）执行测试

将步骤（3）中产生的测试用例在被测系统上执行，以检测被测嵌入式 组件接口功能的正确性。

以上实施方式仅用于说明本发明，而非对本发明的限制。相关技术领 域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以 做出各种变化和变形。因此，所有等同的技术方案也属于本发明的范 畴，本发明的专利保护范围应由权利要求限定。

本发明针对接口的操作语义的形式化描述方法，可准确嵌入式组件的 接口操作、数据和行为特征，为理解和测试组件功能特性提供支持。 传统测试中目前尚缺少对于组件级别的测试方法和技术，本发明在扩 展接口自动机模型的基础上，可支持系统地、自动化地、智能地生成 测试用例，提高嵌入式组件测试的效率和有效性。效率是指通过自动 化测试，与人工设计开发测试用例相比，可减少测试时间，降低测试 本；有效性是指，通过严格地约束定义和约束求解技术生成测试数据 ，提高测试用例的缺陷检测能力（即缺陷数/测试用例数的比值）。