文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.10.004
中文引用格式： 周改云，張國平，呂瓊帥，等. 利用智能控制流方法的嵌入式軟件故障檢測[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.
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：基于內核的候選塊查找算法的核心代碼
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選擇高頻節點；
添加到候選塊集；} Else {
Des=1；
Lpre=添加Tpre的h-1級的所有節點到Lpre；
Lpost=添加Tpost的h-1級的所有節點到Lpost；
h=h-1； }
If(Lpre非空)Then {
從Lpre選擇高頻節點；添加到候選塊集；}
Else Des=0；
If(LpostLpre非空且Des=0) Then{從LpostLpre選擇高頻節點；
添加到候選塊集；
} Else { Des=1；
Lpre=添加Tpre的h-1級的所有節點到Lpre；
Lpost=添加Tpost的h-1級的所有節點到Lpost；
h=h-1；}
If(Lpost非空)Then{
從Lpost選擇高頻節點；
添加到候選塊集；
}
}
(2)算法2：塊執行頻率計算算法Find-basic-block-frequency(V，E)
{ Static int block-frequency[n]；/*n是程序圖節點*/
For 所有節點<>從控制流圖開始{
在塊開始處添加block-frequency[i]++； }
While(i<=5n)
運行程序并保存(節點數，block-frequency)；
}
1.2 數據流錯誤檢查
在程序中應用定義-使用鏈算法[8]確定變量頻率，該算法表明變量到達鏈程序中的不同點。找到變量的定義-使用頻率后，使用頻率進行分類。本文提出的智能塊選擇方法如算法3：
(3)算法3：變量選擇算法
{ 運用Reaching-definition-algorithm()；
基于UF分類變量/*UF是使用頻率*/
Read(VFP)；/*從用戶獲取變量頻率參數*/
For 所有變量
If(UFVFP) then 復制變量
}
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、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?；緣Kvi的Kernel-test和set語句設計如下：
Kernel-test:If(S=S&Li)=0 error
在非候選塊成員的塊中插入上述斷言，引入Kernel-free-test斷言到每個基本塊開頭，引入set斷言到每個基本塊末尾。當該控制從一個塊vj轉移到另一vi的塊時，在S中保存Si的值，直到候選塊中檢查它。Kernel-free-test和set語句設計如下：
Kernel-free-test:S=S&Li
修改的代碼如圖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.1 原型實現
修改代碼的生成過程如圖3所示，本文使用C++實現上述方法，并在代碼中插入斷言，執行該程序尋找瞬時錯誤。該工作首先使用過濾器還原標準C語句為偽代碼語句，還原不改變控制流的語句為空分號。然后，掃描儀獲取偽代碼，并發送它到解析器，進行程序的控制流圖提取。之后，解析器提取程序的前后支配樹，并在其上運用候選塊尋找算法，進行節點分類。解析器的輸出是程序圖表和候選塊信息，在源節點上運用算法1，獲得塊斷言和變量。最后，生成如圖3所示的修改代碼。
2.2 實驗評估
為了評估本文方法的有效性，比較修改代碼和原始代碼的內存大小和性能開銷，還評估了兩種情況下本方法的故障檢測能力，并與RSCFC方法進行了比較，為了實現該比較，選擇下列3個基準：（1）插入排序(IN)；（2）快速排序(QS)；（3）矩陣乘法(MM)。所有程序均在2G內存，Win7的i3 PC上執行。
使用AQtime6[9]配置軟件估計性能和內存開銷，表1和表2分別表示基于原始代碼的RSCFC方法和本文方法的內存率、性能開銷和固化代碼大小，各個指標表示基準程序的倍數。
比較表1和表2，可以得出在候選塊上運用本文方法能夠降低性能開銷，檢測延遲(DL)基于下列公式：
最大故障檢測延遲是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)，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].計算機學報，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：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/.