,,,,

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

0 概述

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

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

1 相關(guān)研究工作

文獻(xiàn)[4,7]中關(guān)于軟件簽名和斷言算法,提出的最重要的解決辦法就是CFDSS技術(shù)和ECCA技術(shù)。這2種技術(shù)能實(shí)現(xiàn)很高的錯(cuò)誤檢測(cè)覆蓋率,但也存在一些不足,以下進(jìn)行簡(jiǎn)要的介紹和分析。

CFDSS是一項(xiàng)純軟件錯(cuò)誤檢測(cè)技術(shù),該技術(shù)中涉及的每一個(gè)基本塊都被賦予一個(gè)特殊的簽名。一個(gè)全局變量(記為G)包含動(dòng)態(tài)簽名,被初始化為程序中第一個(gè)基本塊的簽名。如果程序執(zhí)行過(guò)程中沒(méi)有出現(xiàn)控制流錯(cuò)誤,G應(yīng)等于當(dāng)前程序執(zhí)行基本塊中存儲(chǔ)的簽名。

兩個(gè)基本塊間的跳轉(zhuǎn)發(fā)生之后,結(jié)合前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn))的簽名,G通過(guò)異或運(yùn)算進(jìn)行更新。如果控制流來(lái)源于多個(gè)塊,則每一個(gè)源塊被賦予一個(gè)調(diào)整的簽名,這些簽名將被用于目標(biāo)塊中動(dòng)態(tài)簽名的計(jì)算。

ECCA賦予每一個(gè)基本塊2個(gè)標(biāo)示符:

1)塊標(biāo)示符(Block Identifier,BID):用不同的素?cái)?shù)值表征每一個(gè)基本塊。

2)控制流標(biāo)示符(Control Flow Indicator,CFID):通過(guò)存儲(chǔ)與下個(gè)基本塊的BID的乘積值來(lái)表示控制流。

CFID被存儲(chǔ)在初始化值為第一個(gè)基本塊的CFID的二元隊(duì)列中。當(dāng)控制流進(jìn)入一個(gè)基本塊時(shí),該基本塊的CFID就被壓入隊(duì)列,在該基本塊的出口處被彈出隊(duì)列,并且將CFID與該基本塊的BID相除。因?yàn)槊總€(gè)BID均由素?cái)?shù)組成,CFID與BID相除后總是返回一個(gè)零值,除非程序執(zhí)行了一個(gè)錯(cuò)誤的控制流跳轉(zhuǎn)。當(dāng)存儲(chǔ)CFID的隊(duì)列出現(xiàn)上溢或下溢時(shí),錯(cuò)誤也將會(huì)被檢測(cè)出。

因?yàn)镃FDSS是一項(xiàng)純軟件檢測(cè)方式,所以不需要額外的硬件支持。然而,同樣的簽名必須被賦予多個(gè)節(jié)點(diǎn),即共享扇入節(jié)點(diǎn)的情況同樣會(huì)發(fā)生。如果多個(gè)基本塊共享同樣的基本塊目標(biāo)地址,CFDSS就無(wú)法檢測(cè)出其中發(fā)生的跳轉(zhuǎn)錯(cuò)誤,這是該項(xiàng)技術(shù)的不足之處。

ECCA在算法中采用取余和除法運(yùn)算,增加了算法本身的開(kāi)銷。另外ECCA通過(guò)除法中分母為0引起異常來(lái)檢測(cè)控制流錯(cuò)誤,與系統(tǒng)錯(cuò)誤混淆,同時(shí)異常開(kāi)銷也非常大。

基于上述2種算法的優(yōu)缺點(diǎn),提出EDSS算法的關(guān)鍵在于使用了一個(gè)被稱為CFID表的二維表存儲(chǔ)基本塊和控制流的全部信息。本文在文獻(xiàn)[14]研究的基礎(chǔ)上,進(jìn)一步優(yōu)化了算法,能更好地運(yùn)用CFID表檢測(cè)出控制流圖中非法跳轉(zhuǎn)錯(cuò)誤。

2 控制流錯(cuò)誤檢測(cè)技術(shù)

2.1 控制流圖

本文提出的控制流錯(cuò)誤檢測(cè)方法采用了基本塊的概念?；緣K指的是一串連續(xù)的指令,程序從基本塊中的第一條指令開(kāi)始執(zhí)行,在執(zhí)行完最后一條指令后離開(kāi)基本塊。除了基本塊中的最后一條指令不做要求外,基本塊中的其余指令均不允許為分支指令、跳轉(zhuǎn)指令或者調(diào)用指令。

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

