馬駿馳　汪　蕓　蔡震波　張慶祥　王　穎　胡　誠

1(東南大學計算機科學與工程學院　南京　211189)2(計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學)　南京　211189)3　　　(中國空間技術(shù)研究院總體部　北京　100094)

?

基于錯誤傳播分析的SDC脆弱指令識別方法

馬駿馳1,2汪蕓1,2蔡震波3張慶祥3王穎3胡誠1,2

1(東南大學計算機科學與工程學院南京211189)2(計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學)南京211189)3(中國空間技術(shù)研究院總體部北京100094)

(jcma@seu.edu.cn)

單粒子軟錯誤是高輻照空間環(huán)境下影響計算可靠性的主要因素.隨著芯片晶體管數(shù)的快速增長，單粒子軟錯誤的威脅日益嚴重.結(jié)果錯誤(silent data corruption, SDC)是單粒子軟錯誤造成的一種故障類型.由于SDC是隱蔽傳播的，SDC的檢測是單粒子軟錯誤防護的難點.尋找SDC脆弱指令是目前檢測SDC的重要途徑.現(xiàn)有方法需要進行巨量的錯誤注入，時間代價巨大.首先根據(jù)數(shù)據(jù)關(guān)聯(lián)圖建立了指令的數(shù)據(jù)依賴關(guān)系，研究了函數(shù)間和函數(shù)內(nèi)部錯誤傳播過程；進而推導出判定SDC脆弱指令的充分條件，提出了SDC脆弱指令識別方法,該方法在錯誤注入中依據(jù)充分條件推測潛在的SDC脆弱指令.實驗表明，在保證較高準確率和覆蓋率的前提下，時間代價顯著減少.

單粒子翻轉(zhuǎn)；單粒子軟錯誤；SDC脆弱指令；錯誤注入；錯誤傳播

單粒子翻轉(zhuǎn)(single event upset, SEU)是由宇宙中的質(zhì)子、電子、重離子等高能粒子轟擊半導體器件造成PN結(jié)瞬間充放電現(xiàn)象.單粒子翻轉(zhuǎn)引起的半導體電路瞬態(tài)故障稱為單粒子軟錯誤[1-3](以下簡稱軟錯誤).軟錯誤雖然不會損壞內(nèi)部硬件電路，但是有可能影響程序的正常運行，甚至導致衛(wèi)星運行異常或者失控.

由于單個器件的軟錯誤率基本保持穩(wěn)定，因而處理器整體軟錯誤率主要與集成度相關(guān).在集成度以摩爾定律增長的趨勢下，處理器的整體軟錯誤率也會以摩爾定律增長[4]，未來對于軟錯誤的檢測與加固技術(shù)的需求變得日益迫切.

軟錯誤引起的故障類型大致可以分為4種[5]:屏蔽(benign)、崩潰(crash)、掛起(hang)和結(jié)果錯誤(silent data corruption， SDC)，如表1所示.導致SDC的運行過程不會拋出異常，因此SDC的發(fā)生最為隱蔽.一旦發(fā)生SDC，如果不能有效地檢測，可能導致嚴重的后果.

Table 1　Error Categories Caused by Soft Error and Their Differences

現(xiàn)有的軟錯誤檢測方法主要基于癥狀檢測(symptom-based detector)[6-8].癥狀是指系統(tǒng)的一些異常特征，包括分支預測失效、cache命中率低等.當檢測器捕捉到異常特征時，就認為發(fā)生了軟錯誤.此方法對軟錯誤的檢測率高、代價較低，但是不能檢測SDC，因為SDC是隱蔽傳播的，不會出現(xiàn)常見的異常特征.

為了彌補基于癥狀檢測方法的缺陷，近年來出現(xiàn)了針對SDC的軟錯誤檢測方法，主要包括指令級冗余和程序級斷言.指令級冗余對容易受到軟錯誤干擾的指令進行時間或空間的冗余設(shè)計[9-10]；程序級斷言通過對程序正常運行時為真的條件進行判斷來檢測軟錯誤[11-13].2種方法都需要針對選定的指令添加檢測代碼.執(zhí)行檢測代碼會導致額外的時間代價，并且選定的指令越多，代價越高昂.為了減小時間代價，2種方法都重點針對SDC脆弱指令(SDC-causing instruction)進行部署.如果指令讀寫的寄存器或內(nèi)存發(fā)生軟錯誤會導致SDC，該指令稱為SDC脆弱指令.

SDC脆弱指令一般由軟件實現(xiàn)的錯誤注入(fault injection)得出[14].錯誤注入通過修改寄存器和內(nèi)存的二進制位來模擬軟錯誤(二進制位為0時，將其改為1；二進制位為1時，將其改為0).注入錯誤數(shù)是修改二進制位的總次數(shù)，錯誤注入實驗的時間代價主要與注入錯誤數(shù)相關(guān).由于每條指令都需要進行錯誤注入，即使規(guī)模很小的程序也有巨量的注入錯誤數(shù)，時間代價巨大.例如，對目的操作數(shù)(32位)進行錯誤注入，當程序含有10 000條指令時，注入錯誤數(shù)至少為320 000，整個錯誤注入的時間代價至少為原程序單次運行的320 000倍.對于一般的計算設(shè)備，該時間代價難以接受.

本文提出了一種高效的SDC脆弱指令識別方法.該方法根據(jù)已執(zhí)行的錯誤注入實驗的信息動態(tài)推測潛在的SDC脆弱指令，由此減少未進行的錯誤注入.本文的主要貢獻有：

1) 基于數(shù)據(jù)關(guān)聯(lián)圖(data dependence graph, DDG)建立了指令的數(shù)據(jù)依賴關(guān)系，分析了導致SDC的錯誤在函數(shù)間和函數(shù)內(nèi)部的傳播過程.指出關(guān)鍵指令(即寫函數(shù)間交互數(shù)據(jù)的指令)在導致SDC的錯誤傳播中的作用，由此提出并證明了判定非關(guān)鍵指令是SDC脆弱指令的充分條件.

2) 基于SDC脆弱指令的判定條件，提出了SDC脆弱指令識別方法.該方法可以在注入過程中動態(tài)推斷SDC脆弱指令，從而有效減少注入錯誤數(shù)和時間代價.實驗結(jié)果表明，注入錯誤數(shù)比現(xiàn)有工作Relyzer[15]低25.6%，時間代價減少27.9%.

1　相關(guān)工作

根據(jù)是否進行錯誤注入實驗，可將現(xiàn)有工作中識別SDC脆弱指令的方法分為靜態(tài)注入方法和靜態(tài)分析方法2類，以下分類進行介紹.

1.1靜態(tài)注入方法

靜態(tài)注入方法首先將需要錯誤注入的指令列入注入計劃表(injection map)，然后依次進行錯誤注入.在錯誤注入過程中，注入計劃表不會發(fā)生變化.靜態(tài)注入方法通過選擇性的錯誤注入緩解了原有錯誤注入實驗代價過高的問題.

Relyzer[15]壓縮了等價類的錯誤注入.等價類是指每個基本塊(basic block)都相同的控制流實例組成的集合，對等價類的不同指令實例進行錯誤注入得到的結(jié)果是相似的，因此在等價類中只選擇一個代表進行錯誤注入.

SmartInjector[16]補充了Relyzer的方法，認為具備相同數(shù)據(jù)傳播模式的數(shù)據(jù)流的注入結(jié)果是相似的，將其歸為同一個等價類，并只選擇一個指令實例進行錯誤注入.

CriticalFault[17]通過指令級脆弱性分析來減少注入錯誤數(shù).指令級脆弱性分析能夠找出非敏感位.在非敏感位發(fā)生的軟錯誤不會對程序的運行產(chǎn)生影響，也不會產(chǎn)生SDC，因而CriticalFault排除掉了這些非敏感位的錯誤注入.

1.2靜態(tài)分析方法

靜態(tài)分析方法不進行錯誤注入實驗，而是通過分析程序特征得到SDC脆弱指令.

Shoestring[10]認為所有影響全局內(nèi)存或函數(shù)參數(shù)的指令都是SDC脆弱指令.此判定方法容易實施，但由于判定條件只考慮指令的目的操作數(shù)，而不考慮程序邏輯等其他因素，因此準確率較低.

SymPLFIED[18]通過符號執(zhí)行模擬錯誤傳播過程來識別SDC脆弱指令.由于符號執(zhí)行窮舉了所有錯誤傳播路徑，因此不會出現(xiàn)漏判.但其模擬的某些錯誤在現(xiàn)實中不會發(fā)生，所以準確率較低，并且符號執(zhí)行導致了狀態(tài)爆炸，使得時間和空間代價極大.

綜上所述，靜態(tài)注入方法的優(yōu)點是得到的SDC脆弱指令都是準確的，但錯誤注入導致代價較高；靜態(tài)分析方法的實現(xiàn)簡單，但準確率較低.

為了在保證高準確率情況下降低注入代價，本文提出一種新的動態(tài)注入方法.整體來看，前述靜態(tài)注入方法的主要思路是在錯誤注入實驗開始前對冗余的錯誤注入進行壓縮；而本文是在錯誤注入實驗開始后，根據(jù)已執(zhí)行的錯誤注入的信息動態(tài)推測潛在的SDC脆弱指令，由此調(diào)整注入計劃表來減少未進行的錯誤注入.需要指出的是，由于2種思路并不沖突，本文的識別方法可以與前述靜態(tài)注入方法聯(lián)合使用(本文中聯(lián)合使用了典型的靜態(tài)注入方法Relyzer)，從而進一步降低注入代價.

2　模型假設(shè)及相關(guān)概念

本文主要考慮單粒子一位翻轉(zhuǎn)的情況.通過改變指令讀寫的寄存器或內(nèi)存的一個二進制位來模擬單粒子一位翻轉(zhuǎn).

