李晨歡　薛小平　張　芳　潘　勇　賈建華

(同濟(jì)大學(xué)電子與信息工程學(xué)院　上海 201804)

?

基于ANBD碼的按位運(yùn)算可信算法研究

李晨歡薛小平張芳潘勇賈建華

(同濟(jì)大學(xué)電子與信息工程學(xué)院上海 201804)

摘要由于高安全系統(tǒng)中會使用到按位運(yùn)算，基于ANBD碼的安全編碼無法對按位運(yùn)算直接進(jìn)行編碼，所以會導(dǎo)致這些高安全系統(tǒng)無法通過安全編碼的方式保證該系統(tǒng)的安全完整性等級。針對這種情況，提出基于ANBD碼的按位運(yùn)算編碼轉(zhuǎn)換算法。算法首先將按位運(yùn)算等效地轉(zhuǎn)換為數(shù)組、加法、移位等可直接進(jìn)行安全編碼的運(yùn)算，然后對轉(zhuǎn)換后的運(yùn)算直接進(jìn)行安全編碼，最后得到的是基于ANBD碼的按位運(yùn)算編碼。實驗結(jié)果表明，優(yōu)化后的8位段按位運(yùn)算轉(zhuǎn)換算法能夠兼顧空間和時間上的開銷并且在安全性上能確保達(dá)到1/A的剩余錯誤率。

關(guān)鍵詞安全編碼算法硬件故障檢測位運(yùn)算

STUDY ON TRUSTED ALGORITHM OF BITWISE LOGICAL OPERATION BASED ON ANBD CODE

Li ChenhuanXue XiaopinZhang FangPan YongJia Jianhua

(College of Electronics and Information Engineering,Tongji University, Shanghai 201804,China)

AbstractSince in high-security system the bitwise logical operation will be used, but the ANBD code-based secure encoding cannot encode it directly, so this will result in these high-security systems cannot guarantee the safety integrity level by the means of secure encoding. In view of this, we propose an ANBD code-based conversion algorithm of bitwise logical operation. First, the algorithm converts the bitwise logical operation into array operation, addition operation and shift operation equivalently, those operations can run the secure encoding operation directly. Then, it directly makes secure encoding on the converted operations, and finally, what it obtains is the ANBD coded-based bitwise logical operation encoding. Experimental results show that the optimised conversion algorithm of bitwise logical operation with eight bits can take into account the overheads in both space and time, and in safety property it can ensure to reach the remaining error rate to 1/A.

KeywordsSecure encoding algorithmHardware failure detectionBit computation

0引言

安全苛求領(lǐng)域?qū)τ嬎愕恼_性要求越來越高。傳統(tǒng)的計算理論和方法，由于程序執(zhí)行過程中的各種錯誤可能會導(dǎo)致計算錯誤，如操作錯誤、運(yùn)算錯誤等[1]，為解決這一問題，在文獻(xiàn)[2]中Forin提出了一種基于算術(shù)碼的硬件錯誤檢測方法，采用冗余編碼技術(shù)來實時、在線檢測計算的正確性，有效地解決了加法、減法、控制流等方面的算法[3]，但傳統(tǒng)的安全編碼算法并不支持按位運(yùn)算[4]。

事實上，按位運(yùn)算在運(yùn)算過程中經(jīng)常會使用到，如基于位運(yùn)算的加密解密算法，如MD5算法[5]；ATP車載系統(tǒng)中，按位運(yùn)算能夠完成清零、置位等功能等等。

本文基于ANBD碼，實現(xiàn)了可進(jìn)行按按位運(yùn)算驗證的算法，基本思想是：將按位運(yùn)算等效地轉(zhuǎn)換為安全編碼直接支持的算術(shù)運(yùn)算，從而利用算術(shù)運(yùn)算的安全編碼算法來檢測出硬件在進(jìn)行按位運(yùn)算時的所發(fā)生的錯誤，使得安全編碼的范圍適用于按位運(yùn)算。

1可驗證的位運(yùn)算算法

