基于動態(tài)聚類的有限狀態(tài)機(jī)多錯誤診斷

崔 玲, 張建標(biāo),3

(1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124；2.可信計算北京市重點實驗室，北京 100124；3.信息安全等級保護(hù)關(guān)鍵技術(shù)國家工程實驗室，北京 100124)

近年來，基于人工智能的錯誤診斷成為研究熱點. Li等[1]提出基于深度學(xué)習(xí)的齒輪故障診斷方法；Shi等[2]提出基于數(shù)據(jù)挖掘的航空電子系統(tǒng)故障診斷方法；文成林等[3]對基于深度學(xué)習(xí)的故障診斷方法進(jìn)行了綜述. 但是，目前研究多是基于單個錯誤的假設(shè). 有關(guān)多錯誤診斷的研究多集中在軟件錯誤定位方面，如基于數(shù)據(jù)挖掘的多錯誤定位[4-5]、基于程序切片的多錯誤定位[6]、基于聚類分析的多錯誤定位[7]等.

與軟件的錯誤定位方法不同，對于基于有限狀態(tài)機(jī)(finite state machine，F(xiàn)SM)的錯誤診斷研究不僅是定位錯誤，而且要找出錯誤原因并進(jìn)行修正. 診斷的主要思想是枚舉所有可能的錯誤，然后根據(jù)相關(guān)信息排除一些候選錯誤，從而生成錯誤診斷集. 由于枚舉數(shù)量過于龐大，基于FSM的錯誤診斷也多是針對單錯誤的方法，而且研究多是針對具體系統(tǒng)[8-9]. Lee等[10]和Ghedamsi等[11]提出了基于FSM單個錯誤的通用診斷方法，而基于FSM的多個錯誤的診斷問題還沒有有效可行的通用方法.

本文將聚類分析方法應(yīng)用到基于FSM的錯誤診斷中，提出基于動態(tài)聚類分析的多錯誤診斷方法，將失敗用例分類成簇，以期每簇只存在一個錯誤，進(jìn)而實現(xiàn)多錯誤診斷.

1 基礎(chǔ)術(shù)語

定義1轉(zhuǎn)換錯誤

定義2輸出錯誤

假設(shè)已有測試序列集C={c1,c2,…,cn}，其中每個cm都是一個測試序列，對應(yīng)輸入序列im={im1,im2,…,imp},預(yù)期輸出序列om={om1,om2,…,omp},實際輸出序列o′m={o′m1,o′m2,…,o′mp}.通常，若某個測試序列的實際輸出與預(yù)期輸出不相符，則稱之為失敗用例，簡稱反例；反之簡稱證例.

定義3初始癥狀[12]

若在oi和o′i中有oij≠o′ij且對任意1≤k≤j有oik=o′ik，則稱oij≠o′ij為初始癥狀，記為e0.

定義4沖突集[11]

在某個癥狀e之前測試序列所經(jīng)過的轉(zhuǎn)換稱為該癥狀的沖突集(conflict set)，記為SC(e).

定義5沖突序列

稱某個癥狀e的沖突集對應(yīng)的測試輸入序列段為沖突序列(conflict sequence).

2 多錯誤診斷方法

基于聚類分析的軟件多錯誤定位方法主要分為3個步驟：首先，根據(jù)聚類算法將程序失敗用例進(jìn)行聚類；然后，使用Tarantula方法[13]計算每條語句發(fā)生錯誤的可疑度；最后，按照可疑度降序排名人工檢查程序代碼，從而完成程序錯誤定位.

本文提出的診斷方法中聚類方法為動態(tài)聚類，首先進(jìn)行初始分類，在分析過程中進(jìn)行再次聚類.

由定義可知，初始癥狀沖突集中必定至少包含一個錯誤，而FSM的執(zhí)行軌跡總是從初始狀態(tài)開始，那么具有相同的初始癥狀沖突集的反例發(fā)生的錯誤必定相同. 因此，初始分類時可將具有相同的初始癥狀沖突集的反例聚類. 其次，一個錯誤轉(zhuǎn)換可能出現(xiàn)在不同的初始癥狀沖突集中，在分析該轉(zhuǎn)換時，將所有初始癥狀沖突集包含該轉(zhuǎn)換的反例聚類，然后進(jìn)行錯誤診斷.

