基于表驅動的純軟件簽名錯誤檢測算法

,,,,

(1.國家電網浙江省電力公司信息通信分公司,杭州 310007; 2.華東師范大學 計算機科學與軟件工程學院,上海 200062)

0 概述

隨著技術的發展,微處理器性能的改善將越來越依賴于體積更小、速度更快的晶體管,不同于制造與設計性錯誤等頻繁產生的錯誤,臨時性錯誤(也常被稱作軟錯誤),常常會導致不可預測的行為。最典型的軟錯誤是單粒子翻轉(Single Event Upset,SEU),該錯誤指的是發生在順序邏輯以及單粒子瞬變(Single Event Transient,SET)中的位翻轉,容忍這些錯誤的首要步驟就是檢測出這些錯誤,目前已有相當多的錯誤檢測技術。

錯誤檢測可以通過純硬件方式、軟硬件結合方式以及純軟件方式得以實現。一種常用的純硬件檢錯方式運用了MOTOROLA M68040微處理器[1],該處理器通過監測外部總線和主處理器的行為,實現并發的系統級錯誤檢測,但卻導致了時間和面積開銷的增大,并且隨著具有內部高速緩存和現代流水線技術的微處理器的廣泛應用,這種純硬件檢錯方式已經顯得不必要了。當前用于錯誤檢測的軟硬件混合型的檢錯方式也有很多,例如Argus[2]和CRAFT[3]。Argus基于馮諾依曼型處理器核,可檢測出核中除輸入輸出、異常、中斷部分的其他錯誤。然而,包括通過純軟件簽名的控制流檢測(CFDSS)[4-5]、通過斷言的控制流檢測(ACFC)[6]、運用斷言的增強型控制流檢測(ECCA)[7]、通過冗余指令[8]的錯誤檢測(EDDI)[9-11]等在內的純軟件處理方法,比上述這2種概念運用得更加廣泛,因為這些純軟件檢錯方式不要求特定的硬件設備提供支持。ACFC在執行過程中賦予每一個基本塊一個奇偶校驗位,可檢測出奇偶性錯誤;EDDI采用復制指令,并通過插入合適的檢測指令進行驗證,但這種方法易導致代碼容量增加近100%以及性能方面的損失[12-13]。本文在研究CFDSS算法的基礎上,提出一種基于表驅動[14-15]的控制流錯誤檢測算法,使用一張二維表和簽名來監測目標程序的控制流。

1 相關研究工作

文獻[4,7]中關于軟件簽名和斷言算法,提出的最重要的解決辦法就是CFDSS技術和ECCA技術。這2種技術能實現很高的錯誤檢測覆蓋率,但也存在一些不足,以下進行簡要的介紹和分析。

CFDSS是一項純軟件錯誤檢測技術,該技術中涉及的每一個基本塊都被賦予一個特殊的簽名。一個全局變量(記為G)包含動態簽名,被初始化為程序中第一個基本塊的簽名。如果程序執行過程中沒有出現控制流錯誤,G應等于當前程序執行基本塊中存儲的簽名。

兩個基本塊間的跳轉發生之后,結合前驅節點和后繼節點(當前節點)的簽名,G通過異或運算進行更新。如果控制流來源于多個塊,則每一個源塊被賦予一個調整的簽名,這些簽名將被用于目標塊中動態簽名的計算。

ECCA賦予每一個基本塊2個標示符:

1)塊標示符(Block Identifier,BID):用不同的素數值表征每一個基本塊。

2)控制流標示符(Control Flow Indicator,CFID):通過存儲與下個基本塊的BID的乘積值來表示控制流。

CFID被存儲在初始化值為第一個基本塊的CFID的二元隊列中。當控制流進入一個基本塊時,該基本塊的CFID就被壓入隊列,在該基本塊的出口處被彈出隊列,并且將CFID與該基本塊的BID相除。因為每個BID均由素數組成,CFID與BID相除后總是返回一個零值,除非程序執行了一個錯誤的控制流跳轉。當存儲CFID的隊列出現上溢或下溢時,錯誤也將會被檢測出。

