一种改进的通信有限状态机的错误诊断方法

贾家涛 曲明成 吴翔虎

摘 要 目前对于通信状态机的研究已经很广泛，但对于通信状态机的错误诊断方法的研究不多，已有的问题模型都是输出错误和转换错误。为了更好的将错误诊断与实际相结合，本文在一般的通信有限状态机模型上，新增了一种不可执行的情况，并在传统的问题模型中新增一种转换未执行错误的问题模型。在假设单个错误的情况下，提出了一整套新的错误诊断算法，算法通过分析症状信息进行分步检测，并利用可疑转换下一步输入输出和用例的转换序列等信息来定位出单个错误。最后，文中给出一个实例，详细描述了算法的诊断过程。

关键字：通信状态机；单个错误；错误诊断算法

中图分类号：TP311 文献标识码：A 文章编号：

Abstract： Currently CFSM has been widely studied，but little work has been done for fault diagnosis of CFSM model.Existing study mainly fouces on output fault and transfer fault.For combining theory and practice， this paper presents a excutable status into the CFSM model and a problem model into the general problem model.Under the assumtion of single fault，this paper proposes a series of fault diagnosis algorithm.Based on analysing the output symptom and make use of the information of the next input/output pair and the transition sequence， the algorithm can diagnose the single fault step by step.At last，an example is given to demonstrate the procedure of the algorithm.

Keywords：CFSM；single fault；fault diagnosis algorithm

0 引言

错误定位技术是软件调试中的热点和难点问题。随着通信网络的发展，越来越多的通信软硬件设计模型都基于状态机来提供研发、并获实现。在状态机测试方法研究方面，文献[ ]给出了状态机测试的基本准则和一般方法。目前有关状态机测试的研究更多地集中在如何设计与生成测试用例的方法上，常用的测试用例生成方法有W方法，Wp方法，UIO方法和DS方法[ ]等。这些方法的研究目的在于发现错误，然而在检测到错误后，如何根据错误信息而得出错误诊断则是目前亟待研究的一个现实实用课题。本文即针对这一课题展开设计论述。

Ghedamsi最早研究这一问题，在输出错误、转换错误这2种错误以及单个错误的前提下，给出了一种普遍问题定义和解决办法，并对单个状态机上创建了错误诊断算法[ ]，随后将该算法思想扩展到通信有限状态机模型上[ ]，该套理论是后续研究者们的重要参考。Miller将CFSM模型用于网络协议的被动测试中，证明了其成果实施有效性[ ]。钱兰在文献[ ]中提出了单状态机错误诊断的2个改进算法，缩小了错误诊断集合，并提高了时间复杂度。

由于文献[3]所研究的状态机中每个状态对于输入都存在转换，在设计用例时也需要考虑到状态机能正确实现转换。考虑到这些限制，结合状态机实际特点，本文在CFSM模型中增加了输入在状态中无法转换的情况，并提出新的问题模型，即转换不可执行错误。结合程序错误定位技术中的统计学方法、数据挖掘方法以及分析数据依赖等方法[ ]，在Ghedamsi和钱兰的方法基础上，对CFSM提出一种改进的错误诊断算法。与之前的方法相比，本文的算法更清晰高效，而且能给出完整的错误诊断信息。

1 CFSM模型及问题定义

一个通信状态机（Communicating Finit State Machine，CFSM）系统由一组确定有限状态机（Deterministic Finit State Machine，DFSM）具体构成，每个确定状态机除了各自拥有的外部端口之外，还可以通过内部输入队列实现相互间的通信。

本文研究的问题是2个状态机的情况，如图 1所示。测试通道利用P1、P2端口向2个状态机传送输入，2个状态机通过内部通道q1、q2实现信息传输。而且，2个状态机的外部输出也仍是通过P1、P2端口传递至测试通道，研究者可以由此观察到测试通道中的输入输出信息。

假设每个输入都有足够的时间来执行并得到输出，这样每一时刻系统中只有一个消息在传递。同时为了防止问题过于复杂，研究假设系统的内部转换产生输出到另一个状态机后，该输出将不再引起内部转换。

定义1 确定有限状态机M是一个六元组：M=（I，O，S， ， ），I表示输入集合，O表示输出集合，S表示状态集合，而且包括一个系统初始状态s0， ：S I S是状态转移函数， ：S I O是输出函数，本文用 的形式表示一个转换。

