欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2023100648884
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于高阶函数的动态程序依赖簇检测方法,其特征在于,包括:

利用符号执行工具获取程序在给定输入条件下的语句执行历史和函数调用关系,根据实际的调用关系构建简化的函数调用图;

所述函数调用图中记录被调用的函数名称为Ncallee,对每个函数调用点,记录实际过程调用和被调用的函数名称,构成二元组;通过函数调用关系的二元组构建具体输入条件下的调用图再通过逆拓扑排序的顺序简化函数调用图确定子过程的分析顺序;自设定一个高阶函数,参数有实参的数据依赖、全局变量的数据依赖以及指令索引;

所述高阶函数的数据依赖参数初始化过程P的变量依赖集S,初始化语句依赖集L,依赖簇信息集C为空,获取过程P的入口基本块Bentry;计算Bentry中每条语句i的控制依赖关系即CDi,根据得到的语句执行历史和指令索引I计算当前指令的动态引用集REF(i,I),得到指令依赖l'(i);

所述指令依赖的应用规则为,

当前指令为phi指令时,根据得到的语句执行历史,和指令索引I计算phi指令的动态引用集,即当E(I)=n时,取phi指令的第n个选项为引用变量,其它指令,与它们的静态引用集保持一致,f={fx,fy,...fn},g={gx,gy,...gn}

其中FRML(P)是过程P的形式参数集合;GLOB是程序的全局变量集合;ALLOCA(P)是过程P的局部变量集合;INST(P)是过程P的指令集合;i’,j对应了当前指令i的引用节点和控制节点属于INST(P),λ为匿名函数,参数为f,g,I;f集合是上层函数的实参对应的依赖集合,即fx为第一个实参的依赖集合,fy为第二个实参的依赖集合,以此类推,g集合是上层函数进行调用时,当前全局变量对应的依赖集合,即gx为第一个全局变量的依赖集合,gy为第二个全局变量的依赖集合,以此类推,I为上层函数进行调用时的指令索引;f,g,I在调用点处由具体的数据进行代入,R是控制依赖和数据依赖对应的集合,是关于R的函数,R的参数中使用了λ表达式中的变量f,g;

构建每个过程高阶函数形式的函数摘要,获取过程间由于过程调用和参数传递产生的依赖簇信息;

将计算得到的依赖簇信息进行汇总,获取给定输入条件下相互依赖的程序语句,从而检测动态程序依赖簇。

2.如权利要求1所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:所述符号执行当中将源程序进行编译得到中间代码,其次对中间码进行优化,约简程序中的select,switch语句分别转换为phi语句和有条件跳转语句;符号执行器接收经过优化的中间代码,在给定的用户输入参数下进行符号执行。

3.如权利要求2所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:所述有条件跳转语句是用0和1记录跳转的基本块,0表示条件为否时跳转的基本块,1表示条件为是时跳转的基本块。

4.如权利要求1所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:根据访问的语句类型和指令依赖,更新指令索引I,语句依赖集L,变量依赖集S和依赖簇信息集C,针对赋值语句或内存修改语句i,更新该语句i中所定义变量x的变量依赖集S(x)为l'j(i),更新依赖簇信息集C(i,x)=S(x),

针对赋值语句或内存修改语句以外的语句,更新该语句i语句的依赖集L(i)为l'(i),j更新依赖簇信息集C(i,i)=L(i),

针对有条件跳转语句,函数调用语句,和phi语句,当前指令索引I加1,其它语句的指令索引保持不变,针对有条件跳转语句,根据E(I)=0或1,获取下一个分析的基本块,0表示条件为否时跳转的基本块,1表示条件为真时跳转的基本块,针对无条件跳转语句,获取其跳转地址,

针对Return语句,此过程P结束,

针对Unreachable语句,此分析结束,退出。

5.如权利要求4所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:根据过程语句依赖集L,变量依赖集S和依赖簇信息集C以及更新后的指令索引I,生成高阶函数形式的函数摘要,x∈FRML(P)∪GLOB∪ALLOCA(P),i|∈INST(P)j

λfλgλI.(R(f,g,x),C(i,v),T(I))

j

C(i,v)=R′(f,g,x,i,j)∪R′(f,g,i,i,j)

f={fx,fy,...fn},g={gx,gy,...gn}

其中FRML(P)是过程P的形式参数集合;GLOB是程序的全局变量集合,ALLOCA(P)是过程P的局部变量集合,INST(P)是过程P的指令集合,λ为匿名函数,参数为f,g,I;f集合是上层函数的实参对应的依赖集合,即fx为第一个实参的依赖集合,fy为第二个实参的依赖集合,以此类推,g集合是上层函数进行调用时,当前全局变量对应的依赖集合,即gx为第一个全局变量的依赖集合,gy为第二个全局变量的依赖集合,以此类推,I为上层函数进行调用时的指令索引;f,g,I在调用点处由具体的数据进行代入;将指令索引,变量依赖集S和依赖簇信息集C更新过程视作为函数T,R,R’,返回值为更新后的指令索引,变量依赖集S和依赖簇信息集C。

6.如权利要求4或5所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:通过高阶函数摘要中的执行历史和当前指令索引,可获得被调用函数Q的过程内依赖分析结果,其包含调用结束后指令索引I’过程Q的语句依赖集Lq,变量依赖集Sq和依赖簇信息集Cq;

如果Sq中的依赖信息中不仅包含参数本身,还包括过程内的依赖信息值,则说明该变量是按结果调用类型,否则为按值调用类型,将全局变量视为按结果调用;

针对按值调用的形参类型,对形参依赖关系信息中的参数值,只需代入调用点处的控制依赖,即可获取形参的完整依赖关系;

针对按结果调用形参类型,使用实参的依赖关系来对形参依赖关系信息中的参数值进行代入,并与调用点处的控制依赖进行合并,从而获取形参的完整依赖关系;

针对按值调用的全局变量,使用空集替换全局变量依赖关系信息中的参数值;

针对按结果调用的全局变量,使用调用过程P当前全局变量的依赖关系来对过程Q全局变量依赖关系信息中的参数值进行代入,获取形参的完整依赖关系;

对于过程Q中的依赖簇信息集Cq,其内部参数值均视为按结果调用,调用过程P中的相应实参,全局变量进行替换并与调用点处的控制依赖进行合并;

如果过程Q存在返回值,则将返回值变量对应的依赖信息添加到Sp中;

针对按结果调用形参类型,使用形参的依赖关系将Sp中对应实参依赖关系信息中进行更新;

针对按结果调用的全局变量,当过程Q的全局变量依赖关系不为空集时,对Sp中全局变量依赖关系信息中进行更新;

更新Ip为I’,依赖簇信息集更新方式为Cp←Cp∪Cq。

7.如权利要求6所述的一种基于高阶函数的动态程序依赖簇检测方法,其特征在于:将得到的程序执行历史E,和初始指令索引I,定义I=0,代入该程序入口函数main函数的高阶函数形式的摘要,最终获取最终依赖簇信息集C。