因為CFDSS是一項純軟件檢測方式,所以不需要額外的硬件支持。然而,同樣的簽名必須被賦予多個節點,即共享扇入節點的情況同樣會發生。如果多個基本塊共享同樣的基本塊目標地址,CFDSS就無法檢測出其中發生的跳轉錯誤,這是該項技術的不足之處。

ECCA在算法中采用取余和除法運算,增加了算法本身的開銷。另外ECCA通過除法中分母為0引起異常來檢測控制流錯誤,與系統錯誤混淆,同時異常開銷也非常大。

基于上述2種算法的優缺點,提出EDSS算法的關鍵在于使用了一個被稱為CFID表的二維表存儲基本塊和控制流的全部信息。本文在文獻[14]研究的基礎上,進一步優化了算法,能更好地運用CFID表檢測出控制流圖中非法跳轉錯誤。

2 控制流錯誤檢測技術

2.1 控制流圖

本文提出的控制流錯誤檢測方法采用了基本塊的概念?；緣K指的是一串連續的指令,程序從基本塊中的第一條指令開始執行,在執行完最后一條指令后離開基本塊。除了基本塊中的最后一條指令不做要求外,基本塊中的其余指令均不允許為分支指令、跳轉指令或者調用指令。

控制流圖由節點集合V={v1,v2,…,vi,…,vn}和路徑集合E={e1,e2,…,ei,…,em}組成,使用控制流圖,能準確描述程序P的控制流,即程序P可表示為P={V,E}。一個節點vi表示一個基本塊,其中i為正整數,表示基本塊在程序中的位置。一條路徑表示從vi到vj的分支bri,j。路徑bri,j不一定總代表分支指令,也可表示跳轉、子程序和返回指令等。

suc(vi)定義為后繼節點的集合,pred(vi)定義為前驅節點的集合。這表示如果vj屬于集合suc(vi),則bri,j就一定包含在E中,如果vj是pred(vi)中的一個元素,則brj,i就包含在E中。如果bri,j未被包含在E中,則該跳轉指令就是非法的,即當一個非法指令分支被執行時,控制流錯誤就會發生。若pred(vi)中的元素個數大于2,則vi就是一個分支扇入節點。在本文中后繼節點即為當前節點。

2.2 控制流圖及其CFID表

簽名監測技術在編譯時將簽名賦給控制流圖中一個或多個節點構成的目標基本塊,并在動態執行時生成同樣的簽名,再與靜態存儲的簽名進行比較。CFDSS通過異或操作并運用已賦值的簽名對程序控制流進行檢測。就像在CFDSS中提及的,如果多個節點共享多個分支扇入節點作為目標節點,非法與合法的分支間將會發生混淆,從而導致不可檢測的控制流錯誤的產生。

本文結合有限狀態自動機(Finite State Machine,FSM)理論和控制流圖的基本原理,提出基于編譯時生成的控制流圖(對應于CFID表)及應用軟件簽名的錯誤檢測技術(Error Detection of Software Signature,EDSS),這與先前在CFDSS中使用的方法完全不同。運用EDSS的技術,多于2個分支扇入節點中產生的非法指令分支錯誤也將被檢測出。EDSS的檢測技術的另一大優勢在于它的簡潔性,在本文的檢測指令中,無需按位異或操作指令來計算動態簽名,而僅需要在每個基本塊上進行比較操作。

以圖1中的樣例路徑所示,每一個圓圈為一個節點,代表一個基本塊,且基本塊被賦予一系列遞增的正整數值作為標志符,即v1,v2,…,接著編譯時,軟件簽名SSi被賦給對應節點vi。為使算法的賦值規則便于運用在實現和檢測中,SSi就等于相應的節點vi的標志符值,即如圖1所示,SS1=0001,SS2=0002…將在之后部分進一步說明這個規則為查找二維表帶來的極大便利。

圖1 控制流圖及其節點簽名

