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

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

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

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

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

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

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

0　引言

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

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

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

1　提出的方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3基本塊簽名生成

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

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

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

1.4基于塊間控制流檢測(cè)的候選塊

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

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

(1)前一個(gè)節(jié)點(diǎn)的簽名(分支的源節(jié)點(diǎn)，vj)；

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

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

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

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

圖2　修改的代碼

2　實(shí)驗(yàn)結(jié)果與評(píng)估

2.1原型實(shí)現(xiàn)

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

圖3　修改代碼生成的過(guò)程

2.2實(shí)驗(yàn)評(píng)估

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

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

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

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

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

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

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

3　結(jié)論

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

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

[1]張海軍，王艷軍，劉海見(jiàn)，等.基于ADS2的嵌入式軟件測(cè)試仿真建模方法研究[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]王超，傅忠傳，陳紅松，等.低代價(jià)鎖步 EDDI：處理器瞬時(shí)故障檢測(cè)機(jī)制[J].計(jì)算機(jī)學(xué)報(bào)，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]徐建軍.面向寄存器軟錯(cuò)誤的容錯(cuò)編譯技術(shù)研究[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2010.

[7]朱雪梅.基于動(dòng)態(tài)方法的嵌入式軟件缺陷檢測(cè)技術(shù)研究與實(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é)院青年基金重點(diǎn)項(xiàng)目(PDSU-QNJJ-2013002)；企業(yè)信息化與物聯(lián)網(wǎng)測(cè)控技術(shù)四川省高校重點(diǎn)實(shí)驗(yàn)室項(xiàng)目(2014WZY05)

2015-06-01)

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

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

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

中文引用格式：周改云，張國(guó)平，呂瓊帥，等.利用智能控制流方法的嵌入式軟件故障檢測(cè)[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.