協(xié)議被動測試理論與方法研究.pdf

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

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