基于狀態(tài)機模型的協(xié)議被動測試研究.pdf

1、計算機網(wǎng)絡(luò)技術(shù)的發(fā)展日新月異，網(wǎng)絡(luò)規(guī)模不斷擴大，通信協(xié)議的設(shè)計越來越復(fù)雜，復(fù)雜的協(xié)議設(shè)計和不斷擴大的網(wǎng)絡(luò)規(guī)模會導(dǎo)致網(wǎng)絡(luò)出現(xiàn)故障的可能性增加。協(xié)議是網(wǎng)絡(luò)的靈魂，是通信雙方應(yīng)共同遵循的標準和規(guī)范，為了保證協(xié)議實現(xiàn)和協(xié)議規(guī)范的一致性，有必要對其進行測試。按照測試者同被測系統(tǒng)的交互行為，協(xié)議一致性測試可以分為主動測試(也稱為離線測試)和被動測試(也稱為在線測試)。主動測試先根據(jù)協(xié)議規(guī)范生成測試序列，再向被測系統(tǒng)施加測試序列，并將其輸出同協(xié)議規(guī)范

2、預(yù)期輸出進行比較。被動測試被動觀察被測系統(tǒng)的輸入輸出，無須干擾網(wǎng)絡(luò)設(shè)備的正常運行，適用于運行中網(wǎng)絡(luò)的故障檢查和定位。土動測試的優(yōu)點在于能夠通過外部控制被測系統(tǒng)的輸入，因而能保證較高的測試覆蓋率，狀態(tài)跟蹤和錯誤定位也比較容易。但是主動測試的測試序列長度同模型復(fù)雜程度有關(guān)，在被測系統(tǒng)狀態(tài)和轉(zhuǎn)換較多時，測試序列的生成較為困難。現(xiàn)有的一致性測試序列生成方法沒有覆蓋異常輸入，因而存在一些錯誤無法被檢測，另外存在一些特殊環(huán)境使得主動測試無法開展，而

3、被動測試可以有效地彌補主動測試的不足，成為主動測試的有益補充。 有限狀態(tài)機是描述協(xié)議的最常用模型，本文主要研究該模型上被動測試的一些理論和方法，本論文的主要工作包括： 1．被動測試中的觀察缺失標識： 在高速運行網(wǎng)絡(luò)中，網(wǎng)絡(luò)擁塞或低速的協(xié)議報文捕獲會導(dǎo)致部分協(xié)議報文丟失(即丟包現(xiàn)象)，而網(wǎng)絡(luò)監(jiān)控系統(tǒng)中關(guān)鍵協(xié)議報文的缺失會導(dǎo)致協(xié)議分析的失敗。因而為了完成協(xié)議的連續(xù)分析，有必要對缺失觀察的報文進行標識。本文將上述問題歸

4、結(jié)為狀態(tài)問最小引導(dǎo)序列構(gòu)造問題。先通過被動測試錯誤檢測算法計算出系統(tǒng)在缺失觀察前的可能狀態(tài)，再運用回溯算法求出重新獲取觀察序列后的初始可能狀態(tài)，最后構(gòu)建子樹森林，通過遍歷子樹查找符合條件的引導(dǎo)序列。 2．被動測試中測試覆蓋率分析： 測試序列生成的目標就是用盡可能短的測試序列檢測出盡可能多的錯誤，主動測試中，測試序列是在測試之前就靜態(tài)確定的，因而覆蓋率是固定的。被動測試中，觀察序列在運行時才能確定，具有隨機不確定性，因而對

5、于相同長度的不同觀察序列，其檢測錯誤的能力可能不同。為了能夠?qū)τ^察序列檢測錯誤的能力進行評價，有必要對測試覆蓋率進行量化，本文提出了一種適用于分析被動測試測試覆蓋率的方法，該方法先定義錯誤模型，再依據(jù)模型生成所有可能錯誤，最后使用變異測試的方法檢測錯誤，通過理論和實驗證明了通過增加觀察步驟數(shù)或結(jié)合主動測試可以提高測試覆蓋率。 3．被動測試中的錯誤診斷： 在用被動測試錯誤檢測算法檢測到協(xié)議實現(xiàn)和協(xié)議規(guī)范的差異后，如何分析和

6、定位這些差異變得尤為重要。本義給出了如下兩種方法解決該問題： 擴展了一個經(jīng)典的錯誤標識算法，在標記錯誤過程中記錄該錯誤所導(dǎo)致的系統(tǒng)狀態(tài)，再以該狀態(tài)做為初始狀態(tài)繼續(xù)向前觀察多步以區(qū)分錯誤。 將模型診斷的思想引入到被動測試錯誤診斷中，設(shè)計了一個層次化的被動測試錯誤診斷算法，該算法首先記錄被動檢測過程中系統(tǒng)經(jīng)歷的轉(zhuǎn)換軌跡，再用變異分析的方法生成候選診斷，再通過增加觀察步驟數(shù)減少候選診斷集合規(guī)模，最后通過結(jié)合主動測試的方法進行錯

7、誤區(qū)分，直至定位錯誤。該方法可以解決現(xiàn)有被動測試錯誤診斷算法無法區(qū)分等價錯誤，無法診斷重復(fù)錯誤，繼續(xù)觀察步驟數(shù)受限等問題。最后將該方法由有限狀態(tài)機模型推廣到通信有限狀態(tài)機模型。 4．被動測試中的增量實現(xiàn)標識： 在Internet協(xié)議中，絕大多數(shù)協(xié)議的狀態(tài)機是不完全的。．辛動測試中，基于狀態(tài)機模型自動生成的測試序列往往是弱一致性測試序列。該序列只考慮覆蓋規(guī)范中的轉(zhuǎn)換，如果系統(tǒng)額外的實現(xiàn)了某個轉(zhuǎn)換，主動測試序列檢查不出該轉(zhuǎn)換

8、。本文提出的解決方法是：先用被動測試的方法檢測被測系統(tǒng)是否存在額外實現(xiàn)的轉(zhuǎn)換；檢查出系統(tǒng)中存在增量實現(xiàn)后，分析被動測試軌跡，找出可能出現(xiàn)增量丈現(xiàn)的狀態(tài)和輸入輸出，結(jié)合運用交叉驗證序列來標識增量實現(xiàn)。所提方法可應(yīng)用于協(xié)議實現(xiàn)有差異的操作系統(tǒng)類型鑒定和程序異常檢測。 5．主被動測試相結(jié)合的協(xié)議一致性測試系統(tǒng)設(shè)計和實現(xiàn)： 設(shè)計和實現(xiàn)了一個可高效執(zhí)行的協(xié)議自動化測試系統(tǒng)。該系統(tǒng)能夠在線配置測試參數(shù)，解決了傳統(tǒng)測試中需于工配置被測