利用智能控制流方法的嵌入式軟件故障檢測*

周改云，張國平，呂瓊帥，黎遠松

（1.平頂山學院 軟件學院，河南 平頂山 467000；2.四川理工學院 計算機學院，四川 自貢 643000）

利用智能控制流方法的嵌入式軟件故障檢測*

周改云1，張國平1，呂瓊帥1，黎遠松2

（1.平頂山學院 軟件學院，河南 平頂山 467000；2.四川理工學院 計算機學院，四川 自貢 643000）

針對現有的嵌入式軟件故障檢測方法性能低、開銷大的缺點，提出一種智能選擇檢測點的控制流方法，其創新之處主要為：使用變量的頻率和基本塊的執行頻率用作選擇重要變量和基本塊的兩個參數。檢測的基本流程是首先過濾器還原標準C語句為偽代碼語句，然后掃描儀獲取偽代碼，并發送它到解析器，進行程序的控制流圖提取。最后，解析器提取程序的前后支配樹，運用候選塊尋找算法進行節點分類，獲得塊斷言和變量。實驗結果表明，固化代碼中程序執行時間少于RSCFC方法，但是內存開銷和代碼開銷幾乎相同，執行時間比率接近1，顯著提高故障檢測率。

嵌入式軟件；智能選擇；控制流；內核塊；基本塊

0　引言

嵌入式系統[1]應用非常廣泛，基本隨處可見，如衛星、汽車和飛機等，這些系統的錯誤行為可能導致災難性事故，所以這些設備必須在最短時間內檢測到故障。一般故障分為三類：永久性故障、間歇性故障和瞬時性故障，在這些故障中，瞬時故障最為常見，如程序計數器和存儲器元件故障，可能會導致控制流錯誤(Control Flow Errors，CFES)，多達 70%的瞬時故障導致程序執行的 CFES[2]。因而，用于檢查和解決基于控制流的方法對內存和性能的優化非常重要[3，4]。

文獻[5]是一種劃分程序為基本塊的方法，它利用簽名查找塊之間的關系。通過在運行時間簽名和每個塊開始和結尾有額外指令引導的當前塊的位置信息之間“取與”操作進行控制流故障檢測?？刂屏鳈z查(RSCFC)的特點是在低內存和低性能開銷下可以找到更多故障[6]。該方法的內存和性能開銷都接近CFCSS技術，但它的故障覆蓋率更高。RSCFC基本塊的總數受機器字長限制。

本文提出一種提高控制流檢測效率的新方法，即在運用控制流檢查方法之前，先處理程序代碼，運用基于內核概念的候選塊選擇重要基本塊[7]。執行內核所有頂點的任一測試集即執行流程圖的所有頂點。本文方法的創新之處有：所用變量的頻率和基本塊的執行頻率用于選擇重要變量和基本塊的兩個參數；內核塊用于重要基本塊的選擇；開發人員可以權衡檢測延遲和性能開銷。

1　提出的方法

本文提出一種以智能方式選擇檢測點。在候選塊集中插入控制流斷言，基于內核塊選擇候選塊集。定義候選塊集如下：

定義 1(候選塊集)：候選塊集是具有控制流檢查更高優先級的基本塊，該集合可以基于內核和基本塊頻率來創建。

1.1基于內核的塊選擇算法

本文方法基于文獻[5]創建程序圖，利用算法1找到基本塊執行頻率。如果檢測延遲，則向用戶詢問表示檢測延遲所需百分比的DL值。然后，使用式(1)計算L：

式中，L是必須插入到控制流檢測點的塊數，若檢測延遲并不重要，控制流檢查點將插入候選塊集合。找到候選塊集合后，基于它們的分類插入斷言分類為兩組。

另一種方法是候選塊查找算法，如算法1所示。該算法用于計算候選塊。首先計算程序流圖的前后支配樹，表示為 Tpre和 Tpost。接著，比較樹 Lpre和 Lpost的葉子數，選擇其中具有最小塊數的一個為候選塊集合。

如果性能對于用戶很重要，候選塊集合將用于斷言控制流檢查點。但是，若檢測延遲比較重要，L將與候選塊數相比較，若候選塊數小于 L，則該方法從 Lpost·Lpre選擇高頻塊，并添加它們到候選塊集合。若它們為空，將在Tpre或 Tpost樹的 h－1級運用該方法。通過這種方法，塊將添加到候選塊集合。

如果候選塊數比L大，第一高頻率執行節點將選擇為候選塊集合，斷言將插入這些塊。候選塊集合將從后支配和前支配樹基于混合選擇節點創建。優先級將給予具有高頻率執行和100%分支覆蓋的塊。

第三種方法是節點執行頻率計算方法，即算法2，該方法獲取程序圖作為輸入，并在每個塊的開頭插入計數器。在源代碼中運用這些改變后，程序將運行5n次，其中n為程序節點數。

(1)算法1：基于內核的候選塊查找算法的核心代碼