2.1 可疑度計算

多錯誤診斷復(fù)雜的地方在于，如果錯誤類別是轉(zhuǎn)換錯誤，那么錯誤是具有傳遞性的，也就是說，初始癥狀之后的癥狀可能是由產(chǎn)生初始癥狀的錯誤引起的. 一般來說，具有相同初始癥狀沖突集的反例越多，其錯誤越容易被診斷；反例中的癥狀數(shù)越少，其錯誤越容易被診斷. 因此，在診斷過程中，可按照初始癥狀沖突集的可疑度降序分析其中的轉(zhuǎn)換. 初始癥狀沖突集的可疑度計算方法為

(1)

式中：SSC(e0)表示初始癥狀沖突集的可疑度；FSC(e0)表示包含初始癥狀沖突集SC(e0)的反例個數(shù)；FT表示總的反例個數(shù).

轉(zhuǎn)換可疑度的計算基于這樣一個常理：出現(xiàn)次數(shù)越多，越容易被發(fā)現(xiàn).初始癥狀沖突集中每個轉(zhuǎn)換的可疑度計算方法為

(2)

式(2)在Tarantula公式基礎(chǔ)上進(jìn)行了改進(jìn).由定義可知，初始癥狀是測試用例中第1個出現(xiàn)錯誤的位置，該位置的轉(zhuǎn)換發(fā)生錯誤的可能性最大，其次是初始癥狀之前的轉(zhuǎn)換.在初始癥狀沖突集中，轉(zhuǎn)換t距離初始癥狀越近，系數(shù)r值越大，可疑度就越大，表明發(fā)生錯誤的可能性越大.

2.2 診斷步驟

多錯誤診斷模型如圖1所示，具體包括以下幾個步驟.

圖1 多錯誤診斷模型Fig.1 Multiple-fault diagnosis model

1) 比較預(yù)期輸出和實際輸出，將測試集分為證例和反例，生成癥狀和初始癥狀，并為每個初始癥狀產(chǎn)生沖突集及沖突序列.

2) 生成初始診斷集. 求所有初始癥狀沖突集的交集，作為初始診斷集. 如果初始診斷集不為空，則表明系統(tǒng)錯誤就在初始診斷集中.

3) 初始聚類，并計算可疑度. 若初始診斷集不為空，則計算初始診斷集中各轉(zhuǎn)換的可疑度；若初始診斷集為空，則將具有相同初始癥狀沖突集的反例聚類成簇，按照可疑度計算公式計算每簇的初始癥狀沖突集及其所有轉(zhuǎn)換的可疑度.

4) 錯誤診斷

錯誤診斷過程主要是執(zhí)行如下步驟：

① 枚舉錯誤轉(zhuǎn)換組合.

② 枚舉該組合的所有錯誤可能.

③ 用測試集驗證錯誤可能，若驗證通過，則診斷結(jié)束；若驗證不通過，則再次進(jìn)行枚舉、驗證，直到診斷成功或所有錯誤組合全部驗證完畢.

枚舉錯誤轉(zhuǎn)換組合時遵循以下原則：

① 每一次選擇轉(zhuǎn)換時，選擇未被選擇過的、可疑度最大的初始癥狀沖突集中可疑度最大的轉(zhuǎn)換.

② 若錯誤轉(zhuǎn)換組合為t1,t2,…,tn，則ti為不包含t1,t2,…,ti-1的初始癥狀沖突集中的轉(zhuǎn)換，其中n最大為初始聚類的類別個數(shù).

枚舉每個轉(zhuǎn)換的錯誤可能有如下2種情況：

① 如果該轉(zhuǎn)換是某個初始癥狀沖突集的初始癥狀，則枚舉其輸出錯誤，錯誤的輸出可能是輸出集合中除了正確輸出值之外的其他任一輸出值.

