Статья Декомпилируем проприетарный ассемблер в си-код

[stihl]

Это рассказ о том, как я сделал декомпилятор вроде Hex-Rays для экзотического языка программирования, используемого для скриптов игры «Мор (Утопия)». Ты узнаешь, как работает кросс‑компиляция, и получишь необходимый теоретический минимум из теории компиляции, который поможет тебе сделать так же.

info​

Полный код моих скриптов и результат работы декомпилятора ищи на Для просмотра ссылки Войди или Зарегистрируйся.

Пара слов о декомпиляции​

Мы будем работать с ассемблерным кодом, полученным в статье «Для просмотра ссылки Войди или Зарегистрируйся». Он представляет собой набор из 89 опкодов. Фактически у нас есть только набор команд и заголовки файла.


Декомпиляция на язык более высокого уровня на самом деле является кросс‑компиляцией. То есть мы пишем компилятор, который принимает на вход исходный код на одном языке и превращает его в код на другом. Для этого мы создадим граф исполнения оригинального кода и напишем простенький эмулятор для стековой машины. Но обо всем по порядку. В написании декомпилятора мне сильно помог опыт работы с Angr, о котором я тоже Для просмотра ссылки Войди или Зарегистрируйся. Фактически я повторил типовые решения, используемые в компиляторах и анализаторах кода, и это сработало! Спасибо теории компиляции.

Граф потока управления​

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

Для просмотра ссылки Войди или Зарегистрируйся
Из картинки видно, что есть блоки, которые кончаются командами, не передающими управление. Это связано с тем, что следующий за ними участок кода используется как адреса перехода. То есть другой код (обычно цикл) передает управление в середину базового блока. В таком случае блок делится на два так, чтобы второй начинался с адреса, на который могут передать управление.

Поэтому первым делом я прохожу по всему коду и запоминаю адреса переходов. Будь это команда CALL или JMP — записываем, куда они передают управление. После этого можно делить код на базовые блоки. Проходим от первой инструкции до последней, разделяя их по известным адресам перехода. Для этого я ввел специальные поля в классе самой инструкции: метаданные, хранящие адреса и тип перехода — условный или безусловный.

Разделив код на базовые блоки (создав массив объектов BasicNode), можно приступать к их связыванию, то есть установке ссылок — на какой блок передает управление исследуемый. Каждый базовый блок содержит информацию о своем адресе (адресе первой входящей в него инструкции) и об адресах перехода, которые известны последней инструкции.

Граф должен иметь вершину — первую инструкцию, с которой начинается поток управления. Заголовки из ассемблерного файла дают список возможных точек входа. Я запускаю рекурсивный анализ от первого базового блока, после чего алгоритм проходит по всем адресам перехода и добавляет к блоку ссылки на «дочерние».

При этом каждый блок я прохожу лишь единожды. Существует глобальный список seen — адреса блоков, которые алгоритм уже видел. При повторном анализе они будут проигнорированы. Это позволяет быстро анализировать рекурсивный граф, в котором могут быть вложенные циклы.

Когда все ссылки на «дочерние» блоки расставлены, граф готов. Это аналог абстрактного синтаксического древа (AST). Дальше мы будем работать только с ним.

Обработка функций​

Проприетарный язык игры поддерживает аналог команд CALL и RET из обычного ассемблера x86. Однако тут нет никаких соглашений о вызовах вроде stdcall. Установить число переменных, передаваемых как аргументы функции, невозможно без полноценной эмуляции местного стека.

Поэтому я не стал выделять начала функций как отдельные вершины графа. Каждый вызов значится как обычная передача управления, а тело вызываемой функции — часть тела вызывающей. Этот трюк позволяет анализировать функцию в контексте вызывающего ее кода. После первичного анализа функцию можно выделить в отдельный граф.

Пример построения графа​

Я решил показать все этапы анализа на примере небольшого файла fire.bin. Вот как выглядит его ассемблерный код:

RunOp = 0x6
RunTask = 1

GlobalTasks:
    GTASK_0  Params = 0
        EVENT_5 Op = 0x3 Vars = ()
    GTASK_1  Params = 0
        EVENT_6 Op = 0x26 Vars = ()

0x0: @ Hold()
0x1: Pop(0)
0x2: Return(); Pop(0)

0x3: @ StopGroup0()
0x4: Pop(0)
0x5: Return(); Pop(0)

0x6: PushEmpty(object, object)
0x7: PushEmpty(bool)
0x8: Call 0x2c

0x9: Pop(0)
0xa: Pop(1); Push((bool) Stack[-1] == 0)
0xb: IF (Stack[-1] == 0) GOTO 0x11; Pop(1)