定义2 转换的输出结果通过内部端口到达另一个状态机，这样的转换称为内部转换。转换输出通过外部端口向外传输，这样的转换称为外部转换。

定义3 输入序列用Ii表示，分为2个部分，即Ii=IEi IIi（下标表示状态机编号），IEi表示产生外部输出的输入。IIi表示产生内部输出的输入。类似的，输出序列用Oi表示，也可以分为两个子部分，即Oi= OEi OIi。OEi表示产生的外部输出，OIi表示产生的内部输出。由假设OIj IEi且IIi EIj = 。

定义4 转换未执行错误指，预期转换未执行，表现即是输出为空，状态未迁移，对应的可疑转换用unexec表示。

定义5 测试套用TS（Test Suits）表示，预期输出用o表示，实际输出用 表示。若某步输入对应的预期输出与实际输出不一致，即 ，则称为症状[3]（symptom）。

定义6 所有症状对应同一个可疑转换，则将该可疑转换称为唯一可疑转换[3]（ust），由该唯一可疑转换产生的实际输出则可称作唯一症状输出（uso）。

定义7 观察到某个症状e之前测试序列演变而成的测试用例所经过的转换，构成该症状的冲突集[3]，记为CS（e）。

定义8 标号x/y的头状态集合H（x/y）[6]，表示标号为x/y的转换的头状态集合，相应的尾状态集合为E（x/y）。

定义9 本文定义3种类型错误，也就是错误模型，分述如下：

1）输出错误。即实际输出的结果（包括输出为空的情况）与预期结果不一致；

2）转换错误。即实际转换到达的状态与预期到达的状态不一致[3]；

3）转换未执行错误。

2 错误诊断算法

新的错误诊断方法分为3个主要部分，具体则为预处理、确定所有的错误可能以及区分错误。下面针对每一部分，本文提出完整详尽设计。

2.1 预处理

预处理重点包括以下几步：

第1步：对所有用例生成预期转换序列和预期输出。

第2步：对2个状态机生成内部转换集合TI、外部转换集合TE以及不可转换集合T-，并生成I集合（包括IE集合和II集合）和O集合（包括OE集合和OI集合）。

第3步：比较每个用例的预期输出和实际输出，生成所有的症状，并将TS分为所有的带症状的用例集TSs以及所有不带症状的用例集 TSs。

第4步：对初始症状产生冲突集CS，再取这些冲突集的交集为初始候选集（initial tentative candidate set，ITC），简称候选集。

2.2 确定所有的错误可能

确定所有的错误可能，分别按照外部输出错误、转换未执行错误、内部转换输出错误和转换错误的顺序验证。具体如下：

第5步：确定外部转换输出错误。当是外部转换输出错误时，其产生的症状输出相同，且对应的转换一致。对于存在ust的情况，首先在所有带症状的用例中，验证所有所有症状对应的输出是否均为uso：若是，接着在所有不带症状的用例中，验证是否存在ust；若不存在，则确定该ust为外部转换输出错误。算法1实现过程如下。

算法1

算法输入： CFSM，TS，用例实际输出，ust

算法输出： ustset

Procedure ust-processing（ust）

（1） 设置flag为true

（2） 判断所有症状是否对应唯一转换；

（3） 若否，则设置flag为false，退出；

（4） 若是，判断该转换是否为外部转换；

（5） 若否，则设置flag为false，退出；

（6） 若是，检查所有症状输出是否相等；

（7） 若否，则设置flag为false，退出。

（8） 若相等，检查不带症状的用例的转换序列中是否包含ust；

（9） 若包含，设置flag为false，退出；

（10） 如果flag为true，ustset={ust}。

第6步：确定转换未执行错误。若发生转换未执行错误，则转换对应的输出为空，对于外部转换，由于外部转换均存在输出，如果其发生转换未执行错误，则立即输出错误（即出现症状）；但对于内部转换，由于内部转换接下来的外部转换有可能是不可执行的转换（即预期输出为空），其后的输出既有可能出现症状，也有可能并不出现。故简单通过初始症状来判断错误的转换。

对于ITC中的转换，应先验证其在每个用例中第一次出现时的输出是否为空，若不为空，则将其排除；若为空，则将该转换输出置为空，尾状态置为头状态的一个外部转换，代入到包含该转换的用例中，查看输出与实际输出是否一致，如果一致，则保存该转换，否则排除。具体算法如下。

