Page 107 - 《软件学报》2020年第11期

陈千 等:函数级数据依赖图及其在静态脆弱性分析中的应用 3423

重新定义数据依赖图,从而达到缩减数据依赖图规模、降低数据依赖图生成的时空复杂度的目的.

2 函数级数据依赖图
2.1 数据流分析

数据流分析主要关注程序执行路径上的数据流流动或可能的取值,其目的是在程序的一定范围内,确定变
量定义和引用间的关系.变量定义指程序中的某条语句对变量进行赋值,除定义之外的其他变量出现称为变量
引用.
数据依赖表示程序中对某变量进行引用的语句(或基本块)对定义该变量语句的依赖,即一种“定义-引用”
依赖关系(如图 1 所示).若 a 和 b 分别是程序控制流图中的两个节点,v 为程序中的一个变量,当节点 a 和 b 满足
以下条件时,称节点 b 关于变量 v 直接数据依赖于节点 a:(1) 节点 a 对变量 v 进行定义;(2) 节点 b 中引用了变
量 v;(3) 节点 a 到节点 b 之间存在一条可执行路径,且在此路径上不存在其他语句对变量 v 进行定义.

Fig.1 Example of variable definition and use
图 1 变量定义与引用示例

数据依赖图 DDG [17] 是一种表示程序语句(或基本块)间数据依赖关系的有向图.根据数据依赖关系可以构
建数据依赖图 DDG=(V,E),其中,V 表示程序中所有语句对应节点的集合,E 表示语句之间数据依赖关系的集合.
图 2 为代码片段及其对应的数据依赖图示例.对于二进制代码而言,数据依赖图中的节点均为指令,因此本文将
这种传统的数据依赖图称为指令级数据依赖图.

Fig.2 Example of code snippet and its data dependence graph
图 2 代码片段及其数据依赖图示例
2.2 函数级数据依赖图定义
指令级数据依赖图在数据流分析中应用广泛,但其资源开销限制了可分析代码的规模和分析的效率.鉴于
此,本文提出函数级数据依赖图 FDDG=(FV,FE)的概念,通过降低构图粒度提升分析效能.与指令级数据依赖图
不同的是,FV 表示程序中函数对应节点的集合,FE 表示函数之间参数依赖关系的集合.
2.2.1 函数级数据依赖图中的节点
在函数级数据依赖图中,节点代表函数,其记录了函数参数或返回值之间的“定义-引用”关系,同时包含函数
参数的大小、函数名等信息.节点可以采用(func_name,〈[def_arg1,def_arg2,…],[use_arg1,use_arg2,…]〉)这种形式
来表示,其中,func_name 为函数名称,〈[def_arg1,def_arg2,…],[use_arg1,use_arg2,…]〉表示函数参数或返回值之
间的“定义-引用”关系,[def_arg1,def_arg2,…]为定义参数的集合,[use_arg1,use_arg2,…]为引用参数的集合.