基于ANBD碼的按位運算可信算法研究

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

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

?

基于ANBD碼的按位運算可信算法研究

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

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

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

關鍵詞安全編碼算法硬件故障檢測位運算

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引言

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

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

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

1可驗證的位運算算法

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

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

X=Ax

(1)

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

X=Ax+Bx

(2)

(3) 添加時間標簽D。

X=Ax+Bx+D

(3)

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

X=[XH,XL]

(4)

XH=x

(5)

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

(6)

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

圖1按位與、或等運算編碼流程

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

1.1按位取反運算

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

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

按位取反編碼過程：

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

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

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

(7)

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

ZH=-1-XH

(8)

(2) 校驗域運算

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

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

1.2按位與運算

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

表1　8位段與運算表

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

Step1獲得預計算的數(shù)組：按順序存放兩個8位二進制數(shù)的按位與運算結果，其存放方式如式(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各位段進行與運算后得到的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整合得到按位與的計算結果。

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

(14)

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

2位運算轉換算法優(yōu)化

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

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

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

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

1) 8位段的轉換算法

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

x00=(x<<24)>>24

(15)

x01=(x00>>7)<<8

(16)

x02=x00-x01

(17)

2) 4位段的轉換算法

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

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

x000=(x<<28)>>28

(18)

x001=(x000>>3)<<4

(19)

x010=x000-x001

(20)

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

表2　8位段與4位段運行時間與空間的理論比較

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

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

3仿真與測試

3.1仿真與測試目的

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

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

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

3.2性能仿真與測試

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

表3　轉換算法運行時間結果

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

表4　轉換算法性能比較

3.3檢錯能力仿真與測試

3.3.1測試方案

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

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

圖2　故障注入測試方案

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

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

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

(21)

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

圖3　校驗流程

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

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

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

3.3.3測試結果與分析

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

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

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

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

4結語

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

參考文獻

[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] 李剛，丁佳，梁盟磊，等．安全編碼預編譯器的設計與實現(xiàn)[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]．同濟大學學報：自然科學版，2006，34(6)：823-827．

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

中圖分類號TP3

文獻標識碼A

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

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