基于delta碼的乘除法運算錯誤檢測改進算法

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

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

基于delta碼的乘除法運算錯誤檢測改進算法

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

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

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

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

0 引言

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

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

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

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

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

1 delta碼乘除法改進算法

1.1 原delta碼乘除法算法及改進

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

(1)

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

運算過程分別由X1、X2相加、相減并右移計算出T1、T2。如果計算無誤,則T1、T2的值均應當?shù)扔?x。

(2)

T1、Y1相乘得到K1,T2、Y2相乘得到K2,如果計算無誤,則相當于x直接與Y1、Y2相乘。

(3)

得到K1、K2后進行解碼過程,分別令其對A1、A2做除法運算,得到計算結果Z1、Z2,如果計算無誤,則Z1、Z2均應當?shù)扔趚*y,如果Z1、Z2的結果相同,視為計算正確;否則視為計算錯誤,返回false。

(4)

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

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

1.2 乘法編碼算法

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

(5)

算法分兩部分：

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

(6)

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

(7)

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

(8)

以乘法運算z=x*y為例,所有運算不出錯時,第一部分計算過程如式(9)所示:

(9)

此處進行第一次安全性校驗,檢驗(S1==S2)==true是否成立,如果計算無誤,則S1、S2的值的應當相同；如果S1、S2的結果不同,則說明存在計算錯誤,返回false。

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

(10)

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

(11)

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

(12)

所有運算不出錯時,第二部分計算過程如式(13)所示:

(13)

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

算法中的第三次安全性校驗,對S1、S3的和右移14位,對S2、S4的差右移一位。

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

(14)

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

1.3 除法編碼算法

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

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

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

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

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

inv(y)= ym-2(modm)

(15)

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

(16)

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

2 改進delta碼算法的安全性證明

2.1 安全性證明思路

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

2.2M與N不同時發(fā)生計算錯誤的情況

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

(17)

X1出錯將會導致M1、M2均運算錯誤,使實際計算結果在正確的結果基礎上分別加上p*y*A1、p*y*A2,出錯時的運算過程如式(18)所示：

(18)

由于M1、M2均運算錯誤,會導致V1、V2計算錯誤,出錯時的運算過程如式(19)所示：

(19)

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

2.3M與N同時發(fā)生計算錯誤的情況

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

(20)

X1、Y1出錯將會導致M1、M2、N1均運算錯誤,出錯時的運算過程如式(21)所示：

(21)

由于M1、N1運算錯誤,會導致V1、V2計算錯誤,出錯時的運算過程如式(22)所示：

(22)

正確性校驗將對V1右移14位,對V2右移1位。對于V1、V2的前半部分,(x*y*A1)*(A1+A2)右移14位與(x*y*A1)*(A1-A2)右移1位的結果都是(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位的結果相同,即p*y*A1+q*x*A1+(q*x*A2+pq)=213*(p*y*A1+q*x*A1+(pq-q*x*A2)),可解出對任一個p都有唯一解q使結果漏檢。假設q的二進制表示由n位組成,在2n種錯誤方式中只有一種會使結果漏檢,因此漏檢率為1/2n。

2.4 操作數(shù)錯誤

只有一個操作數(shù)錯誤時,由2.2節(jié)可得不會漏檢。當同時有兩個錯誤存在時,有兩種情況:

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

(23)

M1和N1出錯將會導致V1和V2均運算錯誤,出錯時的運算過程如式(24)所示：

(24)

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

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

(25)

X2、Y1出錯將會導致M1、N1、N2均運算錯誤,出錯時的運算過程如式(26)所示：

(26)

由于M1、M2均運算錯誤,會導致V3、V4計算錯誤,出錯時的運算過程如式(27)所示：

(27)

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

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

3 漏檢率及復雜度測試

3.1 實驗目的和環(huán)境

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

3.2 漏檢率測試

3.2.1 測試方案

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

FIT能模擬的故障類型和對應的指令包括:

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

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

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}

//返回讀寄存器的次

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

3.2.2 測試結果及分析

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

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

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

編碼程序檢錯能力測試中,以四種程序為基準程序,分別是冒泡排序(Bubblesort,BS)、快速排序(Quicksort,QS)、矩陣乘法(Matrixmultiplication,MM)、斐波那契數(shù)列(FibonacciSequence,FS)。分別對安全編碼后的程序進行故障植入,每個編碼后的程序執(zhí)行30 000次,每次執(zhí)行都隨機注入上述描述的錯誤類型。測試結果如表2所示。

編碼程序輸出結果錯誤但未被檢測出來的百分比在1.6%左右。由于漏檢的錯誤將會包括算術運算錯誤與少量控制流錯誤,可見二者總的漏檢率基本符合理論值,實際算術運算錯誤漏檢率也基本符合理論值,且漏檢率低于原delta碼，從而進一步證明了本安全編碼方法的檢錯率符合預期。

表2 原delta編碼及改進編碼30 000次故障注入測試結果 %

3.3 復雜度測試與仿真

3.3.1 測試方案

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

3.3.2 測試結果及分析

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

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

4 結語

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

)

[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] 李剛, 丁佳, 梁盟磊, 等. 安全編碼預編譯器的設計與實現(xiàn)[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。 基金項目:國家科技支撐計劃項目(2015BAG13B01)。

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

1001- 9081(2017)04- 0975- 05

10.11772/j.issn.1001- 9081.2017.04.0975

TP

A