suc(vi)定義為后繼節(jié)點(diǎn)的集合,pred(vi)定義為前驅(qū)節(jié)點(diǎn)的集合。這表示如果vj屬于集合suc(vi),則bri,j就一定包含在E中,如果vj是pred(vi)中的一個(gè)元素,則brj,i就包含在E中。如果bri,j未被包含在E中,則該跳轉(zhuǎn)指令就是非法的,即當(dāng)一個(gè)非法指令分支被執(zhí)行時(shí),控制流錯(cuò)誤就會(huì)發(fā)生。若pred(vi)中的元素個(gè)數(shù)大于2,則vi就是一個(gè)分支扇入節(jié)點(diǎn)。在本文中后繼節(jié)點(diǎn)即為當(dāng)前節(jié)點(diǎn)。

2.2 控制流圖及其CFID表

簽名監(jiān)測(cè)技術(shù)在編譯時(shí)將簽名賦給控制流圖中一個(gè)或多個(gè)節(jié)點(diǎn)構(gòu)成的目標(biāo)基本塊,并在動(dòng)態(tài)執(zhí)行時(shí)生成同樣的簽名,再與靜態(tài)存儲(chǔ)的簽名進(jìn)行比較。CFDSS通過(guò)異或操作并運(yùn)用已賦值的簽名對(duì)程序控制流進(jìn)行檢測(cè)。就像在CFDSS中提及的,如果多個(gè)節(jié)點(diǎn)共享多個(gè)分支扇入節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn),非法與合法的分支間將會(huì)發(fā)生混淆,從而導(dǎo)致不可檢測(cè)的控制流錯(cuò)誤的產(chǎn)生。

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

以圖1中的樣例路徑所示,每一個(gè)圓圈為一個(gè)節(jié)點(diǎn),代表一個(gè)基本塊,且基本塊被賦予一系列遞增的正整數(shù)值作為標(biāo)志符,即v1,v2,…,接著編譯時(shí),軟件簽名SSi被賦給對(duì)應(yīng)節(jié)點(diǎn)vi。為使算法的賦值規(guī)則便于運(yùn)用在實(shí)現(xiàn)和檢測(cè)中,SSi就等于相應(yīng)的節(jié)點(diǎn)vi的標(biāo)志符值,即如圖1所示,SS1=0001,SS2=0002…將在之后部分進(jìn)一步說(shuō)明這個(gè)規(guī)則為查找二維表帶來(lái)的極大便利。

圖1 控制流圖及其節(jié)點(diǎn)簽名

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

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

圖2 存儲(chǔ)簽名的CFID表

2.3 控制流檢測(cè)機(jī)制

本節(jié)將基于3種可能情況運(yùn)用3個(gè)具有代表性的例子闡釋提出的軟件簽名檢測(cè)技術(shù)EDSS的具體功能:合法的分支,不合法的分支以及帶有2個(gè)共享分支扇入節(jié)點(diǎn)的非法分支等的錯(cuò)誤檢測(cè)機(jī)制。

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

圖3 合法指令跳轉(zhuǎn)的檢測(cè)

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

圖4 非法指令跳轉(zhuǎn)的檢測(cè)

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

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

圖5 2個(gè)共享分支扇入節(jié)點(diǎn)的非法指令跳轉(zhuǎn)的檢測(cè)

如果非法的指令分支指向目標(biāo)基本塊中除if-else檢測(cè)指令之外的其他位置,其中產(chǎn)生的控制流錯(cuò)誤一樣可通過(guò)未在v8中進(jìn)行更新的全局變量Reg被檢測(cè)出。由此得出只要各個(gè)節(jié)點(diǎn)被賦予了簽名,建立了基于EDSS算法的二維CFID表,EDSS的技術(shù)就可避免CFDSS中新產(chǎn)生的無(wú)法檢測(cè)出的非法指令跳轉(zhuǎn)錯(cuò)誤。

為了獲得對(duì)本文所做的為改善軟件簽名監(jiān)測(cè)技術(shù)的整體工作的理解,將在下一部分總結(jié)表述EDSS算法。

2.4 EDSS算法

類似CFDSS的算法設(shè)計(jì),EDSS的算法相比之下更加簡(jiǎn)潔和高效。節(jié)點(diǎn)中沒(méi)有嵌入指令來(lái)計(jì)算動(dòng)態(tài)運(yùn)行時(shí)的簽名,同樣,也沒(méi)有多余的指令在運(yùn)行過(guò)程中調(diào)整簽名。當(dāng)一個(gè)程序進(jìn)行編譯時(shí),EDSS算法給程序控制流圖中的每一個(gè)節(jié)點(diǎn)賦予了一個(gè)簽名,N等于程序中的節(jié)點(diǎn)總數(shù)。

