Maximize
Bookmark

VX Heaven

Library Collection Sources Engines Constructors Simulators Utilities Links Forum

Полиморфный генератор и детектор на основе формальных грамматик и конечных автоматов

Pawa
Январь 2009

[Вернуться к списку] [Комментарии]

В работе рассмотрено создание полиморфного генератора, описанного контекстно-свободной грамматикой и реализованного в виде недетерминированного автомата. Также рассмотрены проблемы детектирования кодовой последовательности, выдаваемой генератором. Показан пример детектирования - построен подходящий автомат. Примеры выполнены для IA-32 / Win32.

Грамматический подход

Первое упоминание моделирования техник мутации кода кода найдено в [1]. В работе [2] формально доказана возможность создания недетектируемых метаморфных генераторов. Работа [3] описывает грамматику, которая легла в основу вируса MetaPHOR. Рекомендуется также прочитать что-нибудь по грамматикам и автоматам, например, [4] - дешево и сердито.

В качестве примера рассмотрим генерацию различных вариантов следующего декриптора:

	1. mov R1, len
	2. mov R2, beg
	3. xor [R1], key
	4. add R2, 4
	5. sub R1, 4
	6. jnz 3

Каждую команду назовем блоком и присвоим ему порядковый номер. На эти номера будем иногда ссылаться по ходу повествования. У данного примера есть одно ограничение - он работает только с размерами кода, кратными 4.

Условно разобьем алгоритм на две части:

Соответственно, запишем эти две части в виде двух начальных правил грамматики:

	A -> XB
	B -> Y

Начнем конкретизировать данные правила.

	X  -> X1X2 | X2X1
	X1 -> GX1 | mov R1,len | push len + pop R1 | xor R1,R1 + lea R1,[R1 + len] | sub R1,R1 + add R1,len
	X2 -> GX2 | mov R2,beg | push beg + pop R2 | xor R2,R2 + lea R2,[R2 + beg] | sub R2,R2 + add R2,beg

Первое правило соответствует тому, что блоки 1 и 2 можно менять местами. Часть правила X1 -> GX1 означает, что возможен переход на правило G - генерацию мусора. Про генерацию мусора поговорим ближе к концу.

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

	x1 xor x2  = not(not x1 xor x2) = (x1 and not x2) or (not x1 and x2)

Получим следующий набор правил:

	Y  -> GY | W1 | S4W2
	W1 -> GW1 | xor [R2],key H1
	W1 -> not [R2] + xor [R2],key + not [R2] H1
	W1 -> mov R3,[R2] + not R3 + and R3,key + and [R2],not key + or [R2],R3 H1
	H1 -> GH1 | add R2,4 H2 | sub R2,-4 H2
	S4 -> GS4 | sub R2,4 | add R2,-4
	W2 -> GW2 | xor [R1][R2],key H2
	W2 -> not [R1][R2] + xor [R1][R2],key + not [R1][R2] H2
	W2 -> mov R3,[R1][R2] + not R3 + and R3,key + and [R1][R2],not key + or [R1][R2],R3 H2
	H2 -> GH2 | sub R1,4 + jnz xxx | sub R1,4 + jz yyy + jmp xxx
	H2 -> add R1,-4 + jnz xxx | add R1,-4 + jz yyy + jmp xxx
	H2 -> sub ecx,3 + loop xxx <=> R1 == ecx

Указанный набор правил реализует следующие соображения. Правило Y дает "вилку" на два типа расшифровщика - с базовой и базово-индексной адресацией. Правила расшифрования W1 и W2 реализуют три эквивалентных формулы для операции XOR. Правила H1 и H2 описывают эпилог цикла - изменение счетчиков и условный переход. Правило S4 уменьшает адрес начала с расшифровываемыми данными, чтобы попасть в границы буфера при его проходе с конца.

Описанный генератор может выдавать 4*4*(3*2 + 2*3)*5 = 16*12*5 = 960 вариантов декрипторов, это не учитывая изменения регистров и мусора.

Реализация генератора

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

        command struct
                code                    dq ?    ;буфер команды
                scode                   dq ?    ;короткий вариант команды
                commandLength           db ?
                shortCommandLength      db ?
                reg1                    db ?    ;позиция первого регистра
                reg2                    db ?    ;позиция второго регистра
                reg3                    db ?    ;позиция третьего регистра
                immPosition             db ?    ;позиция непосредственного операнда
                shortImmPosition        db ?    ;позиция непосредственного операнда в короткой команде
        command ends
 