簽名在編譯時被賦給各基本塊。同樣地,在程序控制流圖的基礎上用于存儲簽名的二維表也是在編譯時建立的。EDSS技術的核心特點之一就是這張本文稱為CFID表的二維表的建立。這張CFID表本質上就是一個二維數組,對應i行j列位置上的數值即為CFID[i,j],這代表控制流中的位置標識和跳轉路徑。行數值i表示前驅節點的標識號,列數值j表示當前節點的標識號。以二維表中的一個元素CFID[i,j]為例,它表示從節點vi到節點vj的一條分支。如果bri,j是一條允許的分支,即SSj被存儲在CFID[i,j]中,且SSj不等于0。否則,如果0被存儲在CFID[i,j]中相應位置上,就表示bri,j不是一條合法的指令。當程序首次執行時,值為0的元素CFID[0,0]被讀入,CFID表由此從主存被載入到高速緩存器cache中以提高查表速度。

圖2就是與圖1中表示的控制流圖相對應的CFID表。該CFID表中的空格默認為已填入了0值。同時由于br1,3、br2,4、br2,5…均為合法的分支,后繼節點的簽名SS3、SS4、SS5…就相應地按照前述規則被分別存入CFID[1,3]、CFID[2,4]、CFID[2,5]…中。

圖2 存儲簽名的CFID表

2.3 控制流檢測機制

本節將基于3種可能情況運用3個具有代表性的例子闡釋提出的軟件簽名檢測技術EDSS的具體功能:合法的分支,不合法的分支以及帶有2個共享分支扇入節點的非法分支等的錯誤檢測機制。

圖3是對不帶共享扇入節點的允許執行分支的檢測,圖中所有基本塊都已被標識且編號。如圖3左邊所示,每一個基本塊都被賦予了不同的且與它們自身位置標識相等的數值。圖3右邊表明了檢測指令是如何進行錯誤檢測的。當程序執行到v3時,在接著執行v3中的指令之前,先執行SS3與CFID[Reg,SS3]的比較。Reg是一個用于存儲動態簽名的全局變量,該全局變量被儲存在分配好的寄存器中。如果SS3與CFID[Reg,SS3]的相等關系成立,即若brReg,3是一條合法的分支,則Reg將被更新為SS3,且該基本塊中的原指令將被繼續執行,直到程序執行到下一基本塊v6。接下去SS6與CFID[Reg,SS6]的比較同上個基本塊一樣被執行。如果brReg,6是一條非法的分支,則CFID[Reg,SS6]對應的值一定為0而不是SS6,錯誤語句被執行,從而控制流錯誤被檢測出。

圖3 合法指令跳轉的檢測

圖4表示一條非法跳轉指令的執行以及該錯誤是如何被檢測出的。這種情況下的控制流錯誤可分為2種情況:一種指向if條件語句的非法跳轉;另一種指向下一基本塊中間位置的非法跳轉。在非法跳轉br1,4被執行前,Reg有原值SS1。前一種情況下,當程序執行到v4的if 語句時,CFID[Reg,SS4]從存儲在緩存器cache中的二維CFID表中讀出,并且由于br1,4是不被允許的,CFID[Reg,SS4]對應的值為0。因此,這種不匹配導致接下去的error指令將控制流轉移到出錯處理程序中。

圖4 非法指令跳轉的檢測

而在后一種情況下,跳轉到基本塊中間部分的非法跳轉在EDSS的支持下也可被檢測出來。但是由于分支跳過了v4的檢測指令,檢測產生延遲。從v1到v4的非法跳轉產生,程序控制轉移到v4中的一條指令。Reg保持v1中的簽名不變,直到程序在執行了v4中的指令后運行到v7。顯然,這種情況下CFID[Reg,v7]的對應值為0,這與SS7不同,所以,條件分支指令“ifSS7≠CFID[Reg,SS7] error elseReg=SS7”應跳轉到出錯處理程序。

