齊杏林， 馬繼存， 余春華

(軍械工程學(xué)院彈藥工程系， 河北 石家莊 050003)

基于Petri網(wǎng)的FPGA軟件缺陷分析與改進(jìn)設(shè)計(jì)

齊杏林， 馬繼存， 余春華

(軍械工程學(xué)院彈藥工程系， 河北 石家莊 050003)

為了在FPGA軟件開(kāi)發(fā)過(guò)程的早期發(fā)現(xiàn)設(shè)計(jì)缺陷并進(jìn)行修改，以降低設(shè)計(jì)成本，提出了應(yīng)用Petri網(wǎng)技術(shù)進(jìn)行缺陷分析的方法。對(duì)FPGA軟件開(kāi)發(fā)過(guò)程中形成的工作流程和實(shí)現(xiàn)流程進(jìn)行了分析，并在發(fā)現(xiàn)缺陷的基礎(chǔ)上進(jìn)行了改進(jìn)設(shè)計(jì)。在某引信安全與起爆控制系統(tǒng)的設(shè)計(jì)過(guò)程中應(yīng)用了該方法，結(jié)果表明：該方法能夠發(fā)現(xiàn)并準(zhǔn)確定位軟件缺陷，而且在Petri網(wǎng)模型基礎(chǔ)上能夠迅速地進(jìn)行軟件改進(jìn)設(shè)計(jì)。

FPGA；Petri網(wǎng)；缺陷分析；軟件設(shè)計(jì)

隨著微電子技術(shù)的發(fā)展，在國(guó)防領(lǐng)域應(yīng)用FPGA進(jìn)行信息處理與控制越來(lái)越多。FPGA本身雖為硬件，但是其設(shè)計(jì)是以軟件編程的形式進(jìn)行。在FPGA軟件設(shè)計(jì)過(guò)程中，人工出錯(cuò)會(huì)導(dǎo)致軟件中殘留缺陷，及時(shí)發(fā)現(xiàn)這些缺陷并進(jìn)行改進(jìn)設(shè)計(jì)是降低軟件設(shè)計(jì)成本的重要方法。軟件設(shè)計(jì)按照工作流程設(shè)計(jì)、實(shí)現(xiàn)流程設(shè)計(jì)、代碼編寫(xiě)的順序進(jìn)行，在每一步之后都應(yīng)進(jìn)行相應(yīng)的分析，以便及時(shí)發(fā)現(xiàn)本步驟內(nèi)的錯(cuò)誤。

1962年，C.A. Petri提出了適合描述并發(fā)、異步、分布式軟件系統(tǒng)規(guī)格的形式化方法Petri網(wǎng)[1]。與普通軟件相比，PFGA軟件采用了并行的設(shè)計(jì)思想[2]，整個(gè)軟件是分模塊進(jìn)行設(shè)計(jì)的，各個(gè)模塊之間通過(guò)信號(hào)相互關(guān)聯(lián)。因此，Petri網(wǎng)非常適合描述FPGA軟件，而且Petri網(wǎng)是從整個(gè)系統(tǒng)的角度，使用圖形表現(xiàn)形式進(jìn)行直觀的描述，且對(duì)軟件能夠做到深入代碼級(jí)別的表示。本文將研究在FPGA軟件設(shè)計(jì)過(guò)程中，基于Petri網(wǎng)進(jìn)行缺陷分析與改進(jìn)設(shè)計(jì)的方法。

1 Petri網(wǎng)及建模

1.1 Petri網(wǎng)[3]

Petri網(wǎng)定義為一個(gè)六元組(P，T，F(xiàn)，K，W，M0)，其中：P為站(或稱(chēng)為位置)集合；T為遷移集合；F為有向弧集；K為對(duì)應(yīng)位置中能夠容納令牌的最大數(shù)量；W為權(quán)函數(shù)，表示有向弧的權(quán)值；M0為初始標(biāo)志。站代表狀態(tài)，遷移代表活動(dòng)。

系統(tǒng)當(dāng)前的狀態(tài)可以用Petri網(wǎng)的標(biāo)志表示，標(biāo)志即Petri網(wǎng)中令牌的分布情況。如圖1中的(Pi，Ti，Pj)網(wǎng)，它含有2個(gè)站，其中:遷移觸發(fā)前的標(biāo)志為M0=(2，0)，代表站Pi中含有2個(gè)令牌，站Pj中沒(méi)有令牌；遷移發(fā)射后的狀態(tài)變?yōu)闃?biāo)志M1=(0，1)，代表站Pi中沒(méi)有令牌，站Pj中含有1個(gè)令牌。

