计算机应用   2017, Vol. 37 Issue (4): 975-979  DOI: 10.11772/j.issn.1001-9081.2017.04.0975
0

引用本文 

孙宗奇, 臧海娟, 张春花, 潘勇. 基于delta码的乘除法运算错误检测改进算法[J]. 计算机应用, 2017, 37(4): 975-979.DOI: 10.11772/j.issn.1001-9081.2017.04.0975.
SUN Zongqi, ZANG Haijuan, ZHANG Chunhua, PAN Yong. Improved algorithm for multiplication and division error detection based on delta code[J]. Journal of Computer Applications, 2017, 37(4): 975-979. DOI: 10.11772/j.issn.1001-9081.2017.04.0975.

基金项目

国家科技支撑计划项目(2015BAG13B01)

通讯作者

臧海娟 (1965-), 女, 江苏常州人, 副教授, 博士, 主要研究方向:网络安全、信息安全, E-mail: zhjuan@qq.com

作者简介

孙宗奇 (1992-), 男, 辽宁大连人, 硕士研究生, 主要研究方向:可信计算;
张春花 (1989-), 女, 山东莒县人, 博士研究生, 主要研究方向:信息安全、隐私保护;
潘勇 (1963-), 男, 浙江慈溪人, 副教授, 博士, 主要研究方向:信息安全、可信计算

文章历史

收稿日期:2016-09-22
修回日期:2016-12-27
基于delta码的乘除法运算错误检测改进算法
孙宗奇1, 臧海娟2, 张春花1, 潘勇1    
1. 同济大学 电子与信息工程学院, 上海 201804;
2. 江苏理工学院 计算机工程学院, 江苏 常州 213001
摘要: 为确保安全苛求系统中程序执行的正确性,研究人员将差错控制理论用于对计算机指令进行编码,但由于编码大多涉及模运算,导致复杂度大量增加,应用于实时系统有困难。针对复杂度问题对delta码的乘除法运算算法进行改进。算法在乘法运算中引入冗余编码及差异化思想,从而确保安全性;在除法运算中引入逆元,将除法运算转化为低复杂度的乘法运算,避免了模运算带来的开销,降低了复杂度并提高了算法安全性,并对安全性进行理论论证。理论分析表明:所提算法漏检率可达2.3×10-10。测试结果表明,所提算法的漏检率与理论值相符,且复杂度是未编码运算6.4~7.2倍,比原delta码降低了7%~19%,在漏检率与复杂度方面均满足安全苛求系统的应用要求。
关键词: 安全编码    数据差异化    错误检测    安全性    逆元    
Improved algorithm for multiplication and division error detection based on delta code
SUN Zongqi1, ZANG Haijuan2, ZHANG Chunhua1, PAN Yong1     
1. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China;
2. College of Computer Engineering, Jiangsu University of Technology, Changzhou Jiangsu 213001, China
Abstract: 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.
Key words: security code    data difference    error detection    security proof    inverse element    
0 引言

随着计算机在安全苛求领域里的广泛应用, 计算系统的安全性已经成为研究机构关注的热点问题。但计算系统受到气候、电磁、辐射和力学等环境因素的影响, 如强电磁干扰、恶劣的散热条件、低温环境、长期振动等因素, 都可能造成处理器失效、比特翻转等状况, 导致计算错误。这种错误随机性使系统安全存在着很大隐患。

针对这些问题, 自20世纪70年代末, 研究人员就开始研究利用编码技术来保障计算安全的理论和方法, 称为安全编码理论。Forin[1]提出了基于算术码的运算正确性检测方法。该方法将冗余编码应用到对计算机的各类运算进行编码过程中, 通过对指令层面进行编码运算来检测计算过程中的错误, 并简要地给出了典型指令, 如加法、减法、控制流方面的编码思路。Schiffel[2]基于Forin提出的方法上分别对四则运算、逻辑运算、位运算进行了算术码编码, 并对复杂度进行了测试。但由于文献[2]算法中运用了模运算, 李刚等[3]总结了其算术运算复杂度会因此增加20倍以上, 应用于实时系统有困难。

为将检测计算错误的方法有效地应用到实时的安全苛求系统, 需对这些编码方式进行优化, 且从理论上对该算法进行安全性分析, 使其编码后产生的开销减少到实时安全苛求系统能接受的范围, 保障该系统的安全性和可靠性。

Kuvaiskii等[4]提出了基于AN码 (arithmetic-code, AN code) 和重复指令的delta码 (Δ-Encoding), 通过对AN码系数的差异化取值, 在安全性验证过程中使用右移运算代替模运算, 简化了解码过程, 降低了复杂度, 使其仅增加6~10倍。但delta码对于乘除法运算, 均采用单目编码, 即由编码数据和未编码数据混合运算, 通过理论证明得出, 单目编码安全性对比双目编码有所下降;且算法返回值是预期结果的AN编码, 结果校验时还要加入AN码解码过程, 并引入了额外的除法运算, 导致了复杂度增加。

本文对delta码乘除法编码方案进行改进, 改进后的乘除法的算法, 将单目编码改进为双目编码, 即计算时对所有操作数均进行编码, 使安全性验证过程中只包含加减法运算及右移运算, 消除了结果校验时额外的除法运算部分, 降低了复杂度; 并对所改进的算法安全性进行理论证明, 计算出本文算法漏检率达到2.3×10-10, 低于delta码漏检率。本文通过Pin库注入故障进行检错率与复杂度测试实验, 验证了本文算法的漏检率与理论值相符, 且复杂度增加7倍左右。

1 delta码乘除法改进算法 1.1 原delta码乘除法算法及改进

以乘法运算为例进行说明, delta码对操作数进行两次AN编码, AN码的编码方式为:进行校验时, 若编码数据X能被A整除则运算正确;否则运算错误。delta码乘法运算的具体编码方式如式 (1) 所示:

