周改云，張國平，呂瓊帥，黎遠(yuǎn)松

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

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

周改云1，張國平1，呂瓊帥1，黎遠(yuǎn)松2

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

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

嵌入式軟件；智能選擇；控制流；內(nèi)核塊；基本塊

0　引言

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

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

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

1　提出的方法

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

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

1.1基于內(nèi)核的塊選擇算法

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

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

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

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

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

第三種方法是節(jié)點執(zhí)行頻率計算方法，即算法2，該方法獲取程序圖作為輸入，并在每個塊的開頭插入計數(shù)器。在源代碼中運(yùn)用這些改變后，程序?qū)⑦\(yùn)行5n次，其中n為程序節(jié)點數(shù)。

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

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

1.2數(shù)據(jù)流錯誤檢查

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

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

1.3基本塊簽名生成

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

圖1　插入排序函數(shù)的控制流圖

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

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

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

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

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

(2)程序流圖中當(dāng)前節(jié)點的位置信息Li。

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

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

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

圖2　修改的代碼

2　實驗結(jié)果與評估

2.1原型實現(xiàn)

修改代碼的生成過程如圖3所示，本文使用C++實現(xiàn)上述方法，并在代碼中插入斷言，執(zhí)行該程序?qū)ふ宜矔r錯誤。該工作首先使用過濾器還原標(biāo)準(zhǔn)C語句為偽代碼語句，還原不改變控制流的語句為空分號。然后，掃描儀獲取偽代碼，并發(fā)送它到解析器，進(jìn)行程序的控制流圖提取。之后，解析器提取程序的前后支配樹，并在其上運(yùn)用候選塊尋找算法，進(jìn)行節(jié)點分類。解析器的輸出是程序圖表和候選塊信息，在源節(jié)點上運(yùn)用算法1，獲得塊斷言和變量。最后，生成如圖3所示的修改代碼。

圖3　修改代碼生成的過程

2.2實驗評估

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

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

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

表1　運(yùn)用RSCFC方法后的內(nèi)存和性能開銷

表2　運(yùn)用本方法后的內(nèi)存和性能開銷

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

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

3　結(jié)論

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

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

[1]張海軍，王艷軍，劉海見，等.基于ADS2的嵌入式軟件測試仿真建模方法研究[J].電子技術(shù)應(yīng)用，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ī)制[J].計算機(jī)學(xué)報，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]徐建軍.面向寄存器軟錯誤的容錯編譯技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2010.

[7]朱雪梅.基于動態(tài)方法的嵌入式軟件缺陷檢測技術(shù)研究與實現(xiàn)[D].杭州：杭州電子科技大學(xué)，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

平頂山學(xué)院青年基金重點項目(PDSU-QNJJ-2013002)；企業(yè)信息化與物聯(lián)網(wǎng)測控技術(shù)四川省高校重點實驗室項目(2014WZY05)

2015-06-01)

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

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

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

中文引用格式：周改云，張國平，呂瓊帥，等.利用智能控制流方法的嵌入式軟件故障檢測[J].電子技術(shù)應(yīng)用，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.