基于delta码的乘除法运算错误检测改进算法

doi:10.11772/j.issn.1001-9081.2017.04.0975

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

基于delta码的乘除法运算错误检测改进算法

孙宗奇¹, 臧海娟², 张春花¹, 潘勇¹

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

收稿日期:2016-09-22 修回日期:2016-12-27 出版日期:2017-04-10 发布日期:2017-04-19
通讯作者: 臧海娟
作者简介:孙宗奇(1992-),男,辽宁大连人,硕士研究生,主要研究方向:可信计算;臧海娟(1965-),女,江苏常州人,副教授,博士,主要研究方向:网络安全、信息安全;张春花(1989-),女,山东莒县人,博士研究生,主要研究方向:信息安全、隐私保护;潘勇(1963-),男,浙江慈溪人,副教授,博士,主要研究方向:信息安全、可信计算。
基金资助:
国家科技支撑计划项目（2015BAG13B01）。

Improved algorithm for multiplication and division error detection based on delta code

SUN Zongqi¹, ZANG Haijuan², ZHANG Chunhua¹, PAN Yong¹

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

Received:2016-09-22 Revised:2016-12-27 Online:2017-04-10 Published:2017-04-19
Supported by:
This work is partially supported by the National Science and Technology Support Program (2015BAG13B01).

摘要/Abstract

摘要： 为确保安全苛求系统中程序执行的正确性，研究人员将差错控制理论用于对计算机指令进行编码，但由于编码大多涉及模运算，导致复杂度大量增加，应用于实时系统有困难。针对复杂度问题对delta码的乘除法运算算法进行改进。算法在乘法运算中引入冗余编码及差异化思想，从而确保安全性；在除法运算中引入逆元，将除法运算转化为低复杂度的乘法运算，避免了模运算带来的开销，降低了复杂度并提高了算法安全性，并对安全性进行理论论证。理论分析表明：所提算法漏检率可达2.3×10^-10。测试结果表明，所提算法的漏检率与理论值相符，且复杂度是未编码运算6.4~7.2倍，比原delta码降低了7%~19%，在漏检率与复杂度方面均满足安全苛求系统的应用要求。

关键词: 安全编码, 数据差异化, 错误检测, 安全性, 逆元

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

中图分类号:

TP302.8

孙宗奇, 臧海娟, 张春花, 潘勇. 基于delta码的乘除法运算错误检测改进算法[J]. 计算机应用, 2017, 37(4): 975-979.

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.

参考文献

[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] KUVAISKⅡ 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.
[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.
[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.
[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.
[9] CLARK J A, PRADHAN D K. Fault injection: a method for validating computer-system dependability[J]. Computer, 1995, 28(6): 47-56.
[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.
[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.
[12] BLOUGH D, SULLIVAN G, MASSON G. Intermittent fault diagnosis in multiprocessor systems[J]. IEEE Transactions on Computers, 1992, 41(11): 1430-1441.
[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.
[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.

[1]	谷正川, 郭渊博, 方晨. 基于代理重加密的消息队列遥测传输协议端到端安全解决方案[J]. 计算机应用, 2021, 41(5): 1378-1385.
[2]	张平, 贾亦巧, 王杰昌, 石念峰. 三因子匿名认证与密钥协商协议[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3281-3287.
[3]	沈子懿, 王卫亚, 蒋东华, 荣宪伟. 基于Hopfield混沌神经网络和压缩感知的可视化图像加密算法[J]. 计算机应用, 2021, 41(10): 2893-2899.
[4]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[5]	张国潮, 王瑞锦. 基于门限秘密共享的区块链分片存储模型[J]. 计算机应用, 2019, 39(9): 2617-2622.
[6]	王众, 韩益亮. 基于改进版Niederreiter的双公钥密码方案[J]. 计算机应用, 2019, 39(7): 1997-2000.
[7]	马兰, 崔博花, 刘轩, 岳猛, 吴志军. 基于隐半马尔可夫模型的SWIM应用层DDoS攻击的检测方法[J]. 计算机应用, 2019, 39(7): 1973-1978.
[8]	曾剑平, 陈其乐, 吴承荣, 方熙. 中文语境下的口令分析方法[J]. 计算机应用, 2019, 39(6): 1713-1718.
[9]	史志才, 王益涵, 张晓梅, 陈珊珊, 陈计伟. 可扩展及可证安全的射频识别认证协议[J]. 计算机应用, 2019, 39(3): 774-778.
[10]	许瀚, 罗亮, 孙鹏, 孟飒. 基于马尔可夫模型的云系统安全性与性能建模[J]. 计算机应用, 2019, 39(11): 3304-3309.
[11]	沈敏捷, 曾振柄, 林望, 杨争峰. 基于随机障碍验证的随机连续系统安全性验证[J]. 计算机应用, 2018, 38(6): 1737-1744.
[12]	张晔, 陆余良. PLC程序控制流分析方法[J]. 计算机应用, 2017, 37(12): 3581-3585.
[13]	胡振宇, 李志华, 陈超群. 基于用户社会关系的移动终端认证方案[J]. 计算机应用, 2016, 36(6): 1552-1557.
[14]	徐海琳, 陈莺, 陆阳. 高效无双线性对的基于证书代理重加密方案[J]. 计算机应用, 2016, 36(5): 1250-1256.
[15]	王占君, 马海英, 王金华. 完全安全的等级身份基在线/离线加密[J]. 计算机应用, 2015, 35(9): 2522-2526.

基于delta码的乘除法运算错误检测改进算法

Improved algorithm for multiplication and division error detection based on delta code

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics