面向漏洞挖掘的基于符号分治区的测试用例生成技术

doi:10.3969/j.issn.1671-1122.2020.06.000

信息网络安全 ›› 2020, Vol. 20 ›› Issue (5): 39-46.doi: 10.3969/j.issn.1671-1122.2020.06.000

面向漏洞挖掘的基于符号分治区的测试用例生成技术

李明磊, 黄晖^*(), 陆余良

国防科技大学电子对抗学院,合肥 230009

收稿日期:2020-04-22 出版日期:2020-05-10 发布日期:2020-06-05
通讯作者: 黄晖 E-mail:hhui_123@163.com
作者简介:李明磊（1996—）,男,江苏,硕士研究生,主要研究方向为网络安全、漏洞挖掘与利用|黄晖（1987—）,男,江苏,讲师,博士,主要研究方向为二进制软件分析;|陆余良（1964—）,男,江苏,教授,硕士,主要研究方向为网络空间安全、漏洞挖掘与利用、网络态势感知
基金资助:
国家重点研发计划(2017YFB0802900)

Test Case Generation Technology Based on Symbol Divide and Conquer Area for Vulnerability Mining

LI Minglei, HUANG Hui^*(), LU Yuliang

College of Electronic Engineering, National University of Defense Technology, Hefei 230009, China

Received:2020-04-22 Online:2020-05-10 Published:2020-06-05
Contact: Hui HUANG E-mail:hhui_123@163.com

摘要/Abstract

摘要：

在漏洞挖掘中,符号执行技术是一种常用的测试用例生成技术。但当软件中包含加解密、校验和检验等复杂数学运算函数时,使用符号执行技术生成测试用例存在无法有效求解约束表达式的问题,导致漏洞挖掘效率低下。针对该问题,文章结合分治算法的思想提出基于符号分治区的测试用例生成技术。首先通过静态分析技术识别软件中的加解密、校验和检验等函数;然后以程序中的加解密、校验和检验函数为分界点对软件进行分区,符号执行引擎每执行到软件的一个分治区,就在本区引入一个新的符号变元进行约束构建,在约束求解时从软件最后一个分治区开始递归求解。基于该方法,文章在符号执行平台S2E上实现了漏洞挖掘原型系统Divide,并与现有的符号执行生成测试用例技术进行对比实验。实验结果表明,文章方法能够快速、有效地生成测试用例,提高漏洞挖掘的效率。

关键词: 符号执行, 约束求解, 测试用例生成, 静态分析, 漏洞挖掘

Abstract:

In vulnerability mining, symbol execution technology is a common test case generation technology. However, when the software contains complex mathematical operation functions such as encryption and decryption, checksum verification, using symbol execution technology to generate test cases cannot effectively solve constraint expressions, which results in low efficiency in vulnerability mining. In order to solve this problem, combining the idea of divide and conquer algorithm, this paper proposes a test case generation technique based on symbol divide and conquer area. Firstly, the functions of encryption and decryption, checksum verification in software are identified through static analysis technology. Then using the functions of encryption and decryption, checksum verification in the program as the partition point to partition the software. Every time the symbol execution engine executes to a divide and conquer area of software, a new symbol variable is introduced into this area for constraint construction. When solving constraints, the software will start to solve recursively from the last divide and conquer area of software. Based on this method, this paper implements a vulnerability mining prototype system Divide on the symbolic execution platform S2E, and compares with the existing symbol execution generation test case technologies. The experimental results show that this method can generate test cases quickly and effectively, and improve the efficiency of vulnerability mining.

Key words: symbol execution, constraint solving, test case generation, static analysis, vulnerability mining

中图分类号:

TP309

李明磊, 黄晖, 陆余良. 面向漏洞挖掘的基于符号分治区的测试用例生成技术[J]. 信息网络安全, 2020, 20(5): 39-46.

LI Minglei, HUANG Hui, LU Yuliang. Test Case Generation Technology Based on Symbol Divide and Conquer Area for Vulnerability Mining[J]. Netinfo Security, 2020, 20(5): 39-46.

图/表 8

图1

图2

图3

表1

图4

图5

图6

图7

参考文献 20

