tuzsutТруды учебных заведений связиProceedings of Telecommunication Universities1813-324X2712-8830СПбГУТ10.31854/1813-324X-2025-11-4-129-142UOKLHBtuzsut-704Research ArticleИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ТЕЛЕКОММУНИКАЦИИINFORMATION TECHNOLOGIES AND TELECOMMUNICATIONРеверс-инжиниринг программного обеспечения методом смарт-перебора: пошаговая схемаReverse Engineering of Software Using the Smart Brute Force Method: Step-by-Step Schemehttps://orcid.org/0000-0002-9412-5693ИзраиловК. Е.IzrailovK. E.

кандидат технических наук, доцент, профессор кафедры прикладной математики и безопасности информационных технологий Санкт-Петербургского университета государственной противопожарной службы МЧС России 

konstantin.izrailov@mail.ruhttps://orcid.org/0000-0001-8146-0022БуйневичМ. В.BuinevichM. V.

доктор технических наук, профессор, профессор кафедры КБ-4 МИРЭА – Российского технологического университета

bmv1958@yandex.ruСанкт-Петербургский университет государственной противопожарной службы МЧС РоссииРоссияSaint-Petersburg University of State Fire Service of EMERCOM of RussiaRussian FederationМИРЭА – Российский технологический университетРоссияMIREA – Russian Technological UniversityRussian Federation202501092025114129142Copyright © Израилов К.Е., Буйневич М.В., 20252025Израилов К.Е., Буйневич М.В.Izrailov K.E., Buinevich M.V.This work is licensed under a Creative Commons Attribution 4.0 License.https://tuzs.sut.ru/jour/article/view/704Актуальность

Актуальность. Наличие уязвимостей в программном обеспечении является одной из основных причин возникновения угроз безопасности информации. Противодействие уязвимостям возможно путем их непосредственного поиска в коде программы с его последующим исправлением. Для этого требуется преобразование исполняемого кода в более высокоуровневое и пригодное для поиска и исправления представление (например, в исходный код, алгоритмы, архитектуру и др.); однако существующие решения не могут считаться удовлетворительными по целому ряду причин – поддержка лишь ограниченного набора представлений, получение не тождественного выполняемому псевдокода, невозможность выбора нужной нотации представления. Одним из путей устранения указанных причин является применение полного перебора, который впрочем в случае исходного кода является сверхзатратным по всем параметрам.

Цель исследования

Цель исследования: разработать менее затратный и более оперативный метод перебора вариантов исходного кода.

Методы

Методы: количественное и качественное сравнение различных генераторов исходных кодов; формализация метода путем его записи в аналитическом виде.

Результаты

Результаты: предложена 7-шаговая схема метода для подбора экземпляра исходного кода по заданному машинному коду; метод является «умным» (называемый авторами смарт) с позиции оптимальности комбинаций синтаксических конструкций языка программирования. Авторский принцип генерации кода основан на переборе путей по графу синтаксических правил, являющимся представлением формального синтаксиса языка программирования в пространстве. Синтаксис передается в метод в качестве параметра, что делает его шаги полностью инвариантными от языка программирования исходного кода. После генерации множества экземпляров исходного кода производится их компиляция в машинный и сравнение с заданным; при совпадении задача декомпиляции методом умного перебора считается решенной. Предложенный метод может быть адаптирован для других (и, в частности, более высокоуровневых) представлений программы.

Практическая значимость

Практическая значимость: несмотря на очевидную временную затратность перебора при решении такого рода задач, тем не менее, в ряде сценариев применения метод смарт-перебора показал эффективность, сравнимую с работой эксперта, и может непосредственно применяться для реверс-инжиниринга.

Обсуждение

Обсуждение: существенным усовершенствованием «умного» перебора может стать его качественная оптимизация путем применения искусственного интеллекта в части генетических алгоритмов.

Introduction

Introduction: software vulnerabilities is one of the leading causes of threats to information security. Such vulnerabilities can be countered by directly searching for them in the program code and correcting it. This requires converting the executable code to a higher-level representation that's more suitable for searching and fixes; however, for a number of reasons, existing solutions cannot be considered satisfactory. One of these solutions – an exhaustive search of all possible variants of the source code, converted to a given machine code – is extremely costly in every way.