0xc: PushEmpty()
0xd: Push(-0, 0); TaskCall(0)
0xe: Call 0x0

0xf: Pop(-0, 0); TaskReturn
0x10: Pop(0)
0x11: Push("fire")
0x12: @ FindParticleSystem(Stack[-1], Stack[-2])
0x13: Pop(1)
0x14: Pop(0); Push((bool) Stack[-1] == 0)
0x15: IF (Stack[-1] == 0) GOTO 0x1a; Pop(1)

0x16: Push("Can't find fire particle system")
0x17: @ Trace(Stack[-1])
0x18: Pop(1)
0x19: Return(); Pop(2)

0x1a: Push(CVector(0.0, 0.0, 0.0))
0x1b: Push(CVector(0.0, 1.0, 0.0))
0x1c: Push((float)0.0)
0x1d: @@ AddSource(Stack[-3], Stack[-2], Stack[-1])
0x1e: Pop(3)
0x1f: @@ Enable()
0x20: Pop(0)
0x21: @ Hold()
0x22: Pop(0)
0x23: GOTO 0x21

0x24: Return(); Pop(2)

0x25: Stack[-1] = 0
0x26: PushEmpty()
0x27: Push(-0, 0); TaskCall(0)
0x28: Call 0x0

0x29: Pop(-0, 0); TaskReturn
0x2a: Pop(0)
0x2b: Return(); Pop(0)

0x2c: PushEmpty(bool, bool)
0x2d: @ IsLoaded(Stack[-1])
0x2e: Pop(0)
0x2f: Stack[-3] = Stack[-1]
0x30: Return(); Pop(2)

Из заголовков видно, что тут есть три точки входа: 0x3, 0x6 и 0x26. Пройдя по коду, замечаем два адреса, на которые передается управление через Call, — 0x0 и 0x2C. Это вершины функций. Так выглядит первичный граф:

0x3: @ StopGroup0()
0x4: Pop(0)
0x5: Return(); Pop(0)


0x26: PushEmpty()
0x27: Push(-0, 0); TaskCall(0)
0x28: Call 0x0

    0x0: @ Hold()
    0x1: Pop(0)
    0x2: Return(); Pop(0)

    0x29: Pop(-0, 0); TaskReturn
    0x2a: Pop(0)
    0x2b: Return(); Pop(0)

0x6: PushEmpty(object, object)
0x7: PushEmpty(bool)
0x8: Call 0x2c

    0x2c: PushEmpty(bool, bool)
    0x2d: @ IsLoaded(Stack[-1])
    0x2e: Pop(0)
    0x2f: Stack[-3] = Stack[-1]
    0x30: Return(); Pop(2)

    0x9: Pop(0)
    0xa: Pop(1); Push((bool) Stack[-1] == 0)
    0xb: IF (Stack[-1] == 0) GOTO 0x11; Pop(1)

        0xc: PushEmpty()
        0xd: Push(-0, 0); TaskCall(0)
        0xe: Call 0x0

            0x0: @ Hold()
            0x1: Pop(0)
            0x2: Return(); Pop(0)

            0xf: Pop(-0, 0); TaskReturn
            0x10: Pop(0)

                0x11: Push("fire")
                0x12: @ FindParticleSystem(Stack[-1], Stack[-2])
                0x13: Pop(1)
                0x14: Pop(0); Push((bool) Stack[-1] == 0)
                0x15: IF (Stack[-1] == 0) GOTO 0x1a; Pop(1)

                    0x16: Push("Can't find fire particle system")
                    0x17: @ Trace(Stack[-1])
                    0x18: Pop(1)
                    0x19: Return(); Pop(2)
                    0x1a: Push(CVector(0.0, 0.0, 0.0))
                    0x1b: Push(CVector(0.0, 1.0, 0.0))
                    0x1c: Push((float)0.0)
                    0x1d: @@ AddSource(Stack[-3], Stack[-2], Stack[-1])
                    0x1e: Pop(3)
                    0x1f: @@ Enable()
                    0x20: Pop(0)

                        0x21: @ Hold()
                        0x22: Pop(0)
                        0x23: GOTO 0x21

Для каждой точки входа граф строится отдельно, то есть их тут три штуки. Отступ слева обозначает начало дочернего блока.

У блока по адресу 0x26 есть два «ребенка»: вызов функции по адресу 0x0 и следующая по номеру инструкция 0x29. В первоначальном графе тело вызываемой функции прикреплено к «родительскому» блоку, но только один раз на граф.

