基于层次有向图的接口时序一致性测试方法

高 亮，李 蒙，梁晨光，宫久路

(1.北京理工大学机电学院，北京 100081；2.北京航天控制仪器研究所，北京 100039；3.北京宇航系统工程研究所，北京 100076)

0 引言

武器装备的总装测试中，常出现接口时序不匹配导致的电气系统工作故障问题，因此有必要开展接口时序的一致性在线测试方法研究。现有的一致性测试方法分为主动测试和被动测试两类[1]。ISO/IEC 9646标准定义了主动测试的框架和方法[2]，工程应用中一般基于TTCN-3测试框架实现[3-5]，通过生成能够触发故障的测试集作为测试输入，观测输入与输出之间的因果关系实现一致性检测，其缺点是不能在线测试，且只能检测测试集已覆盖的故障类型。被动测试则利用形式化模型描述被测系统行为，通过对比检测发现所有与模型描述不一致的系统行为实现时序一致性的在线测试，常用的模型有Petri网[6]、有限状态机及其扩展模型[7-9]、有向图模型等[10]。相较于主动测试，被动测试方法能够满足接口时序的在线测试需求，且能发现系统长期运行后出现的错误。目前，一致性测试研究集中于数据链路层和应用层，通过测试物理层电气参数实现一致性测试的研究还很缺乏[11]。同上层测试相比，物理层测试能够直接定位故障产生的原因(如：数据链路层可检测到数据误码，但不能分析出造成误码的原因)，发现潜在的时序缺陷，因此，在线物理层测试成为发现和定位接口时序故障的主要技术途径。

目前主流的物理层在线测试方法是通过示波器或逻辑分析仪进行人工测试[12]，存在测试效率低，不能实现长时间连续测试等问题。为了提高测试效率，有学者开始研究时序的自动化测试系统[13-15]，但研究偏向时序参数的自动测量和判断，较少涉及逻辑关系的检测，同时在描述时序规范时，多采用描述跳变沿时间的方法实现，在时序建模方法上还有待进一步的研究。针对武器装备在总装测试中出现的接口时序不匹配，现有测试方法不能实现长期连续自动测试的问题，本文提出基于层次有向图的时序一致性测试方法。

1 测试框架及有向图模型

1.1 被动测试

武器系统的总装测试要求在线测试，因此只能选择被动测试方法，时序一致性测试的被动测试框架如图1所示。测试时首先利用形式化方法将时序协议输入测试系统，建立标准时序的模式集和约束集；然后在被测系统与外界运行环境交互时获取测量数据，通过测量数据与模式集的对比分析检测出逻辑异常时序，通过验证时序参数是否满足约束集检测出不收敛的异常时序。

图1 一致性测试的被动测试框架Fig.1 Passive testing framework for consistency testing

1.2 有向图模型

有向图模型是一类由节点和有向边构成的，具有严格数学描述的定性模型[16],通常以节点表示系统变量或状态，以节点间的因果影响关系构建有向边，记作〈u,v〉，表示从节点u到节点v的有向边。与边相关的数称作权，可以表示节点之间的变迁时间、传播概率等。若从有向图的节点vi出发，沿有向边经过节点vp1,vp2,…,vpm到达节点vj，则称节点序列(vi,vp1,vp2,…,vpm,vj)为从节点vi到vj的转移路径，路径上所有边的权值之和称作转移路径的长度。

2 层次有向图模型及检测算法

2.1 接口时序的层次结构

考虑到通信接口在实现数据交换时通常是分周期完成的，将重复的时序片段用同一个模型描述能够降低模型的构建难度。为了统一建模方法，首先对接口时序进行层次划分，对应的层次结构如图2所示。图2中，功能时序表示接口实现某种基本功能时对应的工作时序片段，空闲时序表示接口处于空闲状态时对应的时序片段，两类时序对应的时序规范统称为时序模式。

图2 接口时序的层次结构Fig.2 Hierarchical structure of interface timing

图2所示的层次结构的数学描述如下：

1) 设接口含有N种基本功能，每种基本功能对应的时序规范表示为模式φi，则接口时序的功能模式状态空间：

Φ={φ1,φ2,…,φN}

(1)

2) 设接口在空闲状态下存在M种可取的状态组合，每种状态组合对应的时序规范表示为模式γi，则接口时序的空闲模式状态空间：

Γ={γ1,γ2,…,γM}

(2)

