基于delta碼的乘除法運(yùn)算錯(cuò)誤檢測(cè)改進(jìn)算法

孫宗奇,臧海娟,張春花,潘 勇

1.同濟(jì)大學(xué) 電子與信息工程學(xué)院,上海 201804; 2.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院,江蘇 常州 213001)(*通信作者電子郵箱zhjuan@qq.com)

基于delta碼的乘除法運(yùn)算錯(cuò)誤檢測(cè)改進(jìn)算法

孫宗奇1,臧海娟2*,張春花1,潘 勇1

1.同濟(jì)大學(xué) 電子與信息工程學(xué)院,上海 201804; 2.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院,江蘇 常州 213001)(*通信作者電子郵箱zhjuan@qq.com)

為確保安全苛求系統(tǒng)中程序執(zhí)行的正確性,研究人員將差錯(cuò)控制理論用于對(duì)計(jì)算機(jī)指令進(jìn)行編碼,但由于編碼大多涉及模運(yùn)算,導(dǎo)致復(fù)雜度大量增加，應(yīng)用于實(shí)時(shí)系統(tǒng)有困難。針對(duì)復(fù)雜度問(wèn)題對(duì)delta碼的乘除法運(yùn)算算法進(jìn)行改進(jìn)。算法在乘法運(yùn)算中引入冗余編碼及差異化思想,從而確保安全性；在除法運(yùn)算中引入逆元,將除法運(yùn)算轉(zhuǎn)化為低復(fù)雜度的乘法運(yùn)算,避免了模運(yùn)算帶來(lái)的開(kāi)銷(xiāo),降低了復(fù)雜度并提高了算法安全性,并對(duì)安全性進(jìn)行理論論證。理論分析表明：所提算法漏檢率可達(dá)2.3×10-10。測(cè)試結(jié)果表明,所提算法的漏檢率與理論值相符，且復(fù)雜度是未編碼運(yùn)算6.4～7.2倍,比原delta碼降低了7%～19%,在漏檢率與復(fù)雜度方面均滿足安全苛求系統(tǒng)的應(yīng)用要求。

安全編碼;數(shù)據(jù)差異化;錯(cuò)誤檢測(cè);安全性;逆元

0 引言

隨著計(jì)算機(jī)在安全苛求領(lǐng)域里的廣泛應(yīng)用,計(jì)算系統(tǒng)的安全性已經(jīng)成為研究機(jī)構(gòu)關(guān)注的熱點(diǎn)問(wèn)題。但計(jì)算系統(tǒng)受到氣候、電磁、輻射和力學(xué)等環(huán)境因素的影響,如強(qiáng)電磁干擾、惡劣的散熱條件、低溫環(huán)境、長(zhǎng)期振動(dòng)等因素,都可能造成處理器失效、比特翻轉(zhuǎn)等狀況,導(dǎo)致計(jì)算錯(cuò)誤。這種錯(cuò)誤隨機(jī)性使系統(tǒng)安全存在著很大隱患。

針對(duì)這些問(wèn)題,自20世紀(jì)70年代末,研究人員就開(kāi)始研究利用編碼技術(shù)來(lái)保障計(jì)算安全的理論和方法,稱為安全編碼理論。Forin[1]提出了基于算術(shù)碼的運(yùn)算正確性檢測(cè)方法。該方法將冗余編碼應(yīng)用到對(duì)計(jì)算機(jī)的各類(lèi)運(yùn)算進(jìn)行編碼過(guò)程中,通過(guò)對(duì)指令層面進(jìn)行編碼運(yùn)算來(lái)檢測(cè)計(jì)算過(guò)程中的錯(cuò)誤,并簡(jiǎn)要地給出了典型指令,如加法、減法、控制流方面的編碼思路。Schiffel[2]基于Forin提出的方法上分別對(duì)四則運(yùn)算、邏輯運(yùn)算、位運(yùn)算進(jìn)行了算術(shù)碼編碼,并對(duì)復(fù)雜度進(jìn)行了測(cè)試。但由于文獻(xiàn)[2]算法中運(yùn)用了模運(yùn)算,李剛等[3]總結(jié)了其算術(shù)運(yùn)算復(fù)雜度會(huì)因此增加20倍以上,應(yīng)用于實(shí)時(shí)系統(tǒng)有困難。

為將檢測(cè)計(jì)算錯(cuò)誤的方法有效地應(yīng)用到實(shí)時(shí)的安全苛求系統(tǒng),需對(duì)這些編碼方式進(jìn)行優(yōu)化,且從理論上對(duì)該算法進(jìn)行安全性分析,使其編碼后產(chǎn)生的開(kāi)銷(xiāo)減少到實(shí)時(shí)安全苛求系統(tǒng)能接受的范圍,保障該系統(tǒng)的安全性和可靠性。

