IKWYD: Он знает о каждом шаге программы

Цель: создание инструмента для изменения покрытия кода программы.

Ограничение: имеется только исполняемый код, исходных кодов нет.

Требования: простота, скорость, точность.

Что нам может предложить процессор

Процессоры Intel предоставляют специальные возможности для отладки и измерения эффективности приложений[Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1 ]. Доступ к ним осуществляется через регистры DB0-DB7, а так же через ряд специфичных для модели процессора регистров (MSR). Следующие основные возможности предоставляются:

  • исключение отладки (#DB) — передает управление программы на процедуру отладчика в момент возникновения отладочного события;
  • исключение точки отладки (#BP) — см. описание инструкции точки останова (int 3) ниже;
  • регистры адресов точек остановки (DR0 — DR3) — определяют адреса до 4 точек остановки;
  • регистр статуса отладки (DR6) — отображает условия возникновения исключения отладки или точки остановка. Бит BS (бит 14) регистра указывает на то, что исключение было сгенерировано после возведения флага TF;
  • регистр управления отладкой (DR7) — задает области памяти или порты ввода-вывода, для которых генерируется отладочные события;
  • флаг T (trap) в TSS — генерировать отладочное событие (#DB) когда происходит попытка переключиться в поток с установленным флагом T в TSS;
  • Флаг RF (resume) в регистре EFLAGS — предотвращает повторную генерацию исключения на одной и той же инструкции;
  • флаг TF (trap) в регистре EFLAGS — генерирует отладочное исключение(#DB) после исполнения каждой инструкции;
  • инструкция точки останова (int 3) — генерирует исключение точки останова (#BP), которое передает управление процедуре или задаче отладчика. Инструкция используется, когда регистров точек останова не достаточно. На основе данной инструкции был реализован метод динамического анализа, описанный в предыдущих главах;
  • сохранение информации о последних исполненных ветвях, прерываниях или исключениях в стеке регистров MSR LBR ( last branch record ). Запись в LBR состоит из адреса «откуда был совершен переход» и адреса «куда был совершен переход».  Данная информация так же может быть доставлена с помощью сообщений BTM;

Исключение отладки (#DB) обрабатывает вектор прерывания int 1. Здесь отладчики уровня ядра размещают свой код, реализующий логику отладки. Для определения причины исключения используется регистр статуса отладки (DR6). Процессор генерирует исключение отладки во время исполнения инструкции при условии, что взведен флаг TF в регистре EFLAGS. Данное исключение является «исключением-ловушкой»(trap), потому что генерируется после того, как инструкция была исполнена. Процессор не генерирует исключение после инструкций, которые устанавливают флаг TF. К примеру, исключение не произойдет после инструкции POPF. Процессор очищает флаг TF перед тем, как вызывать обработчик int 1. В случае, если одновременно вызываются два прерывания (int 3 и int 1), то прерывание int 1 будет обрабатываться первым.

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

Pic1

Впервые возможность устанавливать точки останова на заданные ветви, прерывания, исключения, а так же при переходе от одной ветви к другой была введена в процессоры семейства P6. Данная возможность была улучшена в следующих процессорах: Pentium 4, Intel Xeon, Pentium M, Intel® CoreTM Solo, Intel® CoreTM Duo, Intel® CoreTM2 Duo, Intel® CoreTM i7, а так же Intel® AtomTM. Данные процессоры имеют схожий набор функционала по отслеживанию ветвей. Различаться могут размер стека для хранения данных о последних ветвях LBR, а так же набор аппаратно специфичных регистров, используемых для управления возможностями. Далее в тексте, будет дано общее описание возможностей процессоров вышеперечисленных семейств. Специфичные возможности и параметры будут представлены на примере процессора Intel Core i7.

MSR-регистр IA32_DEBUGCTL предоставляет собой битовое поле для управления расширенными возможностями отладки. Регистр имеет номер 01D9h и содержит следующие важные биты (для всех поддерживаемых процессоров):

  • флаг LBR (последняя ветвь, прерывание, исключение) (bit 0). Если данный бит установлен, то процессор записывает информацию о последних ветвях, прерываниях и исключениях. Формат стека LBR специфичен для процессора и описан ниже;
  • флаг BTF (трассировка по ветвям) (bit 1). Если данный флаг установлен, то процессор воспринимает флаг TF из регистра EFLAGS как «трассировку по ветвям» вместо «трассировки по инструкциям». Данный механизм позволит значительно сократить накладные расходы при трассировке, когда нет необходимости трассировать каждую инструкцию;
  • флаг TR (включение сообщений трассировки) (bit 6). Если данный флаг установлен, задействован механизм сообщений трассировки. На каждую ветвь, прерывание или исключение процессор шлет сообщение через системную шину в формате BTM;
  • флаг BTS (хранилище трассировки ветвей) (bit 7). Если данный флаг установлен, то процессор сохраняет BTM в специальный буфер в памяти BTS;
  • флаг BTINT (исключение трассировки ветвей)  (bit 8). Если данный флаг установлен, то процессор генерирует исключение при заполнении буфера BTS.

В случае, если флаг LBR (bit 0) из регистра IA32_DEBUGCTL MSR установлен, процессор начинает автоматически записывать данные об исполненных ветвях, прерываниях и исключениях  в стеке регистров MSR LBR. Когда процессор генерирует исключение отладки (#DB), он автоматически очищает флаг LBR до запуска обработчика исключения. Стек MSR-регистров при этом не очищается, что позволяет проводить анализ сохраненных значений. Если LBR сброшен, а TR установлен, то процессор продолжает заполнять LBR, потому что данный стек используется при генерации BTM. Прерывание #DB не очищает данный флаг автоматически.

Процессоры семейства i7 (ядро Nehalem) предоставляют 16 пар регистров MSR[Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3B: System Programming Guide, Part 2 ] для сохранения данных о последних исполненных ветвях кода. Формат данных в регистрах, содержащих значение о месте программы, откуда было передано управление, представлено в следующей таблице.

 

Битовое поле Битовое смещение Доступ Описание
Data 47:0 чтение Адрес, откуда было передано управление
SIGN_Ext 62:48 чтение Знаковое расширение данного регистра
MISPRED 63 чтение Устанавливается, если переход бы предсказан

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

Текущее положение в стеке хранится в регистре MSR_LASTBRANCH_TOS. Номера специфичных для i7 регистров представлены в следующей таблице.

Номер Имя Описание
1C9h MSR_LASTBRANCH_TOS Указатель стека LBR
680h MSR_LASTBRANCH_0_FROM_IP Часть стека LBR (первый элемент), содержащая адрес памяти, из которого был совершен переход
6C0h MSR_LASTBRANCH_0_TO_IP Часть стека LBR (первый элемент), содержащая адрес памяти, на который был совершен переход

Что с этим можно сделать

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

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

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

Значения приведенных выше MSR-регистров доступны только из режима ядра. При реализации алгоритма оценки покрытия только в режиме ядра неизбежны следующие проблемы:

  • cложность идентификации контекста (процесса и потока ) в котором выполняется обработчик прерывания int 3;
  • cложность идентификации модуля к которому принадлежит исполняемый код.

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

  • отладчик пользовательского режима. Эта часть системы отвечает за старт процесса, фиксирование фактов загрузки модулей, старта процессов и потоков;
  • обработчик прерывания int 1. Эта часть системы отвечает за чтение данных из LBR и передачу пользовательскую часть.

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

После того как флаг TF установлен и инструкция исполнена, управление получает часть системы, расположенная в ядерном адресном пространстве. Здесь фиксируется информация о переходе. После этого необходимо установить флаг BTF, который сбрасывается перед передачей управления обработчику int 1.

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

 hardware_debug

Обмен между подсистемой, расположенной в ядре,  и подсистемой пользовательского режима происходит через стандартный механизм ioctl. Получение предыдущей ветви выполняется при обработке шага трассировки в пользовательском режиме. Это дает возможность получить данные для последнего перехода.

Что в итоге получилось

Реализованная утилита проста и наглядна. Называется она IKWYD-0.2.0 (исходные коды). Консольная программа принимает один аргумент — коммандная строка для запуска исселдуемой программы. Утилита сама подгружает драйвер при старте и выгружает при завершении работы.  Скомпилированный проект, исходные коды и описание может быть загружено со страницы проекта.

Из известных минусов на данный момент: драйвер не правильно работает на многопроцессорных системах — требуется доработка. Утилита значительно притормаживает из-за того что флаг TF взводится в пользовательском режиме. Если кто-то знает, как это сделать в драйвере — обязательно расскажите мне об этом!

Буду рад услышать любой фидбэк.