圖5顯示了多個節點共享多個分支扇入節點作為目標節點的情況。在CFDSS技術下易發生指令跳轉混淆的問題,但EDSS技術為該相對復雜的問題提供了簡單的解決辦法,避免了混淆問題的出現。在圖5中,v7為一個有3個前驅節點v3、v4、v5(pred(v7)={v3,v4,v5})的分支扇入節點。根據上文討論的算法,SS7被分別填入CFID[3,7]、CFID[4,7]和CFID[5,7]中。節點v8也是一個分支扇入節點,但只有2個前驅節點v4、v5,不包括v3,即pred(v8)={v4,v5}。因此,CFID[4,8]和CFID[5,8]中均存儲著SS8,而CFID[3,8]中存儲著0值。程序允許的跳轉指令br4,7、br5,8以圖3中顯示的相同方式被檢測和執行。假設一條非法跳轉br3,8出現,并執行到v8的檢測指令位置,在該位置進行CFID[Reg,8]與SS8的比較。Reg在該非法跳轉執行前的值為SS3,且CFID[3,8]在二維CFID表中的對應值為0,因此該控制流錯誤就被檢測出來了。

圖5 2個共享分支扇入節點的非法指令跳轉的檢測

如果非法的指令分支指向目標基本塊中除if-else檢測指令之外的其他位置,其中產生的控制流錯誤一樣可通過未在v8中進行更新的全局變量Reg被檢測出。由此得出只要各個節點被賦予了簽名,建立了基于EDSS算法的二維CFID表,EDSS的技術就可避免CFDSS中新產生的無法檢測出的非法指令跳轉錯誤。

為了獲得對本文所做的為改善軟件簽名監測技術的整體工作的理解,將在下一部分總結表述EDSS算法。

2.4 EDSS算法

類似CFDSS的算法設計,EDSS的算法相比之下更加簡潔和高效。節點中沒有嵌入指令來計算動態運行時的簽名,同樣,也沒有多余的指令在運行過程中調整簽名。當一個程序進行編譯時,EDSS算法給程序控制流圖中的每一個節點賦予了一個簽名,N等于程序中的節點總數。

EDSS算法設計步驟如下:

步驟1確定所有基本塊,建立程序的控制流圖,為每一個節點編號,即基本塊標識號,在控制流圖中以自然數開始,即vi,i=1,2,…,N。

步驟2對每一個節點vi都賦予一個簽名SSi,如果i≠j,則SSi≠SSj,其中i,j=1,2,…,N。每一個簽名SSi都與相應的基本塊的標識號相等。

步驟3對每一個vi,j=1,2,…,執行:

1)對每一個分支bri,j,它的前驅節點為vi,后繼節點為vj。這些分支由一個二維表表示,該二維表稱為CFID[i,j]。在該表中,行i表示前驅節點,列j表示后繼節點。

2)如果分支bri,j在控制流圖中,SSj填入CFID[i,j]對應的位置。否則CFID[i,j]位置應填入0值。

3)Reg寄存器中存儲的全局變量在基本塊每一次執行其檢測指令時都更新一次,以跟蹤程序執行過程中簽名的變化。

4)在基本塊的初始位置插入指令“ifSSi≠CFID[Reg,SSi] error elseReg=SSi”。

3 仿真實驗結果

考慮到本文提出的EDSS算法是一項增強型的簽名監測技術,但采用了與CFDSS相比完全不同的錯誤檢測方式,因此,對EDSS及CFDSS中錯誤檢測的覆蓋率、開銷代價等進行縝密的分析是不可或缺的。相應地,這一部分就集中于對仿真實驗結果的評估分析。在導入實驗之前主要將射入的錯誤分為2類:一類為不帶共享分支扇入節點程序中生成的錯誤;另一類為在包含2個或更多共享扇入節點程序中產生的錯誤。對應不同的程序,執行過程中本文的目的在于比較這2種技術的行為與錯誤檢測能力。