為驗證運(yùn)算的正確性，傳統(tǒng)的方法以剩余碼和AN碼為基礎(chǔ)[6]，并加入了變量的簽名和變量的時間標(biāo)簽，通過運(yùn)算的結(jié)果來驗證各種運(yùn)算的正確性[7]。其過程主要包括：

(1) 構(gòu)造AN碼，A是隨機(jī)選擇的盡可能大的素數(shù)[8]，x是編碼前的編碼，X是編碼后的變量，如式(1)所示。

X=Ax

(1)

(2) 在AN碼基礎(chǔ)上添加簽名的屬性，如式(2)所示。

X=Ax+Bx

(2)

(3) 添加時間標(biāo)簽D。

X=Ax+Bx+D

(3)

其中簽名是計算編碼的重要組成部分，每個變量有唯一的簽名。變量的簽名可在離線計算時分配好的，并且作為運(yùn)算的校驗基準(zhǔn)。在校驗時，將校驗運(yùn)算得到的結(jié)果與校驗基礎(chǔ)進(jìn)行比較，若結(jié)果與校驗基礎(chǔ)相等(或同余)，則運(yùn)算正確，否則檢測到運(yùn)算錯誤。在對變量進(jìn)行編碼的時候采用了分離碼的形式，K為字長(一般取32或者64),如式(4)-式(6)所示：

X=[XH,XL]

(4)

XH=x

(5)

XL=(-(2Kx)%A+Bx)%A+D

(6)

但計算編碼算法無法直接對按位與、或、取反等運(yùn)算進(jìn)行編碼，本文提出采用等效的方法，即用可信計算編碼算法支持的運(yùn)算來等效上述位運(yùn)算。對這些位運(yùn)算進(jìn)行編碼時，將其轉(zhuǎn)換成一系列可編碼的運(yùn)算集合，包括：加法運(yùn)算、減法運(yùn)算、乘法運(yùn)算、除法運(yùn)算、移位運(yùn)算和數(shù)組運(yùn)算。將按位運(yùn)算在邏輯上轉(zhuǎn)化為相應(yīng)的可編碼運(yùn)算組合后，再對這些轉(zhuǎn)化后的運(yùn)算進(jìn)行編碼，最后等效為編碼后的按位運(yùn)算，其編碼基本流程如圖1所示。

圖1按位與、或等運(yùn)算編碼流程

按位運(yùn)算主要包括按位取反、按位或和按位和。事實上，按位取反的轉(zhuǎn)換算法是根據(jù)其本身的運(yùn)算特點(diǎn)推導(dǎo)而來的，且實現(xiàn)比較簡單；但按位與和按位或的轉(zhuǎn)換算法則較為復(fù)雜，不僅需要將按位運(yùn)算轉(zhuǎn)換為移位運(yùn)算和算術(shù)運(yùn)算的混合運(yùn)算，并且還要再將移位運(yùn)算轉(zhuǎn)換為編碼直接支持的算術(shù)運(yùn)算。顯然，按位與和按位或的安全編碼算法所導(dǎo)致的額外編碼開銷是十分嚴(yán)重的。本文進(jìn)一步提出在位段概念的基礎(chǔ)上，利用事先計算好的二維數(shù)組保存移位運(yùn)算的結(jié)果，通過空間復(fù)雜度換取時間復(fù)雜度的思想來降低按位與和按位或的編碼所導(dǎo)致的額外編碼開銷。

1.1按位取反運(yùn)算

按位取反運(yùn)算符“~”是一個單目運(yùn)算符，對一個二進(jìn)制數(shù)的每一位都取反，即0變?yōu)?，1變?yōu)?。

本節(jié)對z=~x按位取反運(yùn)算編碼進(jìn)行說明，其中x為變量，其編碼采用分離碼的形式，分別為XH和XL。

按位取反編碼過程：

(1) 數(shù)據(jù)域運(yùn)算

對32位整型的XH按位取反，等效于用32個“1”表示的數(shù)減去XH，其等效式如下所示。

~XH=(32個“1”表示的數(shù))-XH

(7)

對于32位有符號整型數(shù)，32個“1”表示的數(shù)是-1，就可用下式表示按位取反運(yùn)算，如式(8)所示。

ZH=-1-XH

(8)

(2) 校驗域運(yùn)算