Блок по адресу 0x9 содержит два дочерних блока: следующий по номеру 0xc и переход на 0x11. Из‑за этого перехода блок (внутри которого нет команд передачи управления) по адресу 0xf делится на два. При этом блок по адресу 0x11 одновременно является «ребенком» для блока 0xf, как следующий за ним по номеру. Но так как мы придерживаемся правила «не заходить в один блок дважды», граф будет отображаться с таким причудливым порядком вложенности.

Симулятор стека​

Основная проблема декомпилированного кода — относительные адреса в стеке. К переменной обращаются через индекс от конца стека, и добавление новой переменной в конец стека ломает старые ссылки. Единственный способ понять, какая переменная где используется, — пройти по графу исполнения, симулируя все операции над стеком.

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

class CInstructionPop:
    def init(self, r):
        self.OpCode = 'Pop'
        self.VarIn = r.uint32()
        self.PopCount = self.VarIn

    def repr(self):
        return f'Pop({self.VarIn})'

class CInstructionAdd:
    def init(self, r):
        self.OpCode = 'Add'
        self.Var1 = r.uint32()
        self.Var2 = r.uint32()
        self.TaskVar = r.int8() # signed
        self.PopCount = self.TaskVar & 0x3F
        self.PushType = [VAR_TYPE.INT]

    def repr(self):
        if self.TaskVar >= 0:
            var_1 = f'Stack[-{self.Var1}]'
        else:
            var_1 = f'Stack[{self.Var1} + StackPtr]'

        if self.TaskVar & 0x40:
            var_2 = f'Stack[{self.Var2} + StackPtr]'
        else:
            var_2 = f'Stack[-{self.Var2}]'

        return f'Pop({self.PopCount}); Push({var_1} + {var_2});'

Симулятор стека идет от вершины графа. Каждая инструкция добавляет или убирает из стека значения. Хитрость в том, что мы делаем два снимка стека для каждой инструкции — до выполнения опкода и после. И добавляем их как метаданные в тело инструкции. На следующем этапе анализа снимки стека помогут определить, какая переменная используется в инструкции.

0x6: PushEmpty(object, object)

before: []
after: [var_0_object, var_1_object]

0x7: PushEmpty(bool)

before: [var_0_object, var_1_object]
after: [var_0_object, var_1_object, var_2_bool]

Например, в самом начале функции 0x6 стек пустой, но первая команда помещает в него две переменные типа object. Следующая инструкция добавляет переменную типа bool.

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

Перед входом в дочерний блок создается временная копия стека. Она передается ему как актуальное состояние. Это нужно для того, чтобы первый дочерний блок не смог повлиять на состояние стека во втором. Мы пользуемся трюком из Angr: при наличии условного перехода по очереди заходим в каждую ветку. Таким образом мы посетим каждый блок ровно один раз, подсчитав для каждого актуальное состояние стека.

0x8: Call 0x2c

before: [var_0_object, var_1_object, var_2_bool]
after: [var_0_object, var_1_object, var_2_bool]

0x2c: PushEmpty(bool, bool)

before: [var_0_object, var_1_object, var_2_bool]
after: [var_0_object, var_1_object, var_2_bool, var_3_bool, var_4_bool]

Вызов функции получает копию стека от вызывающего кода. Эта информация пригодится, когда мы будем определять количество аргументов, передаваемых функции. Мы делаем предположение, что вызов функции не меняет состояния стека. К счастью, язык спроектирован так, что аргументы вызываемой функции подчищает вызывающий ее код, поэтому предположение оказалось верным. Иначе пришлось бы писать полноценный эмулятор для вызываемого кода.

Проходы​

Граф состоит из блоков, каждый блок содержит в себе ссылку на «дочерние» блоки и список ассемблерных инструкций. Идея в том, что мы можем дополнять инструкции информацией о коде на языке более высокого уровня. Другими словами, для каждой инструкции низкого уровня должен быть свой обработчик, который заменяет ее инструкцией более высокого уровня.

if isinstance(instr.opcode, CInstructionMovB):
    node.instructions.hl = HLInstructionMovB(instr)

if isinstance(instr.opcode, CInstructionPow):
    node.instructions.hl = HLInstructionPow(instr)

if isinstance(instr.opcode, CInstructionPop):
    node.instructions.hl = HLInstructionNop()

Например, работа со стеком влияет на симулятор стека, но никак не должна отображаться в си‑коде. Поэтому CInstructionPop заменяется HLInstructionNop — объект класса инструкции NOP (No OPeration) высокого уровня, которая не будет учитываться при сборке текста си‑кода.

Работа с графом реализована через набор «проходов», я позаимствовал идею из архитектуры LLVM. Проход — это функция, которая итеративно применяется к каждому блоку в графе, меняет его на ходу или собирает информацию о коде. Также не забываем «отсоединить» вызываемые функции в отдельные графы.

