И снова здравствуйте, друзья! Сегодня я расскажу вам историю о том, как я упоролся виртуализацией программного кода (в плане обфускации и защиты, конечно же, а не в плане этих ваших ВМВарей или ВиртуалБоксов). Тема виртуализации кода достаточно давно меня интересует. В фоне с основным своим родом деятельности я то и дело почитывал всякие интересные вещи об этом. Более того, мой бро Haunt давно просил меня написать что-нибудь интересненькое о виртуализации, а я — ленивая жопа, все никак этого не делал. И тут однажды мне пришла в голову идея, как совместить ее (тему виртуализации) с еще одним моим увлечением — мета-программированием. Я вообще знатный задрот в плане ЯП, знаете ли. В итоге (будем считать, что в качестве упражнения) я решил запилить свою собственную небольшую крекмишу с псевдо-кодом и виртуальной машиной. Ровно такую же, как мы рассматривали в моей предыдущей статье про VEH и INT3, но под своим особым мета-программным соусом. Справедливости ради, я сделал ее раньше, чем стал тестить свой анклав из говна и палок. Но тут матчасть посложнее, и я решил сделать эту статью потом… ну то есть сейчас… не важно. Само собой эту крекмишу я залил на сайт со спецового вида спецовыми спецами по реверсингу, само собой они ее быстро порешали и даже успели изрядно полить желчью и гуаном всю тему с ней, но суть упражнения была далеко не в том, чтобы этих спецов уделать, а научиться компилировать, когда компилируешь…
Содержание:
1. Введение
2. Стековая виртуальная машина
3. Программирование крекмиши
4. Типы и структуры ВМ
5. Создаем эмиттер
6. Создаем ридер и дизассемблер
7. Создаем компилятор
8. Создаем виртуальную машину
9. Заключение
1. Введение
Мы живем с вами в эпоху, когда куча языков с разной степенью успеха пытается заменить собой эти ваши единственные рассово-верные Сишечку и Плюсы. Любимым языком из этой категории для меня был, есть и скорее всего будет язык Nim. Помимо сравнительно читаемого петоно-подобного синтаксиса и неплохого кодогенератора в Сишечку у языка Nim есть особо дорогая моему сердцу фича — мета-программирование. Мета-программирование в Nim по своей сути очень напоминает его же в Lisp’е, но без бесконечно бесящего синтаксиса, состоящего из скобочек больше, чем полностью. В подавляющем большинстве компиляторов и интерпретаторов исходный код представляется в виде древовидной структуры — AST (abstract syntax tree — абстрактно синтаксического дерева), так вот Nim по средствам так называемых «макросов» позволяет получить эту древовидную структуру во время компиляции и произвольно изменять ее. Забегая вперед, эта дивная фича и позволит нам компилировать, когда компилируем. Но для начала давайте обсудим еще несколько вводных вещей.
Как работают всякие динамические интерпретируемые языки, типа Петонов, например? Мы будем рассматривать все этапы в наиболее упрощенном виде. Исходный код в памяти преобразуется в AST с помощью парсера и лексера (бывает, что парсер и лексер реализованы одним и тем же компонентом, но не суть важно). Затем (учитывая, что на прошлом этапе не было синтаксических ошибок) AST проходит несколько этапов упрощения, при которых высокоуровневые конструкции языка преобразуются в более низкоуровневые, это сделано для своего рода минимизации следующих этапов. При этом может производиться семантический анализ (говоря простым языком, проверка «правильности» или корректности написанного кода). Затем AST преобразуется в байт-код для виртуальной машины, которая в последствии будет этот байт-код исполнять. Байт-код и, собственно, виртуальная машина по своей архитектуре в принципе могут быть любыми, но так исторически сложилось, что очень многие виртуальные машины являются стековыми (CLR, JVM, CPython и многие другие). В статье мы будем делать именно стековую виртуальную машину, мне кажется, что для начала она будет проще для понимания, да и знания эти могут пригодится при разборе байт-кода многих других ВМ.
Чем же интересна обфускация через виртуализацию? Ответ достаточно банален: если для нативного кода или же для каких-то байт-кодов типа MSIL (.NET), WASM (WebAssembly), JVM (Java), CPython, Lua/LuaJIT уже существуют готовые дизассемблеры или декомпиляторы, то для байт-кода (или псевдо-кода, я буду использовать эти термины, как равнозначные), который придумаем мы, такого готового средства нет. Поэтому аверскому реверсеру (он же «дятел» в аверском мире) придется потратить побольше времени для понимания того, что же на самом деле делает программа, реализованная в виде ВМ и байт-кода. Нужно будет разобраться, какой опкод псевдокода что делает и зачем (при условии защиты программы от работы в песочнице, конечно). Безусловно, недостатком такого подхода будет существенное уменьшение производительности программы (если программа полностью реализована через ВМ), но виртуализировать можно только те ее части, которые нам действительно хочется скрыть от назойливых глаз. Поэтому в легитимном софте то и дело встречается виртуализация кода, связанного с лицензией, генерацией ключей или какими-то еще приватными вещами, чтобы чуток подзапарить реверсера/крякера, который будет пытаться этот лицензионный код сломать или понять, что он (код) делает.
Писать компилятор байт-кода и саму виртуальную машину мы будем на языке программирования Nim (как вы уже могли догадаться). У аверов есть пунктик по поводу языка Nim, особо всратые сигнатуры особо всратых аверов детектят вообще весь софт написанный на Nim. В контексте статьи мы не будем обсуждать то, каким образом эти сигнатуры можно сбивать (если интересно, то пишите в комментариях к статье, можем это обсудить). Но для особо упоротых танкистов просто скажу, что не надо орать на меня, если у вашего антивируса вдруг начнется эрекция на семплы из этой статьи, никакой малвари встроенной там нет, успокойтесь.
Код из этой статьи будет реализовывать минимальный и немного вырожденный пример, я много чего упрощу, чтобы это было понятно и удобно читать в формате статьи, но надеюсь, что вам будет интересно. Рассматривать что-то более универсальное в одной статье имеет мало смысла, будет слишком много букаф. Да мы с вами даже не будем писать свой сборщик мусора (GC – garbage collector) для нашей виртуальной машины, а переиспользуем тот, что реализован в самом ЯП Nim. Ну и да, представленный ниже код не претендует на истину в последней инстанции, может иметь баги, вызывать нозальных демонов и так далее. Всегда готов и рад услышать здравую критику или какие-либо идеи по улучшению представленного ниже кода. Критикуя — предлагайте свои решения и идеи, в спорах рождается истина, если спор имеет хоть какой-то смысл. Ну давайте начинать.
2. Стековая виртуальная машина
Стековая виртуальная машина — на то она и стековая, что подавляющее большинство вещей в ней решается через стек. Почти все инструкции нашей виртуальной машины будут либо брать что-то со стека, либо класть что-то на стек, либо делать и то и другое. Я подразумеваю, что вы все из каких-то базовых курсов по программированию и структурам данных знаете, что такое стек, если нет, то добро пожаловать на вики: https://ru.wikipedia.org/wiki/Стек — пробегитесь по этой статье и возвращайтесь читать дальше мою. Как давным-давно выяснили разработчики всяческих виртуальных машин для всяческих языков программирования стековая организация виртуальной машины прекрасно подходит для того, чтобы транслировать семантику (смысл) программного кода, представленного в виде AST в байт-код. Давайте рассмотрим следующий пример:
Код:
import macros
dump_tree:
1 + 2 * 3
# nim e astdump.nims
#
# StmtList
# Infix
# Ident "+"
# IntLit 1
# Infix
# Ident "*"
# IntLit 2
# IntLit 3Допустим, мы хотим каким-то образом скомпилировать выражение «1 + 2 * 3». Процедура dump_tree из библиотеки macros языка Nim выведет в консоль то, каким образом код внутри блока dump_tree представляется в виде AST (древовидной структуры, помните же, да?). StmtList — это просто контейнер, который может содержать в себе несколько выражений, но на него обращать существенное внимание сейчас не стоит. Infix — это одно выражение, у которого может быть левая часть, оператор и правая часть. Так сложилось, что оператором в языке Nim является первый потомок Infix, левой частью — второй потомок, а правой частью — третий потомок. Обратите внимание, что Infix для умножения является третьим потомком Infix сложения в данном случае. Это обусловлено тем, что по правилам математики, которые все должны еще со школы знать, умножение имеет больший приоритет, чем сложение, то есть исполняется первым (по сути, исходное выражение является «(1 + (2 * 3))», если мы расставим правильно скобки по его смыслу). Интерпретатор (именно интерпретатор, а не компилятор), если бы исполнял такую конструкцию, сначала бы вычислил значение Infix умножения, потом само значение подставил бы в третьего потомка Infix сложения, а затем уже исполнил Infix сложения. Не так страшно, если вы толком ничего не поняли о том, что я сказал в этом абзаце, надеюсь, что дальше станет понятнее.
Код:
PUSH 1 # Положить на стек 1
PUSH 2 # Положить на стек 2
PUSH 3 # Положить на стек 3
MUL # Взять со стека два числа, перемножить, положить результат на стек
ADD # Взять со стека два числа, сложить, положить результат на стекВот так может выглядеть байт-код стековой виртуальной машины, который получится при компиляции исходного выражения. Ровно так же, как это делал интерпретатор, мы можем обходить узлы AST и генерировать код для каждого из узлов рекурсивно. Давайте рассмотрим, как это будет делать алгоритм. Алгоритм «заходит» в узел StmtList, перечисляет всех потомков узла и «заходит» в каждого из них. У нас такой потомок один. Алгоритм «заходит» в Infix, для этого узла ему сначала нужно посетить второго и третьего потомка, а затем в зависимости от оператора сгенерировать соответствующую инструкцию (для «+» - инструкцию ADD, для «*» - инструкцию MUL). При посещении узлов IntLit алгоритм просто генерирует инструкции PUSH с аргументом целого числа, взятого из узла литерала, и затем выходит, прекращая рекурсивное посещение потомков (ведь потомков у узла нет). Применяемый в этом алгоритме для посещения всех узлов дерева паттерн проектирования называется «Посетитель» (он же «Visitor» в англоязычной литературе). Байт-код стековой виртуальной машины в этом случае в точности повторяет поведения интерпретатора, наверное, именно поэтому стековые виртуальные машины стали часто использоваться при реализации языков программирования. «Я считаю, что это – стековая ВМ потому, что это удобно» (с).
Итак, давайте теперь соберем все мысли вместе. На этапе компиляции мы с помощью мета-программирования получим AST некоторого кода. С помощью паттерна Visitor обойдем все узлы полученного AST рекурсивно — ровно так же, как это сделал бы интерпретатор. Для каждого узла наш компилятор будет генерировать соответствующий байт-код. Затем мы возьмем этот блок байт-кода, обернем в код ВМ и подставим на место исходного кода, который нам нужно было защитить. Ну чтож, звучит, как план — надежный, как швейцарские часы!
3. Программирование крекмиши
Крекмиша будет ровно такая же, как и предыдущей статье. Код будет запрашивать у пользователя пароль в консоли, хешировать его предельно простым алгоритмом, сравнивать значение хеша с эталонным и выводить сообщения об успехе или неуспехе в консоль.
Код:
import vm/types
import vm/compiler
import vm/runtime
const hash_seed = ct_seed.uint32
proc cp_hash_string(str: string): uint32 {. compile_time .} =
result = hash_seed
for i in 0 ..< len(str):
let v1 = result * 0xab10f29f'u32
let v2 = v1 + ord(str[i]).uint32
result += v2 and 0xffffff'u32
proc original_function() =
echo("Enter password, bro: ")
var password = read_line(stdin)
var xhash = hash_seed
for i in 0 ..< len(password):
let v1 = xhash * 0xab10f29f'u32
let v2 = ord(password[i]).uint32
xhash += (v1 + v2) and 0xffffff'u32
if xhash == cp_hash_string("TestDatVmStuff"):
echo("Password is valid, bro!")
echo("You are real cracker, bro!")
else:
echo("Password is invalid, bro!")
echo("Better luck next time, bro!")Константа hash_seed является уникальным зерном для алгоритма хеширования и генерируется в зависимости от даты и времени компиляции. Процедура cp_hash_string хеширует строку на этапе компиляции и подставляет на место ее вызова 32-битный хеш от переданной строки. Процедура original_function проделывает все манипуляции с пользователем и консолью, описанные выше. Почему же я назвал ее «оригинальной функцией»? Помните, я говорил, что компиляторы в байт-код проводят своего рода упрощения кода, переводя высокоуровневые конструкции языка в низкоуровневые. Давайте в качестве упражнения и для упрощения себе жизни при разработке компилятора проделаем это руками.
Код:
proc lowered_function() {. virtualize .} =
echo("Enter password, bro: ")
var password = read_line(stdin)
var xhash = hash_seed
var slen = len(password)
var i = 0
while i < slen:
let v1 = xhash * 0xab10f29f'u32
let v2 = ord(password[i]).uint32
let v3 = (v1 + v2) and 0xffffff'u32
xhash = xhash + v3
i = i + 1
if xhash == cp_hash_string("TestDatVmStuff"):
echo("Password is valid, bro!")
echo("You are real cracker, bro!")
else:
echo("Password is invalid, bro!")
echo("Better luck next time, bro!")
lowered_function()Обратите внимание, что цикл for мы упростили до цикла while. Эта типичный пример так называемого «lowering» в компиляторах. Для того, чтобы в генераторе кода (или байт-кода, как хотите) не делать обработку двух видов циклов (for и while) можно сделать обработку одного низкоуровневого из них, а высокоуровневый привести к виду низкоуровневого заранее (до генерации кода). Таких примеров перевода одних конструкций в другие в компиляторах можно встретить много, для нашего минимального примера достаточно и одного (в образовательных целях).
На последней строчке кода стоит вызов процедуры, а у самой процедуры есть интересный атрибут «virtualize» - это главный макрос, который мы с вами напишем позже, он проделает всю работу над процедурой lowered_function, преобразуя ее в байткод и вызов ВМ.
Давайте посмотрим на этот код и прикинем, какие структуры данных и код нам потребуется, чтобы реализовать процедуру lowered_function в байт-коде виртуальной машины. Для начала я вижу, что в процедуре используются три типа данных. Строки (string) и 32-битные беззнаковые целые числа (uint32) используются явно, но, поскольку у нас есть и операторы сравнения, то нам понадобится еще и булевый тип данных. Таким образом, нам понадобятся опкоды для того, чтобы положить на стек константы для string и uint32 типов данных. В коде есть операторы умножения, сложения, побитового «И», применяемые над типом данных uint32, функции len, echo и ord, применяемые над типом string. Все эти операторы и функции будут в нашей ВМ представлены отдельными опкодами. Кроме того, нам нужна возможность объявлять, получать и изменять значения локальных переменных, для этого тоже будет отдельные опкоды. Нам нужно выводить и считывать строки из/в консоли, еще вам два опкода, получите и распишитесь. Ну и, конечно, самое важное для любой ВМ – опкод NOP (no operation, то есть ничего не делать). Шучу. Его наличие не обязательно, но я его добавил для того, чтобы господа реверсеры, которые будут эту крекмиху решать, имели возможность «занопить» какие-то участки байт-кода. Крекми же подразумевает, что ее как-то можно решить за конечное и адекватное время.
Одной из задач, которую я себе ставил этим проектом, была создать своего рода полиморфную ВМ. То есть, например, сделать так, чтобы при каждой сборке опкоды имели разное значение. Для этого я навернул разных алгоритмов в компилятор, некоторые из них хорошие, некоторые из них плохие. При этом для экономии места я не стал включать в статью алгоритмы полиморфизации кода самой виртуальной машины (только байт-кода), хотя на практике это лучше сделать. Но опкоды у нас будут каждый раз разные и мы даже сделаем небольшой генератор мусорного байт-кода. Мне показалось, что эти вещи будет интереснее осветить в статье, чем другие. Само собой задача статьи – не дать готовый инструмент, а показать основы и пробудить интерес к этой теме в общем.
4. Типы и структуры ВМ
Ну чтож, начнем писать компилятор и код самой виртуальной машины. Для начала нам потребуется один общий модуль, содержащий все типы данных и общие процедуры для ВМ и компилятора. Для этого создадим модуль types.
Код:
import std/algorithm
import std/random
import std/hashes
import std/macros
const ct_time* = CompileDate & CompileTime
const ct_seed* = ct_time.hash().int64
var ct_rand* {. compile_time .} = init_rand(ct_seed)Подключаем необходимые стандартные библиотеки языка Nim и на этапе компиляции генерируем уникальное зерно, для этого получаем хеш-значение текущей даты и времени компиляции. Затем, с помощью зерна инициализируем генератор псевдослучайных чисел. Атрибут compile_time указывает компилятору языка Nim, что этот ГПСЧ может быть использован на этапе компиляции, а не на этапе исполнения.
Код:
macro rand_enum(node: untyped): untyped =
node.last.expect_kind(nnkEnumTy)
var idents = new_seq[NimNode]()
for item in node.last:
if item.kind == nnkIdent:
idents.add(item)
elif item.kind == nnkEnumFieldDef:
item[0].expect_kind(nnkIdent)
idents.add(item[0])
var values = new_seq[uint8]()
for i in 0 ..< idents.len():
var rnd = ct_rand.rand(1..255).uint8
while values.contains(rnd):
rnd = ct_rand.rand(1..255).uint8
values.add(rnd)
values.sort(system.cmp)
ct_rand.shuffle(idents)
var last = nnkEnumTy.new_tree()
last.add(new_empty_node())
let lownode = nnkEnumFieldDef.new_tree()
lownode.add(ident("LowEnumItemFuckYou"))
lownode.add(new_lit(0'u8))
last.add(lownode)
for i in 0 ..< idents.len():
let node = nnkEnumFieldDef.new_tree()
let value = new_lit(values[i])
node.add(idents[i])
node.add(value)
last.add(node)
node[^1] = last
return nodeМакрос rand_enum с помощью генератора псевдослучайных чисел рандомизирует константы элементов перечисления. Для этого он собирает все идентификаторы исходного перечисления, для каждого из них генерирует уникальное псевдослучайное число, а затем создает новое перечисление, где каждому идентификатору соответствует уникальное число. Важно отметить, что компилятору языка Nim по неведомой мне причине необходим нулевой элемент в перечислении (low item). Для удовлетворения этой потребности мы просто закостылим во все рандомизированные перечисления своей нулевой элемент, который у нас будет носить говорящее о многом название «LowEnumItemFuckYou».
Код:
type TypeKind* {. pure, rand_enum .} = enum
Boolean, Integer, String
type Object* = object
case kind: TypeKind
of TypeKind.Boolean:
boolean_key: uint8
boolean_val: uint8
of TypeKind.Integer:
integer_key: uint32
integer_val: uint32
of TypeKind.String:
string_key: uint32
string_val: seq[uint8]
else: discard
const ct_true* = ct_rand.rand(1 .. 255).uint8
const ct_false* = not ct_trueОбъявим перечисление типов данных виртуальной машины (TypeKind), как мы с вами и договаривались ранее (3 типа – були, целые числа, строки). Затем объявим структуру «объекта» виртуальной машины (Object). Под «объектом» мы будем понимать сущность, которая держит внутри себя значение типа данных. Эта сущность будет использоваться при реализации стека и контейнера для всех локальных переменных. Данные в этой сущности будут храниться в памяти в зашифрованном виде и расшифровываться по мере необходимости. Для каждой такой сущности ключ шифрования данных в памяти будет создан псевдослучайно. Ну и в конце представленного кода мы объявим две константы, которые в нашей ВМ будут означать true и false, чтобы не использовать для этого пресловутые единицу и ноль.
Код:
proc rand_uint32*(): uint32 =
let rng = 1'u32 .. 0xFFFFFFFF'u32
return rand(rng).uint32
proc ct_rand_uint32*(): uint32 =
let next = ct_rand.next() and 0xFFFFFFFF'u64
return 1'u32 + (next.uint32 mod 0xFFFFFFFF'u32)
proc rand_uint16*(): uint16 =
let rng = 1'u32 .. 0xFFFF'u32
return rand(rng).uint16
proc ct_rand_uint16*(): uint16 =
let rng = 1'u32 .. 0xFFFF'u32
return ct_rand.rand(rng).uint16
proc rand_uint8*(): uint8 =
return rand(1 .. 255).uint8
proc ct_rand_uint8*(): uint8 =
return ct_rand.rand(1 .. 255).uint8
proc ct_rand_string*(mn: int, mx: int): string =
let length = ct_rand.rand(mn .. mx)
result = new_string_of_cap(length)
for i in 0 ..< length:
let ascii = ct_rand.rand('a' .. 'z')
result &= chr(ascii.int)
proc set_boolean*(obj: var Object, value: bool) =
let rvl =
if value: ct_true
else: ct_false
let key = rand_uint8()
let val = rvl xor key
obj.kind = TypeKind.Boolean
obj.boolean_key = key
obj.boolean_val = val
proc get_boolean*(obj: Object): uint8 =
let key = obj.boolean_key
return obj.boolean_val xor key
proc new_boolean_obj*(value: bool): Object =
result = Object()
result.set_boolean(value)
proc set_integer*(obj: var Object, value: uint32) =
let key = rand_uint32()
let val = value xor key
obj.kind = TypeKind.Integer
obj.integer_key = key
obj.integer_val = val
proc get_integer*(obj: Object): uint32 =
let key = obj.integer_key
return key xor obj.integer_val
proc new_integer_obj*(value: uint32): Object =
result = Object()
result.set_integer(value)
proc xor_string*(key: uint32, value: string): seq[uint8] =
let bkey = [
(key shr 0 and 0xFF'u8).uint8,
(key shr 8 and 0xFF'u8).uint8,
(key shr 16 and 0xFF'u8).uint8,
(key shr 24 and 0xFF'u8).uint8
]
result = new_seq[uint8](value.len)
for i in 0 ..< result.len:
let ikey = bkey[i mod 4] + i.uint8
let ichr = ord(value[i]).uint8
result[i] = ikey xor ichr
proc xor_string*(key: uint32, value: seq[uint8]): string =
let bkey = [
(key shr 0 and 0xFF'u8).uint8,
(key shr 8 and 0xFF'u8).uint8,
(key shr 16 and 0xFF'u8).uint8,
(key shr 24 and 0xFF'u8).uint8
]
result = new_string_of_cap(value.len)
for i in 0 ..< value.len:
let ikey = bkey[i mod 4] + i.uint8
let ichr = ikey xor value[i]
result &= chr(ichr)
proc set_string*(obj: var Object, value: string) =
let key = rand_uint32()
let val = xor_string(key, value)
obj.kind = TypeKind.String
obj.string_key = key
obj.string_val = val
proc get_string*(obj: Object): string =
let key = obj.string_key
let val = obj.string_val
return xor_string(key, val)
proc new_string_obj*(value: string): Object =
result = Object()
result.set_string(value)Нам понадобятся отдельные вспомогательные функции для генерации псевдослучайных чисел, как на этапе компиляции, так и на этапе выполнения, для четкого разделения между ними функции времени компиляции имеют префикс “ct”. Далее мы создаем вспомогательные функции для того, чтобы устанавливать и получать значения «объекта» виртуальной машины, в зависимости от его типа. При этом мы реализуем простое шифрование, таким образом данные в памяти не будут присутствовать в открытом виде до их непосредственного использования. Некоторые вещи здесь выглядят не особо оптимизированными, как, например, перевод 32-битного числа в массив из четырех байт в функциях xor_string, но это не суть важно, понадеемся, что компилятор эти вещи правильно соптимизирует.
Код:
type Opcode* {. pure, rand_enum .} = enum
Nop, # Ничего не делать
PushI, # Положить на стек целое число
PushS, # Положить на стек строку
Pop, # Удалить верхушку стека
Store, # Сохранить верхушку стека в переменную
Load, # Загрузить переменную на стек
Add, # Сложить два числа на верхушке стека
Mul, # Умножить два числа на верхушке стека
And, # Применить побитовое "И" к верхушке стека
Eq, # Сравнить два числа на верхушке стека на равенство
Lt, # Сравнить, что одно число меньше другого
JmpF, # Условный переход, если на верхушке стека false
Jmp, # Безусловный переход
Slen, # Взять строку с верхушки стека, положить ее длину на стек
Ord, # Взять строку и индекс со стека, положить ASCII-код символа
Echo, # Вывести в консоль строку с верхушки стека
Input, # Считать с консоли строку, положить в стек
Halt # Завершить исполнение ВМ
proc ct_rand_choice*(arr: open_array[Opcode]): Opcode =
return ct_rand.sample(arr)
type Fixup* = object
opcode*: int
offset*: intНу и в конце объявляем опкоды нашей виртуальной машины и функцию для выбора псевдослучайного элемента из массива на этапе компиляции. Опкоды по идее должны говорить сами за себя, но если что-то не понятно, то пишите свои вопросы в комментарии к статье. Ну и да, обратите внимание, что опкоды и идентификаторы типов данных ВМ мы полиморфим с помощью реализованного в самом начале макроса. Структура Fixup понадобится нам для реализации условных и безусловных переходов в компиляторе, в ней будет хранится смещение опкода и на что его пофиксить. Чем-то похоже на релок в PE-формате, но смысл этой конструкции аналогичен использованию метки в ассемблерном листинге или в рассово-верных Сишечках и Басиках.
5. Создаем эмиттер
«Эмиттером» в компиляторах часто называют некий интерфейс, который создает байт-код (или нативный код), который ему скажут. В нашем случае мы просто будем иметь структуру с динамическим массивом байт и набор функций для того, чтобы просто и удобно писать туда (в динамический массив) наш байт-код.
Код:
import types
type Emitter* = object
code*: seq[uint8]
proc new_emitter*(): Emitter =
result = Emitter()
result.code = new_seq[uint8]()
proc position*(emi: Emitter): int =
return emi.code.len
proc write(emi: var Emitter, value: uint8) =
emi.code.add(value)
proc write(emi: var Emitter, value: uint32) =
emi.code.add((value shr 0 and 0xFF'u8).uint8)
emi.code.add((value shr 8 and 0xFF'u8).uint8)
emi.code.add((value shr 16 and 0xFF'u8).uint8)
emi.code.add((value shr 24 and 0xFF'u8).uint8)
proc write(emi: var Emitter, position: int, value: uint32) =
emi.code[position + 0] = (value shr 0 and 0xFF'u8).uint8
emi.code[position + 1] = (value shr 8 and 0xFF'u8).uint8
emi.code[position + 2] = (value shr 16 and 0xFF'u8).uint8
emi.code[position + 3] = (value shr 24 and 0xFF'u8).uint8
proc write(emi: var Emitter, value: open_array[uint8]) =
emi.code.add(value)
proc emit_opcode*(emi: var Emitter, opcode: Opcode): int =
result = emi.code.len
var key = ct_rand_uint8()
var val = opcode.uint8
emi.write(key xor val)
emi.write(key)
proc emit_arg_uint8(emi: var Emitter, value: uint8): int =
result = emi.code.len
var key = ct_rand_uint8()
emi.write(key xor value)
emi.write(key)
proc emit_arg_uint32(emi: var Emitter, value: uint32): int =
result = emi.code.len
var key = ct_rand_uint32()
emi.write(value xor key)
emi.write(key)
proc emit_arg_uint32(emi: var Emitter, position: int, value: uint32): int =
result = emi.code.len
var key = ct_rand_uint32()
emi.write(position, value xor key)
emi.write(position + 4, key)
proc emit_arg_string(emi: var Emitter, value: string): int =
result = emi.code.len
var key = ct_rand_uint32()
var ke2 = (key and 0xFF).uint8
var val = xor_string(key, value)
var sln = val.len.uint8 xor ke2
emi.write(sln)
emi.write(key)
emi.write(val)
proc emit_nop*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Nop)
proc emit_pushi*(emi: var Emitter, value: uint32): int =
result = emi.emit_opcode(Opcode.PushI)
discard emi.emit_arg_uint32(value)
proc emit_pushs*(emi: var Emitter, value: string): int =
result = emi.emit_opcode(Opcode.PushS)
discard emi.emit_arg_string(value)
proc emit_pop*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Pop)
proc emit_store*(emi: var Emitter, index: int): int =
result = emi.emit_opcode(Opcode.Store)
discard emi.emit_arg_uint8(index.uint8)
proc emit_load*(emi: var Emitter, index: int): int =
result = emi.emit_opcode(Opcode.Load)
discard emi.emit_arg_uint8(index.uint8)
proc emit_add*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Add)
proc emit_mul*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Mul)
proc emit_and*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.And)
proc emit_eq*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Eq)
proc emit_lt*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Lt)
proc emit_slen*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Slen)
proc emit_ord*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Ord)
proc emit_jmpf*(emi: var Emitter): Fixup =
result = Fixup()
result.opcode = emi.emit_opcode(Opcode.JmpF)
result.offset = emi.emit_arg_uint32(0)
proc emit_jmp*(emi: var Emitter): Fixup =
result = Fixup()
result.opcode = emi.emit_opcode(Opcode.Jmp)
result.offset = emi.emit_arg_uint32(0)
proc emit_echo*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Echo)
proc emit_input*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Input)
proc emit_halt*(emi: var Emitter): int =
result = emi.emit_opcode(Opcode.Halt)
proc bind_fixup*(emi: var Emitter, fix: Fixup, value: uint32): int =
return emi.emit_arg_uint32(fix.offset, value)Для начала мы объявляем структуру объекта эмиттера (Emitter), его конструктор (new_emitter) и функцию для получения текущей позиции эмиттера (смещение от начала байт-кода того места, куда будет записана следующая инструкция). Затем мы создадим несколько приватных методов для записи различных типов данных в эмиттер, а уже после этого все методы для записи всех опкодов нашей ВМ. Каждый опкод и каждая константа записывается вместе с псевдослучайным ключем для ее простого шифрования. Если опкод требует параметра, то значение этого параметра передается в соответствующую функцию записи опкода (сделать такие функции прослойки – это хороший метод не проебаться на ровном месте, ведь компилятор выдаст ошибку, если мы попытаемся записать опкод без аргумента, или же с аргументом неправильного типа). Функция bind_fixup заменяет указанный релок или фиксап, прописывая действительный адрес байт-кода, относительно его начала.
6. Создаем ридер и дизассемблер
«Ридером» у нас будет называться отдельный интерфейс образно обратный эмиттеру, то есть предназначенный для чтения и дешифрования того, что мы записали с помощью эмиттера. Его можно было бы встроить и в саму ВМ, но мы с вами еще и дизассемблер напишем в процессе, так что хорошо бы этот функционал вывести в отдельный модуль, который может быть переиспользован в разных компонентах. Код должен говорить сам за себя, но, если что-то непонятно, не стесняйтесь спрашивать.
Код:
import types
type Reader* = object
code*: seq[uint8]
position*: int
proc new_reader*(code: seq[uint8]): Reader =
result = Reader()
result.code = code
result.position = 0
proc at_end*(rea: Reader): bool =
return rea.position >= rea.code.len
proc set_end*(rea: var Reader) =
rea.position = rea.code.len
proc read_uint8(rea: var Reader): uint8 =
result = rea.code[rea.position]
rea.position = rea.position + 1
proc read_uint32(rea: var Reader): uint32 =
result = rea.code[rea.position].uint32 shl 0
result = result or (rea.code[rea.position + 1].uint32 shl 8)
result = result or (rea.code[rea.position + 2].uint32 shl 16)
result = result or (rea.code[rea.position + 3].uint32 shl 24)
rea.position = rea.position + 4
proc read_bytes(rea: var Reader, length: int): seq[uint8] =
result = rea.code[rea.position ..< rea.position + length]
rea.position = rea.position + length
proc read_opcode*(rea: var Reader): Opcode =
let val = rea.read_uint8()
let key = rea.read_uint8()
return (key xor val).Opcode
proc read_arg_uint8*(rea: var Reader): uint8 =
let val = rea.read_uint8()
let key = rea.read_uint8()
return key xor val
proc read_arg_uint32*(rea: var Reader): uint32 =
var val = rea.read_uint32()
var key = rea.read_uint32()
return key xor val
proc read_arg_string*(rea: var Reader): string =
var sln = rea.read_uint8()
let key = rea.read_uint32()
let ke2 = (key and 0xFF).uint8
sln = sln xor ke2
let val = rea.read_bytes(sln.int)
return xor_string(key, val)Дизассемблер байт-кода может пригодиться нам в том случае, если наш будущий компилятор будет генерировать какой-то ошибочный байт-код. Поэтому на этапе компиляции языка Nim мы будем на всякий случай выбрасывать в консоль то, что накомпилировал уже наш компилятор. Поскольку мы будем использовать дизассемблер только на этапе компиляции в финальный экзешник он не попадет. По функционалу дизассемблер просто считывает байт-код с помощью ридера и выводит каждую инструкцию и ее аргумент (если такой есть) в консоль.
Код:
import std/strformat
import std/strutils
import reader
import types
proc to_string*(opcode: Opcode): string =
return case opcode
of Opcode.Nop: "NOP"
of Opcode.PushI: "PUSHI"
of Opcode.PushS: "PUSHS"
of Opcode.Pop: "POP"
of Opcode.Store: "STORE"
of Opcode.Load: "LOAD"
of Opcode.Add: "ADD"
of Opcode.Mul: "MUL"
of Opcode.And: "AND"
of Opcode.Eq: "EQ"
of Opcode.Lt: "LT"
of Opcode.JmpF: "JMPF"
of Opcode.Jmp: "JMP"
of Opcode.Slen: "SLEN"
of Opcode.Ord: "ORD"
of Opcode.Echo: "ECHO"
of Opcode.Input: "INPUT"
of Opcode.Halt: "HALT"
else: "WTF?!"
proc disassemble_one*(rea: var Reader): string =
let offset = rea.position
let opcode = rea.read_opcode()
let opcstr = opcode.to_string()
var opcarg = ""
case opcode
of Opcode.PushI:
let arg = rea.read_arg_uint32()
opcarg = &"{arg} (0x{arg.to_hex})"
of Opcode.PushS:
let arg = rea.read_arg_string()
opcarg = &"\"{arg}\""
of Opcode.Load:
let arg = rea.read_arg_uint8()
opcarg = &"index:{arg}"
of Opcode.Store:
let arg = rea.read_arg_uint8()
opcarg = &"index:{arg}"
of Opcode.JmpF:
let arg = rea.read_arg_uint32()
opcarg = &"{arg:04}"
of Opcode.Jmp:
let arg = rea.read_arg_uint32()
opcarg = &"{arg:04}"
else: discard
return &"{offset:04} {opcstr: 5} {opcarg}"
proc disassemble_restore*(rea: var Reader): string =
let position = rea.position
result = disassemble_one(rea)
rea.position = position
proc disassemble*(code: seq[uint8]): string =
result = ""
var rea = new_reader(code)
while not rea.at_end():
result &= rea.disassemble_one()
result &= "\n"7. Создаем компилятор
Компилятор будет получать AST-дерево кода, который нужно защитить, обходить все дерево этого кода с помощью паттерна «Посетитель» и генерировать байт-код для нашей ВМ. Это, наверное, самая сложная часть всего проекта, так что пристегните ремни.
Код:
import std/strformat
import std/strutils
import std/tables
import std/macros
import emitter
import disasm
import types
const generate_trash = false
type Fixup = object
target: uint32
fixup: uint32
type Compiler = object
locals: Table[string, int]
fixups: seq[Fixup]
emit: Emitter
root: NimNode
proc to_hex(code: seq[uint8]): string =
result = ""
for byt in code:
result &= byt.to_hex()
proc new_compiler(root: NimNode): Compiler =
root.expect_kind(nnkStmtList)
result = Compiler()
result.locals = init_table[string, int]()
result.fixups = new_seq[Fixup]()
result.emit = new_emitter()
result.root = rootКонстанта generate_trash определяет, нужно ли компилятору генерировать мусорный байт-код и вмешивать его в настоящий байт-код. Опциональная генерация мусорного кода сделана для удобства отладки компилятора, зачем нам копаться в мусорном коде, если нужно отладить компилятор, так ведь? У нашей структуры компилятора будет всего лишь несколько полей. Нам нужно содержать таблицу локальных переменных, где имя локальной переменной будет ассоциировано с ее же порядковым номером внутри виртуальной машины. Массив фиксапов на самом деле оказался не так уж и нужен, но я его добавил на всякий случай, если фиксап нужно будет реализовывать между разными узлами AST в компиляторе. Но вот эмиттер нам понадобится, с его помощью компилятор будет генерировать байт-код. На всякий случай и указатель на корень компилируемого дерева (AST имеется ввиду) сохраним. Еще мы сделаем специальную функцию to_hex, которая просто конвертирует массив байт-кода в длинную хекс строку, ее мы будем выводить в консоль, чтобы убедиться в некоей степени полиморфности байт-кода. В конструкторе компилятора (new_compiler) мы просто проверяем, что нам передали узел StmtList (с помощью функции expect_kind) и инициализируем все поля структуры.
Код:
proc trash_generate_math(compiler: var Compiler) =
let val1 = ct_rand_uint32()
let val2 = ct_rand_uint32()
let oper = ct_rand_choice([
Opcode.Add, Opcode.Mul,
Opcode.And
])
discard compiler.emit.emit_pushi(val1)
discard compiler.emit.emit_pushi(val2)
discard compiler.emit.emit_opcode(oper)
discard compiler.emit.emit_pop()
proc trash_generate_str(compiler: var Compiler) =
let str = ct_rand_string(4, 12)
discard compiler.emit.emit_pushs(str)
if ct_rand_uint8() mod 2 == 1:
discard compiler.emit.emit_slen()
discard compiler.emit.emit_pop()
else: discard compiler.emit.emit_pop()
proc trash_generate(compiler: var Compiler) =
if generate_trash:
case ct_rand_uint8() mod 4
of 0: compiler.trash_generate_math()
of 1: compiler.trash_generate_math()
of 2: compiler.trash_generate_str()
else: discard compiler.emit.emit_nop()Для начала давайте разогреемся написанием небольшого генератора мусорного кода. Наша ВМ стековая, поэтому по большому счету семантика (смысл) двух следующих друг за другом опкодов не поменяется, если между ними вставить любой фрагмент байт-кода, который после своего исполнения оставит стек ровно таким же, как и до своего исполнения. Так, например, функция trash_generate_math сгенерирует код, который как будто бы производит математическую операцию над двумя константами, но на самом деле просто отбрасывает результат математики с помощью опкода POP в конце. Аналогично функция trash_generate_str производит как будто бы манипуляции с длиной строки, но также отбрасывает результат исполнения и оставляет стек в исходном виде. Функция trash_generate псевдослучайно выбирает, какой мусорный код генерировать, в том числе может и просто NOP пихнуть. Понятно, что генератор мусорного кода достаточно примитивен, мне он по большому счету был нужен только для того, чтобы продемонстрировать концепт встраивания мусорного кода в байт-код стековой ВМ. Более интеллектуальные генераторы останутся вам в качестве домашнего задания.
Код:
proc compile_generic(compiler: var Compiler, node: NimNode)
proc compile_children(compiler: var Compiler, node: NimNode, exclude: open_array[int] = []) =
var i = 0
for child in node.children:
if not exclude.contains(i):
compiler.compile_generic(child)
i = i + 1Для реализации паттерна «Посетитель» нам необходимо будет реализовать несколько методов. Самый главный из них - compile_generic пока мы просто объявим, но реализуем его позже. Он будет посещать текущий узел, посещать всех потомков узла, и в зависимости от типа текущего узла вызывать соответствующую функцию для генерации байт-кода. Функция compile_children посещает всех потомков узла кроме тех, номера которых указаны в массиве параметром exclude.
Код:
proc compile_strlit(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkStrLit)
compiler.trash_generate()
discard compiler.emit.emit_pushs(node.str_val)
proc compile_intlit(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkIntLit)
compiler.trash_generate()
discard compiler.emit.emit_pushi(node.int_val.uint32)
proc compile_uintlit(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkUintLit)
compiler.trash_generate()
discard compiler.emit.emit_pushi(node.int_val.uint32)
proc compile_uint32lit(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkUint32Lit)
compiler.trash_generate()
discard compiler.emit.emit_pushi(node.int_val.uint32)В том случае, если компилятор посещает узлы, содержащие константы, такие как строки или целые числа, он должен сгенерировать соответствующие опкоды для того, чтобы положить на стек текущую константу. В каждом из указанных выше методов мы сначала проверяем, что находимся в том узле, в котором ожидаем, затем генерируем мусорный код (если trash_generate выставлена в true), а затем просто генерируем нужный опкод (один из опкодов PUSH). Факт генерации мусорного кода и где он находится в какой функции в дальнейшем я буду опускать, я думаю, что это вещь не нуждается в отдельных пояснениях каждый раз, как и факт проверки валидности узла.
Код:
proc compile_call(compiler: var Compiler, node: NimNode) =
node.expectKind(nnkCall)
node[0].expectKind(nnkSym)
compiler.trash_generate()
case $node[0]
of "readLine":
discard compiler.emit.emit_input()
of "echo":
compiler.compile_children(node, [0])
discard compiler.emit.emit_echo()
of "len":
compiler.compile_children(node, [0])
discard compiler.emit.emit_slen()
of "ord":
compiler.compile_children(node, [0])
discard compiler.emit.emit_ord()
else:
echo(&"Unknown call {$node[0]}")
proc compile_conv(compiler: var Compiler, node: NimNode) =
node.expectKind(nnkConv)
compiler.compile_children(node, [0])Если компилятор посещает узлы nnkCall (вызовы функций), то мы проверяем есть ли у него идентификатор (имя) функции, которую он должен вызвать. В зависимости от идентификатора мы генерируем соответствующий байт-код. Вообще, в этой статье для упрощения всего я опустил описание стек фреймов и вызовов внешних или внутренних функций, поэтому компилятор умеет генерировать только вызовы четырех функций, каждая из которых в рантайме ВМ будет реализована одним опкодом. Да и сама ВМ замкнута внутри одной функции. Вызовы нативных функций из ВМ – сложная тема, которую без ассемблерных вставок скорее всего нормально не решить, а про вызовы функций ВМ функциями ВМ можно дополнительно почитать во многих источниках (могу кинуть ссылку на хорошую книгу, если желаете). Узел nnkConv (конвертация одного типа данных в другой) нам для текущей реализации не нужен, но при его посещении нам нужно исключить первого потомка, поскольку он является типом nnkSym, обрабатывать который нам не нужно в контексте такого родителя, как nnkConv.
Код:
proc compile_asgn(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkAsgn)
node[0].expect_kind(nnkSym)
compiler.compile_children(node, [0])
if compiler.locals.contains($node[0]):
let index = compiler.locals[$node[0]]
discard compiler.emit.emit_store(index)
else: echo(&"Unknown symbol {$node}")
proc compile_sym(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkSym)
if compiler.locals.contains($node):
let index = compiler.locals[$node]
discard compiler.emit.emit_load(index)
else: echo(&"Unknown symbol {$node}")Если компилятор приходит в узел nnkAssn (присваивание значения переменной), то мы находим в таблице локальных переменных ту, что имеет имя, указанное в узле идентификатором, и генерируем опкод STORE, который возьмет значение с верхушки стека и положит его в таблицу переменных. Наступая на узел nnkSym мы предполагаем, что это получение значение переменной (поэтому мы ранее забанили в этом плане первого потомка nnkConv) и генерируем опкод LOAD, который положит значение переменной на стек ВМ.
Код:
proc compile_infix(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkInfix)
node[0].expect_kind(nnkSym)
compiler.compile_children(node, [0])
compiler.trash_generate()
case $node[0]
of "and": discard compiler.emit.emit_and()
of "==": discard compiler.emit.emit_eq()
of "<": discard compiler.emit.emit_lt()
of "+": discard compiler.emit.emit_add()
of "*": discard compiler.emit.emit_mul()
else: echo(&"Unknown infix {$node[0]}")
proc compile_identdefs(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkIdentDefs)
node[0].expect_kind(nnkSym)
let name = $node[0]
let count = compiler.locals.len
compiler.locals[name] = count
compiler.compile_children(node, [0])
compiler.trash_generate()
discard compiler.emit.emit_store(count)Узел nnkInfix – бинарное выражение с оператором, генерируется аналогичным с nnkCall образом, то есть все операторы, которые нам нужны для данной крекмиши реализуются отдельными опкодами. Узел nnkIdentDefs отвечает за объявление новых переменных, мы предполагаем, что у каждой из переменных будет указано начальное значение, поэтому генерируем байт-код для потомков, регистрируем переменную в таблице и генерируем опкод STORE, который положит значение в переменную.
Код:
proc compile_whilestmt(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkWhileStmt)
let loop_start = compiler.emit.position.uint32
compiler.compile_generic(node[0])
let jmp_out = compiler.emit.emit_jmpf()
compiler.compile_generic(node[1])
let jmp_loop = compiler.emit.emit_jmp()
let loop_end = compiler.emit.position.uint32
discard compiler.emit.bind_fixup(jmp_out, loop_end)
discard compiler.emit.bind_fixup(jmp_loop, loop_start)Мы подошли к более сложным в плане генерации узлам. nnkWhile – это цикл while в исходном коде. Для начала нам нужно сохранить метку старта цикла. Затем скомпилировать байт-код для сравнения в условии цикла (первого потомка). После байт-кода сравнения нам нужно вставить байт-код JMPF (сделать условный переход, если на вершине стека лежит false). Дальше мы генерируем байт-код тела цикла и за ним добавляем опкод JMP (безусловный переход в начало цикла), при этом сохраняя метку конца цикла. После того, как мы сгенерировали код мы можем поправить адреса (на самом деле смещения от начала байт-кода) в опкодах JMP и JMPF с помощью функции bind_fixup.
Код:
proc compile_ifstmt(compiler: var Compiler, node: NimNode) =
node.expect_kind(nnkIfStmt)
node[0].expect_kind(nnkElifBranch)
node[1].expect_kind(nnkElse)
node[0][1].expectKind(nnkStmtList)
node[1][0].expectKind(nnkStmtList)
compiler.compile_generic(node[0][0])
let jmp1 = compiler.emit.emit_jmpf()
compiler.compile_generic(node[0][1])
let jmp2 = compiler.emit.emit_jmp()
let ofs1 = compiler.emit.position.uint32
discard compiler.emit.bind_fixup(jmp1, ofs1)
compiler.compile_generic(node[1][0])
let ofs2 = compiler.emit.position.uint32
discard compiler.emit.bind_fixup(jmp2, ofs2)Узел nnkIfStmt генерируется аналогично. Мы генерируем код для потомков, вставляя в него JMP и JMPF опкоды для условных переходов. В тот момент, когда нам становятся известны адреса (смещения блет) для всех JMP и JMPF, мы просто исправляем их в уже сгенерированном байт-коде, используя все ту же функцию bind_fixup.
Код:
proc compile_generic(compiler: var Compiler, node: NimNode) =
case node.kind
of nnkIdentDefs: compiler.compile_identdefs(node)
of nnkWhileStmt: compiler.compile_whilestmt(node)
of nnkUint32Lit: compiler.compile_uint32lit(node)
of nnkUintLit: compiler.compile_uintlit(node)
of nnkIfStmt: compiler.compile_ifstmt(node)
of nnkStrLit: compiler.compile_strlit(node)
of nnkIntLit: compiler.compile_intlit(node)
of nnkInfix: compiler.compile_infix(node)
of nnkCall: compiler.compile_call(node)
of nnkConv: compiler.compile_conv(node)
of nnkAsgn: compiler.compile_asgn(node)
of nnkSym: compiler.compile_sym(node)
else: compiler.compile_children(node)
proc get_bytecode(compiler: var Compiler): seq[uint8] =
compiler.compile_validate_jmpf()
compiler.compile_generic(compiler.root)
compiler.trash_generate()
compiler.trash_generate()
compiler.trash_generate()
discard compiler.emit.emit_halt()
compiler.trash_generate()
compiler.trash_generate()
compiler.trash_generate()
return compiler.emit.codeТеперь, когда у нас есть все функции для генерации всех важных узлов дерева, которые есть в нашей крекмише, мы можем написать функцию compile_generic. Она представляет собой просто один большой свитч, который вызывает методы в зависимости от типа текущего узла. Если тип текущего узла нам не важен, то функция просто рекурсивно посетит всех его потомков. Метод get_bytecode компилирует все узлы, начиная с корня дерева и возвращает байт-код в виде массива байт. Пока не обращайте внимание на метод compile_validate_jmpf, что это такое я расскажу в заключении.
Код:
macro virtualize*(node: typed): untyped =
echo("\n*** *** ***")
echo(tree_repr(node))
var cmp = new_compiler(node.last)
let cod = cmp.get_bytecode()
echo("\n*** *** ***")
echo(cmp.locals)
echo("\n*** *** ***")
echo(disassemble(cod))
echo("\n*** *** ***")
echo(cod.to_hex())
var bytes = new_seq[string](cod.len)
for i in 0 ..< bytes.len:
bytes[i] = &"{cod[i]}'u8"
let name = $node[0]
let joined = bytes.join(", ")
let sources = &"""
proc {name}() =
let opcodes = @[{joined}]
var frame = new_frame(opcodes)
frame.execute()
"""
let newnode = parse_stmt(sources)
return newnode[0]А вот и тот самый макрос virtualize, про который мы говорили в самом начале. Важно заметить, что он должен принимать типизированное AST-дерево (typed) и возвращает нетипизированное. Дело в том, что все макросы и функции времени компиляции языка Nim исполняются и раскрываются на так называемом semPass этапе, на котором в том числе и происходит типизация и семантическая проверка кода. Для нашей крекмиши необходимо, чтобы cp_hash_string был раскрыт до того, как он попадет компилятору, поэтому в макрос нам нужно получать именно типизированное дерево. Макрос создает новый компилятор байт-кода, передает ему корень AST-дерева и получает от компилятора байт-код в виде массива байт. Затем для отладки он выводит список локальных переменных, дизасм байт-кода и хекс строку с байт-кодом. После чего он генерирует исходники для функции, которая создаст и запустит нашу ВМ, передав туда массив байт-кода. Саму виртуальную машину (и функцию execute) мы напишем чуть позже, а пока давайте посмотрим, как это все работает на практике.
Код:
0345 LOAD index:1
0349 PUSHI 1881464870 (0x7024E026)
0359 EQ
0361 JMPF 0448
0371 PUSHS "Password is valid, bro!"
0401 ECHO
0403 PUSHS "You are real cracker, bro!"
0436 ECHO
0438 JMP 0518
0448 PUSHS "Password is invalid, bro!"
0480 ECHO
0482 PUSHS "Better luck next time, bro!"
0516 ECHO
0518 HALTТак, например, будет выглядеть наша конструкция if-else из крекмиши без мусорного кода. Инструкция LOAD загружает переменную xhash на стек (переменную с индексом 1). Инструкция PUSHI загружает на стек эталонное значение хеша, с которым нам нужно произвести сравнение. Инструкция EQ забирает со стека два значения, сравнивает их и кладет на стек true, если значения совпали, ну и false в противном случае. Инструкция JMPF переходит по адресу 0448, если на стеке лежит false. Инструкции PUSHS и ECHO просто выводят строку на экран. Ну а инструкция JMP перепрыгивает ветку else при исполнении ветки if. Для тех, кто впервые видит такой своего рода низкоуровневый код, может быть непонятно, так что не стесняйтесь задавать вопросы в комментариях. Завсегдатаям же всяких ассемблеров, тут и объяснять особо нечего.
8. Создаем виртуальную машину
Единственной задачей виртуальной машины является корректно исполнить байт-код и не накосячить при этом. Единицу исполнения ВМ, инкапсулирующую стек, локальные переменные и байт-код внутри себя, обычно называют фрейм. Наш фрейм будет единственным и предельно простым, в реальных ВМ существуют целые стеки или же цепочки фреймов, где каждый новый фрейм добавляется в цепочку, когда ВМ вызывает одну функцию с байт-кодом из другой. Но не будем усложнять, и так много иногда сложной для понимания информации в статье.
Код:
mport std/macros
import std/random
import reader
import types
const debug_runtime = false
when debug_runtime:
import disasm
type Frame = object
reader: Reader
locals: seq[Object]
stack: seq[Object]
proc new_frame*(code: seq[uint8]): Frame =
result = Frame()
result.reader = new_reader(code)
result.locals = new_seq[Object]()
result.stack = new_seq[Object]()Константа debug_runtime определяет нужно ли нам отлаживать то, как ВМ исполняет байт-код или нет. В случае отладки нам понадобится импортировать и использовать дизассемблер, который мы написали ранее. Наш фрейм – это структура с ридером (что почти одно и тоже, что и «с байт-кодом»), массивом значений локальных переменных и стеком. Конструктор фрейма просто создает вложенные структуры.
Код:
proc push(stack: var seq[Object], value: Object) =
stack.add(value)
proc pop(stack: var seq[Object]): Object =
result = stack[stack.len - 1]
stack.del(stack.len - 1)
proc store(locals: var seq[Object], index: uint8, value: Object) =
let idx = index.int
if idx >= locals.len:
locals.set_len(idx + 1)
locals[idx] = value
proc load(locals: var seq[Object], index: uint8): Object =
return locals[index.int]Названия функций push/pop и store/load говорят сами за себя. Функция push кладет значение на стек, pop – получает значение с верхушки стека, store – сохраняет значение локальной переменной, load – получает значение переменной. Давайте теперь рассмотрим функции для исполнения каждого опкода нашей виртуальной машины.
Код:
proc execute_nop(frame: var Frame) =
discard
proc execute_pushi(frame: var Frame) =
let arg = frame.reader.read_arg_uint32()
frame.stack.push(new_integer_obj(arg))
proc execute_pushs(frame: var Frame) =
let arg = frame.reader.read_arg_string()
frame.stack.push(new_string_obj(arg))
proc execute_pop(frame: var Frame) =
discard frame.stack.pop()
proc execute_store(frame: var Frame) =
let val = frame.stack.pop()
let idx = frame.reader.read_arg_uint8()
frame.locals.store(idx, val)
proc execute_load(frame: var Frame) =
let idx = frame.reader.read_arg_uint8()
let val = frame.locals.load(idx)
frame.stack.push(val)
proc execute_add(frame: var Frame) =
let o2 = frame.stack.pop()
let o1 = frame.stack.pop()
let vl = o1.get_integer() + o2.get_integer()
frame.stack.push(new_integer_obj(vl))
proc execute_mul(frame: var Frame) =
let o2 = frame.stack.pop()
let o1 = frame.stack.pop()
let vl = o1.get_integer() * o2.get_integer()
frame.stack.push(new_integer_obj(vl))
proc execute_and(frame: var Frame) =
let o2 = frame.stack.pop()
let o1 = frame.stack.pop()
let vl = o1.get_integer() and o2.get_integer()
frame.stack.push(new_integer_obj(vl))
proc execute_eq(frame: var Frame) =
let o2 = frame.stack.pop()
let o1 = frame.stack.pop()
let vl = o1.get_integer() == o2.get_integer()
frame.stack.push(new_boolean_obj(vl))
proc execute_lt(frame: var Frame) =
let o2 = frame.stack.pop()
let o1 = frame.stack.pop()
let vl = o1.get_integer() < o2.get_integer()
frame.stack.push(new_boolean_obj(vl))
proc execute_slen(frame: var Frame) =
let str = frame.stack.pop()
let val = str.get_string().len.uint32
frame.stack.push(new_integer_obj(val))
proc execute_ord(frame: var Frame) =
let idx = frame.stack.pop().get_integer()
let str = frame.stack.pop().get_string()
let res = new_integer_obj(str[idx].uint32)
frame.stack.push(res)
proc execute_jmpf(frame: var Frame) =
let arg = frame.reader.read_arg_uint32()
let val = frame.stack.pop().get_boolean()
if val == ct_false:
frame.reader.position = arg.int
proc execute_jmp(frame: var Frame) =
let arg = frame.reader.read_arg_uint32()
frame.reader.position = arg.int
proc execute_echo(frame: var Frame) =
let msg = frame.stack.pop()
echo(msg.get_string())
proc execute_input(frame: var Frame) =
let msg = read_line(stdin)
let obj = new_string_obj(msg)
frame.stack.push(obj)
proc execute_halt(frame: var Frame) =
frame.reader.set_end()Опкод NOP не делает ничего, этим он немного похож на всех тех критиков, которые любят устраивать срачи в комментах статей, но сами статьи не пишут. Но мы его (опкод) любим таким, какой он есть. Опкод PUSHI кладет на стек константу целочисленного типа. Опкод PUSHS кладет на стек строковую константу. Опкод POP удаляет значение с вершины стека, покойся с миром, значение. Опкод STORE берет с вершины стека одно значение и присваивает его указанной в аргументах опкода переменной. Опкод LOAD делает обратную операцию, кладет на стек значение переменной. Опкод ADD берет со стека два значения, складывает их и результат сложения кладет обратно на стек. Тоже самое делают опкоды MUL и AND, но для умножения и побитового «И» соответственно. Опкод EQ берет два значения с вершины стека, сравнивает их и кладет на стек либо true, либо false в зависимости от результатов сравнения. Опкод LT делает тоже самое, но для сравнения «less than» (меньше чем). Опкод SLEN забирает с вершины стека строку и кладет на стек ее длину. Опкод ORD забирает с вершины стека индекс и строку и кладет на стек целочисленное значение символа из строки по указанному индексу. Опкоды JMP и JMPF производят безусловные и условные переходы соответственно. Опкод ECHO берет с вершины стека строку и выводит ее в консоль. Опкод INPUT считывает пользовательский ввод в консоль в виде строки и кладет ее на вершину стека. Опкод HALT завершает работу ВМ.
Код:
macro generate_execute_table(): untyped =
let handlers = [
"execute_nop",
"execute_pushi",
"execute_pushs",
"execute_pop",
"execute_store",
"execute_load",
"execute_add",
"execute_mul",
"execute_and",
"execute_eq",
"execute_lt",
"execute_slen",
"execute_ord",
"execute_jmpf",
"execute_jmp",
"execute_echo",
"execute_input"
]
result = nnkStmtList.new_tree()
for i in 0 ..< 255:
let handler = case i
of Opcode.Nop.int: "execute_nop"
of Opcode.PushI.int: "execute_pushi"
of Opcode.PushS.int: "execute_pushs"
of Opcode.Pop.int: "execute_pop"
of Opcode.Store.int: "execute_store"
of Opcode.Load.int: "execute_load"
of Opcode.Add.int: "execute_add"
of Opcode.Mul.int: "execute_mul"
of Opcode.And.int: "execute_and"
of Opcode.Eq.int: "execute_eq"
of Opcode.Lt.int: "execute_lt"
of Opcode.Slen.int: "execute_slen"
of Opcode.Ord.int: "execute_ord"
of Opcode.JmpF.int: "execute_jmpf"
of Opcode.Jmp.int: "execute_jmp"
of Opcode.Echo.int: "execute_echo"
of Opcode.Input.int: "execute_input"
of Opcode.Halt.int: "execute_halt"
else: ct_rand.sample(handlers)
result.add(nnkAsgn.new_tree(
nnkBracketExpr.new_tree(
ident("execute_table"),
new_lit(i)
),
ident(handler)
))
type Handler = proc (frame: var Frame)
var execute_table = new_seq[Handler](256)
generate_execute_table()
proc execute*(frame: var Frame) =
while not frame.reader.at_end():
when debug_runtime:
echo(disassemble_restore(frame.reader))
let opc = frame.reader.read_opcode()
execute_table[opc.int](frame)Бывают разные реализации ВМ, классической реализацией можно считать функцию с огромным свитчом, которая в зависимости от опкода вызывает соответствующую функцию обработчик (одну из тех, что были описаны выше). Мы же с вами сделаем jump table с функциями обработчиками. Один опкод нашей ВМ (хоть и имеет псевдослучаное значение) умещается в один байт, то есть от 0 до 255 включительно. Поэтому мы можем создать массив указателей на функции обработчики, а опкод будет индексом в этом массиве. Конечно, нам же хочется полиморфную ВМ, поэтому массив этих обработчиков мы будем формировать псевдослучайно с помощью макроса generate_execute_table. Макрос проходит все индексы от 0 до 255 включительно, если индекс соответствует действующему опкоду (вы же помните, что значения опкодов у нас тоже псевдослучайные), он пихает туда указатель на соответствующий опкоду обработчик, если же индекс не соответствует опкоду (опкодов у нас явно меньше, чем 256), то он пихает туда указатель на псевдослучайный обработчик. Таблица обработчиков формируется в таблицу execute_table в рантайме. Метод execute в цикле считывает опкоды до конца байт-кода, для каждого из них вызывая соответствующий обработчик из таблицы. В режиме отладки мы также выводим, какая инструкция исполнялась в след за какой с помощью дизассемблера.
9. Заключение
В заключении хочу вам немного рассказать о судьбе этой крекмиши. Изначально я предполагал, что господам реверсерам придется разбираться в байт-коде и патчить опкод JMPF в проверке валидности пароля на NOP. Я даже построил компилятор таким образом, чтобы это было удобно сделать, и добавил опкод NOP, без которого ВМ вполне могла бы обойтись. Однако выяснилось, что жуликоватые реверсеры могут просто пропатчить обработчик опкода JMPF таким образом, чтобы он не делал условный переход. Из-за структуры самой машины и крекмиши это вполне себе работало и даже не рушило стек. Во второй версии я добавил такую приколюху, о которой обещал вам рассказать:
Код:
proc compile_validate_jmpf(compiler: var Compiler) =
let val1 = ct_rand_uint32()
var val2 = ct_rand_uint32()
while val2 == val1:
val2 = ct_rand_uint32()
compiler.trash_generate()
discard compiler.emit.emit_pushi(val1)
compiler.trash_generate()
discard compiler.emit.emit_pushi(val2)
compiler.trash_generate()
discard compiler.emit.emit_eq()
compiler.trash_generate()
let jmp = compiler.emit.emit_jmpf()
let msg1 = "Please don't patch my opcode handlers, bro!"
let msg2 = "This is so rude of you, please don't, bro!"
compiler.trash_generate()
discard compiler.emit.emit_pushs(msg1)
compiler.trash_generate()
discard compiler.emit.emit_echo()
compiler.trash_generate()
discard compiler.emit.emit_pushs(msg2)
compiler.trash_generate()
discard compiler.emit.emit_echo()
compiler.trash_generate()
discard compiler.emit.emit_halt()
compiler.trash_generate()
let jump_out = compiler.emit.emit_jmp()
discard compiler.emit.bind_fixup(jump_out, 9999)
let ofs = compiler.emit.position.uint32
discard compiler.emit.bind_fixup(jmp, ofs)Этот метод генерирует байт-код проверяющий семантику (смысл, поведение) опкода JMPF. Если обработчик этого опкода был пропатчен, то байт-код выводит сообщение реверсеру о том, чтобы тот не патчил обработчики, и останавливает ВМ. Конечно, это можно было бы решить, запатчив обработчик с использованием счетчика (типа первый раз он корректный, последующие разы он пропатченный), но в итоге господа реверсеры решали крекмишу так, как я изначально задумал, а именно патчами байт-кода.
Друзья, спасибо, что дочитали эту мою статью до конца. Она получилось довольно сложная и большая, как минимум я писал ее сложно и долго, но надеюсь, что вам было интересно и нескучно ее читать. Очень давно хотел донести до вас эту интересную тему и очень хотел вас заинтересовать ей. Мы с вами сделали небольшую и достаточно высокоуровневую ВМ, которая больше напоминает всякие Петоны и Луа, чем на ВМПротекты и Темиды, но концептуально эти вещи похожи. Простите, если для вас таких низкоуровневых эстетов, данная тема кажется слишком высокоуровневой. Сама тема очень обширная и мне пришлось многие моменты функционирования реальных ВМ опустить или сильно упростить. Созданная ВМ, по сути, может нормально исполнять только одну захардкоженную крекмишу, отсутствует хоть какая-нибудь оптимизация байт-кода, многие вещи мы переиспользовали, а не писали с нуля (лексер и парсер, сборщик мусора из языка Nim, например), но статья уже получилась на 30к символов. Остальные аспекты, которых я не коснулся мы можем пообсуждать в комментариях к статье, и надеюсь, что даже новичкам теперь эта тема не кажется такой уж сложной. Статья написана специальной для вас - моего любимого уютненького комьюнити xss.pro.
Последнее редактирование:
