[發明專利]基于UIO序列法驗證有限狀態機所處狀態的方法

有效

• 申請號: 201410106244.8
• 申請日: 2014-03-20
• 公開（公告）號: CN103888314B
• 公開（公告）日: 2017-06-09
• 發明（設計）人: 張冰;方爽;張奭;周元海;吳效穎;崔璨;彭露
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/26
• 分類號: H04L12/26;G06F11/36
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 王品華,朱紅星

技術領域

本發明屬于通信技術領域，特別涉及一種驗證有限狀態機所處狀態的方法，可用于各種通信協議在其有限狀態機內某些狀態不存在唯一輸入輸出UIO序列情況下一致性測試集的設計和實現。

背景技術

協議的一致性測試是一種黑盒測試，其目的是檢查運行協議的系統與協議標準的符合程度。在通信協議一致性測試中，測試集是滿足測試準則的多個測試序列的集合。測試序列通常由三部分構成：引導序列、測試輸入輸出操作、狀態驗證序列。其中，引導序列用于把被測系統所處的狀態置為所需狀態；測試輸入輸出操作用于驗證被測系統與協議要求的行為是否一致；狀態驗證序列用于檢查被測系統是否轉換到了協議規范所描述的狀態。狀態驗證序列作為測試序列的組成部分之一，對提高測試序列的檢錯能力有重要作用。

目前，大多數的狀態驗證序列的構造方法都是基于有限狀態機的。一個有限狀態機可以表示為五元組（S，I，O，δ，γ），其中，S是狀態的有限非空集合，I是輸入事件的有限非空集合，O是輸出事件的有限非空集合，δ是狀態轉移函數，γ是輸出函數。有限狀態機需具備以下基本特征：

1.有限狀態機的狀態數、輸入事件數和所產生的輸出事件數都是有限的、確定的。

2.有限狀態機的每個狀態下都能接受所有輸入事件。

3.對于每個輸入事件，如果有限狀態機能夠產生輸出事件，那么該輸出事件將在給定的有限時間內產生。

4.有限狀態機的每個狀態都是可達的，其狀態轉移圖是連通圖。

當前針對有限狀態機，主要的狀態驗證序列構造的方法有三種：區分序列法、特征序列集法、UIO序列法。與區分序列法、特征序列集法相比，UIO序列法復雜度低，且生成的測試序列長度較短，因此，在數字系統和通信等時序行為領域的建模過程中，特別是在尋找優化的測試集方面有著廣泛應用。

UIO序列是唯一輸入輸出序列，即對于有限狀態機中的某一狀態，其他狀態都不能表現出與之相同的輸入/輸出I/O序列，因而該UIO序列可以唯一標識和驗證此狀態。在某一狀態Sa下，對于某一輸入y，當且僅當狀態Sa的輸出λa與其他所有狀態下的輸出均不同時，則y/λa是狀態Sa的UIO序列，記做UIO(Sa)=y/λa，其中，y/λa表示在狀態Sa時的輸入/輸出序列。求解UIO(Sa)的步驟如下：

1）設狀態集合P是從Sa經過1步就能到達的狀態的集合，檢查從Sa到狀態集合P中所有狀態的1步路徑中是否有I/O序列唯一的路徑：若有，則該I/O序列就是Sa的唯一輸入輸出UIO序列；否則，執行步驟2）；

2）設狀態集合Q是從Sa經過n步就能到達的狀態的集合，n≥2，檢查從Sa到狀態集合Q中所有狀態的n步路徑中是否有I/O序列唯一的路徑：若有，則該I/O序列就是Sa的唯一輸入輸出UIO序列；否則，n=n+1，重新檢查從Sa到狀態集合Q中所有狀態的n步路徑中是否有I/O序列唯一的路徑；

I/O序列和UIO序列均由輸入事件序列和輸出事件序列組成，輸入事件序列表示I/O序列中的一個輸入事件或具有先后關系的多個輸入事件的組合，輸出事件序列表示I/O序列中的一個輸出事件或具有先后關系的多個輸出事件的組合。

UIO序列法就是以尋找有限狀態機中的各狀態的UIO序列為基礎，構造狀態驗證序列的方法。獲得狀態驗證序列后，再結合引導序列、測試輸入輸出操作，就可得到測試序列，所有測試序列的集合就構成了完整的測試集。因此，通常認為，可否尋找到所有狀態的UIO序列是能否使用UIO序列法的前提。

多數情況下，有限狀態機內各狀態都可以找到UIO序列，但是在某些情況下，有限狀態機的某些狀態不存在UIO序列。例如對于某一狀態Sa，對任意輸入y，有輸出λa，并轉移到某一狀態Sb，對狀態Sb，同樣輸入y，如果有相同的輸出λa，則狀態Sa不存在UIO序列。如附圖2中所示，其中以圓形表示狀態，以帶箭頭的實線表示狀態的轉移，實線上標識的是狀態轉移的條件，即I/O行為，以英文字母表示輸入事件和輸出事件。在狀態S2下，輸入B，得到輸出Y并轉移到狀態S3，由于在狀態S3下輸入B，同樣得到輸出Y，則狀態S2不存在UIO序列。通常認為此時將無法使用UIO序列法對這些狀態進行狀態驗證，只能轉而采用區分序列法、特征序列集法等更為復雜的驗證方法，使一致性測試集更加復雜，增加了測試序列的長度。

發明內容