Первый проход заменяет инструкции их аналогами на языке высокого уровня. Но в нем есть несколько особых случаев.

if isinstance(instr.opcode, CInstructionJump):

node.instructions.hl = HLInstructionJump(instr)
    self.insert_label_list.append(instr.opcode.VarIn)

if isinstance(instr.opcode, CInstructionJumpB):
    node.instructions.hl = HLInstructionJumpB(instr)
    self.insert_label_list.append(instr.opcode.VarIn)

Команды передачи управления внутри той же функции прыгают по конкретному адресу. В си‑коде нет адресов, поэтому мы добавляем в код новую инструкцию — метку с уникальным номером. На очередном проходе собранная информация о метках будет преобразована в новые инструкции.

def pass_InsertLabels(self, top_node):
    if hasattr(self, 'insert_label_list'):
        for i in self.insert_label_list:
            self.insert_label(i, top_node)
        self.insert_label_list = []
Отдельно хочу сказать о проходе, записывающем используемые переменные:

def pass_RecordUsedVars(self, node):
    node.Created = []
    node.Used = []

    for i in node.instructions:
        if hasattr(i, 'hl'):

            if hasattr(i.hl, 'Created'):
                node.Created += i.hl.Created

            if hasattr(i.hl, 'Used'):
                node.Used += i.hl.Used

    node.Created = list(set(node.Created))
    node.Used = list(set(node.Used))

Внутри каждой инструкции высокого уровня собираются поля с метаданными: какие переменные она использует и какие в ней были созданы.

class HLInstructionPush:
    def init(self, instr):
        opcode = instr.opcode
        stack = opcode.stack_snapshot_after
        stack_before = opcode.stack_snapshot_before

        self.VarIn = stack_before[-opcode.VarIn]
        self.VarOut = stack[-1]

        self.Used = [self.VarIn]
        self.Created = [self.VarOut]

    def repr(self):
        return f'{self.VarOut} = {self.VarIn};'

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

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

Метаданные из полей Created и Used используются для определения входных аргументов функций:

def get_func_args(self, top_node):
    Created = []
    Used = []

    for node, i in list(parse_graph(top_node, [])):

        if hasattr(node, 'Created'):
            Created += node.Created
            Used += node.Used

    # Used, but not created
    Args = list(set(Used) - set(Created))
    Args.sort(key=lambda x: x.index)
    return Args

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

Отдельный проход добавляет пролог и эпилог каждой функции, то есть инструкции, которые будут отрендерены в текст как func_44(var_2_bool){ ... }. Оставшийся проход добавляет отступы для кода слева.

Так выглядит распечатка финального древа:

task_0_event_5()
{
    StopGroup0(); // 0x3 Func
    return 0; // 0x5 Return
}

task_1_event_6()
{
    TaskCall(0); // 0x27 TaskCall
    func_0(); // 0x28 Call
    TaskReturn(); // 0x29 TaskReturn
    return 0; // 0x2b Return
}

main()
{
    var_0_object = Obj(); var_1_object = Obj(); // 0x6 PushV
    var_2_bool = 0; // 0x7 PushV
    func_44(var_2_bool); // 0x8 Call
    var_5_bool = var_2_bool == 0; // 0xa Not
    if(var_5_bool == 0) goto Label_17; // 0xb JumpB
    TaskCall(0); // 0xd TaskCall
    func_0(); // 0xe Call
    TaskReturn(); // 0xf TaskReturn

Label_17:
    var_6_string = "fire"; // 0x11 PushS
    FindParticleSystem(var_6_string, var_1_object); // 0x12 Func
    var_7_bool = var_1_object == 0; // 0x14 NullEq
    if(var_7_bool == 0) goto Label_26; // 0x15 JumpB
    var_8_string = "Can't find fire particle system"; // 0x16 PushS
    Trace(var_8_string); // 0x17 Func
    return 2; // 0x19 Return

Label_26:
    var_9_cvector = CVector(0.0, 0.0, 0.0); // 0x1a PushVec
    var_10_cvector = CVector(0.0, 1.0, 0.0); // 0x1b PushVec
    var_11_float = 0.0; // 0x1c PushF
    AddSource(var_9_cvector, var_10_cvector, var_11_float); // 0x1d ObjFunc
    Enable(); // 0x1f ObjFunc

Label_33:
    Hold(); // 0x21 Func
    goto Label_33; // 0x23 Jump
}


func_0()
{
    Hold(); // 0x0 Func
    return 0; // 0x2 Return
}