為了評估本文提出的基于表驅動的控制流檢測技術EDSS的可行性和有效性,用C程序分別實現了EDSS算法和CFDSS算法,并分別實施了一系列錯誤射入實驗,測試了這2種技術的錯誤覆蓋率和開銷代價。相比之下,實驗結果證實這2項技術中的錯誤檢測能力在被用于檢測帶有第1類錯誤的程序時是相類似的,但當程序中射入第2類錯誤時,EDSS技術就擁有了絕對優勢。

聚焦于不帶共享扇入節點的程序中出現的第1類錯誤,為比較EDSS和CFDSS,實驗中選擇了4個基準測試程序:1)LZW(壓縮程序);2)FFT(快速傅里葉變換程序);3)矩陣乘法運算程序;4)快速排序。其中,LZW和FFT是相對較大的基準測試程序。EDSS和CFDSS這2個算法都是用C語言實現的,通過比較應用EDSS技術寫出的程序以及參照應用CFDSS寫出的程序的檢錯覆蓋率,結果記錄在表1中。從表1中的數據可以看出,EDSS在FFT和快速排序上的檢錯覆蓋率比CFDSS高出約1.5%,在LZW和矩陣乘法上與CFDSS幾乎具有相同的檢錯覆蓋率。由此可知,EDSS具備比CFDSS更好的錯誤檢測能力,滿足錯誤檢測的要求。

表1 CFDSS和EDSS的檢錯覆蓋率 %

需要注意的是無法應用上述基準測試程序檢測出EDSS和CFDSS在帶有2個或多個共享分支扇入節點的程序中的表現,因為有2個或多個共享分支扇入節點的構造產生的可能性很小,在這些基準測試程序中均很難找到。因此,表1的數據并不能全面評價EDSS的檢錯覆蓋率。

鑒于上述原因,本文決定根據圖5所示的控制流圖構造測試的程序。對有多扇入節點程序的檢錯能力的評估如表2所示,實驗中獲得的數據極好地證實了EDSS的錯誤檢測能力,在具有1個共享分支扇入節點和2個嵌套的共享分支扇入節點,以及1個共享分支扇入節點的循環測試程序中,EDSS算法的檢錯率比CFDSS算法平均高出約1.9個百分點,原因是有些分支跳轉錯誤只能通過EDSS技術檢測出而無法通過CFDSS技術檢測出,而這恰好與在前述討論過的算法中提出的分析相符合。

表2 多扇入節點問題中的檢錯率 %

在算法增加的代碼空間開銷方面,EDSS算法略優于CFDSS算法。EDSS算法在對簽名的計算方面不要求在程序中插入計算動態簽名的指令,這就相應地減少了插入指令的數目。在這方面,CFDSS技術給每個基本塊設置了3條指令,而EDSS技術給每個基本塊僅設置2條指令。但EDSS算法需要在內存中存儲CFID表,這需要一定的代碼空間開銷。

除代碼空間開銷以外,其他影響系統開銷的關鍵性因素也是值得關注的。系統開銷是通過檢測技術中額外指令的使用數量計算得到的,因此這是一個與編譯時插入的多余指令相關的問題。由于EDSS算法較CFDSS算法所需要插入的指令數量更少,對于性能代價,EDSS與CFDSS相比具有相對更高的性能優勢。同時也考慮到,在EDSS算法中,錯誤檢測指令需要從CFID表中讀取后繼節點的簽名,這將直接影響指令的執行效率。對于這個問題的解決辦法為,在程序初始化時,在初始化用于存儲動態簽名的全局變量Reg的同時,通過將CFID[0,0]賦值給Reg,達到使CFID表裝載到高速緩存cache中,實現表1中數據的高速讀取。因此,EDSS算法檢測指令的減少有助于提高程序執行的速度,并有助于改善EDSS技術的性能指標。

因此,實驗結果表明,從錯誤檢測覆蓋率、代碼空間開銷以及對程序性能影響等方面,EDSS算法是一種具有優勢的純軟件簽名錯誤檢測技術,對比于已有的CFDSS錯誤檢測技術,在不增加代碼空間開銷和對程序性能影響更小的前提下,解決了CFDSS算法不能檢測的2個或多個共享扇入節點非法跳轉的問題,提高了控制流錯誤檢測的覆蓋率。

