计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (1): 29-49.doi: 10.1007/s11390-021-1663-7

所属专题： Software Systems； Theory and Algorithms

• • 上一篇    下一篇

DeltaFuzz：历史版本信息制导的模糊测试

  

  • 收稿日期:2021-06-01 修回日期:2021-11-28 接受日期:2021-12-16 出版日期:2022-01-28 发布日期:2022-01-28

DeltaFuzz: Historical Version Information Guided Fuzz Testing

Jia-Ming Zhang1 (张家铭), Zhan-Qi Cui1,* (崔展齐), Senior Member, CCF, Member, IEEE, Xiang Chen2 (陈翔), Senior Member, CCF, Member, IEEE, Huan-Huan Wu1 (吴欢欢), Li-Wei Zheng1 (郑丽伟), Member, CCF, and Jian-Bin Liu1 (刘建宾)        

  1. 1Computer School, Beijing Information Science and Technology University, Beijing 100101, China
    2School of Information Science and Technology, Nantong University, Nantong 226019, China
  • Received:2021-06-01 Revised:2021-11-28 Accepted:2021-12-16 Online:2022-01-28 Published:2022-01-28
  • Contact: Zhan-Qi Cui E-mail:czq@bistu.edu.cn
  • About author:Zhan-Qi Cui received his B.E. degree in software engineering and his Ph.D. degree in computer software and theory, in 2005 and 2011, respectively, both from Nanjing University, Nanjing. He was a visiting Ph.D. student in University of Virginia, Virginia, from Sept. 2009 to Sept. 2010. He is currently an associate professor at Beijing Information Science and Technology University, Beijing. His research interests include software analysis and testing.
  • Supported by:
    This work was partially supported by the Leading-Edge Technology Program of Jiangsu Natural Science Foundation of China under Grant No.BK20202001, the National Natural Science Foundation of China under Grant No.61702041, and the Beijing Information Science and Technology University "Qin-Xin Talent'' Cultivation Project under Grant No.QXTCP C201906.

PDF (PC)

101

补充材料

1

1、研究背景（Context）
随着敏捷开发等新型软件开发过程的被广泛应用，软件更新迭代得更为频繁。为保证软件质量，通常需要在新版本发布前进行回归测试。但是，人工设计有针对性的回归测试用例开销较大。模糊测试是一种自动生成测试用例的技术，它可以驱动被测程序执行测试用例，并监测被测程序运行情况。现有的模糊测试技术通常以高覆盖率为目标，而在回归测试过程中应重点关注新版本程序中被修改和影响到的位置，因此模糊测试技术难以直接应用于回归测试。
2、目的（Objective）
由于人工设计回归测试用例开销较大、覆盖率制导的模糊测试难以直接用于回归测试的原因，本文提出了历史版本信息制导的模糊测试方法。该方法通过历史版本差异比较和变更影响分析获取变更点与受影响的基本块，使模糊测试生成的测试用例更倾向于覆盖包含变更点的基本块，以将模糊测试技术应用于回归测试场景。
3、方法（Method）
首先，通过历史版本差异比较获取所有包含变更点的基本块；然后，进行变更影响分析，获得受变更点影响的基本块；最后，在测试过程中计算种子测试用例的适应度，适应度越高的测试用例会获得更多的测试资源，以产生更多的子代测试用例。此外，本文还通过覆盖包含变更点基本块数量、覆盖目标基本块时间、漏洞检测数量来评估所提出方法的有效性。
4、结果（Result & Findings）
我们实现了历史版本信息制导的模糊测试原型工具DeltaFuzz，并与AFLGo、AFLFast与AFL进行了对比实验。与AFLGo和AFLFast相比，DeltaFuzz覆盖包含变更点的基本块数量分别是它们的1.03与1.09倍，触发的缺陷数量分别是它们的1.07与1.20倍。与AFLGo，AFLFast和AFL相比，覆盖到目标基本块的总时间分别减少了20.59%，30.05%与32.61%。
5、结论（Conclusions）
本文中提出一种历史版本信息制导的模糊测试方法，并实现了原型工具DeltaFuzz。与其他目标制导的模糊测试工具相比，它无需获取已知漏洞所在的位置，可通过版本差异制导模糊测试，更适用于回归测试场景。在未来工作中，我们计划将符号执行与历史版本信息制导的模糊测试集成，以覆盖难以到达的变更点，并且将进一步优化适应度函数，以更合理地分配测试资源。

