基于符号执行与模糊测试的混合测试方法
作者:
作者单位:

作者简介:

谢肖飞(1989-),男,山西运城人,博士,主要研究领域为程序分析、测试,形式化验证;孟国柱(1987-),男,博士,副研究员,CCF专业会员,主要研究领域为软件与系统安全;李晓红(1965-),女,博士,教授,博士生导师,CCF高级会员,主要研究领域为安全软件工程,可信软件,信息安全;刘杨(1982-),男,博士,副教授,主要研究领域为Formal Methods,Security,Software Engineering,Multi-agent Systems;陈翔(1980-),男,博士,副教授,CCF高级会员,主要研究领域为软件缺陷预测,软件缺陷定位,回归测试,组合测试.

通讯作者:

李晓红,E-mail:xiaohongli@tju.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61572349,61272106)


Hybrid Testing Based on Symbolic Execution and Fuzzing
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61572349, 61272106)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    软件测试是保障软件质量的常用方法,如何获得高覆盖率是测试中十分重要且具有挑战性的研究问题.模糊测试与符号执行作为两大主流测试技术已被广泛研究并应用到学术界与工业界中,这两种技术都具有一定的优缺点:模糊测试随机变异生成测试用例并动态执行程序,可以执行并覆盖到较深的分支,但其很难通过变异的方法生成覆盖到复杂条件分支的测试用例.而符号执行依赖约束求解器,可以生成覆盖复杂条件分支的测试用例,但在符号化执行过程中往往会出现状态爆炸问题,因此很难覆盖到较深的分支.有工作已经证明,将符号执行与模糊测试相结合可以获得比单独使用模糊测试或者符号执行更好的效果.分析符号执行与模糊测试的优缺点,提出了一种基于分支覆盖将两种方法结合的混合测试方法——Afleer,结合双方优点从而可以生成具有更高分支覆盖率的测试用例.具体来说,模糊测试(例如AFL)为程序快速生成大量可以覆盖较深分支的测试用例,符号执行(例如KLEE)基于模糊测试的覆盖信息进行搜索,仅为未覆盖到的分支生成测试用例.为了验证Afleer的有效性,选取标准程序集LAVA-M以及实际项目oSIP作为评测对象,以漏洞检测能力以及覆盖能力作为评测指标.实验结果表明:(1)在漏洞检测能力上,Afleer总共可以发现755个漏洞,而AFL仅发现1个;(2)在覆盖能力上,Afleer在标准程序集上以及实际项目中都有不同程度的提升.其中,在oSIP中,Afleer比AFL在分支覆盖率上提高2.4倍,在路径覆盖率上提升6.1倍.除此之外,Afleer在oSIP中还检测出一个新的漏洞.

    Abstract:

    Software testing is a common way to guarantee software quality. How to achieve high coverage is a very important and challenging goal in testing. Fuzz testing and symbolic execution, as two mainstream testing techniques, have been widely studied and applied to academia and industry, both technologies have certain advantages and limitations. Fuzz testing can execute and cover deeper branches by randomly mutating test cases and dynamically executing programs. However, it is difficult to generate test cases that can cover complex conditional branches by random mutation. Symbolic execution can cover complex conditional branches with SMT solvers, but it is difficult to cover deeper branches due to state explosion during symbolic execution. Current works have shown that hybrid testing involving fuzzing and symbolic execution can archive better performance than fuzzing or symbolic execution. By analyzing the advantages and disadvantages in fuzzing and symbolic execution, this study proposes a branch coverage-based hybrid testing approach that combines the two methods with each other to achieve better test cases with high branch coverage. Specifically, fuzz testing (e.g., AFL) quickly generates a large number of test cases that can cover deeper branches, and symbolic execution (e.g., KLEE) performs a search based on the coverage of fuzz testing, and generating test cases for uncovered branches. To evaluate the effectiveness of Afleer, the study selects the standard benchmark LAVA-M and one real project oSIP as the evaluation object, and uses bug detection and coverage as the evaluation measures. The experimental results show that:1) For bug discovery, Afleer found 755 bugs while AFL only found 1; 2) For coverage, Afleer achieved some improvement on benchmarks and real project. In the project oSIP, Afleer increases the branch coverage by 2.4 times and the path coverage by 6.1 times. In addition, Afleer found a new bug in oSIP.

    参考文献
    相似文献
    引证文献
引用本文

谢肖飞,李晓红,陈翔,孟国柱,刘杨.基于符号执行与模糊测试的混合测试方法.软件学报,2019,30(10):3071-3089

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-08-29
  • 最后修改日期:2018-10-31
  • 录用日期:
  • 在线发布日期: 2019-05-16
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号