② 如果該轉(zhuǎn)換在某個初始癥狀沖突集中，但不是初始癥狀，則枚舉其轉(zhuǎn)換錯誤，轉(zhuǎn)換錯誤指的是尾狀態(tài)錯誤，錯誤的尾狀態(tài)可能是狀態(tài)集中除了正確的尾狀態(tài)之外的其他任一狀態(tài).

用測試集驗證這些錯誤可能，這里有2種情況：

① 若錯誤可能使得測試集得到的輸出與系統(tǒng)的實際輸出相符，則計算修正該錯誤后的測試集輸出，與期望輸出進(jìn)行比較，結(jié)果分為2種情況：若修正該錯誤后的測試集輸出與期望輸出相符，則表明錯誤已成功診斷；若修正該錯誤后的測試集輸出與期望輸出不相符，則表明還存在其他錯誤，因此，在修正目前診斷的錯誤后，轉(zhuǎn)至1)，進(jìn)行剩余錯誤的診斷.

② 若錯誤可能使得測試集得到的輸出與系統(tǒng)的實際輸出不相符，則首先觀察證例的輸出與實際輸出是否相符. 若不相符，則排除該錯誤；若相符，則計算該錯誤對初始癥狀沖突序列的輸出. 若初始癥狀沖突序列的輸出與其實際輸出相符，則計算修正該錯誤后對初始癥狀沖突序列的輸出，與其期望輸出進(jìn)行比較. 若輸出與期望輸出相符，則同樣表明還存在其他錯誤，因此，在修正目前診斷的錯誤后，轉(zhuǎn)至1)，進(jìn)行剩余錯誤的診斷.

5) 若上述過程無法得到確定的錯誤診斷集，則需要在初始癥狀沖突集之后的轉(zhuǎn)換中進(jìn)行枚舉，或者增加一些測試用例再按照本文方法進(jìn)行診斷.

2.3 與單錯誤診斷方法的比較

在單錯誤診斷方法中，比較經(jīng)典的是文獻(xiàn)[11]提出的Ghedamsi算法以及文獻(xiàn)[12]提出的基于Ghedamsi算法的改進(jìn)算法. 本文方法是在這2種方法基礎(chǔ)上，結(jié)合聚類分析方法提出的一種多錯誤診斷方法. 該方法基于與單錯誤診斷方法相同的2個假設(shè)：假設(shè)錯誤只有轉(zhuǎn)換錯誤和輸出錯誤2種；假設(shè)一個轉(zhuǎn)換只發(fā)生一種錯誤.

文獻(xiàn)[12]在得到初始診斷集后，會依次對初始診斷集中的每個轉(zhuǎn)換進(jìn)行錯誤枚舉，而本文方法則會首先計算初始診斷集中每個轉(zhuǎn)換的可疑度，然后按照可疑度高低進(jìn)行錯誤枚舉，在這一點上分析效率要比文獻(xiàn)[12]高. 不過文獻(xiàn)[12]是基于單錯誤的診斷方法，在錯誤枚舉時還結(jié)合了尾狀態(tài)的下一轉(zhuǎn)換提供的信息，可快速排除一些枚舉項，而在多錯誤情況下無法利用這些信息，因為無法確定這些信息是否正確.

3 實例驗證

圖2 一個有限狀態(tài)機(jī)示例的描述及其實現(xiàn)Fig.2 Description and implementation of an example of FSM

表1 有限狀態(tài)機(jī)示例的UIO序列

1) 生成初始癥狀及其沖突集

如圖2、表2所示，比較測試序列的預(yù)期輸出和實際輸出，可知c1、c4和c10為證例，其余為反例.

表2 測試序列集的預(yù)期輸出和實際輸出

2) 生成初始診斷集

根據(jù)初始癥狀沖突集生成初始診斷集，ITC=SC1∩SC2∩SC3∩SC4=?，初始診斷集為空.

3) 初始聚類，并計算可疑度

將具有相同初始癥狀沖突集的反例及所有證例聚類成簇

C1={c1,c4,c10,c2,c7}
C2={c1,c4,c10,c3}
C3={c1,c4,c10,c5,c8,c11,c12}
C4={c1,c4,c10,c6,c9}

