Под лежачий камень вода не течет.

Методы анализа программ часто представляют программы в виде графов. Эти графики должны автоматически генерироваться из исходного кода. Для этого было реализовано много инструментов, но их часто сложно настроить. В этом посте я сравню 3 фреймворка для анализа программ, которые я использовал для создания графовых представлений программ на C.

TL;DR: более мощные платформы сложнее настроить, поскольку они требуют информации о компиляторе или предоставляют сложные API.

  • SrcML отлично подходит, если все, что вам нужно, это AST, и вам не нужна 100% точность.
  • Джорн отлично подходит, если вам нужны CFG или PDG для большого набора программ, и вы согласны с возможным неправильным анализом некоторых программ.
  • LLVM отлично подходит, если вам нужен надежный анализ и вы хотите использовать сложные этапы анализа программы, используемые в компиляторе Clang, и вы можете предоставить информацию о компиляторе.

Управление потоком что-сейчас?

Различные типы графиков используются для разных анализов, в зависимости от того, какая информация необходима [0]:

  • Абстрактное синтаксическое дерево (AST): древовидное представление токенов в программе, которое абстрагирует такие детали, как круглые скобки, пробелы и разделители.
  • Граф потока управления (CFG): Графическое представление, в котором каждый узел является оператором, а каждое ребро является переходом в потоке управления.
  • Program Dependence Graph (PDG): Представление графа, в котором каждый узел является оператором, а каждое ребро является элементом управления или зависимостью данных. Переменная зависит от оператора, если этот оператор влияет на значение переменной.

Я решил изучить относительные преимущества трех популярных фреймворков для анализа программ, которые я использовал в своих исследованиях:

Я оценивал фреймворки по трем критериям, которые важны для любой задачи анализа программы.

  • Скорость: насколько быстр фреймворк?
  • Точность: насколько точен результирующий CFG?
  • Простота использования: сколько усилий требуется для использования фреймворка, особенно. на большом наборе программ?

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

Проблемы с разбором кода C

Программы на C трудно анализировать, потому что препроцессор допускает произвольную замену текста [1]. Если макросы препроцессора не определены, синтаксический анализатор может неправильно интерпретировать контекст определенного фрагмента кода и совершенно неправильно его проанализировать. Я называю это неточностью в моей оценке трех фреймворков.

Программам на C также требуется информация компилятора, такая как типы и функции, определенные в заголовочных файлах, для правильного анализа [2]. Эти файлы заголовков могут быть разбросаны по всему компьютеру, а заголовки стандартных библиотек находятся в разных местах в разных ОС или дистрибутивах. Информация о компиляторе обычно передается синтаксическому анализатору с помощью флагов компилятора, таких как -I или -D.

SrcML

SrcML — это формат XML для исходного кода. Он предоставляет AST в независимом от языка формате. Он также сохраняет все символы, включая пробелы, комментарии и макросы препроцессора.

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

Авторы SrcML заявляют, что он быстрее компилятора (более 25KLOC/сек) [3]. Я заметил, что он работает очень быстро и, кроме того, может выполнять всю свою обработку в памяти из-за того, что выводит XML в виде текста.

SrcML предоставляет AST, но не CFG или PDG. Таким образом, чтобы получить CFG, нам пришлось бы реализовать алгоритм для создания CFG на основе AST. Некоторые проекты сделали это как часть своей реализации (особенно srcSlice и srcPtr), но мне было трудно адаптировать эти реализации для других целей.