由ZH=-1-XH知，按位取反實際上是減法運(yùn)算。校驗域根據(jù)按位取反轉(zhuǎn)化后的減法運(yùn)算進(jìn)行相應(yīng)計算。

對按位取反運(yùn)算進(jìn)行校驗時，利用提取的簽名與預(yù)編譯器預(yù)分配的簽名Bz進(jìn)行比較。若相等，則按位取反運(yùn)算正確；否則，檢測到運(yùn)算錯誤。

1.2按位與運(yùn)算

按位與、或、取反、異或運(yùn)算采用“分段查表”的方式，其思想是：參考C語言中“分段”的思想，以一個字節(jié)為分段單位，一個字節(jié)有256種可能，兩個字節(jié)進(jìn)行按位與運(yùn)算有256×256種可能，將這些結(jié)果事先放在一個二維數(shù)組table_and8[256][256]里，如表1所示。這樣每段的按位運(yùn)算轉(zhuǎn)換成查找A[256][256]即可獲得結(jié)果。對于兩個K位二進(jìn)制數(shù)進(jìn)行按位與運(yùn)算，首先將其按字節(jié)分段，然后對每一段進(jìn)行按位與運(yùn)算(即查表)，最后將各段結(jié)果整合在一起即可獲得最終結(jié)果。其校驗過程轉(zhuǎn)換成一系列數(shù)組、移位、加法等運(yùn)算的編碼校驗過程。

表1　8位段與運(yùn)算表

下面以與運(yùn)算z=x&y為例說明其編碼過程(x、y均為32位整型數(shù))：

Step1獲得預(yù)計算的數(shù)組：按順序存放兩個8位二進(jìn)制數(shù)的按位與運(yùn)算結(jié)果，其存放方式如式(9)所示。

staticinttable_and8[256][256]={0X00,0X01,0X02,…}

(9)

Step2將x,y分別按字節(jié)分段，各四段，每段8位，依次獲取x和y各段數(shù)據(jù)。獲取x各段數(shù)據(jù)信息，分別記為x02、x12、x22、x32(x02為低8位，x32為高8位)；獲取y各段的數(shù)據(jù)信息，分別記為y02、y12、y22、y32(y02為低8位，y32為高8位)。x和y數(shù)據(jù)信息的獲取方法相同。

Step3通過查表，獲取x和y各位段進(jìn)行與運(yùn)算后得到的z的各段數(shù)據(jù)。(z00為低8位，z03為高8位)

z00=table_and8[x02][y02]

(10)

z01=table_and8[x12][y12]

(11)

z02=table_and8[x22][y22]

(12)

z03=table_and8[x32][y32]

(13)

Step4整合得到按位與的計算結(jié)果。

z=(z03<<24)+(z02<<16)+(z01<<8)+(z00)

(14)

通過上述步驟，將按位與運(yùn)算的校驗過程轉(zhuǎn)換成一系列的對數(shù)組結(jié)果的移位、加法等運(yùn)算的編碼校驗過程。然后，分別對這些移位、加法等運(yùn)算進(jìn)行安全編碼，也就是間接實現(xiàn)了對按位與運(yùn)算的安全編碼。對按位與運(yùn)算進(jìn)行校驗時，利用提取的簽名與預(yù)編譯器預(yù)分配的簽名Bz進(jìn)行比較。若相等，則按位取反運(yùn)算正確；否則，檢測到運(yùn)算錯誤。

2位運(yùn)算轉(zhuǎn)換算法優(yōu)化

按位運(yùn)算轉(zhuǎn)換算法的核心思想就是分段和查表，其中查表運(yùn)算需要預(yù)先在內(nèi)存中存儲兩個8比特位的數(shù)的位運(yùn)算結(jié)果，對于一種類型的位運(yùn)算而言(例如按位與運(yùn)算)，則需在內(nèi)存中存儲256×256=65 536個數(shù)，會占用較大的內(nèi)存空間。因此本節(jié)的優(yōu)化主要針對空間上的優(yōu)化，并對優(yōu)化后的空間占用和運(yùn)行時間進(jìn)行分析測算。

2.1位段劃分優(yōu)化

轉(zhuǎn)換算法是將32位的整型數(shù)劃分為4個8比特位的數(shù)進(jìn)行運(yùn)算、整合的，需預(yù)先存儲256×256個數(shù)，其占用空間較大。為節(jié)省空間，將4個8比特位的整合改為8個4比特位的數(shù)進(jìn)行整合，亦即將x和y劃分8個4比特位的數(shù)，再通過查表得到這些4比特位的數(shù)進(jìn)行位運(yùn)算后的結(jié)果，最后將8個通過查表得到的4比特位的結(jié)果整合起來，得到最終32位整型數(shù)進(jìn)行按位與、或等位運(yùn)算的結(jié)果。

將8位段改為4位段后，查找的表的空間為16×16=256，相比于8位段的方案，空間節(jié)省了256倍。但是，與8位段的方法相比，4位段的轉(zhuǎn)換算法需要更多的步驟，下面對8位段和4位段的運(yùn)行步驟進(jìn)行理論分析。

1) 8位段的轉(zhuǎn)換算法

32位的x按8位來分段，可分成4段：x02、x12、x22、x32,獲取x每一段需經(jīng)歷3步運(yùn)算，如獲取低8位：

x00=(x<<24)>>24

(15)

x01=(x00>>7)<<8

(16)

x02=x00-x01

(17)

2) 4位段的轉(zhuǎn)換算法

32位的x按4位來分段，可分成8段：x010、x110、x210、x310、x410、x510、x610、x710(x010為低4位，x710為高4位)。

同理，獲取x每一段需經(jīng)歷3步運(yùn)算，如獲取低4位。

x000=(x<<28)>>28

(18)

x001=(x000>>3)<<4

(19)

x010=x000-x001

(20)

綜上，可得到8位段和4位段在理論上的運(yùn)行時間比較和空間占用情況的比較，如表2所示。其中，4位段方案的查表次數(shù)是8位段方案的兩倍，4位段方案的實現(xiàn)所需要的計算量為8位段方案的兩倍左右。

表2　8位段與4位段運(yùn)行時間與空間的理論比較

2.28位段空間優(yōu)化

4位段雖然能大大節(jié)省空間上的開銷，但相比于8位段，其理論運(yùn)行時間大幅增加。為兼顧運(yùn)行時間和空間，考慮對8位段的方案進(jìn)行空間優(yōu)化。觀察8位段按位與運(yùn)算編碼結(jié)果表1，發(fā)現(xiàn)該表對稱，即x&y的運(yùn)算結(jié)果與y&x的運(yùn)算結(jié)果相同。實際只需存儲表1的下三角區(qū)域，可節(jié)省一半存儲空間。由于表的數(shù)據(jù)存儲方式發(fā)生了改變，在8位段算法的查表過程亦需要作一些變動。

3仿真與測試

3.1仿真與測試目的

基于ANBD碼實現(xiàn)的硬件錯誤檢測技術(shù)應(yīng)用于實踐時，需要考慮的兩個因素分別是基于ANBD碼的安全編碼的檢錯能力和經(jīng)過安全編碼后犧牲的額外性能開銷。仿真與測試的具體目的如下：

(1) 仿真和測試按位運(yùn)算經(jīng)過安全編碼所生成的冗余轉(zhuǎn)換代碼所導(dǎo)致的性能開銷。為了滿足一定的錯誤檢測能力，需要將不可靠的源代碼轉(zhuǎn)換為可靠的冗余代碼，其中必須犧牲掉一些性能開銷，通過測試仿真來比較4位段、8位段和優(yōu)化后的8位段方案的性能開銷。在不同的硬件和應(yīng)用環(huán)境下，都有其特定的性能限制，比如內(nèi)存大小的限制和實時性要求的限制。因而，有必要分別對空間開銷和效率開銷進(jìn)行測試與比較。

(2) 通過仿真與測試來驗證按位運(yùn)算經(jīng)過上述方案編碼后的檢錯能力是否滿足理論值。Forin在理論上論證了基于ANBD碼的安全編碼的剩余錯誤率為1/P，但由于實際應(yīng)用復(fù)雜的環(huán)境，需要對編碼后的代碼進(jìn)驗證。

3.2性能仿真與測試

將8位段轉(zhuǎn)換算法、優(yōu)化的8位段轉(zhuǎn)換算法和4位段轉(zhuǎn)換算法的代碼經(jīng)過冗余編碼后，將其運(yùn)行500 000次，測試運(yùn)行時間，得表3所示。

表3　轉(zhuǎn)換算法運(yùn)行時間結(jié)果

如表4所示，分別對8位段未優(yōu)化、4位段未優(yōu)化和8位段優(yōu)化在時間復(fù)雜度、表占用空間大小、空間復(fù)雜度、查表次數(shù)等因素進(jìn)行比較。

表4　轉(zhuǎn)換算法性能比較

3.3檢錯能力仿真與測試

3.3.1測試方案

評價系統(tǒng)安全性的傳統(tǒng)方法是通過觀察系統(tǒng)的失效行為，進(jìn)而來分析錯誤記錄來完成的。對于一個高可靠系統(tǒng)而言，不可能通過長時間的觀察來統(tǒng)計結(jié)果。所以，本文采用故障注入的方式來模擬硬件出錯，從而來驗證按位運(yùn)算經(jīng)過安全編碼后的錯誤剩余率是否滿足理論值。

本文采用的是基于Linux系統(tǒng)中易于實現(xiàn)的軟件故障注入的方案[9，10]。該方案是基于Linux的vfork()函數(shù)調(diào)用來實現(xiàn)的，其調(diào)用格式為：pid_t vfork(void)。vfork()用于創(chuàng)建一個新進(jìn)程，但它并不將父進(jìn)程的地址空間完全復(fù)制到子進(jìn)程中。子進(jìn)程的目的是用來執(zhí)行新的程序，在其退出之前，它在父進(jìn)程的空間運(yùn)行，即它能夠共享父進(jìn)程的數(shù)據(jù)。vfork()函數(shù)調(diào)用時，創(chuàng)建的子進(jìn)程先運(yùn)行，父進(jìn)程被阻塞直到子進(jìn)程調(diào)用退出函數(shù)。在子進(jìn)程運(yùn)行的過程中，子進(jìn)程通過修改父進(jìn)程的數(shù)據(jù)來模擬硬件故障錯誤，包括：運(yùn)算錯誤、操作符錯誤和操作數(shù)錯誤，從而實現(xiàn)了故障注入。具體方案流程如圖2所示。

圖2　故障注入測試方案

圖2中子進(jìn)程注入故障的方式：通過在子進(jìn)程中將父進(jìn)程中計算的值修改成錯誤的值來模擬硬件錯誤導(dǎo)致的運(yùn)算錯誤、操作符錯誤和操作數(shù)錯誤。

校驗的方法：通過校驗運(yùn)算從編碼變量中獲得變量的校驗值(其中包含了變量的簽名)，然后將其與校驗基準(zhǔn)(離線分配的該變量的簽名狀態(tài))進(jìn)行直接比較。從校驗值中提取出該變量簽名的公式如下：

Z′sonlineSignature=(2KZH+ZL-D)%A

(21)

簽名提取是在線計算時進(jìn)行的，將計算得到的結(jié)果與離線計算的簽名進(jìn)行比較，同時比較過程也是在線計算的。校驗流程如圖3所示。

圖3　校驗流程

3.3.2測試環(huán)境與內(nèi)容

(1) 測試環(huán)境：操作系統(tǒng)為ubuntu 14.04.2 LTS、CPU為Pentium(R) Dual-Core CPU 2.6 GHz、內(nèi)存為2 GB、軟件工具為Gcc和G++;

(2) 測試內(nèi)容：測試單步按位與運(yùn)算經(jīng)過安全編碼后的檢錯能力是否滿足理論值。由于沒有復(fù)雜的控制流跳轉(zhuǎn)，對其注入的故障最容易通過變量碼字反映出來，因而便于統(tǒng)計注入的錯誤數(shù)和檢測到的錯誤數(shù)。其中測試的錯誤有運(yùn)算錯誤、操作符錯誤和操作數(shù)錯誤。

3.3.3測試結(jié)果與分析

由于便于編程，A選取的值為97。每次運(yùn)行中隨機(jī)注入上述三種錯誤的任意一種，并且逐漸增加運(yùn)行的次數(shù)，最后根據(jù)總錯誤數(shù)和檢測得到的錯誤數(shù)來計算剩余錯誤數(shù)和剩余錯誤率。具體測試結(jié)果如表5和圖4所示。

表5　按位與編碼運(yùn)算的檢錯數(shù)據(jù)表

圖4　剩余錯誤率與運(yùn)行次數(shù)關(guān)系

結(jié)果分析：對于測試中注入的各種錯誤，經(jīng)過編碼后的按位運(yùn)算能夠有效地檢測出來，并且滿足1/A的錯誤剩余率。本次測試中，A選取為97，也就是說理論上安全編碼后的代碼的錯誤剩余率約為0.01031。從表5中可以看出，當(dāng)運(yùn)行次數(shù)較大時，剩余錯誤率趨于0.01，可見按位于運(yùn)算的安全編碼的剩余錯誤率基本滿足理論值。

4結(jié)語

本文基于ANBD碼，通過將按位運(yùn)算轉(zhuǎn)化為數(shù)組、移位和加法運(yùn)算，使得按位運(yùn)算能夠間接地進(jìn)行安全編碼。實驗結(jié)果表明，4位段雖然能大大減小空間開銷，相比8位段的方案，其運(yùn)行時間大幅增加；經(jīng)過空間優(yōu)化的8位段轉(zhuǎn)換算法能夠減小部分空間開銷，且相比于未優(yōu)化的版本，其運(yùn)行時間增幅不大。因此，優(yōu)化的8位段轉(zhuǎn)換算法能夠兼顧空間和時間上的開銷，建議采用優(yōu)化的8位段方案。除了在性能上分析了按位運(yùn)算的安全編碼實現(xiàn)開銷，其次也分析了經(jīng)過安全編碼的按位運(yùn)算的安全性。通過實驗分析，經(jīng)過間接的安全編碼的按位運(yùn)算能夠滿足1/A的剩余錯誤率。

參考文獻(xiàn)

[1] 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]//Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium 2011.

[2] Forin P. Vital coded microprocessor principles and application for various transit systems[C]//IFA-GCCT, September 1989:79-84.

[3] The MathWorks. Code Verification and Run-Time Error Detection Through Abstract Interpretation[R].Technical report, The MathWorks,2012,7:1-10.

[4] Ute Schiel, Martin Sukraut, Christof Fetzer. AN-EncodingCompiler: Building Safety-Critical Systems with Commodity Hardware[C]//The 28th International Conference on Computer Safety,Reliability and Security,2009.

[5] Al Saud K A, Tahir M, Saleh M. Impact of MD5 Authentication on Routing Traffic for the Case of: EIGRP, RIPv2 and OSPF[J].Journal of Computer Science,2013，4(9):721-728.

[6] Hardware Error Detection Using AN-Codes (Ute Schiffel), PhD thesis[D] Technische Universit?t Dresden, 2011，6:1-258.

[7] 李剛，丁佳，梁盟磊，等．安全編碼預(yù)編譯器的設(shè)計與實現(xiàn)[J]．計算機(jī)工程，2011，37(3)：230-232.

[8] Sen B, Dutta M, Banik D, et al． Design of Fault Tolerant Reversible Arithmetic Logic Unit in QCA[C]//Electronic System Design (ISED), 2012 International Symposium, 2012:241-245.

[9] 江建慧，梁建華，靳昂，等．Linux上軟件實現(xiàn)的瞬時故障注入方案及實現(xiàn)[J]．同濟(jì)大學(xué)學(xué)報：自然科學(xué)版，2006，34(6)：823-827．

[10] 潘慶和. 軟件故障注入關(guān)鍵技術(shù)研究[D].哈爾濱工業(yè)大學(xué),2011.

中圖分類號TP3

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.061

收稿日期：2015-06-15。李晨歡，碩士，主研領(lǐng)域：可信計算。薛小平，教授。張芳，講師。潘勇，副教授。賈建華，副教授。