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

Вместо введения.

Итак, в предыдущей статье  я показал несколько занятных случаев для иллюстрации того, что написанное на языке высокого уровня может при компиляции приводить к непокрытому объектному («ассемблерному») коду даже в случае 100% покрытия для исходного языка.

В этой статье я опишу методику инструментирования на основе промежуточного ассемблера. Данный метод в частности используется таким инструментом как LDRA, с которым мне недавно пришлось столкнуться в рамках одного проекта. Плюсом данного метода инструментирования является то, что само ПО писать можно на любом языке, который может быть транслирован в ассемблер: хочешь на С++, хочешь на Brainfuck.

Эта статья является в некотором роде реверс-инжинирингом того, как устроено инструментирование в LDRA. А также иллюстрацией, как подобное инструментирование может быть реализовано.

Дисклеймер: я не пишу профессионально на python, данная статья и примеры к ней не учат писать на python. Также я не являюсь специалистом в области регулярных выражений. Многие вещи можно сделать проще и более оптимально, чем представлено в примере к статье. Весь код написан исключительно для иллюстрации метода инструментирования.

Что мы будем инструментировать?

Итак, мы будем инструментировать программу на уровне промежуточного ассемблера, который для нас будет создан компилятором (например с помощью опции компилятора "-S" для GCC и языка С). У этого метода есть плюсы и минусы. 

Плюсы: код, который мы инструментируем, очень близок к тому, что будет исполнять процессор (ну, в простом случае), код очень просто устроен структурно.

Минусы: код не линейно соответствует тому, что написано программистом (из-за оптимизаций и прочих перестановок), и не всегда просто отследить, какой фрагмент ассемблера соответствует какому участку кода языка более высокого уровня. Для инструментирования как такового это не очень существенно, но понять, как покрытие, собранное д��я ассемблерного кода, соответствует коду, который вы, написали порой не легко.

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

Методика инструментирования.

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

В английском варианте дополнительный код, встраиваемый в программу, чаще называется probe. В виду того, что какой-либо общей русскоязычной терминологии я не нашел, то буду использовать слово «трассёр», которое, на мой взгляд, лучше отражает суть, чем калька с английского «зонд».

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

Рамка считывания.

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

• начало метки;

• переход на другую метку;

• возврат из процедуры.

Тут есть момент условности. Мы собираемся инструментировать промежуточный ассемблер, который для нас сделает компилятор. У этого компилятора есть свой диалект для обозначения меток в коде, поэтому парсер, используемый для разбиения, должен понимать диалект, на котором «говорит» компилятор.

Упрощая, метка в коде - это «название» некоторого адреса с которого начинается исполняемый фрагмент кода. Частным случаем метки является начало функции. Метки в ряде случаев могут быть заданы программистом непосредственно (например, использование оператора «goto» в C). Или могут быть добавлены компилятором для обозначения точек для переходов.

Пример меток в коде:

foo: <--- ЭТО МЕТКА
…
jne .L12
…
.L12: <--- И ЭТО МЕТКА
…

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

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

И еще, для удобства чтения графов в дальнейшем можно построить ��писок всех символов в секции исполняемого кода, которые компилятор решит создать для нашей программы. Это позволит отличать метки-функции от произвольных меток, добавленых компилятором. Этот список может не совпадать с набором описанных функций (даже для «чистого» С), так как часть из них может быть выкинута в ходе оптимизации или подвергнута каким-либо трансформациям.

Скипы и джампы.

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

• начало каждого блока - сразу после объявления метки;

• конец каждого блока - вставляется либо перед инструкцией перехода, либо перед началом новой метки, либо перед возвратом из процедуры;

• конец перехода - это специальный трассёр, который вставляется после каждого перехода для того, чтобы отследить произошел этот переход или нет.

Трассёры в начале и конце блоков вызываются автоматически при исполнении блока. Это происходит потому что блок - это линейный код, не содержащий условных конструкций. Как я говорил выше, у этого правила есть исключение, которое возникает в том случае, когда внутри блока вызывается какая-либо функция, которая не возвращается. Функция может не вернуться, например, в случае завершения программы, либо в случае, когда в ней выполняется нелокальный переход. В этом случае будет вызван только «открывающий» трассёр.

