一種改進的通信有限狀態機的錯誤診斷方法

賈家濤 曲明成 吳翔虎

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

關鍵字：通信狀態機；單個錯誤；錯誤診斷算法

中圖分類號：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 結束語

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

本文的錯誤診斷算法只適用于單個錯誤的定位，在后續研究中，將考慮多個錯誤的診斷并進一步分析在多種狀態機模型上的顯示功能應用。