关键词: 模糊测试, 回归测试, 变更影响分析, 适应度函数

Abstract: With the widespread use of agile software development methods, such as agile and scrum, software is iteratively updated more frequently. To ensure the quality of the software, regression testing is conducted before new versions are released. Moreover, to improve the efficiency of regression testing, testing efforts should be concentrated on the modified and impacted parts of a program. However, the costs of manually constructing new test cases for the modified and impacted parts are relatively expensive. Fuzz testing is an effective method for generating test data automatically, but it is usually devoted to achieving higher code coverage, which makes fuzz testing unsuitable for direct regression testing scenarios. For this reason, we propose a fuzz testing method based on the guidance of historical version information. First, the differences between the program being tested and the last version are analyzed, and the results of the analysis are used to locate change points. Second, change impact analysis is performed to find the corresponding impacted basic blocks. Finally, the fitness values of test cases are calculated according to the execution traces, and new test cases are generated iteratively by the genetic algorithm. Based on the proposed method, we implement a prototype tool DeltaFuzz and conduct experiments on six open-source projects. Compared with the fuzzing tool AFLGo, AFLFast and AFL, DeltaFuzz can reach the target faster, and the time taken by DeltaFuzz was reduced by 20.59%, 30.05% and 32.61%, respectively.

Key words: fuzz testing, regression testing, change impact analysis, fitness function