Данная структура, конечно, не оптимальна с точки зрения использования памяти: под смещение регистра от начала команды требуется 5 бит, под смещение непосредственного операнда от начала команды в байтах 2 бита, под короткий вариант команды 1 байт, под длину команды 2-3 бита. Но это учебный пример. Если в команде нет какой-то компоненты, инициализируем соответствующий член структуры значением 0FFh.

Для каждого правила последовательности команд формируются в блок выбора эквивалентов. Например, для правил X1 или X2 блок выглядит так:

        x       db 4            ;4 эквивалента в блоке
                db 1            ;длина последовательности команд
        command <0B8h,0FFh,5,0FFh,5,0FFh,0FFh,1,0FFh>   ;первый эквивалент для mov R1,imm32
                                ;0FFh означает, что соответствующее поле не заполнено,
                                ;5 - длина команды 5 байт
                                ;5 - битовая позиция регистра в коде команды
                                ;1 - байтовое смещение от начала команды на непосредственные данные
                db 2            ; push/pop
        command <68h,0FFh,5,0FFh,0FFh,0FFh,0FFh,1,0FFh>
        command <58h,0FFh,1,0FFh,5,0FFh,0FFh,0FFh,0FFh>
                db 2            ; xor/lea
        command <0C033h,0FFh,2,0FFh,10,13,0FFh,0FFh,0FFh>
        command <808Dh,0FFh,6,0FFh,10,13,0FFh,2,0FFh>
                db 2            ;sub/add
        command <0C02Bh,0FFh,2,0FFh,10,13,0FFh,0FFh,0FFh>
        command <0C081h,05h,6,5,13,0FFh,0FFh,2,1>
 

Стоит отметить, что из-за объявления буфера кода как учетверенного слова (dq) и особенностей архитектуры процессоров Интел, приходится "переворачивать" байты команд при записи последних в элементы структуры. Осталось реализовать процедуру buildCommand, которая на основе указанной структуры command и переданных значений регистров и непосредственного операнда сконструирует готовую команду.

Правила рассмотренной выше грамматики эквивалентны следующему недетерминированному конечному автомату:

    0    1     2    3    4     5     6
        X1 -> X2        W1 -> H1
    A ->         -> Y ->          -> H2
        X3 -> X4        S4 -> W2
    0    7     8    3    9     10

Отметим, что состояние X3 эквивалентно состоянию X2, X4 эквивалентно состоянию X1. Каждое состояние опишем следующей структурой:

        state struct
                callback        dd ?    ;функция обработки состояния
                brunchNum       db ?    ;количество "вилок" в переходе
                state1          db ?    ;новое состояние
                state2          db ?    ;новое состояние
                state3          db ?    ;новое состояние
        state ends
 

Здесь член state3 излишен и применяется для выравнивания размера структуры до 8-ми байт с целью более простого ее использования. Генерация команд в каждом состоянии будет осуществляться при вызове соответствующей callback-процедуры. На основе данной структуры "состояние" опишем автомат таблицей:

        states  state < 0        , 2, 1, 7,-1> ;0 <=> A
                state < offset X1, 1, 2,-1,-1> ;1 <=> X1
                state < offset X2, 1, 3,-1,-1> ;2 <=> X2
                state < 0        , 2, 4, 9,-1> ;3 <=> Y
                state < offset W1, 1, 5,-1,-1> ;4 <=> W1
                state < offset H1, 1, 6,-1,-1> ;5 <=> H1
                state < offset H2, 0,-1,-1,-1> ;6 <=> H2 - finish state
                state < offset X2, 1, 8,-1,-1> ;7 <=> X3
                state < offset X1, 1, 3,-1,-1> ;8 <=> X4
                state < offset S4, 1,10,-1,-1> ;9 <=> S4
                state < offset W2, 1, 6,-1,-1> ;10<=> W2
 

Имея табличное описание, просто реализуется процедура automaton, которая осуществляет переходы между состояниями и обеспечивает вызов callback-функций. Здесь же реализуется вызов генератора мусорных инструкций.

Другим важным компонентом генератора является генератор случайных чисел. Воспользуемся конгруэнтным генератором с подходящим выбором констант. Подробнее можно почитать в Д. Кнут, Искусство программирования, Т.2. Выбором констант можно добиться максимального периода генератора (в нашем случае, 2^32). Если применить метод случайного сбоя генератора каждый N-ный шаг, можно вообще исключить период, не ухудшая качества случайных чисел. Для инициализации генератора и последующих сбоев будем использовать инструкцию RDTSC.

