一种实用的程序控制流错误检测方法.pdf

《一种实用的程序控制流错误检测方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第33卷第8期绵阳师范学院学报V01．33No．82014年8月JournalofMianyangNormalUniversAug．，2014一种实用的程序控制流错误检测方法宋伟，余强，孙庆中(西华大学数学与计算机学院，四川成都610039)摘要：该文武介绍了一种检测软件控制流错误的方法，阐述了该方法的原理，给出了具体的实现方案和测试结果．本方法在RSCFC方法的基础上，通过把程序划分为若干个基本模块并分别为每个模块设定静态标记，在每个基本模块的首部和尾部分别加上相应的测试和设置指令，在程序运行时通过比较运行时生成的动态标记和编译时确定的静态标记是否匹配来检测程序控制流错误

2、．本方法和RSCFC方法相比的优点在于：使用相同长度的标记可以编码更多的基本模块；在基本模块的起始处和结束处都进行错误检测，错误覆盖率高；可以在发生错误的当前基本模块检测出所有的单个控制流错误，不会延迟到控制流进入下一个基本模块．关键词：程序错误检测；控制流错误；软件检测；基本模块；非法跳转中图分类号：TP311．5文献标志码：A文章编号：1672-612x(2014)08-0095-05O引言当今世界对计算机的运行速度和可靠性的要求越来越高，尤其是在诸如航天、医疗和军事等领域可靠性显得尤为重要uJ．但是在现实世界由于各种因素的干扰计算机中程序的运行难免会出现一些问题．程序

3、运行出现的问题主要包括两个方面——数据错误和控制流错误J．针对程序错误现在主要有3种检测方法：硬件检测、软件检测和软硬件结合检测l3]．硬件检测需要修改硬件结构，但这种方法指令冗余小，其主要通过看门狗计数器和看门狗协助处理器完成一，基于看门狗定时器的控制流检测方法只能检测出控制流较长时间或永久偏离正常轨道的错误，错误检测率低；软件方法错误检测是通过在同一处理单元上重复执行同一程序，比较各次的执行结果是否相同来检测程序执行是否正确，这种方法会增加程序代码的长度和运行时间，不适合实时眭较高的场合．随着计算机技术的发展，计算机运行速度越来越快，软件检测的优越性得以逐步体现．到目前

4、为止已经提出了很多有关程序错误检测的软件方法，其中比较重要的有ECCA_8J、CFCSS9和RSCFC．RSCFC赋予每个基本模块唯一的标记si和位置信息Li，RSCFC通过全局变量s检测程序控制流的执行，s中包含着程序流图中当前基本模块的标记si，每个基本模块的人口和出口分别加入测试和设置指令，当控制流从一个基本块跳转到另一个基本块时，测试指令使用s和Li两个值来确认当前跳转是否合法。。．RSCFC的测试和设置指令都非常简单，但由于位置信息Li的编码方式导致在使用4字节无符号长整型表示位置信息时最多只能表示31个基本模块，编码效率较低，随着软件规模的增加，编码往往不够用，

5、影响了RSCFC的实用性．本文提出了另外一种程序错误检测方法，称之为SD(Shiftingdetection)．该方法通过把基本模块间的正确跳转关系分段编码到基本模块标记中，在程序运行过程中用移位运算依次取出各段分别进行检测，从而判断跳转是否正确．1SD方法原理1．1基本模块的生成基本模块的定义：从第一个指令开始进入执行而从最后一个指令离开的最大指令序列．即在基本模块收稿日期：2013—11—27基金项目：教育部春晖计划(NO．13226651)；四川省教育厅应用基础研究项目(NO．11226016)作者简介：宋伟(1988一)，男，安徽阜阳市，助教，硕士研究生．研究方向：

6、P2P技术及应用．第33卷绵阳师范学院学报(自然科学版)·96·中除最后一个指令外，不包括任何改变控制流的跳转、分支或调用指令．这样一个程序就可以由基本模块组成的节点集V和节点之间连接的“边”集E组成的一个图来表示，即程序流图(PFG)，P={V，E}，其中V={v。，v，⋯⋯，v⋯．．v}，E={e。，e：，⋯⋯e⋯．．e}．节点vi代表基本模块，边ei代表从节点vi到vj的分支bri；．对于一个程序流图P={V，E}，我们定义SUC(vi)为节点vi的后继节点集pred(vi)为vi的前驱结点集．只有当br∈E时，节点vi∈suc(v)．与之类似只有当brj．i∈E时，

7、节点vj∈pred(vi)．在程序执行过程中，如果br．．i章E，那么br就是一个非法分支．从节点vi到节点v的跳转就是一个非法跳转．1．2运行过程中控制流检查假设一个程序有n个基本模块(n<255)，分别标记为v，v：，v⋯⋯，v．基本模块vi的静态位置信息是Li(Li=i)(此处静态的意思是指在编译时确定)，基本模块的编码从1开始依次递增(0用作特殊功能)．假定最多有255个基本模块，每个基本模块对应一个位置信息，则Li需要8bit来表示．假设每个基本模块最多可以跳转到8个不同的基本模块起始处(在实际情况中这个