Символизированный раздвоенный двоичный файл с использованием символов из более ранней версии отладки (неточное сопоставление графов)

Question

У меня есть двоичный файл A , который представляет собой отладочную сборку с сопровождающими символами - созданную много лет назад.У меня также есть двоичный файл B , сборка релиза без сопровождающих символов и намного более поздняя версия.Я ищу наиболее эффективный метод сопоставления символов из двоичного A с потенциальными кандидатами в двоичном B .

Учитывая, что сборка отладки значительно больше (делаетбольше проверки ввода, печатает больше вещей в stderr и т. д.) и что функции неизменно меняются со временем, я полагаю, что попытка снять отпечатки пальцев с отдельных функций будет напрасной тратой времени.- совершенно невесело, так что я могу лаять не на то дерево - что лучший способ снять отпечатки пальцев с функций - создать графы вызовов обоих двоичных файлов и попытаться сопоставить их с вершинами (то есть с функциями).

Я уже выполнил некоторую предварительную обработку, поэтому у меня есть следующие структуры данных:

# binary A
[[60, 60, 8734], # function 0 is called by functions 60 (twice) and 8734
 [193, 441, 505], # function 1 is called by functions 193, 441 and 505
 [193, 742],
 [23],  
 [21],  
 [21],  
 [26],  
 [26, 1508, 1509, 1573],  
 [24],  
 [25],
 ...] # (~10k functions)

# binary B
[[8999], # function 0 is called by function 8999
 [9016], # function 1 is called by function 9016
 [1126], 
 [7904, 7904, 7913], 
 [182, 336, 396, 396], 
 [9010], 
 [407], 
 [182, 632], 
 [20], 
 [24],
 ...] # (~10k functions)

Важное замечание, которое необходимо уловить, заключается в том, что в функции "0" нет соответствия no двоичный файл A и функция "0" в двоичном формате B .Это произвольные идентификаторы, которые я назначил каждой функции в каждом двоичном файле.

Следующий шаг - это то, что смущает меня.Мой алгоритм фу очень слабый, и я не могу придумать, как правильно поступить.Мое (очень ограниченное) понимание состоит в том, что для решения этой проблемы я бы хотел использовать некую форму неточного сопоставления графов .Другими словами, какой набор отображений Ai -> Bi максимизирует сходство двух графов вызовов?

Учитывая, что в двоичном коде есть дополнительные функции отладки A и очевидный факт, чтопрограммы развиваются с течением времени, скорее всего, нет точного соответствия.В идеале я хотел бы получить вывод вида:

[[(37, 0.998), (8432, 0.912), (442, 0.75)], # matching-ness of function "0" in binary A with function "37" in binary B is 0.998, second most likely candidate is function "8432" in binary B with score 0.912, etc.
 [(42, 0.973), (7751, 0.788)], # matching-ness of function "1" in binary A with function "42" in binary B is 0.973, second most likely candidate is function "7751" in binary B with score 0.788, etc.
 [(4579, 0.996), (123, 0.934)], 
 ...] # around ~10k mappings

На самом деле, я был бы счастлив, если бы мне пришлось обойтись только с одним кандидатом, а рейтинг не был предоставлен, но можно мечтать.

Есть ли у кого-нибудь из SO-идей идея, с чего мне начать?

Answer 1

Конечно, интересная проблема, хотя я подозреваю, что это будет трудно решить. Похоже, это пример приближенного изоморфизма графов на ориентированных графах. Я не нашел много гугл для этого, но вот какое-то программное обеспечение для решения для неориентированных общих графов, более общий случай, который NP труден.

Выравнивание исполняемого кода

Я думаю, что наиболее практичная вещь, которую вы можете сделать, это забыть об информации времени выполнения и просто взять секции исполняемого кода каждой версии и использовать алгоритм глобального выравнивания (например, Needleman-Wunsch , хотя существуют гораздо более быстрые, но менее точные алгоритмы) для них:

1. Обрабатывает все инструкции как символы (это потребует создания элементарного дизассемблера)
2. Полное игнорирование адресных компонентов инструкций
3. Удаление с понижением веса (при условии, что «первый» файл является отладочной версией, которую мы ожидаем увеличить)
4. совпадения с апвитами CALL инструкций и, возможно, другие "надежные" последовательности инструкций.

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

Задача о назначении (двустороннее максимальное совпадение)

В качестве альтернативы, если вы можете найти способ (и моя интуиция предполагает, что это должен быть итеративный подход, в соответствии с тем, как PageRank определяет значение веб-страницы), чтобы "оценить" вероятность того, что функция f в отладочной версии соответствует функции g в оптимизированной версии, тогда да, вы можете использовать метод сопоставления графиков. В этом случае вершинами графа будут все функции в обеих версиях, и между каждой функцией из отладочной версии и каждой функцией из оптимизированной версии будет взвешенное ребро с весом, определяемым вашей системой оценки.

Этот график будет двухсторонним, потому что никогда не будет ребра между двумя функциями в одной и той же версии. Это означает, что это экземпляр Задачи назначения , для которой существуют довольно хорошие (и не слишком сложные) алгоритмы.

Однако отсутствующий фрагмент здесь является средством определения весов для каждой пары. Один примерный способ сделать это - построить вектор для подсчета числа ближайших детей, внуков, правнуков и так далее для каждой функции. Затем вы можете сравнить эти векторы, используя любое расстояние, которое вам нравится. Но я ожидаю, что выполнение этого здесь не будет работать хорошо, потому что мы уже ожидаем, что отладочная версия будет содержать гораздо больше вызовов функций, чем оптимизированная версия.

Использование полного дерева вызовов

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

1. Извлечение списка отдельных функций, вызываемых данной функцией
2. Маркировка 1-й вызываемой функции 1, 2-й вызываемой отдельной функции 2 и т. Д.
3. Сигнатура - это просто последовательность меток функций в порядке их вызова в функции.

Теперь Расстояние Левенштейна можно использовать для сравнения 2 подписей. Для большей точности за счет большего количества вычислений вы можете использовать вариант, в котором разрешено удалять до k различных функций в отладочной версии для некоторого небольшого k (например, k = 3), и берется наилучшее расстояние Левенштейна по всем таким «урезанным» версиям с небольшим штрафом, пропорциональным количеству удаленных функций.

Answer 2

Если можете себе это позволить, IDA Pro + BinDiff .