Kuvaiskii等[4]提出了基于AN碼(arithmetic-code, AN code)和重復(fù)指令的delta碼(Δ-Encoding),通過(guò)對(duì)AN碼系數(shù)的差異化取值,在安全性驗(yàn)證過(guò)程中使用右移運(yùn)算代替模運(yùn)算,簡(jiǎn)化了解碼過(guò)程,降低了復(fù)雜度,使其僅增加6～10倍。但delta碼對(duì)于乘除法運(yùn)算,均采用單目編碼,即由編碼數(shù)據(jù)和未編碼數(shù)據(jù)混合運(yùn)算,通過(guò)理論證明得出,單目編碼安全性對(duì)比雙目編碼有所下降；且算法返回值是預(yù)期結(jié)果的AN編碼,結(jié)果校驗(yàn)時(shí)還要加入AN碼解碼過(guò)程,并引入了額外的除法運(yùn)算,導(dǎo)致了復(fù)雜度增加。

本文對(duì)delta碼乘除法編碼方案進(jìn)行改進(jìn),改進(jìn)后的乘除法的算法,將單目編碼改進(jìn)為雙目編碼,即計(jì)算時(shí)對(duì)所有操作數(shù)均進(jìn)行編碼,使安全性驗(yàn)證過(guò)程中只包含加減法運(yùn)算及右移運(yùn)算,消除了結(jié)果校驗(yàn)時(shí)額外的除法運(yùn)算部分,降低了復(fù)雜度;并對(duì)所改進(jìn)的算法安全性進(jìn)行理論證明,計(jì)算出本文算法漏檢率達(dá)到2.3×10-10,低于delta碼漏檢率。本文通過(guò)Pin庫(kù)注入故障進(jìn)行檢錯(cuò)率與復(fù)雜度測(cè)試實(shí)驗(yàn),驗(yàn)證了本文算法的漏檢率與理論值相符,且復(fù)雜度增加7倍左右。

1 delta碼乘除法改進(jìn)算法

1.1 原delta碼乘除法算法及改進(jìn)

以乘法運(yùn)算為例進(jìn)行說(shuō)明,delta碼對(duì)操作數(shù)進(jìn)行兩次AN編碼,AN碼的編碼方式為：進(jìn)行校驗(yàn)時(shí),若編碼數(shù)據(jù)X能被A整除則運(yùn)算正確；否則運(yùn)算錯(cuò)誤。delta碼乘法運(yùn)算的具體編碼方式如式(1)所示:

(1)

兩次AN編碼的系數(shù)分別為A1、A2,delta碼對(duì)A1與A2差異化取值為:A1=213+1，A2=213-1,使A1+A2=214,因此包含A1+A2的部分可用右移14位代替除法運(yùn)算,對(duì)A1-A2=21可用右移1位代替除法運(yùn)算,從而省去了除法運(yùn)算,降低了復(fù)雜度。delta碼算法應(yīng)用于32位系統(tǒng)中。A1、A2取在213周?chē)鷷r(shí),16位的操作數(shù),在解碼時(shí)右移14位后,不會(huì)超過(guò)32位,不會(huì)造成溢出。

運(yùn)算過(guò)程分別由X1、X2相加、相減并右移計(jì)算出T1、T2。如果計(jì)算無(wú)誤,則T1、T2的值均應(yīng)當(dāng)?shù)扔?x。

(2)

T1、Y1相乘得到K1,T2、Y2相乘得到K2,如果計(jì)算無(wú)誤,則相當(dāng)于x直接與Y1、Y2相乘。

(3)

得到K1、K2后進(jìn)行解碼過(guò)程,分別令其對(duì)A1、A2做除法運(yùn)算,得到計(jì)算結(jié)果Z1、Z2,如果計(jì)算無(wú)誤,則Z1、Z2均應(yīng)當(dāng)?shù)扔趚*y,如果Z1、Z2的結(jié)果相同,視為計(jì)算正確;否則視為計(jì)算錯(cuò)誤,返回false。

(4)

式(3)相當(dāng)于只進(jìn)行了單目編碼,即兩個(gè)操作數(shù)中只有Y是編碼的,而X是不編碼的。文獻(xiàn)[4]提出使用單目編碼的delta碼的理論漏檢率為1/(A1*A2),最小漏檢率約為3.7×10-9,高于本改進(jìn)雙目編碼算法的理論漏檢率。原delta碼中由于返回值是z的AN編碼,因此在得到計(jì)算結(jié)果z之前還需要對(duì)返回值Z1、Z2進(jìn)行AN碼解碼,即需要對(duì)其進(jìn)行除法運(yùn)算,增加了AN碼的復(fù)雜度。