Выбор событий с заданной вероятностью осуществляется исходя из следующих соображений. Конгруэнтный генератор выдает равномерно распределенные случайные величины. Делением очередного случайного числа на максимальное значения генератора (в нашем случае 65536, как у функции rand из библиотеки Си) получаем выход генератора в диапазоне [0..1]. Для равномерных случайных величин из диапазона [0..1], вероятность P{x <= 0.8} = 0.8, вероятность P{0.3 < x <= 0.4} = P{x <= 0.4} - P{x <= 0.3} = 0.4 - 0.3 = 0.1. То есть, имея таблицу вероятностей выбора событий и равномерный датчик диапазона [0..1], отслеживая в какой диапазон попадает очередное число, можно сказать, какое из событий произошло.

Начало же работы полиморфного генератора выглядит следующим образом: случайно выбираются регистры R1,R2,R3, ключ шифрования и запускается процедура automaton.

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

Детектирование

Автомат для детектирования всех возможных декрипторов выглядит следующим образом.

automaton-detector

Нетрудно видеть, что произвольный декриптор, выдаваемый нашей грамматикой типа 2 (недетерминированным автоматом) детектируется обыкновенным конечным детерминированным автоматом с 28 состояниями. В принципе, в этом нет ничего удивительного, так как недетерминированный автомат сводится к детерминированному путем экспоненциального увеличения числа состояний.

Что тут можно сделать... Можно увеличить количество правил исходной грамматики, в этом случае автомат-детектор будет много сложнее. А можно генерировать очень "хитрый" мусор, похожий на полезные команды декриптора, с целью загнать данный автомат в такое промежуточное состояние, из которого он не выйдет. Например, если подать на вход автомату-детектору последовательность команд:

	mov	;мусор
	push	;мусор
	mov	;1
	sub	;2
	add	;2
	xor	;3
	add	;4
	sub	;5
	jnz	;6
	pop	;мусор

В этом случае, автомат до последней команды зациклится в состоянии q5, а декриптор тем временем выполнится.

Что бы все это проверить, реализуем процедуру дизассемблирования на основе движка Hacker Disassembler Engine 32 C. Полученная программа disasm.c вычитывает N файлов из указанного каталога, дизассемблирует их и выдает листинг на стандартный вывод. Пример листинга без мусорных инструкций.

    samples/file0 30
    00 PUSH 44554433
    01 POP ESI
    02 SUB EBX,EBX
    03 ADD EBX, 124
    04 XOR [ESI],d20b9a65
    05 ADD ESI,4
    06 SUB EBX,4
    07 JZ $ + 2
    08 JMP $ + f0

    samples/file1 42
    00 XOR EDI,EDI
    01 LEA EDI,[EDI+124]
    02 PUSH 44554433
    03 POP ESI
    04 MOV EDX,[ESI]
    05 NOT EDX
    06 AND EDX,d75d40bc
    07 AND [ESI],28a2bf43
    08 OR [ESI],EDX
    09 ADD ESI,4
    10 SUB EDI,4
    11 JZ $ + 2
    12 JMP $ + e4

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

    [0] = PUSH  state: 0 => 1
    [1] = POP   state: 1 => 4
    [2] = SUB   state: 4 => 7
    [3] = ADD   state: 7 => 8
    [4] = XOR   state: 8 => 9
    [5] = ADD   state: 9 => 17
    [6] = SUB   state: 17 => 25
    [7] = JZ    state: 25 => 26
    [8] = JMP   state: 26 => 27
    DETECTED
    [0] = XOR   state: 0 => 2
    [1] = LEA   state: 2 => 4
    [2] = PUSH  state: 4 => 5
    [3] = POP   state: 5 => 8
    [4] = MOV   state: 8 => 10
    [5] = NOT   state: 10 => 11
    [6] = AND   state: 11 => 12
    [7] = AND   state: 12 => 13
    [8] = OR    state: 13 => 9
    [9] = ADD   state: 9 => 17
    [10] = SUB  state: 17 => 25
    [11] = JZ   state: 25 => 26
    [12] = JMP  state: 26 => 27
    DETECTED