本文只研究應(yīng)用程序范圍內(nèi)可能導致SDC的指令，因此不考慮在系統(tǒng)庫函數(shù)的指令.浮點運算指令的工作方式與普通運算指令不同，本文不考慮浮點運算指令.因為指令操作碼發(fā)生錯誤一般會導致崩潰[17]，所以本文只考慮指令操作數(shù)的錯誤，后文中指令發(fā)生錯誤特指操作數(shù)發(fā)生錯誤.

應(yīng)用程序的結(jié)果一般是通過printf，cout等系統(tǒng)庫函數(shù)進行輸出.本文將進行結(jié)果輸出的函數(shù)稱為輸出函數(shù).由于輸出函數(shù)是系統(tǒng)庫函數(shù)，基于前述假設(shè)，輸出函數(shù)的錯誤都是從其他函數(shù)傳遞進去的.

本文采用數(shù)據(jù)關(guān)聯(lián)圖[19]對錯誤傳播過程進行分析.數(shù)據(jù)關(guān)聯(lián)圖G(V，E)是根據(jù)程序指令的讀寫依賴建立的有向圖，其中節(jié)點集V代表程序運行中執(zhí)行的指令，而邊集E代表指令的數(shù)據(jù)依賴關(guān)系.例如，節(jié)點u讀入了節(jié)點v寫的數(shù)據(jù)，就會產(chǎn)生一條由v指向u的邊.?vi，vj∈V，若vi可達vj，則稱vi為vj的祖先節(jié)點，vj為vi的子孫節(jié)點.根據(jù)數(shù)據(jù)關(guān)聯(lián)圖能夠找出錯誤的傳入路徑.在3.3節(jié)將通過數(shù)據(jù)關(guān)聯(lián)圖來分析錯誤傳播過程.

以求和程序sum生成的數(shù)據(jù)關(guān)聯(lián)圖為例.sum程序的代碼如下所示，輸入是變量size，計算了從0到size-1的總和，并將其作為輸出返回.

intsum(intsize){

k=0;

for (inti=0;i

{

k=k+i;

}

returnk;

}

圖1表示了sum生成的數(shù)據(jù)關(guān)聯(lián)圖，表2顯示了sum編譯后的指令及其對應(yīng)數(shù)據(jù)關(guān)聯(lián)圖中的節(jié)點.圖1中，節(jié)點按照指令所寫變量排列.比如變量k所在列的節(jié)點都是對k進行寫操作的指令.以節(jié)點7為例，節(jié)點7對應(yīng)的指令為add dword ptr [esp+0x24],eax，讀取寄存器eax和內(nèi)存[esp+0x24]，寫內(nèi)存[esp+0x24].[esp+0x24]代表寄存器esp與常量0x24相加后所對應(yīng)內(nèi)存地址的值.節(jié)點7的父節(jié)點是上一次寫eax的節(jié)點6和上一次寫[esp+0x24]的節(jié)點1，其子節(jié)點是下一次讀[esp+0x24]的節(jié)點13.

Fig. 1　The DDG of the program of sum.圖1　求和程序sum的數(shù)據(jù)關(guān)聯(lián)圖

Table 2　The Instructions of the Program of sum and Their Corresponding Nodes in the DDG

3　導致SDC的錯誤傳播分析

基于第2節(jié)的模型假設(shè)，本節(jié)討論導致SDC的錯誤傳播過程的特征.導致SDC的執(zhí)行過程沒有拋出異常，每條指令都是合法的，但結(jié)果是錯誤的.由于結(jié)果是由輸出函數(shù)輸出的，而輸出函數(shù)的參數(shù)是輸出的內(nèi)容或者輸出內(nèi)容的地址，所以導致SDC的直接原因是輸出函數(shù)的參數(shù)發(fā)生了錯誤.本文以函數(shù)為單元分析錯誤傳播.在傳播到輸出函數(shù)參數(shù)前，錯誤首先會在應(yīng)用程序的不同函數(shù)間和函數(shù)內(nèi)部傳播.函數(shù)間和函數(shù)內(nèi)部錯誤傳播的方式具有不同的特點，在3.1節(jié)和3.2節(jié)分別對其進行分析.以此為基礎(chǔ)，在3.3節(jié)得出非關(guān)鍵指令的SDC脆弱性的判定定理.

3.1函數(shù)間錯誤傳播

函數(shù)間錯誤傳播是指錯誤從函數(shù)內(nèi)部指令讀寫的數(shù)據(jù)傳播到函數(shù)間交互數(shù)據(jù).函數(shù)間交互數(shù)據(jù)可以被其他函數(shù)讀取，錯誤繼而傳入了讀取交互數(shù)據(jù)的函數(shù).假設(shè)有2個函數(shù)A，B，函數(shù)B讀取函數(shù)A寫的數(shù)據(jù)，使得函數(shù)A將錯誤傳播給函數(shù)B.函數(shù)間交互數(shù)據(jù)指的是函數(shù)A寫、函數(shù)B讀的數(shù)據(jù).如圖2所示，函數(shù)間錯誤傳播方式有以下3種：

1) 函數(shù)A調(diào)用函數(shù)B，函數(shù)A把錯誤的數(shù)據(jù)通過調(diào)用參數(shù)傳遞給函數(shù)B.

