﻿ 基于delta码的乘除法运算错误检测改进算法
 计算机应用   2017, Vol. 37 Issue (4): 975-979  DOI: 10.11772/j.issn.1001-9081.2017.04.0975 0

### 引用本文

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.

### 文章历史

1. 同济大学 电子与信息工程学院, 上海 201804;
2. 江苏理工学院 计算机工程学院, 江苏 常州 213001

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

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

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

 $\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)

 $\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)

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

1.2 乘法编码算法

 $\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)

 $\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)

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

 $\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)

 $\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)

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

 $\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)

 $\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)

1.3 除法编码算法

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

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

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

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)

 $\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)

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)

 $\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)

2.4 操作数错误

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)

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)

 $\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)

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

3.2 漏检率测试 3.2.1 测试方案

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");

}}

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

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

3.2.2 测试结果及分析

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

3.3.2 测试结果及分析

4 结语

 [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