圖1 標(biāo)志示意圖

1.2 基于軟件流程的Petri網(wǎng)建模

1.2.1 軟件相關(guān)單元的Petri網(wǎng)建模

軟件相關(guān)單元是指會(huì)影響軟件運(yùn)行過(guò)程或受軟件運(yùn)行影響的變量、寄存器和外部元器件等。因?yàn)檫@些單元具有保持自身狀態(tài)不變的特性，如果直接在整個(gè)系統(tǒng)網(wǎng)中對(duì)其進(jìn)行建模，就會(huì)造成整體Petri網(wǎng)過(guò)于復(fù)雜。下面，以標(biāo)志變量為例對(duì)軟件相關(guān)單元的Petri網(wǎng)建模進(jìn)行說(shuō)明。

標(biāo)志變量是標(biāo)志某過(guò)程是否已經(jīng)發(fā)生的變量，該過(guò)程的發(fā)生將影響標(biāo)志變量的值，其通常含有0和1兩個(gè)值。設(shè)計(jì)標(biāo)志變量的Petri網(wǎng)模型如圖2所示，標(biāo)志變量的示意圖如圖3所示。圖2模型中共包含2個(gè)站，分別代表標(biāo)志變量的值為0和1。圖3在軟件的整體Petri網(wǎng)中使用，通過(guò)在其輸入弧上添加置0或者置1的命令，來(lái)明確軟件對(duì)標(biāo)志變量值的影響。

圖2 標(biāo)志變量的Petri網(wǎng)模型

圖3 標(biāo)志變量的示意圖

標(biāo)志變量的Petri網(wǎng)模型在軟件整體Petri網(wǎng)模型中受Ti和Tj的輸入站控制。通過(guò)分析標(biāo)志變量的物理性質(zhì)，對(duì)其運(yùn)行規(guī)則進(jìn)行如下規(guī)定：

1)在Ti或Tj遷移的輸入站中有令牌出現(xiàn)時(shí)，遷移立即發(fā)射，并且在軟件Petri網(wǎng)模型中存在沖突遷移時(shí)，Ti或Tj優(yōu)先發(fā)射；

2)在標(biāo)志變量的當(dāng)前值為0、Ti的輸入站中含有令牌時(shí)，或在標(biāo)志變量的當(dāng)前值為1、Tj的輸入站中含有令牌時(shí)，輸入站中的令牌自動(dòng)消失，標(biāo)志變量的值保持不變；

3)其他運(yùn)行規(guī)則與Petri網(wǎng)的基本運(yùn)行規(guī)則相同。

1.2.2 系統(tǒng)完整的Petri網(wǎng)建模

根據(jù)軟件流程，結(jié)合相關(guān)單元模型建立總的Petri網(wǎng)模型。軟件流程轉(zhuǎn)換成Petri網(wǎng)模型遵循如下3個(gè)規(guī)律[4-5]：

1)將流程圖中用矩形框表示的進(jìn)程轉(zhuǎn)變成Petri網(wǎng)中的遷移；

2)將流程圖中的連接弧轉(zhuǎn)變成Petri網(wǎng)中的站；

3)將流程圖中的判斷節(jié)點(diǎn)轉(zhuǎn)變成起判斷作用的站及該站的2個(gè)遷移后集。

2 基于Petri網(wǎng)的軟件缺陷分析方法

2.1 軟件設(shè)計(jì)過(guò)程分析

軟件設(shè)計(jì)的過(guò)程為：1)依據(jù)軟件需求進(jìn)行工作流程的設(shè)計(jì)[6]，工作流程代表的是軟件要干什么，對(duì)于FPGA軟件，其對(duì)應(yīng)的是軟件的輸入和輸出是什么；2)根據(jù)工作流程，對(duì)軟件的實(shí)現(xiàn)流程進(jìn)行分析，實(shí)現(xiàn)流程是指軟件怎么運(yùn)行，即要得到所需的輸入、輸出,軟件自身是如何動(dòng)作的；3)根據(jù)軟件實(shí)現(xiàn)流程進(jìn)行代碼的編寫(xiě)。