2) 函數(shù)A被函數(shù)B調(diào)用，函數(shù)A把錯誤的數(shù)據(jù)通過函數(shù)返回值傳遞給函數(shù)B.

3) 函數(shù)A將錯誤的數(shù)據(jù)寫入全局變量，函數(shù)B讀取全局變量.

Fig. 2　The inter-function fault propagation圖2　函數(shù)間的錯誤傳播方式

將完成對上述函數(shù)間交互數(shù)據(jù)寫操作的指令定義為關(guān)鍵指令，其余指令定義為非關(guān)鍵指令.圖2虛線框中的關(guān)鍵指令以直線劃出.對應(yīng)函數(shù)間錯誤傳播方式，關(guān)鍵指令包括以下3種類型:

1) 函數(shù)參數(shù)寫指令.該指令是調(diào)用者函數(shù)將參數(shù)寫入棧的指令.函數(shù)參數(shù)寫指令執(zhí)行后，被調(diào)用函數(shù)彈棧以取得參數(shù).如圖2(a)中的關(guān)鍵指令1將變量x寫入棧地址[esp]中，被調(diào)用函數(shù)B讀取[esp]的值來獲取參數(shù)x.

2) 函數(shù)返回值寫指令.該指令是被調(diào)用函數(shù)將函數(shù)返回值寫入eax的指令.函數(shù)返回值寫指令執(zhí)行后，調(diào)用者函數(shù)通過讀取寄存器eax來獲取返回值.如圖2(b)中的關(guān)鍵指令2將變量y的值寫入eax，函數(shù)B通過讀取eax來獲取返回值.

3) 全局變量寫指令.該指令是指修改全局變量的指令.圖2(c)中的關(guān)鍵指令3是全局變量寫指令，它將1寫入靜態(tài)區(qū)中存放全局變量z的地址中.

定理1. 關(guān)鍵指令發(fā)生錯誤是導致SDC的必要條件.

證明.

1) 證明關(guān)鍵指令的存在性，即導致SDC的過程中必然執(zhí)行過關(guān)鍵指令.假設(shè)在函數(shù)內(nèi)部的非關(guān)鍵指令I(lǐng)k發(fā)生的軟錯誤最終導致SDC，其傳播過程中必須經(jīng)過函數(shù)間錯誤傳播.因為導致SDC一定要輸出函數(shù)輸出錯誤的內(nèi)容，而發(fā)生軟錯誤的指令I(lǐng)k在輸出函數(shù)外部，只有通過函數(shù)間的錯誤傳播才能把錯誤傳遞到輸出函數(shù)的參數(shù).函數(shù)間的錯誤傳播是由關(guān)鍵指令完成的，所以導致SDC的過程中執(zhí)行過關(guān)鍵指令.

2) 用反證法證明導致SDC的過程一定存在發(fā)生錯誤的關(guān)鍵指令.假設(shè)所有執(zhí)行過的關(guān)鍵指令都是正確的，那么與Ik所在函數(shù)交互的函數(shù)沒有受到錯誤的影響，得到的輸出結(jié)果是正確的，不會產(chǎn)生SDC.綜上，導致SDC的執(zhí)行過程存在發(fā)生錯誤的關(guān)鍵指令.

證畢.

3.2函數(shù)內(nèi)部錯誤傳播

函數(shù)內(nèi)部錯誤傳播是指僅在某一函數(shù)內(nèi)部進行讀寫的數(shù)據(jù)之間的傳播.函數(shù)內(nèi)部錯誤傳播是由非關(guān)鍵指令完成的.包括以下2種方式:

1) 計算傳播

計算傳播是指在指令讀入數(shù)據(jù)發(fā)生錯誤的情況下，造成了錯誤的寫入數(shù)據(jù).讀入數(shù)據(jù)包括源操作數(shù)、基址、狀態(tài)寄存器等.寫入數(shù)據(jù)包括目的操作數(shù)、狀態(tài)寄存器等.當一條指令有多個讀入數(shù)據(jù)時，任一讀入數(shù)據(jù)的錯誤都有可能造成目的操作數(shù)的錯誤.比如，指令mov eax,DWORD PTR[ebp]需要讀入的數(shù)據(jù)有ebp和 [ebp]，不管哪一個存在錯誤，都有可能導致eax的錯誤.

2) 控制流傳播

控制流傳播是由于比較指令(cmp，test等指令)發(fā)生錯誤導致程序執(zhí)行錯誤的分支.一般地，比較指令后的第一條指令是條件轉(zhuǎn)移指令(例如jz指令).比較指令影響狀態(tài)寄存器的標志位，而條件轉(zhuǎn)移指令根據(jù)標志位來選擇究竟執(zhí)行哪一個分支.當比較指令的讀入數(shù)據(jù)發(fā)生錯誤時，可能會導致執(zhí)行錯誤的分支.

3.3非關(guān)鍵指令的SDC脆弱性的判定

根據(jù)定理1，非關(guān)鍵指令的錯誤要導致SDC，必須要經(jīng)過關(guān)鍵指令的傳播.進一步地，如果非關(guān)鍵指令的錯誤造成了關(guān)鍵指令的錯誤，由于兩者存在的對應(yīng)關(guān)系，可以通過分析關(guān)鍵指令錯誤的影響來確定非關(guān)鍵指令錯誤的影響.由上面的分析，本文得到了判定非關(guān)鍵指令的SDC脆弱性的充分條件.

定理2. 對于非關(guān)鍵指令I(lǐng)nc，若在同一函數(shù)中存在同時滿足以下條件的關(guān)鍵指令I(lǐng)c，則Inc是SDC脆弱指令.

1)Inc是Ic的祖先節(jié)點;

2) 當在Inc發(fā)生錯誤時，Ic是錯誤的，且是唯一錯誤的關(guān)鍵指令;

3)Ic是SDC脆弱指令.

證明. 由條件1和條件2，Ic的錯誤是由Inc傳播的.Ic是唯一錯誤的關(guān)鍵指令，其余關(guān)鍵指令是正確的，因而Inc的錯誤對于其他函數(shù)的影響是通過Ic傳遞出去的，在Inc發(fā)生的錯誤對其他函數(shù)的影響相當于在Ic發(fā)生錯誤對其他函數(shù)的影響.由條件3，根據(jù)SDC脆弱指令的定義，在Ic發(fā)生錯誤會產(chǎn)生SDC，那么在Inc發(fā)生錯誤也會產(chǎn)生SDC，所以Inc是SDC脆弱指令.

證畢.

4　SDC脆弱指令識別方法

根據(jù)3.3節(jié)SDC脆弱性的判定條件，本文設(shè)計了SDC脆弱指令識別方法，分別對關(guān)鍵指令和非關(guān)鍵指令進行處理.關(guān)鍵指令中的SDC脆弱指令是通過錯誤注入實驗得到的，非關(guān)鍵指令中的SDC脆弱指令是通過錯誤注入實驗和推斷算法得到的.由于非關(guān)鍵指令占注入錯誤數(shù)的絕大多數(shù)，因而對非關(guān)鍵指令的處理是識別方法的重點.識別方法的步驟是：

1) 根據(jù)定義找出關(guān)鍵指令集合Γ.

2) 通過錯誤注入實驗判定關(guān)鍵指令集合Γ中的指令的SDC脆弱性.如果錯誤注入得到的結(jié)果是SDC，則將該關(guān)鍵指令加入SDC脆弱指令集合ΓSDC.

3) 識別非關(guān)鍵指令中的SDC脆弱指令.首先使用Relyzer等價類注入的方法對非關(guān)鍵指令進行采樣，將指令實例樣本添加進注入計劃表；然后依次進行錯誤注入，當?shù)玫降慕Y(jié)果是SDC則運行推斷算法，將推測得到的SDC脆弱指令從注入計劃表中刪去.

其中，步驟3的推斷算法根據(jù)錯誤注入實驗的數(shù)據(jù)對非關(guān)鍵指令的SDC脆弱性進行分析和推理.

推斷算法的輸入是錯誤注入實驗中指令寫入數(shù)據(jù)的記錄、無錯運行時指令寫入數(shù)據(jù)的記錄、關(guān)鍵指令中的SDC脆弱指令集合ΓSDC，輸出是推測出的SDC脆弱指令集合S.推斷算法分為3個階段，如圖3所示.其中，p是指向錯誤注入實驗的指令記錄的指針，p′是指向無錯運行時指令記錄的指針，*p代表p所指向的指令，p.Od代表p所指向指令記錄的寫入數(shù)據(jù).

1) 比較階段.將p.Od與對應(yīng)的p′.Od進行比較，若寫入數(shù)據(jù)是不同的，則判定指令*p發(fā)生了錯誤.如果*p屬于SDC脆弱指令集合ΓSDC，則進入推測階段，否則進入結(jié)束階段.

直接比較寫入數(shù)據(jù)是地址的指令可能會造成誤判.由于操作系統(tǒng)的內(nèi)存分配機制，2次運行過程一般會分配不同的地址空間，因而寫入數(shù)據(jù)是地址的指令會被認為是錯誤的.本文通過錯誤傳播分析來判斷地址是否是錯誤的，規(guī)定當指令的讀入數(shù)據(jù)是錯誤的、寫入數(shù)據(jù)是地址時，該地址是錯誤的；否則是正確的.

Fig. 3　The flow chart of inference algorithm.圖3　推斷算法的流程圖

2) 推測階段.深度優(yōu)先搜索*p的祖先節(jié)點，若祖先節(jié)點是正確的，則結(jié)束該分支的搜索；否則，如果祖先節(jié)點只有一個錯誤的關(guān)鍵指令子孫節(jié)點(即*p)，則將該祖先節(jié)點加入推測出的SDC脆弱指令集合S.