Purpose

Purpose: developing a less costly and more efficient method of exhaustive searching through source code variants.

Methods

Methods: quantitative and qualitative comparison of different source code generators, as well as the formalization of this method by writing it in an analytical form.

Results

Results: a 7-step scheme for selecting an instance of the source code according to a given machine code is proposed; the authors refer to this method as «smart» because of its optimal combinations of syntactic constructions of the programming language. This method of code generation is based on iterating through paths along the graph of syntactic rules that represent the formal syntax of a programming language in a given space. The syntax is presented as a parameter, which makes its steps completely invariant from the programming language of the source code. After multiple instances of the source code are generated, they are compiled into machine code and compared with the specified instance; if they match, the task of decompilation by smart exhaustive search is considered solved.

Practical significance

Practical significance: despite the time cost of using exhaustive searching in solving such tasks, the smart iteration method has shown expert efficiency in a number of application scenarios; thus, it can be directly applied to reverse engineering.

Discussion

Discussion: the qualitative optimization of the "smart" exhaustive search can significantly improve it by genetic algorithms used.

уязвимости в программном обеспеченииугроза безопасности информацииреверс-инжинирингдекомпиляцияметодсмарт-переборисходный кодмашинный кодinformation securityreverse engineeringdecompilationmethodsmart brute-forcesource codemachine codeReferencesTan T.-T., Wang B.-S., Tang Y., Zhou X. Crash Analysis Mechanisms in Vulnerability Mining Research // Proceedings of the 4th International Conference on Computer and Communication Systems (Singapore, Singapore, 23‒25 February 2019). IEEE, 2019. PP. 355‒359. DOI:10.1109/CCOMS.2019.8821775Tan T.-T., Wang B.-S., Tang Y., Zhou X. Crash Analysis Mechanisms in Vulnerability Mining Research. Proceedings of the 4th International Conference on Computer and Communication Systems, 23‒25 February 2019, Singapore, Singapore. IEEE; 2019. p.355‒359. DOI:10.1109/CCOMS.2019.8821775Chondamrongkul N., Sun J., Warren I. Automated Security Analysis for Microservice Architecture // Proceedings of the International Conference on Software Architecture Companion (Salvador, Brazil, 16‒20 March 2020). IEEE, 2020. PP. 79‒82. DOI:10.1109/ICSA-C50368.2020.00024Chondamrongkul N., Sun J., Warren I. Automated Security Analysis for Microservice Architecture. Proceedings of the International Conference on Software Architecture Companion, 16‒20 March 2020, Salvador, Brazil. IEEE; 2020. p.79‒82. DOI:10.1109/ICSA-C50368.2020.00024Iannone E., Guadagni R., Ferrucci F., De Lucia A., Palomba F. The Secret Life of Software Vulnerabilities: a Large-Scale Empirical Study // IEEE Transactions on Software Engineering. 2023. Vol. 49. Iss. 1. PP. 44‒63. DOI:10.1109/TSE.2022.3140868. EDN:GKKIKOIannone E., Guadagni R., Ferrucci F., De Lucia A., Palomba F. The Secret Life of Software Vulnerabilities: a Large-Scale Empirical Study. IEEE Transactions on Software Engineering. 2023;49(1):44‒63. DOI:10.1109/TSE.2022.3140868. EDN:GKKIKOFu J., Zhang K., Zheng J., Li W., Zhu Y. Research and Application of Grey Box Detection Technology Based on Reverse Engineering and Dynamic Pollution Diffusion // Proceedings of the 7th Information Technology and Mechatronics Engineering Conference (Chongqing, China, 15‒17 September 2023). IEEE, 2023. PP. 2380‒2384. DOI:10.1109/ITOEC57671.2023.10291380Fu J., Zhang K., Zheng J., Li W., Zhu Y. Research and Application of Grey Box Detection Technology Based on Reverse Engineering and Dynamic Pollution Diffusion. Proceedings of the 7th Information Technology and Mechatronics Engineering Conference, 15‒17 September 2023, Chongqing, China. IEEE; 2023. p.2380‒2384. DOI:10.1109/ITOEC57671.2023.10291380Devine T.R., Campbell M., Anderson M., Dzielski D. SREP+SAST: A Comparison of Tools for Reverse Engineering Machine Code to Detect Cybersecurity Vulnerabilities in Binary Executables // Proceedings of the International Conference on Computational Science and Computational Intelligence (Las Vegas, USA, 14‒16 December 2022). IEEE, 2022. PP. 862‒869. DOI:10.1109/CSCI58124.2022.00156Devine T.R., Campbell M., Anderson M., Dzielski D. SREP+SAST: A Comparison of Tools for Reverse Engineering Machine Code to Detect Cybersecurity Vulnerabilities in Binary Executables. Proceedings of the International Conference on Computational Science and Computational Intelligence, 14‒16 December 2022, Las Vegas, USA. IEEE; 2022. p.862‒869. DOI:10.1109/CSCI58124.2022.00156Bhardwaj V., Kukreja V., Sharma C., Kansal I., Popali R. Reverse Engineering-A Method for Analyzing Malicious Code Behavior // Proceedings of the International Conference on Advances in Computing, Communication, and Control (Mumbai, India, 03‒04 December 2021). IEEE, 2021. PP. 1‒5. DOI:10.1109/ICAC353642.2021.9697150Bhardwaj V., Kukreja V., Sharma C., Kansal I., Popali R. Reverse Engineering-A Method for Analyzing Malicious Code Behavior. Proceedings of the International Conference on Advances in Computing, Communication, and Control, 03‒04 December 2021, Mumbai, India. IEEE; 2021. p.1‒5. DOI:10.1109/ICAC353642.2021.9697150Израилов К.Е., Покусов В.В. Архитектура программной платформы преобразования машинного кода в высоко-уровневое представление для экспертного поиска уязвимостей // Электронный сетевой политематический журнал «Научные труды КубГТУ». 2021. № 6. С. 93‒111. EDN:AIOUWFIzrailov K.E., Pokusov V.V. Software platform architecture for converting machine code into a high-level representation for expert search of vulnerabilities. Scientific Works of the Kuban State Technological University. 2021;6:93‒111. (in Russ.) EDN:AIOUWFБуйневич М.В., Израилов К.Е., Покусов В.В., Тайлаков В.А., Федулина И.Н. Интеллектуальный метод алгоритмизации машинного кода в интересах поиска в нем уязвимостей // Защита информации. Инсайд. 2020. № 5(95). С. 57‒63. EDN:HIHDOMBuinevich M.V., Izrailov K.E., Pokusov V.V., Tailakov V.A., Fedulina I.N. An intelligent method of machine code algorithmization for vulnerabilities search. Zaŝita informacii. Inside. 2020;5(95):57‒63. (in Russ.) EDN:HIHDOMCummins C., Fisches Z.V., Ben-Nun T., Hoefler T., O'Boyle M.F.P., Leather H. ProGraML: A Graph-based Program Representation for Data Flow Analysis and Compiler Optimizations // Proceedings of the 38th International Conference on Machine Learning (PMLR, 18‒24 July 2021). 2021. Vol. 139. PP. 2244‒2253.Cummins C., Fisches Z.V., Ben-Nun T., Hoefler T., O'Boyle M.F.P., Leather H. ProGraML: A Graph-based Program Representation for Data Flow Analysis and Compiler Optimizations. Proceedings of the 38th International Conference on Machine Learning, PMLR, 18‒24 July 2021, vol.139. 2021. p.2244‒2253.Израилов К.Е. Концепция генетической декомпиляции машинного кода телекоммуникационных устройств // Труды учебных заведений связи. 2021. Т. 7. № 4. С. 95‒109. DOI:10.31854/1813-324X-2021-7-4-95-109. EDN:AIOFPMIzrailov K. Genetic Decompilation Concept of the Telecommunication Devices Machine Code. Proceedings of Telecommunication Universities. 2021;7(4):10‒17. (in Russ.) DOI:10.31854/1813-324X-2021-7-4-95-109. EDN:AIOFPMTonis R.B.M. Automating Scientific Paper Screening with Backus-Naur Form (BNF) Grammars // Didactica danubiensis. 2024. Vol. 4. Iss. 1. PP. 46–57.Tonis R.B.M. Automating Scientific Paper Screening with Backus-Naur Form (BNF) Grammars. Didactica danubiensis. 2024;4(1):46–57.Израилов К.Е. Концепция генетической деэволюции представлений программы. Часть 1 // Вопросы кибербезопасности. 2024. № 1(59). С. 61‒66. DOI:10.21681/2311-3456-2024-1-61-66. EDN:CBCKRFIzrailov K.E. The genetic de-evolution concept of program representations. Part 1. Voprosy kiberbezopasnosti. 2024;1(59): 61‒66. (in Russ.) DOI:10.21681/2311-3456-2024-1-61-66. EDN:CBCKRFИзраилов К.Е. Концепция генетической деэволюции представлений программы. Часть 2 // Вопросы кибербезопасности. 2024. № 2(60). С. 81‒86. DOI:10.21681/2311-3456-2024-2-81-86. EDN:JUBPMLIzrailov K.E. The genetic de-evolution concept of program representations. Part 2. Voprosy kiberbezopasnosti. 2024;2(60): 81‒86. (in Russ.) DOI:10.21681/2311-3456-2024-2-81-86. EDN:JUBPMLHamberger P., Klammer C., Luger T., Moser M., Pfeiffer M., Piereder C. Specification-Based Test Case Generation for C++ Engineering Software // Proceedings of the International Conference on Software Maintenance and Evolution (ICSME, Bogotá, Colombia, 01‒06 October 2023). IEEE, 2023. PP. 519‒529. DOI:10.1109/ICSME58846.2023.00066Hamberger P., Klammer C., Luger T., Moser M., Pfeiffer M., Piereder C. Specification-Based Test Case Generation for C++ Engineering Software. Proceedings of the International Conference on Software Maintenance and Evolution, ICSME, 01‒06 October 2023, Bogotá, Colombia. IEEE; 2023. p.519‒529. DOI:10.1109/ICSME58846.2023.00066Sato Y. Specification-Based Test Case Generation with Constrained Genetic Programming // Proceedings of the 20th International Conference on Software Quality, Reliability and Security Companion (QRS-C, Macau, China, 11‒14 December 2020). IEEE, 2020. PP. 98‒103. DOI:10.1109/QRS-C51114.2020.00027Sato Y. Specification-Based Test Case Generation with Constrained Genetic Programming. Proceedings of the 20th International Conference on Software Quality, Reliability and Security Companion, QRS-C, 11‒14 December 2020, Macau, China. IEEE; 2020. p.98‒103. DOI:10.1109/QRS-C51114.2020.00027Huang C., Zhou H., Zhao H., Cai W., Zhou Z.Q., Jiang M. On the Usefulness of Crossover in Search-Based Test Case Generation: An Industrial Report // Proceedings of the 29th Asia-Pacific Software Engineering Conference (APSEC, Japan, 06‒09 December 2022). IEEE, 2022. PP. 417‒421. DOI:10.1109/APSEC57359.2022.00054Huang C., Zhou H., Zhao H., Cai W., Zhou Z.Q., Jiang M. On the Usefulness of Crossover in Search-Based Test Case Generation: An Industrial Report. Proceedings of the 29th Asia-Pacific Software Engineering Conference, APSEC, 06‒09 December 2022, Japan. IEEE; 2022. p.417‒421. DOI:10.1109/APSEC57359.2022.00054Schwachhofer D., Angione F., Becker S., Wagner S., Sauer M., Bernardi P., Polian I. Optimizing System-Level Test Program Generation via Genetic Programming // Proceedings of the European Test Symposium (ETS, The Hague, Netherlands, 20‒24 May 2024). IEEE, 2024. PP. 1‒4. DOI:10.1109/ETS61313.2024.10567817Schwachhofer D., Angione F., Becker S., Wagner S., Sauer M., Bernardi P., Polian I. Optimizing System-Level Test Program Generation via Genetic Programming. Proceedings of the European Test Symposium, ETS, 20‒24 May 2024, The Hague, Netherlands. IEEE; 2024. p.1‒4. DOI:10.1109/ETS61313.2024.10567817Supaartagorn C. Web application for automatic code generator using a structured flowchart // Proceedings of the International Conference on Software Engineering and Service Science (ICSESS, Beijing, China, 24‒26 November 2017). IEEE, 2017. PP. 114‒117. DOI:10.1109/ICSESS.2017.8342876Supaartagorn C. Web application for automatic code generator using a structured flowchart. Proceedings of the International Conference on Software Engineering and Service Science, ICSESS, 24‒26 November 2017, Beijing, China. IEEE; 2017. p.114‒117. DOI:10.1109/ICSESS.2017.8342876Shinde K., Sun Y. Template-Based Code Generation Framework for Data-Driven Software Development // Proceedings of the 4th Intl Conf on Applied Computing and Information Technology / 3rd Intl Conf on Computational Science / Intelligence and Applied Informatics / 1st Intl Conf on Big Data, Cloud Computing, Data Science & Engineering (ACIT-CSII-BCD, Las Vegas, USA, 12‒14 December 2016). IEEE, 2016. PP. 55‒60. DOI:10.1109/ACIT-CSII-BCD.2016.023Shinde K., Sun Y. Template-Based Code Generation Framework for Data-Driven Software Development. Proceedings of the 4th Intl Conf on Applied Computing and Information Technology / 3rd Intl Conf on Computational Science / Intelligence and Applied Informatics / 1st Intl Conf on Big Data, Cloud Computing, Data Science & Engineering, ACIT-CSII-BCD, 12‒14 December 2016, Las Vegas, USA. IEEE; 2016. p.55‒60. DOI:10.1109/ACIT-CSII-BCD.2016.023Shimonaka K., Sumi S., Higo Y., Kusumoto S. Identifying Auto-Generated Code by Using Machine Learning Techniques // Proceedings of the 7th International Workshop on Empirical Software Engineering in Practice (IWESEP, Osaka, Japan, 13 March 2016). IEEE, 2016. PP. 18‒23. DOI:10.1109/IWESEP.2016.18Shimonaka K., Sumi S., Higo Y., Kusumoto S. Identifying Auto-Generated Code by Using Machine Learning Techniques. Proceedings of the 7th International Workshop on Empirical Software Engineering in Practice, IWESEP, 13 March 2016, Osaka, Japan. IEEE; 2016. p.18‒23. DOI:10.1109/IWESEP.2016.18Igwe K., Pillay N. Automatic programming using genetic programming // Proceedings of the Third World Congress on Information and Communication Technologies (WICT 2013, Hanoi, Vietnam, 15‒18 December 2013). IEEE, 2013. PP. 337‒342. DOI:10.1109/WICT.2013.7113158Igwe K., Pillay N. Automatic programming using genetic programming. Proceedings of the Third World Congress on Information and Communication Technologies, WICT 2013, 15‒18 December 2013, Hanoi, Vietnam. IEEE; 2013. p.337‒342. DOI:10.1109/WICT.2013.7113158Бирюков Д.Н., Дудкин А.С., Захаров О.О. Способ тестирования средств защиты информации на основе применения многовариантной генерации исходного кода по заданной функциональной спецификации // Труды Военно-космической академии имени А.Ф. Можайского. 2022. № 684. С. 113‒122. EDN:BJWKLGBiryukov D.N., Dudkin A.S., Zakharov O.O. A method for testing information security tools based on the use of multivariate source code generation according to a given functional specification. Proceedings of the Mozhaisky Military Space Academy. 2022;684:113‒122. (in Russ.) EDN:BJWKLGСамохвалов Э.Н., Ревунков Г.И., Гапанюк Ю.Е. Генерация исходного кода программного обеспечения на основе многоуровневого набора правил // Вестник Московского государственного технического университета им. Н.Э. Баумана. Серия Приборостроение. 2014. № 5(98). С. 77‒87. EDN:SVZLSLSamohvalov E.N., Revunkov G.I., Gapanyuk Yu.E. Source code generation of software based on multilevel set of rules. Herald of the Bauman Moscow State Technical University. Series Instrument Engineering. 2014;5(98):77‒87. (in Russ.) EDN:SVZLSLСоколов А.П., Макаренков В.М., Першин А.Ю., Лаишевский И.А. Разработка программного обеспечения генерации кода на основе шаблонов при создании систем инженерного анализа // Программная инженерия. 2019. Т. 10. № 9-10. С. 400‒416. DOI:10.17587/prin.10.400-416. EDN:CHYPRESokolov A.P., Makarenkov V.M., Pershin A.Yu., Laishevskiy I.A. Development of template-based code generation software for development of computer-aided engineering system. Software Engineering. 2019;10(9-10):400‒416. (in Russ.) DOI:10.17587/prin.10.400-416. EDN:CHYPREДовгаль В.М., Корольков О.Ф., Чаплыгин А.А., Королькова В.О. К вопросу решения проблемы автоматической генерации кода программ по заданному управляющему продукционному алгоритму // В мире научных открытий. 2012. № 1(25). С. 220‒235. EDN:PBBWKPDovgal V.M., Korolkov O.F., Chaplygin A.A., Korolkova V.O. Considering of solving automatic code generation problem basing on given control production algorithm. In the World of Scientific Discoveries. 2012(1);25:220‒235. (in Russ.) EDN:PBBWKPАндрианова А.А., Ицыксон В.М. Технология анализа исходного кода программного обеспечения и частичных спецификаций для автоматизированной генерации тестов // Системы и средства информатики. 2014. Т. 24. № 2. С. 99‒113. DOI:10.14357/08696527140207. EDN:SJHATLAndrianova A., Itsykson V. Source code and partial specifications analysis for automated generation of unit tests. Systems and Means of Informatics. 2014;24(2):99‒113. (in Russ.) DOI:10.14357/08696527140207. EDN:SJHATLСаух А.М., Хмельнов А.Е. Трансляция фрагментов исходных текстов программ с использованием спецификаций синтаксиса и семантики языков программирования // Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2013. Т. 11. № 3. С. 53‒62. EDN:RCHBLBSaukh A.M., Hmelnov A.E. Source code fragments translation based on programming languages syntax and semantics specifications. Vestnik NSU. Series: Information Technologies. 2013;11(3):53‒62. (in Russ.) EDN:RCHBLBHaq I.U., Caballero J.A. Survey of Binary Code Similarity // ACM Computing Surveys. 2021. Vol. 54. Iss. 3. PP. 1‒38. DOI:10.1145/3446371. EDN:KEPQCCHaq I.U., Caballero J.A. Survey of Binary Code Similarity. ACM Computing Surveys. 2021;54(3):1‒38. DOI:10.1145/3446371. EDN:KEPQCCКуделя В.Н. Методы перечисления путей в графе // Наукоемкие технологии в космических исследованиях Земли. 2023. Т. 15. № 5. С. 28‒38. DOI:10.36724/2409-5419-2023-15-5-28-38. EDN:HQEASNKudelya V.N. Methods for enumerating paths in a graph. H&ES Research. 2023;15(5):28‒38. (in Russ.) DOI:10.36724/2409-5419-2023-15-5-28-38. EDN:HQEASNКусаинов А.Р., Глазырина Н.С. Обзор инструментов статического анализа программного кода // Colloquium-Journal. 2020. № 32-1(84). С. 48‒52. EDN:JXSKQXKussainov A.R., Glazyrina N.S. Overview of static program code analysis tools. Colloquium-Journal. 2020;32-1(84):48‒52. (in Russ.) EDN:JXSKQX

The authors declare that there are no conflicts of interest present.