Из примера видно, что автомат-детектор успешно распознает указанные варианты декрипторов. Проведенные тесты показывают, что детектор определяет все варианты декрипторов, выдаваемых нашим генератором. Это не удивительно - автомат работает как и задумано. В примере использовался генератор без мусорных инструкций. Усложним задачу: добавим в генератор возможность добавления случайных мусорных инструкций (однобайтные команды типа cld), а также инструкций, используемых в правилах X1 и X2 с произвольными значениями регистров (из числа неиспользуемых) и констант (см. файл pgen2.asm). Пример листинга после дизассемблирования приведен ниже.

    00 GRBG
    01 MOV EDX,124
    02 GRBG
    03 GRBG
    04 XOR ESI,ESI
    05 LEA ESI,[ESI+44554433]
    06 MOV EBX,b69bcb88
    07 XOR EBX,EBX
    08 LEA EBX,[EBX+a40b14ee]
    09 GRBG
    10 GRBG
    11 GRBG
    12 GRBG
    13 XOR ECX,ECX
    14 LEA ECX,[ECX+ddb3fe99]
    15 GRBG
    16 GRBG
    17 GRBG
    18 PUSH 154f25e1
    19 POP EBX
    20 XOR [ESI],b79275ab
    21 GRBG
    22 ADD ESI,4
    23 SUB EDX,4
    24 JNZ $ + f1

Вывод автомата-детектора после обработки этого и других вариантов декрипторов:

    [0] = GRBG  state: 0 => 0
    [1] = MOV   state: 0 => 4
    [2] = GRBG  state: 4 => 4
    [3] = GRBG  state: 4 => 4
    [4] = XOR   state: 4 => 6
    [5] = LEA   state: 6 => 8
    [6] = MOV   state: 8 => 10
    [7] = XOR   state: 10 => 10
    [8] = LEA   state: 10 => 10
    [9] = GRBG  state: 10 => 10
    [10] = GRBG state: 10 => 10
    [11] = GRBG state: 10 => 10
    [12] = GRBG state: 10 => 10
    [13] = XOR  state: 10 => 10
    [14] = LEA  state: 10 => 10
    [15] = GRBG state: 10 => 10
    [16] = GRBG state: 10 => 10
    [17] = GRBG state: 10 => 10
    [18] = PUSH state: 10 => 10
    [19] = POP  state: 10 => 10
    [20] = XOR  state: 10 => 10
    [21] = GRBG state: 10 => 10
    [22] = ADD  state: 10 => 10
    [23] = SUB  state: 10 => 10
    [24] = JNZ  state: 10 => 10
    NOT DETECTED
    ...
    Total code sequences:   100
    Detected sequences:     68
    Non-detected sequences: 32

Таким образом, незначительное усложнение генератора приводит в вероятности детектирования в 2/3. Усовершенствование автомата-детектора довольно трудоемко. Однако, детектирование возможно путем прогона декриптора через эмулятор и выявление сигнатуры в распакованном теле программы, либо же путем мониторинга системных вызовов. Если способы борьбы с первым типом известны - анти-эмуляционные приемы или метаморфное изменение всего тела программы, то с детектированием по системным вызовам дела обстоят намного хуже.

Вместо заключения

Генерация "правильного" мусора - интересная тема. Например, очень неплохо выглядит мусорный вызов процедуры:

        ...
        push    @after_garbage
        cmp     Reg,что-нибудь
        jxx     @label_call_proc
@proc:
        push    ebp
        mov     ebp,esp
        sub     esp,N
        ...
        ;возможен рекурсивный вызов генератора мусора
        ;возможно выполнение полезных инструкций
        ...
        mov     esp,ebp
        pop     ebp
        ret
@label_call_proc:
        ;возможен мусор
        call    @proc
@after_garbage:
        ...
 

Хороший генератор мусорных инструкций может решать несколько задач:

Литература

  1. Qozah. Polymorphism and grammars, 29A E-zine, 1999, #4
  2. Filiol E. Metamorphism, Formal Grammars and Undecidable Code Mutation, Proceedings of World Academy of Science, Engineering and Technology (PWASET), 2007. Volume 20.
  3. SPTH. Chomsky Hierarchy and the Word Problem in Code Mutation.
  4. Пентус А. Е., Пентус М. Р. Теория формальных языков. Учебное пособие

Приложение

[Вернуться к списку] [Комментарии]
By accessing, viewing, downloading or otherwise using this content you agree to be bound by the Terms of Use! vxheaven.org aka vx.netlux.org
deenesitfrplruua