賈家濤 曲明成 吳翔虎

摘 要 目前對(duì)于通信狀態(tài)機(jī)的研究已經(jīng)很廣泛，但對(duì)于通信狀態(tài)機(jī)的錯(cuò)誤診斷方法的研究不多，已有的問(wèn)題模型都是輸出錯(cuò)誤和轉(zhuǎn)換錯(cuò)誤。為了更好的將錯(cuò)誤診斷與實(shí)際相結(jié)合，本文在一般的通信有限狀態(tài)機(jī)模型上，新增了一種不可執(zhí)行的情況，并在傳統(tǒng)的問(wèn)題模型中新增一種轉(zhuǎn)換未執(zhí)行錯(cuò)誤的問(wèn)題模型。在假設(shè)單個(gè)錯(cuò)誤的情況下，提出了一整套新的錯(cuò)誤診斷算法，算法通過(guò)分析癥狀信息進(jìn)行分步檢測(cè)，并利用可疑轉(zhuǎn)換下一步輸入輸出和用例的轉(zhuǎn)換序列等信息來(lái)定位出單個(gè)錯(cuò)誤。最后，文中給出一個(gè)實(shí)例，詳細(xì)描述了算法的診斷過(guò)程。

關(guān)鍵字：通信狀態(tài)機(jī)；單個(gè)錯(cuò)誤；錯(cuò)誤診斷算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：

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 引言

錯(cuò)誤定位技術(shù)是軟件調(diào)試中的熱點(diǎn)和難點(diǎn)問(wèn)題。隨著通信網(wǎng)絡(luò)的發(fā)展，越來(lái)越多的通信軟硬件設(shè)計(jì)模型都基于狀態(tài)機(jī)來(lái)提供研發(fā)、并獲實(shí)現(xiàn)。在狀態(tài)機(jī)測(cè)試方法研究方面，文獻(xiàn)[ ]給出了狀態(tài)機(jī)測(cè)試的基本準(zhǔn)則和一般方法。目前有關(guān)狀態(tài)機(jī)測(cè)試的研究更多地集中在如何設(shè)計(jì)與生成測(cè)試用例的方法上，常用的測(cè)試用例生成方法有W方法，Wp方法，UIO方法和DS方法[ ]等。這些方法的研究目的在于發(fā)現(xiàn)錯(cuò)誤，然而在檢測(cè)到錯(cuò)誤后，如何根據(jù)錯(cuò)誤信息而得出錯(cuò)誤診斷則是目前亟待研究的一個(gè)現(xiàn)實(shí)實(shí)用課題。本文即針對(duì)這一課題展開設(shè)計(jì)論述。

Ghedamsi最早研究這一問(wèn)題，在輸出錯(cuò)誤、轉(zhuǎn)換錯(cuò)誤這2種錯(cuò)誤以及單個(gè)錯(cuò)誤的前提下，給出了一種普遍問(wèn)題定義和解決辦法，并對(duì)單個(gè)狀態(tài)機(jī)上創(chuàng)建了錯(cuò)誤診斷算法[ ]，隨后將該算法思想擴(kuò)展到通信有限狀態(tài)機(jī)模型上[ ]，該套理論是后續(xù)研究者們的重要參考。Miller將CFSM模型用于網(wǎng)絡(luò)協(xié)議的被動(dòng)測(cè)試中，證明了其成果實(shí)施有效性[ ]。錢蘭在文獻(xiàn)[ ]中提出了單狀態(tài)機(jī)錯(cuò)誤診斷的2個(gè)改進(jìn)算法，縮小了錯(cuò)誤診斷集合，并提高了時(shí)間復(fù)雜度。

由于文獻(xiàn)[3]所研究的狀態(tài)機(jī)中每個(gè)狀態(tài)對(duì)于輸入都存在轉(zhuǎn)換，在設(shè)計(jì)用例時(shí)也需要考慮到狀態(tài)機(jī)能正確實(shí)現(xiàn)轉(zhuǎn)換。考慮到這些限制，結(jié)合狀態(tài)機(jī)實(shí)際特點(diǎn)，本文在CFSM模型中增加了輸入在狀態(tài)中無(wú)法轉(zhuǎn)換的情況，并提出新的問(wèn)題模型，即轉(zhuǎn)換不可執(zhí)行錯(cuò)誤。結(jié)合程序錯(cuò)誤定位技術(shù)中的統(tǒng)計(jì)學(xué)方法、數(shù)據(jù)挖掘方法以及分析數(shù)據(jù)依賴等方法[ ]，在Ghedamsi和錢蘭的方法基礎(chǔ)上，對(duì)CFSM提出一種改進(jìn)的錯(cuò)誤診斷算法。與之前的方法相比，本文的算法更清晰高效，而且能給出完整的錯(cuò)誤診斷信息。

