Алгоритм вычисления похожести графов и его применение для сравнения бинарных исполняемых файлов
Ключевые слова:
сравнение графов, похожесть программ, эффективность и стойкость обфускацииАннотация
Рассматривается задача статического (без запуска) сравнения бинарных исполняемых файлов. Программа и любая ее процедура могут быть представлены в виде ориентированного графа. Для программы соответствующий граф представляет собой граф вызова функций (процедур), где узлами являются сами функции, а ребро из вершины a в b описывает вызов функции b из функции a. Для процедуры такой граф представляет собой граф потока управления, где вершинами являются базовые блоки, а ребро между узлами a и b означает возможное исполнение команд блока b после исполнения команд блока a. В работе предлагается алгоритм сравнения направленных графов, который далее применяется для сравнения программ. В основе алгоритма сравнения графов лежит применение функции похожести узлов. Для сравнения графов процедур в качестве такой функции похожести применяются нечеткая (fuzzy) хеш-функция и криптографическая хеш-функция. Далее этот способ сравнения графов процедур используется как функция похожести узлов при сравнении графов программ. На базе предложенного алгоритма разработан метод сравнения программ, проведено его исследование в рамках двух экспериментов. В первом эксперименте исследовано поведение метода при сравнении программ, полученных с применением разных опций оптимизации (O0, O1, O2, O3 и Os). Во втором эксперименте исследована возможность выявления эффективных и стойких обфусцирующих преобразований в рамках ранее разработанной модели. В первом эксперименте получены свидетельства в пользу верности гипотезы об уменьшении похожести файлов с ростом оптимизации от O1 до O3. Во втором эксперименте подтверждены некоторые полученные ранее результаты, касающиеся эффективности (неэффективности) и стойкости (нестойкости) обфусцирующих преобразований.
Литература
2. Li B., He J., Huang J., Shi Y.Q. A survey on image steganography and steganalysis // Journal of Information Hiding and Multimedia Signal Processing. 2011. vol. 2. no. 2. pp. 142–172.
3. Chabot C. Recognition of a code in a noisy environment // IEEE International Symposium on Information Theory. IEEE, 2007. pp. 2211–2215. DOI: 10.1109/ISIT.2007.4557548.
4. Crawford M., Khoshgoftaar T.M., Prusa J.D, Richter A.N., Al Najada H. Survey of review spam detection using machine learning techniques // Journal of Big Data. 2015. vol. 2. DOI: 10.1186/s40537-015-0029-9.
5. Forrest S., Hofmeyr S., Somayaji A. The evolution of system-call monitoring // Proceedings of the 2008 Annual Computer Security Applications Conference (ACSAC). 2008. pp. 418–430. DOI: 10.1109/ACSAC.2008.5.
6. Khraisat A., Gondal I., Vamplew P., Kamruzzaman J. Survey of intrusion detection systems: techniques, datasets and challenges // Cybersecurity. 2019. vol. 2. DOI: 10.1186/s42400-019-0038-7.
7. Kosolapov Y.V. On detecting code reuse attacks // Automatic Control and Computer Sciences. 2020. vol. 54. no. 7. pp. 573–583. DOI: 10.3103/S0146411620070111.
8. Kiger J., Ho S.-S., Heydari V. Malware binary image classification using convolutional neural networks // Proceedings of the 17th International Conference on Cyber Warfare and Security (ICCWS). 2022. vol. 17. pp. 469–478. DOI: 10.34190/iccws.17.1.59.
9. Polsani H., Jiang H., Liu Y. DeepGray: Malware Classification Using Grayscale Images with Deep Learning // The 37th International FLAIRS Conference. 2024. pp. 1–5.
10. Борисов П.Д., Косолапов Ю.В. Способ количественного сравнения обфусцирующих преобразований // Информатика и автоматизация. 2024. Т. 23. № 3. С. 684–726. DOI: 10.15622/ia.23.3.3.
11. Борисов П.Д., Косолапов Ю.В. Способ оценки похожести программ методами машинного обучения // Труды Института системного программирования РАН. 2022. Т. 34. № 5. С. 63–76. DOI: 10.15514/ISPRAS-2022-34(5)-4.
12. Kornblum J. Identifying almost identical files using context triggered piecewise hashing // Digital investigation. 2006. vol. 3. pp. 91–97. DOI: 10.1016/j.diin.2006.06.015.
13. Breitinger F., Baier H. Similarity preserving hashing: Eligible properties and a new algorithm mrsh-v2 // Digital Forensics and Cyber Crime: 4th International Conference (ICDF2C 2012). 2013. pp. 167–182. DOI: 10.1007/978-3-642-39891-9_11.
14. Roussev V. An evaluation of forensic similarity hashes // Digital investigation. 2011. vol. 8. pp. S34–S41. DOI: 10.1016/j.diin.2011.05.005.
15. Pagani F., Dell’Amico M., Balzarotti D. Beyond precision and recall: understanding uses (and misuses) of similarity hashes in binary analysis // Proc. of the Eighth ACM Conference on Data and Application Security and Privacy. 2018. pp. 354–365. DOI: 10.1145/3176258.3176306.
16. BinDiff. URL: https://www.zynamics.com/ (дата обращения: 23.06.2025).
17. Aslanyan H., Avetisyan A., Arutunian M., Keropyan G., Kurmangaleev S., Vardanyan V. Scalable Framework for Accurate Binary Code Comparison // Ivannikov ISPRAS Open Conference (ISPRAS). 2017. pp. 34–38. DOI: 10.1109/ISPRAS.2017.00013.
18. Machoc hash. URL: https://github.com/ANSSI-FR/polichombr/blob/dev/ (дата обращения: 23.06.2025).
19. Machoke. URL: https://github.com/conix-security/machoke (дата обращения:
23.06.2025).
20. Li Y., Jang J., Ou X. Topology-aware hashing for effective control flow graph similarity analysis // Security and Privacy in Communication Networks: 15th EAI International Conference (SecureComm). 2019. pp. 278–298.
21. Borisov P.D., Kosolapov Y.V. On the Automatic Analysis of the Practical Resistance of Obfuscating Transformations // Aut. Control Comp. Sci. 2020. vol. 54. pp. 619–629. DOI: 10.3103/S0146411620070044.
22. Борисов П.Д., Косолапов Ю.В. О функции похожести графических представлений исполняемых файлов в модели оценки обфусцирующих преобразований // Известия ЮФУ. 2025. № 3(245). С. 264–273.
23. Naville Z. Hikari–an improvement over Obfuscator-LLVM. 2017. URL: https://github.com/HikariObfuscator/Hikari (дата обращения: 26.11.2024).
24. Holder W., McDonald J.T., Andel T.R. Evaluating optimal phase ordering in obfuscation executives // Proceedings of the 7th Software Security, Protection, and Reverse Engineering/Software Security and Protection Workshop. 2017. pp. 1–12. DOI: 10.1145/3151137.3151140.
25. small-programs. A set of small programs for experiments with obfuscations. URL: https://github.com/Boriskin61/small-programs (дата обращения: 22.06.2025).
Опубликован
Как цитировать
Раздел
Copyright (c) Юрий Владимирович Косолапов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).