Алгоритм вычисления похожести графов и его применение для сравнения бинарных исполняемых файлов

Обложка

Цитировать

Полный текст

Аннотация

Рассматривается задача статического (без запуска) сравнения бинарных исполняемых файлов. Программа и любая ее процедура могут быть представлены в виде ориентированного графа. Для программы соответствующий граф представляет собой граф вызова функций (процедур), где узлами являются сами функции, а ребро из вершины a в b описывает вызов функции b из функции a. Для процедуры такой граф представляет собой граф потока управления, где вершинами являются базовые блоки, а ребро между узлами a и b означает возможное исполнение команд блока b после исполнения команд блока a. В работе предлагается алгоритм сравнения направленных графов, который далее применяется для сравнения программ. В основе алгоритма сравнения графов лежит применение функции похожести узлов. Для сравнения графов процедур в качестве такой функции похожести применяются нечеткая (fuzzy) хеш-функция и криптографическая хеш-функция. Далее этот способ сравнения графов процедур используется как функция похожести узлов при сравнении графов программ. На базе предложенного алгоритма разработан метод сравнения программ, проведено его исследование в рамках двух экспериментов. В первом эксперименте исследовано поведение метода при сравнении программ, полученных с применением разных опций оптимизации (O0, O1, O2, O3 и Os). Во втором эксперименте исследована возможность выявления эффективных и стойких обфусцирующих преобразований в рамках ранее разработанной модели. В первом эксперименте получены свидетельства в пользу верности гипотезы об уменьшении похожести файлов с ростом оптимизации от O1 до O3. Во втором эксперименте подтверждены некоторые полученные ранее результаты, касающиеся эффективности (неэффективности) и стойкости (нестойкости) обфусцирующих преобразований.

Об авторах

П. Д Борисов

ФГАНУ НИИ «Спецвузавтоматика»

Email: borisovpetr@mail.ru
улица Города Волос 6

Д. В Варламов

Южный федеральный университет (ЮФУ)

Email: varlamov@sfedu.ru
улица Мильчакова 8a

Ю. В Косолапов

Южный федеральный университет (ЮФУ)

Email: yvkosolapov@sfedu.ru
улица Мильчакова 8a

Список литературы

  1. Van Tilborg H., Jajodia S. Encyclopedia of cryptography and security. Springer Science & Business Media. 2014. 1416 p.
  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 (дата обращения:
  20. 06.2025).
  21. 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.
  22. 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.
  23. Борисов П.Д., Косолапов Ю.В. О функции похожести графических представлений исполняемых файлов в модели оценки обфусцирующих преобразований // Известия ЮФУ. 2025. № 3(245). С. 264–273.
  24. Naville Z. Hikari–an improvement over Obfuscator-LLVM. 2017. URL: https://github.com/HikariObfuscator/Hikari (дата обращения: 26.11.2024).
  25. 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.
  26. small-programs. A set of small programs for experiments with obfuscations. URL: https://github.com/Boriskin61/small-programs (дата обращения: 22.06.2025).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».