Посоветуйте библиотеку для анализа кода

oliver11

Что требуется от библиотеки:
1. Умение разбирать код на ассемблере (x86 из-под objdump-а подойдёт) или на Си (real-world программы должны приниматься).
2. Умение переводить прочитанное в граф потока управления с каким-нибудь простым кодом (типа трёхадресного) в базовых блоках.
3. Умение считать reaching definitions, переводить в SSA-представление. Value set анализ тоже не повредит.
4. Чтобы в ней можно было разобраться студенту за месяц.
Куда копать? Frama-C, LLVM? Кто чем пользовался?

Oper

Frama-C не годится для анализа реального кода.
llvm-gcc умеет транслировать сишный код в LLVM-ассемблер, это есть некое подобие трехадресного кода. Дальше, боюсь, придется действовать самостоятельно.
Я бы советовал копать в сторону clang (llvm)
PS. А вообще, это задача не на один месяц уж точно

oliver11

Frama-C не годится для анализа реального кода.

А можно поподробнее, что не работает? Навскидку я только про goto назад знаю.
Вообще, Frama-C мне пока не нравится следующими вещами:
1. Только Си.
2. Устаревшая и неполная документация. Прочитав её, так до конца и не понял, из чего они там CFG строят.
3. Ocaml.
4. Сложно применять. Как минимум, надо правильные опции препроцессора сказать. CLang втыкается более бесшовно.

PS. А вообще, это задача не на один месяц уж точно

Уточню задачу. :-) Пользователь должен уметь показать в коде на одну или более функций, сказать, какими общими данными они оперируют (допустим, перечислить номера аргументов функции, которые у параллельных вызовов могут быть указателями на одно и то же). Программа должна будет эти функции перевести в ещё одно промежуточное представление (типа конечного автомата, но с переменными и не конечного над которым уже будут производится интересные вычисления. Это план-минимум.
А результатами вычислений по сути будут места, в которые надо вставить memory fences, чтобы код правильно работал на конкретной архитектуре с relaxed memory model (не sequentially consistent). Будет круто, если эти mfences получится вставлять в llvm-представление и потом переносить в ассемблер. Но это уже план-максимум.
Сколько реализация такого с использованием LLVM может занять у студента старших курсов? :-)

xronik111

План-минимум - это курсовая, план-максимум - это диплом.

Oper

Вообще, Frama-C мне пока не нравится следующими вещами:
1. Только Си.
2. Устаревшая и неполная документация. Прочитав её, так до конца и не понял, из чего они там CFG строят.
3. Ocaml.
4. Сложно применять. Как минимум, надо правильные опции препроцессора сказать. CLang втыкается более бесшовно.

Из того, что я помню про Frama-C (модуль value analysis, ключ -val).
1. Ограниченное количество отслеживаемых объектов (переменных, массивов и т.п.). По умолчанию — не более 200. Это принципиальное ограничение, используемый разработчиками алгоритм не может быть переделан с тем, чтобы следить за неограниченным количеством таких объектов. Кроме того, давая команду использовать больше объектов, время анализа возрастает нелинейно.
2. Некорректная обработка стандартных библиотечных функций (даже таких, как malloc, free). Для функции free, например, Frama-C считает, что не выполняется никаких действий. А для функции malloc считает, что выделяемый участок памяти — одинаковый для каждого прохода через эту точку.
3. На мой взгляд, использование ocaml - ну никак нельзя считать недостатком
Проблем с парсингом замечено не было.

Oper

Уточню задачу. :-) Пользователь должен уметь показать в коде на одну или более функций, сказать, какими общими данными они оперируют (допустим, перечислить номера аргументов функции, которые у параллельных вызовов могут быть указателями на одно и то же). Программа должна будет эти функции перевести в ещё одно промежуточное представление (типа конечного автомата, но с переменными и не конечного над которым уже будут производится интересные вычисления. Это план-минимум.
А результатами вычислений по сути будут места, в которые надо вставить memory fences, чтобы код правильно работал на конкретной архитектуре с relaxed memory model (не sequentially consistent). Будет круто, если эти mfences получится вставлять в llvm-представление и потом переносить в ассемблер. Но это уже план-максимум.
Сколько реализация такого с использованием LLVM может занять у студента старших курсов? :-)

Alias analysis для языка Си — довольно суровая задача
Хотя все зависит от требований к качеству решения.
В целом, я бы сказал, там теории и практики с головой хватит на кандидатскую
Насчет LLVM: его использовать можно, хотя и не так просто. Фактически парсинг сишного кода он сделает, но затем преобразование дерева разбора программы в промежуточное представление (типа трех-адресного кода) придется делать руками (хотя и с использованием clang api).
Если использовать непосредственно трансляцию в llvm-ассемблер (llvm-gcc то многие важные для alias analysis свойства программы, видимые на уровне сишного кода, в llvm-формате будут потеряны и все довольно быстро сведется к модели "все зависит от всего".
Для начала я бы советовал определиться именно с требованиями к качеству такого анализа. Продумать в каких случаях надо уметь находить точный результат (кто на что указывает в каких случаях хватит приближенного ответа. Это можно делать даже на конкретных примерах сишных тестовых программ, чем больше — тем лучше. Важно, чтобы неточность, возникшая в одном месте программы, не накапливалась и не приводила к ситуации, когда указатель может указывать куда угодно. Затем важный момент — рекурсия и динамическое выделение/освобождение памяти. Как будет проводиться учет участков памяти в такой ситуации? Как будет проводиться анализ много-файловых программ? Не получится ли анализируемая модель слишком большой и как ее делить на части в таком случае? и так далее....