Комбинирование динамического символьного исполнения, статического анализа кода и фаззинга

В этой статье описывается новый подход для динамического анализа программ. Он совмещает динамическое символьное исполнение программ и статический анализ кода программ с фаззингом для повышения эффективности каждого из методов. В процессе фаззинга восстанавливаются вызовы по вычисляемым адресам и расширенный граф вызовов передается модулю статического анализа. Это позволяет улучшить вычисление путей исполнения программы в процессе статического анализа. Открытые новые пути исполнения в программе передаются модулю динамического символьного исполнения для генерации новых наборов внешних данных программы с целью исполнения и анализа программы по открытым путям исполнения. Новые наборы входных данных передаются модулю фаззинга для увеличения покрытия программы с их использованием в качестве затравки. Предложенный подход может быть использован в рамках классического алгоритма работы фаззинга с целью достижения высокого покрытия кода программы тестовыми наборами. Также предложенный метод может использоваться для направленного анализа путей и фрагментов кода программы. В этом случает фаззер формирует набор адресов и передает их модулю статического анализа. Статический анализ формирует набор путей, которые приводят к исполнению инструкций по этим адресам от точки входа в программу. Далее модуль динамическое символьного исполнения используется для построения наборов входных данных для прохождения по этим путям. Результаты экспериментов показывают высокую эффективность обнаружения программных ошибок при применении предложенного метода.

фаззинг, направленный фаззинг, статический анализ, обнаружение путей исполнения, динамическое символьное исполнение

1. . Fuzzing (online publication). Режим доступа: https://en.wikipedia.org/wiki/Fuzzing, 11.12.2018

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. . American fuzzy lop (online publication). Режим доступа: http://lcamtuf.coredump.cx/afl/, 11.12.2018

4. . A fork of AFL for fuzzing Windows binaries (online publication). Режим доступа: https://github.com/ivanfratric/winafl, 11.12.2018

5. . American fuzzy lop for network fuzzing (unofficial) (online publication). Режим доступа: https://github.com/jdbirdwell/afl, 11.12.2018

6. . Technical «whitepaper» for afl-fuzz (online publication). Режим доступа: http://lcamtuf.coredump.cx/afl/technical_details.txt, 11.12.2018

7. . QEMU (online publication). Режим доступа: https://www.qemu.org/, 11.12.2018

8. . libFuzzer – a library for coverage-guided fuzz testing (online publication). Режим доступа: https://llvm.org/docs/LibFuzzer.html, 11.12.2018

9. . The LLVM Compiler Infrastructure (online publication). Режим доступа: https://llvm.org, 11.12.2018

10. . Syzkaller is an unsupervised, coverage-guided kernel fuzzer (online publication). Режим доступа: https://github.com/google/syzkaller, 11.12.2018

11. . Peach (online publication). Режим доступа: https://www.peach.tech/products/peach-fuzzer/, 11.12.2018

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. . Исаев И.К., Сидоров Д.В., Герасимов А.Ю., Ермаков М.К. Avalanche: Применение динамического анализа для автоматического обнаружения ошибок в программах, использующих сетевые сокеты. Труды ИСП РАН, том 21, 2011, стр. 55-70

14. . Ермаков М.К., Герасимов А.Ю. Avalanche: применение параллельного и распределенного динамического анализа программ для ускорения поиска дефектов и уязвимостей. Труды ИСП РАН, том 25, 2013, стр. 29-38. doi:10.15514/ISPRAS-2013-25-2

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. . 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. . 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. . 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. . 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. . 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. . DynamoRIO (online publication). Режим доступа: http://www.dynamorio.org/, 11.12.2018.

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. . Cyber Grand Challenge (online publication). Режим доступа: https://www.darpa.mil/program/cyber-grand-challenge, 11.12.2018

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. . 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. . 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