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

Реализация собственного инструмента анализа трассы. Анализ помеченных данных.

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

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

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

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

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

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

$ # Вывод трассы программы 01-copy в текстовом виде в файл 01-copy.txt
$ ../../../pin -t obj-intel64/CCA3Trace.so -o 01-copy.txt -- ./01-copy
$ # Вывод трассы программы 02-calculate в JSON-формате с информацией о прочитанных/записанных регистрах и участках памяти в файл 02-calculate.json
$ ../../../pin -t obj-intel64/CCA3Trace.so -d -j -o 02-calculate.json -- ./02-calculate

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

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

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

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

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

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

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

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

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

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

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

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

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

Формат входного файла с тестом

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

Название поля Тип Пояснение
step обязательное, целое число Номер шага трассы (нумерация с 0).
type обязательное, строка Тип действия. Может принимать значения source или sink. Значение source обозначает, что перед обработкой шага, указанного в step, необходимо дополнительно пометить данные в некоторых регистрах/участках памяти. Значение sink обозначает, что перед обработкой шага, указанного в step, необходимо вывести текущие регистры/участки памяти, содержащие помеченные данные.
taint необязательное, массив Это поле присутствует всегда, когда поле type установлено в значение source, и содержит массив регистров/участков памяти, данные в которых необходимо пометить.

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

Файл с ответами на тест должен представлять собой JSON-массив, каждый элемент которого соответствует записи с типом sink входного файла с тестом. Каждый элемент массива должен представлять собой JSON-объект со следующими полями.

Название поля Тип Пояснение
step обязательное, целое число номер шага трассы (нумерация с 0)
answer обязательное, массив ответ на тест - массив регистров/участки памяти, содержащих помеченные данные на момент времени перед выполнением данного шага

Далее перечислены требования к файлу с ответами.

  1. В массиве элементов, содержащих помеченные данные, не должно быть пересекающихся элементов (в том числе в множестве регистров (например, не могут присутствовать одновременно rax и ax)).
  2. В случае, если помеченные данные содержатся в части регистра, для которой не существует названия (например, 2-ой байт регистра r8), следует вывести тройку [имя 8-байтного регистра, смещение в байтах, размер в байтах] (например, ["r8", 1, 1]). При этом такая часть не должна содержать регистров с существующим названием (например, если помечены 3 младших байта регистра eax, следует вывести массив из 2 элементов ["ax", ["rax", 2, 1]).
  3. Точность анализа - байтовая. Байт данных считается помеченным, если помечен хотя бы один его бит.
  4. В случае, если какой-либо байт элемента не содержит помеченные данные, такой элемент не должен быть выведен - вместо него должен быть выведен более "точный" элемент/набор элементов.
  5. Количество выведенных элементов должно быть минимальным - если существуют 2 элемента, которые могут быть объединены в один, такое объединение должно быть произведено (с учётом предыдущих требований).

Правила распространения пометок

Распространение пометок происходит в соответствии с полями readRegs, writeRegs, readMem, writtenMem каждого шага трассы. Если регистр/участок памяти зависит по данным от другого регистра/участка памяти, содержащего помеченные данные на некотором шаге, то после обработки этого шага пометка должна также распространиться на данные, содержащиеся в этом регистре/участке памяти. Если в регистр/участок памяти с помощью команды типа mov (mov, cmov, movz, movs) на некотором шаге записываются непомеченные данные, то после обработки этого шага данный регистр/участок памяти должен быть удалён из множества регистров/участков памяти, содержащих помеченные данные. Следует считать, что каждый элемент, содержащийся в writeRegs, writtenMem, зависит по данным от всех элементов, содержащихся в readRegs, readMem. Таким образом, получаем следующие правила распространения пометок:

  1. Если для данного шага существует соответствующая запись с типом source в файле с тестом, пометить соответствующие элементы.
  2. Если хотя бы один элемент readRegs или readMem содержит помеченные данные, пометить также данные в элементах writeRegs, writtenMem.
  3. Иначе, если команда является командой типа mov (mov, cmov, movz, movs), снять пометки с данных, содержащихся в элементах writeRegs, writtenMem.

Анализ помеченных данных должен работать на трассах, снятых с программ, скомпилированных под архитектуру x86-64. При анализе помеченных данных из регистров следует учитывать только регистры общего назначения и регистр флагов rflags (см. справку по архитектуре x86-64) - на остальные регистры пометки распространяться не должны.

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

В подкаталоге PublicTests архива с вариантом размещены пять тестовых трасс ((имя программы).json) и соответствующих файлов с тестами ((имя программы).tests.json). Кроме того, даны исходные тексты соответствующих программ ((имя программы).c). Вам необходимо проверить разработанный вами инструмент, выполняющий анализ помеченных данных, и сдать архив с его исходными текстами. Проверка корректности решения будет заключаться в сравнении получаемых инструментом ответов с эталонными.

Для упрощения первоначальной отладки для первых двух тестовых трасс даны также ответы на тесты ((имя программы).out.json).

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

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

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

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

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