«МЕТОД ЗАЩИТЫ ИСПОЛНЯЕМОГО ПРОГРАММНОГО КОДА ОТ ДИНАМИЧЕСКОГО И СТАТИЧЕСКОГО АНАЛИЗА ...»

Так же хочется выделить компанию VMProtect, которая для своих приложений использует метод виртуализации кода, как один из основных методов защиты программного обеспечения. В настоящее время их наиболее популярный продукт - VMProtect SenseLock Edition (VMProtect SE) - это совместная разработка компании "VMProtect Software" и "Seculab", в которой реализованы все новейшие достижения в области защиты программного обеспечения от несанкционированного использования [Ошибка! Источник ссылки не найден.]:

выполнение кода защиты с использованием электронного ключа;

ограничивающиеколичество запусков, устанавливать ограничения по времени работы программы, лицензировать разные участки кода с привязкой к различным лицензиям;

асимметричного алгоритма RSA-1024, исключающий появление эмуляторов.

В завершении анализа хочется отметить, что метод виртуализации в защите ПО с различными ограничениями реализован в таких крупных продуктах как StarForce3, Themida, NeoGuard, VMProtect и др. и, таким образом, только комплексное использование всех вышеизложенных методов позволит создать по настоящему эффективный продукт способный противодействовать современным вызовам.

ЗАЩИТА ИСПОЛНЯЕМОГО КОДА ОТ СТАТИЧЕСКОГО АНАЛИЗА

Виртуализация программного кода псевдослучайным набором инструкций 2. 2.2.1 Понятие виртуальных машин Существует несколько подходов к определению виртуальной машины.

Виртуальная машина — это:

программная и/или аппаратная система, эмулирующая аппаратное обеспечение некоторой гостевой (целевой) платформы и исполняющая программы для целевой платформы на хост-платформе;

система, виртуализирующая некоторую платформу и создающая на ней среды, изолирующие друг от друга программы и даже операционные системы;

спецификация некоторой вычислительной среды.

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

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

Рассмотрим работу виртуального процессора подробнее. Для этого введем понятие алгоритма.

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

Компилятор преобразует текстовую форму виртуальной программы в код, который будет интерпретироваться виртуальным процессором. Так же, как и реальный процессор, виртуальный процессор использует программный счетчик (program counter), который указывает на текущую виртуальную команду. Виртуальный процессор выбирает очередную команду (получает ее кодовый номер) и вызывает инструкцию с указанным номером. Инструкция получает свои аргументы, следующие за кодом команды, и выполняет действия, реализующие эту команду.

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

компиляция и интерпретация.

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

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

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

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

Для выполнения диссертационного исследования для создания промежуточного представления был выбран инструмент LLVM (Low Level Virtual Machine). Проект LLVM представляет собой универсальную систему анализа, трансформации и оптимизации программ.

Несмотря на свое название, LLVM не является традиционной виртуальной машиной, но предоставляет полезные библиотеки, которые могут быть использованы для их создания. В основе LLVM лежит промежуточное представление кода (intermediate representation, IR), над которым можно производить трансформации во время компиляции, компоновки и выполнения.

На выбор LLVM повлияли следующие его преимущества:

библиотеки LLVM обеспечивают генерацию кода для многих популярных процессоров, среди которых x86, x86-64, ARM, PowerPC, SPARC, MIPS, IA-64, Alpha.

Эти библиотеки строятся вокруг четко определенного представления кода, известного как промежуточное представление LLVM (LLVM IR). Таким образом, обеспечивает многоплатформенность нашего протектора;

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

Кроме того, LLVM предоставляет API ко всем частям компилятора.

2.2.2 Виртуальная машина Тьюринга Простейшим примером виртуальной машины является виртуальная машина Тьюринга.

Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина), предложенная Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам преобразует входные данные с помощью последовательности элементарных действий. Элементарность действий заключается в том, что действие меняет лишь небольшой кусочек данных в памяти (в случае машины Тьюринга — лишь одну ячейку), и число возможных действий конечно.

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

Рассмотрим состав конкретной машины Тьюринга. Она задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина [10]. Для каждой возможной конфигурации, где qi – состояние и aj – буква алфавита, имеется ровно одно правило перехода. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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

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

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

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

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

На рисунке 2.1 показано, как блок инструкций x86 преобразуется в различные виртуальные инструкции, соответствующие блоку исходного кода.

Рисунок 2.1 - Генерация различных кодов виртуальной машиной на основе одного блока Когда злоумышленник попытается дизассемблировать блок кода, защищенный протектором, он не увидит оригинальных инструкций x86. Вместо этого он обнаружит абсолютно новый набор инструкций, который неизвестен злоумышленнику или какому-либо декомпилятору. Таким образом, чтобы получить исходный алгоритм, злоумышленник должен проделать очень сложную работу по распознаванию семантики каждого опкода и того, как определенная виртуальная машина работает для каждого защищаемого приложения. Поэтому важно варьировать максимально большое количество параметров виртуальных машин таким образом, чтобы виртуальные машины, создаваемые генератором виртуальных машин, кардинально отличались друг от друга. Кроме того, привязка создаваемой виртуальной машины к защищаемому коду алгоритму является дополнительным осложнением, помогающим защитить генератор от анализа и обратного проектирования.

2.2.4 Выбор защищаемого участка кода Как уже было сказано, главная цель нашего протектора – защита алгоритмов, являющихся интеллектуальной собственностью и коммерческой тайной. Очевидно, что нет необходимости защищать приложение полностью, так как это увеличивает время работы программного продукта и предоставляет большее количество данных для анализа (например, статистического). Поэтому разрабатываемый протектор позволяет защитить именно ту часть исполняемого файла, которая содержит этот алгоритм. Для этого необходимо выбрать функцию, в которой содержится тот код, который представляет определенную ценность.

