Анализ трассы выполнения программы, часть 1

Реализация собственного инструмента анализа трассы. Восстановление графа потока управления по трассе.

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

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

Инструмент получения трассы

Инструмент получения трассы программы реализован как Pin-инструмент и находится в архиве с вариантом задания в подкаталоге CCA3Trace. Инструмент предназначен для работы в Linux-окружении. Вы можете использовать любой современный дистрибутив Linux, в т.ч. развёрнутый в виртуальной машине.

В качестве подготовительного шага необходимо будет разместить предложенный инструмент в подкаталоге source/tools/CCA3Trace дистрибутива Pin и осуществить его сборку командой make.

Запуск инструмента осуществляется с обязательным ключом -o, указывающим имя выходного файла с трассой. Необязательный ключ -j переключает режим вывода трассы с текстового формата на формат JSON. Примеры:

$ # Вывод трассы программы 01-linear в текстовом виде в файл 01-linear.txt
$ ../../../pin -t obj-intel64/CCA3Trace.so -o 01-linear.txt -- ./01-linear
$ # Вывод трассы программы 02-bubblesort в JSON-формате в файл 02-bubblesort.json
$ ../../../pin -t obj-intel64/CCA3Trace.so -j -o 02-bubblesort.json -- ./02-bubblesort

Ограничения инструмента

Инструмент корректно работает с программами, для которых выполнено следующее.

  1. Программа не порождает новые процессы и потоки выполнения.
  2. Программа скомпонована со стандартной библиотекой динамически, с использованием таблиц PLT и GOT.
  3. Программа не осуществляет системные вызовы напрямую, минуя стандартную библиотеку.
  4. Программа не использует UNIX-сигналы.
  5. Программа не использует динамически сгенерированный или модифицируемый код.

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

Формат трассы

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

Название поля Тип Пояснение
address обязательное, целое число адрес выполняемой инструкции в десятичном виде
hexDump обязательное, строка машинный код выполняемой инструкции в шестнадцатеричном виде, от первого байта к последнему
text обязательное, строка декодированный вид выполняемой инструкции
isBranch необязательное, логическое значение если это поле присутствует, то оно имеет значение true, и это указывает на то, что данная инструкция осуществляет передачу управления
isForeignBranch необязательное, логическое значение это поле может присутствовать только одновременно с полем isBranch, и его значение true указывает на то, что данная команда передаёт управление за пределы программы
foreignTargetAddress необязательное, целое число это поле присутствует всегда, когда установлено поле isForeignBranch, и содержит десятичный адрес целевой команды за пределами программы
foreignTargetName необязательное, строка это поле присутствует всегда, когда установлено поле isForeignBranch, и указывает имя внешней подпрограммы, на которую передаётся управление

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

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

Постановка задачи

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

Разработанный инструмент должен принимать два аргумента командной строки: имя входного файла с JSON-трассой и имя выходного файла с графом. Рекомендуется использовать для разработки один из следующих языков программирования:

  • C/C++;
  • Rust;
  • D;
  • Java;
  • Python;
  • Ruby;
  • Perl.

Инструмент сдаётся в виде архива со всеми необходимыми исходными файлами, Makefile (если применяется) и текстовым файлом README, в котором необходимо описать требуемые шаги по сборке (в т.ч. требуемые библиотеки). Более быстро могут быть проверены решения, выполеннные на скриптовых языках без внешних библиотечных пакетов.

Формат выходного файла с графом потока управления

Выходной файл с графом потока управления разрабатываемый инструмент должен сформировать в формате Graphviz DOT. Вершины графа — базовые блоки из трассы и внешние подпрограммы, рёбра — выполняющиеся в трассе переходы между вершинами. Далее перечислены требования к DOT-файлу.

  1. Тип графа — strict digraph.
  2. Вершины могут быть перечислены явно, а могут быть и заданы неявно как концы рёбер (см. документацию по языку DOT). Оба варианта принимаются как правильные.
  3. Идентификатором вершины базового блока является строка длиной 16 символов, представляющая собой шестнадцатеричную запись адреса начала базового блока, например 0000000000400440 или 00000000004003C8. Ведующие нули обязательны, а регистр символов не имеет значения.
  4. Идентификатором вершины внешней подпрограммы является строка с её именем (т.е. значением поля foreignTargetName).
  5. Несколько раз встреченный в трассе базовый блок или внешняя подпрограмма не должны приводить к дублированию вершин.
  6. Ребро, которое пройдено в трассе несколько раз, не должно дублироваться.
  7. Количество вершин в графе должно быть минимальным: базовые блоки должны иметь наибольший возможный размер без нарушения их свойств. Это означает, в частности, что нельзя создавать по одному базовому блоку на каждую инструкцию.
  8. Порядок вершин и рёбер в выходном файле не имеет значения.
  9. Вершины и рёбра могут иметь произвольные внутренние атрибуты (shape, label и т.д.) для отображения. При проверке решений учитывается только структура графа и идентификаторы вершин.
  10. Пробельные символы и комментарии в выходном файле остаются на ваше усмотрение.

Далее приведён фрагмент минимального корректного выходного файла, где перечислены только рёбра.

strict digraph {
"0000000000400440" -> "__libc_start_main@plt";
"__libc_start_main@plt" -> "0000000000400540";
"0000000000400540" -> "00000000004003C8";
# и так далее
}

Эквивалентный пример с явным перечислением вершин и необязательными атрибутами выглядит следующим образом.

strict digraph {
"0000000000400440" [ shape = box, label = "0000000000400440\nxor ebp, ebp\nmov r9, rdx\npop rsi\nmov rdx, rsp\nand rsp, 0xfffffffffffffff0\npush rax\npush rsp\nmov r8, 0x4005b0\nmov rcx, 0x400540\nmov rdi, 0x400430\ncall 0x400410" ];
"0000000000400440" -> "__libc_start_main@plt";
"__libc_start_main@plt" [ label = "__libc_start_main@plt" ];
"__libc_start_main@plt" -> "0000000000400540";
"0000000000400540" [ shape = box, label = "0000000000400540\npush r15\npush r14\nmov r15d, edi\npush r13\npush r12\nlea r12, ptr [rip+0x2008be]\npush rbp\nlea rbp, ptr [rip+0x2008be]\npush rbx\nmov r14, rsi\nmov r13, rdx\nsub rbp, r12\nsub rsp, 0x8\nsar rbp, 0x3\ncall 0x4003c8" ];
"0000000000400540" -> "00000000004003C8";
# и так далее
}

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

$ # Сгенерировать изображение графа в файле 01-linear.dot.png
$ dot -Tpng -O 01-linear.dot

Проверка на открытых тестах

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

Для упрощения первоначальной отладки для первых двух тестовых трасс даны также PNG-изображения эталонных графов.

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

Проверка на слепых тестах

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

Самая длинная трасса среди слепых тестов не превышает 400000 шагов. Обработка каждой трассы вашим решением должна длиться не более, чем одну минуту, на компьютере с процессором Intel Core i7-6700 с 32 Гбайт оперативной памяти.

Система оценивания
Тип теста Количество тестов Баллы за один тест Суммарные баллы
Открытые тесты 5 1 5
Слепые тесты 5 2 10
Всего 15