本文改進(jìn)了delta碼乘法、除法的算法,對(duì)delta碼進(jìn)行雙目編碼。在不改變A1、A2取值的基礎(chǔ)上,使計(jì)算與檢錯(cuò)完全使用編碼后的操作數(shù)進(jìn)行,實(shí)現(xiàn)了編碼數(shù)據(jù)參與運(yùn)算,且省去了delta碼中的模運(yùn)算過(guò)程,降低了delta碼的復(fù)雜度。

1.2 乘法編碼算法

本文算法對(duì)原delta碼進(jìn)行改進(jìn),將單目編碼改進(jìn)為雙目編碼,即完全通過(guò)操作數(shù)編碼后的數(shù)據(jù)進(jìn)行計(jì)算。X1、X2、Y1、Y2為x、 y分別以A1、A2為系數(shù)進(jìn)行AN編碼后的編碼數(shù)據(jù),A1、A2的取值與delta碼相同。具體編碼如式(5)所示:

(5)

算法分兩部分：

第一部分由X1、Y1相乘得到M1,X2、Y1相乘得到N1,具體編碼如式(6)所示:

(6)

由M1、N1計(jì)算出V1、V2,具體過(guò)程如式(7)所示:

(7)

此后對(duì)V1右移14位得到S1,對(duì)V2右移1位得到S2。

(8)

以乘法運(yùn)算z=x*y為例,所有運(yùn)算不出錯(cuò)時(shí),第一部分計(jì)算過(guò)程如式(9)所示:

(9)

此處進(jìn)行第一次安全性校驗(yàn),檢驗(yàn)(S1==S2)==true是否成立,如果計(jì)算無(wú)誤,則S1、S2的值的應(yīng)當(dāng)相同；如果S1、S2的結(jié)果不同,則說(shuō)明存在計(jì)算錯(cuò)誤,返回false。

第二部分由X1、Y2相乘得到M2,X2、Y2相乘得到N2,具體編碼如式(10)所示:

(10)

由M2、N2計(jì)算出V3、V4,具體過(guò)程如式(11)所示:

(11)

此后對(duì)V3右移14位得到S3,對(duì)V4右移1位得到S4,具體過(guò)程如式(12)所示:

(12)

所有運(yùn)算不出錯(cuò)時(shí),第二部分計(jì)算過(guò)程如式(13)所示:

(13)

此處進(jìn)行第二次安全性校驗(yàn),檢驗(yàn)S3==S4是否為true,若計(jì)算正確,則S3、S4的值相同；若S3、S4的結(jié)果不同,則表明計(jì)算錯(cuò)誤,返回false。

算法中的第三次安全性校驗(yàn),對(duì)S1、S3的和右移14位,對(duì)S2、S4的差右移一位。

2.3.2 精密度 隨機(jī)選取6個(gè)心肌組織樣品（編號(hào)分別為1 001、2 004、3 106、4 106、4 108、5 109）混勻進(jìn)行前處理，按實(shí)驗(yàn)室建立的分析方法，按體積比1∶1加入0.02 mg/mL混合對(duì)照品溶液，樣品重復(fù)進(jìn)樣6次，用各物質(zhì)的標(biāo)準(zhǔn)曲線，計(jì)算各物質(zhì)的濃度，用濃度結(jié)果計(jì)算樣品的日內(nèi)精密度；第2天再重復(fù)進(jìn)樣6次，計(jì)算各物質(zhì)的濃度，用12次實(shí)驗(yàn)結(jié)果計(jì)算樣品的日間精密度。實(shí)驗(yàn)結(jié)果表明，除ATP日間精密度3.80%、肌酐的日間精密度4.98%之外，各組分日內(nèi)、日間精密度均小于2%，說(shuō)明心肌樣品中各能量組分的精密度良好。

(14)

若計(jì)算正確,右移的結(jié)果均等于x*y；若兩次右移結(jié)果不同,則表明計(jì)算出錯(cuò),返回false。由此可見(jiàn)校驗(yàn)時(shí)完全用加減法和右移代替了delta碼中的除法,在保證安全性的前提下,降低了復(fù)雜度。

1.3 除法編碼算法

本文算法通過(guò)取模運(yùn)算將除法運(yùn)算轉(zhuǎn)化為乘法運(yùn)算，轉(zhuǎn)換為乘法運(yùn)算之后,具體的計(jì)算過(guò)程與乘法相同。為此,下面將引入逆元的概念,并介紹將除法轉(zhuǎn)化為乘法的過(guò)程。