根據(jù)式(1)，通過計算得到每類初始癥狀沖突集的可疑度如表3所示.

表3 初始癥狀沖突序列覆蓋向量及可疑度

根據(jù)式(2)，通過計算得到每類初始癥狀沖突集中轉(zhuǎn)換的可疑度如表4所示.

表4 初始癥狀沖突集中轉(zhuǎn)換的可疑度

4) 錯誤診斷

由上述過程可知，該例中運用本文方法只需枚舉2個轉(zhuǎn)換組合的錯誤可能，即可獲得確定的錯誤診斷集.

4 實驗分析

基于FSM的錯誤診斷方法主要在于如何充分利用已有信息有效地減少枚舉數(shù)量，從而獲得錯誤診斷集.

從第3節(jié)實例中可知，一個轉(zhuǎn)換的錯誤可能個數(shù)與狀態(tài)集和輸出集大小成正相關(guān). 為了驗證診斷算法的有效性，構(gòu)建5個FSM模型進(jìn)行驗證，如圖3所示. 這5個FSM模型的狀態(tài)數(shù)、輸入/輸出個數(shù)和轉(zhuǎn)換數(shù)分別為(3,2,2,6)、(3,3,2,9)、(3,2,3,9)、(5,2,2,10)、(6,2,2,12). 對每一個FSM模型，枚舉其1～3個錯誤的所有可能，表5列出了錯誤轉(zhuǎn)換個數(shù)及其轉(zhuǎn)換集中的占比.

表5 FSM及錯誤個數(shù)和錯誤占比

圖3 實驗集Fig.3 Experimental set

4.1 評價指標(biāo)

1) 錯誤診斷率

枚舉所有錯誤可能，依次診斷，當(dāng)錯誤診斷集與錯誤集相同時表示診斷成功. 該指標(biāo)為診斷成功的個數(shù)占所有錯誤可能的百分比，公式為

(3)

式中：P表示錯誤診斷率；NS表示診斷成功的個數(shù)；NT表示所有錯誤可能的個數(shù).該指標(biāo)表明了診斷算法的有效性.

2) 診斷代價

該指標(biāo)為診斷成功前檢查錯誤可能的個數(shù)占所有錯誤可能的百分比，公式為

(4)

式中：Q表示診斷代價；NC表示診斷成功前檢查的錯誤個數(shù).基于FSM的錯誤診斷要明確指出錯誤所在及錯誤原因，枚舉錯誤的個數(shù)較為龐大，能夠以較小的代價獲得成功診斷，表明了診斷算法的可應(yīng)用性.

4.2 實驗結(jié)果分析

4.2.1 錯誤診斷率

圖4是本文算法診斷1個錯誤、2個錯誤和3個錯誤的錯誤診斷率. 由圖可知，錯誤診斷率與錯誤數(shù)量成負(fù)相關(guān)，也就是說診斷錯誤的成功率會隨著錯誤數(shù)量的增加而降低. 圖中顯示3個錯誤的錯誤診斷率為86.50%～93.74%，而1個錯誤的錯誤診斷率則基本是100.00%，只有模型4的錯誤診斷率是92.00%.

圖4 錯誤診斷率Fig.4 Fault diagnosis rate

影響本文方法錯誤診斷率的因素主要有3個.

1) 與FSM模型本身有關(guān)，如表6所示的2個模型是具有相同狀態(tài)集和輸入/輸出集，并且轉(zhuǎn)換個數(shù)相同，但轉(zhuǎn)換函數(shù)不同. 采用同一種測試集生成算法生成測試集，然后應(yīng)用本文算法進(jìn)行錯誤診斷，表6數(shù)據(jù)顯示錯誤診斷率和診斷成功需枚舉錯誤個數(shù)都是有差別的.

表6 不同轉(zhuǎn)換函數(shù)對錯誤診斷率的影響

