Реализация собственного инструмента анализа трассы. Анализ помеченных данных.
Задание посвящено анализу помеченных данных по трассе выполнения программы. Вам предлагается проанализировать последовательность выполненных процессором инструкций и реализовать алгоритм анализа помеченных данных, учитывающий зависимости по данным, представленные в трассе.
Инструмент получения трассы
Инструмент получения трассы программы реализован как Pin-инструмент и находится в архиве с вариантом задания в подкаталоге CCA3Trace. Инструмент предназначен для работы в Linux-окружении. Вы можете использовать любой современный дистрибутив Linux, в т.ч. развёрнутый в виртуальной машине.
В качестве подготовительного шага необходимо будет разместить предложенный инструмент в подкаталоге source/tools/CCA3Trace дистрибутива Pin и осуществить его сборку командой make.
Запуск инструмента осуществляется с обязательным ключом -o, указывающим имя выходного файла с трассой. Необязательный ключ -j переключает режим вывода трассы с текстового формата на формат JSON. Необязательный ключ -d включает вывод информации о прочитанных/записанных регистрах и участках памяти. Примеры:
Ограничения инструмента
Инструмент корректно работает с программами, для которых выполнено следующее.
- Программа не порождает новые процессы и потоки выполнения.
- Программа скомпонована со стандартной библиотекой динамически, с использованием таблиц PLT и GOT.
- Программа не осуществляет системные вызовы напрямую, минуя стандартную библиотеку.
- Программа не использует UNIX-сигналы.
- Программа не использует динамически сгенерированный или модифицируемый код.
Формат трассы
Для тестирования будут использоваться трассы в 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 | обязательное, массив | ответ на тест - массив регистров/участки памяти, содержащих помеченные данные на момент времени перед выполнением данного шага |
Далее перечислены требования к файлу с ответами.
- В массиве элементов, содержащих помеченные данные, не должно быть пересекающихся элементов (в том числе в множестве регистров (например, не могут присутствовать одновременно rax и ax)).
- В случае, если помеченные данные содержатся в части регистра, для которой не существует названия (например, 2-ой байт регистра r8), следует вывести тройку [имя 8-байтного регистра, смещение в байтах, размер в байтах] (например, ["r8", 1, 1]). При этом такая часть не должна содержать регистров с существующим названием (например, если помечены 3 младших байта регистра eax, следует вывести массив из 2 элементов ["ax", ["rax", 2, 1]).
- Точность анализа - байтовая. Байт данных считается помеченным, если помечен хотя бы один его бит.
- В случае, если какой-либо байт элемента не содержит помеченные данные, такой элемент не должен быть выведен - вместо него должен быть выведен более "точный" элемент/набор элементов.
- Количество выведенных элементов должно быть минимальным - если существуют 2 элемента, которые могут быть объединены в один, такое объединение должно быть произведено (с учётом предыдущих требований).
Правила распространения пометок
Распространение пометок происходит в соответствии с полями readRegs, writeRegs, readMem, writtenMem каждого шага трассы. Если регистр/участок памяти зависит по данным от другого регистра/участка памяти, содержащего помеченные данные на некотором шаге, то после обработки этого шага пометка должна также распространиться на данные, содержащиеся в этом регистре/участке памяти. Если в регистр/участок памяти с помощью команды типа mov (mov, cmov, movz, movs) на некотором шаге записываются непомеченные данные, то после обработки этого шага данный регистр/участок памяти должен быть удалён из множества регистров/участков памяти, содержащих помеченные данные. Следует считать, что каждый элемент, содержащийся в writeRegs, writtenMem, зависит по данным от всех элементов, содержащихся в readRegs, readMem. Таким образом, получаем следующие правила распространения пометок:
- Если для данного шага существует соответствующая запись с типом source в файле с тестом, пометить соответствующие элементы.
- Если хотя бы один элемент readRegs или readMem содержит помеченные данные, пометить также данные в элементах writeRegs, writtenMem.
- Иначе, если команда является командой типа 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 |