對(duì)于正整數(shù)a、m,如果a*x≡1(modm),則把這個(gè)方程的最小正整數(shù)解x稱為a對(duì)于m的逆元,表示為x=inv(a)。如果m為素?cái)?shù),根據(jù)費(fèi)馬小定理計(jì)算出逆元,解為x=am-2(modm)。

獲得a對(duì)于m的逆元inv(a)后,則在計(jì)算(b/a)modm時(shí),可用inv(a)代替1/a,即只需要計(jì)算(b*inv(a))modm即可,這樣就把除法轉(zhuǎn)化成了乘法。

以除法運(yùn)算z=x/y為例,首先需要在計(jì)算時(shí)加入模運(yùn)算,即實(shí)際上計(jì)算(x/y)modm,m為一個(gè)大于x的素?cái)?shù),使得x/y必定小于m,從而(x/y)modm=x/y。

對(duì)于(x/y)modm,計(jì)算y對(duì)m的逆元,結(jié)果如式(15)所示:

inv(y)= ym-2(modm)

(15)

(x/y)modm=(x*inv(y))modm

(16)

經(jīng)過(guò)以上步驟,原本的除法運(yùn)算轉(zhuǎn)化成了乘法運(yùn)算,從而可通過(guò)delta碼乘法安全編碼的步驟來(lái)進(jìn)行編碼運(yùn)算。

2 改進(jìn)delta碼算法的安全性證明

2.1 安全性證明思路

由于本文提出的除法運(yùn)算最終轉(zhuǎn)換成乘法運(yùn)算來(lái)實(shí)現(xiàn),為證明安全性,只要證明乘法運(yùn)算的安全性。在推導(dǎo)過(guò)程中,假設(shè)所有錯(cuò)誤之間互相獨(dú)立且互斥。乘法運(yùn)算可能的錯(cuò)誤類(lèi)型包括以下三種:M、N不同時(shí)發(fā)生計(jì)算錯(cuò)誤;M、N同時(shí)發(fā)生計(jì)算錯(cuò)誤;操作數(shù)錯(cuò)誤。此處的編碼方式如1.2節(jié)所示,因此本節(jié)只給出數(shù)學(xué)推導(dǎo)過(guò)程。

2.2M與N不同時(shí)發(fā)生計(jì)算錯(cuò)誤的情況

以X1=x*A1運(yùn)算出錯(cuò)為例。這種運(yùn)算錯(cuò)誤具體表現(xiàn)為:X1=x*A1錯(cuò)誤運(yùn)算為X1=x*A1+p,出錯(cuò)時(shí)的編碼如式(17)所示：

(17)

X1出錯(cuò)將會(huì)導(dǎo)致M1、M2均運(yùn)算錯(cuò)誤,使實(shí)際計(jì)算結(jié)果在正確的結(jié)果基礎(chǔ)上分別加上p*y*A1、p*y*A2,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(18)所示：

(18)

由于M1、M2均運(yùn)算錯(cuò)誤,會(huì)導(dǎo)致V1、V2計(jì)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(19)所示：

(19)

正確性校驗(yàn)將對(duì)V1右移14位,對(duì)V2右移1位。對(duì)于V1、V2的前半部分,(x*y)*(A1+A2)右移14位與(x*y)*(A1-A2)右移1位的結(jié)果都是(x*y),二者必然相同。因此漏檢需要V1的后半部分右移14位與V2的后半部分右移1位的結(jié)果相同,即p*y=213*(p*y),解出p=0即不可能漏檢。

2.3M與N同時(shí)發(fā)生計(jì)算錯(cuò)誤的情況

以X1=x*A1和X2=x*A2同時(shí)運(yùn)算出錯(cuò)為例。運(yùn)算錯(cuò)誤具體表現(xiàn)為:X1=x*A1錯(cuò)誤運(yùn)算為X1=x*A1+p,以及Y1=y*A1錯(cuò)誤運(yùn)算為Y1=y*A1+q,p、q均不為0且獨(dú)立同分布,運(yùn)算出錯(cuò)時(shí)的編碼如式(20)所示：

(20)

X1、Y1出錯(cuò)將會(huì)導(dǎo)致M1、M2、N1均運(yùn)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(21)所示：

(21)

由于M1、N1運(yùn)算錯(cuò)誤,會(huì)導(dǎo)致V1、V2計(jì)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(22)所示：

(22)

