基于UPPAAL的路由協議驗證.pdf

1、近年來，關于下一代互聯網和物聯網的研究成果日漸豐富，新的數據通信和傳輸方法不斷涌現。其中，新的路由協議是新型網絡的關鍵部分，其正確性直接影響著網絡的穩(wěn)定性。然而路由協議在設計上具有自身特殊的復雜性，在設計過程中經常會出現一些人工方法難以察覺的缺陷。
　　模型檢測是一種形式化的驗證技術，能夠對系統進行自動驗證，并在發(fā)現系統缺陷時，給出導致此缺陷出現的執(zhí)行路徑。借助模型檢測的這種特性可以發(fā)現路由協議中隱含的缺陷，從而提高路由協議的可靠

2、性?；跁r間自動機的模型檢測工具UPPAAL是一個高效的可達性分析工具，常常被應用于包括網絡協議在內的各類實時系統的驗證。然而，使用模型檢測方法對路由協議進行驗證時，還存在以下兩方面的問題，一方面是協議建模困難，其中的關鍵在于復雜定時數據的建模;另一方面是狀態(tài)爆炸問題嚴重。
　　本文首先對路由協議中存在的復雜定時數據進行研究。針對復雜定時數據建模困難的問題，提出了一種基于離散化的抽象建模方法。通過實驗測試了這種建模方法的有效性，并

3、通過進一步實驗分析了這種建模方法的性能。
　　針對模型檢測的狀態(tài)爆炸問題，本文在建模過程中采用抽象技術與組合技術把原模型分解為兩個子模型，分別對其進行驗證，并通過假設/保證的組合策略驗證了原模型的性質。
　　最后，在抽象與組合技術以及復雜定時數據建模方法的基礎上，對OLSR路由協議進行驗證。實驗結果表明，0LSR協議具有無死鎖、行為一致性以及連通性。實驗結果同時表明，OLSR協議中的路由表計算部分存在冗余計算，可通過延遲路由