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

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

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

0 引言

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

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

1 測試框架及有向圖模型

1.1 被動測試

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

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

1.2 有向圖模型

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

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

2.1 接口時序的層次結(jié)構(gòu)

考慮到通信接口在實現(xiàn)數(shù)據(jù)交換時通常是分周期完成的，將重復(fù)的時序片段用同一個模型描述能夠降低模型的構(gòu)建難度。為了統(tǒng)一建模方法，首先對接口時序進(jìn)行層次劃分，對應(yīng)的層次結(jié)構(gòu)如圖2所示。圖2中，功能時序表示接口實現(xiàn)某種基本功能時對應(yīng)的工作時序片段，空閑時序表示接口處于空閑狀態(tài)時對應(yīng)的時序片段，兩類時序?qū)?yīng)的時序規(guī)范統(tǒng)稱為時序模式。

圖2 接口時序的層次結(jié)構(gòu)Fig.2 Hierarchical structure of interface timing

圖2所示的層次結(jié)構(gòu)的數(shù)學(xué)描述如下：

1) 設(shè)接口含有N種基本功能，每種基本功能對應(yīng)的時序規(guī)范表示為模式φi，則接口時序的功能模式狀態(tài)空間：

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

(1)

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

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

(2)

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

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

(3)

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

2.2 時序的有向圖模型

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

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

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

1) 確定時序模式φi的開始和結(jié)束位置，從開始位置起沿時間軸方向?qū)Ζ読的時序圖進(jìn)行虛擬采樣掃描，直至結(jié)束位置；

2) 以φi的第一個采樣狀態(tài)作為節(jié)點P1，設(shè)相鄰兩次采樣所得到的系統(tǒng)狀態(tài)分別為di和di+1，di對應(yīng)的圖節(jié)點為vi，若di=di+1，則有向邊為自循環(huán)路徑〈vi,vi〉；若di≠di+1，則生成新節(jié)點ui+1，并構(gòu)建有向邊〈vi,ui+1〉，直至φi的最后一個節(jié)點Pm；

3) 在步驟2)中，若相鄰狀態(tài)di和di+1之間存在1個以上的信號沿，則在di和di+1對應(yīng)的節(jié)點之間添加扇區(qū)結(jié)構(gòu)；

4) 設(shè)接口在空閑狀態(tài)下可取的系統(tǒng)狀態(tài)為：d1,d2,…,dk，使用雙圓圈γ節(jié)點表征空閑時序，該節(jié)點含有對應(yīng)的k種屬性，并構(gòu)建有向邊〈Pm,γ〉和〈γ,P1〉；

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

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

1) 信號沿的理想位置不在同一時刻，如信號沿a、b，偏移后不會產(chǎn)生新的系統(tǒng)狀態(tài)；

2) 信號沿的理想位置對應(yīng)同一時刻，如信號沿c、d、e，偏移后會出現(xiàn)新的系統(tǒng)狀態(tài)，且狀態(tài)的數(shù)量和出現(xiàn)的先后順序都不相同。

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

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

(4)

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

1) 若扇區(qū)對應(yīng)的時序區(qū)間內(nèi)有n個信號沿的理想位置重疊，則扇區(qū)內(nèi)圖結(jié)構(gòu)的轉(zhuǎn)移路徑包含的節(jié)點數(shù)量不超過n-1；

2) 扇區(qū)內(nèi)一定不含有與扇入節(jié)點和扇出節(jié)點屬性相同的節(jié)點；

3) 每條轉(zhuǎn)移路徑上所包含的節(jié)點，一定是互異的。

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

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

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

1) 假設(shè)系統(tǒng)初始候選狀態(tài)為所有狀態(tài)，通過不斷觀測，候選狀態(tài)數(shù)不斷減少，當(dāng)候選狀態(tài)數(shù)變?yōu)?時確定初始狀態(tài)，當(dāng)候選狀態(tài)數(shù)變?yōu)?時表示檢測到錯誤，報告錯誤，并重新開始執(zhí)行步驟1)；

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

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

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

3 實驗驗證

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

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

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

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

4 結(jié)論

本文提出了基于層次有向圖模型的接口時序一致性測試方法。該方法通過建立接口時序的層次有向圖模型，設(shè)計錯誤檢測算法，實現(xiàn)對接口異常時序的檢測。實驗結(jié)果表明，該方法能夠?qū)νㄐ胖芷趦?nèi)單個邏輯性錯誤的異常時序?qū)崿F(xiàn)準(zhǔn)確檢測，對不收斂的異常時序能實現(xiàn)完全檢測，但是當(dāng)通信周期的開始或結(jié)束信號出現(xiàn)錯誤時，可能會出現(xiàn)虛警率較高的問題，并且對通信周期內(nèi)存在多個錯誤的異常時序檢測時準(zhǔn)確度較低，甚至?xí)霈F(xiàn)較高的錯誤漏檢率。