3) 若接口含有k个步骤的功能操作，设φi∈Φ(1≤i≤k)，γj∈Γ(0≤j≤k)，则接口时序Θ可描述为：

Θ={γ0,φ1,…,φk,γk}

(3)

在上述层次结构中，功能时序和空闲时序是描述接口时序的最小基本单位，两类基本级时序的不同组合可实现不同系统级时序的描述，所构成的系统级时序同时又可作为更上层时序描述的基本单位。特别地，当接口时序Θ的模式状态空间Φ和Γ分别只含有一种模式时，称Θ为单模式时序，反之称Θ为多模式时序。

2.2 时序的有向图模型

模型构建的关键在于实现状态空间中每个φi和γj的具体描述，本文针对单模式时序构建接口时序的有向图模型，如图3所示。图3中，单圆圈节点表示只含有1种属性，双圆圈节点表示含有多种属性，有向边上的竖线表示信号沿，扇区是本文提出的一种新的结构，用六边形表示。紧邻扇区的两个节点分别称作扇入节点和扇出节点。

图3 单模式时序的有向图模型Fig.3 Directed graph model of timing mode

模型以同一时刻下接口各信号线的逻辑状态di=(x1,x2,…,xn)作为节点属性，其中xi表示第i个信号的逻辑值；以接口时序的状态变迁规律构建有向边，并定义系统观测的时间分辨率为模型中所有邻接路径的权，权值大小等于观测频率fsamp的倒数。建立时序有向图模型的主要步骤如下：

1) 确定时序模式φi的开始和结束位置，从开始位置起沿时间轴方向对φi的时序图进行虚拟采样扫描，直至结束位置；

2) 以φi的第一个采样状态作为节点P1，设相邻两次采样所得到的系统状态分别为di和di+1，di对应的图节点为vi，若di=di+1，则有向边为自循环路径〈vi,vi〉；若di≠di+1，则生成新节点ui+1，并构建有向边〈vi,ui+1〉，直至φi的最后一个节点Pm；

3) 在步骤2)中，若相邻状态di和di+1之间存在1个以上的信号沿，则在di和di+1对应的节点之间添加扇区结构；

4) 设接口在空闲状态下可取的系统状态为：d1,d2,…,dk，使用双圆圈γ节点表征空闲时序，该节点含有对应的k种属性，并构建有向边〈Pm,γ〉和〈γ,P1〉；

5) 时序约束在模型中的映射方式为：根据时序约束条件确定受约束的两个信号沿位置，时间位置靠前的称作基准信号沿，时间位置靠后的称作受约信号沿。从基准信号沿出发，按照有向转移路径到达受约信号沿，设共有n条可能的转移路径，则为每条转移路径都添加一个二元约束值，其形式为(max,t)或(min,t)，分别表示对应转移路径的路径长度不得超过或小于t。

模型中的扇区结构是针对逻辑变迁规律具有随机性的时序区间而提出的，其目的是为了缩减模型体积，进一步降低模型的构建难度。如图4所示时序含有A、B、C三个并行信号，a、b、c、d、e分别表示信号沿的理想位置，其中c、d、e对应同一时刻，a′、b′、c′、d′、e′分别表示信号沿的实际位置。由于时序规范允许信号沿在约束范围内发生有限偏移，因此可能出现两种情况：

1) 信号沿的理想位置不在同一时刻，如信号沿a、b，偏移后不会产生新的系统状态；

2) 信号沿的理想位置对应同一时刻，如信号沿c、d、e，偏移后会出现新的系统状态，且状态的数量和出现的先后顺序都不相同。

图4 时序的实际位置与理想位置的示意图Fig.4 Schematic diagram of the actual position and ideal position of the sequence

针对上述的情况2)分析所有可能出现的情况，假设有n个信号沿的理想位置对应同一时刻，其中只有m个信号沿的实际位置对应同一时刻，则所有相对位置关系的可能情况数可按照排列组合的方法计算出：

(4)

如果使用传统的有向图模型就需要构建s条不同的转移路径，根据式(4)可以看出，随着n的增大，模型体积和结构复杂度会急剧增加，且后续检测时的搜索空间也随之增加。为了解决这个问题，本文使用扇区结构整体取代这部分时序区间对应的图结构，并通过扇区边界条件保证取代前后描述的等效性。即只要满足扇区边界条件，就一定在原图结构中存在一条对应的转移路径。考虑到信号的偏移不会导致电平状态的改变，因此可构建扇区的边界条件如下：