Список всех доступных функций строится на основе анализа секций исполняемого файла с помощью API LLVM. Затем, определенный блок инструкций ассемблера x86 может быть трансформирован в различные блоки инструкций для каждой виртуальной машины, что способствует защите от анализа злоумышленником генерируемых виртуальных опкодов после трансформации инструкций различными виртуальными машинами. Рисунок иллюстрирует преобразование части исполняемого файла в защищенный код.

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

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

Исходный исполняемый файл Рисунок 2.2 - Исполняемый файл и соответствующий защищенный файл 2.2.5 Создание виртуальной машины и общая схема защиты исполняемого файла При создании конкретной виртуальной машины необходимо выполнить следующие этапы:

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

Механизм выбора этих данных описан в разд. 1.3.

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

3. Реализовать интерпретатор виртуальной машины, представляющий собой совокупность механизмов. Посредством этих механизмов виртуальная машина осуществляет интерпретацию команд, находящихся в программном поле.

4. Реализовать транслятор из внешнего представления бинарного файла в последовательность команд виртуальной машины.

Для виртуальной машины должен быть определён способ её использования, то есть:

способ передачи входной информации и формирования точки входа в виртуальную способ активизации (запуска) системы;

способ останова системы;

способ извлечения переработанной информации [11].

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

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

2.2.6 Классы используемых виртуальных машин Все многообразие виртуальных машин, которое строится генератором виртуальных машин, можно разделить на следующие классы:

- по способу адресации: регистровые и стековые;

- по составу и сложности команд: CISC или RISC;

- виртуальные машины с командами одинаковой или разной длины;

- виртуальные машины с регистрами одинаковой или разной длины;

- виртуальные машины с регистрами одного или разных типов.

Эти классы виртуальных машин полны по Тьюрингу т.е. на них можно реализовать любую вычислительную функцию. Рассмотрим их подробнее.

2.2.7 Стековые и регистровые виртуальные машины Стековые виртуальные машины Этот класс виртуальных машин определяется организацией регистрового файла в виде стека, и косвенной адресацией регистров через указатель стека, который определяет положение вершины стека [12]. Операции производятся над значениями на вершине стека, и результат кладётся также на вершину.

Все команды используются без операндов, поэтому арифметические операции кодируются в нуль-операндные инструкции. Например, команда sub (вычесть) берет с вершины стека два числа, вычитает первое из второго и результат вталкивает в стек. Разумеется, до этого необходимые значения вставляются в стек.

Отдельной команды, которая кладет в стек значение переменной, или константу нет.

Переменная или константа сама является командой вставки этой константы в стек.

Вот пример кода для выражения a*(b-10) (действие команды MUL аналогично SUB, только вместо вычитания она перемножает значения в стеке):

Таким образом, стековая система команд для выражения - это система команд в виде обратной польской записи.

Достоинства:

- простота аппаратной реализации;

- простота записи алгоритмов вычисления;

- простота мнемонического описания микроопераций (с одним или без операндов).

Недостатки:

- Стек – запоминающее устройство с последовательным доступом обладающее медленной скоростью работы. Но этот недостаток не играет существенной роли т.к. главная задача – надежная защита кода [13].

К стековым виртуальным машинам относятся:

Регистровые виртуальные машины Регистровая архитектура характеризуется свободным доступом к регистрам для выборки всех аргументов и записи результата [14]. Это значит, что для регистровой виртуальной машины, в отличие от стековой, в качестве хранилища промежуточных результатов вычислений используется не стек, а регистры общего назначения. Эти регистры, в каком-то смысле, можно рассматривать как явно управляемый кэш для хранения недавно использовавшихся данных. Размер регистров может быть как фиксирован, так и нет. К любому регистру можно обратиться, указав его имя.

Общий вид операций наших регистровых виртуальных машин имеет вид:

OP получатель, источник1, источник2, …, источникN OP получатель OP - это код операции. В качестве источника может быть либо регистр, либо переменная, либо число. Из источника берутся данные для выполнения операции. Получателем для наших виртуальных машин может быть как регистр, так и переменная. Результат операции помещается в получателя.

Код операции вместе с кодами операндов для создаваемых виртуальных машин занимают максимум 64 бита. При этом если у инструкции есть операнды, то их коды должны идти следом за кодом инструкции и их число не должно превышать семи.

Пример команды MOV(загрузить) с различными источниками:

MOV R1, S (загрузить значение переменной S в регистр R1) MOV R2, 24 (загрузить число 24 в регистр R2) MOV R1, R5 (загрузить значение из регистра R5 в регистр R1) Регистровые виртуальные машины допускают расположение операндов в одной из двух запоминающих сред: основной памяти или регистрах. Мы будем рассматривать три подвида команд обработки: регистр-регистр; регистр-память; память-память.

- В варианте «регистр-регистр» операнды могут находиться только в регистрах. В них же записывается и результат.

- Подтип «регистр-память» предполагает, что один из операндов размещается в регистре, а второй в основной памяти. Результат обычно замещает один из операндов.

- В командах типа «память-память» оба операнда хранятся в основной памяти. Результат также заносится в память.

Вариант «регистр-регистр» является основным в вычислительных машинах типа RISC.

Команды типа «регистр-память» характерны для CISC-машин. В наших же виртуальных машинах оба эти варианта будут равноправны для RISC и CISC виртуальных машин.

