ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
МОДЕЛИРОВАНИЕ ОПЕРАЦИОННОЙ СЕМАНТИКИ МАШИННЫХ ИНСТРУКЦИЙ
© 2011 г. В.А. Падарян, М.А. Соловьев, А.И. Кононов Институт системного программирования РАН 109004 г. Москва, ул. Солженицына, 25 E-mail: vartan@ispras.ru, eyescream@ispras.ru, extreme@ispras.ru Поступила в редакцию 03.09.2010 г.
В работе предлагается модель, позволяющая описывать операционную семантику машинных инструкций для широкого класса целевых архитектур. Особенностью модели является то, что она предназначена для обратного по сравнению с классической компиляторной задачей тракта преобразований, но в то же время модель позволяет выполнять над ней различные оптимизирующие преобразования. Для описания целевой машины применяются внешние спецификации. Рассмотрена прототипная подсистема интерпретации модели.
1. ВВЕДЕНИЕ
Анализ бинарного кода, нацеленный на восстановление алгоритмов и повышение уровня их представления, включает в себя большое количество этапов. Часть из используемых этапов анализа применяется последовательно, с целью выделения интересующей части программы. Другие используются итеративно для восстановления отдельных аспектов семантики.
В настоящее время актуальна задача анализа кода, снабженного механизмами, препятствующими как отладке, так и статическому анализу. Примерами подобных механизмов являются различные запутывающие преобразования [1]. Значительная часть преобразований такого рода нацелена на противодействие статическому анализу. Так, преобразование „диспетчер" [2] не оказывает заметного усложняющего влияния при применении динамического анализа. Кроме того, использование динамического анализа в виде снятия трассы работы целевого процессора (стенда) и последующего ее анализа позволяет анализировать не только пользовательский код, но и код системный, например, драйверов.
В системе динамического анализа кода ХгБк [3] применяется подход с использованием полносистемных симуляторов для сбора трасс.
Среда поддерживает несколько целевых процессорных архитектур (в том числе Intel 64 и MIPS64) за счёт использования прослойки абстракции архитектуры. На данный момент указанная прослойка обладает возможностями декодирования инструкций в машинно-независимый вид и построения частичных графов зависимостей по данным отдельных инструкций. Указанные особенности позволяют при реализации алгоритмов анализа, основанных на анализе зависимостей, абстрагироваться от целевой машины, что, в свою очередь, значительно упрощает разработку.
Возможность построения декомпозиции на зависимости позволяет проводить более точно различные виды анализа, в том числе слайсинг трассы [4, 5]. Тем не менее, вопрос повышения уровня представления выделенного алгоритма не может быть решен без возможности анализа семантики составляющих алгоритм инструкций по отдельности и в совокупности.
В настоящей работе предлагается модель, пригодная для описания операционной семантики машинных инструкций. Описывается алгоритм приведения бинарной машинной инструкции к модельному виду. Кроме того, рассматривается применение описываемой
модели к задаче интерпретации инструкций.
Прежде чем перейти к изложению предлагаемой модели, необходимо указать требования, исходя из которых принимались решения при ее построении.
Модель должна позволять описывать операционную семантику как пользовательских, так и системных инструкций современных процессорных архитектур. Важно поддержать различные по своей природе процессорные архитектуры, как CISC, так и RISC. В набор архитектур, рассматривавшихся при построении модели, входят Intel 64, MIPS64, PowerPC, ARM v6, SPARC и Motorola m68k. Описание семантики инструкций этих архитектур должно быть достаточным для моделирования всех эффектов выполнения инструкции, в том числе побочных (влияние на слово состояния машины).
Необходимо обеспечить такой уровень модели, который позволял бы без существенных дополнительных затрат применять различные виды компиляторных оптимизаций, таких как удаление общих подвыражений или удаление мертвого кода. Это требование вызвано необходимостью противодействия тем видам запутывающих преобразований, которые намеренно усложняют выражения, входящие в операторы программы, или граф потока управления за счет введения дублирующих или нереализуемых путей. Наличие данных о семантике машинных инструкций, составляющих алгоритм, является необходимым требованием при решении этих задач. Тем самым, модель должна быть приближена к промежуточным представлениям, применяемым в современных компиляторах (SSA, трехадресный код и так далее).
Наконец, необходимо обеспечить возможность интерпретации модельного представления, а именно указать, каким образом из состояния машины перед выполнением моделируемой инструкции можно получить ее состояние после. Тем самым может быть обеспечен режим работы системы анализа, сходный с работой отладчика.
Дальнейшее повествование построено следующим образом. В разделе 2 приводится обзор связанных работ и выделяются те их особенности, которые могут быть использованы
при решении задачи моделирования семантики инструкций. В разделе 3 описывается построенная модель. Указываются отдельные объекты модели и их взаимосвязь. В разделе 4 дается краткое описание способа спецификации целевой машины и указывается способ построения модели инструкции при наличии такой спецификации. В разделе 5 кратко описывается прототип интерпретатора модели. В разделе 6 дается заключение и указываются направления дальнейших работ.
2. ОБЗОР РАБОТ
Решаемая задача напрямую связана с двумя сферами компиляторных технологий: собственно построением компиляторов и бинарной трансляцией.
С точки зрения задачи построения компиляторов, пересечение с настоящей работой находится на уровне промежуточного представления. Используя классификацию из [6], можно охарактеризовать это промежуточное представление как представление низкого уровня (LIR). В самом деле, исходными данными для моделирования являются машинные инструкции, оперирующие с конкретными регистрами и адресами в памяти (в противовес виртуальным регистрам или переменным). Несмотря на то, что такое представление может быть механически повышено до представления среднего уровня (MIR) за счёт того, что является его подмножеством, подобное механическое повышение бессмысленно, так как ведет к повышению уровня представления лишь формально.
Одной из широко распространенных форм представления низкого уровня является форма RTL (register transfer list), применяемая, с различными модификациями, в большом количестве компиляторных продуктов, например, в открытом компиляторе GNU GCC [7]. В GCC также используется представление среднего уровня GIMPLE.
Следует учитывать, однако, что поставленная задача, в противовес задаче компиляции, предполагает обратный тракт: от машинных инструкций к более высоким представлениям. Такой тракт встречается в задаче бинарной трансляции, когда машинные инструкции одной
процессорной архитектуры сначала повышаются до некоторого модельного представления, а затем используются для синтеза машинных инструкций другой архитектуры.
Частным случаем можно считать среды для динамического инструментирования, в которых исходная и целевая архитектуры совпадают, например, Valgrind [8] и iDNA [9].
В работах [10, 11] описываются соответственно система статической и динамической бинарной трансляции. Обе системы среди поддерживаемых архитектур указывают и CISC-архитектуру Intel 64. В качестве промежуточного представления используется расширенная форма RTL, называемая авторами H-RTL. Следует отметить, что в данных работах рассматривается вопрос трансляции лишь пользовательских инструкций.
Среда Valgrind [8] использует в качестве промежуточного представления виртуальную RISC-машину с достаточно малым набором операций. При этом регистровый файл и пространство памяти целевой машины являются внешними по отношению к виртуальной машине, то есть трансляции не подвергаются. Valgrind не поддерживает системные инструкции. Кроме того, с точки зрения расширяемости среда Valgrind достаточно неудобна: трансляция в промежуточное представление и последующий синтез закодированы напрямую, а не при помощи внешних спецификаций. Кроме того, этапы декодирования инструкции и формирования ее модели не отделены друг от друга, что вносит дополнительные сложности.
Среди существующих систем бинарной трансляции реальный интерес в контексте данной работы представляют лишь те, которые, во-первых, в том или ином виде используют спецификации для описания машин и, во-вторых, способны проводить трансляцию из и в CISC-архитектуры (в частности, Intel 64). Трансляция в инструкции CISC-машины необходима для обеспечения эффективного решения задачи интерпретации. В то время как первое требование реализовано в достаточном количестве рассмотренных работ, второе значительно ограничивает этот список.
Проведенный обзор работ позволяет сделать вывод о необходимости реализации своей
модели операционной семантики машинных инструкций, не обладающей недостатками рассмотренных работ и удовлетворяющей заявленным требованиям. Предлагаемая модель представляет собой комбинацию возможностей рассмотренных систем с дополнением оригинальными особенностями. Без изменений может быть использована модель адресных пространств, используемая в близких видах в [8] и [3]. Во многом удовлетворяет заявленным требованиям модель, используемая в качестве промежуточного представления в [8], однако она должна быть дополнена возможностью подгрузки внешних спецификаций наподобие используемых в [11].
3. МОДЕЛЬ ОПЕРАЦИОННОЙ СЕМАНТИКИ
Перед изложением построенной модели необходимо обозначить некоторые сложности, с которыми приходится сталкиваться при моделировании современных наборов инструкций. В большей части указанные сложности относятся к CISC-архитектурам, в частности к Intel 64.
Первой сложностью является нетривиальный вид регистровых файлов современных процессоров. Так, регистры могут являться частями друг друга (Intel 64), располагаться в нескольких теневых наборах (MIPS64) или иметь организацию в виде регис
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.