[1]	DONG Qixing . Research on Test Case Generation Technology Based on Dynamic Symbol Execution[D]. Hefei:University of Science and Technology of China, 2014.
	董齐兴 . 基于动态符号执行的测试用例生成技术研究[D]. 合肥:中国科学技术大学, 2014.
[2]	RENFER G . Automatic Program Testing [EB/OL]. https://link.springer.com/book/10.1007/978-3-319-30348-2, 1962/2020, 2020-4-10.
[3]	MILLER B P, FREDRIKSEN L, SO B . An Empirical Study of the Reliability of UNIX Utilities[J]. Communications of the ACM, 1990,33(12):32-44.
[4]	CHEN Jianmin, SHU Hui, XIONG Xiaobing . Fuzzing Test Method Based on Symbolic Execution[J]. Computer Engineering, 2009,35(21):33-35.
	陈建敏, 舒辉, 熊小兵 . 基于符号化执行的 Fuzzing 测试方法[J]. 计算机工程, 2009; 35(21):33-35.
[5]	CHA S K, AVGERINOS T, REBERT A , et al. Unleashing Mayhem on Binary Code [C]//IEEE. 2012 IEEE Symposium on Security and Privacy, May 20-23, 2012, San Francisco, CA, USA. NJ: IEEE, 2012: 380-394.
[6]	STEPHENS N, GROSEN J, SALLS C , et al. Driller: Augmenting Fuzzing Through Selective Symbolic Execution[EB/OL]. https://sefcom.asu.edu/publications/driller:augmenting-fuzzing-through-selective-symbolic-execution-ndss2016.pdf, 2020-4-10.
[7]	RAWAT S, JAIN V, KUMAR A , et al. VUzzer: Application-aware Evolutionary Fuzzing[EB/OL]. http://sharcs-project.eu/m/filer_public/48/8c/488c5fb7-9aad-4c87-ab9c-5ff251ebc73d/vuzzer_ndss17.pdf, 2020-4-10.
[8]	JOHANSSON W, SVENSSON M, LARSON U E , et al. T-Fuzz: Model-Based Fuzzing for Robustness Testing of Telecommunication Protocols [C]//IEEE. 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation, March 31-April 4, 2014, Cleveland, OH, USA. NJ: IEEE, 2014: 323-332.
[9]	GANESH V, DILL D L . A Decision Procedure for Bit-vectors and Arrays[M] //Springer. Computer Aided Verification. Heidelberg: Springer, Berlin, Heidelberg, 2007: 519-531.
[10]	DE MOURA L, BJORNER N . Z3: An Efficient SMT Solver[M] //Springer. Tools and Algorithms for the Construction and Analysis of Systems. Heidelberg: Springer, Berlin, Heidelberg, 2008: 337-340.
[11]	CHIPOUNOV V, KUZNETSOV V, CANDEA G . S2E: A Platform for In-vivo Multi-path Analysis of Software Systems[EB/OL]. https://www.ndsl.kaist.edu/~kyoungsoo/ee807_2014/papers/s2e.pdf, 2020-4-10.
[12]	Shellphish . Angr[EB/OL]. https://github.com/angr/, 2020-4-7.
[13]	HUANG S K, HUANG M H, HUANG P Y , et al. CRAX: Software Crash Analysis for Automatic Exploit Generation by Modeling Attacks as Symbolic Continuations [C]//IEEE. 2012 IEEE Sixth International Conference on Software Security and Reliability, June 20-22, 2012, Gaithersburg, MD, USA. NJ: IEEE, 2012: 78-87.
[14]	WANG Yan, ZHANG Chao, XIANG Xiaobo , et al. Revery: from Proof-of-concept to Exploitable[EB/OL]. https://www.researchgate.net/publication/328321653_Revery_From_Proof-of-Concept_to_Exploitable, 2020-4-10.
[15]	GODEFROID P, LEVIN M Y, MOLNAR D . SAGE: Whitebox Fuzzing for Security Testing[J]. Communications of the ACM, 2012,55(3):40-44.
[16]	BALDONI R, COPPA E, D’ELIA D C , et al. A Survey of Symbolic Execution Techniques[EB/OL]. https://arxiv.org/abs/1610.00502, 2020-4-10.
[17]	HOU Gang, ZHOU Kuanjiu, YONG Jiawei , et al. A Review of Research on State Explosion in Model Detection[J]. Computer Science, 2013,40(S1):77-86, 111.
	侯刚, 周宽久, 勇嘉伟 , 等. 模型检测中状态爆炸问题研究综述[J]. 计算机科学, 2013,40(S1):77-86,111.