1 CFSM模型及問(wèn)題定義

一個(gè)通信狀態(tài)機(jī)（Communicating Finit State Machine，CFSM）系統(tǒng)由一組確定有限狀態(tài)機(jī)（Deterministic Finit State Machine，DFSM）具體構(gòu)成，每個(gè)確定狀態(tài)機(jī)除了各自擁有的外部端口之外，還可以通過(guò)內(nèi)部輸入隊(duì)列實(shí)現(xiàn)相互間的通信。

本文研究的問(wèn)題是2個(gè)狀態(tài)機(jī)的情況，如圖 1所示。測(cè)試通道利用P1、P2端口向2個(gè)狀態(tài)機(jī)傳送輸入，2個(gè)狀態(tài)機(jī)通過(guò)內(nèi)部通道q1、q2實(shí)現(xiàn)信息傳輸。而且，2個(gè)狀態(tài)機(jī)的外部輸出也仍是通過(guò)P1、P2端口傳遞至測(cè)試通道，研究者可以由此觀察到測(cè)試通道中的輸入輸出信息。

假設(shè)每個(gè)輸入都有足夠的時(shí)間來(lái)執(zhí)行并得到輸出，這樣每一時(shí)刻系統(tǒng)中只有一個(gè)消息在傳遞。同時(shí)為了防止問(wèn)題過(guò)于復(fù)雜，研究假設(shè)系統(tǒng)的內(nèi)部轉(zhuǎn)換產(chǎn)生輸出到另一個(gè)狀態(tài)機(jī)后，該輸出將不再引起內(nèi)部轉(zhuǎn)換。

定義1 確定有限狀態(tài)機(jī)M是一個(gè)六元組：M=（I，O，S， ， ），I表示輸入集合，O表示輸出集合，S表示狀態(tài)集合，而且包括一個(gè)系統(tǒng)初始狀態(tài)s0， ：S I S是狀態(tài)轉(zhuǎn)移函數(shù)， ：S I O是輸出函數(shù)，本文用 的形式表示一個(gè)轉(zhuǎn)換。

定義2 轉(zhuǎn)換的輸出結(jié)果通過(guò)內(nèi)部端口到達(dá)另一個(gè)狀態(tài)機(jī)，這樣的轉(zhuǎn)換稱為內(nèi)部轉(zhuǎn)換。轉(zhuǎn)換輸出通過(guò)外部端口向外傳輸，這樣的轉(zhuǎn)換稱為外部轉(zhuǎn)換。

定義3 輸入序列用Ii表示，分為2個(gè)部分，即Ii=IEi IIi（下標(biāo)表示狀態(tài)機(jī)編號(hào)），IEi表示產(chǎn)生外部輸出的輸入。IIi表示產(chǎn)生內(nèi)部輸出的輸入。類似的，輸出序列用Oi表示，也可以分為兩個(gè)子部分，即Oi= OEi OIi。OEi表示產(chǎn)生的外部輸出，OIi表示產(chǎn)生的內(nèi)部輸出。由假設(shè)OIj IEi且IIi EIj = 。

定義4 轉(zhuǎn)換未執(zhí)行錯(cuò)誤指，預(yù)期轉(zhuǎn)換未執(zhí)行，表現(xiàn)即是輸出為空，狀態(tài)未遷移，對(duì)應(yīng)的可疑轉(zhuǎn)換用unexec表示。

定義5 測(cè)試套用TS（Test Suits）表示，預(yù)期輸出用o表示，實(shí)際輸出用 表示。若某步輸入對(duì)應(yīng)的預(yù)期輸出與實(shí)際輸出不一致，即 ，則稱為癥狀[3]（symptom）。