[1] Masso J, Pino F J, Pardo C et al. Risk management in the software life cycle: A systematic literature review. Computer Standards & Interfaces, 2020, 71: Article No.103431. DOI: 10.1016/j.csi.2020.103431.
[2] Gu T, Ma X, Xu C et al. Synthesizing object transformation for dynamic software updating. In Proc. the 39th IEEE/ACM International Conference on Software Engineering Companion, May 2017, pp.336-338. DOI: 10.1109/ICSE-C.2017.96.
[3] Khatibsyarbini M, Isa M A, Jawawi D N A et al. Test case prioritization approaches in regression testing: A systematic literature review. Information and Software Technology, 2018, 93: 74-93. DOI: 10.1016/j.infsof.2017.08.014.
[4] Han J C, Zhou Z Q. Metamorphic fuzz testing of autonomous vehicles. In Proc. the 42nd IEEE/ACM International Conference on Software Engineering, June 27-July 19, 2020, pp.380-385. DOI: 10.1145/3387940.3392252.
[5] Dong Z, Böhme M, Cojocaru L et al. Time-travel testing of Android apps. In Proc. the 42nd IEEE/ACM International Conference on Software Engineering, June 27-July 19, 2020, pp.481-492. DOI: 10.1145/3377811.3380402.
[6] Qian J, Zhou D. Prioritizing test cases for memory leaks in Android applications. Journal of Computer Science and Technology, 2016, 31(5): 869-882. DOI: 10.1007/s11390-016-1670-2.
[7] Chen Y, Su T, Su Z. Deep differential testing of JVM implementations. In Proc. the 41st IEEE/ACM International Conference on Software Engineering, May 2019, pp.1257-1268. DOI: 10.1109/ICSE.2019.00127.
[8] Wüstholz V, Christakis M. Targeted greybox fuzzing with static lookahead analysis. In Proc. the 42nd IEEE/ACM International Conference on Software Engineering, June 27-July 19, 2020, pp.789-800. DOI: 10.1145/3377811.3380388.
[9] Böhme M, Manès V J M, Cha S K. Boosting fuzzer efficiency: An information theoretic perspective. In Proc. the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, November 2020, pp.678-689. DOI: 10.1145/3368089.3409748.
[10] Song S, Song C, Jang Y et al. CrFuzz: Fuzzing multi-purpose programs through input validation. In Proc. the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, November 2020, pp.690-700. DOI: 10.1145/3368089.3409769.
[11] Havrikov N. Efficient fuzz testing leveraging input, code, and ution. In Proc. the 39th IEEE/ACM International Conference on Software Engineering Companion, May 2017, pp.417-420. DOI: 10.1109/ICSE-C.2017.26.
[12] Klees G, Ruef A, Cooper B et al. Evaluating fuzz testing. In Proc. the 2018 ACM SIGSAC Conference on Computer and Communications Security, October 2018, pp.2123-2138. DOI: 10.1145/3243734.3243804.
[13] Zhang M Z, Gong Y Z, Wang Y W et al. Unit test data generation for C using rule-directed symbolic ution. Journal of Computer Science and Technology, 2019, 34(3): 670-689. DOI: 10.1007/s11390-019-1935-7.
[14] He J, Balunovic M, Ambroladze N et al. Learning to fuzz from symbolic ution with application to smart contracts. In Proc. the 2019 ACM SIGSAC Conference on Computer and Communications Security, November 2019, pp.531-548. DOI: 10.1145/3319535.3363230.
[15] Zhang Q, Wang J, Gulzar M A et al. BigFuzz: Efficient fuzz testing for data analytics using framework abstraction. In Proc. the 35th IEEE/ACM International Conference on Automated Software Engineering, September 2020, pp.722-733. DOI: 10.1145/3324884.3416641.
[16] Nguyen H L, Nassar N, Kehrer T et al. MoFuzz: A fuzzer suite for testing model-driven software engineering tools. In Proc. the 35th IEEE/ACM International Conference on Automated Software Engineering, September 2020, pp.1103-1115. DOI: 10.1145/3324884.3416668.
[17] Olsthoorn M, Van Deursen A, Panichella A. Generating highly-structured input data by combining search-based testing and grammar-based fuzzing. In Proc. the 35th IEEE/ACM International Conference on Automated Software Engineering, September 2020, pp.1224-1228. DOI: 10.1145/3324884.3418930.
[18] Nguyen T D, Pham L H, Sun J et al. sfuzz: An efficient adaptive fuzzer for solidity smart contracts. In Proc. the 42nd ACM/IEEE International Conference on Software Engineering, June 27-July 19, 2020, pp.778-788. DOI: 10.1145/3377811.3380334.
[19] Manès V J M, Kim S, Cha S K. Ankou: Guiding grey-box fuzzing towards combinatorial difference. In Proc. the 42nd ACM/IEEE International Conference on Software Engineering, June 27-July 19, 2020, pp.1024-1036. DOI: 10.1145/3377811.3380421.
[20] Böhme M, Pham V T, Nguyen M D et al. Directed greybox fuzzing. In Proc. the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 30-November 3, 2017, pp.2329-2344. DOI: 10.1145/3133956.3134020.
[21] Gao X, Saha R K, Prasad M R et al. Fuzz testing based data augmentation to improve robustness of deep neural networks. In Proc. the 42nd IEEE/ACM International Conference on Software Engineering, June 27-July 19, 2020, pp.1147-1158. DOI: 10.1145/3377811.3380415.
[22] Wen C, Wang H, Li Y et al. MemLock: Memory usage guided fuzzing. In Proc. the 42nd ACM/IEEE International Conference on Software Engineering, June 27-July 19, 2020, pp.765-777. DOI: 10.1145/3377811.3380396.
[23] Babic D, Bucur S, Chen Y et al. FUDGE: Fuzz driver generation at scale. In Proc. the 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, August 2019, pp.975-985. DOI: 10.1145/3338906.3340456.
[24] Chen H, Xue Y, Li Y et al. Hawkeye: Towards a desired directed grey-box fuzzer. In Proc. the 2018 ACM SIGSAC Conference on Computer and Communications Security, October 2018, pp.2095-2108. DOI: 10.1145/3243734.3243849.
[25] Medicherla R K, Komondoor R, Roychoudhury A. Fitness guided vulnerability detection with greybox fuzzing. In Proc. the 42nd IEEE/ACM International Conference on Software Engineering, June 27--July 19, 2020, pp.513-520. DOI: 10.1145/3387940.3391457.
[26] österlund S, Razavi K, Bos H et al. ParmeSan: Sanitizer-guided greybox fuzzing. In Proc. the 29th USENIX Security Symposium, August 2020, pp.2289-2306.
[27] Gao X, Mechtaev S, Roychoudhury A. Crash-avoiding program repair. In Proc. the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, July 2019, pp.8-18. DOI: 10.1145/3293882.3330558.
[28] Fioraldi A, Maier D, Eißfeldt H et al. AFL++: Combining incremental steps of fuzzing research. In Proc. the 14th USENIX Workshop on Offensive Technologies, August 2020.
[29] Grieco G, Ceresa M, Buiras P. QuickFuzz: An automatic random fuzzer for common file formats. ACM SIGPLAN Notices, 2016, 51(12): 13-20. DOI: 10.1145/2976002.2976017.
[30] Liang H, Zhang Y, Yu Y et al. Sequence coverage directed greybox fuzzing. In Proc. the 27th IEEE/ACM International Conference on Program Comprehension, May 2019, pp.249-259. DOI: 10.1109/ICPC.2019.00044.
[31] Zhang M, Liu J, Ma F et al. IntelliGen: Automatic driver synthesis for fuzz testing. In Proc. the 43rd IEEE/ACM International Conference on Software Engineering, May 2021, pp.318-327. DOI: 10.1109/ICSE-SEIP52600.2021.00041.
[32] You W, Liu X, Ma S et al. SLF: Fuzzing without valid seed inputs. In Proc. the 41st IEEE/ACM International Conference on Software Engineering, May 2019, pp.712-723. DOI: 10.1109/ICSE.2019.00080.
[33] Choi W, Sen K, Necul G et al. DetReduce: Minimizing Android GUI test suites for regression testing. In Proc. the 40th IEEE/ACM International Conference on Software Engineering, May 27-June 3, 2018, pp.445-455. DOI: 10.1145/3180155.3180173.
[34] Zhang L. Hybrid regression test selection. In Proc. the 40th IEEE/ACM International Conference on Software Engineering, May 27-June 3, 2018, pp.199-209. DOI: 10.1145/3180155.3180198.
[35] Nagy S, Hicks M. Full-speed fuzzing: Reducing fuzzing overhead through coverage-guided tracing. In Proc. the 2019 IEEE Symposium on Security and Privacy, May 2019, pp.787-802. DOI: 10.1109/SP.2019.00069.
[36] Liang J, Jiang Y, Wang M et al. DeepFuzzer: Accelerated deep greybox fuzzing. IEEE Transactions on Dependable and Secure Computing, 2019, 18(6): 2675-2688. DOI: 10.1109/TDSC.2019.2961339.
[37] Fioraldi A, D'Elia D C, Coppa E. WEIZZ: Automatic grey-box fuzzing for structured binary formats. In Proc. the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis, July 2020, pp.1-13. DOI: 10.1145/3395363.3397372.
[38] Chen Y, Poskitt C M, Sun J et al. Learning-guided network fuzzing for testing cyber-physical system defences. In Proc. the 34th IEEE/ACM International Conference on Automated Software Engineering, November 2019, pp.962-973. DOI: 10.1109/ASE.2019.00093.
[39] Peng H, Shoshitaishvili Y, Payer M. T-Fuzz: Fuzzing by program transformation. In Proc. the 2018 IEEE Symposium on Security and Privacy, May 2018, pp.697-710. DOI: 10.1109/SP.2018.00056.
[40] Padhye R, Lemieux C, Sen K. JQF: Coverage-guided property-based testing in Java. In Proc. the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, July 2019, pp.398-401. DOI: 10.1145/3293882.3339002.
[41] Noller Y, Kersten R, Pasareanu C S. Badger: Complexity analysis with fuzzing and symbolic ution. In Proc. the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, July 2018, pp.322-332. DOI: 10.1145/3213846.3213868.
[42] Zhou C, Wang M, Liang J et al. Zeror: Speed up fuzzing with coverage-sensitive tracing and scheduling. In Proc. the 35th IEEE/ACM International Conference on Automated Software Engineering, September 2020, pp.858-870. DOI: 10.1145/3324884.3416572.
[43] Wang T, Wei T, Gu G et al. TaintScope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection. In Proc. the 2010 IEEE Symposium on Security and Privacy, May 2010, pp.497-512. DOI: 10.1109/SP.2010.37.
[44] Lemieux C, Sen K. Fairfuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage. In Proc. the 33rd ACM/IEEE International Conference on Automated Software Engineering, September 2018, pp.475-485. DOI: 10.1145/3238147.3238176.
[45] Situ L, Wang L, Li X, Guan L, Zhang W, Liu P. Energy distribution matters in greybox fuzzing. In Proc. the 41st IEEE/ACM International Conference on Software Engineering, May 2019, pp.270-271. DOI: 10.1109/ICSE-Companion.2019.00109.
[46] Böhme M, Pham V T, Roychoudhury A. Coverage-based greybox fuzzing as Markov chain. IEEE Transactions on Software Engineering, 2017, 45(5): 489-506. DOI: 10.1109/TSE.2017.2785841.
[47] Wüstholz V, Christakis M. Harvey: A greybox fuzzer for smart contracts. In Proc. the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, November 2020, pp.1398-1409. DOI: 10.1145/3368089.3417064.
[48] Gan S, Zhang C, Qin X et al. CollAFL: Path sensitive fuzzing. In Proc. the 2018 IEEE Symposium on Security and Privacy, May 2018, pp.679-696. DOI: 10.1109/SP.2018.00040.
[1] 张根, 王鹏飞, 乐泰, 孔祥东, 周旭, 卢凯. ovAFLow：使用基于模糊测试的污点推理检测内存漏洞[J]. 计算机科学技术学报, 2022, 37(2): 405-422.
[2] 赵泽林, 黄頔, 马晓星. 软件动态更新中对象转换函数的自动测试[J]. 计算机科学技术学报, 2022, 37(1): 50-66.
[3] Ling-Yun Situ, Zhi-Qiang Zuo, Le Guan, Lin-Zhang Wang, Xuan-Dong Li, Jin Shi, Peng Liu. 漏洞区域感知的灰盒模糊测试[J]. 计算机科学技术学报, 2021, 36(5): 1212-1228.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 潘启敬;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[2] 黄国祥; 刘健;. A Key-Lock Access Control[J]. , 1987, 2(3): 236 -243 .
[3] 陈国良;. A Partitioning Selection Algorithm on Multiprocessors[J]. , 1988, 3(4): 241 -250 .
[4] 王海鹰;. A Framework for Command Recovery in User Interface[J]. , 1990, 5(3): 296 -301 .
[5] 沈一栋;. A Comparison of Closed World Assumptions[J]. , 1992, 7(3): 243 -246 .
[6] 沈一栋;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[7] 金芝;. The Structure and Semantics of an Object-Oriented Logic Programming Language: SCKE[J]. , 1995, 10(1): 74 -84 .
[8] 黄雄;. Some Undecidable Problems on Approximability of NP Optimization Problems[J]. , 1996, 11(2): 126 -132 .
[9] 秦开怀;. Representing Quadric Surfaces Using NURBS Surfaces[J]. , 1997, 12(3): 210 -216 .
[10] 孙济洲; Richard L;. A Radiosity Solution for Curved Surface Environments[J]. , 1997, 12(5): 414 -424 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：