func_44(var_2_bool)
{
    var_3_bool = 0; var_4_bool = 0; // 0x2c PushV
    IsLoaded(var_4_bool); // 0x2d Func
    var_2_bool = var_4_bool; // 0x2f Mov
    return 2; // 0x30 Return
}

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

Сжатие кода​

Декомпилировав подобным образом все скрипты, я отловил несколько ошибок. Посмотрим на знакомый нам по прошлой статье скрипт item_milk.bin:

main()
{
    var_0_bool = 0; var_1_string = ""; var_2_float = 0; var_3_float = 0; var_4_float = 0; // 0x0 PushV
    var_1_string = "hunger"; // 0x1 MovS
    var_2_float = -0.17; // 0x2 MovF
    var_3_float = 0; // 0x3 MovI
    var_4_float = 1; // 0x4 MovI
    func_8(var_0_bool, var_1_string, var_2_float, var_3_float, var_4_float); // 0x5 Call
    return 0; // 0x7 Return
}

func_8(var_0_bool, var_1_string, var_2_float, var_3_float, var_4_float)
{
    var_5_bool = 0; var_6_float = 0; var_7_bool = 0; var_8_float = 0; // 0x8 PushV
    HasProperty(var_1_string, var_7_bool); // 0x9 Func
    var_9_bool = var_7_bool == 0; // 0xb Not
    if(var_9_bool == 0) goto Label_15; // 0xc JumpB
    var_0_bool = 0; // 0xd MovB
    return 4; // 0xe Return

Label_15:
    GetProperty(var_1_string, var_8_float); // 0xf Func
    var_10_float = 0; var_11_float = 0; var_12_float = 0; var_13_float = 0; // 0x11 PushV
    var_11_float = var_8_float + var_2_float; // 0x12 Add2
    var_12_float = var_3_float; // 0x13 Mov
    var_13_float = var_4_float; // 0x14 Mov
    func_27(var_10_float, var_11_float, var_12_float, var_13_float); // 0x15 Call
    SetProperty(var_1_string, var_10_float); // 0x17 Func
    var_0_bool = 1; // 0x19 MovB
    return 4; // 0x1a Return
}

func_27(var_10_float, var_11_float, var_12_float, var_13_float)
{
    var_14_bool = var_11_float < var_12_float; // 0x1c LT
    if(var_14_bool == 0) goto Label_32; // 0x1d JumpB
    var_10_float = var_12_float; // 0x1e Mov
    return 0; // 0x1f Return

Label_32:
    var_15_bool = var_11_float > var_13_float; // 0x20 GT
    if(var_15_bool == 0) goto Label_36; // 0x21 JumpB
    var_10_float = var_13_float; // 0x22 Mov
    return 0; // 0x23 Return

Label_36:
    var_10_float = var_11_float; // 0x24 Mov
    return 0; // 0x25 Return
}

Функции получают имена по адресам первой инструкции. В оригинальном коде у них были осмысленные имена, но они потерялись при компиляции. Процесс восстановления скрипта напоминает работу в IDA Pro: аналитик добавляет имена переменных и функций. Видимо, по‑другому декомпиляцию не провести.

main()
{
    var_0_bool = 0;
    func_8(var_0_bool, "hunger", -0.17, 0, 1);
    return;
}

func_8(var_0_bool, var_1_string, var_2_float, var_3_float, var_4_float)
{
    var_7_bool = 0; var_8_float = 0;
    HasProperty(var_1_string, var_7_bool);
    if(var_7_bool != 0) goto Label_15;
    var_0_bool = 0;
    return;

Label_15:
    GetProperty(var_1_string, var_8_float);
    var_10_float = 0;
    func_27(var_10_float, var_8_float + var_2_float, var_3_float, var_4_float);
    SetProperty(var_1_string, var_10_float);
    var_0_bool = 1;
    return;
}

func_27(var_10_float, var_11_float, var_12_float, var_13_float)
{
    if(var_11_float >= var_12_float) goto Label_32;
    var_10_float = var_12_float;
    return;

Label_32:
    if(var_11_float <= var_13_float) goto Label_36;
    var_10_float = var_13_float;
    return;

Label_36:
    var_10_float = var_11_float;
    return;
}

Код можно значительно упростить, подставляя определения переменных в те места, где они используются. Это несложно автоматизировать через RD-анализ, но проблема в том, что у меня нет определений используемых API вроде SetProperty. Без прототипов функций невозможно сказать, какие аргументы функция использует по значению, а какие по ссылке. Например, HasProperty принимает первый строковый аргумент как значение, а во второй записывает возвращаемое значение по ссылке. Но сжатие кода — это уже на будущее.

Выводы​

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