定義6 所有癥狀對(duì)應(yīng)同一個(gè)可疑轉(zhuǎn)換，則將該可疑轉(zhuǎn)換稱為唯一可疑轉(zhuǎn)換[3]（ust），由該唯一可疑轉(zhuǎn)換產(chǎn)生的實(shí)際輸出則可稱作唯一癥狀輸出（uso）。

定義7 觀察到某個(gè)癥狀e之前測(cè)試序列演變而成的測(cè)試用例所經(jīng)過(guò)的轉(zhuǎn)換，構(gòu)成該癥狀的沖突集[3]，記為CS（e）。

定義8 標(biāo)號(hào)x/y的頭狀態(tài)集合H（x/y）[6]，表示標(biāo)號(hào)為x/y的轉(zhuǎn)換的頭狀態(tài)集合，相應(yīng)的尾狀態(tài)集合為E（x/y）。

定義9 本文定義3種類型錯(cuò)誤，也就是錯(cuò)誤模型，分述如下：

1）輸出錯(cuò)誤。即實(shí)際輸出的結(jié)果（包括輸出為空的情況）與預(yù)期結(jié)果不一致；

2）轉(zhuǎn)換錯(cuò)誤。即實(shí)際轉(zhuǎn)換到達(dá)的狀態(tài)與預(yù)期到達(dá)的狀態(tài)不一致[3]；

3）轉(zhuǎn)換未執(zhí)行錯(cuò)誤。

2 錯(cuò)誤診斷算法

新的錯(cuò)誤診斷方法分為3個(gè)主要部分，具體則為預(yù)處理、確定所有的錯(cuò)誤可能以及區(qū)分錯(cuò)誤。下面針對(duì)每一部分，本文提出完整詳盡設(shè)計(jì)。

2.1 預(yù)處理

預(yù)處理重點(diǎn)包括以下幾步：

第1步：對(duì)所有用例生成預(yù)期轉(zhuǎn)換序列和預(yù)期輸出。

第2步：對(duì)2個(gè)狀態(tài)機(jī)生成內(nèi)部轉(zhuǎn)換集合TI、外部轉(zhuǎn)換集合TE以及不可轉(zhuǎn)換集合T-，并生成I集合（包括IE集合和II集合）和O集合（包括OE集合和OI集合）。

第3步：比較每個(gè)用例的預(yù)期輸出和實(shí)際輸出，生成所有的癥狀，并將TS分為所有的帶癥狀的用例集TSs以及所有不帶癥狀的用例集 TSs。

第4步：對(duì)初始癥狀產(chǎn)生沖突集CS，再取這些沖突集的交集為初始候選集（initial tentative candidate set，ITC），簡(jiǎn)稱候選集。

2.2 確定所有的錯(cuò)誤可能

確定所有的錯(cuò)誤可能，分別按照外部輸出錯(cuò)誤、轉(zhuǎn)換未執(zhí)行錯(cuò)誤、內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤和轉(zhuǎn)換錯(cuò)誤的順序驗(yàn)證。具體如下：

第5步：確定外部轉(zhuǎn)換輸出錯(cuò)誤。當(dāng)是外部轉(zhuǎn)換輸出錯(cuò)誤時(shí)，其產(chǎn)生的癥狀輸出相同，且對(duì)應(yīng)的轉(zhuǎn)換一致。對(duì)于存在ust的情況，首先在所有帶癥狀的用例中，驗(yàn)證所有所有癥狀對(duì)應(yīng)的輸出是否均為uso：若是，接著在所有不帶癥狀的用例中，驗(yàn)證是否存在ust；若不存在，則確定該ust為外部轉(zhuǎn)換輸出錯(cuò)誤。算法1實(shí)現(xiàn)過(guò)程如下。

算法1

算法輸入： CFSM，TS，用例實(shí)際輸出，ust

算法輸出： ustset

Procedure ust-processing（ust）

（1） 設(shè)置flag為true

（2） 判斷所有癥狀是否對(duì)應(yīng)唯一轉(zhuǎn)換；

（3） 若否，則設(shè)置flag為false，退出；

（4） 若是，判斷該轉(zhuǎn)換是否為外部轉(zhuǎn)換；

（5） 若否，則設(shè)置flag為false，退出；

（6） 若是，檢查所有癥狀輸出是否相等；

（7） 若否，則設(shè)置flag為false，退出。

（8） 若相等，檢查不帶癥狀的用例的轉(zhuǎn)換序列中是否包含ust；

（9） 若包含，設(shè)置flag為false，退出；

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

第6步：確定轉(zhuǎn)換未執(zhí)行錯(cuò)誤。若發(fā)生轉(zhuǎn)換未執(zhí)行錯(cuò)誤，則轉(zhuǎn)換對(duì)應(yīng)的輸出為空，對(duì)于外部轉(zhuǎn)換，由于外部轉(zhuǎn)換均存在輸出，如果其發(fā)生轉(zhuǎn)換未執(zhí)行錯(cuò)誤，則立即輸出錯(cuò)誤（即出現(xiàn)癥狀）；但對(duì)于內(nèi)部轉(zhuǎn)換，由于內(nèi)部轉(zhuǎn)換接下來(lái)的外部轉(zhuǎn)換有可能是不可執(zhí)行的轉(zhuǎn)換（即預(yù)期輸出為空），其后的輸出既有可能出現(xiàn)癥狀，也有可能并不出現(xiàn)。故簡(jiǎn)單通過(guò)初始癥狀來(lái)判斷錯(cuò)誤的轉(zhuǎn)換。

對(duì)于ITC中的轉(zhuǎn)換，應(yīng)先驗(yàn)證其在每個(gè)用例中第一次出現(xiàn)時(shí)的輸出是否為空，若不為空，則將其排除；若為空，則將該轉(zhuǎn)換輸出置為空，尾狀態(tài)置為頭狀態(tài)的一個(gè)外部轉(zhuǎn)換，代入到包含該轉(zhuǎn)換的用例中，查看輸出與實(shí)際輸出是否一致，如果一致，則保存該轉(zhuǎn)換，否則排除。具體算法如下。

算法2

算法輸入： CFSM，TS，用例實(shí)際輸出，ITC

算法輸出： unexec

Procedure unexec-processing（ITC）

（1） 對(duì)于ITC中的轉(zhuǎn)換tk，在帶癥狀的用例中，驗(yàn)證其首次出現(xiàn)時(shí)對(duì)應(yīng)的輸出；

（2） 若存在不為“-”，則轉(zhuǎn)向（1）中下一個(gè)轉(zhuǎn)換tk+1；

（3） 若都為“-”，將tk置為“-”，尾狀態(tài)置為頭狀態(tài)，代入到帶tk的用例中，驗(yàn)證輸出與實(shí)際輸出是否一致；

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

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

第7步：確定內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤。當(dāng)出現(xiàn)內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤時(shí)，由于內(nèi)部轉(zhuǎn)換輸出不可見，可能導(dǎo)致接下來(lái)另一個(gè)狀態(tài)機(jī)轉(zhuǎn)換錯(cuò)誤。對(duì)于在ITC中的轉(zhuǎn)換tk，由于其內(nèi)部輸出集合OI是確定的，故將OI中的每一項(xiàng)逐項(xiàng)替換掉該內(nèi)部轉(zhuǎn)換的輸出，在帶有該內(nèi)部轉(zhuǎn)換的用例中驗(yàn)證輸出是否和觀察到的結(jié)果相同。若相同，記錄該轉(zhuǎn)換和對(duì)應(yīng)的輸出。算法設(shè)計(jì)可表述如下。

算法3

算法輸入： CFSM，TS，用例實(shí)際輸出，ITC

算法輸出： ITCou，output

Procedure findoutputs（ITCi）/*i代表狀態(tài)機(jī)編號(hào)，i=1，2*/

（1） 對(duì)于ITCi中轉(zhuǎn)換，找出其中內(nèi)部轉(zhuǎn)換tk；

（2） 生成i狀態(tài)機(jī)內(nèi)部轉(zhuǎn)換所有輸出集合Oi；

（3） 將tk的輸出置為ok（ok是Oi中首個(gè)元素）；

（4） 將更改后的轉(zhuǎn)換代入到包含該轉(zhuǎn)換的用例中，驗(yàn)證輸出與實(shí)際輸出是否一致；

（5） 若不一致，換下一個(gè)ok+1，繼續(xù)執(zhí)行（4），直到驗(yàn)證完畢，換下一個(gè)tk+1繼續(xù)（3）-（5）的過(guò)程；

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

第8步：確定轉(zhuǎn)換錯(cuò)誤。

在此，需要考慮對(duì)錯(cuò)誤尾狀態(tài)診斷集進(jìn)行縮減，主要利用可疑轉(zhuǎn)換的下一步信息。與單FSM錯(cuò)誤定位不同的是，在CFSM模型中，下一步的輸入輸出未必會(huì)在同一個(gè)狀態(tài)機(jī)下，所以也無(wú)法判定是否對(duì)應(yīng)著一個(gè)轉(zhuǎn)換。但只要確認(rèn)下一步的輸出是從該可疑轉(zhuǎn)換尾狀態(tài)開始的，就能根據(jù)該輸出信息反推回去得到可疑轉(zhuǎn)換的尾狀態(tài)。由CFSM的特性知，該轉(zhuǎn)換到達(dá)尾狀態(tài)后，只有在接收到的輸入對(duì)應(yīng)的是其所在狀態(tài)機(jī)內(nèi)部轉(zhuǎn)換時(shí)，該轉(zhuǎn)換的下一步轉(zhuǎn)換及尾狀態(tài)是未知的。如果下一步輸出為空，由于不知道從哪個(gè)狀態(tài)開始轉(zhuǎn)換，且無(wú)法判斷哪個(gè)狀態(tài)機(jī)的輸出為空（均無(wú)輸出），故應(yīng)找到所有輸出為空的情況所對(duì)應(yīng)的頭狀態(tài)。其它情況都可以根據(jù)輸出來(lái)推斷可能的尾狀態(tài)，具體見算法4。另外由于某轉(zhuǎn)換發(fā)生了轉(zhuǎn)換錯(cuò)誤，不管是內(nèi)部轉(zhuǎn)換還是外部轉(zhuǎn)換，由于轉(zhuǎn)換錯(cuò)誤在該步并未引起輸出錯(cuò)誤，所以不會(huì)產(chǎn)生癥狀，若ITC中包含初始癥狀對(duì)應(yīng)的轉(zhuǎn)換，則需將該轉(zhuǎn)換去掉。簡(jiǎn)單地說(shuō)，上述過(guò)程是根據(jù)可疑轉(zhuǎn)換的下一步輸入輸出信息得到下一步可能的頭狀態(tài)集，即得到該轉(zhuǎn)換的可疑尾狀態(tài)集。

在縮小了錯(cuò)誤尾狀態(tài)候選集后，將可疑轉(zhuǎn)換的尾狀態(tài)替換為錯(cuò)誤尾狀態(tài)集中的元素，代入到包含該可疑轉(zhuǎn)換的用例中。如果輸出與用例實(shí)際輸出相同，則判斷出該轉(zhuǎn)換可能是轉(zhuǎn)換錯(cuò)誤，且錯(cuò)誤的尾狀態(tài)為該尾狀態(tài)。若不同，則去掉該尾狀態(tài)，繼續(xù)判斷下一個(gè)尾狀態(tài)。算法設(shè)計(jì)流程如下。

算法4

算法輸入： CFSM，TS，用例實(shí)際輸出，ITC

算法輸出： ITCtri，endstate

Procedure findendstate（ITCi）/*i代表狀態(tài)機(jī)編號(hào)，i=1，2*/

（1） 對(duì)于ITCi中的轉(zhuǎn)換tk，去掉其中初始癥狀對(duì)應(yīng)的轉(zhuǎn)換；

（2） 在所有用例中，找到（1）中轉(zhuǎn)換首次出現(xiàn)的位置的下一步輸入a和輸出b，做如下判斷和處理；

（a）如果a屬于狀態(tài)機(jī)i，b屬于狀態(tài)機(jī)i，記錄這個(gè)轉(zhuǎn)換a/b；

（b）如果a屬于狀態(tài)機(jī)i，b屬于另一狀態(tài)機(jī)，則找到b在狀態(tài)機(jī)j中對(duì)應(yīng)的所有可能的輸入c，記錄c；/*c為狀態(tài)機(jī)i內(nèi)部轉(zhuǎn)換的輸出*/

（c）如果a屬于狀態(tài)機(jī)j，b屬于狀態(tài)機(jī)i，記錄b；

