李晨欢　薛小平　张　芳　潘　勇　贾建华

(同济大学电子与信息工程学院　上海 201804)



基于ANBD码的按位运算可信算法研究

李晨欢薛小平张芳潘勇贾建华

(同济大学电子与信息工程学院上海 201804)

摘要由于高安全系统中会使用到按位运算，基于ANBD码的安全编码无法对按位运算直接进行编码，所以会导致这些高安全系统无法通过安全编码的方式保证该系统的安全完整性等级。针对这种情况，提出基于ANBD码的按位运算编码转换算法。算法首先将按位运算等效地转换为数组、加法、移位等可直接进行安全编码的运算，然后对转换后的运算直接进行安全编码，最后得到的是基于ANBD码的按位运算编码。实验结果表明，优化后的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引言

安全苛求领域对计算的正确性要求越来越高。传统的计算理论和方法，由于程序执行过程中的各种错误可能会导致计算错误，如操作错误、运算错误等[1]，为解决这一问题，在文献[2]中Forin提出了一种基于算术码的硬件错误检测方法，采用冗余编码技术来实时、在线检测计算的正确性，有效地解决了加法、减法、控制流等方面的算法[3]，但传统的安全编码算法并不支持按位运算[4]。

事实上，按位运算在运算过程中经常会使用到，如基于位运算的加密解密算法，如MD5算法[5]；ATP车载系统中，按位运算能够完成清零、置位等功能等等。

本文基于ANBD码，实现了可进行按按位运算验证的算法，基本思想是：将按位运算等效地转换为安全编码直接支持的算术运算，从而利用算术运算的安全编码算法来检测出硬件在进行按位运算时的所发生的错误，使得安全编码的范围适用于按位运算。

1可验证的位运算算法

为验证运算的正确性，传统的方法以剩余码和AN码为基础[6]，并加入了变量的签名和变量的时间标签，通过运算的结果来验证各种运算的正确性[7]。其过程主要包括：

(1) 构造AN码，A是随机选择的尽可能大的素数[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)

但计算编码算法无法直接对按位与、或、取反等运算进行编码，本文提出采用等效的方法，即用可信计算编码算法支持的运算来等效上述位运算。对这些位运算进行编码时，将其转换成一系列可编码的运算集合，包括：加法运算、减法运算、乘法运算、除法运算、移位运算和数组运算。将按位运算在逻辑上转化为相应的可编码运算组合后，再对这些转化后的运算进行编码，最后等效为编码后的按位运算，其编码基本流程如图1所示。

图1按位与、或等运算编码流程

按位运算主要包括按位取反、按位或和按位和。事实上，按位取反的转换算法是根据其本身的运算特点推导而来的，且实现比较简单；但按位与和按位或的转换算法则较为复杂，不仅需要将按位运算转换为移位运算和算术运算的混合运算，并且还要再将移位运算转换为编码直接支持的算术运算。显然，按位与和按位或的安全编码算法所导致的额外编码开销是十分严重的。本文进一步提出在位段概念的基础上，利用事先计算好的二维数组保存移位运算的结果，通过空间复杂度换取时间复杂度的思想来降低按位与和按位或的编码所导致的额外编码开销。

1.1按位取反运算

按位取反运算符“~”是一个单目运算符，对一个二进制数的每一位都取反，即0变为1，1变为0。

本节对z=~x按位取反运算编码进行说明，其中x为变量，其编码采用分离码的形式，分别为XH和XL。

按位取反编码过程：

(1) 数据域运算

对32位整型的XH按位取反，等效于用32个“1”表示的数减去XH，其等效式如下所示。

~XH=(32个“1”表示的数)-XH

(7)

对于32位有符号整型数，32个“1”表示的数是-1，就可用下式表示按位取反运算，如式(8)所示。

ZH=-1-XH

(8)

(2) 校验域运算

由ZH=-1-XH知，按位取反实际上是减法运算。校验域根据按位取反转化后的减法运算进行相应计算。

对按位取反运算进行校验时，利用提取的签名与预编译器预分配的签名Bz进行比较。若相等，则按位取反运算正确；否则，检测到运算错误。

1.2按位与运算

按位与、或、取反、异或运算采用“分段查表”的方式，其思想是：参考C语言中“分段”的思想，以一个字节为分段单位，一个字节有256种可能，两个字节进行按位与运算有256×256种可能，将这些结果事先放在一个二维数组table_and8[256][256]里，如表1所示。这样每段的按位运算转换成查找A[256][256]即可获得结果。对于两个K位二进制数进行按位与运算，首先将其按字节分段，然后对每一段进行按位与运算(即查表)，最后将各段结果整合在一起即可获得最终结果。其校验过程转换成一系列数组、移位、加法等运算的编码校验过程。