$ \left\{ \begin{array}{l} {X_1} = x*{A_1};{X_2} = x*{A_2}\\ {Y_1} = y*{A_1};{Y_2} = y*{A_2} \end{array} \right. $ (1)

两次AN编码的系数分别为A1A2, delta码对A1A2差异化取值为:A1=213+1,A2=213-1, 使A1+A2=214, 因此包含A1+A2的部分可用右移14位代替除法运算, 对A1-A2=21可用右移1位代替除法运算, 从而省去了除法运算, 降低了复杂度。delta码算法应用于32位系统中。A1A2取在213周围时, 16位的操作数, 在解码时右移14位后, 不会超过32位, 不会造成溢出。

运算过程分别由X1X2相加、相减并右移计算出T1T2。如果计算无误, 则T1T2的值均应当等于x

$ \left\{ \begin{array}{l} {T_1} = ({X_1} + {X_2}) \gg 14\\ {T_2} = ({X_1} - {X_2}) \ll 1 \end{array} \right. $ (2)

T1Y1相乘得到K1, T2Y2相乘得到K2, 如果计算无误, 则相当于x直接与Y1Y2相乘。

$ \left\{ \begin{array}{l} {K_1} = {T_1}*{Y_1}\\ {K_2} = {T_2}*{Y_2} \end{array} \right. $ (3)

得到K1K2后进行解码过程, 分别令其对A1A2做除法运算, 得到计算结果Z1Z2, 如果计算无误, 则Z1Z2均应当等于x*y, 如果Z1Z2的结果相同, 视为计算正确; 否则视为计算错误, 返回false。

$ \left\{ \begin{array}{l} {Z_1}{\rm{ = }}{M_1}/{A_1}\\ {Z_2} = {M_2}/{A_2} \end{array} \right. $ (4)

式 (3) 相当于只进行了单目编码, 即两个操作数中只有Y是编码的, 而X是不编码的。文献[4]提出使用单目编码的delta码的理论漏检率为1/(A1*A2), 最小漏检率约为3.7×10-9, 高于本改进双目编码算法的理论漏检率。原delta码中由于返回值是z的AN编码, 因此在得到计算结果z之前还需要对返回值Z1Z2进行AN码解码, 即需要对其进行除法运算, 增加了AN码的复杂度。

本文改进了delta码乘法、除法的算法, 对delta码进行双目编码。在不改变A1A2取值的基础上, 使计算与检错完全使用编码后的操作数进行, 实现了编码数据参与运算, 且省去了delta码中的模运算过程, 降低了delta码的复杂度。

1.2 乘法编码算法

本文算法对原delta码进行改进, 将单目编码改进为双目编码, 即完全通过操作数编码后的数据进行计算。X1X2Y1Y2xy分别以A1A2为系数进行AN编码后的编码数据, A1A2的取值与delta码相同。具体编码如式 (5) 所示:

$ \left\{ \begin{array}{l} {X_1} = x*{A_1}\\ {X_2} = x*{A_2}\\ {Y_1} = y*{A_1}\\ {Y_2} = y*{A_2} \end{array} \right. $ (5)

算法分两部分:

第一部分由X1Y1相乘得到M1, X2Y1相乘得到N1, 具体编码如式 (6) 所示:

$ \left\{ \begin{array}{l} {M_1} = {X_1}*{Y_1}\\ {N_1} = {X_2}*{Y_1} \end{array} \right. $ (6)

M1N1计算出V1V2, 具体过程如式 (7) 所示:

$ \left\{ \begin{array}{l} {V_1} = {M_1} + {N_1}\\ {V_2} = {M_1} - {N_1} \end{array} \right. $ (7)

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

$ \left\{ \begin{array}{l} {S_1} = {V_1} \gg 14\\ {S_2} = {V_2} \gg 1 \end{array} \right. $ (8)

以乘法运算z=x*y为例, 所有运算不出错时, 第一部分计算过程如式 (9) 所示:

$ \left\{ \begin{array}{l} {M_1} = x{\rm{*}}y{\rm{*}}{A_1}*{A_1}\\ {N_1} = x{\rm{*}}y{\rm{*}}{A_1}*{A_2}\\ {V_1} = (x*y{\rm{*}}{A_1})*({A_1} + {A_2}) = (x*y{\rm{*}}{A_1})*{2^{14}}\\ {V_2} = (x*y{\rm{*}}{A_1})*({A_1} - {A_2}) = (x*y{\rm{*}}{A_1})*{2^1}\\ {S_1} = x*y{\rm{*}}{A_1}\\ {S_2} = x*y{\rm{*}}{A_1} \end{array} \right. $ (9)

此处进行第一次安全性校验, 检验 (S1= =S2)== true是否成立, 如果计算无误, 则S1S2的值的应当相同;如果S1S2的结果不同, 则说明存在计算错误, 返回false。

第二部分由X1Y2相乘得到M2, X2Y2相乘得到N2, 具体编码如式 (10) 所示:

$ \left\{ \begin{array}{l} {M_2} = {X_1}*{Y_2}\\ {N_2} = {X_2}*{Y_2} \end{array} \right. $ (10)

M2N2计算出V3V4, 具体过程如式 (11) 所示:

$ \left\{ \begin{array}{l} {V_3} = {M_2} + {N_2}\\ {V_4} = {M_2} - {N_2} \end{array} \right. $ (11)

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

$ \left\{ \begin{array}{l} {S_3} = {V_3} \gg 14\\ {S_4} = {V_4} \gg 1 \end{array} \right. $ (12)

所有运算不出错时, 第二部分计算过程如式 (13) 所示:

$ \left\{ \begin{array}{l} {M_2} = x{\rm{*}}y{\rm{*}}{A_2}*{A_1}\\ {N_2} = x{\rm{*}}y{\rm{*}}{A_2}*{A_2}\\ {V_3} = (x*y{\rm{*}}{A_2})*({A_1} + {A_2}) = (x*y{\rm{*}}{A_2})*{2^{14}}\\ {V_4} = (x*y{\rm{*}}{A_2})*({A_1} - {A_2}) = (x*y{\rm{*}}{A_2})*{2^1}\\ {S_3} = x*y{\rm{*}}{A_2}\\ {S_4} = x*y{\rm{*}}{A_2} \end{array} \right. $ (13)

此处进行第二次安全性校验, 检验S3= =S4是否为true, 若计算正确, 则S3S4的值相同;若S3S4的结果不同, 则表明计算错误, 返回false。

算法中的第三次安全性校验, 对S1S3的和右移14位, 对S2S4的差右移一位。

$ \left\{ \begin{array}{l} \left( {{S_1}{\rm{ + }}{S_3}} \right) \gg 14\\ \left( {{S_2} - {S_4}} \right) \gg 1 \end{array} \right. $ (14)

若计算正确, 右移的结果均等于x*y;若两次右移结果不同, 则表明计算出错, 返回false。由此可见校验时完全用加减法和右移代替了delta码中的除法, 在保证安全性的前提下, 降低了复杂度。

1.3 除法编码算法

本文算法通过取模运算将除法运算转化为乘法运算,转换为乘法运算之后, 具体的计算过程与乘法相同。为此, 下面将引入逆元的概念, 并介绍将除法转化为乘法的过程。

对于正整数am, 如果a*x≡1(mod m), 则把这个方程的最小正整数解x称为a对于m的逆元, 表示为x=inv (a)。如果m为素数, 根据费马小定理计算出逆元, 解为x=am-2(mod m)。

获得a对于m的逆元inv (a) 后, 则在计算 (b/a) mod m时, 可用inv (a) 代替1/a, 即只需要计算 (b*inv (a)) mod m即可, 这样就把除法转化成了乘法。

以除法运算z=x/y为例, 首先需要在计算时加入模运算, 即实际上计算 (x/y) mod m, m为一个大于x的素数, 使得x/y必定小于m, 从而 (x/y) mod m=x/y

对于 (x/y) mod m, 计算ym的逆元, 结果如式 (15) 所示:

$ {\rm{inv(}}y{\rm{) = }}{y^{m{\rm{ - 2}}}}{\rm{(mod }}m{\rm{)}} $ (15)

之后把 (x/y) mod m转换为乘法, 结果如式 (16) 所示:

$(x/y)\,\bmod \,m{\rm{ = }}(x{\rm{*inv}}(y))\,\bmod \,m$ (16)

经过以上步骤, 原本的除法运算转化成了乘法运算, 从而可通过delta码乘法安全编码的步骤来进行编码运算。

2 改进delta码算法的安全性证明 2.1 安全性证明思路

由于本文提出的除法运算最终转换成乘法运算来实现, 为证明安全性, 只要证明乘法运算的安全性。在推导过程中, 假设所有错误之间互相独立且互斥。乘法运算可能的错误类型包括以下三种:MN不同时发生计算错误; MN同时发生计算错误; 操作数错误。此处的编码方式如1.2节所示, 因此本节只给出数学推导过程。

2.2 MN不同时发生计算错误的情况

X1=x*A1运算出错为例。这种运算错误具体表现为:X1=x*A1错误运算为X1=x*A1+p, 出错时的编码如式 (17) 所示:

$ \left\{ \begin{array}{l} {X_1} = x*{A_1} + p\\ {X_2} = x*{A_2}\\ {Y_1} = y*{A_1}\\ {Y_2} = y*{A_2} \end{array} \right. $ (17)

X1出错将会导致M1M2均运算错误, 使实际计算结果在正确的结果基础上分别加上p*y*A1p*y*A2, 出错时的运算过程如式 (18) 所示:

$ \left\{ \begin{array}{l} {M_1} = (x{\rm{*}}y)*{A_1}*{A_1} + p*y*{A_1}\\ {M_2} = (x{\rm{*}}y)*{A_1}*{A_2} + p*y*{A_2} \end{array} \right. $ (18)

由于M1M2均运算错误, 会导致V1V2计算错误, 出错时的运算过程如式 (19) 所示:

$ \left\{ \begin{array}{l} {V_1} = (x*y*{A_1})*({A_1} + {A_2}) + p*y*{A_1} = \\ \;\;\;\;\;\;\;(x*y)*{2^{14}} + p*y*{A_1}\\ {V_2} = (x*y*{A_1})*({A_1} - {A_2}) + p*y*{A_1} = \\ \;\;\;\;\;\;\;(x*y)*{2^1} + p*y*{A_1} \end{array} \right. $ (19)

正确性校验将对V1右移14位, 对V2右移1位。对于V1V2的前半部分, (x*y)*(A1+A2) 右移14位与 (x*y)*(A1-A2) 右移1位的结果都是 (x*y), 二者必然相同。因此漏检需要V1的后半部分右移14位与V2的后半部分右移1位的结果相同, 即p*y=213*(p*y), 解出p=0即不可能漏检。

2.3 MN同时发生计算错误的情况

X1=x*A1X2=x*A2同时运算出错为例。运算错误具体表现为:X1=x*A1错误运算为X1=x*A1+p, 以及Y1= y*A1错误运算为Y1= y*A1+q, pq均不为0且独立同分布, 运算出错时的编码如式 (20) 所示:

$ \left\{ \begin{array}{l} {X_1} = x*{A_1} + p\\ {X_2} = x*{A_2}\\ {Y_1} = y*{A_1} + q\\ {Y_2} = y*{A_2} \end{array} \right. $ (20)

X1Y1出错将会导致M1M2N1均运算错误, 出错时的运算过程如式 (21) 所示:

$ \left\{ \begin{array}{l} {M_1} = (x*y)*{A_1}*{A_1} + p*y*{A_1} + q*x*{A_1} + pq\\ {N_1} = (x*y)*{A_2}*{A_1} + q*x*{A_2}\\ {M_2} = (x*y)*{A_1}*{A_2} + p*y*{A_2}\\ {N_2} = (x*y)*{A_2}*{A_2} \end{array} \right. $ (21)

由于M1N1运算错误, 会导致V1V2计算错误, 出错时的运算过程如式 (22) 所示:

$ \left\{ \begin{array}{l} {V_1} = (x*y*{A_1})*({A_1} + {A_2}) + p*y*{A_1} + \\ \;\;\;\;\;\;\;q*x*{A_1} + (q*x*{A_2} + pq)\\ {V_2} = (x*y*{A_1})*({A_1} - {A_2}) + p*y*{A_1} + \\ \;\;\;\;\;\;\;q*x*{A_1} + (pq - q*x*{A_2}) \end{array} \right. $ (22)

正确性校验将对V1右移14位, 对V2右移1位。对于V1V2的前半部分, (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 操作数错误

只有一个操作数错误时, 由2.2节可得不会漏检。当同时有两个错误存在时, 有两种情况:

1) MN操作数错误:以M1=X1*Y1N1=X2*Y1同时运算出错为例。M1=X1*Y1操作数取错为M1=X1*p, 以及N1=X2*Y1操作数取错为N1=X2*q, 出错时的运算过程如式 (23) 所示:

$ \left\{ \begin{array}{l} {M_1} = x*{A_1}*p\\ {N_1} = x*{A_2}*q \end{array} \right. $ (23)

M1N1出错将会导致V1V2均运算错误, 出错时的运算过程如式 (24) 所示:

$ \left\{ \begin{array}{l} {V_1} = x*{A_1}*p + x*{A_2}*q\\ {V_2} = x*{A_1}*p - x*{A_2}*q \end{array} \right. $ (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) XY操作数错误:以Y1= y*A1X2=x*A2运算出错为例。这种运算错误具体表现为:Y1= y*A1操作数取错为Y1=q*A1, 且q不等于y, 以及X2=x*A2操作数取错为X2= p*A2, 且p不等于x, 出错时的编码如式 (25) 所示:

$ \left\{ \begin{array}{l} {X_1} = x*{A_1}\\ {X_2} = p*{A_2}\\ {Y_1} = q*{A_1}\\ {Y_2} = y*{A_2} \end{array} \right. $ (25)

X2Y1出错将会导致M1N1N2均运算错误, 出错时的运算过程如式 (26) 所示:

$ \left\{ \begin{array}{l} {M_1} = (x*q)*{A_1}*{A_1} = \\ \;\;\;\;\;\;\;\;(x*y)*{A_1}*{A_1} + (q - y)*x*{A_1}*{A_1}\\ {N_1} = (p*q)*{A_2}*{A_1} = (x*y)*{A_2}*{A_1} + \\ \;\;\;\;\;\;\;\;(p*q - x*y)*{A_2}*{A_1}\\ {M_2} = (x*y)*{A_1}*{A_2}\\ {N_2} = (p*y)*{A_2}*{A_2} = \\ \;\;\;\;\;\;\;\;(x*y)*{A_2}*{A_2} + (p - x)*y*{A_2}*{A_2} \end{array} \right. $ (26)

由于M1M2均运算错误, 会导致V3V4计算错误, 出错时的运算过程如式 (27) 所示:

$ \left\{ \begin{array}{l} {V_3} = (x*y*{A_2})*({A_1} + {A_2}) + (p - x)*y*{A_2}*{A_2}\\ {V_4} = (x*y*{A_2})*({A_1} - {A_2}) - (p - x)*y*{A_2}*{A_2} \end{array} \right. $ (27)

正确性校验将对V3右移14位, 对V4右移1位。对于V3V4的前半部分, (x*y*A2)(A1+A2) 右移14位与 (x*y*A2)(A1-A2) 右移1位的结果都是 (x*y*A2), 二者必然相同。因此漏检需要V3V4的后半部分, 即 (p-x)*y*A2*A2右移14位与右移1位的结果相同, 解出p=0, 即不可能漏检。

在多种错误情况中, 只有MN同时发生计算错误或者MN操作数错误时会出现漏检, 漏检率为1/2n。当N=32时可得漏检率为2.3×10-10

3 漏检率及复杂度测试 3.1 实验目的和环境

测试内容包括漏检率测试和复杂度测试。实现安全编码C语言预编译器, 将没有检错能力的原始代码转换成具有检错能力的代码。实验的故障注入工具为Intel Pin。Intel Pin是Intel公司开发的动态二进制插桩框架, 提供了丰富的API, 可在指令级别对程序进行修改, 达到故障注入的目的。

3.2 漏检率测试 3.2.1 测试方案

使用的故障注入方案,是在Intel Pin库的基础上设计了对应故障类型的故障注入插件 (Fault Injection Tool, FIT), 其中大量调用了Pin库的API来实现动态故障注入。根据故障注入类型, 分别开发了对应的代码实现。

FIT能模拟的故障类型和对应的指令包括:

①WVAL:在写入内存之前, 值被修改为某个指定的值; ②RVAL :内存在被读入时, 之前的值修改为某个指定的值; ③WADDR:写值时, 写入到其他地址上; ④RADDR:读值时, 读了错误地址对应到其他有效码字的地址上; ⑤RREG:寄存器在被读入时, 之前的值修改为某个指定的值; ⑥WREG:在写入寄存器之前, 值被修改为某个指定的值。

在本次测试中通过注入①、②、⑤、⑥指令模拟操作数被修改错误; 通过注入④指令模拟操作数被调换错误; 通过注入④、⑤指令模拟操作符被调换错误; 通过注入④、⑤指令模拟运算错误错误; 通过注入③指令模拟未更新错误:从而通过不同的指令对需要注入故障的测试用例进行故障注入。注入寄存器故障的代码如下。

static VOID

instrument_rreg (INS ins, 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);

}

static VOID

insert_trigger (INS ins)

{

switch (ttype) {

case RR: INS_InsertIfCall (ins, IPOINT_BEFORE, (AFUNPTR) find_rreg, IARG_INST_PTR, IARG_END);

break;

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

break;

default:DIE ("FATAL: not implemented");

}}

static ADDRINT

find_wreg (ADDRINT ip)        //ip为指令地址

{ return counters.wreg }        //返回读寄存器的次

受限于测试环境, 本文在注入①~⑥的故障指令时, 限制对正确值的注入错误范围为32位中的6位, 相当于前文安全性证明中的漏检率中的n值取为6。

3.2.2 测试结果及分析

运算编码检错能力测试中, 每次运行中随机注入错误类型中的一种, 逐渐增加运行次数, 根据总错误数和检测到的错误数计算漏检数和漏检率。测试结果如表 1所示。

表 1 10 000次运算编码检错数据表 Table 1 Error detection results after 10 000 operations

由第2章证明可得, 漏检率在n取6的情况下理论上趋于1.5×10-2。由表 1可知, 当运行次数为10 000时, 10次实验的平均漏检率趋于0.01, 接近理论值1.5×10-2。可见编码运算的漏检率基本符合理论值, 且对比原delta码的剩余错误数有了改进。在实际应用中, 可通过增大n值来使漏检率达到预期的要求。

编码程序检错能力测试中, 以四种程序为基准程序, 分别是冒泡排序 (Bubble sort, BS)、快速排序 (Quick sort, QS)、矩阵乘法 (Matrix multiplication, MM)、斐波那契数列 (Fibonacci Sequence, FS)。分别对安全编码后的程序进行故障植入, 每个编码后的程序执行30 000次, 每次执行都随机注入上述描述的错误类型。测试结果如表 2所示。

表 2 原delta编码及改进编码30 000次故障注入测试结果    % Table 2 Error detection results of original and improved delta codes after 30 000 operations    %

编码程序输出结果错误但未被检测出来的百分比在1.6%左右。由于漏检的错误将会包括算术运算错误与少量控制流错误, 可见二者总的漏检率基本符合理论值, 实际算术运算错误漏检率也基本符合理论值, 且漏检率低于原delta码,从而进一步证明了本安全编码方法的检错率符合预期。

3.3 复杂度测试与仿真 3.3.1 测试方案

复杂度测试过程中, 先要将未具有检错能力的代码转化为具有检错能力的代码; 其次选择循环次数, 并对具有检错能力的代码进行循环执行; 最后记录循环执行所用的时间, 本文基于C语言, 实现了对乘法、除法的编码。分别记录非编码运算和编码运算时间, 并对测得的时间进行比较。

3.3.2 测试结果及分析

本测试中所选的差异因子A1=5、A2=3。每种运算运行100次, 记录源程序的总运行时间,结果如表 3所示。从测试所得数据中可看出, 编码后运算的执行效率都有不同程度的降低。对于不同的运算, 因为编码算法不同, 增加的冗余操作的数目也有所不同, 所以各自降低情况有所区别。总体复杂度对比原delta码有所下降。

表 3 各类运算执行100次时间数据表 Table 3 Improved algorithm's time cost of no code, delta code and improved delta code after 100 operations
4 结语

本文在Kuvaiskii提出的delta安全编码算法的基础上, 进一步提出了采用双目编码的数据进行运算。在复杂度符合要求的基础上, 提高了算法的检错率, 并对算法安全性进行了证明。实验和仿真结果表明:复杂度为未编码运算的6.4~7.2倍, 比原delta码降低了7%~19%,可应用于实时性要求不是很高的场景。未来的工作将在本文的基础上, 在不降低检错能力的前提下, 对算法进行复杂度优化, 以适用于实时性要求较高的场景。

参考文献
[1] FORIN P. Vital coded microprocessor principles and application for various transit systems[M]//PERRIN J P. Control, Computers, Communications in Transportation. New York: IFAC Publications, 1990:79-84.
[2] SCHIFFEL U. Hardware error detection using AN-codes[EB/OL].[2016-03-10]. https://core.ac.uk/download/pdf/35186697.pdf.
[3] 李刚, 丁佳, 梁盟磊, 等. 安全编码预编译器的设计与实现[J]. 计算机工程, 2011, 37 (3) : 230-232. ( LI G, DING J, LIANG M L, et al. Design and implementation of vital coded pre-compile[J]. Computer Engineering, 2011, 37 (3) : 230-232. )
[4] KUVAISKII D, FETZER C. Δ-Encoding: practical encoded processing[C]//Proceedings of the 201545th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2015:13-24. http://ieeexplore.ieee.org/abstract/document/7266834/
[5] SHIRVANI P P. Software-implemented hardware fault tolerance experiments: COTS in space[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] KNIGHT J C. Safety critical systems: challenges and directions[C]//ICSE 2002: Proceedings of the 24th International Conference on Software Engineering. Piscataway, NJ: IEEE, 2002: 547-550. http://ieeexplore.ieee.org/abstract/document/1007998/
[7] SCHEICK L, GUERTIN S, NGUYEN D. Investigation of the mechanism of stuck bits in high capacity SDRAMs[C]//Proceedings of the 2008 IEEE Radiation Effects Data Workshop. Piscataway, NJ: IEEE, 2008: 47-52. http://ieeexplore.ieee.org/abstract/document/4638613/
[8] DUZELLIER S, FALGUERE D, ECOFFET R. Protons and heavy ions induced stuck bits on large capacity RAMs[C]//RADECS 1993: Proceedings of the Second European Conference on Radiation and its Effects on Components and Systems. Piscataway, NJ: IEEE, 1993: 468-472. http://ieeexplore.ieee.org/abstract/document/316527/
[9] CLARK J A, PRADHAN D K. Fault injection: a method for validating computer-system dependability[J]. Computer, 1995, 28 (6) : 47-56. doi: 10.1109/2.386985
[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. http://ieeexplore.ieee.org/abstract/document/6026503/
[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. http://ieeexplore.ieee.org/abstract/document/1633498/
[12] BLOUGH D, SULLIVAN G, MASSON G. Intermittent fault diagnosis in multiprocessor systems[J]. IEEE Transactions on Computers, 1992, 41 (11) : 1430-1441. doi: 10.1109/12.177313
[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. http://ieeexplore.ieee.org/abstract/document/996639/
[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. doi: 10.1109/TNS.2004.839110