正確性校驗(yàn)將對(duì)V1右移14位,對(duì)V2右移1位。對(duì)于V1、V2的前半部分,(x*y*A1)*(A1+A2)右移14位與(x*y*A1)*(A1-A2)右移1位的結(jié)果都是(x*y*A1),二者相同。因此漏檢需要p*y*A1+q*x*A1+(q*x*A2+pq)右移14位與p*y*A1+q*x*A1+(pq-q*x*A2)右移1位的結(jié)果相同,即p*y*A1+q*x*A1+(q*x*A2+pq)=213*(p*y*A1+q*x*A1+(pq-q*x*A2)),可解出對(duì)任一個(gè)p都有唯一解q使結(jié)果漏檢。假設(shè)q的二進(jìn)制表示由n位組成,在2n種錯(cuò)誤方式中只有一種會(huì)使結(jié)果漏檢,因此漏檢率為1/2n。

2.4 操作數(shù)錯(cuò)誤

只有一個(gè)操作數(shù)錯(cuò)誤時(shí),由2.2節(jié)可得不會(huì)漏檢。當(dāng)同時(shí)有兩個(gè)錯(cuò)誤存在時(shí),有兩種情況:

1)M與N操作數(shù)錯(cuò)誤:以M1=X1*Y1和N1=X2*Y1同時(shí)運(yùn)算出錯(cuò)為例。M1=X1*Y1操作數(shù)取錯(cuò)為M1=X1*p,以及N1=X2*Y1操作數(shù)取錯(cuò)為N1=X2*q,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(23)所示：

(23)

M1和N1出錯(cuò)將會(huì)導(dǎo)致V1和V2均運(yùn)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(24)所示：

(24)

正確性校驗(yàn)將對(duì)V1右移14位,對(duì)V2右移1位。漏檢需要x*A1*p+x*A2*q右移14位與x*A1*p-x*A2*q右移1位的結(jié)果相同,即x*A1*p+x*A2*q=213*(x*A1*p-x*A2*q),可解出對(duì)任一個(gè)p都有唯一解q使結(jié)果漏檢,因此漏檢率為1/2n。

2)X與Y操作數(shù)錯(cuò)誤:以Y1=y*A1和X2=x*A2運(yùn)算出錯(cuò)為例。這種運(yùn)算錯(cuò)誤具體表現(xiàn)為:Y1=y*A1操作數(shù)取錯(cuò)為Y1=q*A1,且q不等于y,以及X2=x*A2操作數(shù)取錯(cuò)為X2=p*A2,且p不等于x,出錯(cuò)時(shí)的編碼如式(25)所示：

(25)

X2、Y1出錯(cuò)將會(huì)導(dǎo)致M1、N1、N2均運(yùn)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(26)所示：

(26)

由于M1、M2均運(yùn)算錯(cuò)誤,會(huì)導(dǎo)致V3、V4計(jì)算錯(cuò)誤,出錯(cuò)時(shí)的運(yùn)算過(guò)程如式(27)所示：

(27)

正確性校驗(yàn)將對(duì)V3右移14位,對(duì)V4右移1位。對(duì)于V3、V4的前半部分,(x*y*A2)(A1+A2)右移14位與(x*y*A2)(A1-A2)右移1位的結(jié)果都是(x*y*A2),二者必然相同。因此漏檢需要V3、V4的后半部分,即(p-x)*y*A2*A2右移14位與右移1位的結(jié)果相同,解出p=0,即不可能漏檢。

在多種錯(cuò)誤情況中,只有M與N同時(shí)發(fā)生計(jì)算錯(cuò)誤或者M(jìn)與N操作數(shù)錯(cuò)誤時(shí)會(huì)出現(xiàn)漏檢,漏檢率為1/2n。當(dāng)N=32時(shí)可得漏檢率為2.3×10-10。

3 漏檢率及復(fù)雜度測(cè)試

3.1 實(shí)驗(yàn)?zāi)康暮铜h(huán)境

測(cè)試內(nèi)容包括漏檢率測(cè)試和復(fù)雜度測(cè)試。實(shí)現(xiàn)安全編碼C語(yǔ)言預(yù)編譯器,將沒(méi)有檢錯(cuò)能力的原始代碼轉(zhuǎn)換成具有檢錯(cuò)能力的代碼。實(shí)驗(yàn)的故障注入工具為IntelPin。IntelPin是Intel公司開(kāi)發(fā)的動(dòng)態(tài)二進(jìn)制插樁框架,提供了豐富的API,可在指令級(jí)別對(duì)程序進(jìn)行修改,達(dá)到故障注入的目的。

3.2 漏檢率測(cè)試

3.2.1 測(cè)試方案

使用的故障注入方案，是在IntelPin庫(kù)的基礎(chǔ)上設(shè)計(jì)了對(duì)應(yīng)故障類(lèi)型的故障注入插件(FaultInjectionTool,FIT),其中大量調(diào)用了Pin庫(kù)的API來(lái)實(shí)現(xiàn)動(dòng)態(tài)故障注入。根據(jù)故障注入類(lèi)型,分別開(kāi)發(fā)了對(duì)應(yīng)的代碼實(shí)現(xiàn)。