3) 結(jié)束階段.p和p′ 轉(zhuǎn)到下一條指令記錄.如果*p是條件跳轉(zhuǎn)指令，判斷是否與無錯運行時選擇了同一分支，若選擇了不同分支，則發(fā)生了控制流傳播.p和p′指向同一指令對應(yīng)的實例才能進行比較，所以為了對齊p和p′，p和p′指向*p所在函數(shù)的ret指令(ret指令一般是函數(shù)最后一條指令).如果*p已經(jīng)是最后一條指令，則結(jié)束.

以圖1為例來說明推斷過程.對節(jié)點1進行錯誤注入后導致了SDC.圖1中灰色節(jié)點經(jīng)過比較階段后被判定發(fā)生了錯誤.從節(jié)點1開始進行搜索，發(fā)現(xiàn)節(jié)點1的子孫節(jié)點18是關(guān)鍵指令，并且是SDC脆弱指令(識別方法步驟2后，節(jié)點18屬于ΓSDC).搜索節(jié)點18的祖先節(jié)點，發(fā)現(xiàn)錯誤節(jié)點1，7和13滿足判定SDC脆弱指令的充分條件，推測出節(jié)點7和13為SDC脆弱指令.

5　驗證實驗

5.1實驗方法

本文的實驗平臺是Ubuntu10.04，并采用工具Pin[20]對原有指令執(zhí)行進行修改，添加錯誤注入的代碼.Pin是針對IA-32和x86-64指令集的動態(tài)二進制插樁工具，能夠?qū)θ我庵噶畈迦胗脩糇远x的分析代碼.

錯誤注入是根據(jù)注入計劃表來依次進行的.注入計劃表包含注入指令的靜態(tài)地址、實例序號、注入硬件位置和注入位.靜態(tài)地址是指令相對于代碼段開始位置的偏移量;實例序號是被注入錯誤的實例在所有相同靜態(tài)地址運行實例中的序號;注入硬件位置是注入錯誤的具體位置;注入位表明了對硬件位置的第幾個二進制位進行注入.

測試程序是西門子標準測試集[21]，包括rep(完成字符匹配和替換)、sc和sc2(優(yōu)先級調(diào)度算法)、pri和pri2(詞法分析)、tot(統(tǒng)計數(shù)據(jù)).對每個測試程序，本文隨機選擇3組輸入進行實驗.

5.2實驗結(jié)果

本文從準確率、覆蓋率、注入錯誤數(shù)和時間代價4個方面來評價SDC脆弱指令識別方法.其中，準確率用來衡量推斷算法得到的SDC脆弱指令的準確程度；覆蓋率用來衡量得到的SDC脆弱指令的完整程度.

為了計算準確率和覆蓋率，對測試程序的每一條指令都進行錯誤注入，找出了真實的SDC脆弱指令集合LSDC.以下的描述中，S表示根據(jù)推斷算法得到的SDC脆弱指令集合，F(xiàn)表示根據(jù)錯誤注入得到的SDC脆弱指令集合，S∪F表示本識別方法得到的SDC脆弱指令集合.

5.2.1準確率

準確率的計算過程如式(1)所示.card(S)代表集合S元素的個數(shù).由于錯誤注入得到的SDC脆弱指令都是正確的，因此不需要考察集合F.式(1)右側(cè)分子代表推測得到的SDC脆弱指令被驗證為正確的指令數(shù)，分母是推測得到的SDC脆弱指令總數(shù).

(1)

各測試程序的準確率如圖4所示.其中，每個測試程序都包含3組輸入.實驗表明，6個測試程序?qū)嶒灲Y(jié)果的平均準確率為98.8%;除了sc2的第1組輸入，其他測試的準確率都大于97%;對于pri2和tot這2個測試程序，準確率為100%;sc2的第1組輸入推測的錯誤主要是特殊地址相關(guān)的指令,由于該地址存放的是結(jié)構(gòu)化數(shù)據(jù)的指針，改變指針導致了崩潰而沒有產(chǎn)生SDC,通過分析程序的數(shù)據(jù)結(jié)構(gòu)可以解決這一問題，這是推斷算法能夠改進的一個地方.

Fig. 4　Accuracy rate of our method.圖4　本文方法的準確率

圖5比較了本文與其他SDC脆弱指令識別方法的準確率,圖5中的SDCPredictor為本文的識別方法. Relyzer只通過錯誤注入來得到SDC脆弱指令，因而準確率是100%.Shoestring認為所有影響全局內(nèi)存或函數(shù)參數(shù)的指令都是SDC脆弱指令，準確率為77.2%，比本文的方法低21.6%.準確率低的原因是SDC脆弱指令與應(yīng)用程序的邏輯高度相關(guān)，影響全局內(nèi)存或函數(shù)參數(shù)的指令不一定會產(chǎn)生SDC.

Fig. 5　The comparison of accuracy rate.圖5　準確率比較

5.2.2覆蓋率

覆蓋率的計算過程如式(2)所示.式(2) 右側(cè)分子是識別方法得到的SDC脆弱指令中被驗證為正確的指令數(shù)，分母是真實的SDC脆弱指令總數(shù).

(2)

Fig. 6　The comparison of coverage rate.圖6　覆蓋率比較

圖6比較了本文識別方法與其他SDC脆弱指令識別方法的覆蓋率.本文識別方法的平均覆蓋率是96.9%，比Relyzer高1.7%.因為本文采用了與Relyzer類似的等價類錯誤注入壓縮方法，所以遺漏的SDC脆弱指令與Relyzer相似，主要是地址相關(guān)的指令.這些指令經(jīng)過錯誤注入后發(fā)生SDC的概率很小，甚至是否發(fā)生SDC與當次的地址有關(guān)，因而很難完整覆蓋.

本識別方法的覆蓋率比靜態(tài)分析方法Shoestring高59.9%.Shoestring只選擇了影響全局內(nèi)存和函數(shù)參數(shù)的指令作為SDC脆弱指令，導致其他形式的指令都沒有被覆蓋到.

5.2.3注入錯誤數(shù)與時間代價

本節(jié)比較本識別方法、Relyzer和全注入(每條指令都注入)的注入錯誤數(shù)和時間代價.圖7顯示了每個測試程序的注入錯誤數(shù)，圖8顯示了時間代價.其中，F(xiàn)ull-scale代表全注入，縱軸顯示了每種方法與全注入的注入錯誤數(shù)或時間代價的比值.注入錯誤數(shù)分為關(guān)鍵指令和非關(guān)鍵指令2部分.實驗中，非關(guān)鍵指令的部分占總注入錯誤數(shù)的87.9%，是注入錯誤數(shù)的主要部分.由于采用了推斷算法，非關(guān)鍵指令的注入錯誤數(shù)得到了大量削減.經(jīng)過統(tǒng)計，本識別方法比Relyzer的注入錯誤數(shù)平均減少25.6%，時間代價平均減少27.9%；相比于全注入，注入錯誤數(shù)平均減少74.6%，時間代價平均減少80.8%.

Fig. 7　The comparison of number of fault injections.圖7　注入錯誤數(shù)比較

Fig. 8　The comparison of time spent on injection.圖8　時間代價比較

5.2.4小結(jié)

綜上所述，本文的推斷算法得到的SDC脆弱指令的準確率為98.8%，只存在很少的誤判；與典型靜態(tài)注入方法Relyzer相比，本識別方法的覆蓋率高1.7%，時間代價低27.9%，因此錯誤注入更加高效.

6　結(jié)束語

本文通過建立程序的數(shù)據(jù)關(guān)聯(lián)圖，分析了導致SDC的錯誤傳播過程，開發(fā)了SDC脆弱指令識別方法.該方法在保證高準確度和高覆蓋率前提下，大大降低了注入錯誤數(shù)和時間代價.

在得到SDC脆弱指令后，下一步需要進行檢測機制的設(shè)計，包括檢測器的位置、形式以及檢測代價的評估.本文的推斷算法實際上找到了導致SDC的錯誤傳播路徑以及路徑上的關(guān)鍵點(關(guān)鍵指令節(jié)點).在未來的工作中，將研究檢測器的建模以及檢測代價的優(yōu)化等內(nèi)容.

[1]Walters J P, Zick K M, French M. A practical characterization of a NASA SpaceCube application through fault emulation and laser testing [C]Proc of IEEE Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2013: 1-8[2]Xing Kefei. Single event effect detection and mitigation techniques for spaceborne signal processing platform[D]. Changsha: National University of Defense Technology, 2007 (in Chinese)(邢克飛. 星載信號處理平臺單粒子效應(yīng)檢測與加固技術(shù)研究[D]. 長沙: 國防科學技術(shù)大學, 2007)[3]Xu Jianjun, Tan Qingping, Li Jianli, et al. An extendable control flow checking method based on formatted signatures[J]. Journal of Computer Research and Development, 2011, 48(4): 638-646 (in Chinese)(徐建軍, 譚慶平, 李建立, 等. 一種基于格式化標簽的可擴展控制流檢測方法[J]. 計算機研究與發(fā)展, 2011, 48(4): 638-646)[4]Racunas P, Constantinides K, Manne S, et al. Perturbation-based fault screening[C]Proc of the Int Symp on High Performance Computer Architecture. Los Alamitos, CA: IEEE Computer Society, 2007: 169-180[5]Gu W, Kalbarczyk Z, Iyer R K, et al. Characterization of Linux kernel behavior under errors[C]Proc of IEEE Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2003: 22-25[6]Wang N J, Patel S J. ReStore: Symptom-based soft error detection in microprocessors[J]. IEEE Trans on Dependable and Secure Computing, 2006, 3(3): 188-201[7]Li M L, Ramachandran P, Sahoo S K, et al. Understanding the propagation of hard errors to software and implications for resilient system design[C]Proc of Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS). New York:ACM, 2008: 265-276[8]Dimitrov M, Zhou H. Unified architectural support for soft-error protection or software bug detection[C]Proc of Int Conf on Parallel Architecture and Compilation Techniques. Los Alamitos, CA: IEEE Computer Society, 2007: 73-82[9]Reis G A, Chang J, August D I. Automatic instruction-level software-only recovery[J]. IEEE Micro, 2007, 27(1): 36-47[10]Feng S, Gupta S, Ansari A, et al. Shoestring: Probabilistic soft error reliability on the cheap[C]Proc of Int Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS). New York: ACM, 2010: 385-396[11]Hari S K S, Adve S V, Naeimi H. Low-cost program-level detectors for reducing silent data corruptions[C]Proc of IEEE Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2012: 1-12[12]Yim K S, Pham C, Saleheen M, et al. Hauberk: Lightweight silent data corruption error detector for GPGPU[C]Proc of IEEE Int Symp on Parallel & Distributed Processing Symp. Piscataway, NJ: IEEE, 2011: 287-300[13]Pattabiraman K, Kalbarczyk Z, Iyer R K. Application-based metrics for strategic placement of detectors[C]Proc of IEEE Pacific Rim Int Symp on Dependable Computing. Piscataway, NJ: IEEE, 2005: 75-82[14]Pradeep R, Prabhakar K, Jeffrey W K. Statistical fault injection[C]Proc of Dependable Systems and Networks. Piscataway, NJ: IEEE, 2008: 122-127[15]Hari S K S, Adve S V, Naeimi H, et al. Relyzer: Exploiting application-level fault equivalence to analyze application resiliency to transient faults[C]Proc of ASPLOS. New York: ACM, 2012: 123-134[16]Li J, Tan Q. SmartInjector: Exploiting intelligent fault injection for SDC rate analysis[C]Proc of IEEE Int Symp on Defect and Fault Tolerance in VLSI and Nanotechnology Systems. Piscataway, NJ: IEEE, 2013: 236-242[17]Xu X, Li M L. Understanding soft error propagation using efficient vulnerability-driven fault injection[C]Proc of IEEE Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2012: 1-12[18]Pattabiraman K, Nakka N, Kalbarczyk Z, et al. SymPLFIED: Symbolic program-level fault injection and error detection framework[C]Proc of Dependable Systems and Networks. Piscataway, NJ: IEEE, 2008: 472-481[19]Nethercote N, Mycroft A. Redux: A dynamic dataflow tracer[J]. Electronic Notes in Theoretical Computer Science, 2003, 89(2): 149-170[20]Luk C K, Cohn R, Muth R, et al. Pin: Building customized program analysis tools with dynamic instrumentation[J]. ACM Sigplan Notices, 2005, 40(6): 190-200[21]Hutchins M, Foster H, Goradia T, et al. Experiments of the effectiveness of dataflow-and controlflow-based test adequacy criteria[C]Proc of the 16th Int Conf on Software Engineering. Washington, DC: IEEE Computer Society, 1994: 191-200

Ma Junchi, born in 1988. PhD candidate. His current research interests include soft error mitigation and software reliability.

Wang Yun, born in 1967. Professor and PhD supervisor. Member of China Computer Federation. Her current research interests include distributed computing, fault tolerance and wireless sensor network.

Cai Zhenbo, born in 1971. Research fellow. His current research interests include spacecraft environment engineering.

Zhang Qingxiang, born in 1971. Research fellow. His current research interests include spacecraft environment engineering.

Wang Ying, born in 1982. Engineer. Her current research interests include spacecraft environment engineering.

Hu Cheng, born in 1988. PhD candidate. His current research interests include distributed computing and wireless rechargeable sensor network.

An Approach for Identifying SDC-Causing Instructions by Fault Propagation Analysis

Ma Junchi1,2, Wang Yun1,2, Cai Zhenbo3, Zhang Qingxiang3, Wang Ying3, and Hu Cheng1,2

1(SchoolofComputerScience&Engineering,SoutheastUniversity,Nanjing211189)2(KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)3(InstituteofSpacecraftSystemEngineering,ChinaAcademyofSpaceTechnology,Beijing100094)

Single event upset (SEU) is caused by external radiation in outer space and it has a great influence on computing reliability of space devices. As process technology scales, space devices become more susceptible to SEU. SEU could result in silent data corruption (SDC), which means wrong outcomes of a program without any crash detected. SDC may lead to serious failure and hence cannot be ignored. As SDC-causing fault always propagates silently, it is very difficult to detect SDC. To develop SDC detectors, SDC-causing instructions of a program should be identified as the first step. However, this step usually needs a huge number of fault injections, which is extremely time-consuming and not achievable for most applications. In this paper, we build data dependence graph (DDG) to capture the dependencies among the values of instructions. Then the inter-function and intra-function propagation that leads to SDC is analyzed and the sufficient condition of SDC-causing instructions is demonstrated. Further, we propose a novel method of identifying SDC-causing instructions. Taking advantage of the trace files of injection, our method can detect underlying SDC-causing instructions without any expensive computations. Validation efforts show that our method yields high accuracy and coverage rate with a great reduction of injection cost.

single event upset (SEU); soft error; SDC-causing instruction; fault injection; fault propagation

2014-12-12；

2015-12-14

TP302.8