EDSS算法設(shè)計(jì)步驟如下:

步驟1確定所有基本塊,建立程序的控制流圖,為每一個(gè)節(jié)點(diǎn)編號(hào),即基本塊標(biāo)識(shí)號(hào),在控制流圖中以自然數(shù)開(kāi)始,即vi,i=1,2,…,N。

步驟2對(duì)每一個(gè)節(jié)點(diǎn)vi都賦予一個(gè)簽名SSi,如果i≠j,則SSi≠SSj,其中i,j=1,2,…,N。每一個(gè)簽名SSi都與相應(yīng)的基本塊的標(biāo)識(shí)號(hào)相等。

步驟3對(duì)每一個(gè)vi,j=1,2,…,執(zhí)行:

1)對(duì)每一個(gè)分支bri,j,它的前驅(qū)節(jié)點(diǎn)為vi,后繼節(jié)點(diǎn)為vj。這些分支由一個(gè)二維表表示,該二維表稱為CFID[i,j]。在該表中,行i表示前驅(qū)節(jié)點(diǎn),列j表示后繼節(jié)點(diǎn)。

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

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

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

3 仿真實(shí)驗(yàn)結(jié)果

考慮到本文提出的EDSS算法是一項(xiàng)增強(qiáng)型的簽名監(jiān)測(cè)技術(shù),但采用了與CFDSS相比完全不同的錯(cuò)誤檢測(cè)方式,因此,對(duì)EDSS及CFDSS中錯(cuò)誤檢測(cè)的覆蓋率、開(kāi)銷代價(jià)等進(jìn)行縝密的分析是不可或缺的。相應(yīng)地,這一部分就集中于對(duì)仿真實(shí)驗(yàn)結(jié)果的評(píng)估分析。在導(dǎo)入實(shí)驗(yàn)之前主要將射入的錯(cuò)誤分為2類:一類為不帶共享分支扇入節(jié)點(diǎn)程序中生成的錯(cuò)誤;另一類為在包含2個(gè)或更多共享扇入節(jié)點(diǎn)程序中產(chǎn)生的錯(cuò)誤。對(duì)應(yīng)不同的程序,執(zhí)行過(guò)程中本文的目的在于比較這2種技術(shù)的行為與錯(cuò)誤檢測(cè)能力。

為了評(píng)估本文提出的基于表驅(qū)動(dòng)的控制流檢測(cè)技術(shù)EDSS的可行性和有效性,用C程序分別實(shí)現(xiàn)了EDSS算法和CFDSS算法,并分別實(shí)施了一系列錯(cuò)誤射入實(shí)驗(yàn),測(cè)試了這2種技術(shù)的錯(cuò)誤覆蓋率和開(kāi)銷代價(jià)。相比之下,實(shí)驗(yàn)結(jié)果證實(shí)這2項(xiàng)技術(shù)中的錯(cuò)誤檢測(cè)能力在被用于檢測(cè)帶有第1類錯(cuò)誤的程序時(shí)是相類似的,但當(dāng)程序中射入第2類錯(cuò)誤時(shí),EDSS技術(shù)就擁有了絕對(duì)優(yōu)勢(shì)。

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

表1 CFDSS和EDSS的檢錯(cuò)覆蓋率 %

需要注意的是無(wú)法應(yīng)用上述基準(zhǔn)測(cè)試程序檢測(cè)出EDSS和CFDSS在帶有2個(gè)或多個(gè)共享分支扇入節(jié)點(diǎn)的程序中的表現(xiàn),因?yàn)橛?個(gè)或多個(gè)共享分支扇入節(jié)點(diǎn)的構(gòu)造產(chǎn)生的可能性很小,在這些基準(zhǔn)測(cè)試程序中均很難找到。因此,表1的數(shù)據(jù)并不能全面評(píng)價(jià)EDSS的檢錯(cuò)覆蓋率。

鑒于上述原因,本文決定根據(jù)圖5所示的控制流圖構(gòu)造測(cè)試的程序。對(duì)有多扇入節(jié)點(diǎn)程序的檢錯(cuò)能力的評(píng)估如表2所示,實(shí)驗(yàn)中獲得的數(shù)據(jù)極好地證實(shí)了EDSS的錯(cuò)誤檢測(cè)能力,在具有1個(gè)共享分支扇入節(jié)點(diǎn)和2個(gè)嵌套的共享分支扇入節(jié)點(diǎn),以及1個(gè)共享分支扇入節(jié)點(diǎn)的循環(huán)測(cè)試程序中,EDSS算法的檢錯(cuò)率比CFDSS算法平均高出約1.9個(gè)百分點(diǎn),原因是有些分支跳轉(zhuǎn)錯(cuò)誤只能通過(guò)EDSS技術(shù)檢測(cè)出而無(wú)法通過(guò)CFDSS技術(shù)檢測(cè)出,而這恰好與在前述討論過(guò)的算法中提出的分析相符合。

表2 多扇入節(jié)點(diǎn)問(wèn)題中的檢錯(cuò)率 %

在算法增加的代碼空間開(kāi)銷方面,EDSS算法略優(yōu)于CFDSS算法。EDSS算法在對(duì)簽名的計(jì)算方面不要求在程序中插入計(jì)算動(dòng)態(tài)簽名的指令,這就相應(yīng)地減少了插入指令的數(shù)目。在這方面,CFDSS技術(shù)給每個(gè)基本塊設(shè)置了3條指令,而EDSS技術(shù)給每個(gè)基本塊僅設(shè)置2條指令。但EDSS算法需要在內(nèi)存中存儲(chǔ)CFID表,這需要一定的代碼空間開(kāi)銷。

除代碼空間開(kāi)銷以外,其他影響系統(tǒng)開(kāi)銷的關(guān)鍵性因素也是值得關(guān)注的。系統(tǒng)開(kāi)銷是通過(guò)檢測(cè)技術(shù)中額外指令的使用數(shù)量計(jì)算得到的,因此這是一個(gè)與編譯時(shí)插入的多余指令相關(guān)的問(wèn)題。由于EDSS算法較CFDSS算法所需要插入的指令數(shù)量更少,對(duì)于性能代價(jià),EDSS與CFDSS相比具有相對(duì)更高的性能優(yōu)勢(shì)。同時(shí)也考慮到,在EDSS算法中,錯(cuò)誤檢測(cè)指令需要從CFID表中讀取后繼節(jié)點(diǎn)的簽名,這將直接影響指令的執(zhí)行效率。對(duì)于這個(gè)問(wèn)題的解決辦法為,在程序初始化時(shí),在初始化用于存儲(chǔ)動(dòng)態(tài)簽名的全局變量Reg的同時(shí),通過(guò)將CFID[0,0]賦值給Reg,達(dá)到使CFID表裝載到高速緩存cache中,實(shí)現(xiàn)表1中數(shù)據(jù)的高速讀取。因此,EDSS算法檢測(cè)指令的減少有助于提高程序執(zhí)行的速度,并有助于改善EDSS技術(shù)的性能指標(biāo)。

因此,實(shí)驗(yàn)結(jié)果表明,從錯(cuò)誤檢測(cè)覆蓋率、代碼空間開(kāi)銷以及對(duì)程序性能影響等方面,EDSS算法是一種具有優(yōu)勢(shì)的純軟件簽名錯(cuò)誤檢測(cè)技術(shù),對(duì)比于已有的CFDSS錯(cuò)誤檢測(cè)技術(shù),在不增加代碼空間開(kāi)銷和對(duì)程序性能影響更小的前提下,解決了CFDSS算法不能檢測(cè)的2個(gè)或多個(gè)共享扇入節(jié)點(diǎn)非法跳轉(zhuǎn)的問(wèn)題,提高了控制流錯(cuò)誤檢測(cè)的覆蓋率。

4 結(jié)束語(yǔ)

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

[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] 李靜梅,吳艷霞,沈 晶,等.改進(jìn)的CFDSS控制流檢測(cè)算法[J].哈爾濱工程大學(xué)學(xué)報(bào),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] 張 鵬,朱 利,杜小智,等.基于結(jié)構(gòu)化標(biāo)簽的控制流錯(cuò)誤檢測(cè)算法[J].計(jì)算機(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ī)器人高可信軟件檢錯(cuò)技術(shù)[J].計(jì)算機(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] 李劍明,譚慶平,徐建軍,等.基于路徑跟蹤的控制流檢測(cè)[J].計(jì)算機(jī)工程,2009,35(20):68-70.

[13] 楊 挺,孫雨耕,張志東,等.無(wú)線傳感器網(wǎng)絡(luò)異構(gòu)驅(qū)動(dòng)路由算法[J].計(jì)算機(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] 谷曉鋼,江榮安,趙銘偉.無(wú)線傳感器網(wǎng)絡(luò)異構(gòu)驅(qū)動(dòng)路由算法[J].計(jì)算機(jī)工程,2008,34(19):12-14.