基于層次有向圖的接口時序一致性測試方法

高 亮，李 蒙，梁晨光，宮久路

(1.北京理工大學機電學院，北京 100081；2.北京航天控制儀器研究所，北京 100039；3.北京宇航系統工程研究所，北京 100076)

0 引言

武器裝備的總裝測試中，常出現接口時序不匹配導致的電氣系統工作故障問題，因此有必要開展接口時序的一致性在線測試方法研究?，F有的一致性測試方法分為主動測試和被動測試兩類[1]。ISO/IEC 9646標準定義了主動測試的框架和方法[2]，工程應用中一般基于TTCN-3測試框架實現[3-5]，通過生成能夠觸發故障的測試集作為測試輸入，觀測輸入與輸出之間的因果關系實現一致性檢測，其缺點是不能在線測試，且只能檢測測試集已覆蓋的故障類型。被動測試則利用形式化模型描述被測系統行為，通過對比檢測發現所有與模型描述不一致的系統行為實現時序一致性的在線測試，常用的模型有Petri網[6]、有限狀態機及其擴展模型[7-9]、有向圖模型等[10]。相較于主動測試，被動測試方法能夠滿足接口時序的在線測試需求，且能發現系統長期運行后出現的錯誤。目前，一致性測試研究集中于數據鏈路層和應用層，通過測試物理層電氣參數實現一致性測試的研究還很缺乏[11]。同上層測試相比，物理層測試能夠直接定位故障產生的原因(如：數據鏈路層可檢測到數據誤碼，但不能分析出造成誤碼的原因)，發現潛在的時序缺陷，因此，在線物理層測試成為發現和定位接口時序故障的主要技術途徑。

目前主流的物理層在線測試方法是通過示波器或邏輯分析儀進行人工測試[12]，存在測試效率低，不能實現長時間連續測試等問題。為了提高測試效率，有學者開始研究時序的自動化測試系統[13-15]，但研究偏向時序參數的自動測量和判斷，較少涉及邏輯關系的檢測，同時在描述時序規范時，多采用描述跳變沿時間的方法實現，在時序建模方法上還有待進一步的研究。針對武器裝備在總裝測試中出現的接口時序不匹配，現有測試方法不能實現長期連續自動測試的問題，本文提出基于層次有向圖的時序一致性測試方法。

1 測試框架及有向圖模型

1.1 被動測試

武器系統的總裝測試要求在線測試，因此只能選擇被動測試方法，時序一致性測試的被動測試框架如圖1所示。測試時首先利用形式化方法將時序協議輸入測試系統，建立標準時序的模式集和約束集；然后在被測系統與外界運行環境交互時獲取測量數據，通過測量數據與模式集的對比分析檢測出邏輯異常時序，通過驗證時序參數是否滿足約束集檢測出不收斂的異常時序。

圖1 一致性測試的被動測試框架Fig.1 Passive testing framework for consistency testing

1.2 有向圖模型

有向圖模型是一類由節點和有向邊構成的，具有嚴格數學描述的定性模型[16],通常以節點表示系統變量或狀態，以節點間的因果影響關系構建有向邊，記作〈u,v〉，表示從節點u到節點v的有向邊。與邊相關的數稱作權，可以表示節點之間的變遷時間、傳播概率等。若從有向圖的節點vi出發，沿有向邊經過節點vp1,vp2,…,vpm到達節點vj，則稱節點序列(vi,vp1,vp2,…,vpm,vj)為從節點vi到vj的轉移路徑，路徑上所有邊的權值之和稱作轉移路徑的長度。

2 層次有向圖模型及檢測算法

2.1 接口時序的層次結構

考慮到通信接口在實現數據交換時通常是分周期完成的，將重復的時序片段用同一個模型描述能夠降低模型的構建難度。為了統一建模方法，首先對接口時序進行層次劃分，對應的層次結構如圖2所示。圖2中，功能時序表示接口實現某種基本功能時對應的工作時序片段，空閑時序表示接口處于空閑狀態時對應的時序片段，兩類時序對應的時序規范統稱為時序模式。

圖2 接口時序的層次結構Fig.2 Hierarchical structure of interface timing

圖2所示的層次結構的數學描述如下：

1) 設接口含有N種基本功能，每種基本功能對應的時序規范表示為模式φi，則接口時序的功能模式狀態空間：

Φ={φ1,φ2,…,φN}

(1)

2) 設接口在空閑狀態下存在M種可取的狀態組合，每種狀態組合對應的時序規范表示為模式γi，則接口時序的空閑模式狀態空間：

Γ={γ1,γ2,…,γM}

(2)

3) 若接口含有k個步驟的功能操作，設φi∈Φ(1≤i≤k)，γj∈Γ(0≤j≤k)，則接口時序Θ可描述為：

Θ={γ0,φ1,…,φk,γk}

(3)

在上述層次結構中，功能時序和空閑時序是描述接口時序的最小基本單位，兩類基本級時序的不同組合可實現不同系統級時序的描述，所構成的系統級時序同時又可作為更上層時序描述的基本單位。特別地，當接口時序Θ的模式狀態空間Φ和Γ分別只含有一種模式時，稱Θ為單模式時序，反之稱Θ為多模式時序。

2.2 時序的有向圖模型

模型構建的關鍵在于實現狀態空間中每個φi和γj的具體描述，本文針對單模式時序構建接口時序的有向圖模型，如圖3所示。圖3中，單圓圈節點表示只含有1種屬性，雙圓圈節點表示含有多種屬性，有向邊上的豎線表示信號沿，扇區是本文提出的一種新的結構，用六邊形表示。緊鄰扇區的兩個節點分別稱作扇入節點和扇出節點。

圖3 單模式時序的有向圖模型Fig.3 Directed graph model of timing mode

模型以同一時刻下接口各信號線的邏輯狀態di=(x1,x2,…,xn)作為節點屬性，其中xi表示第i個信號的邏輯值；以接口時序的狀態變遷規律構建有向邊，并定義系統觀測的時間分辨率為模型中所有鄰接路徑的權，權值大小等于觀測頻率fsamp的倒數。建立時序有向圖模型的主要步驟如下：

1) 確定時序模式φi的開始和結束位置，從開始位置起沿時間軸方向對φi的時序圖進行虛擬采樣掃描，直至結束位置；

2) 以φi的第一個采樣狀態作為節點P1，設相鄰兩次采樣所得到的系統狀態分別為di和di+1，di對應的圖節點為vi，若di=di+1，則有向邊為自循環路徑〈vi,vi〉；若di≠di+1，則生成新節點ui+1，并構建有向邊〈vi,ui+1〉，直至φi的最后一個節點Pm；

3) 在步驟2)中，若相鄰狀態di和di+1之間存在1個以上的信號沿，則在di和di+1對應的節點之間添加扇區結構；

4) 設接口在空閑狀態下可取的系統狀態為：d1,d2,…,dk，使用雙圓圈γ節點表征空閑時序，該節點含有對應的k種屬性，并構建有向邊〈Pm,γ〉和〈γ,P1〉；

5) 時序約束在模型中的映射方式為：根據時序約束條件確定受約束的兩個信號沿位置，時間位置靠前的稱作基準信號沿，時間位置靠后的稱作受約信號沿。從基準信號沿出發，按照有向轉移路徑到達受約信號沿，設共有n條可能的轉移路徑，則為每條轉移路徑都添加一個二元約束值，其形式為(max,t)或(min,t)，分別表示對應轉移路徑的路徑長度不得超過或小于t。

模型中的扇區結構是針對邏輯變遷規律具有隨機性的時序區間而提出的，其目的是為了縮減模型體積，進一步降低模型的構建難度。如圖4所示時序含有A、B、C三個并行信號，a、b、c、d、e分別表示信號沿的理想位置，其中c、d、e對應同一時刻，a′、b′、c′、d′、e′分別表示信號沿的實際位置。由于時序規范允許信號沿在約束范圍內發生有限偏移，因此可能出現兩種情況：

1) 信號沿的理想位置不在同一時刻，如信號沿a、b，偏移后不會產生新的系統狀態；

2) 信號沿的理想位置對應同一時刻，如信號沿c、d、e，偏移后會出現新的系統狀態，且狀態的數量和出現的先后順序都不相同。

圖4 時序的實際位置與理想位置的示意圖Fig.4 Schematic diagram of the actual position and ideal position of the sequence

針對上述的情況2)分析所有可能出現的情況，假設有n個信號沿的理想位置對應同一時刻，其中只有m個信號沿的實際位置對應同一時刻，則所有相對位置關系的可能情況數可按照排列組合的方法計算出：

(4)

如果使用傳統的有向圖模型就需要構建s條不同的轉移路徑，根據式(4)可以看出，隨著n的增大，模型體積和結構復雜度會急劇增加，且后續檢測時的搜索空間也隨之增加。為了解決這個問題，本文使用扇區結構整體取代這部分時序區間對應的圖結構，并通過扇區邊界條件保證取代前后描述的等效性。即只要滿足扇區邊界條件，就一定在原圖結構中存在一條對應的轉移路徑?？紤]到信號的偏移不會導致電平狀態的改變，因此可構建扇區的邊界條件如下：

