Page 111 - 《软件学报》2020年第11期
P. 111
陈千 等:函数级数据依赖图及其在静态脆弱性分析中的应用 3427
系,先后在当前函数和全局变量定义列表中查找函数参数定义中引用参数的定义,若查找成功,则将
对参数进行定义的函数和对其引用参数进行定义的函数作为节点、参数之间的依赖关系作为边添加
到数据依赖图中,然后跳转到步骤(5).
(4) 将对该参数进行定义的函数作为节点添加到数据依赖图中.若在当前函数和全局变量定义列表中均
无法找到该定义中引用参数的定义,则将该参数的定义更新到所有直接调用当前函数的父函数中.
(5) 若当前函数的控制流图中某个节点的出度为 0,则需要将函数内对函数参数的定义更新到所有直接
调用该函数的父函数中;同时,将对全局变量的定义更新到全局变量定义列表中.
(6) 若函数控制流图遍历完毕,则跳转到步骤(7);否则跳转到步骤(2).
(7) 若函数调用图遍历完毕则停止,否则跳转到步骤(1).
其中,在步骤(3)中,针对某个关键参数的定义,如果该定义中引用参数的类型为整数类型,则不查找引用参
数的定义,只有当其类型为堆/栈变量、返回值、函数参数或全局变量时才进行查找.此外,在全局变量定义列表
中查找其引用参数的定义时,如果存在多个对引用参数的定义,则在对关键参数进行定义的函数和每个对其引
用参数进行定义的函数之间都建立一条边.在步骤(5),由于函数内部对函数参数的定义会影响父函数的行为,当
遇到出度为 0 的节点时,需要更新函数参数定义,同时也要更新全局变量定义列表.
算法 1. 函数级数据依赖图构建算法.
输入:函数调用图 CG,控制流图 CFG.
输出:函数级数据依赖图 FDDG.
1 GenerateFDDG(CG,CFG);
2 for each node n i in CG
3 for each block_node b i in CFG
i n
4 for each dst_def_info dd i in b i
5 sd←search_src_def(dd i ); /*在局部或全局变量定义列表中查找引用参数的定义*/
6 if sd
7 FDDG.add_edge(sd,dd i );
8 else
9 FDDG.add_node(dd i );
10 save_forward_def_info(n i ,dd i ); /*保存参数用于后续在父节点中继续查找*/
11 end if
12 save_def_info(n i ,dd i );
13 end for
14 for each node s i in successors(b i )
15 add_def_info(s i ); /*将 b i 中的信息添加到后继节点中*/
16 end for
17 if out_degree bi ==0
18 for each node p i in predecessors(n i )
19 update_def_infos(p i ); /*将 n i 中的信息更新到父节点中*/
20 end for
21 end if
22 end for
23 for each node p i in predecessors(n i )
24 search_forward_def(p i ); /*对于未查找到的定义,在父节点中进行查找*/
25 end for