FIT能模擬的故障類(lèi)型和對(duì)應(yīng)的指令包括:

①WVAL:在寫(xiě)入內(nèi)存之前,值被修改為某個(gè)指定的值;②RVAL:內(nèi)存在被讀入時(shí),之前的值修改為某個(gè)指定的值;③WADDR:寫(xiě)值時(shí),寫(xiě)入到其他地址上;④RADDR:讀值時(shí),讀了錯(cuò)誤地址對(duì)應(yīng)到其他有效碼字的地址上;⑤RREG:寄存器在被讀入時(shí),之前的值修改為某個(gè)指定的值;⑥WREG:在寫(xiě)入寄存器之前,值被修改為某個(gè)指定的值。

在本次測(cè)試中通過(guò)注入①、②、⑤、⑥指令模擬操作數(shù)被修改錯(cuò)誤;通過(guò)注入④指令模擬操作數(shù)被調(diào)換錯(cuò)誤;通過(guò)注入④、⑤指令模擬操作符被調(diào)換錯(cuò)誤;通過(guò)注入④、⑤指令模擬運(yùn)算錯(cuò)誤錯(cuò)誤;通過(guò)注入③指令模擬未更新錯(cuò)誤:從而通過(guò)不同的指令對(duì)需要注入故障的測(cè)試用例進(jìn)行故障注入。注入寄存器故障的代碼如下。

staticVOIDinstrument_rreg(INSins,VOID*v) {insert_trigger(ins);INS_InsertThenCall(ins,IPOINT_BEFORE, (AFUNPTR)inject_reg,IARG_THREAD_ID,IARG_INST_PTR,IARG_CONTEXT,IARG_UINT32,INS_RegR(ins,r),IARG_END);

}

staticVOID

insert_trigger(INSins)

{switch(ttype) {caseRR:INS_InsertIfCall(ins,IPOINT_BEFORE, (AFUNPTR)find_rreg,IARG_INST_PTR,IARG_END);

break;

caseWR:INS_InsertIfCall(ins,IPOINT_BEFORE, (AFUNPTR)find_wreg,IARG_INST_PTR,IARG_END);

break;

default:DIE("FATAL:notimplemented");

}}

staticADDRINT

find_wreg(ADDRINTip)

//ip為指令地址

{returncounters.wreg}

//返回讀寄存器的次

受限于測(cè)試環(huán)境,本文在注入①～⑥的故障指令時(shí),限制對(duì)正確值的注入錯(cuò)誤范圍為32位中的6位,相當(dāng)于前文安全性證明中的漏檢率中的n值取為6。

3.2.2 測(cè)試結(jié)果及分析

運(yùn)算編碼檢錯(cuò)能力測(cè)試中,每次運(yùn)行中隨機(jī)注入錯(cuò)誤類(lèi)型中的一種,逐漸增加運(yùn)行次數(shù),根據(jù)總錯(cuò)誤數(shù)和檢測(cè)到的錯(cuò)誤數(shù)計(jì)算漏檢數(shù)和漏檢率。測(cè)試結(jié)果如表1所示。

由第2章證明可得,漏檢率在n取6的情況下理論上趨于1.5×10-2。由表1可知,當(dāng)運(yùn)行次數(shù)為10 000時(shí),10次實(shí)驗(yàn)的平均漏檢率趨于0.01,接近理論值1.5×10-2。可見(jiàn)編碼運(yùn)算的漏檢率基本符合理論值,且對(duì)比原delta碼的剩余錯(cuò)誤數(shù)有了改進(jìn)。在實(shí)際應(yīng)用中,可通過(guò)增大n值來(lái)使漏檢率達(dá)到預(yù)期的要求。

表1 10 000次運(yùn)算編碼檢錯(cuò)數(shù)據(jù)表

編碼程序檢錯(cuò)能力測(cè)試中,以四種程序?yàn)榛鶞?zhǔn)程序,分別是冒泡排序(Bubblesort,BS)、快速排序(Quicksort,QS)、矩陣乘法(Matrixmultiplication,MM)、斐波那契數(shù)列(FibonacciSequence,FS)。分別對(duì)安全編碼后的程序進(jìn)行故障植入,每個(gè)編碼后的程序執(zhí)行30 000次,每次執(zhí)行都隨機(jī)注入上述描述的錯(cuò)誤類(lèi)型。測(cè)試結(jié)果如表2所示。