1) 若扇區對應的時序區間內有n個信號沿的理想位置重疊，則扇區內圖結構的轉移路徑包含的節點數量不超過n-1；

2) 扇區內一定不含有與扇入節點和扇出節點屬性相同的節點；

3) 每條轉移路徑上所包含的節點，一定是互異的。

2.3 基于模型的錯誤檢測算法

根據錯誤檢測標準的不同，將接口的異常時序劃分為兩種類型：一是信號間的邏輯關系發生改變，稱作邏輯性錯誤；二是時序參數的測量值不滿足約束條件，稱作收斂性錯誤。當邏輯關系發生改變時，可能導致時序參數的測量位置發生偏差，因此時序參數的約束符合性檢測應建立在邏輯關系正確的基礎上。同時考慮到硬件工作具有順序執行的特點，當在通信周期的ti時刻發生邏輯性錯誤時，即使ti+1時刻的時序正確，也不能保證接口正常通信。換言之，當通信周期檢測到錯誤后，再對當前通信周期內的后續時序進行一致性檢測沒有意義，因此在算法設計時只需考慮通信周期內出現單個錯誤的情況。為了保證測試的準確性，一致性測試應盡可能地證明系統存在錯誤，因此在設計算法時不允許將錯誤的時序診斷為正確，但允許將正確的時序檢測為錯誤?；谏鲜龇治?，設計層次化錯誤檢測算法如下，算法的工作流程圖如圖5所示。

圖5 層次化錯誤檢測算法的工作流程圖Fig.5 Workflow of hierarchical error detection algorithm

1) 假設系統初始候選狀態為所有狀態，通過不斷觀測，候選狀態數不斷減少，當候選狀態數變為1時確定初始狀態，當候選狀態數變為0時表示檢測到錯誤，報告錯誤，并重新開始執行步驟1)；

2) 通過有限狀態機對所有測試數據點進行標記，將測試數據分為空閑時序和功能時序兩類，并同時檢測位于空閑時序的數據點是否屬于γ，如果不屬于表示檢測到位于空閑時序的邏輯性錯誤；

3) 將位于同一個通信周期的功能時序數據點提取為一個完整的通信幀，通過校驗幀格式檢測位于功能時序段的邏輯性錯誤；如果不存在錯誤則執行步驟4)，否則報告錯誤，并停止當前通信幀的后續檢測；

4) 定位被測時序參數的兩個信號沿位置，通過計算信號沿位置之間的時間距離得到測量值，并判斷測量值是否符合約束不等式，如果不符合表示檢測到收斂性錯誤。

3 實驗驗證

本文基于LabVIEW完成時序一致性測試系統的樣機開發，利用FPGA實現了4種不同的被測信號源，各被測信源中存在的時序故障詳見表1。為了驗證設計算法對通信周期內存在多個錯誤的時序的檢測效果，在復合錯誤信源的通信周期內均注入了2種不同類型的邏輯性錯誤。利用測試系統分別對4種被測信號源進行單獨測試，測試結果如表2所示。

表1 各被測信源中存在的時序故障列表

表2 各被測信源的時序一致性測試結果

表2的測試結果表明，含有邏輯性錯誤的兩類信源均存在不同程度的虛警率，這是因為當通信周期的開始標志出現錯誤時，檢測算法會將功能時序的數據點當作空閑時序來檢測，因此凡是不屬于空閑時序集合的狀態會被誤檢為出現邏輯性錯誤。對通信周期內只含有1種錯誤類型的信源測試結果顯示，沒有錯誤漏檢的情況出現，說明設計算法對單個錯誤有著較高的檢測率，其中對收斂性錯誤的檢測準確度可達到100%，因為時序參數的收斂性檢測結果僅與自身的測量值有關，在邏輯關系正確的前提下，可保證參數的測量位置不出現偏差，在采樣分辨率足夠高的情況下，可達到很高的檢測準確度。復合錯誤信源的測試結果顯示存在較高的漏警率，造成錯誤漏檢的根本原因是算法是基于單個錯誤假設設計的，當檢測到通信周期存在錯誤后便不再對這個周期內的后續數據做檢測，因此會漏檢通信周期內時間位置靠后的錯誤。

4 結論

本文提出了基于層次有向圖模型的接口時序一致性測試方法。該方法通過建立接口時序的層次有向圖模型，設計錯誤檢測算法，實現對接口異常時序的檢測。實驗結果表明，該方法能夠對通信周期內單個邏輯性錯誤的異常時序實現準確檢測，對不收斂的異常時序能實現完全檢測，但是當通信周期的開始或結束信號出現錯誤時，可能會出現虛警率較高的問題，并且對通信周期內存在多個錯誤的異常時序檢測時準確度較低，甚至會出現較高的錯誤漏檢率。