Достоинства:

- Обеспечивается высокая скорость работы с кэшем, что позволяет эффективнее осуществлять арифметические операции.

- При переходе к решению задач управления эффективность таких виртуальных машин падает, так как при переключениях подпрограмм необходимо разгружать и загружать регистры в кэш [15].

Примерами регистровых виртуальных машин являются:

2.2.8 RISC – CISC виртуальные машины Двумя основными классами виртуальных машин по составу команд являются виртуальные машины с архитектурой CISC и RISC.

а) RISC (Reduced (Restricted) Instruction Set Computer) – уменьшенный набор команд, которыми пользуется виртуальная машина, содержащая только наиболее простые команды.

Особенности этого класса виртуальных машин.

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

Обращение к памяти допускается лишь с помощью специальных команд чтения и Небольшое количество форматов команд и способов указания адресов операндов.

Реализация сложных команд за счет последовательности простых, но быстрых RISCкоманд [16].

Примерами RISC виртуальных машин являются:

TRVM, the Tiny RISC Virtual Machine;

б) CISC (Complete Instruction Set Computer) – полный набор команд микропроцессора.

Для виртуальных машин CISC-архитектуры характерны:

наличие сравнительно небольшого числа регистров общего назначения;

большое количество машинных команд, некоторые из них аппаратно реализуют сложные операторы виртуальной машины;

разнообразие способов адресации операндов;

множество форматов команд различной разрядности;

наличие команд, где обработка совмещается с обращением к памяти.

Особенностью виртуальных машин с RISC архитектурой является наличие достаточно большого регистрового файла (в типовых RISC-процессорах реализуются 32 или большее число регистров по сравнению с 8–16 регистрами в CISC архитектурах). Это позволяет большему объему данных храниться в регистрах более длительное время и упрощает работу компилятора по распределению регистров под переменные.

Количество регистров в архитектурах типа CISC обычно невелико (от 8 до 32), и для представления номера конкретного регистра необходимо не более пяти разрядов, благодаря чему в адресной части команд обработки допустимо одновременно указать номера двух, а зачастую и трех регистров (двух регистров операндов и регистра результата). RISC-архитектура предполагает использование существенно большего числа регистров общего назначения (до нескольких сотен). Однако, типичная для таких ВМ длина команд (обычно 32 разряда) позволяет определить в команде до трех регистров [17]. В разрабатываемом протекторе длина команды составляет 64 бита, что позволяет создавать команды с числом операндов, не превышающим семи, при этом, на данный момент реализованы только команды, имеющие до трех операндов.

Примерами CISC виртуальных машин являются:

2.2.9 Виртуальные машины с командами одинаковой и разной длины Средняя длина команды составляет 3,5 байта. Поскольку МП 80386 использует 16байтовую очередь команд, в среднем 5 команд оказываются предварительно выбранными из памяти[18].

Команды содержат 0, 1, 2 или 3 операнда и, теоретически можно так же реализовать команды с числом операндов равным 4, 5, 6 и 7. Операнды могут храниться в регистре, в самой команде или в памяти. Большинство безоперандных команд занимают лишь 1 байт, в то время как двухоперандные команды обычно имеют длину 2 байт. Однако к любой команде может быть добавлен префикс замены длины операнда, действующей по умолчанию.

Принадлежность виртуальной машины к одному из этих классов определяется принадлежностью к определенному классу CISC или RISC.

Для виртуальных машин класса RISC длина команд одинаковая, а для виртуальных машин класса CISC она варьируется.

2.2.10 Виртуальные машины с регистрами одинаковой или разной длины Регистры виртуальной машины могут иметь фиксированную или варьирующуюся длину регистров. Принадлежность к одному из этих классов для каждой виртуальной машины выбирается произвольным образом.

Примеры виртуальных машин с регистрами одной длины:

Dalvic virtual machine (все регистры 32 бита);

Java virtual machine (все регистры 32 бита).

Примеры виртуальных машин с регистрами разной длины:

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

Пример виртуальной машины с регистрами одного типа: Java Virtual Machine – все регистры типа float.

Примеры виртуальных машин с регистрами разных типов:

Parrot – имеет регистры четырех типов: float, integer, string, parrot magic cookie (специальный тип для этой виртуальной машины);

2.2.12 Определение набора правил, по которым происходит создание всего многообразия виртуальных машин Каждая виртуальная машина содержит интерпретатор. Интерпретатор виртуальной машины для нашего протектора написан на языке C и реализуется в виде условного оператора типа «switch» с большим количеством условий. Интерпретатор обрабатывает входные данные, написанные на языке виртуальной машины. Язык виртуальной машины отличается от языка машин x86 и динамически формируется в процессе генерации виртуальной машины. Правила формирования языков виртуальных машин описаны дальше.

2.2.13 Коды операций виртуальных машин Байт-код виртуальной машины представляет собой скомпилированный бинарный код, предназначенный исключительно для интерпретатора этой виртуальной машины. Алгоритм работы виртуальной машины:

1. Получить опкод виртуальной машины и ее аргументы.

2. Выполнить инструкцию.

3. Повторять шаг 1) и 2) до команды выхода.

Рассмотрим этот алгоритм на псевдокоде:

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

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

В зависимости от архитектуры, операнды могут быть значениями регистров, значениями стека, значениями в памяти, непосредственными значениями.

У нас есть множество кодов операций для каждой построенной виртуальной машины.

Эти опкоды уникальны по построению. Закодируем опкоды, чтобы скрыть структуру построения. Нам необходимо сохранить уникальность опкодов, и, кроме того, полученные опкоды должны так же иметь размерность 8 бит. Таким образом, необходимо построить автоморфизм изоморфизм группы на себя. Для каждого опкода сгенерируем 3 произвольных значения:

key1 = randFromTo(0, 7);

key2 = randFromTo(0, 0xFF);

key3 = randFromTo(0, 7);

И выполним следующие автоморфные преобразования опкодов.

b = ror(b, key1); циклический сдвиг вправо b = rol(b, key3); циклический сдвиг влево Так как расшифровывать опкоды нет необходимости, можно использовать любые автоморфные преобразования.

2.2.14 Регистры виртуальных машин Для построения языков виртуальных машин определим сначала, что представляют собой регистры виртуальных машин. Рассмотрим конечное множество R регистров заданной виртуальной машины. Каждый регистр характеризуется именем и размером:

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

Множество имен регистров будет уникальным для каждой виртуальной машины. На этапе генерации виртуальной машины случайным образом сгенерируется конечное множество имен регистров. Так как все регистры имеют одинаковый размер не надо делать акцент на их имени, который позволит по именам определять размер регистра (как это сделано в языке ассемблер: eax, ebx – 32-разрядные регистры, ax, bx – 8-разрядные регистры и т.д.).

Код на языке ассемблера:

Код на языке виртуальной машины:

advm17 R13, R11, R Набор создаваемых кодов (имен) регистров уникален по построению. Чтобы скрыть структуру построения кодов регистров используем автоморфные преобразования, аналогичные преобразованиям для кодов инструкций.

Также для всех виртуальных машин введем следующие ограничения по числу регистров:

количество регистров не может быть меньше двух;

максимальное количество регистров не превышает целого числа n, которое динамически определяется для каждой виртуальной машины.

Остальные правила будут изменяться в зависимости от классификации, приведенной в п.

3.4. Создадим набор правил построения таких виртуальных машин.

2.2.15 Правил построения виртуальных машин разных классов 1) Стековые или регистровые Для стековых виртуальных машин все операции будут описываться в польской записи.

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

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

б) Регистровые Для регистровых виртуальных машин все операции представляются в виде:

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

В отличие от x86, количество источников для каждой операции может варьироваться, но не превышать 7, как описано в разд. 3.4. Наиболее распространенный случай для арифметических операций - один приемник и два источника, например:

add32 R1, R2 (сложить значения регистров 32 –битных регистров R2 и R1, результат положить в R1) Но также могут встречаться операции с одним или тремя … или с семью источниками.

2) CISC или RISC архитектура Для виртуальных машин типа CISC будет переопределено всё многообразие команд x86.

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

Виртуальные машины типа RISC будут содержать ограниченный (базовый) набор инструкций. Это означает, что одна инструкция типа CISC будет представлена в виде нескольких инструкций виртуальной машины.

Например, инструкция со сложным обращением к памяти mov eax, [ebx+ecx*4+123456h] будет заменена на следующую последовательность инструкций:

3) Виртуальные машины с командами одинаковой или разной длины В виртуальных машинах с командами одинаковой длины команды имеют размер 8 байт.

Длина команд в виртуальных машинах с различной длиной команд зависит от количества операндов:

Максимальный размер команды – 8 байт, и таким образом теоретически может быть до операндов.

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

Виртуальные машины с регистрами разной длины будут поддерживать размеры регистров 8, 16, 32, 64 бита, а так же 80 бит для некоторого подкласса команд.

4) Виртуальные машины с регистрами одного или разных типов В виртуальных машинах с регистрами одного типа все регистры имеют тип float.

В виртуальных машинах с регистрами разных типов поддерживаются регистры типов float и integer.

2.2.16 Правила построения табличного, не табличного и недетерминированного языков ассемблера виртуальной машины Мы будем рассматривать следующие классы операций для построения языков ассемблера виртуальной машины:

а) арифметические операции;

б) логические операции;

в) операции сравнения;

г) control flow;

д) операции сдвига;

е) операции со стеком;

ж) операции пересылки данных.

Перечисленные выше классы представляют основные операции языков виртуальной машины и поэтому позволяют полностью описать всё многообразие этих языков. Большинство инструкций допускает довольно широкий спектр операндов, как с точки зрения синтаксиса, так и с точки зрения семантики.

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

сначала указывается мнемокод, отображающий семантику команды:

xor – логическая операция «исключающего или», or – операция логического сложения, and – операция логического умножения, not – операция логического отрицания, add – арифметическая операция сложения, sub – арифметическая операция вычитания, mul – арифметическая операция умножения, div – арифметическая операция деления, je – операция перехода, если сравниваемые значения равны, jne – операция перехода, если сравниваемые значения не равны, jl – операция перехода для знаковых операндов, если значение первого операнда инструкции сравнения меньше значения второго, jg – операция перехода для знаковых операндов, если значение первого операнда инструкции сравнения больше значения второго jle– операция перехода для знаковых операндов, если значение первого операнда инструкции сравнения меньше или равно значению второго, jge– операция перехода для знаковых операндов, если значение первого операнда инструкции сравнения больше или равно значению второго, ja - операция перехода для беззнаковых операндов, если значение первого операнда инструкции сравнения выше значения второго jae - операция перехода для беззнаковых операндов, если значение первого операнда инструкции сравнения выше или равно значению второго jb - операция перехода для беззнаковых операндов, если значение первого операнда инструкции сравнения ниже значения второго, jbe – операция перехода для беззнаковых операндов, если значение первого операнда инструкции сравнения ниже или равно значению второго, load – операция извлечения из стека, store – операция вставки в стек, mov – операция пересылки данных, shr – операция побитового сдвига вправо, shl – операция побитового сдвига влево, rol – операция циклического побитового сдвига влево, ror – операция циклического побитового сдвига вправо, call – вызов процедуры;

