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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(11):3421−3435 [doi: 10.13328/j.cnki.jos.005833] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

1,2
1,2
1,2
陈 千 1,2,3 , 程 凯 , 郑尧文 , 朱红松 , 孙利民 1,2
1
(物联网信息安全技术北京市重点实验室(中国科学院 信息工程研究所),北京 100093)
2
(中国科学院大学 网络空间安全学院,北京 100049)
3 (北京奇虎科技有限公司,北京 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.htm
英文引用格式: 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.htm

Function-level Data Dependence Graph and Its Application in Static Vulnerability Analysis

1,2
1,2
1,2
CHEN Qian 1,2,3 , CHENG Kai , ZHENG Yao-Wen , ZHU Hong-Song , SUN Li-Min 1,2
1 (Beijing Key Laboratory of IOT Information Security Technology (Institute of Information Engineering, Chinese Academy of Sciences),
Beijing 100093, China)
2 (School of Cyber Security, University of Chinese Academy of Science, Beijing 100049, China)
3 (Qihoo 360 Technology Co. Ltd., Beijing 100015, China)
Abstract: Data flow analysis plays an important role in binary code analysis. Due to consuming too much time and space, constructing
the traditional data dependence graph (DDG) limits the size of the analyzed code thoroughly. This study introduces a novel graph model,
function-level data dependence graph (FDDG), and proposes a corresponding construction method. The 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 inside the function. As a result, the size of the data dependence graph is reduced significantly. Also, the time
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