Вычисления без инструкций на x86
В этой статье обсуждается необычное применение особенностей защищённого режима архитектуры x86 — для произведения вычислений без исполнения инструкций, то есть за счёт внутренних механизмов процессора: аппаратного переключения задач, хитроумного управления памятью и нетривиальной логики вызова обработчика прерываний. Как известно, любая сколько-нибудь сложная система обладает полнотой по Тьюрингу, поэтому мало удивительного в том, чтобы найти её в неожиданных местах естественно эволюционировавшей x86. Приглашаю под кат интересующихся подобными низкоуровневыми извращениями.
Данная публикация основана на статье под названием «The Page-Fault Weird Machine: Lessons in Instruction-less Computation». Греет душу, что один из её соавторов, Sergey Bratus, — давний выпускник Физтеха. Впервые я узнал о данной работе из заметки Gwern Barwen «Surprisingly Turing-Complete», содержащей множество удивительных примеров Тьюринг-полных систем. Кстати, часть её переведена на Хабре, правда описываемому в данной статье явлению там отведено всего три предложения.
Оригинальная статья была опубликована в 2013 году, что может натолкнуть на вопрос об актуальности данного её пересказа в связи с завершившимся за эти годы переходом на x86–64, а следовательно отказом от защищённого режима исполнения в пользу long mode, в котором аппаратное переключение задач не поддерживается. Однако благодаря обратной совместимости архитектуры x86 излагаемая идея может быть реализована на современной аппаратуре и гипервизорах.
Продолжая тему актуальности, замечу, что первоисточник не претендовал на прямое практическое применение описанных в статье идей, а лишь приоткрыл завесу «странных вычислителей», обнаруживающихся в современных процессорах. Тем не менее, определённый полезный результат из этой работы следует напрямую: во-первых, запуск программы, которая нестандартным способом утилизирует крайние случаи, при этом полностью соответствуя спецификации — отличный способ поиска ошибок в железе и гипервизорах (и немало было найдено в QEMU, по словам авторов). Во-вторых, так как обычные гипервизоры тестируются и ориентированы на наиболее распространённые операционные системы, результат исполнения в них подобной неординарной программы может отличаться от ожидаемого на голом железе. Данный феномен, позволяющий обнаружить факт исполнения под гипервизором, называется red pill, по аналогии с красной таблеткой, которая позволила Нео осознать виртуальность привычного ему мира. Число red pills является важной характеристикой гипервизора, так как многие вредоносные программы пользуются ими для определения уровня «осторожности», с которой нужно исполняться, чтобы не быть обнаруженными антивирусным ПО и системами отладки, которые обычно запускаются в безопасной среде. На самом деле тренд применения red pill в последние годы пошёл на спад, так как всё больше сервисов мигрируют в облако, где всё работает в виртуальной среде, и создатели вирусов не готовы пожертвовать этим «рынком» ради усложнения собственного анализа. И тем не менее, приведу несколько примеров вредоносного ПО, меняющего своё поведение при наличии гипервизора. Хотя часть его уже и ушла в прошлое, в своё время оно нанесло немало вреда. Среди таких программ: Neutrino (2016 г.), Conficker (2008 г.), Rebhip (2011 г.), IRC боты: Phatbot (2008 г.), Rbot, SDbot/Reptile, Mechbot, SpyBot и другие (ссылки ведут на упоминания об использовании ими методов проверки наличия виртуальной среды). В-третьих, нестандартные способы произведения вычислений открывают широкие просторы для обфускации. Особенно перспективной видится обфускация с помощью подобных «странных» вычислений в контексте unikernel.
Red pill — программа, обнаруживающая виртуальную среду. Blue pill — вредоносный гипервизор
В чём же заключается «странность» вычислителя, которому посвящена эта статья, и как построить Тьюринг-полную машину без единого гвоздя без единой инструкции? Чтобы ответить на этот вопрос, нужно сначала напомнить читателям некоторые аспекты архитектуры x86.
Обработка исключений и аппаратное переключение задач
В архитектуре IA-32 существует функционал аппаратного переключения задач, предназначенный облегчить работу разработчикам операционных систем. Использованный вместе с механизмом call gates совершения системных вызовов, как предполагалось, он минимизирует затраты программистов на описание логики смены контекста. Но на сегодняшний день, насколько мне известно, всё это — мёртвый кремний, давно заброшенный операционными системами в пользу более производительных программных решений; со стороны же производителей процессоров деоптимизированный до микрокода. А в x86–64 поддержка аппаратного переключения задач вообще отключена.
Единственный пример использования аппаратного переключения задач, с которым я сталкивался (и который, кстати, близок к описанному в работе), — это использование в 32-bit Linux отдельной задачи (в терминах процессора) для обработки double fault, дословно, двойного исключения. Double fault возникает, если процессор столкнулся с ошибкой на этапе запуска или исполнения обработчика какого-то другого исключения или прерывания; например, в обработчике совершена попытка деления на ноль. Обычно, конечно, причиной double fault является не арифметика, а глубоко сломанное состояние процессора, именно поэтому системные таблицы, о которых пойдёт речь ниже, в Linux настроены так, что для обработки double fault используется отдельная задача, которая могла бы вывести в kernel panic «грязное» состояние основной задачи. Если же и в double fault возникает какая-то критическая ошибка, происходит triple fault, также известный как перезагрузка компьютера.
С каждой задачей в x86 ассоциировано состояние, хранящееся в task-state segment (TSS). Главным образом, в него сохраняются регистры процессора, подлежащие восстановлению при возобновлении исполнения задачи. Среди этих регистров нас будут особенно интересовать EIP (instruction pointer) — указатель на текущую исполняемую инструкцию, ESP (stack pointer) — указатель на вершину стека, CR3 — указатель на таблицу страниц (строго говоря, page directory), а также регистры общего назначения EAX и ECX, о необходимости в которых чуть ниже.
Содержимое TSS. Обратите внимание на расположение CR3, EIP, EAX, ECX, EDX, ESP.
Аппаратное переключение задач тесно связано с механизмами обработки прерываний, исключений, а также сегментацией памяти. Одними из важнейших таблиц, конфигурирующих работу процессора, являются GDT (Global Descriptor Table) — глобальная таблица дескрипторов и IDT (Interrupt Descriptor Table) — таблица дескрипторов прерываний. Опуская подробности, перечислю некоторые типы дескрипторов, которые могут в них располагаться: memory segment descriptor — дескриптор сегмента памяти (кода, данных), TSS descriptor — указатель на task-state segment, interrupt-gate descriptor — указатель на дескриптор одного из первых двух типов, определяющий, как обрабатывать прерывание — с переключением задачи или совершив far call. Неудивительно, что эти три головы гидры — управление памятью, задачами и прерываниями — неразлучны.
Тьюринг-полнота во всей красе
Это всё выглядит довольно сложно и, наверное, скрывает в себе вычислительную мощность, но откуда возникает Тьюринг-полнота? Дело в том, что при вызове обработчиков некоторых исключений, таких как page fault и double fault, в стек кладётся 4-байтный код ошибки. Сам код ошибки нам неинтересен, важен лишь побочный эффект, состоящий в уменьшении (не забываем, что стек в x86 растёт вниз) значения регистра ESP на 4. Но что произойдёт, если ESP на момент срабатывания прерывания уже равен нулю, то есть уменьшать его некуда? Было бы очень странно, если бы указатель на стек оборачивался вокруг 32 бит, поэтому в таких случаях срабатывает double fault-исключение.
Попробуем создать из описанных выше примитивов наш странный вычислитель. Для начала, так как никакие вычисления не будут производиться инструкциями процессора, присвоим регистру EIP во всех задачах недействительное значение, например, 0xFFFFFFFF. Это будет постоянно приводить к page fault, который срабатывает при ошибках доступа к памяти. Как мы уже выяснили, при попытке обработать page fault произойдёт нечто подобное:
if (esp == 0) {
goto double_fault_handler;
} else {
esp -= 4;
goto page_fault_handler;
}Уже намечается какое-то уменьшение значения, ветвление… Но для Тьюринг-полноты нам этого мало. Как уже можно догадаться, каждая «инструкция» нашего странного вычислителя будет исполняться побочными эффектами от срабатывания исключения. А так как одним из таких эффектов (согласно нашей конфигурации IDT и GDT) является загрузка в регистры содержимого очередной TSS, на момент обработки каждого исключения значение регистра CR3, отвечающего, как мы помним, за таблицу страниц, может быть своё (то, которое хранится в TSS, ассоциированного с данным исключением). И поскольку регистры IDTR и GDTR (не сохраняемые в TSS, а следовательно неизменные) хранят виртуальные адреса IDT и GDT, получается, что при исполнении очередной «инструкции» ⇒ срабатывании исключения ⇒ смене задачи ⇒ загрузке нового значения CR3 ⇒ смене таблицы страниц мы можем менять IDT и GDT, которые видит процессор. Вместе с IDT меняется и хранящийся в нём указатель на TSS, это также пригодится нам в дальнейшем.
Взаимосвязь между IDT, GDT и TSS. TR (Task Register) содержит индекс дескриптора текущей TSS в GDT.
Реализация movdbz-вычислителя
Получается, что исполнение «инструкции» состоит из следующих этапов:
Генерация исключения, которое выполнит следующую «инструкцию». Согласно конфигурации IDT и GDT, это приводит к смене задачи.
Загрузка TSS, ассоциированного со сгенерированным исключением, в регистровый файл. В частности, из TSS загружаются
EIP,ESP,CR3.В «стек» загруженной TSS кладётся код ошибки, а также (что более важно), если регистр
ESP > 0, то изESPвычитается 4, иначеESPне изменяется.Так как загрузка
CR3из шага 2 имела побочный эффект в виде смены таблицы страниц, результирующийESPбудет помещён в TSS, на который указывает ячейка в новом GDT (см. также Task Register) и который не обязан совпадать с исходным.Если условие из пункта 3 оказалось истинным и вычитание было успешным, то произойдёт попытка исполнения инструкций процессора, что невозможно ввиду недействительного значения
EIP, следовательно произойдёт переход на задачу, ассоциированную с исключением page fault; в противном случае следующей задачей будет ассоциированная с исключением double fault.
Запишем последовательность выше в виде псевдокода, в котором сразу введём некоторые обозначения: rsrc — это ESP, подгруженный из исходной TSS; rdest — это ESP, хранящийся в TSS, на которую указывает GDT после загрузки регистра CR3 из исходной TSS. label_zero — задача, ассоциированная с исключением double fault, label_nonzero — с исключением page fault. Также будем трактовать ESP как значение регистра нашего вычислителя, умноженное на 4, тогда из последнего на каждой обработке исключения будет вычитаться единица, а не четвёрка.
if (rsrc == 0) {
rdest = rsrc;
goto label_zero;
} else {
rdest = rsrc - 1;
goto label_nonzero;
}Последовательность выше — не что иное, как расшифровка инструкции movdbz, move-branch-if-zero-or-decrement (перемести-прыгни-если-ноль-или-уменьши). Как известно, инструкция subtract-and-branch-if-negative (вычти-и-прыгни-если-отрицательный-результат), которую несложно реализовать через вышеупомянутую movdbz(это строго показано в оригинальной статье), позволяет построить Тьюринг-полный вычислитель. Дочитавшим до сюда также, наверное, будет интересно узнать про более экзотическое доказательство — это компилятор Тьюринг-полного Brainfuck в набор инструкций movdbz-вычислителя.
Итак, наша инструкция movdbz имеет четыре аргумента:
movdbz rdest, rsrc, label_nonzero, label_zeroВ качестве упражнения для читателя остаётся написание с использованием одной только этой инструкции игры Жизнь Джона Конвея (коронавирус забирает лучших), использованной в демо авторов оригинальной статьи. На movdbz нужно написать именно логику эволюции ячеек, для вывода содержимого кадрового буфера на экран авторы используют реальные инструкции x86. Поэтому утверждение про недействительное значение EIP выполняется в их демо не во всех TSS.
Сопротивление архитектуры
В real-mode с его A20 и high memory, когда стрельба себе в ногу входила в стандартный арсенал программиста, можно было много всего себе позволить. Но времена изменились, и в защищённом режиме Intel создали некоторые препоны насилию нам своими чипами, которые, в частности, мешают нам развлекаться со своими странными вычислителями. Например, ESP должен указывать внутрь выделенного под стек участка памяти (иначе мы получим исключение #SS — stack-segment fault), поэтому нужно пометить первую страницу памяти в каждой таблице страниц как содержащую стек. И так как в ESP хранится значение, в 4 раза большее содержимого «регистра» нашего вычислителя, последний может принимать значения от 0 до 1023, а не от 0 до 4095 (используется 4 КиБ страница). Но подобные мелочи мне кажутся довольно скучными, поэтому далее я поговорю только о тех препятствиях, методы борьбы с которыми мне показались интересными.
Данные отдельно, кодлеты отдельно
Одной из незамеченных в вышеприведённых рассуждениях оказалась следующая проблема: в пункте 4 из списка выше в «destination TSS» записывается не только ESP, но и CR3. Хорошо подумав, можно осознать, что ESP, хранящиеся в разных TSS, — это регистры нашего вычислителя, и их значения не должны быть привязаны инструкциям. А CR3 как раз отвечает за то, какая инструкция сейчас исполняется, ведь от CR3 зависит содержимое IDT, а значит и то, какие инструкции исполнятся следующими — то есть он определяет положение текущей инструкции в «программе». В связи с этим мы хотим разделить TSS на две части — отвечающую за инструкции, которые исполнятся следующими; и содержающую регистр, с которым оперирует текущий movdbz. Поэтому мы «рассекаем» TSS границей страницы между регистрами ECX и EDX(сейчас стоит обратиться к картинке с содержимым TSS выше). Таким образом, так как в верхней части TSS из полезных для нашего вычислителя данных остаётся только ESP, основным смыслом трюка с CR3 становится переотбражение в верхнюю часть TSS физической страницы c rdest, куда будет записан результат исполнения инструкции.
Busy bit
Также крайне находчивым мне показался способ обхода помехи busy bit, встроенного в указатель на TSS в GDT и определяющего, находится ли сейчас процессор в состоянии обработки исключения. Если этот бит выставлен, архитетура запрещает переключение задач, что делает невозможным пункт 5 из описания выше. Этот бит автоматически выставляется при срабатывании исключения и, при обычном исполнении, очищается при выходе из обработчика. Но у нас нет обработчика, мы не исполняем инструкций процессора, поэтому нужно найти другой способ очищать этот бит. Будет нелишним заметить, что, по словам автора, на то, чтобы дойти до этой идеи и реализовать её, у него ушло 8 недель из 10, затраченных на весь проект.
Решение этой проблемы следующее: расположим GDT так, чтобы она перекрывалась с TSS! GDT может занимать максимум 16 страниц, последние 8 байт каждой из этих страниц — это, как мы помним, вследствие рассечения TSS, регистры EAX и ECX. Хак состоит в том, чтобы заранее в каждой TSS положить на место регистров EAX и ECX этот самый указатель на TSS (строго говоря, дескриптор TSS) с очищенным busy bit-ом. Таким образом, при каждой выгрузке TSS из регистрового файла на 4 шаге busy bit в дескрипторе текущей TSS в GDT будет выставляться в ноль. Осталось только записать в IDT указатели на правильные дескрипторы в GDT — те, которые занимают последние 8 байт в каждой из 16 страниц.
Заключение
Каков же смысл во всех этих исхищрениях, в построении такого «странного вычислителя»? Во-первых, у описанных выше идей есть прямое, хотя и не столь актуальное, практическое применение — создание red pill, позволяющей отличить голое железо от гипервизора. Во-вторых, такое неортодоксальное применение архитектуры x86, выискивание тёмных уголков и крайних случаев может доставить неподдельное удовольствие любителям эзотерического программирования. В-третьих, данная работа несёт, на мой взгляд, глубокую философскую идею, подчёркивая ценность хакерского склада ума применительно к нахождению «странных вычислителей» там, где они не подразумевались или где их не видят другие. Ведь любой эксплойт — по сути плод мастерского программирования «странной виртуальной машины», своеобразным «байткодом» которой являются баги, фичи и различные неожиданные пути исполнения целевой платформы. Кстати, тентакли макаронного монстра на обложке как раз и олицетворяют всевозможные особенности и изъяны, обнажаемые программными и аппаратными системами и с охотой используемые разработчиками эксплойтов для нарушения задумываемого хода работы программы.
Основные источники (в рекомендуемом порядке ознакомления):