для команд с вещественными операндами перед соответствующей командой ставится префикс f;

затем определяются размеры операндов (8, 16, 32, 64 или 80 бит) – одно число, если у всех операндов один и тот же размер, несколько чисел, каждое из которых соответствует размеру одного из операндов, если операнды имеют разный размер. Так как после размера операнда указывается его тип, визуально эти значения разделены;

как было сказано выше, после размера указывается тип операнда:

i – непосредственное значение, b – регистр, содержащий адрес ячейки памяти;

если команда имеет различные операции для знаковых/ беззнаковых соответствующих инструкций, то после указания типа операнда (операндов) указывается знаковый тип операнда (операндов):

u – беззнаковый (unsigned);

для команд перехода после этого определяется тип перехода: abs – абсолютный переход, переход по адресу в памяти, rel –относительный переход, переход относительно текущей позиции;

затем через пробел указываются операнды - роль и тип (источник – приемник).

Источник обозначается через i (input), приемник через o (output), операнд одновременно являющийся приемником и источником через io. Для команд условных переходов у второго операнда стоит буква j – jump, что говорит о том, что этот операнд определяет;

для команд сдвига второй операнд с префиксов sh определяет сдвиг (shift). По аналогии с описанным выше типы операндов:

imm - непосредственное значение, brg - регистр, содержащий адрес ячейки памяти.

div64s_mr io_mem, i_reg – команда знакового деления 64 битных значений, где первый операнд – ячейка памяти, второй – регистр, при этом первый операнд является одновременно приемником и источником, а второй только источником.

Рассмотрим каждый из классов операций виртуальных машин подробнее.

2.2.17 Класс арифметических операций К арифметическим операциям относятся сложение, вычитание, умножение и деление.

Они могут быть разделены на две основные группы:

операции с целочисленными данными;

операции с вещественными данными.

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

Виртуальные машины различают следующие типы операндов.

Конкретное значение, известное на этапе компиляции — например, числовая константа или символ. Эти операнды называются непосредственными;

При этом если операнд-источник может быть любого из перечисленных типов, то операнд-приемник не может быть конкретным значением.

Примеры арифметических инструкций с операндами разных типов:

Реализуется набор инструкций с операндами следующих размеров: 8, 16, 24, 32, 64 и бит.

Примеры арифметических инструкций с разными размерами операндов:

В данных примерах размер регистров составляет соответственно 8 бит для первого примера, 16 для второго, 32 для третьего.

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

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

Все арифметические инструкции делятся на двухоперандные и трехоперандные.

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

Примеры двухоперандных инструкций:

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

Примеры трехоперандных арифметических инструкций:

Значения операндов могут быть типа int или float, и, соответственно для разных типов значений используются разные команды.

Примеры операций с вещественными операндами:

Таким образом, для команды сложения реализовано 600 различных команд:

4*3*2*5 =120 двухоперандных и 4*4*3*2*5 = 480 трехоперандных.

Аналогично, для остальных арифметических команд. С учетом различных команд для операций знакового и беззнакового деления, общее число арифметических команд составляет 3*103.

2.2.18 Класс логических операций Логические команды выполняют над операндами логические (побитовые) операции, то есть они рассматривают операнды не как единое число, а как набор отдельных битов. Этим они отличаются от арифметических команд. Логические инструкции выполняют следующие основные операции:

сложение по модулю 2 (исключающее ИЛИ);

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

Операция ИЛИ (OR) применяется для принудительной установки заданных битов (в качестве одного из операндов при этом используется код маски, в котором разряды, требующие установки в единицу, равны единице). Операция «Исключающее ИЛИ» (XOR) используется для инверсии заданных битов (в качестве одного из операндов при этом применяется код маски, в котором биты, подлежащие инверсии, установлены в единицу). Команды требуют двух входных операндов и формируют один выходной операнд.

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

Примеры логических операций виртуальных машин:

Таким образом, число логических команд превышает 103.

2.2.19 Класс операций сравнения Инструкции виртуальных машин для сравнения чисел являются аналогами ассемблерной инструкции cmp. После этих команд используются команды условного перехода, описанные в пункте 3.7.4. и, таким образом, используя последовательно cmp и команды условного перехода, организовываются условные операторы, циклы и так далее, как описано в пункте 3.7.4.

Операции сравнения имеют 2 операнда, первый является одновременно приемником и источником, второй только источником. Первый операнд сравнивается со вторым и результат сравнения записывается в первый операнд.

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

Тип операндов: в качестве первого операнда может выступать регистр, указатель на ячейку в памяти, или регистр, содержащий адрес ячейки памяти. В качестве второго конкретное значение, регистр, указатель на ячейку в памяти, или регистр, содержащий адрес ячейки памяти.

Размер операндов может быть одним из следующих: 8, 16, 32, 64 бит. При этом для операций сравнения размеры первого и второго операнда могут различаться.

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

Число операндов: они могут быть двухоперандные и трехоперандные:

в двухоперандных инструкциях первый операнд является одновременно приемником и источником, второй является источником, в трехоперандных – первый является приемником, второй и третий источником.

Примеры операций сравнения:

cmp32bu16bu [reg19], [reg13] cmp16rs16bs16bs reg8 [reg5], [reg6] Общее число команд сравнения превышает 103.

