協(xié)議被動(dòng)測試?yán)碚撆c方法研究.pdf

1、　 本文研究了有限狀態(tài)機(jī)模型上被動(dòng)測試的一些理論和方法,本文給出了樹狀結(jié)構(gòu)上帶權(quán)和不帶權(quán)頂點(diǎn)覆蓋問題的線性時(shí)間算法，并改進(jìn)了一個(gè)已知的近似比為2的不帶權(quán)頂點(diǎn)覆蓋問題的近似算法，同時(shí)還給出了帶權(quán)頂點(diǎn)覆蓋問題的一個(gè)貪心近似算法。 本文采用Markov鏈模型來模擬被動(dòng)測試過程，提出了一種將有限狀態(tài)機(jī)中的狀態(tài)和到達(dá)該狀態(tài)的輸入/輸出對(duì)綁定在一起映射到Markov鏈中的狀態(tài)上的方法，最終得到了輸入/輸出對(duì)的平穩(wěn)概率分布，然后再將其與

2、觀察到的輸入/輸出對(duì)的概率分布進(jìn)行比較，若兩者不一致則說明檢測到了錯(cuò)誤，這是一種基于概率統(tǒng)計(jì)思想的算法，它可以應(yīng)用到分布式系統(tǒng)測試中。另外基于一個(gè)邏輯推理的算法，本文還提出了另一種適用于分布式被動(dòng)測試的錯(cuò)誤檢測算法。 本文先給出了一個(gè)單錯(cuò)誤診斷算法的兩種改進(jìn)算法，并且以BGPv4協(xié)議為例給出了模擬實(shí)驗(yàn)結(jié)果；其后采用類似于醫(yī)生給病人做檢查的思想，本文提出了一種新的單錯(cuò)誤診斷算法并將其推廣到多錯(cuò)誤診斷，并以O(shè)SPF協(xié)議的接口狀態(tài)機(jī)為