函数级数据依赖图及其在静态脆弱性分析中的应用-陈千，程凯，郑尧文，朱红松，孙利民.pdf

上善若水

346

15页

0次

2022-05-24

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2020,31(11):3421−3435 [doi: 10.13 328/j.cnki.jos.005833] http://www.jos.org.cn

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

∗

陈

千

1,2,3

程

凯

1,2

郑尧文

1,2

朱红松

1,2

孙利民

1,2

(物联网信息安全技术北京市重点实验室(中国科学院信息工程研究所),北京 100093)

(中国科学院大学网络空间安全学院,北京 100049)

(北京奇虎科技有限公司,北京 100015)

通讯作者: 朱红松, E-mail: zhuhongsong@iie.ac.cn

摘要: 数据流分析是二进制程序分析的重要手段,但传统数据依赖图(DDG)构建的时间与空间复杂度较高,限制

了可分析代码的规模.提出了函数级数据依赖图(FDDG)的概念,并设计了函数级数据依赖图的构建方法.在考虑函

数参数及参数间相互依赖关系的基础上,将函数作为整体分析,忽略函数内部的具体实现,显著缩小了数据依赖图规

模,降低了数据依赖图生成的时空复杂度.实验结果表明,与开源工具 angr 中的 DDG 生成方法相比,FDDG 的生成时

间性能普遍提升了 3 个数量级.同时,将 FDDG 应用于嵌入式二进制固件脆弱性分析,实现了嵌入式固件脆弱性分析

原型系统 FFVA,在对 D-Link、NETGEAR、EasyN、uniview 等品牌的设备固件分析中,发现了 24 个漏洞,其中 14

个属于未知漏洞,进一步验证了 FDDG 在静态脆弱性分析中的有效性.

关键词: 数据流分析;函数级数据依赖图;脆弱性分析;固件

中图法分类号: TP311

中文引用格式: 陈千,程凯,郑尧文,朱红松,孙利民.函数级数据依赖图及其在静态脆弱性分析中的应用.软件学报,2020,

31(11):3421−3435. http://www.jos.org.cn/1000-9825/5833.h tm

英文引用格式: Chen Q, Cheng K, Zheng YW, Zhu HS, Sun LM. Function-level data dependence graph and its application in

static vulnerability analysis. Ruan Jian Xue Bao/Journal of Software, 2020,31(11):3421−3435 (in Chinese). http://www.jos.org.

cn/1000-9825/5833.ht m

Function-lev el Da ta De pende nce Gra ph a nd It s Applicatio n in Static Vuln erabili ty Analysis

CHEN Qian

1,2,3

, CHENG Kai

1,2

, ZHENG Yao-Wen

1,2

, ZHU Hong-Song

1,2

, SUN Li-Min

1,2

(Beijing Key Laboratory of IOT Inf ormation Security Technology (Institute of Infor mation Engineering, Chinese Academy of S ciences),

Beijing 100093, China)

(School of Cyber Security, University of Chin ese Academy of Sci ence, Beijing 100049 , China)

(Qihoo 360 Technology Co. Ltd., Beijing 100015, China)

Abstra ct : Data flow analysis plays an important role in binary code analysis. Due to consuming too much time and space, constructing

the traditional data d ependence graph (DDG) limits th e size of the analyzed code thoroughly. This study introduces a novel gr aph model,

function-level data dependence graph (F DDG), and proposes a corresponding construction method. Th e key insights behind FDDG lie in

the following two points. First, FDDG focuses on the relationships between function parameters; Second, FDDG treats a function as a

whole and ignores the details insid e the function. As a result, th e size of th e data dependence graph is reduced signifi cantly. Also, the ti me

and space are saved greatly. The experimental results show the time performance of the method is improved by about three orders of

∗ 基金项目: 国家自然科学基金(U1766215, U1636120); 中国科学院信息工程研究所国际合作项目(Y7Z0451104); 国家电网公

司科学技术项目(52110417001B)

Foundation item: National Natural Science Foundation of China (U1766215, U1636120); International Cooperation Project of

Institute of Information Engineering, Chinese Academy of Sciences (Y7Z0451104); Science and Technology Project of State Grid

Corporation of China (52110417001B)

收稿时间: 2018-10-09; 修改时间: 2018-11-29, 2019-01-18; 采用时间: 2019-02-28

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 vulnerabilit ies in the d evices from D-Link, NETGEAR, EasyN, univi ew, a nd

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 d ata dep endence graph; vulnerabilit y analysis; firmware