表1　8位段与运算表

下面以与运算z=x&y为例说明其编码过程(x、y均为32位整型数)：

Step1获得预计算的数组：按顺序存放两个8位二进制数的按位与运算结果，其存放方式如式(9)所示。

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

(9)

Step2将x,y分别按字节分段，各四段，每段8位，依次获取x和y各段数据。获取x各段数据信息，分别记为x02、x12、x22、x32(x02为低8位，x32为高8位)；获取y各段的数据信息，分别记为y02、y12、y22、y32(y02为低8位，y32为高8位)。x和y数据信息的获取方法相同。

Step3通过查表，获取x和y各位段进行与运算后得到的z的各段数据。(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)

通过上述步骤，将按位与运算的校验过程转换成一系列的对数组结果的移位、加法等运算的编码校验过程。然后，分别对这些移位、加法等运算进行安全编码，也就是间接实现了对按位与运算的安全编码。对按位与运算进行校验时，利用提取的签名与预编译器预分配的签名Bz进行比较。若相等，则按位取反运算正确；否则，检测到运算错误。

2位运算转换算法优化

按位运算转换算法的核心思想就是分段和查表，其中查表运算需要预先在内存中存储两个8比特位的数的位运算结果，对于一种类型的位运算而言(例如按位与运算)，则需在内存中存储256×256=65 536个数，会占用较大的内存空间。因此本节的优化主要针对空间上的优化，并对优化后的空间占用和运行时间进行分析测算。

2.1位段划分优化

转换算法是将32位的整型数划分为4个8比特位的数进行运算、整合的，需预先存储256×256个数，其占用空间较大。为节省空间，将4个8比特位的整合改为8个4比特位的数进行整合，亦即将x和y划分8个4比特位的数，再通过查表得到这些4比特位的数进行位运算后的结果，最后将8个通过查表得到的4比特位的结果整合起来，得到最终32位整型数进行按位与、或等位运算的结果。

将8位段改为4位段后，查找的表的空间为16×16=256，相比于8位段的方案，空间节省了256倍。但是，与8位段的方法相比，4位段的转换算法需要更多的步骤，下面对8位段和4位段的运行步骤进行理论分析。

1) 8位段的转换算法

32位的x按8位来分段，可分成4段：x02、x12、x22、x32,获取x每一段需经历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每一段需经历3步运算，如获取低4位。

x000=(x<<28)>>28

(18)

x001=(x000>>3)<<4

(19)

x010=x000-x001

(20)

综上，可得到8位段和4位段在理论上的运行时间比较和空间占用情况的比较，如表2所示。其中，4位段方案的查表次数是8位段方案的两倍，4位段方案的实现所需要的计算量为8位段方案的两倍左右。

表2　8位段与4位段运行时间与空间的理论比较

2.28位段空间优化

4位段虽然能大大节省空间上的开销，但相比于8位段，其理论运行时间大幅增加。为兼顾运行时间和空间，考虑对8位段的方案进行空间优化。观察8位段按位与运算编码结果表1，发现该表对称，即x&y的运算结果与y&x的运算结果相同。实际只需存储表1的下三角区域，可节省一半存储空间。由于表的数据存储方式发生了改变，在8位段算法的查表过程亦需要作一些变动。

3仿真与测试

3.1仿真与测试目的

基于ANBD码实现的硬件错误检测技术应用于实践时，需要考虑的两个因素分别是基于ANBD码的安全编码的检错能力和经过安全编码后牺牲的额外性能开销。仿真与测试的具体目的如下：

(1) 仿真和测试按位运算经过安全编码所生成的冗余转换代码所导致的性能开销。为了满足一定的错误检测能力，需要将不可靠的源代码转换为可靠的冗余代码，其中必须牺牲掉一些性能开销，通过测试仿真来比较4位段、8位段和优化后的8位段方案的性能开销。在不同的硬件和应用环境下，都有其特定的性能限制，比如内存大小的限制和实时性要求的限制。因而，有必要分别对空间开销和效率开销进行测试与比较。

(2) 通过仿真与测试来验证按位运算经过上述方案编码后的检错能力是否满足理论值。Forin在理论上论证了基于ANBD码的安全编码的剩余错误率为1/P，但由于实际应用复杂的环境，需要对编码后的代码进验证。

3.2性能仿真与测试

