计算机应用 ›› 2015, Vol. 35 ›› Issue (12): 3450-3455.DOI: 10.11772/j.issn.1001-9081.2015.12.3450

• 信息安全 • 上一篇    下一篇

用于程序循环控制的错误检测算法

邹宇1, 薛小平1, 张芳1, 潘勇1, 潘腾2   

  1. 1. 同济大学电子与信息工程学院, 上海 201804;
    2. 上海交通大学密西根学院, 上海 200240
  • 收稿日期:2015-06-04 修回日期:2015-08-22 出版日期:2015-12-10 发布日期:2015-12-10
  • 通讯作者: 邹宇(1991-),男,江西赣州人,硕士研究生,主要研究方向:可信计算
  • 作者简介:薛小平(1963-),男,江苏常州人,教授,博士生导师,博士,主要研究方向:安全苛求系统、网络路由;张芳(1971-),女,浙江绍兴人,讲师,博士,主要研究方向:可信计算、信号处理;潘勇(1963-),男,浙江慈溪人,副教授,主要研究方向:信息安全、可信计算;潘腾(1994-),男,上海人,主要研究方向:信号处理。

Error detection algorithm of program loop control

ZOU Yu1, XUE Xiaoping1, ZHANG Fang1, PAN Yong1, PAN Teng2   

  1. 1. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China;
    2. University of Michigan-Shanghai Jiao Tong University Joint Institute, Shanghai 200240, China
  • Received:2015-06-04 Revised:2015-08-22 Online:2015-12-10 Published:2015-12-10

摘要: 为确保安全苛求系统中程序执行的正确性,针对程序循环控制中内存未更新、循环提前结束和循环滞后结束的问题,提出一种基于含签名和时间戳的算术(ANBD)码的循环控制错误检测算法。该算法通过ANBD码,将程序变量编码为含签名的码字。通过校验码字签名,检测循环控制错误。运用ANBD码中的时间标签,可检测内存未更新错误。另外,在ANBD码基础上,通过采用在线语句块签名分配算法、语句块签名函数和变量签名补偿函数,检测循环提前结束错误和循环滞后结束错误。该算法理论错误漏检概率为1/A,其中A为编码素数,选取97~10993的素数进行错误漏检概率测试,得到理论模型与测试结果的归一化均方误差(NMSE)约为-30 dB。测试结果表明,该算法可检测循环控制中出现的各类错误,且编码素数A接近232时,错误漏检概率可达10-9,能够满足安全苛求系统的应用要求。

关键词: 循环控制, 错误检测, 含签名和时间戳的算术(ANBD)码, 签名

Abstract: There are the errors that memory data is not updated, the loop exits early and the loop exits late in the program loop control. In order to ensure the correctness of the program execution in the safety critical system, a new error detection algorithm of program loop control based on ANBD-code (arithmetic-code with signature and timestamp) was proposed. Through ANBD-code, the program variables were encoded as a signed code word by the proposed algorithm. And the errors in the loop control were detected by verifying code signature, the error of memory data being not updated could be detected by using the time label of ANBD-code. In addition, on the basis of the ANBD-code, the errors of the loop exiting early and the loop exiting late could be detected by using the online statement block signature allocation algorithm, the block signature function and the variable signature compensation function. The occurrence probability of an undetected error was 1/A in theory, where A was coding prime. The primes were selected between 97 and 10993 to test occurrence probability of an undetected error and the Normalized Mean Square Error (NMSE) of theoretical model and test result was about-30 dB. The test results show that the proposed algorithm can effectively detect all kinds of errors in the loop control and the occurrence probability of an undetected error is up to 10-9 when the prime A is close to 232. The proposed algorithm can satisfy the requirements of safety critical system.

Key words: loop control, error detection, arithmetic-code with signature and timestamp (ANBD-code), signature

中图分类号: