一種改進(jìn)的通信有限狀態(tài)機(jī)的錯誤診斷方法

賈家濤 曲明成 吳翔虎

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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 引言

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

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

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

1 CFSM模型及問題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 錯誤診斷算法

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

2.1 預(yù)處理

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

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

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

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

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

2.2 確定所有的錯誤可能

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

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

算法1

算法輸入： CFSM，TS，用例實際輸出，ust

算法輸出： ustset

Procedure ust-processing（ust）

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

（2） 判斷所有癥狀是否對應(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í)行錯誤。若發(fā)生轉(zhuǎn)換未執(zhí)行錯誤，則轉(zhuǎn)換對應(yīng)的輸出為空，對于外部轉(zhuǎn)換，由于外部轉(zhuǎn)換均存在輸出，如果其發(fā)生轉(zhuǎn)換未執(zhí)行錯誤，則立即輸出錯誤（即出現(xiàn)癥狀）；但對于內(nèi)部轉(zhuǎn)換，由于內(nèi)部轉(zhuǎn)換接下來的外部轉(zhuǎn)換有可能是不可執(zhí)行的轉(zhuǎn)換（即預(yù)期輸出為空），其后的輸出既有可能出現(xiàn)癥狀，也有可能并不出現(xiàn)。故簡單通過初始癥狀來判斷錯誤的轉(zhuǎn)換。

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

算法2

算法輸入： CFSM，TS，用例實際輸出，ITC

算法輸出： unexec

Procedure unexec-processing（ITC）

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

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

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

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

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

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

算法3

算法輸入： CFSM，TS，用例實際輸出，ITC

算法輸出： ITCou，output

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

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

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

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

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

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

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

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

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

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

算法4

算法輸入： CFSM，TS，用例實際輸出，ITC

算法輸出： ITCtri，endstate

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

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

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

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

（b）如果a屬于狀態(tài)機(jī)i，b屬于另一狀態(tài)機(jī)，則找到b在狀態(tài)機(jī)j中對應(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為空，則對空輸出執(zhí)行（b）～（c）處理。

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

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

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

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

2.3 區(qū)分錯誤

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

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

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

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

3 實例

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

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

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

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

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

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

4 結(jié)束語

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

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