對(duì)于復(fù)雜的軟件，由工作流程設(shè)計(jì)實(shí)現(xiàn)流程，可以先根據(jù)軟件功能將工作流程劃分為相對(duì)獨(dú)立的流程段，然后分別對(duì)各個(gè)流程段的軟件實(shí)現(xiàn)流程進(jìn)行設(shè)計(jì)。在工作流程正確的前提下，如果各個(gè)流程段的實(shí)現(xiàn)流程都正確，則能夠說(shuō)明系統(tǒng)完整的實(shí)現(xiàn)流程是正確的。

由于實(shí)現(xiàn)流程與代碼基本一致，所以對(duì)代碼的分析與對(duì)實(shí)現(xiàn)流程的分析基本相同。因此在進(jìn)行軟件的缺陷分析時(shí)，只需對(duì)工作流程和實(shí)現(xiàn)流程進(jìn)行分析即可。

2.2 Petri網(wǎng)缺陷分析方法

對(duì)于一個(gè)Petri網(wǎng)，在其初始標(biāo)志下，通過(guò)使能的遷移，會(huì)觸發(fā)Petri網(wǎng)產(chǎn)生新的標(biāo)志，在新的標(biāo)志下又有新使能的遷移，如此反復(fù)，將得到更多的標(biāo)志，這一系列的標(biāo)志可以用樹(shù)結(jié)構(gòu)來(lái)表示，被稱(chēng)為覆蓋樹(shù)[7-11]。覆蓋樹(shù)以初始標(biāo)志作為根節(jié)點(diǎn)，經(jīng)過(guò)使能的遷移，由初始標(biāo)志得到的新標(biāo)志作為樹(shù)中的節(jié)點(diǎn)；樹(shù)的葉子節(jié)點(diǎn)為無(wú)使能遷移的標(biāo)志或者重復(fù)出現(xiàn)的標(biāo)志。這樣,覆蓋樹(shù)就覆蓋了Petri網(wǎng)的所有可達(dá)標(biāo)志。因?yàn)镻etri網(wǎng)的標(biāo)志表示系統(tǒng)的狀態(tài)，所以覆蓋樹(shù)也就覆蓋了系統(tǒng)可能出現(xiàn)的全部狀態(tài)，通過(guò)分析覆蓋樹(shù)就能夠分析整個(gè)系統(tǒng)的狀態(tài)。

通過(guò)前面的分析，在軟件設(shè)計(jì)過(guò)程中利用Petri網(wǎng)技術(shù)進(jìn)行缺陷分析，可以按照以下過(guò)程進(jìn)行：

1) 進(jìn)行需求分析，進(jìn)而設(shè)計(jì)軟件的工作流程；

2) 建立軟件工作流程的Petri網(wǎng)模型，并構(gòu)建相應(yīng)的覆蓋樹(shù)；

3)通過(guò)分析覆蓋樹(shù),對(duì)軟件工作流程進(jìn)行分析，并在發(fā)現(xiàn)錯(cuò)誤的前提下進(jìn)行改進(jìn)設(shè)計(jì)；

4)劃分工作流程為相對(duì)獨(dú)立的功能模塊；

5)對(duì)軟件各功能模塊分別建立詳細(xì)的實(shí)現(xiàn)流程；

6)根據(jù)軟件實(shí)現(xiàn)流程，建立相應(yīng)的Petri網(wǎng)模型，并構(gòu)建覆蓋樹(shù)；

7)通過(guò)分析覆蓋樹(shù)，對(duì)軟件的實(shí)現(xiàn)流程進(jìn)行分析，并在發(fā)現(xiàn)錯(cuò)誤的前提下進(jìn)行改進(jìn)設(shè)計(jì)。

3 基于Petri網(wǎng)的FPGA軟件改進(jìn)設(shè)計(jì)

3.1 內(nèi)鎖

系統(tǒng)中出現(xiàn)的含有錯(cuò)誤的狀態(tài)可能是在同一個(gè)標(biāo)志中同時(shí)出現(xiàn)了會(huì)導(dǎo)致錯(cuò)誤的2個(gè)站，為了避免這種情況出現(xiàn)，可以在Petri網(wǎng)中加入限制它們同時(shí)出現(xiàn)的內(nèi)鎖。加入內(nèi)鎖的Petri網(wǎng)如圖4所示，為了避免P3和P2同時(shí)出現(xiàn)，向其中加入一個(gè)新站Padd，這樣T1的發(fā)射必須在T2之后，保證了P3中丟掉令牌以后，P2才能獲得令牌，從而在同一個(gè)標(biāo)志中不可能同時(shí)出現(xiàn)P2和P3。內(nèi)鎖在軟件中通常采用監(jiān)控程序來(lái)實(shí)現(xiàn)。

圖4 加入內(nèi)鎖的Petri網(wǎng)

3.2 標(biāo)志變量

在覆蓋樹(shù)構(gòu)造過(guò)程中，Petri網(wǎng)中某一部分可能會(huì)意外重復(fù)地運(yùn)行。為了避免這種情況發(fā)生，可以向Petri網(wǎng)中添加標(biāo)志變量，并以該變量作為意外重復(fù)運(yùn)行部分運(yùn)行的前提條件。如：某FPGA軟件的一個(gè)功能是在FPGA復(fù)位后，首先進(jìn)行10 s的定時(shí)，在定時(shí)結(jié)束后發(fā)送“計(jì)時(shí)結(jié)束信息”，設(shè)計(jì)其Petri網(wǎng)模型如圖5所示。通過(guò)分析發(fā)現(xiàn)：在晶振信號(hào)的驅(qū)動(dòng)下，定時(shí)器會(huì)重復(fù)計(jì)時(shí)，并在每一次計(jì)時(shí)結(jié)束后，重復(fù)發(fā)送遠(yuǎn)距離接電計(jì)時(shí)結(jié)束信息。為了避免這種情況發(fā)生，向Petri網(wǎng)模型中引入r_restrict標(biāo)志變量，如圖6所示。在復(fù)位后置r_restrict為0，在控制遠(yuǎn)距離接電時(shí)間的計(jì)數(shù)器之前，加入判斷r_restrict是否為0的條件，并在一次定時(shí)后置r_restrict為1，從而防止了遠(yuǎn)距離接電計(jì)數(shù)器的重復(fù)計(jì)時(shí)。

圖5 意外重復(fù)發(fā)射T8的Petri網(wǎng)

圖6 加入標(biāo)志變量后的Petri網(wǎng)

4 實(shí)例應(yīng)用

在某引信安全與起爆控制系統(tǒng)的設(shè)計(jì)中，對(duì)FPGA軟件的工作流程進(jìn)行了設(shè)計(jì)，并對(duì)其進(jìn)行了缺陷分析，結(jié)果發(fā)現(xiàn)：在工作流程中沒(méi)有缺陷。劃分了FPGA軟件的功能模塊，設(shè)計(jì)了各功能模塊的實(shí)現(xiàn)流程，并對(duì)其進(jìn)行了缺陷分析，結(jié)果發(fā)現(xiàn)：在轉(zhuǎn)速突降環(huán)境判斷模塊存在缺陷。該模塊的Petri網(wǎng)模型如圖7所示，其中a、b、c、d代表輸入的電平量，其值取1時(shí)為高電平，取0時(shí)為低電平，復(fù)位后初始化為abcd=0000。圖7中虛線框內(nèi)為改進(jìn)后添加的部分。

對(duì)改進(jìn)之前設(shè)計(jì)的實(shí)現(xiàn)流程構(gòu)建覆蓋樹(shù)，如圖8所示。圖中標(biāo)志Mp+5和Mp雖然相同，但根據(jù)實(shí)際的時(shí)序運(yùn)行情況可知：Mp+5和Mp此時(shí)所表示的系統(tǒng)狀態(tài)已經(jīng)發(fā)生改變，Mp到Mp+4的所有標(biāo)志均是由上一次時(shí)鐘的變化引起的。而在Mp+5到Mp+7這一標(biāo)志處，則表示系統(tǒng)馬上進(jìn)入下一個(gè)時(shí)鐘周期，以及由下一個(gè)時(shí)鐘周期的開(kāi)始時(shí)刻所引起的系統(tǒng)狀態(tài)變化。所以在標(biāo)志Mp+5處還要繼續(xù)進(jìn)行分析。圖中帶箭頭虛線代表的是從標(biāo)志Mp到Mp+7的重復(fù)變遷過(guò)程；所不同的只是隨著循環(huán)次數(shù)的增加，P105中的令牌數(shù)ω在逐漸增加。

根據(jù)圖8可知：在充電結(jié)束時(shí)，系統(tǒng)又意外地返回了系統(tǒng)運(yùn)行的中間狀態(tài)，即圖中最后一個(gè)標(biāo)志(P24，P4，P106，P104，P108)處，這將使K2不能正常打開(kāi)，發(fā)火電容持續(xù)充電，這是由r_env_2被重復(fù)地置1造成的。

圖7 轉(zhuǎn)速突降環(huán)境判斷模塊Petri網(wǎng)模型

圖8 轉(zhuǎn)速突降環(huán)境判斷模塊Petri網(wǎng)覆蓋樹(shù)

為了消除該軟件缺陷，向Petri網(wǎng)中添加一個(gè)標(biāo)志變量r_env_2_rstr，如圖7中虛線框所示。復(fù)位時(shí)將r_env_2_rstr置0，只有在r_env_2_rstr=0的情況下，才能控制K2閉合，發(fā)火電容充電。在T15發(fā)射時(shí)，將r_env_2_rstr置1，這樣在T15發(fā)射后r_env_2置0，并且不能再回到r_env_2=1的狀態(tài)，從而T25發(fā)射，K2正常打開(kāi)，發(fā)火電容停止充電。

[1] Lv Y Q, Lee C K M, Wu Z, et al. Priority-based Distributed Manufacturing Process Modeling via Hierarchical Timed Color Petri Net[C]. Washington, DC: IEEE Computer Society, 2013.

[2] 馬克斯菲爾德. FPGA權(quán)威指南[M]. 杜生海,譯.北京:人民郵電出版社,2012.

[3] 孫海春, 杜玉越. 基于程序Petri網(wǎng)的新型軟件開(kāi)發(fā)方法研究[J]. 系統(tǒng)仿真學(xué)報(bào), 2009, 20(增刊): 55-58.

[4] 張賢彪, 尚雅玲. 引信安全系統(tǒng)信息控制邏輯分析[J].四川兵工學(xué)報(bào), 2010, 31(1): 32-35.

[5] 吳越, 王宏偉, 史長(zhǎng)虹, 等. 引信安全系統(tǒng)慣性保險(xiǎn)技術(shù)研究[J].中北大學(xué)學(xué)報(bào): 自然科學(xué)版, 2012, 33(3): 257-261.

[6] 馬海云. 面向過(guò)程的軟件設(shè)計(jì)及優(yōu)化技術(shù)[M].北京：國(guó)防工業(yè)出版社, 2013.

[7] 趙靜麗.基于Petri網(wǎng)的構(gòu)件軟件系統(tǒng)的安全性分析[D].太原：太原科技大學(xué),2011.

[8] 林紅, 楊瀚程. 基于Petri網(wǎng)的軟件故障樹(shù)分析[J]. 火控雷達(dá)技術(shù), 2013,42(4):40-43.

[9] 雷軍環(huán). 利用廣義隨機(jī)Petri網(wǎng)分析軟件系統(tǒng)可靠性[J].計(jì)算機(jī)測(cè)量與控制, 2013,21(2):433-435, 444.

[10] 趙成貴, 普兆斌. 一種軟件可靠性評(píng)估模型及其Petri網(wǎng)描述[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(1):141-144.

[11] 王佳慧, 王書(shū)鋒. 隨機(jī)Petri網(wǎng)可視化軟件的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(5):1845-1848.

(責(zé)任編輯:尚彩娟)

Defect Analysis and Improvement Design of FPGA Software Based on Petri Net

QI Xing-lin, MA Ji-cun, YU Chun-hua

(Department of Ammunition Engineering, Ordnance Engineering College, Shijiazhuang 050003, China)

In order to discover the design defect of FPGA software and improve the software in the early stage of development process to decrease the cost of development, the method of using Petri net in defect analysis is proposed. The working flow and realization flow are analyzed, and on the basis of defects discovered, the software is improved. This method is used in a design process of safety and detonating control system, results prove this method can discover and locate defects exactly, based on the Petri net model, software improvement can be gained easily.

FPGA; Petri net; defect analysis; software design

1672-1497(2015)01-0090-05

2014- 11- 18

齊杏林(1964-)，男，教授，博士。

TP306+.3

A

10.3969/j.issn.1672-1497.2015.01.018