[发明专利]一种表驱动的签名错误检测算法

摘要

本发明公开了一种表驱动的签名错误检测算法，该算法是基于有限状态自动机理论（FSM），在二维表（CFID表）中存储控制流图的信息，通过比较基本块中的签名和存储在CFID表中的签名检测出非法的指令跳转。对于CFCSS算法不能检测的共享分支扇入节点的非法指令跳转错误，本发明可成功检测出这类错误。实验结果显示，本发明平均错误检测覆盖率达到98.1%，并且本发明在每个基本块中插入的错误检测指令较CFCSS中的更少。

主权项

一种表驱动的签名错误检测算法，其特征在于，该检测算法包括以下具体步骤：步骤1：确定所有基本块，即节点，建立程序P的控制流图，为每一个节点编号，即基本块标识号，在控制流图中以自然数开始，即vi, i=1, 2….N；步骤2：对每一个节点vi都赋予一个签名SSi，如果i≠j, 则SSi≠SSj，其中i,j=1,2,…N；每一个签名 SSi 与相应的基本块标识vi中的i相等；步骤3：对每一个vi,i=1,2,3…，进行如下操作：a）对每一个分支bri,j ，它的前驱节点为vi ，后继节点为vj；这些分支由一个二维表表示，该二维表称为CFID[i,j]；在该表中，行i表示前驱节点，列j表示后继节点；b）如果分支 bri,j在控制流图中，将后继节点的签名SSj 填入CFID[i,j]对应的位置；否则CFID[i,j]位置应填入0值；c）Reg寄存器中存储的全局变量在基本块每一次执行其检测指令时都更新一次，以跟踪程序执行过程中签名的变化；d）在基本块的初始位置插入一条判断指令，判断SSi与CFID[Reg,SSi]是否相等，如果相等，则将SSi赋值给Reg，如果不相等，则报错。