将8位段转换算法、优化的8位段转换算法和4位段转换算法的代码经过冗余编码后，将其运行500 000次，测试运行时间，得表3所示。

表3　转换算法运行时间结果

如表4所示，分别对8位段未优化、4位段未优化和8位段优化在时间复杂度、表占用空间大小、空间复杂度、查表次数等因素进行比较。

表4　转换算法性能比较

3.3检错能力仿真与测试

3.3.1测试方案

评价系统安全性的传统方法是通过观察系统的失效行为，进而来分析错误记录来完成的。对于一个高可靠系统而言，不可能通过长时间的观察来统计结果。所以，本文采用故障注入的方式来模拟硬件出错，从而来验证按位运算经过安全编码后的错误剩余率是否满足理论值。

本文采用的是基于Linux系统中易于实现的软件故障注入的方案[9，10]。该方案是基于Linux的vfork()函数调用来实现的，其调用格式为：pid_t vfork(void)。vfork()用于创建一个新进程，但它并不将父进程的地址空间完全复制到子进程中。子进程的目的是用来执行新的程序，在其退出之前，它在父进程的空间运行，即它能够共享父进程的数据。vfork()函数调用时，创建的子进程先运行，父进程被阻塞直到子进程调用退出函数。在子进程运行的过程中，子进程通过修改父进程的数据来模拟硬件故障错误，包括：运算错误、操作符错误和操作数错误，从而实现了故障注入。具体方案流程如图2所示。

图2　故障注入测试方案

图2中子进程注入故障的方式：通过在子进程中将父进程中计算的值修改成错误的值来模拟硬件错误导致的运算错误、操作符错误和操作数错误。

校验的方法：通过校验运算从编码变量中获得变量的校验值(其中包含了变量的签名)，然后将其与校验基准(离线分配的该变量的签名状态)进行直接比较。从校验值中提取出该变量签名的公式如下：

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

(21)

签名提取是在线计算时进行的，将计算得到的结果与离线计算的签名进行比较，同时比较过程也是在线计算的。校验流程如图3所示。

图3　校验流程

3.3.2测试环境与内容

(1) 测试环境：操作系统为ubuntu 14.04.2 LTS、CPU为Pentium(R) Dual-Core CPU 2.6 GHz、内存为2 GB、软件工具为Gcc和G++;

(2) 测试内容：测试单步按位与运算经过安全编码后的检错能力是否满足理论值。由于没有复杂的控制流跳转，对其注入的故障最容易通过变量码字反映出来，因而便于统计注入的错误数和检测到的错误数。其中测试的错误有运算错误、操作符错误和操作数错误。

3.3.3测试结果与分析

由于便于编程，A选取的值为97。每次运行中随机注入上述三种错误的任意一种，并且逐渐增加运行的次数，最后根据总错误数和检测得到的错误数来计算剩余错误数和剩余错误率。具体测试结果如表5和图4所示。

表5　按位与编码运算的检错数据表

图4　剩余错误率与运行次数关系

结果分析：对于测试中注入的各种错误，经过编码后的按位运算能够有效地检测出来，并且满足1/A的错误剩余率。本次测试中，A选取为97，也就是说理论上安全编码后的代码的错误剩余率约为0.01031。从表5中可以看出，当运行次数较大时，剩余错误率趋于0.01，可见按位于运算的安全编码的剩余错误率基本满足理论值。

4结语

本文基于ANBD码，通过将按位运算转化为数组、移位和加法运算，使得按位运算能够间接地进行安全编码。实验结果表明，4位段虽然能大大减小空间开销，相比8位段的方案，其运行时间大幅增加；经过空间优化的8位段转换算法能够减小部分空间开销，且相比于未优化的版本，其运行时间增幅不大。因此，优化的8位段转换算法能够兼顾空间和时间上的开销，建议采用优化的8位段方案。除了在性能上分析了按位运算的安全编码实现开销，其次也分析了经过安全编码的按位运算的安全性。通过实验分析，经过间接的安全编码的按位运算能够满足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] 李刚，丁佳，梁盟磊，等．安全编码预编译器的设计与实现[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上软件实现的瞬时故障注入方案及实现[J]．同济大学学报：自然科学版，2006，34(6)：823-827．

[10] 潘庆和. 软件故障注入关键技术研究[D].哈尔滨工业大学,2011.

中图分类号TP3

文献标识码A

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

收稿日期：2015-06-15。李晨欢，硕士，主研领域：可信计算。薛小平，教授。张芳，讲师。潘勇，副教授。贾建华，副教授。