Combining dynamic symbolic execution, code static analysis and fuzzing

This paper describes a new approach for dynamic code analysis. It combines dynamic symbolic execution and static code analysis with fuzzing to increase efficiency of each component. During fuzzing we recover indirect function calls and pass that information to the static analysis engine. This improves static path detection in the control flow graph of a program. Detected paths are used in dynamic symbolic execution to construct inputs which will cover new paths during execution. These inputs are used by the fuzzing tool to improve test-case generation and increase code coverage. The proposed approach can be used for classic fuzzing when the main goal is achieving high code coverage. As well it can be used for targeted analysis of paths and code fragments in the program. In this case the fuzzing tool accepts a set of programs addresses with potential defects and passes them to the static analysis engine. The engine constructs all paths connecting program entry point to the given addresses. Finally, dynamic symbolic execution is used to construct the set of inputs, which will cover these paths. Experimental results have shown that the proposed method can effectively detect different program defects.

fuzzing, directed fuzzing, static analysis, path detection, dynamic symbolic execution

1. [1]. Fuzzing (online publication). Available at: https://en.wikipedia.org/wiki/Fuzzing, 11.12.2018

2. [2]. Ting Chen, Xiao-song Zhang, Shi-ze Guo, Hong-yuan Li, Yue Wu. State of the art: Dynamic symbolic execution for automated test generation. Future Generation Computer Systems, volume 29, issue 7, 2013, pp.1758-1773

3. [3]. American fuzzy lop (online publication). Available at: http://lcamtuf.coredump.cx/afl/, 11.12.2018

4. [4]. A fork of AFL for fuzzing Windows binaries (online publication). Available at: https://github.com/ivanfratric/winafl, 11.12.2018

5. [5]. American fuzzy lop for network fuzzing (unofficial) (online publication). Available at: https://github.com/jdbirdwell/afl, 11.12.2018

6. [6]. Technical «whitepaper» for afl-fuzz (online publication). Available at: http://lcamtuf.coredump.cx/afl/technical_details.txt, 11.12.2018

7. [7]. QEMU (online publication). Available at: https://www.qemu.org/, 11.12.2018

8. [8]. libFuzzer – a library for coverage-guided fuzz testing (online publication). Available at: https://llvm.org/docs/LibFuzzer.html, 11.12.2018

9. [9]. The LLVM Compiler Infrastructure (online publication). Available at: https://llvm.org, 11.12.2018

10. [10]. Syzkaller is an unsupervised, coverage-guided kernel fuzzer (online publication). Available at: https://github.com/google/syzkaller, 11.12.2018

11. [11]. Peach (online publication). Available at: https://www.peach.tech/products/peach-fuzzer/, 11.12.2018

12. [12]. Sevak Sargsyan, Shamil Kurmangaleev, Matevos Mehrabyan, Maksim Mishechkin, Tsolak Ghukasyan, Sergey Asryan. Grammar-Based Fuzzing. In Proc. of the Ivannikov Memorial Workshop. Yerevan, Armenia, 2018, pp. 32-36

13. [13]. Ildar Isaev, Denis Sidorov, Alexander Gerasimov, Mikhail Ermakov. Avalanche: Using dynamic analysis for automatic defect detection in programs based on network sockets. Trudy ISP RAN/Proc. ISP RAS, vol. 21, 2011, pp. 55-70

14. [14]. M.K. Ermakov, A.Y. Gerasimov. Avalanche: adaptation of parallel and distributed computing for dynamic analysis to improve performance of defect detection. Trudy ISP RAN/Proc. ISP RAS, vol. 25, 2013, pp. 29-38. doi:10.15514/ISPRAS-2013-25-2

15. [15]. Christoph Csallner, Nikolai Tillmann, Yannis Smaragdakis. DySy: Dynamic Symbolic Execution for Invariant Inference. In Proc. of the 30th international conference on Software, 2008, pp. 281-290

16. [16]. Robin David, Sebastien Bardin, Thanh Dinh Ta, Laurent Mounier, Josselin Feist, Marie-Laure Potet, Jean-Yves Marion. BINSEC/SE: A Dynamic Symbolic Execution Toolkit for Binary-level Analysis. In Proc. of the 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER), 2016, pp. 653-656

17. [17]. R.S. Boyer, B. Elspas, K.N. Levitt. SELECT – F Formal System for Testing and Debugging Programs by Symbolic Execution. In Proc. of the Internations Conference on Reliable software. pp. 234-245, Los Angeles, Califirnia, USA, Aprul 21-23, 1975

18. [18]. Jayaraman K.k, Harvison D., Ganesh V., Kiezun A. jFuzz: A Concolic Whitebox Fuzzer for Java. In Proc. of the First NASA Formal Methods Symposium, 2009, pp. 121-125

19. [19]. N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta, Y. Shoshitaishvili, C. Kruegel, G. Vigna. Driller: Augmenting fuzzing through selective symbolic execution. In Proc. of the 2016 Annual Network and Distributed System Security Symposium (NDSS), San Diego, CA, Feb. 2016

20. [20]. Li Zhang, Vrizlynn L. L. Thing. A hybrid symbolic execution assisted fuzzing method. In Proc. of the TENCON 2017 - 2017 IEEE Region 10 Conference, doi: 10.1109/TENCON.2017.8227972, 5-8 Nov. 2017

21. [21]. DynamoRIO (online publication). Available at: http://www.dynamorio.org/, 11.12.2018.

22. [22]. A. Gerasimov, S. Vartanov, M. Ermakov, L. Kruglov, D. Kutz, A. Novikov, S. Asryan. Anxiety: a dynamic symbolic execution framework. In Proc. of the 2017 Ivannikov ISPRAS Open Conference, 2017, pp. 16-21. doi:10.1109/ISPRAS.2017.00010

23. [23]. Cyber Grand Challenge (online publication). Available at: https://www.darpa.mil/program/cyber-grand-challenge, 11.12.2018

24. [24]. Yannic Nolle, Rody Kersten, Corina S. Păsăreanu. Badger: complexity analysis with fuzzing and symbolic execution. In Proc. of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 322-332, Amsterdam, Netherlands — July 16 - 21, 2018

25. [25]. Guowei Yang, Corina S. Păsăreanu, Sarfraz Khurshid. Memoized symbolic execution. In Proc. of the 2012 International Symposium on Software Testing and Analysis, pp. 144-154 Minneapolis, MN, USA — July 15 - 20, 2012

26. [26]. Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, Taesoo Kim. QSYM: a practical concolic execution engine tailored for hybrid fuzzing. In Proc. of the 27th USENIX Conference on Security Symposium, pp. 745-761, Baltimore, MD, USA — August 15 - 17, 2018