О методах извлечения алгоритмов из бинарного кода

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

1. D. Brumley, I. Jager, T. Avgerinos, E. J. Schwartz. BAP: A Binary Analysis Platform. In Proceedings of the 23rd International Conference on Computer Aided Verification. Snowbird, UT, 2011.

2. Y. Shoshitaishvili, R. Wang, C. Salls, N. Stephens, M. Polino, A. Dutcher, J. Grosen, S. Feng, C. Hauser, C. Kruegel,G. Vigna. SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis. IEEE Symposium on Security and Privacy, 2016.

3. The IDA Pro disassembler and debugger. [Online]. http://www.hex-rays.com/idapro/.

4. NSA, Ghidra is a software reverse engineering (SRE) framework. NSA. [Online]. https://github.com/NationalSecurityAgency/ghidra.

5. The Official Rizin Book. [Online]. https://book.rizin.re/.

6. ESIL: Radare2 book. [Online]. https://radare.gitbooks.io/radare2book/content/disassembling/esil.html.

7. Андрей Тихонов, Арутюн Аветисян, Вартан Падарян. Методика извлечения алгоритма из бинарного кода на основе динамического анализа. // Проблемы информационной безопасности. Компьютерные системы. №3 2008. стр. 66-71.

8. Retargetable Decompiler. [Online] https://retdec.com/.

9. Alessandro Di Federico, Mathias Payer, Giovanni Agosta. Rev.ng: a unified binary analysis framework to recover CFGs and function boundaries. In Proceedings of the 26th International Conference on Compiler Construction (CC 2017). Association for Computing Machinery, New York, NY, USA, pp. 131–141.

10. Reps T., Balakrishnan G. Improved memory-access analysis for x86 executables // Proceedings of the International Conference on Compiler Construction, April 2008.

11. Balakrishnan G., Reps T. DIVINE: DIscovering Variables IN Executables // Proceedings of the VMCAI. Nice, France. Jan. 14-16, 2007.

12. M. Weiser. Program Slicing. In Int. Conf. on Softw. Eng. IEEE Comp. Soc., Wash., DC, pp. 439–449, 1981

13. Michael Vaughn, Thomas Reps. A Generating-Extension-Generator for Machine Code. 2020.

14. Venkatesh Srinivasan and Thomas Reps. Partial Evaluation of Machine Code. SIGPLAN Not. 50, 10 (Oct. 2015), pp. 860–879.

15. Venkatesh Srinivasan, Thomas Reps. An improved algorithm for slicing machine code. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016). Association for Computing Machinery, New York, NY, USA, 378–393.

16. N. Jones, C. Gomard, P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Inc., 1993.

17. B. Yadegari, B. Johannesmeyer, B. Whitely, S. Debray. A generic approach to automatic deobfuscation of executable code. In S&P, 2015.

18. K. Coogan, G. Lu, S. Debray. Deobfuscation of virtualizationobfuscated software: A semantics-based approach. In CCS, 2011.

19. S. Bansal, A. Aiken. Automatic generation of peephole superoptimizers. In ASPLOS, 2006.

20. E. Schkufza, R. Sharma, A. Aiken. Stochastic superoptimization. In ASPLOS, 2013.

21. M. Abadi, M. Budiu, U. Erlingsson, J. Ligatti. Control-flow integrity. In CCS, 2005.

22. U. Erlingsson, F. Schneider. SASI enforcement of security policies: A retrospective. In Workshop on New Security Paradigms, 1999.

23. A. Slowinska, T. Stancescu, H. Bos. Body armor for binaries: Preventing buffer overflows without recompilation. In ATC, 2012.

24. L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, Univ. of Copenhagen, 1994.

25. C. Consel, L. Hornof, F. No¨el, J. Noy´e, and N. Volanschi. A uniform approach for compile-time and run-time specialization. Dagstuhl Seminar on Partial Evaluation, pages 54–72, 1996.

26. P. Kleinrubatscher, A. Kriegshaber, R. Z¨ochling, and R. Gl¨uck. Fortran program specialization. SIGPLAN Notices, 30(4), 1995.

27. П.М. Довгалюк, В.А. Макаров, В.А. Падарян, М.С. Романеев, Н.И. Фурсова. Применение программных эмуляторов в задачах анализа бинарного кода. Труды Института системного программирования РАН, том 26, вып. 1, 2014, стр. 277-296. DOI: 10.15514/ISPRAS-2014-26(1)-9.

28. A. B. Bugerya, I. I. Kulagin, V. A. Padaryan, M. A. Solovev, A. Y. Tikhonov, Recovery of High-Level Intermediate Representations of Algorithms from Binary Code," 2019 Ivannikov Memorial Workshop (IVMEM), 2019, pp. 57-63.

29. Z. Lin, X. Zhang, D. Xu. Automatic Reverse Engineering of Data Structures from Binary Execution. In Proceedings of the 11th Annual Information Security Symposium, West Lafayette, Indiana, 2010.

30. G. Ramalingam, J. Field, F. Tip. Aggregate Structure Identification and Its Application to Program Analysis. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Antonio, Texas, USA, 1999.