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

Итак, в предыдущей статье  я показал несколько занятных случаев для иллюстрации того, что написанное на языке высокого уровня может при компиляции приводить к непокрытому объектному («ассемблерному») коду даже в случае 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