Статический анализ исходного кода с помощью LLVM

Question

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

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

EDIT:

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

Answer 1

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

Если ваша программа только на C, я рекомендую вам взглянуть на Анализ значений в Frama-C . Он вычисляет надмножества возможных значений для любого l-значения в каждой точке программы, в соответствии с некоторыми гипотезами, которые объясняются с длиной здесь . Сложность в анализируемой программе означает только то, что возвращенные надмножества являются более приближенными, но они все еще содержат все возможные значения времени выполнения (пока вы остаетесь в пределах вышеупомянутых гипотез).

РЕДАКТИРОВАТЬ: если вас интересуют возможные значения указателей на функции с целью нарезки анализируемой программы, вам определенно следует взглянуть на существующие зависимости и нарезки вычислений в Frama-C. На сайте нет хорошего примера нарезки, вот один из обсуждения в списке рассылки

Answer 2

Вам стоит взглянуть на Эльза . Его относительно легко расширить, и он позволяет достаточно легко анализировать AST. Он обрабатывает все синтаксический анализ, лексирование и генерацию AST, а затем позволяет обходить дерево, используя шаблон Visitor.

class CallGraphGenerator : public ASTVisitor
{
  //...
  virtual bool visitFunction(Function *func);
  virtual bool visitExpression(Expression *expr);
}

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

Answer 3

В нашем проекте мы выполняем статический анализ исходного кода путем преобразования байт-кода LLVM в код C с помощью программы llc, поставляемой с LLVM. Затем мы анализируем код C с помощью CIL (C Intermediate Language) , но для языка C доступно множество инструментов. Недостаток в том, что код, сгенерированный llc, равен AWFUL и страдает от большой потери точности. Но все же, это один из способов.

Редактировать: на самом деле, я бы никому не рекомендовал это нравится. Но все же, только для записи ...

Answer 4

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

DMS был протестирован на монолитных системах кода C с 25 миллионами строк. (В графе вызовов этого монстра было 250 000 функций).

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

Answer 5

Я думаю, что ваш вопрос ошибочен. В заголовке написано «Статический анализ исходного кода». Тем не менее, ваша основная причина заключается в построении (части) графа вызовов, включая вызовы через указатель на функцию. Суть указателей на функции заключается в том, что вы не можете знать их значения во время компиляции, то есть в тот момент, когда вы выполняете статический анализ исходного кода. Рассмотрим этот бит кода:

void (*pFoo)() = GetFoo();
pFoo();

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

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