[發明專利]基于并行擴展有限狀態機的協議層次化測試生成方法

有效

• 申請號: 201310308805.8
• 申請日: 2013-07-22
• 公開（公告）號: CN103391224A
• 公開（公告）日: 2013-11-13
• 發明（設計）人: 王之梁;姚姜源;施新剛;尹霞
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L29/06
• 代理公司: 北京聿宏知識產權代理有限公司 11372
• 代理人: 吳大建;劉華聯

技術領域

本發明涉及網絡協議測試技術領域，具體涉及一種基于并行擴展有限狀態機的協議層次化測試生成方法。

背景技術

協議測試技術是保證網絡通訊協議正確實現以及不同的網絡設備之間正確互連的重要手段。一致性測試是基本的協議測試方法，其目標是檢測協議實現是否與協議規范相一致。

基于形式化方法的測試生成是這一領域中的重要問題，其目標是從協議規范的形式化模型出發，生成用于測試活動的測試集（或測試序列）。在大多數已提出的測試生成技術中，其基本思想是將被測系統（System?Under?Test,簡稱SUT）模型化為一個有限狀態機或擴展有限狀態機的系統，進而生成測試序列。

在已提出的測試生成技術中存在以下一些問題：第一，基于擴展有限狀態機的啟發式測試生成技術能夠有效避免狀態爆炸問題，但是由于啟發式方法固有的特點，該技術無法確保生成的測試序列都是可執行的。第二，基于擴展有限狀態機的可達性分析測試生成技術能夠確保生成的測試序列都是可執行的，但是存在狀態爆炸問題。

發明內容

本發明所要解決的技術問題之一是需要提供一種基于并行擴展有限狀態機的協議層次化測試生成方法，該方法確保基于并行擴展有限狀態機模型生成的測試序列的執行性，同時減緩狀態爆炸問題。

為了解決上述技術問題，本發明提供了一種基于并行擴展有限狀態機的協議層次化測試生成方法，包括：步驟1，將待測試的網絡設備的協議規范描述為一并行擴展有限狀態機模型；步驟2，將所述并行擴展有限狀態機模型中各個組件模型間的變量使用情況描述為一狀態機依賴圖；步驟3，根據所述狀態機依賴圖，采用自底向上的可達圖生成算法生成組件狀態機可達圖；步驟4，根據所述組件狀態機可達圖生成組件狀態機本地測試集；步驟5，根據狀態機依賴圖，采用自頂向下的生成算法將所述組件狀態機本地測試集生成組件狀態機并行測試集。

在一個實施例中，所述并行擴展有限狀態機模型是由n個組件狀態機組成的集合，用Ms表示，Ms={M₁,M₂,…,M_n}；

各組件狀態機用于描述各協議進程的規范，各組件狀態機用M_i表示，i=0,1,…,n，M_i是一個七元組，M_i＝(S,s₀,V_I,V_E,I,O,T)：

其中，S是M_i的有限狀態集合；

s₀∈S，是M_i的初始狀態；

V_I=(V_i1,V_i2,…V_ik,…,V_in)，其中V_ik是所有定義與使用均在M_i內部的變量，稱為內部變量，k=1,2,…,n，n為正整數，V_I是M_i所有內部變量的集合；

V_E=(V_e1,V_e2,…V_ek,…,V_en)，其中V_ek是所有定義在M_i外部，但是在M_i內部被使用的變量，稱為外部變量，k=1,2,…,n，n為正整數，V_E是M_i所有外部變量的集合；

I=(I₁,I₂,…I_k,…,I_n)，其中I_k是M_i的一個輸入符號，k=1,2,…,n，n為正整數，I是M_i所有輸入符號的集合，I為非空集合；

O=(O₁,O₂,…O_k,…,O_n)，其中O_k是M_i的一個輸出符號，k=1,2,…,n，n為正整數，O是M_i所有輸出符號的集合，O為非空集合；