基于層次有向圖的接口時(shí)序一致性測(cè)試方法

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

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

0 引言

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

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

1 測(cè)試框架及有向圖模型

1.1 被動(dòng)測(cè)試

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

圖1 一致性測(cè)試的被動(dòng)測(cè)試框架Fig.1 Passive testing framework for consistency testing

1.2 有向圖模型

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

2 層次有向圖模型及檢測(cè)算法

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

2.2 時(shí)序的有向圖模型

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

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

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

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

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

2.3 基于模型的錯(cuò)誤檢測(cè)算法

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

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

表1 各被測(cè)信源中存在的時(shí)序故障列表

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

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

4 結(jié)論

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