Формат SrcML не зависит от языка, поэтому теоретически вы можете написать анализ на основе формата XML и применить его ко всем поддерживаемым языкам (в настоящее время C, C++, C# и Java).

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

Команда SrcML довольно быстро ответила на мои вопросы об их фреймворке.

Йорн

Joern — это рабочая среда, которая анализирует код C/C++ и генерирует график свойств кода (CPG). CPG представляет собой комбинацию AST, CFG и PDG в один большой график и предоставляет информацию, достаточную для выполнения широкого спектра анализов. Основным интерфейсом инструмента является интерпретатор командной строки, который позволяет пользователям писать собственные запросы в DSL на основе Scala.

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

Я обнаружил, что реализация Joern работает намного медленнее, чем SrcML и LLVM. Это может быть связано с выбором платформы времени выполнения: SrcML и LLVM построены на C++ и имеют узкую функциональность, в то время как Joern построен на Scala и обладает широкими возможностями настройки/скриптов.

Поддерживается несколько языков: C/C++, сборка x86/64, JVM, LLVM Bitcode и Javascript. Я пробовал только C/C++, и это единственные языки, отмеченные как высокие зрелые на их странице документации.

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

Команда ShiftLeft очень активно занимается разработкой Joern и помогает пользователям своего фреймворка.

LLVM

LLVM — дедушка всех фреймворков для анализа программ. Это зрелая коллекция инструментов, предназначенных для разработки компиляторов.

LLVM является основой компилятора Clang, Clang Static Analyzer (CSA), klee и многих других известных инструментов. Поскольку он используется во многих популярных инструментах, он оптимизирован для быстрой работы. LLVM предоставляет API для информации AST, CFG и PDG, а также весь ряд других анализов. По сути, любая информация, доступная компилятору, доступна и разработчику инструмента LLVM. Кроме того, информация является 100% точной, так как компилятор не может допустить неверной информации.

Эта сила имеет свою цену — LLVM требует, чтобы все типы были определены, чтобы правильно анализировать код. Из-за неоднозначной грамматики C, если тип не определен, компилятор не может отличить определение функции от определения переменной, что приводит к ошибкам при синтаксическом анализе (цитировать). Если некоторые определения отсутствуют, LLVM может создать поврежденный AST с отсутствующими большими разделами.

Обычно эта информация предоставляется путем предоставления LLVM набора флагов компилятора, которые будут использоваться для компиляции программы. Получить эти флаги может быть сложно, если вы хотите проанализировать множество программ, поскольку флаги зависят от платформы и конфигурации. Это может привести к большим ручным усилиям для получения этих флагов, что может сделать LLVM непригодным для анализа крупномасштабных наборов программных данных.

Функция анализа LLVM обрабатывает только C/C++ на уровне исходного кода. Дополнительные утилиты доступны для LLVM IR, который представляет собой низкоуровневый язык ассемблера SSA, предназначенный для многих других языков.

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

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

Сравнительный анализ

Я реализовал простой инструмент рефакторинга с каждым фреймворком, чтобы оценить скорость каждого инструмента. Инструмент рефакторинга заменяет оператор for оператором while. Это можно сделать только с помощью AST, хотя информация о потоке управления необходима для обработки ранних break, cont inue или return. Вы можете получить доступ к исходному коду прототипа здесь: https://github.com/bstee615/pa_framework_examples.

Вот пример инструмента в работе. При вводе этой программы:

Тогда эта программа должна быть выходом.

Я измерил время работы моего прототипа инструмента в секундах на программе-примере, в среднем за 5 запусков. Результаты показаны ниже. Формат: Среднее значение ± станд. отклонение.

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

LLVM и SrcML очень похожи по производительности во всех практических вопросах. Примечательно, что я использовал Python для вызова SrcML и анализа выходного XML. Возможно, было бы немного быстрее, если бы я написал его на C++ и связал с библиотекой SrcML.

Джорн был самым медленным. Это может быть связано с накладными расходами на запуск виртуальной машины Scala и интерпретатора Джоерна.

Каждый из этих фреймворков имеет свою золотую середину в анализе программ. На самом деле анализ реальных программ затруднен. Есть много вариантов с разными размерами боли/удовольствия. Я сравнил скорость на небольшом примере, чтобы подчеркнуть различия между фреймворками. Я предлагаю вам провести собственное исследование этих трех фреймворков, чтобы выяснить, какой из них лучше всего подходит для вашего приложения. Самое главное, не будьте догматичны в отношении использования одного подхода над другим — например, предположим, что вы привыкли к LLVM, дающему вам точность на уровне компилятора в ваших анализах, вы можете получить выгоду от перехода на Joern, чтобы ускорить цикл разработки.

Ресурсы

[0] Ф. Ямагучи, Н. Голд, Д. Арп и К. Рик, Моделирование и обнаружение уязвимостей с помощью графов свойств кода, Симпозиум IEEE по безопасности и конфиденциальности, 2014 г., стр. 590–604, DOI: https ://doi.org/10.1109/SP.2014.44.

[1] Алехандра Гарридо и Ральф Джонсон. 2002. Проблемы рефакторинга программ на C. В материалах Международного семинара по принципам развития программного обеспечения (IWPSE '02). Ассоциация вычислительной техники, Нью-Йорк, штат Нью-Йорк, США, 6–14. DOI: https://doi.org/10.1145/512035.512039

[2] Бендерский, Э. (2007, ноябрь). Контекстная чувствительность грамматики C. Веб-сайт Эли Бендерскис ATOM. Получено 3 марта 2022 г. с https://web.archive.org/web/20210713114717/https://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar.

[3] М. Л. Коллард, М. Дж. Декер и Дж. И. Малетик, srcML: инфраструктура для исследования, анализа и манипулирования исходным кодом: демонстрация инструмента, Международная конференция IEEE по обслуживанию программного обеспечения, 2013 г., стр. 516–519, DOI: https://doi.org/10.1109/ICSM.2013.85

Первоначально опубликовано на https://benjijang.com