編碼程序輸出結(jié)果錯(cuò)誤但未被檢測(cè)出來(lái)的百分比在1.6%左右。由于漏檢的錯(cuò)誤將會(huì)包括算術(shù)運(yùn)算錯(cuò)誤與少量控制流錯(cuò)誤,可見(jiàn)二者總的漏檢率基本符合理論值,實(shí)際算術(shù)運(yùn)算錯(cuò)誤漏檢率也基本符合理論值,且漏檢率低于原delta碼，從而進(jìn)一步證明了本安全編碼方法的檢錯(cuò)率符合預(yù)期。

表2 原delta編碼及改進(jìn)編碼30 000次故障注入測(cè)試結(jié)果 %

3.3 復(fù)雜度測(cè)試與仿真

3.3.1 測(cè)試方案

復(fù)雜度測(cè)試過(guò)程中,先要將未具有檢錯(cuò)能力的代碼轉(zhuǎn)化為具有檢錯(cuò)能力的代碼;其次選擇循環(huán)次數(shù),并對(duì)具有檢錯(cuò)能力的代碼進(jìn)行循環(huán)執(zhí)行;最后記錄循環(huán)執(zhí)行所用的時(shí)間,本文基于C語(yǔ)言,實(shí)現(xiàn)了對(duì)乘法、除法的編碼。分別記錄非編碼運(yùn)算和編碼運(yùn)算時(shí)間,并對(duì)測(cè)得的時(shí)間進(jìn)行比較。

3.3.2 測(cè)試結(jié)果及分析

本測(cè)試中所選的差異因子A1=5、A2=3。每種運(yùn)算運(yùn)行100次,記錄源程序的總運(yùn)行時(shí)間，結(jié)果如表3所示。從測(cè)試所得數(shù)據(jù)中可看出,編碼后運(yùn)算的執(zhí)行效率都有不同程度的降低。對(duì)于不同的運(yùn)算,因?yàn)榫幋a算法不同,增加的冗余操作的數(shù)目也有所不同,所以各自降低情況有所區(qū)別?？傮w復(fù)雜度對(duì)比原delta碼有所下降。

表3 各類(lèi)運(yùn)算執(zhí)行100次時(shí)間數(shù)據(jù)表

4 結(jié)語(yǔ)

本文在Kuvaiskii提出的delta安全編碼算法的基礎(chǔ)上,進(jìn)一步提出了采用雙目編碼的數(shù)據(jù)進(jìn)行運(yùn)算。在復(fù)雜度符合要求的基礎(chǔ)上,提高了算法的檢錯(cuò)率,并對(duì)算法安全性進(jìn)行了證明。實(shí)驗(yàn)和仿真結(jié)果表明:復(fù)雜度為未編碼運(yùn)算的6.4～7.2倍,比原delta碼降低了7%～19%，可應(yīng)用于實(shí)時(shí)性要求不是很高的場(chǎng)景。未來(lái)的工作將在本文的基礎(chǔ)上,在不降低檢錯(cuò)能力的前提下,對(duì)算法進(jìn)行復(fù)雜度優(yōu)化,以適用于實(shí)時(shí)性要求較高的場(chǎng)景。

)

[1]FORINP.Vitalcodedmicroprocessorprinciplesandapplicationforvarioustransitsystems[M]//PERRINJP.Control,Computers,CommunicationsinTransportation.NewYork:IFACPublications, 1990:79-84.

[2]SCHIFFELU.HardwareerrordetectionusingAN-codes[EB/OL]. [2016- 03- 10].https://core.ac.uk/download/pdf/35186697.pdf.

[3] 李剛, 丁佳, 梁盟磊, 等. 安全編碼預(yù)編譯器的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程, 2011, 37(3):230-232.(LIG,DINGJ,LIANGML,etal.Designandimplementationofvitalcodedpre-compile[J].ComputerEngineering, 2011, 37(3): 230-232.)

[4]KUVAISKIID,FETZERC.Δ-Encoding:practicalencodedprocessing[C]//Proceedingsofthe2015 45thAnnualIEEE/IFIPInternationalConferenceonDependableSystemsandNetworks.Piscataway,NJ:IEEE, 2015:13-24.

[5]SHIRVANIPP.Software-implementedhardwarefaulttoleranceexperiments:COTSinspace[EB/OL]. [2016- 03- 10].https://www.researchgate.net/profile/Philip_Shirvani/publication/238623000_Software-Implemented_Hardware_Fault_Tolerance_Experiments_COTS_in_Space/links/55de543508aeaa26af0f2589.pdf.

[6]KNIGHTJC.Safetycriticalsystems:challengesanddirections[C]//ICSE2002:Proceedingsofthe24thInternationalConferenceonSoftwareEngineering.Piscataway,NJ:IEEE, 2002: 547-550.