（d）如果a屬于狀態(tài)機(jī)j，b屬于另一狀態(tài)機(jī)，轉(zhuǎn)到該用例的下一步輸入輸出，繼續(xù)（a）～（d）步判斷；

（e）如果a屬于狀態(tài)機(jī)j，b為空，則對(duì)空輸出執(zhí)行（b）～（c）處理。

（3） 取上一步記錄的轉(zhuǎn)換和輸出，生成可能的頭狀態(tài)集合，取這些集合的交集S；

（4） 將tk尾狀態(tài)置為S中的狀態(tài)sk，代入到包含tk的用例中，檢查輸出與實(shí)際輸出是否一致；

（5） 若不一致，則轉(zhuǎn)（1）中下一個(gè)轉(zhuǎn)換tk+1；

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

2.3 區(qū)分錯(cuò)誤

區(qū)分錯(cuò)誤，即在可能的錯(cuò)誤集合中找到唯一的錯(cuò)誤。

第9步：當(dāng)經(jīng)過(guò)以上步驟之后診斷出多種錯(cuò)誤可能，接下來(lái)需要結(jié)合主動(dòng)測(cè)試，通過(guò)附加的測(cè)試用例，診斷出哪種可能是唯一的錯(cuò)誤。

不管最后可能的錯(cuò)誤集合中是多種類型的可能錯(cuò)誤，還是同一類型多個(gè)可能的錯(cuò)誤，結(jié)合主動(dòng)測(cè)試設(shè)計(jì)用例時(shí)都是對(duì)每個(gè)可能錯(cuò)誤而言的。借鑒測(cè)試用例生成的UIO方法和DS方法[2]，該步方法旨在是找到這樣的差異轉(zhuǎn)換序列，序列能反應(yīng)錯(cuò)誤轉(zhuǎn)換與預(yù)期轉(zhuǎn)換的不同輸出，而且該差異轉(zhuǎn)換序列不能經(jīng)過(guò)其它可疑轉(zhuǎn)換。對(duì)于外部轉(zhuǎn)換輸出錯(cuò)誤，生成只包含該可疑轉(zhuǎn)換（不包含其它可疑轉(zhuǎn)換，下同）的用例；對(duì)于轉(zhuǎn)換未執(zhí)行錯(cuò)誤，生成只包含該可疑轉(zhuǎn)換且在該步預(yù)期輸出不為空的用例；對(duì)于內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤和轉(zhuǎn)換錯(cuò)誤，生成只包含該可疑轉(zhuǎn)換且在該步預(yù)期輸出與錯(cuò)誤后的輸出不同的用例。

對(duì)于必須經(jīng)過(guò)其它可疑轉(zhuǎn)換的情況，可以先去驗(yàn)證其必須經(jīng)過(guò)的轉(zhuǎn)換，以此類推。這樣每個(gè)判斷后的轉(zhuǎn)換會(huì)有明確的結(jié)果（即是否是該唯一錯(cuò)誤），后面的轉(zhuǎn)換在進(jìn)行判斷時(shí)不需要再將判斷后的轉(zhuǎn)換當(dāng)做是可疑轉(zhuǎn)換，于是所有錯(cuò)誤可能都可以進(jìn)行判斷。如果同一個(gè)轉(zhuǎn)換有多種類型的錯(cuò)誤可能時(shí)，則要把這些錯(cuò)誤可能匯總起來(lái)綜合考慮，找到差異輸出，從而進(jìn)行用例設(shè)計(jì)。

3 實(shí)例

如圖 2所示，是一個(gè)CFSM的描述演示，對(duì)于狀態(tài)無(wú)法處理的轉(zhuǎn)換及轉(zhuǎn)換未執(zhí)行的情況，統(tǒng)一表示為一個(gè)輸出為“-”，并實(shí)現(xiàn)自遷移的一個(gè)外部轉(zhuǎn)換，圖中用虛線表示。內(nèi)部轉(zhuǎn)換用加粗實(shí)線表示，外部轉(zhuǎn)換用正常實(shí)線表示。假設(shè)有隨機(jī)生成的測(cè)試套TS={rafbefc，raedbfc，rbeabfa，rbfecda，rcbefad，rcfeaeb}，r表示reset，即每測(cè)試一個(gè)用例之前均要先重置CFSM。假設(shè)t3發(fā)生轉(zhuǎn)換未執(zhí)行錯(cuò)誤，結(jié)果如圖 3所示。

