文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.2015.10.004
中文引用格式： 周改云，張國平，呂瓊帥，等. 利用智能控制流方法的嵌入式軟件故障檢測[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.
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)系。通過在運行時間簽名和每個塊開始和結(jié)尾有額外指令引導(dǎo)的當(dāng)前塊的位置信息之間“取與”操作進(jìn)行控制流故障檢測。控制流檢查(RSCFC)的特點是在低內(nèi)存和低性能開銷下可以找到更多故障[6]。該方法的內(nèi)存和性能開銷都接近CFCSS技術(shù)，但它的故障覆蓋率更高。RSCFC基本塊的總數(shù)受機(jī)器字長限制。
本文提出一種提高控制流檢測效率的新方法，即在運用控制流檢查方法之前，先處理程序代碼，運用基于內(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)榭眨瑢⒃赥pre或Tpost樹的h-1級運用該方法。通過這種方法，塊將添加到候選塊集合。
如果候選塊數(shù)比L大，第一高頻率執(zhí)行節(jié)點將選擇為候選塊集合，斷言將插入這些塊。候選塊集合將從后支配和前支配樹基于混合選擇節(jié)點創(chuàng)建。優(yōu)先級將給予具有高頻率執(zhí)行和100％分支覆蓋的塊。
第三種方法是節(jié)點執(zhí)行頻率計算方法，即算法2，該方法獲取程序圖作為輸入，并在每個塊的開頭插入計數(shù)器。在源代碼中運用這些改變后，程序?qū)⑦\行5n次，其中n為程序節(jié)點數(shù)。
(1)算法1：基于內(nèi)核的候選塊查找算法的核心代碼
Nominee-block-set-find(V,E,entry，exit，L)
{ Tpre=PREDOMINATORTREE(V,E,entry)；
Lpre=Tpre的葉子集；
Tpost=POSTDOMINATORTREE(V,E,exit)；
While(L>Nominee-block-count) {
If(T=1) Then {/*第一個if*/
If(LpostLpre非空且Des=0)Then {
從LpostLpre選擇高頻節(jié)點；
添加到候選塊集；} Else {
Des=1；
Lpre=添加Tpre的h-1級的所有節(jié)點到Lpre；
Lpost=添加Tpost的h-1級的所有節(jié)點到Lpost；
h=h-1； }
If(Lpre非空)Then {
從Lpre選擇高頻節(jié)點；添加到候選塊集；}
Else Des=0；
If(LpostLpre非空且Des=0) Then{從LpostLpre選擇高頻節(jié)點；
添加到候選塊集；
} Else { Des=1；
Lpre=添加Tpre的h-1級的所有節(jié)點到Lpre；
Lpost=添加Tpost的h-1級的所有節(jié)點到Lpost；
h=h-1；}
If(Lpost非空)Then{
從Lpost選擇高頻節(jié)點；
添加到候選塊集；
}
}
(2)算法2：塊執(zhí)行頻率計算算法Find-basic-block-frequency(V，E)
{ Static int block-frequency[n]；/*n是程序圖節(jié)點*/
For 所有節(jié)點<>從控制流圖開始{
在塊開始處添加block-frequency[i]++； }
While(i<=5n)
運行程序并保存(節(jié)點數(shù)，block-frequency)；
}
1.2 數(shù)據(jù)流錯誤檢查
在程序中應(yīng)用定義-使用鏈算法[8]確定變量頻率，該算法表明變量到達(dá)鏈程序中的不同點。找到變量的定義-使用頻率后，使用頻率進(jìn)行分類。本文提出的智能塊選擇方法如算法3：
(3)算法3：變量選擇算法
{ 運用Reaching-definition-algorithm()；
基于UF分類變量/*UF是使用頻率*/
Read(VFP)；/*從用戶獲取變量頻率參數(shù)*/
For 所有變量
If(UFVFP) then 復(fù)制變量
}
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如下：
式中，上標(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)的運行時間簽名，當(dāng)在程序圖上運用候選塊尋找算法時，劃分塊為候選成員塊和普通成員塊。
識別這些集后，在塊中插入斷言，引入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?；緣Kvi的Kernel-test和set語句設(shè)計如下：
Kernel-test:If(S=S&Li)=0 error
在非候選塊成員的塊中插入上述斷言，引入Kernel-free-test斷言到每個基本塊開頭，引入set斷言到每個基本塊末尾。當(dāng)該控制從一個塊vj轉(zhuǎn)移到另一vi的塊時，在S中保存Si的值，直到候選塊中檢查它。Kernel-free-test和set語句設(shè)計如下：
Kernel-free-test:S=S&Li
修改的代碼如圖2所示，在插入排序圖中運用內(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”，最終，用新運行時間簽名Si &(-1)=Si更新S。另一方面，假設(shè)節(jié)點vi不是vj的后繼，則S&Li應(yīng)該為0，執(zhí)行節(jié)點vi的Kernel-test斷言之后將檢測到控制流錯誤，該控制將轉(zhuǎn)移到錯誤處理例程。
2 實驗結(jié)果與評估
2.1 原型實現(xiàn)
修改代碼的生成過程如圖3所示，本文使用C++實現(xiàn)上述方法，并在代碼中插入斷言，執(zhí)行該程序?qū)ふ宜矔r錯誤。該工作首先使用過濾器還原標(biāo)準(zhǔn)C語句為偽代碼語句，還原不改變控制流的語句為空分號。然后，掃描儀獲取偽代碼，并發(fā)送它到解析器，進(jìn)行程序的控制流圖提取。之后，解析器提取程序的前后支配樹，并在其上運用候選塊尋找算法，進(jìn)行節(jié)點分類。解析器的輸出是程序圖表和候選塊信息，在源節(jié)點上運用算法1，獲得塊斷言和變量。最后，生成如圖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，可以得出在候選塊上運用本文方法能夠降低性能開銷，檢測延遲(DL)基于下列公式：
最大故障檢測延遲是W，如果在候選塊上運用本文方法，最大故障檢測延遲將為(N/L)×W。
根據(jù)上述公式，增加候選塊數(shù)能降低故障檢測延遲，如果候選塊數(shù)降低，檢測延遲也會增加。從表1和表2的“性能”列中可以觀察到，本方法中程序執(zhí)行時間少于RSCFC方法，且從表2的“性能”列可以看出，執(zhí)行時間比率接近1，即程序執(zhí)行時間幾乎保持相同，但是固化代碼能檢測瞬時錯誤。
3 結(jié)論
本文運用控制流檢測方法檢測嵌入式軟件故障，預(yù)處理包括使用高頻變量和重要基本塊的檢測，改進(jìn)了RSCFC方法中關(guān)系簽名的有效性。此外，使用本文方法，使嵌入式軟件開發(fā)人員能權(quán)衡檢測延遲和性能開銷。使用3個基準(zhǔn)的實驗結(jié)果表明，固化代碼中程序執(zhí)行時間少于RSCFC方法，但是內(nèi)存開銷和代碼開銷幾乎相同，本文方法產(chǎn)生的固化代碼與原始代碼的程序執(zhí)行時間幾乎相同。
未來，將測試和評估在固化程序中由專業(yè)故障工具插入的故障，研究基于程序語義在程序中插入斷言的新方法。
參考文獻(xiàn)
[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)，2011IEEE 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 Journalof 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：princi-ples，techniques，and tools[J].2006，22(12)：852-857.
[9] Automated Q A.AQtime[EB/OL].(2010)[2015].http：//www.automatedqa.com/products/aqtime/.