算法2

算法输入： CFSM，TS，用例实际输出，ITC

算法输出： unexec

Procedure unexec-processing（ITC）

（1） 对于ITC中的转换tk，在带症状的用例中，验证其首次出现时对应的输出；

（2） 若存在不为“-”，则转向（1）中下一个转换tk+1；

（3） 若都为“-”，将tk置为“-”，尾状态置为头状态，代入到带tk的用例中，验证输出与实际输出是否一致；

（4） 若一致，unexec={tk}

（5） 若不一致，则退出。

第7步：确定内部转换输出错误。当出现内部转换输出错误时，由于内部转换输出不可见，可能导致接下来另一个状态机转换错误。对于在ITC中的转换tk，由于其内部输出集合OI是确定的，故将OI中的每一项逐项替换掉该内部转换的输出，在带有该内部转换的用例中验证输出是否和观察到的结果相同。若相同，记录该转换和对应的输出。算法设计可表述如下。

算法3

算法输入： CFSM，TS，用例实际输出，ITC

算法输出： ITCou，output

Procedure findoutputs（ITCi）/*i代表状态机编号，i=1，2*/

（1） 对于ITCi中转换，找出其中内部转换tk；

（2） 生成i状态机内部转换所有输出集合Oi；

（3） 将tk的输出置为ok（ok是Oi中首个元素）；

（4） 将更改后的转换代入到包含该转换的用例中，验证输出与实际输出是否一致；

（5） 若不一致，换下一个ok+1，继续执行（4），直到验证完毕，换下一个tk+1继续（3）-（5）的过程；

（6） 若一致，ITCoui ={tk}，outputk={ok}

第8步：确定转换错误。

在此，需要考虑对错误尾状态诊断集进行缩减，主要利用可疑转换的下一步信息。与单FSM错误定位不同的是，在CFSM模型中，下一步的输入输出未必会在同一个状态机下，所以也无法判定是否对应着一个转换。但只要确认下一步的输出是从该可疑转换尾状态开始的，就能根据该输出信息反推回去得到可疑转换的尾状态。由CFSM的特性知，该转换到达尾状态后，只有在接收到的输入对应的是其所在状态机内部转换时，该转换的下一步转换及尾状态是未知的。如果下一步输出为空，由于不知道从哪个状态开始转换，且无法判断哪个状态机的输出为空（均无输出），故应找到所有输出为空的情况所对应的头状态。其它情况都可以根据输出来推断可能的尾状态，具体见算法4。另外由于某转换发生了转换错误，不管是内部转换还是外部转换，由于转换错误在该步并未引起输出错误，所以不会产生症状，若ITC中包含初始症状对应的转换，则需将该转换去掉。简单地说，上述过程是根据可疑转换的下一步输入输出信息得到下一步可能的头状态集，即得到该转换的可疑尾状态集。

在缩小了错误尾状态候选集后，将可疑转换的尾状态替换为错误尾状态集中的元素，代入到包含该可疑转换的用例中。如果输出与用例实际输出相同，则判断出该转换可能是转换错误，且错误的尾状态为该尾状态。若不同，则去掉该尾状态，继续判断下一个尾状态。算法设计流程如下。

算法4

算法输入： CFSM，TS，用例实际输出，ITC

算法输出： ITCtri，endstate

Procedure findendstate（ITCi）/*i代表状态机编号，i=1，2*/

（1） 对于ITCi中的转换tk，去掉其中初始症状对应的转换；

（2） 在所有用例中，找到（1）中转换首次出现的位置的下一步输入a和输出b，做如下判断和处理；

（a）如果a属于状态机i，b属于状态机i，记录这个转换a/b；

（b）如果a属于状态机i，b属于另一状态机，则找到b在状态机j中对应的所有可能的输入c，记录c；/*c为状态机i内部转换的输出*/

（c）如果a属于状态机j，b属于状态机i，记录b；

（d）如果a属于状态机j，b属于另一状态机，转到该用例的下一步输入输出，继续（a）～（d）步判断；

（e）如果a属于状态机j，b为空，则对空输出执行（b）～（c）处理。

（3） 取上一步记录的转换和输出，生成可能的头状态集合，取这些集合的交集S；

（4） 将tk尾状态置为S中的状态sk，代入到包含tk的用例中，检查输出与实际输出是否一致；