2.2.20 Класс control flow В императивном программировании control flow (порядок исполнения, порядок вычислений) — это способ упорядочения инструкций программы в процессе ее выполнения.

Инструкции, входящие в программу, могут исполняться как последовательно, одна за другой, так и одновременно, однократно или многократно. Последовательность исполнения инструкций может совпадать с последовательностью их расположения в записи программы или не совпадать, а также зависеть от текущего состояния вычислителя, исполняющего программу и от внешних событий, образовывая, таким образом, разнообразные порядки выполнения инструкций [19].

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

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

Отклонение от естественного для применяемого способа записи порядка называется переход. В этом случае после окончания выполнения текущей инструкции вычислитель переходит не к следующей в записи, а к некоторой другой, произвольно заданной инструкции [19]. При безусловном переходе инструкция перехода выбирается без учета состояния вычислителя, а при условном переходе выбирается в зависимости от состояния вычислителя путём проверки условия.

Команды перехода виртуальных машин будут иметь тот же принцип работы, что и инструкции x86. Если в коде встречается инструкция, меняющая порядок выполнения, то осуществляется переход на указанную область памяти и с неё продолжается выполнение программы. Все команды перехода делятся на команды перехода с возвратом и без возврата.

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

Команды переходов делятся на две группы:

команды безусловных переходов;

команды условных переходов.

1.1. Команды безусловных переходов вызывают переход в новый адрес независимо ни от чего. Они могут вызывать переход на указанную величину смещения (вперед или назад) или же на указанный адрес памяти. В многообразии инструкций виртуальных машин инструкции безусловного перехода делятся на два класса: инструкции относительного перехода (на величину смещения) и абсолютного перехода (на указанный адрес памяти).

Величина смещения или новое значение адреса указываются в качестве единственного входного операнда. Этот операнд всегда 32 битный, что соответствует размеру поля перехода Примеры:

jmp_rel -5 – относительный переход jmp_abs [reg3] – переход по адресу, находящемуся в reg 1.2. Команды условных переходов вызывают переход при выполнении заданных условий. Эти команды имеют два входных операнда: значение первого операнда выступает в качестве условия, в качестве второго операнда выступает величина смещения или новое значение адреса. Таким образом, команды условного перехода так же делятся на команды относительного и абсолютного перехода. Несколько примеров команд условных переходов:

переход, если больше или равно нулю;

переход, если меньше или равно нулю.

Кроме того, многообразие инструкций условного перехода определяется изменением следующих параметров:

размер первого операнда: могут быть использованы операнды следующих размеров 8, 16, 32, 64, 80. При этом второй операнд всегда 32 битный;

тип операндов: операнды могут быть регистрами, адресами ячеек памяти или непосредственными значениями, регистрами, содержащими адрес ячейки памяти;

первый операнд может быть знаковый или беззнаковый.

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

Примеры команд условных переходов:

Таким образом, команд условного перехода более 1.5*103.

2. Команды переходов с дальнейшим возвратом в точку, из которой был произведен переход, применяются для выполнения подпрограмм, то есть вспомогательных программ. Эти команды называются также командами вызова подпрограмм (аналог ассемблерной команды CALL). Использование подпрограмм позволяет упростить структуру основной программы, сделать ее более логичной, гибкой, легкой для написания и отладки.

Все команды переходов с возвратом предполагают безусловный переход. При этом они требуют одного входного операнда, который может указывать как абсолютное значение нового адреса, так и смещение, складываемое с текущим значением адреса.

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

2.2.21 Класс операций сдвига Команды сдвигов позволяют побитно сдвигать значение операнда вправо (в сторону младших разрядов) или влево (в сторону старших разрядов). Циклические сдвиги позволяют сдвигать биты значения операнда по кругу (по часовой стрелке при сдвиге вправо или против часовой стрелки при сдвиге влево) [20]. Эти команды имеют два операнда: в первом находится значение, сдвиг которого мы хотим осуществить, во втором - величина сдвига.

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

В качестве первого операнда может выступать регистр, указатель на ячейку в памяти, или регистр, содержащий указатель на ячейку памяти. В качестве второго - конкретное значение, регистр, указатель на ячейку в памяти, или регистр, содержащий адрес ячейки памяти.

Размер операндов Реализуется набор инструкций с операндами следующих размеров: 8, 16, 24, 32, 64 и бит.

Число операндов В двухоперандных инструкциях – первый операнд является одновременно приемником и источником, второй является источником; в трехоперандных – первый является приемником, второй и третий источником.

Примеры операций сдвига:

Таким образом, число команд сдвигов превышает 1000.

2.2.22 Класс операций для работы со стеком Стек - это способ хранения данных. В языке виртуальных машин можно выделить группы команд работы со стеком: команды, которые кладут новую порцию данных на верхушку стека (STORE), и команды которые получают данные с вершины стека (LOAD).

Использование стека позволяет сохранять данные в памяти, не заботясь об их абсолютных адресах.

Пример вызова этих функций: команда вызова функции CALL32 func записывает в стек адрес следующей за ней команды, а команда возврата RET достает его из стека.

Формально стек ограничен лишь протяженностью адресного пространства. Направление роста стека: от больших адресов – к меньшим. Еще говорят, что стек растет снизу вверх.

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

виртуальные машины могут класть в стек или брать из стека как регистры, так и переменные.

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

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

размер регистра (первый операнд) – он может быть одним из следующих: 8, 16, 32, величина переменной, хранящей смещение (второй операнд) – он может быть 8, Примеры инструкций работы со стеком:

2.2.23 Класс операций пересылки данных Инструкции виртуальных машин, осуществляющие пересылку данных, являются аналогом ассемблерной команды mov за тем исключением, что машины архитектуры x86 не поддерживают адресации типа память – память; одно из обрабатываемых чисел обязательно должно находиться в регистре или представлять собой непосредственное значение.

Генерируемые виртуальные машины это жесткое правило соблюдать не будут.

Арифметические операции над данными в памяти будут разрешены. Таким образом, для выполнения арифметической операции данные не надо будет предварительно класть в стек и, таким образом, мы усложним проблему анализа языка виртуальной машины.

Код на языке ассемблер:

Код на языке виртуальной машины:

Команды пересылки данных не требуют выполнения никаких операций над операндами.

Операнды просто пересылаются (точнее, копируются) из источника в приемник.

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

В качестве первого операнда (приемника) может выступать регистр, указатель на ячейку в памяти, или регистр, содержащий адрес ячейки памяти. В качестве второго (источника)- конкретное значение, регистр, указатель на ячейку в памяти, или регистр, содержащий адрес ячейки памяти.

Размер операндов может быть одним из следующих: 8, 16, 32, 64, 80 бит.

2.2.24 Получение полного набора инструкций У разных процессоров системы команд существенно различаются по количеству, составу, а так же семантикой. Если рассматривать количество команд, то у процессора 8086 — 133 команды. У современных мощных процессоров количество команд достигает нескольких сотен [21].

Как было сказано в разделе 2, имея исходный алгоритм, можно построить виртуальную машину, содержащую не полный по Тьюрингу набор команд, а набор команд достаточный для выполнения данного алгоритма. Кроме того, набор инструкций генерируемых протектором явно избыточен. Из раздела 3 видно, что общее число команд, создаваемое генератором виртуальных машин, составляет около 8*103 команд. Этот набор включает множество одинаковых инструкций с различной семантикой, например, он содержит множества одинаковых инструкций, у которых отличается только размер операндов. Таким образом, если использовать весь набор этих инструкций, то защищенные файлы будут весить гораздо больше исходных, так как виртуальная машина записывается в защищенный исполняемый файл. Кроме того это предоставляет большое количество данных для анализа системы защиты злоумышленником. Поэтому для каждой виртуальной машины произвольным образом из всего многообразия выбирается функционально-полный набор из 200 команд, причем состав этого набора будет специфичный для каждого запуска генератора виртуальных машин. Число выбрано, как среднее число команд у современных процессоров.

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

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

Благодаря многообразию команд пересылки данных, одни типы операндов преобразуются к другим, и набор команд остается функционально-полным.

Кроме того, существуют различные инструкции, которые могут быть выражены друг через друга. К ним относятся логические инструкции, и инструкции сравнения, а так же инструкции циклического сдвига. Рассмотрим их подробнее.

2.2.25 Полнота подмножеств инструкций Рассмотрим следующие множества логических инструкций:

множества логических инструкций, множества инструкций сравнения, множества «избыточных» инструкций.

2.2.26 Логические инструкции множества {,,, }.

Определение 4.1. Система булевых функций F называется полной, если формулами над этой системой можно задать любую булеву функцию из P.

Определение 4.2.

Функция fP сохраняет 0 (сохраняет 1),если f(0,0,…0)=0 ( f(1,1,…,1)=1 ). Класс всех функций, сохраняющих 0, обозначим через S0, а класс всех функций, сохраняющих 1, - через S1.

Функция fP называется самодвойственной, если для любого набора аргументов (1, 2, …,n) Bn выполняется равенство f(1, 2, …,n)=f(1, 2, …, n). Класс всех самодвойственных функций обозначим через S.

Функция fP называется линейной, если она может быть задана линейным многочленом Жегалкина вида 0+1X1+2X2+…+nXn, где i{0,1} при i=1..n. Класс всех линейных функций обозначим через L.

Функция fP называется монотонной, если для любых двух наборов аргументов (1, 2, …,n) Bn и (1, 2, …,n) Bn таких, что для всех j[1,n] 1 n имеет место неравенство f(1, 2, …,n)f(1, 2, …,n). Класс всех монотонных функций обозначим через Теорема 4.1 (Теорема Поста о полноте): Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов S0, S1, S, M и L. Другими словами, система булевых функций F является полной тогда и только тогда, когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция [22].

Рассмотрим таблицу истинности (табл. 4.1) для логических инструкций и сделаем вывод о соответствии между булевскими функциями, входящими в набор инструкций виртуальных машин и классами Поста.

На основании табл. 5.1 построим табл. 5.2 принадлежности булевских функций классам Поста. Знаком «#» отмечается не принадлежность функции классу, «+» - принадлежность.

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

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

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

В этом случае, команда OR выражается двумя способами:

2.2.27 Инструкции сравнения Аналогично с логическими инструкциями, инструкции сравнения так же могут быть выражены друг через друга. Рассмотрим полные наборы операций сравнения.

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

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

2.2.28 «Избыточные» инструкции К этому классу инструкций относятся инструкции циклического сдвига и пара инструкций (add, sub).

Циклический сдвиг Действительно, инструкции циклического сдвига выражаются через инструкции правого и левого сдвига.

Так циклический сдвиг влево на s бит может быть выражен следующим образом:

И циклический сдвиг вправо на s бит следующим образом:

return result;

Примечание: блок, который начинается с входа в функцию, обозначается %0.

define i32 @factorial(i32 %n) %i.start = sub i32 %n, br label %LoopEntry LoopEntry:

%result = phi i32 [%n, %0], [%result.next, %LoopBody] %i = phi i32 [%i.start, %0], [%i.next, %LoopBody] %cond = icmp sle i32 %i, br i1 %cond, label %Exit, label %LoopBody LoopBody:

%result.next = mul i32 %result, %i %i.next = sub i32 %i, br label %LoopEntry Exit:

ret i32 %result LLVM также требует, чтобы все phi-инструкции шли в начале блока и до них не было никаких других инструкций. Хотя SSA-форма позволяет производить много полезных трансформаций, непосредственно генерировать её из кода на императивном языке затруднительно, хотя есть хорошо известные алгоритмы преобразования в SSA. При написании компилятора на основе LLVM нет никакой необходимости заниматься этим, потому что система умеет генерировать SSA самостоятельно.

SSA представление, в основе которого лежит разбиение кода на BasicBlock, очень удобно для реализации обфускации на базе сетей Петри. Так как внутри BasicBlock нет переходов, то выполнение сети Петри можно контролировать. То есть все инструкции, выполняющие суммирование сети, гарантированно будет выполнены, и кроме того всегда будет соблюден порядок их выполнения. При наличии терминаторов это немаловажное условие могло быть нарушено, что привело бы к некорректной работе сети: целевые значения не были бы получены в фиксированных метках. [27] 2.3.8 LLVM Pass Manager LLVM Pass фреймворк является важной частью всей системы LLVM. Pass Manager выполняет преобразования и оптимизации, которые и составляют компилятор. Он также выполняет анализ результата, который используется для преобразований.

Все LLVM оптимизации являются наследниками класса Pass, содержащий набор виртуальных методов, которые реализуют наследники. В зависимости от того, какая задача решается с помощью LLVM оптимизаций, необходимо наследоваться от одного из следующих классов: ModulePass, CallGraphSCCPass, FunctionPass, LoopPass, RegionPass, или BasicBlockPass класс. Они дают системе больше информации о том, что конкретно делает реализуемая LLVM оптимизация и как она может сочетаться с другими оптимизациями.

При разработке нового класса оптимизации необходимо четко определить, от какого из возможных LLVM Pass классов надо наследоваться. При выборе надо руководствоваться правилом, что лучше выбирать наиболее специфичный класс, это дает LLVM больше необходимой информации, что позволяет компилятору работать быстрее. Ниже приведены классы, которые использовались в данной работе. Подробную информацию о всевозможных классах оптимизации можно получить в [29].

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

Не изменять функцию, кроме той, которая в данный момент обрабатывается;

Не добавлять и не удалять функции из текущего модуля;

Не добавлять и не удалять глобальные переменные из текущего модуля;

Не хранить текущее состояние между вызовами функции runOnFunction (включая глобальные переменные).

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

virtual bool doInitialization(Module &M);

Этот метод позволяет делать многое из того, что запрещено наследникам FunctionPass:

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

Хороший пример, как должен использоваться этот метод, это LowerAllocations оптимизация. Эта оптимизация преобразует инструкции malloc() и free() в платформозависимые инструкции. В этом случае метод doIninitialize получает ссылку на функции malloc() и free(), которые и необходимы, добавляя в модуль прототипы, если это необходимо.

virtual bool runOnFunction(Function &F) = 0;

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

virtual bool doFinalization(Module &M);

Данный метод редко используется, он вызывается, когда LLVM Pass фреймворк закончил вызов метода runOnFunction для всех функций в программе, которая компилируется.

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

Модификация BasicBlock вне текущего;

Сохранение текущего состояние между вызовами функции runOnFunction.

BasicBlockPasses полезен для обычной локальной оптимизации. Наследники могут перегружать те же функции, что и наследники FunctionPass.

virtual bool doInitialization(Function &F);

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

virtual bool runOnBasicBlock(BasicBlock &BB) = 0;

Этот метод выполняет основную работу BasicBlockPass: не позволяет модифицировать BasicBlock вне того, который в данный момент обрабатывается. Возвращает значение истина, если текущий BasicBlock был модифицирован.

virtual bool doFinalization(Function &F);

Данный метод редко используется, он вызывается, когда LLVM Pass фреймворк закончил вызов метода runOnFunction для всех функций в программе, которая компилируется.

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

BOOL) Типом шаблона и первым аргументом является специальное имя, которое используется командной строкой для того чтобы добавить текущую оптимизацию к программе. Вторым аргументом является название оптимизации, которое далее используется для именования выходных данных при опциях –help и --debug-pass. Последние два аргумента описывают поведение оптимизации: если оптимизация не модифицирует граф потока управления (control flow graph, CFG), третий параметр устанавливается в значение истина, если текущая оптимизация анализирует работу самой оптимизации, то значением четвертого аргумента также является истина.

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

PassManager берет список всех оптимизаций, проверяет, выполнены ли требования для каждой оптимизации, и далее выполняет их в том порядке, который приводит к наиболее эффективному результату. Весь инструментарий LLVM, который работает с оптимизациями, запускает их, используя PassManager.

Для уменьшения времени выполнения оптимизаций PassManager следует двум важным принципам.

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

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

2.3.9 Защита интрепретатора многоуровневой виртуальной машины при помощи сети Петри с возможность встраивания стандартный процесс компиляции.

2.3.10 Генерация сети Петри Класс Petri, который генерирует сеть Петри для защиты кода, проектируется как наследник класса FunctionPass. То есть в данном случае оптимизация применяется к каждой функции. В классе реализован метод runOnFunction, который в качестве параметра принимает обрабатываемую функцию.