(2)算法 2：塊執行頻率計算算法 Find－basic－blockfrequency(V，E)

1.2數據流錯誤檢查

在程序中應用定義－使用鏈算法[8]確定變量頻率，該算法表明變量到達鏈程序中的不同點。找到變量的定義－使用頻率后，使用頻率進行分類。本文提出的智能塊選擇方法如算法3：

(3)算法3：變量選擇算法

1.3基本塊簽名生成

本文方法中，簽名生成與 RSCFC方法類似，succ(vi)＝{vf，…，vk，…，vm}定義為vi的后繼節點集，類似地，pred(vi)定義為vi的前驅節點集，基于程序流圖P(V，E)。當且僅當bri，j∈E，節點vj∈succ(vi)。類似地，僅當 brj，i∈E，節點vj∈pred(vi)。P執行期間，如果 bri，j?E，bri，j非法，即控制流錯誤。如圖1所示，succ(v2)＝{v3}，pred(v2)＝{v1}。如果存在從v2到v5的跳，則br2，5為非法跳，因為v5不屬于succ(v2)。假設程序有 n個基本塊，標記為 v1，v2，…，vn，則設置塊vi的簽名 Si如下：

圖1　插入排序函數的控制流圖

式中，上標1、f、k、m和 n+1分別表示從低位開始 Si的第1、第f、第k、第m和第n+1位，即如果程序有n個基本塊，則基本塊的簽名應該總共有 n+1位，其最高位n+ 1通常設置為“1”，Si中每一位，除了第n+1位，第2位表示節點v2，第n位表示節點vn，如果P中節點是vi的后繼節點，則Si的對應位設為“1”，否則，設為“0”。

1.4基于塊間控制流檢測的候選塊

本文使用專用全局變量S檢查程序的控制器，包含程序流圖中當前節點相關的運行時間簽名，當在程序圖上運用候選塊尋找算法時，劃分塊為候選成員塊和普通成員塊。

識別這些集后，在塊中插入斷言，引入 Kernel-test斷言到每個基本塊開頭，引入set斷言到每個基本塊末尾。當該控制從一個塊vj轉移到一個如vi的內核塊時，Kernel-test斷言使用下列兩個值檢查該目的節點 vi是否合法：

(1)前一個節點的簽名(分支的源節點，vj)；

(2)程序流圖中當前節點的位置信息Li。

Li的創建類似于 Si，但是僅設置 Li的一位為“1”，該位表示程序流圖中vi的數量為i。如圖1所示，L1=000001，L5=010000?；緣K vi的 Kernel-test和 set語句設計如下：

在非候選塊成員的塊中插入上述斷言，引入Kernelfree-test斷言到每個基本塊開頭，引入set斷言到每個基本塊末尾。當該控制從一個塊vj轉移到另一vi的塊時，在S中保存Si的值，直到候選塊中檢查它。Kernel-freetest和set語句設計如下：

修改的代碼如圖2所示，在插入排序圖中運用內核算法之后，塊劃分成兩類，塊3和5是內核塊，必須在它們上插入Kernel-test斷言，但是塊1、2、4、6是普通塊，則在它們上插入Kernel-free-test斷言。當取set斷言時，S和 Li執行異或操作結果為“0”，“-”的邏輯非將變為“-1”，最終，用新運行時間簽名 Si&(-1)=Si更新 S。另一方面，假設節點 vi不是 vj的后繼，則 S&Li應該為 0，執行節點 vi的 Kernel-test斷言之后將檢測到控制流錯誤，該控制將轉移到錯誤處理例程。

圖2　修改的代碼

2　實驗結果與評估

2.1原型實現

修改代碼的生成過程如圖3所示，本文使用C++實現上述方法，并在代碼中插入斷言，執行該程序尋找瞬時錯誤。該工作首先使用過濾器還原標準C語句為偽代碼語句，還原不改變控制流的語句為空分號。然后，掃描儀獲取偽代碼，并發送它到解析器，進行程序的控制流圖提取。之后，解析器提取程序的前后支配樹，并在其上運用候選塊尋找算法，進行節點分類。解析器的輸出是程序圖表和候選塊信息，在源節點上運用算法1，獲得塊斷言和變量。最后，生成如圖3所示的修改代碼。

圖3　修改代碼生成的過程

2.2實驗評估

為了評估本文方法的有效性，比較修改代碼和原始代碼的內存大小和性能開銷，還評估了兩種情況下本方法的故障檢測能力，并與 RSCFC方法進行了比較，為了實現該比較，選擇下列 3個基準：（1）插入排序(IN)；（2）快速排序(QS)；（3）矩陣乘法(MM)。所有程序均在2G內存，Win7的i3 PC上執行。

使用AQtime6[9]配置軟件估計性能和內存開銷，表1和表2分別表示基于原始代碼的 RSCFC方法和本文方法的內存率、性能開銷和固化代碼大小，各個指標表示基準程序的倍數。