2) 與測試集相關(guān). 圖3中對FSM4診斷1個錯誤的錯誤診斷率為92.00%，實驗顯示有4個錯誤未被診斷出，設(shè)計實驗分析診斷失敗原因，發(fā)現(xiàn)在這4個錯誤情況下，測試集的所有用例的實際輸出均等于期望輸出，也就是說均沒有反例. 沒有反例就不存在癥狀，本文算法也無法應(yīng)用. 表7的實驗是基于相同的模型，而測試集分別由2種算法生成，一種是部分W(part of W,Wp)算法，一種是UIO算法. 表7顯示不同測試集下的錯誤診斷率和診斷成功需枚舉的錯誤個數(shù)，實驗結(jié)果表明，無論是錯誤診斷率還是診斷代價都是有區(qū)別的. 基于UIO測試集的錯誤診斷率偏低，但多個錯誤的診斷代價略小.

表7 不同測試集對錯誤診斷率的影響

3) 與算法本身相關(guān). 若聚類算法能夠使得每類只包含1個錯誤，那么本文算法錯誤診斷率必定為100.00%. 但本文算法只是枚舉了初始癥狀沖突集中轉(zhuǎn)換的錯誤可能組合，沒有枚舉所有轉(zhuǎn)換. 在現(xiàn)有測試集基礎(chǔ)上，若初始癥狀沖突集不能夠包含所有錯誤轉(zhuǎn)換，則無法診斷成功. 例如，當(dāng)前錯誤的尾狀態(tài)是后續(xù)錯誤的頭狀態(tài)時，往往會出現(xiàn)假證例現(xiàn)象. 假證例使得初始癥狀沖突集不能夠包含所有錯誤轉(zhuǎn)換，本文算法則無法成功診斷出錯誤原因.

4.2.2 診斷代價

診斷代價反映了錯誤診斷的效率. 基于FSM的錯誤診斷方法其實就是枚舉并驗證錯誤可能. 若能窮舉所有的錯誤可能，則必定可以診斷成功，但代價太大. 圖5是盒圖，顯示了5個模型基于Wp測試集的平均診斷代價、最大值和最小值. 本文算法基本上可以在只枚舉12%以內(nèi)的錯誤可能情況下，以75%以上的成功率診斷出高達(dá)50%的錯誤轉(zhuǎn)換及原因所在，說明該方法具有應(yīng)用價值.

圖5 診斷代價范圍Fig.5 Diagnosis cost range

5 結(jié)論

1) 本文提出了一種基于FSM的多錯誤診斷方法. 現(xiàn)階段針對多錯誤的研究主要集中在軟件代碼上且主要在如何定位錯誤，而本文方法可適用于采用FSM模型進(jìn)行測試的系統(tǒng)，診斷結(jié)果不僅會給出錯誤所在，而且會指出錯誤原因.

2) 本文利用動態(tài)聚類分析方法解決多錯誤診斷問題. 首先，將反例按照初始癥狀沖突集相同與否進(jìn)行聚類，并計算初始癥狀沖突集及其中轉(zhuǎn)換的可疑度. 然后，選取高可疑的轉(zhuǎn)換進(jìn)行錯誤診斷分析，枚舉可能發(fā)生錯誤的轉(zhuǎn)換組合及其錯誤可能. 枚舉錯誤組合時進(jìn)行再次聚類，原則是錯誤組合中的轉(zhuǎn)換不在同一個初始癥狀沖突集中. 最后，用測試集驗證錯誤可能，若修正錯誤后符合期望輸出則表示診斷成功.

3) 實例及實驗結(jié)果表明，本文方法可以有效減少錯誤枚舉數(shù)量，并且在不需要額外枚舉或者增加測試用例情況下可以較低的診斷代價和較高的錯誤診斷率獲得確定的錯誤診斷集.

4) 如果一個FSM有n種錯誤，在實際應(yīng)用中只需要最多枚舉n種錯誤即可獲得診斷結(jié)果. 但由于實驗需要驗證方法的錯誤診斷率，枚舉的工作量相當(dāng)于nn，在單機(jī)實驗中耗時較長，因此，文中實驗的FSM規(guī)模較小，錯誤數(shù)也僅在3個之內(nèi). 下一步研究工作將改進(jìn)實驗的硬件環(huán)境，優(yōu)化實驗程序，進(jìn)行規(guī)模更大的實驗.