（5） 若不一致，则转（1）中下一个转换tk+1；

（6） 若一致，则ITCtri={tk}，endstatek={sk}。

2.3 区分错误

区分错误，即在可能的错误集合中找到唯一的错误。

第9步：当经过以上步骤之后诊断出多种错误可能，接下来需要结合主动测试，通过附加的测试用例，诊断出哪种可能是唯一的错误。

不管最后可能的错误集合中是多种类型的可能错误，还是同一类型多个可能的错误，结合主动测试设计用例时都是对每个可能错误而言的。借鉴测试用例生成的UIO方法和DS方法[2]，该步方法旨在是找到这样的差异转换序列，序列能反应错误转换与预期转换的不同输出，而且该差异转换序列不能经过其它可疑转换。对于外部转换输出错误，生成只包含该可疑转换（不包含其它可疑转换，下同）的用例；对于转换未执行错误，生成只包含该可疑转换且在该步预期输出不为空的用例；对于内部转换输出错误和转换错误，生成只包含该可疑转换且在该步预期输出与错误后的输出不同的用例。

对于必须经过其它可疑转换的情况，可以先去验证其必须经过的转换，以此类推。这样每个判断后的转换会有明确的结果（即是否是该唯一错误），后面的转换在进行判断时不需要再将判断后的转换当做是可疑转换，于是所有错误可能都可以进行判断。如果同一个转换有多种类型的错误可能时，则要把这些错误可能汇总起来综合考虑，找到差异输出，从而进行用例设计。

3 实例

如图 2所示，是一个CFSM的描述演示，对于状态无法处理的转换及转换未执行的情况，统一表示为一个输出为“-”，并实现自迁移的一个外部转换，图中用虚线表示。内部转换用加粗实线表示，外部转换用正常实线表示。假设有随机生成的测试套TS={rafbefc，raedbfc，rbeabfa，rbfecda，rcbefad，rcfeaeb}，r表示reset，即每测试一个用例之前均要先重置CFSM。假设t3发生转换未执行错误，结果如图 3所示。

第二步，确定所有错误可能。由于症状对应外部转换不唯一，故不是外部转换输出错误。在包含t3的用例中t3首次出现位置对应的输出都为空，将t3置为 ，代入到包含t3的用例中，得到输出与实际输出一致，说明t3为转换未执行错误是可能的。在tc1中t5首次出现位置输出不为空，故排除t5未执行的可能。

接着判断是否存在内部转换输出错误。ITC中t3是内部转换，OI2={b，c}，故将t3置为 ，代入到包含t3的用例中，在tc1中输出与实际输出一致，在tc3中，第2步输出为e，与实际的输出不一致。故不是内部转换输出错误。

最后判断是否存在转换错误。由于t3和t5在tc5中为初始症状对应的外部转换，且在该步均为首次出现，故两转换不可能为转换错误，排除是转换错误的可能。

由于排除了其它所有可能，而错误唯一，故确定最终的错误为t3发生转换未执行错误，无需再进行第三步。诊断结束。

本例中若TS不包含tc3，则在进行内部转换输出错误验证时，t3错误的输出为c，代入到tc1、tc5和tc6的输出与实际输出都一致，即t3输出错误是可能的。于是存在2个错误可能：t3未转换或者t3输出错误。下面进行区分错误。可以发现M1中s0对输入c的预期是有输出的，如果t3发生输出错误，则对应有输出，如果t3发生未转换错误，则输出为空，故可以直接简单地设计用例为re，输出为空，故不是t3输出错误，而是未转换错误。

4 结束语

本文对通信状态机提出了一种新的问题模型，新的模型考虑到输出为空和转换不可执行的情况，更接近真实应用。而且该模型下的测试用例可以随机生成，无需考虑到状态机的逻辑是否正确，这样对状态机实际测试时的冒烟测试[ ]和随机测试有很大帮助。算法利用统计学方法和数据依赖的思想，充分利用某转换在所有用例中的下一步输入输出信息，缩小了候选诊断集。另外在候选集验证时，只对带可疑转换的用例执行验证，使算法更趋高效。通过实例可以看出，算法过程简单有效，能准确地诊断出错误结果。

本文的错误诊断算法只适用于单个错误的定位，在后续研究中，将考虑多个错误的诊断并进一步分析在多种状态机模型上的显示功能应用。