基于狀態(tài)機(jī)模型的協(xié)議被動(dòng)測(cè)試研究.pdf

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

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

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

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

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

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

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

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