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

3422 Journal of Software 软件学报 Vol.31, No.11, November 2020

magnitude compared to the method in angr. As an instance, FDDG is employed to analyze the vulnerability of embedded firmwares, and a
firmware vulnerability analysis prototype system called FFVA is implemented. The implemented FFVA system is used to analyze
firmwares from real embedded devices, and find a total of 24 vulnerabilities in the devices from D-Link, NETGEAR, EasyN, uniview, and
so on, among which 14 are unknown vulnerabilities, thus validating the effectiveness of function-level data dependence graph in static
vulnerability analysis.
Key words: data flow analysis; function-level data dependence graph; vulnerability analysis; firmware

[1]
数据流分析是一种用来获取相关数据沿着程序执行路径流动的信息分析技术 ,分析对象是程序执行路
径上的数据流动或可能的取值,最初被广泛应用于程序的编译优化过程.作为程序静态分析的辅助支撑技术,该
技术也逐渐被运用于程序切片、变量别名分析、信息泄露检测等中.
由于程序数据流的某些特点或性质与程序漏洞紧密相关,也可以将数据流分析技术用于程序漏洞的检测
[2]
中 .比如对 SQL 注入、系统命令注入等漏洞进行检测,主要关心数据的流动或数据的性质,即需要知道某个变
量的取值是否来源于某个非可信的数据源.文献[3]采用上下文敏感的数据流分析方式来发现 Web 应用中的脆
弱点,适用于 SQL 注入、XSS 和命令注入等污点类漏洞的检测.而针对缓冲区溢出漏洞的检测,还需要知道某个
程序变量可能的取值范围.目前,数据流分析已被广泛应用于各种面向源代码的漏洞检测分析工具中,典型的工
[5]
[4]
[7]
[6]
[8]
具包括 FindBugs 、Fortify SCA 、Coverity 、IBM Appscan Source Edition 和 Pinpoint 等.类似地,数据流
[9]
分析技术也可以用于二进制代码的漏洞检测与分析中,如 CodeSonar .
在进行数据流分析时,由于构建传统数据依赖图(data dependence graph,简称 DDG)的时间与空间复杂度高,
严重限制了可分析代码的规模.如何对数据依赖图进行改进,对于提升静态分析效率具有重要意义.本文提出了
函数级数据依赖图(function-level data dependence graph,简称 FDDG)的概念,设计了 FDDG 的构建方法,在保证
数据流准确性的同时,缩小数据依赖图的规模,显著降低数据依赖图的构建时间.实验结果表明:基于 FDDG 对
嵌入式固件进行脆弱性分析,在保证分析能力的情况下,能够极大地提升分析效率.
1 相关工作

近年来,数据依赖分析成为程序自动并行化、运行时调度和性能优化等应用中的研究热点.在程序自动并
行化的研究中,数据依赖分析是指令可并行性判别的重要方法.Ye 等人 [10] 通过离线分析代码块间数据依赖关
系,从而节省运行时的计算资源和开销.Abbas 等人 [11] 通过自适应采样方式生成近似的数据依赖图,避免通过代
码插装方式带来的运行时性能损失过高问题,但该方式会带来一定的精度损失.而 Li 等人 [12] 则提出了一种快速
数据依赖分析技术,允许跳过循环中重复执行的内存操作,在保证精度的同时,降低数据依赖分析的时间开销.
上述方法虽然降低了数据依赖分析的时间开销,但构建得到的数据依赖图包含大量与脆弱性分析无关的变量
信息,大大降低了变量回溯的效率,不适用于程序静态脆弱性分析.
在数据流分析中,函数摘要技术是过程间分析常用的技术 [13] .通过为函数生成摘要信息,避免在不同上下文
对同一函数进行多次分析,从而简化过程间分析的复杂度.Rountev 等人 [14] 采用生成库代码摘要的方式来加快
数据流分析,但其时间复杂度较高,同时未考虑存在间接调用的情形.而 Tang 等人 [15] 提出了一个用于程序分析
的 TAL(tree-adjoining language)可达性框架,在降低开销的同时,解决了存在间接调用时库代码的摘要生成问题.
利用函数摘要技术,可以在一定程序上能够降低数据依赖分析的时间开销.但该技术与数据依赖图生成过程无
关,不能从结构上优化数据依赖图.
也有一些学者对数据依赖图进行了简单改进,以满足特定应用场景的需求.杨轶等人 [16] 在研究恶意代码相
似性比较方法时,对传统的数据依赖图进行了扩展——在数据依赖图中增加了恶意代码行为统计信息记录;之
后,通过对依赖图进行预处理以缩减图的规模;然后,基于扩展的依赖图进行相似性比较,以提升结果的准确性,
同时避免由于混淆、加壳等反制手段引起的干扰.
本文从依赖图构建的角度,提出了一种新的数据依赖图——函数级数据依赖图(FDDG).其核心思想是:在
考虑函数参数及参数间相互依赖关系的基础上,将函数作为整体进行分析,忽略函数内部的具体实现,从结构上