[7]SCHEICKL,GUERTINS,NGUYEND.InvestigationofthemechanismofstuckbitsinhighcapacitySDRAMs[C]//Proceedingsofthe2008IEEERadiationEffectsDataWorkshop.Piscataway,NJ:IEEE, 2008: 47-52.

[8]DUZELLIERS,FALGUERED,ECOFFETR.ProtonsandheavyionsinducedstuckbitsonlargecapacityRAMs[C]//RADECS1993:ProceedingsoftheSecondEuropeanConferenceonRadiationanditsEffectsonComponentsandSystems.Piscataway,NJ:IEEE, 1993: 468-472.

[9] CLARK J A, PRADHAN D K. Fault injection: a method for validating computer-system dependability[J]. Computer, 1995, 28(6): 47-56.

[10] RADHAKRISHNAN C, JENKINS W K. Reliable transform domain adaptive filters designed with a hybrid combination of redundant hardware modules and algorithmic error detection and correction [C]// Proceedings of the 2011 IEEE 54th International Midwest Symposium on Circuits and Systems. Piscataway, NJ: IEEE, 2011:1-4.

[11] CHANG J, REIS G A, AUGUST D I. Automatic instruction-level software-only recovery [C]// DSN 2006: Proceedings of the International Conference on Dependable Systems and Networks. Washington, DC: IEEE Computer Society, 2006: 83-92.

[12] BLOUGH D, SULLIVAN G, MASSON G. Intermittent fault diagnosis in multiprocessor systems [J]. IEEE Transactions on Computers, 1992, 41(11): 1430-1441.

[13] MAVIS D, EATON P. Soft error rate mitigation techniques for modern microcircuits [C]// Proceedings of the 40th Annual Reliability Physics Symposium. Piscataway, NJ: IEEE, 2002: 216-225.

[14] NICOLESCU B, SAVARIA Y, VELAZCO R. Software detection mechanisms providing full coverage against single bit-flip faults[J]. IEEE Transactions on Nuclear Science, 2004, 51(6):3510-3518.

This work is partially supported by the National Science and Technology Support Program (2015BAG13B01).

SUN Zongqi, born in 1992, M. S. candidate. His research interests include trusted computing.

ZANG Haijuan, born in 1965, Ph. D., associate professor. Her research interests include network security, information security.

ZHANG Chunhua, born 1989, Ph. D. candidate. Her research interests include information security, privacy protection.

PAN Yong, born in 1963, Ph. D., associate professor. His research interests include information security, trusted computing.

Improvedalgorithmformultiplicationanddivisionerrordetectionbasedondeltacode

SUNZongqi1,ZANGHaijuan2*,ZHANGChunhua1,PANYong1

(1.CollegeofElectronicsandInformationEngineering,TongjiUniversity,Shanghai201804,China;2.CollegeofComputerEngineering,JiangsuUniversityofTechnology,ChangzhouJiangsu213001,China)

In order to ensure the correctness of program execution in the safety critical system, the error control theory is used to encode the computer instructions, but the algorithm involves the modular operation, resulting in high additional complexity and difficulty to use in real-time systems. Aiming at reducing the additional complexity, delta code’s multiplication and division algorithm was improved. The idea of redundancy encoding and differentiated ideology was introduced to ensure security, while the inverse element was introduced into division to transform division into multiplication, thus avoiding the overhead of the modular operation and reducing the additional complexity while improving the security of the algorithm. Theoretical analysis shows that the undetected error rate is proved to be 2.3*10-10. Simulation results show that the undetected error rate of the proposed algorithm is consistent with the theoretical value, and the complexity is 6.4-7.2 times of the original algorithm, but 7%-19% lower than original delta code. The proposed algorithm satisfies the requirements of safety critical application systems in terms of error detection rate and complexity.

security code; data difference; error detection; security proof; inverse element

2016- 09- 22;

2016- 12- 27。 基金項(xiàng)目:國(guó)家科技支撐計(jì)劃項(xiàng)目(2015BAG13B01)。

孫宗奇(1992—),男,遼寧大連人,碩士研究生,主要研究方向:可信計(jì)算; 臧海娟(1965—),女,江蘇常州人,副教授,博士,主要研究方向:網(wǎng)絡(luò)安全、信息安全; 張春花(1989—),女,山東莒縣人,博士研究生,主要研究方向:信息安全、隱私保護(hù); 潘勇(1963—),男,浙江慈溪人,副教授,博士,主要研究方向:信息安全、可信計(jì)算。

1001- 9081(2017)04- 0975- 05

10.11772/j.issn.1001- 9081.2017.04.0975

TP

A