Так же особым случаем является трассёр, который вставлен после условного перехода. Он может быть вызван или не вызван в зависимости от выполнения инструкции перехода. Если он вызывается, то значит предыдущая инструкция условного перехода «не сработала» и произошел скип, а если он не вызывается, то произошел джамп. Давайте рассмотрим пример для псевдокода ниже:

foo:
  call __instrument0
  …
  call __instrument1
  jne .L10 // Jump to L10
  call __instrument2
  …
  call __instrument3
  .L10:
  call __instrument4

Если переход на метку .L10 произойдет то будут вызваны следующие маркеры:
__instrument0, __instrument1, __instrument4

В случае если переход не произойдет, то будут зафиксированы такие метки:
__instrument0, __instrument1, __instrument2, __instrument3 и __instrument4.

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

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

Граф исполнения.

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

Разобьем код на фрагменты, которые будем хранить в массиве (make_instrument.py::fragments). Каждый элемент этого массива будет представлять из себя блок кода (ins_blocks.py::CodeBlock). Из важных сейчас полей класса CodeBlock можно выделить jtransition, stransition и ftransition. Это собственно поля,содержащие информацию о том, куда случился переход из данного блока, а также о его типе, соответственно jump, skip или fall-thru в случае, когда в конце метки нет перехода, а есть просто следующая метка.

Собственно, make_instrument.py первым делом проходит по всем строкам ассемблерного листинга, созданного gcc для каждого файла исходного кода, и выделяет блоки, исполняемое безусловно. Затем идет построение графа переходов (transitions), в результате которого строится граф переходов от блока к блоку с определением их типов. В завершении выводится общее число переходов. Эта информация необходима для того, чтобы в дальнейшем определить размер массива, используемого в модуле инструментирования для хранения информации о переходах, собранной во время исполнения программы (финальное число будет передано при сборке в виде макроса TRANSITIONS, смотри toolbox/Makefile.koi::koi_toolbox).

Как построить трассу?

Мы построили граф переходов и определили их общее число, давайте теперь рассмотрим, а как собственно можно собрать данные о исполнении программы. Чтобы что-то собрать нужно что-то сохранить. В нашем случае информацию о переходах мы будем хранить в памяти нашей программы, которая должна быть слинкована с неким дополнительным объектным файлом, реализующим сбор данных о трассе и содержащим определение массива переходов (это файл лежит в папке toolbox). Для простоты объявим массив переходов приблизительно так:

typedef struct __attribute__((packed)) {
        void * from;
        void * to;
        unsigned int flags;
        size_t t;
} transition_t;

static transition_t  __transitions[TRANSITIONS];

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

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

Для того чтобы заполнить этот массив в каждой точке инструментирования вызывается функция-трассёр - __koi_covdump(). Объявлена она следующим образом:

void __attribute__((used, noinline))
  __koi_covdump(unsigned int from, unsigned int to, unsigned int id);

При каждом вызове ей будут передана информация, откуда ее вызвали, куда она должна перейти и ID перехода - собственно его номер.

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

Как уже говорилось выше для того чтобы собрать информацию о покрытии нам нужно вставить определенный код в созданный компилятором ассемблер. Это делается в методе CodeBlock.instrumentBlock в который передается номер трассёра. Дальше этот номер трассёра используется чтобы с помощью platform.asm.instrument() получить собственно фрагмент кода, который будет вставлен в начале и конце блока.

Код трассёра платформо-специфичен и в нашей реализации для x86_64 выглядит вот так (не обращайте внимания на конкретные значения):

        pushq   %rbp ## INS
        pushq   %rdi ## INS
        pushq   %rsi ## INS
        pushq   %rax ## INS
        pushq   %rdx ## INS
        pushq   %rcx ## INS
        pushfq   ## INS
        movl    $5, %edi ## Номер строчки откуда
        movl    $0, %esi ## Номер строчки куда (0 для метки в начале блока)
        movl    $53, %edx ## Номер трассёра
        callq   ___koi_covdump ## INS
        popfq    ## INS
        popq    %rcx ## INS
        popq    %rdx ## INS
        popq    %rax ## INS
        popq    %rsi ## INS
        popq    %rdi ## INS
        popq    %rbp ## INS

Что происходит в этом блоке? Чтобы сохранить информацию о прохождении точки трассы, нам нужно вызвать функцию __koi_covdump(), в которую мы передаем 3 аргумента. Для того чтобы встроить этот код в уже созданный для нас ассемблер нам нужно согласно ABI сохранить все регистры, которые могут быть изменены при вызове этой функции на стек, вызвать функцию, передав требуемые аргументы и вернуть ранее сохранённые на стеке значения на место. Это выглядит немного по-разному для разных платформ, но суть та же.