4 結束語

在純軟件簽名的控制流檢測技術(CFDSS)的基礎上,基于有限狀態自動機原理,本文提出了基于表驅動的純軟件簽名錯誤檢測算法(EDSS)。編譯時,控制流圖中的信息,包括各節點之間的關系,都是通過構建一張二維CFID表表達的。表中存儲著控制流圖合法路徑中目標節點的簽名。當出現非法跳轉時,通過檢測賦予變量Reg的簽名和表中存儲的目標節點的簽名,控制流錯誤能被可靠地檢測出。根據這種方法,共享多于2個扇入節點導致的非法指令跳轉錯誤也可由本文提出的算法得以檢測。實驗結果顯示,EDSS算法平均錯誤檢測覆蓋率為98.1%,比CFDSS算法高出1.3%,在共享分支扇入節點的測試程序中,EDSS算法的檢錯率比CFDSS算法平均高出約1.9個百分點,并且EDSS技術在每個基本塊中為錯誤檢測插入的指令數相對更少。

[1] BENSO A,CARLO S D,Natale G D,et al.A watchdog processor to detect data and control flow errors[C]//Proceedings of the 9th IEEE International On-line Testing Symposium.Washington D.C.,USA:IEEE Press,2003:144-148.

[2] NATHAN R,SORIN D J.Argus-G:comprehensive,low-cost error detection for GPGPU cores[J].IEEE Computer Architecture Letters,2015,14(1):13-16.

[3] REIS G A,CHANG J,VACHHARAJANI N,et al.Design and evaluation of hybrid fault-detection systems[J].ACM Sigarch Computer Architecture News,2005,33(2):148-159.

[4] SEVERINOVA H,ABAFFY J,KRAJCOVIC T.Control-flow checking using binary encoded software signatures[C]//Proceedings of Innovations and Advances in Computing,Informatics,Systems Sciences,Networking and Engineering.Berlin,Germany:Springer,2015:345-347.

[5] 李靜梅,吳艷霞,沈 晶,等.改進的CFDSS控制流檢測算法[J].哈爾濱工程大學學報,2011,32(6):814-819.

[6] NAZARIAN G,RODRIGUES D G,MOREIRA A,et al.Bit-flip aware control-flow error detection[C]//Proceedings of Euromicro International Conference on Parallel,Distributed and Network-based Processing.Berlin,Germany:Springer,2015:215-221.

[7] LI Aiguo,HONG Bingrong.On-line control flow error detection using relationship signatures among basic blocks[J].Computers and Electrical Engineering,2010,36(1):132-141.

[8] 張 鵬,朱 利,杜小智,等.基于結構化標簽的控制流錯誤檢測算法[J].計算機工程,2016,42(6):37-42.

[9] ALWI H,EDWARDS C,TAN C P.Fault detection and fault-tolerant control using sliding modes[M].Berlin,Germany:Springer,2015.

[10] 高 星,廖明宏,吳翔虎.空間機器人高可信軟件檢錯技術[J].計算機工程,2009,35(16):56-58.

[11] MIAO S,DOU W,LI Y.An error-detecting approach for fault tolerance parallel recomputing with parallel digital terrain analysis[J].Journal of Algorithms & Computational Technology,2016,34(10):539-542.

[12] 李劍明,譚慶平,徐建軍,等.基于路徑跟蹤的控制流檢測[J].計算機工程,2009,35(20):68-70.

[13] 楊 挺,孫雨耕,張志東,等.無線傳感器網絡異構驅動路由算法[J].計算機工程,2016,42(3):7-12.

[14] JU Xiaoming,ZHANG Helen,WANG Aoran.Error detection by software signatures based on control flow graph[C]//Proceedings of International Conference on Future Computer and Information Technology.Berlin,Germany:Springer,2013:51-63.

[15] 谷曉鋼,江榮安,趙銘偉.無線傳感器網絡異構驅動路由算法[J].計算機工程,2008,34(19):12-14.