[發明專利]基于變量依賴的并行擴展有限狀態機的協議測試生成方法

有效

• 申請號: 201110344327.7
• 申請日: 2011-11-03
• 公開（公告）號: CN102404167A
• 公開（公告）日: 2012-04-04
• 發明（設計）人: 王之梁;姚姜源;尹霞
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L29/06
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩

技術領域

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

背景技術

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

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

在已提出的測試生成技術中存在以下一些問題：第一，基于擴展有限狀態機的測試生成僅考慮單一進程模型情形，對于多個相互關聯的并行進程的情形沒有涉及。后者只能通過窮舉多個并行進程的各種組合，并對各種組合分別建立組合模型加以解決，建模的規模難以接受，并且給后續的測試生成造成了障礙。第二，基于通信有限狀態機或通信擴展有限狀態機的測試生成都是用于網絡中多實體的情形，沒有涉及單一實體中多個進程的情形，而且前者的測試方法大都存在組合模型造成的狀態爆炸問題。

發明內容

(一)要解決的技術問題

本發明所要解決的技術問題是：如何解決變量依賴導致的路徑不可執行問題，同時避免狀態爆炸。

(二)技術方案

為解決上述技術問題，本發明提供了一種基于變量依賴的并行擴展有限狀態機的協議測試生成方法，所述方法是在網絡操作環境中對于一個被測試的網絡設備依次執行以下步驟實現的：

步驟1：在計算機中，把被測試的網絡設備的協議規范描述為一個并行擴展有限狀態機模型Ms；

步驟2：采用忽略變量依賴的擴展有限狀態機測試生成技術生成組件狀態機抽象測試集；

步驟3：針對外部變量，生成可執行化外部前導序列；

步驟4：采用鏈接外部前導序列的方法對組件狀態機抽象測試集進行可執行化處理；

步驟5：生成關于外部變量的跨狀態機抽象測試集；

步驟6：將經過步驟4處理的抽象測試集與步驟5生成的抽象測試集合并，刪除重復或被包含的測試序列，得到協議狀態機的抽象測試集。

優選地，步驟1具體為：

設：在所述被測試的網絡設備中包含一個或多個協議，各協議包含一個或多個可并行工作的進程，各協議的規范是已知的；則：將所述被測試的網絡設備用一個并行擴展有限狀態機模型來描述，所述并行擴展有限狀態機模型是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，TR，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所有外部變量的集合；