数据流分析是一种用来获取相关数据沿着程序执行路径流动的信息分析技术

[1]

,分析对象是程序执行路

径上的数据流动或可能的取值,最初被广泛应用于程序的编译优化过程.作为程序静态分析的辅助支撑技术,该

技术也逐渐被运用于程序切片、变量别名分析、信息泄露检测等中.

由于程序数据流的某些特点或性质与程序漏洞紧密相关,也可以将数据流分析技术用于程序漏洞的检测

中

[2]

.比如对 SQL 注入、系统命令注入等漏洞进行检测,主要关心数据的流动或数据的性质,即需要知道某个变

量的取值是否来源于某个非可信的数据源.文献[3]采用上下文敏感的数据流分析方式来发现 Web 应用中的脆

弱点,适用于 SQL 注入、XSS 和命令注入等污点类漏洞的检测.而针对缓冲区溢出漏洞的检测,还需要知道某个

程序变量可能的取值范围.目前,数据流分析已被广泛应用于各种面向源代码的漏洞检测分析工具中,典型的工

具包括 FindBu gs

[4]

、Fortify SCA

[5]

、Coverity

[6]

、IBM Appscan Source Edition

[7]

和 Pinpoint

[8]

等.类似地,数据流

分析技术也可以用于二进制代码的漏洞检测与分析中,如 CodeSonar

[9]

在进行数据流分析时,由于构建传统数据依赖图(data depende nce graph,简称 DDG)的时间与空间复杂度高,

严重限制了可分析代码的规模.如何对数据依赖图进行改进,对于提升静态分析效率具有重要意义.本文提出了

函数级数据依赖图(function-level data dependence graph,简称 FDDG)的概念,设计了 FDDG 的构建方法,在保证

数据流准确性的同时,缩小数据依赖图的规模,显著降低数据依赖图的构建时间.实验结果表明:基于 FDDG 对

嵌入式固件进行脆弱性分析,在保证分析能力的情况下,能够极大地提升分析效率.

1 相关工作

近年来,数据依赖分析成为程序自动并行化、运行时调度和性能优化等应用中的研究热点.在程序自动并

行化的研究中,数据依赖分析是指令可并行性判别的重要方法.Ye 等人

[10]

通过离线分析代码块间数据依赖关

系,从而节省运行时的计算资源和开销.Abbas 等人

[11]

通过自适应采样方式生成近似的数据依赖图,避免通过代

码插装方式带来的运行时性能损失过高问题,但该方式会带来一定的精度损失.而 Li 等人

[12]

则提出了一种快速

数据依赖分析技术,允许跳过循环中重复执行的内存操作,在保证精度的同时,降低数据依赖分析的时间开销.

上述方法虽然降低了数据依赖分析的时间开销,但构建得到的数据依赖图包含大量与脆弱性分析无关的变量

信息,大大降低了变量回溯的效率,不适用于程序静态脆弱性分析.

在数据流分析中,函数摘要技术是过程间分析常用的技术

[13]

.通过为函数生成摘要信息,避免在不同上下文

对同一函数进行多次分析,从而简化过程间分析的复杂度.Rountev 等人

[14]

采用生成库代码摘要的方式来加快

数据流分析,但其时间复杂度较高,同时未考虑存在间接调用的情形.而 Tang 等人

[15]

提出了一个用于程序分析

的 TAL(tree-adjoini ng language )可达性框架,在降低开销的同时,解决了存在间接调用时库代码的摘要生成问题.

利用函数摘要技术,可以在一定程序上能够降低数据依赖分析的时间开销.但该技术与数据依赖图生成过程无

关,不能从结构上优化数据依赖图.

也有一些学者对数据依赖图进行了简单改进,以满足特定应用场景的需求.杨轶等人

[16]

在研究恶意代码相

似性比较方法时,对传统的数据依赖图进行了扩展——在数据依赖图中增加了恶意代码行为统计信息记录;之

后,通过对依赖图进行预处理以缩减图的规模;然后,基于扩展的依赖图进行相似性比较,以提升结果的准确性,

同时避免由于混淆、加壳等反制手段引起的干扰.

本文从依赖图构建的角度,提出了一种新的数据依赖图——函数级数据依赖图(FDDG).其核心思想是:在

考虑函数参数及参数间相互依赖关系的基础上,将函数作为整体进行分析,忽略函数内部的具体实现,从结构上

of 15

免费下载

软件学报计算机技术

关注

评论