Сама __koi_covdump() (toolbox.c) устроена очень просто. Она заполняет массив __transitions[] используя номер трассёра (id, третий аргумент) в качестве индекса и отслеживает тип перехода (jump или skip). Для того чтобы понять какой тип перехода произошел проверяется адрес источника перехода, если он совпадает для текущего и предыдущего трассёра (по индексу в массиве переходов), то текущий трассёр находится за инструкцией условного перехода и следовательно условный переход не произошел.

Файл toolbox.c также содержит функцию __koi_covdump_render(), которая печатает покрытие - содержимое массива __transitions[]. Эту функцию мы зарегистрируем в нашей тестовой программе с помощью atexit(), чтобы получить данные о собранной трассе при выходе из программы.

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

Веселые картинки:

Реализация демо—кода доступна тут - https://github.com/bougumot/koi.git

Для запуска примера потребуется третий питон и gcc или clang. Для того чтобы просматривать *.dot файлы потребуется graphviz (ну либо любая online dot-смотрелка, например https://dreampuf.github.io/GraphvizOnline/)

Как играть:

Чтобы построить инструментированную демо-программу, переходим в папку проекта (там, где лежит make_instrument.py) и делаем:

export KOI_ROOT=`pwd`

 Далее переходим в examples и делаем :

make all_oc

 После того как все соберется запустите tst_app:

./tst_app
Usage: <option> <directory name>
1::5:0;[1]
2::49:559;[1]
49::559:0;[1]
53::5:0;[1]

Собственно программа напечатала свой вывод и за ним трассу. Соберем трассу в coverage.log и сохраним его там же в examples.

Теперь запустим

make graph

Для каждого файла программы создастся *.cov файл. Для ls.c он будет выглядеть вот так (часть обрезана):

        FUNCTION COVERAGE AND TRANSITIONS
===============================================================================
_main :58/556(10.43)
-------------------------------------------------------------------------------
Type    From    To      Status
S       49      50      ---
J       49      559     COVERED
S       64      65      ---
J       64      574     ---
S       99      100     ---
J       99      494     ---
…

То есть main() покрылся на 10% (58 строк из 556) и покрыт только 1 переход. Графически это выглядит вот так:

Обратите внимание на LBB0_17 в самом низу, он окрашен в коричневый цвет, для этого блока пройден только открывающий трассёр, а завершающий - нет. Данный блок вызывает _exit(), который не возвращается.

Теперь давайте запустим приложение с опциями:

user$ ./tst_app -u ./

Добавим новую трассу к ранее собранному coverage.log.

Удалим *.dot файлы и перестроим покрытие.

make graph

        FUNCTION COVERAGE AND TRANSITIONS
===============================================================================
_main :380/556(68.35)
-------------------------------------------------------------------------------
Type    From    To      Status
S       49      50      COVERED
J       49      559     COVERED
S       64      65      COVERED
J       64      574     ---
S       99      100     COVERED
J       99      494     ---
S       115     116     COVERED
S       150     151     COVERED
J       150     527     ---
S       166     167     COVERED
J       166     482     ---
S       255     256     ---
J       255     330     COVERED
J       327     339     ---
S       338     339     COVERED
S       371     372     ---
J       371     420     COVERED
S       399     400     ---
J       399     420     ---
S       418     419     ---
J       418     541     ---
S       463     464     COVERED
S       479     480     COVERED
J       479     116     COVERED
J       480     494     COVERED
J       492     464     ---
S       505     506     COVERED
J       505     521     ---
S       526     527     ---
S       540     541     ---
S       558     559     ---
S       573     574     ---

Картина поменялась и покрытых переходов (и строк) стало больше:

Соответственно, добавляя все новые тесты и накапливая покрытие, можно либо покрыть всю программу, либо определить участки "мертвого" кода, которые не будут выполнены ни при каких условиях.

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

P.S.: Весь код, на который ссылается статья (включая ls.c в examples, который я утянул у кого-то с гитхаба), доступен под открытой лицензией, так что развлекайтесь как хотите.
Пример запускался и проверялся на x86 MacOS, clang-1200.0.32.21, Python 3.9.13 и RH Linux, gcc (GCC) 7.1.0, Python 3.6.8