第二步，確定所有錯(cuò)誤可能。由于癥狀對(duì)應(yīng)外部轉(zhuǎn)換不唯一，故不是外部轉(zhuǎn)換輸出錯(cuò)誤。在包含t3的用例中t3首次出現(xiàn)位置對(duì)應(yīng)的輸出都為空，將t3置為 ，代入到包含t3的用例中，得到輸出與實(shí)際輸出一致，說(shuō)明t3為轉(zhuǎn)換未執(zhí)行錯(cuò)誤是可能的。在tc1中t5首次出現(xiàn)位置輸出不為空，故排除t5未執(zhí)行的可能。

接著判斷是否存在內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤。ITC中t3是內(nèi)部轉(zhuǎn)換，OI2={b，c}，故將t3置為 ，代入到包含t3的用例中，在tc1中輸出與實(shí)際輸出一致，在tc3中，第2步輸出為e，與實(shí)際的輸出不一致。故不是內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤。

最后判斷是否存在轉(zhuǎn)換錯(cuò)誤。由于t3和t5在tc5中為初始癥狀對(duì)應(yīng)的外部轉(zhuǎn)換，且在該步均為首次出現(xiàn)，故兩轉(zhuǎn)換不可能為轉(zhuǎn)換錯(cuò)誤，排除是轉(zhuǎn)換錯(cuò)誤的可能。

由于排除了其它所有可能，而錯(cuò)誤唯一，故確定最終的錯(cuò)誤為t3發(fā)生轉(zhuǎn)換未執(zhí)行錯(cuò)誤，無(wú)需再進(jìn)行第三步。診斷結(jié)束。

本例中若TS不包含tc3，則在進(jìn)行內(nèi)部轉(zhuǎn)換輸出錯(cuò)誤驗(yàn)證時(shí)，t3錯(cuò)誤的輸出為c，代入到tc1、tc5和tc6的輸出與實(shí)際輸出都一致，即t3輸出錯(cuò)誤是可能的。于是存在2個(gè)錯(cuò)誤可能：t3未轉(zhuǎn)換或者t3輸出錯(cuò)誤。下面進(jìn)行區(qū)分錯(cuò)誤?？梢园l(fā)現(xiàn)M1中s0對(duì)輸入c的預(yù)期是有輸出的，如果t3發(fā)生輸出錯(cuò)誤，則對(duì)應(yīng)有輸出，如果t3發(fā)生未轉(zhuǎn)換錯(cuò)誤，則輸出為空，故可以直接簡(jiǎn)單地設(shè)計(jì)用例為re，輸出為空，故不是t3輸出錯(cuò)誤，而是未轉(zhuǎn)換錯(cuò)誤。

4 結(jié)束語(yǔ)

本文對(duì)通信狀態(tài)機(jī)提出了一種新的問(wèn)題模型，新的模型考慮到輸出為空和轉(zhuǎn)換不可執(zhí)行的情況，更接近真實(shí)應(yīng)用。而且該模型下的測(cè)試用例可以隨機(jī)生成，無(wú)需考慮到狀態(tài)機(jī)的邏輯是否正確，這樣對(duì)狀態(tài)機(jī)實(shí)際測(cè)試時(shí)的冒煙測(cè)試[ ]和隨機(jī)測(cè)試有很大幫助。算法利用統(tǒng)計(jì)學(xué)方法和數(shù)據(jù)依賴的思想，充分利用某轉(zhuǎn)換在所有用例中的下一步輸入輸出信息，縮小了候選診斷集。另外在候選集驗(yàn)證時(shí)，只對(duì)帶可疑轉(zhuǎn)換的用例執(zhí)行驗(yàn)證，使算法更趨高效。通過(guò)實(shí)例可以看出，算法過(guò)程簡(jiǎn)單有效，能準(zhǔn)確地診斷出錯(cuò)誤結(jié)果。

本文的錯(cuò)誤診斷算法只適用于單個(gè)錯(cuò)誤的定位，在后續(xù)研究中，將考慮多個(gè)錯(cuò)誤的診斷并進(jìn)一步分析在多種狀態(tài)機(jī)模型上的顯示功能應(yīng)用。