1) 若扇区对应的时序区间内有n个信号沿的理想位置重叠，则扇区内图结构的转移路径包含的节点数量不超过n-1；

2) 扇区内一定不含有与扇入节点和扇出节点属性相同的节点；

3) 每条转移路径上所包含的节点，一定是互异的。

2.3 基于模型的错误检测算法

根据错误检测标准的不同，将接口的异常时序划分为两种类型：一是信号间的逻辑关系发生改变，称作逻辑性错误；二是时序参数的测量值不满足约束条件，称作收敛性错误。当逻辑关系发生改变时，可能导致时序参数的测量位置发生偏差，因此时序参数的约束符合性检测应建立在逻辑关系正确的基础上。同时考虑到硬件工作具有顺序执行的特点，当在通信周期的ti时刻发生逻辑性错误时，即使ti+1时刻的时序正确，也不能保证接口正常通信。换言之，当通信周期检测到错误后，再对当前通信周期内的后续时序进行一致性检测没有意义，因此在算法设计时只需考虑通信周期内出现单个错误的情况。为了保证测试的准确性，一致性测试应尽可能地证明系统存在错误，因此在设计算法时不允许将错误的时序诊断为正确，但允许将正确的时序检测为错误。基于上述分析，设计层次化错误检测算法如下，算法的工作流程图如图5所示。

图5 层次化错误检测算法的工作流程图Fig.5 Workflow of hierarchical error detection algorithm

1) 假设系统初始候选状态为所有状态，通过不断观测，候选状态数不断减少，当候选状态数变为1时确定初始状态，当候选状态数变为0时表示检测到错误，报告错误，并重新开始执行步骤1)；

2) 通过有限状态机对所有测试数据点进行标记，将测试数据分为空闲时序和功能时序两类，并同时检测位于空闲时序的数据点是否属于γ，如果不属于表示检测到位于空闲时序的逻辑性错误；

3) 将位于同一个通信周期的功能时序数据点提取为一个完整的通信帧，通过校验帧格式检测位于功能时序段的逻辑性错误；如果不存在错误则执行步骤4)，否则报告错误，并停止当前通信帧的后续检测；

4) 定位被测时序参数的两个信号沿位置，通过计算信号沿位置之间的时间距离得到测量值，并判断测量值是否符合约束不等式，如果不符合表示检测到收敛性错误。

3 实验验证

本文基于LabVIEW完成时序一致性测试系统的样机开发，利用FPGA实现了4种不同的被测信号源，各被测信源中存在的时序故障详见表1。为了验证设计算法对通信周期内存在多个错误的时序的检测效果，在复合错误信源的通信周期内均注入了2种不同类型的逻辑性错误。利用测试系统分别对4种被测信号源进行单独测试，测试结果如表2所示。

表1 各被测信源中存在的时序故障列表

表2 各被测信源的时序一致性测试结果

表2的测试结果表明，含有逻辑性错误的两类信源均存在不同程度的虚警率，这是因为当通信周期的开始标志出现错误时，检测算法会将功能时序的数据点当作空闲时序来检测，因此凡是不属于空闲时序集合的状态会被误检为出现逻辑性错误。对通信周期内只含有1种错误类型的信源测试结果显示，没有错误漏检的情况出现，说明设计算法对单个错误有着较高的检测率，其中对收敛性错误的检测准确度可达到100%，因为时序参数的收敛性检测结果仅与自身的测量值有关，在逻辑关系正确的前提下，可保证参数的测量位置不出现偏差，在采样分辨率足够高的情况下，可达到很高的检测准确度。复合错误信源的测试结果显示存在较高的漏警率，造成错误漏检的根本原因是算法是基于单个错误假设设计的，当检测到通信周期存在错误后便不再对这个周期内的后续数据做检测，因此会漏检通信周期内时间位置靠后的错误。

4 结论

本文提出了基于层次有向图模型的接口时序一致性测试方法。该方法通过建立接口时序的层次有向图模型，设计错误检测算法，实现对接口异常时序的检测。实验结果表明，该方法能够对通信周期内单个逻辑性错误的异常时序实现准确检测，对不收敛的异常时序能实现完全检测，但是当通信周期的开始或结束信号出现错误时，可能会出现虚警率较高的问题，并且对通信周期内存在多个错误的异常时序检测时准确度较低，甚至会出现较高的错误漏检率。