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

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