Реализация собственного инструмента анализа трассы. Восстановление графа потока управления по трассе.
Задание посвящено анализу трассы выполнения программы в части восстановления потоков управления. Вам предлагается проанализировать последовательность выполненных процессором инструкций программы и построить межпроцедурный граф потока управления, соответствующий покрытой трассой части кода программы.
Инструмент получения трассы
Инструмент получения трассы программы реализован как Pin-инструмент и находится в архиве с вариантом задания в подкаталоге CCA3Trace. Инструмент предназначен для работы в Linux-окружении. Вы можете использовать любой современный дистрибутив Linux, в т.ч. развёрнутый в виртуальной машине.
В качестве подготовительного шага необходимо будет разместить предложенный инструмент в подкаталоге source/tools/CCA3Trace дистрибутива Pin и осуществить его сборку командой make.
Запуск инструмента осуществляется с обязательным ключом -o, указывающим имя выходного файла с трассой. Необязательный ключ -j переключает режим вывода трассы с текстового формата на формат JSON. Примеры:
Ограничения инструмента
Инструмент корректно работает с программами, для которых выполнено следующее.
- Программа не порождает новые процессы и потоки выполнения.
- Программа скомпонована со стандартной библиотекой динамически, с использованием таблиц PLT и GOT.
- Программа не осуществляет системные вызовы напрямую, минуя стандартную библиотеку.
- Программа не использует UNIX-сигналы.
- Программа не использует динамически сгенерированный или модифицируемый код.
Формат трассы
Для тестирования будут использоваться трассы в JSON-формате. Трассы в текстовом формате предлагаются только для удобства отладки. На верхнем уровне трасса представляет собой JSON-массив, каждый элемент которого соответствует очередному шагу трассы. Шаг описывается JSON-объектом со следующими полями.
| Название поля | Тип | Пояснение |
|---|---|---|
| address | обязательное, целое число | адрес выполняемой инструкции в десятичном виде |
| hexDump | обязательное, строка | машинный код выполняемой инструкции в шестнадцатеричном виде, от первого байта к последнему |
| text | обязательное, строка | декодированный вид выполняемой инструкции |
| isBranch | необязательное, логическое значение | если это поле присутствует, то оно имеет значение true, и это указывает на то, что данная инструкция осуществляет передачу управления |
| isForeignBranch | необязательное, логическое значение | это поле может присутствовать только одновременно с полем isBranch, и его значение true указывает на то, что данная команда передаёт управление за пределы программы |
| foreignTargetAddress | необязательное, целое число | это поле присутствует всегда, когда установлено поле isForeignBranch, и содержит десятичный адрес целевой команды за пределами программы |
| foreignTargetName | необязательное, строка | это поле присутствует всегда, когда установлено поле isForeignBranch, и указывает имя внешней подпрограммы, на которую передаётся управление |
Внешние по отношению к программе участки кода не попадают в трассу. Это означает, что следующий шаг после вызова внешней подпрограммы (т.е. после шага с признаком isForeignBranch) — это шаг программы, который будет выполняться после выхода из внешней подпрограммы.
Постановка задачи
Необходимо разработать собственный инструмент анализа трассы в JSON-формате, который строит межпроцедурный граф потока управления без рёбер сквозь вызов (но с рёбрами вызова и возврата). Вспомогательные начальная и конечная вершина не строятся.
Разработанный инструмент должен принимать два аргумента командной строки: имя входного файла с JSON-трассой и имя выходного файла с графом. Рекомендуется использовать для разработки один из следующих языков программирования:
- C/C++;
- Rust;
- D;
- Java;
- Python;
- Ruby;
- Perl.
Инструмент сдаётся в виде архива со всеми необходимыми исходными файлами, Makefile (если применяется) и текстовым файлом README, в котором необходимо описать требуемые шаги по сборке (в т.ч. требуемые библиотеки). Более быстро могут быть проверены решения, выполеннные на скриптовых языках без внешних библиотечных пакетов.
Формат выходного файла с графом потока управления
Выходной файл с графом потока управления разрабатываемый инструмент должен сформировать в формате Graphviz DOT. Вершины графа — базовые блоки из трассы и внешние подпрограммы, рёбра — выполняющиеся в трассе переходы между вершинами. Далее перечислены требования к DOT-файлу.
- Тип графа — strict digraph.
- Вершины могут быть перечислены явно, а могут быть и заданы неявно как концы рёбер (см. документацию по языку DOT). Оба варианта принимаются как правильные.
- Идентификатором вершины базового блока является строка длиной 16 символов, представляющая собой шестнадцатеричную запись адреса начала базового блока, например 0000000000400440 или 00000000004003C8. Ведующие нули обязательны, а регистр символов не имеет значения.
- Идентификатором вершины внешней подпрограммы является строка с её именем (т.е. значением поля foreignTargetName).
- Несколько раз встреченный в трассе базовый блок или внешняя подпрограмма не должны приводить к дублированию вершин.
- Ребро, которое пройдено в трассе несколько раз, не должно дублироваться.
- Количество вершин в графе должно быть минимальным: базовые блоки должны иметь наибольший возможный размер без нарушения их свойств. Это означает, в частности, что нельзя создавать по одному базовому блоку на каждую инструкцию.
- Порядок вершин и рёбер в выходном файле не имеет значения.
- Вершины и рёбра могут иметь произвольные внутренние атрибуты (shape, label и т.д.) для отображения. При проверке решений учитывается только структура графа и идентификаторы вершин.
- Пробельные символы и комментарии в выходном файле остаются на ваше усмотрение.
Далее приведён фрагмент минимального корректного выходного файла, где перечислены только рёбра.
Эквивалентный пример с явным перечислением вершин и необязательными атрибутами выглядит следующим образом.
Полученный DOT-файл может быть преобразован в изображение, которое будет полезным при отладке вашего решения. Для этого используется следующая команда (в системе должен быть установлен пакет graphviz).
Проверка на открытых тестах
В подкаталоге PublicTests архива с вариантом размещены пять тестовых трасс. Каждая трасса дана в двух форматах: текстовом и JSON-формате. Кроме того, даны исходные тексты соответствующих программ. Вам необходимо проверить разработанный вами инструмент восстановления графа потока управления и сдать архив с его исходными текстами. Проверка корректности решения будет заключаться в сравнении получаемых инструментом графов с эталонными.
Для упрощения первоначальной отладки для первых двух тестовых трасс даны также PNG-изображения эталонных графов.
Если на каком-либо открытом тесте ваша программа работает некорректно, вам будет указано на одно (произвольно выбранное) несоответствие между вашим ответом и эталонным (лишнее ребро, недостающее ребро и т.п.). При этом будут указаны адреса базовых блоков, где возникает ошибка.
Проверка на слепых тестах
Дополнительно ваши решения проверяются на пяти слепых тестах, т.е. на трассах, которые вам заранее не известны. Принцип проверки такой же, что и для открытых тестов, с тем отличием, что при неправильном ответе будет указан только тип ошибки, но не адреса базовых блоков.
Самая длинная трасса среди слепых тестов не превышает 400000 шагов. Обработка каждой трассы вашим решением должна длиться не более, чем одну минуту, на компьютере с процессором Intel Core i7-6700 с 32 Гбайт оперативной памяти.
| Тип теста | Количество тестов | Баллы за один тест | Суммарные баллы |
|---|---|---|---|
| Открытые тесты | 5 | 1 | 5 |
| Слепые тесты | 5 | 2 | 10 |
| Всего | 15 | ||