Структурное сравнение программ

Мозг, глаза, руки... сложно что-то ещё предложить.

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

Готового решения нет. Я бы попробовал сравнивать нормализованный llvm ir (идентификаторы нумеровать в порядке топологической сортировки cfg, например). Вообще, задача интересная.

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

UPD. Предложенный аноном вариант с LLVM — то же самое на готовом инструменте. Но я с IR не работал, не знаю как он генерируется, но по идее должно сработать.

Синтаксические деревья - недостаточно абстрактный уровень. while замененый на if и goto будеть выглядеть иначе.

Мозг, глаза, руки...

Слишком трудоемко.

сложно что-то ещё предложить.

Вот и незанятая ниша опенсорса :)

Подобные изменения ты все равно не отловишь, это алгоритмически неразрешимо.

Это еще что за бред? Функционально идентичный код после нормализации дает идентичный IR, если только часть функциональности не выносилась в отдельные функции.

Исходная задача: «возможное переименование идентификаторов (имен функций и переменных) плюс возможное перемещение текста».

А вообще, т.к. задача в переименовывании идентификаторов, я само собой предполагал обработку деревьев, в случае необходимости на этом же этапе можно раскрыть макросы, циклы развернуть в if-goto (а при некотором упорстве — и вызовы функций) и т.д. — в общем степень обработки зависит лишь от потребности ТС.

PS. Из готовых тулз еще можно попробовать gcc-xml.

while замененый на if и goto будеть выглядеть иначе.

Подобные изменения ты все равно не отловишь, это алгоритмически неразрешимо.

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

да, причем в общем, мне необходимая.

Мне нужно документировать утилиту, исходные тексты которой безвозвратно утеряны, программист попал под каток и никто в мире не знает, как конкретно

Исходные тексты на Си я смог восстановить с помощью IDA + сами знаете какой плагин, но там же имена идентификаторов декомпилятор сам придумывает.

у меня их нет. У меня есть восстановленный исходный текст на Си - один файл на 5 Мб. Сравнивать самому глазами - себя не уважать.

Ограничения gccxml К сожалению, gccxml имеет некоторые недостатки. Из кода извлекаются только декларации, а тела функций не доступны. Декларации шаблонов также не доступны. Gccxml основан на достаточно старой версии gcc и разработка идет не слишком активно.

да, но мне нужно еще и тела функций нужно сравнивать.

Хм, я читал, что gccxml делает дамп внутреннего представления компилятора о программе. Ну раз нет, искать какой-то готовый парсер или воспользоваться llvm или самопал. Но по данному тобой позже описанию проблемы я уже очень сильно не уверен, что получится что-нибудь сделать, максимум, что можно будет сказать, — похоже/совсем не похоже, банально вычислить инлайны функций и констант — уже проблема, вообще исходный компилятор может нагородить уйму оптимизаций, отследить которые будет очень нелегкой задачей. Может лучше попробовать обложить две версии программы тестами и сравнивать их прохождение?

Изначально я думал, речь идет о достаточно небольших изменениях, внесенных человеком.

UPD. Хотя я еще раз перечитал твое сообщение о проблеме и совсем запутался. Если тебе нужно задокументировать программу, исходный текст которой ты восстановил, зачем нужно средство сравнения двух исходных текстов?

Я сравниваю оригинал (базовую версию) и измененную версию.

Мне нужно задокументировать изменения, которые были внесены в «базовую программу» - именно это мне важно.

вот текст

Пароль: 12344321

Функционально идентичный код после нормализации дает идентичный IR, если только часть функциональности не выносилась в отдельные функции.

Это же просто отлично! Можно написать виснущую программу, проверять другую на эквивалентность ее IR и разрешить пробелму останова!

Идиот. Лечись.

граф вызовов функций может пригодится cflow

возьмите голову, и прогоните обе проги в отладчике.

плюсую.

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

параллельно шагая восстановить имена переменных и функций по оригиналу.

исходные тексты недоступны и там и там.

Как я буду восстанавливать имена переменных?

И как я буду запускать отладку кода без исходных текстов? Он мне же мне ассемблер будет показывать.

Или вы считаете, что сами знаете какой плагин для IDA настолько умный, что я смогу откомпилировать его текст, а потом запустить отладчик из студии? Ну и? Я буду восстанавливать имена переменных по поведению программы?

Мне-то зачем? Это ты у нас ловко придумал как решать алгоритмически неразрешимые задачи. Надо всего лишь сравнить ir пограмм, вот чудо-то. Как никто раньше не догадался.

из

Имеются исходные тексты двух программ: оригинал и его модификация.

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

Вот эти изменения и нужно отловить.

я подумал, что у вас на руках сорцы оригинала (старой версии) и бинарь (декомпилированный сорц) от производной. И задача восстановить нормальный исходный текст производной. То есть объяснимая ситуация - например в конторе всем хором делали софт, потом ведущий разработчик(группа) свалил затерев последние изменения в релизе. А релиз надо сопровождать.

вариант когда ОБЕ сорца - результат декомпиляции и исходный текст недоступен даже теоретически, сильно похож на реверс софта конкурентов, что выходит за рамки данного форума.

в принципе как и ваш тон ;-)

Если что нибудь «попроще»?

Слово «попроще» тут вообще неприменимо. Я тоже гуглил, тут есть немного ссылок, в т.ч. твой ydiff. В итоге забил, ничего сложнее xml толком не научились сравнивать.

Если есть история между двумя версиями программ, их можно понемногу отреплеить и попробовать что-нибудь изобразить через теорию патчей darcs :)

сильно похож на реверс софта конкурентов

это похоже на документирование софта, которое было сделано где-то на Тайване, саппорта нет, описание API нет, документации «кот наплакал» и она не соответствует реальному положению.

Зы. Саппорт нам так и сказал - е..сь сами. Зы. зы. А еще мне нужно документировать ПО, по которому тоже прекращена поддержка (1-2 человека знали, как оно работает), а сам разработчик попал под каток. Зы. зы. зы. Ревер-инжиниринг разрешен российскими законодательством, даже если в лицензии указано обратное. При соблюдении определенных условий.