Метод и средства защиты исполняемого программного кода от динамического и статического анализа

Определение 4.1. Система булевых функций F называется полной, если формулами над этой системой можно задать любую булеву функцию из Р . Определение 4.2. Функция feP сохраняет 0 (сохраняет 1),если f(0,0,...0)=0 ( f(l,l,...,l)=l ). Класс всех функций, сохраняющих 0, обозначим через So, а класс всех функций, сохраняющих 1, - через Si. Функция feP называется самодвойственной, если для любого набора аргументов (cri, сг2, ... ,<Уп) еВ^п выполняется равенство f(oi, ф, ... ,n)=-if(-ioi, -юъ, ... , -югп). Класс всех самодвойственных функций обозначим через S'. Функция feP называется линейной, если она может быть задана линейным многочленом Жегалкина вида (Хо+aiXi+(Х2Х2+...+(ХпХп, где a,e{0,l} при i=l..n. Класс всех линейных функций обозначим через L. Функция feP называется монотонной, если для любых двух наборов аргументов (ai, ф, ... ,Ф) eB^nn(pi, р2, ... ,рп) еВ" таких, что для всех/е[1,п] сп>рп имеет место неравенство /(ф, <У2, — ,n)^f(pi, Р2, ■■■ ,рп). Класс всех монотонных функций обозначим через М. Теорема 4.1 (Теорема Поста о полноте): Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов So, Si, S, М и L. Другими словами, система булевых функций F является полной тогда и только тогда, когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция [24]. Рассмотрим таблицу истинности (табл. 4.1) для логических инструкций и сделаем вывод о соответствии между булевскими функциями, входящими в набор инструкций виртуальных машин и классами Поста. Таблица 5.1 Таблица истинности стандартных булевских функций X	У	xvy	хлу	хФу	—iX	-■У	xvy	хлу
хФу
0	0	0	0	0	1	1	0	0	0
0	1	1	0	1	1	0	0	1	1
1	0	1	0	1	0	1	0	1	1
1	1	1	1	0	0	0	1	1	1

49

На основании табл. 5.1 построим табл. 5.2 принадлежности булевских функций классам Поста. Знаком «#» отмечается не принадлежность функции классу, «+» - принадлежность. Таблица 5.2 Булевские функции и классы Поста Функции	Классы булевых функций
	So	Si	5	L	м
xvy	+	+	#	#	+
хлу	+	+	#	#	+
х®у	+	#	#	+	#
—iX	#	#	+	+	#
1	#	+	#	+	+
0	+	#	#	+	+

Таким образом, функционально полными являются следующие наборы инструкций виртуальных машин: OR, AND, XOR, NOT Это функционально полный набор логических операций, включающий все возможные логические инструкции виртуальных машин протектора. OR, NOT Выразим остальные инструкции, через инструкции OR и NOT AND:	х л у = xvy - правило де Моргана.
XOR:	х ф у=х у v xy=xvyvyvx

AND, NOT Выразим остальные инструкции, через инструкции AND и NOT OR:	X V у = хлу
XOR:	X Ф y=xyvxy =1"у ЛХр

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

50

5. 
   AND, NOT, XOR
   

В этом случае, команда OR выражается двумя способами:
OR: х v у = х л у
OR: xvу = (хлу) Ф(хФу)

6. 
   XOR, AND, OR
   

NOT: -пх = х Ф 1

7. 
   XOR, AND
   

NOT: —>x ⁼ x Ф 1
OR: x vy = ((x© 1)л(уФ 1)Ф 1

8. 
   XOR, OR
   

NOT: -ix = x Ф 1
AND: x л у = ((x Ф 1) v (у Ф 1)) Ф 1

14. 
    Инструкции сравнения
    

Аналогично с логическими инструкциями, инструкции сравнения так же могут быть выражены друг через друга. Рассмотрим полные наборы операций сравнения.
1)
Выразим для этого набора все остальные операции сравнения. Для остальных наборов операции сравнения, не вошедшие в набор, выражаются аналогично.
х > У ~ ->(х<у)л ->(х=у)


X >= У ~ ->(х<у)
X <= У * (xX != У ~ Чх<у)л —,(х⁼у)

2. 
   (»<”“ = ”)
   

3)

2. 
   (“!=”,“>”)
   
3. 
   (“ != ”, “ < ”)
   
4. 
   (“>=”,“ = ”)
   
5. 
   (“>=”,“ = ”)
   
6. 
   (“>”“ = ”)
   

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


51

14. 
    «Избыточные» инструкции
    

К этому классу инструкций относятся инструкции циклического сдвига и пара инструкций (add, sub).
Циклический сдвиг
Действительно, инструкции циклического сдвига выражаются через инструкции правого и левого сдвига.
Так циклический сдвиг влево на s бит может быть выражен следующим образом: int roti(int a, int s) {
return (a<>sizeof(a)-s);
}
И циклический сдвиг вправо на s бит следующим образом:
int rotr(int a, int s) {
return (a>>s) | (a<< sizeof(a)-s);
}
Пара инструкций add/sub
Пара сложение/ вычитание так же является избыточной, так как эти команды выражаются друг через друга.
х + у = х - (-у)
X - у = X + (-у)

14. 
    Набор инструкций конкретной виртуальной машины
    

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


52




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

14. 
    Повышение скрытности алгоритма с использованием теории скрытности
    

За счет использования виртуализированного и исполняемого ПИОК кода возможно общее повышение скрытности алгоритма. Если рассматривать алгоритм обфускации в рамках теории скрытности то можно рассматривать полезные действия, совершаемые алгоритмом, как симптомы состояний [15] инструкций машинного кода, которые подвергаются обфускации.
Таким образом при замене кода на обфусцированный происходит добавление новых симптомов, скрывающих целевые.
Известно, что потенциальная энтропийная скрытность множества симптомов вычисляется
В А
по формуле S(Y) - -^PCyJlogj Р(у_}), где Р(у_}) = Р_} = ^_lP(x_l)P(y_J /х,), определяется по _У=1 ,=1
формуле полной вероятности, где значения P(yj /х_г) = /)/, - условная вероятность симптома у_} при состоянии объекта х,. В нашем случае симптомами является информация доступная


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


выбирается из имеющегося арсенала с равными вероятностями p_t = 1/А. При этом условии


потенциальная арсенальная скрытность (А-скрытность) для виртуальной машины определяется выражением^ = - log ₂ (1/^4) = log₂ А, где А — общее число возможных команд виртуальной машины.
Групповая же скрытность виртуальной машины тогда будет вычисляться из соотношения


S(m) = A-log₂ A-(A-m)-log₂(A-m)—wlog₂ m + — log₂
, L J


—— — , A - общее
2тт(л — m)m


53




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

• 
  Медленной кодогенерации кода виртуальной машины
  
• 
  Раскрытию всего арсенала команд при исследовании защищенного кода.
  

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

1. 
   Необходимо создавать генераторы виртуальных машин с максимально большим числом команд.
   
2. 
   Для наилучшей защиты одной виртуальной машины, число команд должно выбираться равным половине общего числа команд.
   
3. 
   В случае, если при помощи одного набора команд защищается множество алгоритмов, необходимо в каждом наборе использовать возможно меньшее число команд.