基于Petri網的FPGA軟件缺陷分析與改進設計

齊杏林， 馬繼存， 余春華

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

基于Petri網的FPGA軟件缺陷分析與改進設計

齊杏林， 馬繼存， 余春華

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

為了在FPGA軟件開發過程的早期發現設計缺陷并進行修改，以降低設計成本，提出了應用Petri網技術進行缺陷分析的方法。對FPGA軟件開發過程中形成的工作流程和實現流程進行了分析，并在發現缺陷的基礎上進行了改進設計。在某引信安全與起爆控制系統的設計過程中應用了該方法，結果表明：該方法能夠發現并準確定位軟件缺陷，而且在Petri網模型基礎上能夠迅速地進行軟件改進設計。

FPGA；Petri網；缺陷分析；軟件設計

隨著微電子技術的發展，在國防領域應用FPGA進行信息處理與控制越來越多。FPGA本身雖為硬件，但是其設計是以軟件編程的形式進行。在FPGA軟件設計過程中，人工出錯會導致軟件中殘留缺陷，及時發現這些缺陷并進行改進設計是降低軟件設計成本的重要方法。軟件設計按照工作流程設計、實現流程設計、代碼編寫的順序進行，在每一步之后都應進行相應的分析，以便及時發現本步驟內的錯誤。

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

1 Petri網及建模

1.1 Petri網[3]

Petri網定義為一個六元組(P，T，F，K，W，M0)，其中：P為站(或稱為位置)集合；T為遷移集合；F為有向弧集；K為對應位置中能夠容納令牌的最大數量；W為權函數，表示有向弧的權值；M0為初始標志。站代表狀態，遷移代表活動。

系統當前的狀態可以用Petri網的標志表示，標志即Petri網中令牌的分布情況。如圖1中的(Pi，Ti，Pj)網，它含有2個站，其中:遷移觸發前的標志為M0=(2，0)，代表站Pi中含有2個令牌，站Pj中沒有令牌；遷移發射后的狀態變為標志M1=(0，1)，代表站Pi中沒有令牌，站Pj中含有1個令牌。

圖1 標志示意圖

1.2 基于軟件流程的Petri網建模

1.2.1 軟件相關單元的Petri網建模

軟件相關單元是指會影響軟件運行過程或受軟件運行影響的變量、寄存器和外部元器件等。因為這些單元具有保持自身狀態不變的特性，如果直接在整個系統網中對其進行建模，就會造成整體Petri網過于復雜。下面，以標志變量為例對軟件相關單元的Petri網建模進行說明。

標志變量是標志某過程是否已經發生的變量，該過程的發生將影響標志變量的值，其通常含有0和1兩個值。設計標志變量的Petri網模型如圖2所示，標志變量的示意圖如圖3所示。圖2模型中共包含2個站，分別代表標志變量的值為0和1。圖3在軟件的整體Petri網中使用，通過在其輸入弧上添加置0或者置1的命令，來明確軟件對標志變量值的影響。

圖2 標志變量的Petri網模型

圖3 標志變量的示意圖

標志變量的Petri網模型在軟件整體Petri網模型中受Ti和Tj的輸入站控制。通過分析標志變量的物理性質，對其運行規則進行如下規定：

1)在Ti或Tj遷移的輸入站中有令牌出現時，遷移立即發射，并且在軟件Petri網模型中存在沖突遷移時，Ti或Tj優先發射；

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

3)其他運行規則與Petri網的基本運行規則相同。

1.2.2 系統完整的Petri網建模

根據軟件流程，結合相關單元模型建立總的Petri網模型。軟件流程轉換成Petri網模型遵循如下3個規律[4-5]：

1)將流程圖中用矩形框表示的進程轉變成Petri網中的遷移；

2)將流程圖中的連接弧轉變成Petri網中的站；

3)將流程圖中的判斷節點轉變成起判斷作用的站及該站的2個遷移后集。

2 基于Petri網的軟件缺陷分析方法

2.1 軟件設計過程分析

軟件設計的過程為：1)依據軟件需求進行工作流程的設計[6]，工作流程代表的是軟件要干什么，對于FPGA軟件，其對應的是軟件的輸入和輸出是什么；2)根據工作流程，對軟件的實現流程進行分析，實現流程是指軟件怎么運行，即要得到所需的輸入、輸出,軟件自身是如何動作的；3)根據軟件實現流程進行代碼的編寫。

對于復雜的軟件，由工作流程設計實現流程，可以先根據軟件功能將工作流程劃分為相對獨立的流程段，然后分別對各個流程段的軟件實現流程進行設計。在工作流程正確的前提下，如果各個流程段的實現流程都正確，則能夠說明系統完整的實現流程是正確的。

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