比較表1和表2，可以得出在候選塊上運用本文方法能夠降低性能開銷，檢測延遲(DL)基于下列公式：

表1　運用RSCFC方法后的內存和性能開銷

表2　運用本方法后的內存和性能開銷

最大故障檢測延遲是W，如果在候選塊上運用本文方法，最大故障檢測延遲將為(N/L)×W。

根據上述公式，增加候選塊數能降低故障檢測延遲，如果候選塊數降低，檢測延遲也會增加。從表1和表2的“性能”列中可以觀察到，本方法中程序執行時間少于RSCFC方法，且從表2的“性能”列可以看出，執行時間比率接近1，即程序執行時間幾乎保持相同，但是固化代碼能檢測瞬時錯誤。

3　結論

本文運用控制流檢測方法檢測嵌入式軟件故障，預處理包括使用高頻變量和重要基本塊的檢測，改進了RSCFC方法中關系簽名的有效性。此外，使用本文方法，使嵌入式軟件開發人員能權衡檢測延遲和性能開銷。使用3個基準的實驗結果表明，固化代碼中程序執行時間少于 RSCFC方法，但是內存開銷和代碼開銷幾乎相同，本文方法產生的固化代碼與原始代碼的程序執行時間幾乎相同。

未來，將測試和評估在固化程序中由專業故障工具插入的故障，研究基于程序語義在程序中插入斷言的新方法。

[1]張海軍，王艷軍，劉海見，等.基于ADS2的嵌入式軟件測試仿真建模方法研究[J].電子技術應用，2014，40(6)：17-19.

[2]MOHAMED A，ZULKERNINE M.A connection-based signature approach for control flow error detection[C]. Dependable，Autonomic and Secure Computing(DASC)，2011 IEEE Ninth International Conference on.IEEE，2011，24(7)：129-136.

[3]PRASAD K S S.Embeded technology for vehicle cabin safety monitoring and alerting system[J].Middle-East Journal of Scientific Research，2014，20(12)：2210-2212.

[4]王超，傅忠傳，陳紅松，等.低代價鎖步 EDDI：處理器瞬時故障檢測機制[J].計算機學報，2012，35(12)：2562-2572.

[5]ASGHARI S A，KAYNAK O，TAHERI H.An investigation into soft error detection efficiency at operating system level[J]. The Scientific World Journal，2014，24(18)：1047-1053.

[6]徐建軍.面向寄存器軟錯誤的容錯編譯技術研究[D].長沙：國防科學技術大學，2010.

[7]朱雪梅.基于動態方法的嵌入式軟件缺陷檢測技術研究與實現[D].杭州：杭州電子科技大學，2013.

[8]LAM M，SETHI R，ULLMAN J D，et al.Compilers：principles，techniques，and tools[J].2006，22(12)：852-857.

[9]Automated Q A.AQtime[EB/OL].(2010)[2015].http：//www. automatedqa.com/products/aqtime/.

Error detection of embedded software using intelligent control flow method

Zhou Gaiyun1，Zhang Guoping1，Lv Qiongshuai1，Li Yuansong2
(1.School of Software，Pingdingshan University，Pingdingshan 467000，China；(2.School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China)

As the existing embedded software error detection method has low performance and big cost,a control flow method of intelligent selection of detection point is proposed.The ruain innovation is that variable frequency and fundamental frequency for blocks are used as two important variables.The basic process is to detect filter restore the standard C code statement to the pseudo-code statement firstly.Then,the pseudo-code is obtained by scanners,and the code is send to the parser,and the control flow graph is extracted.Finally,the before-after dominant tree parser is extracted by procedures,and the node classification is done by the algorithm of finding candidate block.And the block assertions and variables are obtained.Experimental results show that the running time of the proposed method is less than that of RSCFC method in curing codes,but the memory cost and code cost are almost the same,and the execution time ratio is close to 1.The error detection rate is remarkably improved.

embedded software；intelligent selection；control flow；core block

TP391

A

10.16157/j.issn.0258-7998.2015.10.004

平頂山學院青年基金重點項目(PDSU-QNJJ-2013002)；企業信息化與物聯網測控技術四川省高校重點實驗室項目(2014WZY05)

2015-06-01)

周改云（1980－），女，碩士，講師，主要研究方向：嵌入式、軟件工程等。

張國平（1980-），男，碩士，講師，主要研究方向：軟件工程、嵌入式與軟件開發，移動通信應用等。

呂瓊帥（1985-），男，碩士，講師，主要研究方向：軟件工程、智能算法等。

中文引用格式：周改云，張國平，呂瓊帥，等.利用智能控制流方法的嵌入式軟件故障檢測[J].電子技術應用，2015，41 (10)：20-23.

英文引用格式：Zhou Gaiyun，Zhang Guoping，Lv Qiongshuai，et al.Error detection of embedded software using intelligent control flow method[J].Application of Electronic Technique，2015，41(10)：20-23.