[18]	BELLARD F. QEMU , A Fast and Portable Dynamic Translator[EB/OL]. https://www.mendeley.com/catalogue/e628a8cb-4d09-36c3-bf08-824b8a481808/, 2020-4-10.
[19]	CADAR C, DUNBAR D, ENGLER D . Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs[EB/OL]. https://static.usenix.org/events/osdi08/tech/full_papers/cadar/cadar.pdf, 2009/2020, 2020-4-10.
[20]	LATTNER C, ADVE V . LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation [C]//IEEE. InInternational Symposium on Code Generation and Optimization, March 20-24, 2004, San Jose, CA, USA. NJ: IEEE, 2004: 75-86.

求解目标	工具	TTE/ms	Improve
Code3	Divide	171340	1.236
Code3	CRAX	211875	—
Code5	Divide	107541	NULL
Code5	CRAX	—	—
Pwn11	Divide	55548	4.05
Pwn11	CRAX	225444	—
Pwn18	Divide	143010	1.87
Pwn18	CRAX	267814	—
Pwn48	Divide	554628	NULL
Pwn48	CRAX	—	—
Pwn52	Divide	218328	1.36
Pwn52	CRAX	297342	—

面向漏洞挖掘的基于符号分治区的测试用例生成技术

Test Case Generation Technology Based on Symbol Divide and Conquer Area for Vulnerability Mining

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杜笑宇, 叶何, 文伟平. 基于字节码搜索的Java反序列化漏洞调用链挖掘方法[J]. 信息网络安全, 2020, 20(7): 19-29.
[2]	段斌, 李兰, 赖俊, 詹俊. 基于动态污点分析的工控设备硬件漏洞挖掘方法研究[J]. 信息网络安全, 2019, 19(4): 47-54.
[3]	胡建伟, 赵伟, 闫峥, 章芮. 基于机器学习的SQL注入漏洞挖掘技术的分析与实现[J]. 信息网络安全, 2019, 19(11): 36-42.
[4]	陈虎, 周瑶, 赵军锁. 针对特定文件结构和关键指令的符号执行优化方法[J]. 信息网络安全, 2018, 18(9): 86-94.
[5]	王夏菁, 胡昌振, 马锐, 高欣竺. 二进制程序漏洞挖掘关键技术研究综述[J]. 信息网络安全, 2017, 17(8): 1-13.
[6]	彭建山, 奚琪, 王清贤. 二进制程序整型溢出漏洞的自动验证方法[J]. 信息网络安全, 2017, 17(5): 14-21.
[7]	郭亮, 罗森林, 潘丽敏. 编码函数交叉定位网络协议测试数据生成方法研究[J]. 信息网络安全, 2016, 16(3): 8-14.
[8]	李汶洋. Android操作系统恶意软件检测技术研究[J]. 信息网络安全, 2015, 15(9): 62-65.
[9]	张帆, 钟章队. 基于权限分析的手机恶意软件检测与防范[J]. 信息网络安全, 2015, 15(10): 66-73.
[10]	. 基于模糊测试的网络协议自动化漏洞挖掘工具设计与实现[J]. , 2014, 14(6): 23-.
[11]	陈震;许建林;余奕凡;刘洪健. 移动网络软件架构中的安全技术研究[J]. , 2013, 13(12): 0-0.
[12]	崔化良;兰芸;崔宝江. 动态污点分析技术在ActiveX控件漏洞挖掘上的应用[J]. , 2013, 13(12): 0-0.
[13]	黄超;李毅;麻荣宽;马建勋. 网页漏洞挖掘系统设计[J]. , 2012, 12(9): 0-0.
[14]	李向东;刘晓;夏冰;郑秋生. 恶意代码检测技术及其在等级保护工作中的应用[J]. , 2012, 12(8): 0-0.
[15]	舒心;王永伦;张鑫. 手机病毒分析与防范[J]. , 2012, 12(8): 0-0.