2.2 Petri網缺陷分析方法

對于一個Petri網，在其初始標志下，通過使能的遷移，會觸發Petri網產生新的標志，在新的標志下又有新使能的遷移，如此反復，將得到更多的標志，這一系列的標志可以用樹結構來表示，被稱為覆蓋樹[7-11]。覆蓋樹以初始標志作為根節點，經過使能的遷移，由初始標志得到的新標志作為樹中的節點；樹的葉子節點為無使能遷移的標志或者重復出現的標志。這樣,覆蓋樹就覆蓋了Petri網的所有可達標志。因為Petri網的標志表示系統的狀態，所以覆蓋樹也就覆蓋了系統可能出現的全部狀態，通過分析覆蓋樹就能夠分析整個系統的狀態。

通過前面的分析，在軟件設計過程中利用Petri網技術進行缺陷分析，可以按照以下過程進行：

1) 進行需求分析，進而設計軟件的工作流程；

2) 建立軟件工作流程的Petri網模型，并構建相應的覆蓋樹；

3)通過分析覆蓋樹,對軟件工作流程進行分析，并在發現錯誤的前提下進行改進設計；

4)劃分工作流程為相對獨立的功能模塊；

5)對軟件各功能模塊分別建立詳細的實現流程；

6)根據軟件實現流程，建立相應的Petri網模型，并構建覆蓋樹；

7)通過分析覆蓋樹，對軟件的實現流程進行分析，并在發現錯誤的前提下進行改進設計。

3 基于Petri網的FPGA軟件改進設計

3.1 內鎖

系統中出現的含有錯誤的狀態可能是在同一個標志中同時出現了會導致錯誤的2個站，為了避免這種情況出現，可以在Petri網中加入限制它們同時出現的內鎖。加入內鎖的Petri網如圖4所示，為了避免P3和P2同時出現，向其中加入一個新站Padd，這樣T1的發射必須在T2之后，保證了P3中丟掉令牌以后，P2才能獲得令牌，從而在同一個標志中不可能同時出現P2和P3。內鎖在軟件中通常采用監控程序來實現。

圖4 加入內鎖的Petri網

3.2 標志變量

在覆蓋樹構造過程中，Petri網中某一部分可能會意外重復地運行。為了避免這種情況發生，可以向Petri網中添加標志變量，并以該變量作為意外重復運行部分運行的前提條件。如：某FPGA軟件的一個功能是在FPGA復位后，首先進行10 s的定時，在定時結束后發送“計時結束信息”，設計其Petri網模型如圖5所示。通過分析發現：在晶振信號的驅動下，定時器會重復計時，并在每一次計時結束后，重復發送遠距離接電計時結束信息。為了避免這種情況發生，向Petri網模型中引入r_restrict標志變量，如圖6所示。在復位后置r_restrict為0，在控制遠距離接電時間的計數器之前，加入判斷r_restrict是否為0的條件，并在一次定時后置r_restrict為1，從而防止了遠距離接電計數器的重復計時。

圖5 意外重復發射T8的Petri網

圖6 加入標志變量后的Petri網

4 實例應用

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

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

根據圖8可知：在充電結束時，系統又意外地返回了系統運行的中間狀態，即圖中最后一個標志(P24，P4，P106，P104，P108)處，這將使K2不能正常打開，發火電容持續充電，這是由r_env_2被重復地置1造成的。

圖7 轉速突降環境判斷模塊Petri網模型

圖8 轉速突降環境判斷模塊Petri網覆蓋樹

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

[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權威指南[M]. 杜生海,譯.北京:人民郵電出版社,2012.

[3] 孫海春, 杜玉越. 基于程序Petri網的新型軟件開發方法研究[J]. 系統仿真學報, 2009, 20(增刊): 55-58.

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

[5] 吳越, 王宏偉, 史長虹, 等. 引信安全系統慣性保險技術研究[J].中北大學學報: 自然科學版, 2012, 33(3): 257-261.

[6] 馬海云. 面向過程的軟件設計及優化技術[M].北京：國防工業出版社, 2013.

[7] 趙靜麗.基于Petri網的構件軟件系統的安全性分析[D].太原：太原科技大學,2011.

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

[9] 雷軍環. 利用廣義隨機Petri網分析軟件系統可靠性[J].計算機測量與控制, 2013,21(2):433-435, 444.

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

[11] 王佳慧, 王書鋒. 隨機Petri網可視化軟件的設計與實現[J].計算機工程與設計,2011,32(5):1845-1848.

(責任編輯:尚彩娟)

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