Метод защиты программных средств на основе запутывающих преобразований

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

2.2.2 Преобразования структур данных

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

34 вании с другими методами запутывания, т.к. учитывая свойства уязвимости ПС (отсутствие независимости функционирования ПС на уровне операцион­ной системы и открытость семантики обращений к операционной системе) легко определить зависимость выполнения ПС по данным.

2.2.3 Преобразования потока управления

Преобразования потока управления изменяют граф потока управления одной функции. Они могут приводить к созданию в программе новых функ­ций. В работе [71, 86] приведено описание преобразований потока управле­ния.

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

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

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

Непрозрачные предикаты (opaque predicates). Данные преобразования основываются на введении непрозрачных переменных и предикатов. Слож­ность анализа непрозрачных предикатов и переменных обеспечивает устой­чивость таких преобразований к анализу.

35 Определение. Переменная v является непрозрачной, если существует свойство Р относительно этой переменной, которое априори известно в мо­мент запутывания программы, но трудно устанавливаемо после того, как за­путывание завершено. То есть, предикат Н называется непрозрачным, если его значение известно только в процессе запутывания программы, но после того, как запутывание завершено определение его значения становится труд­ным.

Обозначим непрозрачный предикат, который всегда имеет значение «ложь» (false) как H{f), а предикат, который всегда имеет значение «исти­на» (true), как H{t). Тогда непрозрачный предикат H(t,f) может принимать любое из этих двух значений, и в момент запутывания текущее значение не известно.

Непрозрачные предикаты могут быть:

-         локальными - вычисления содержаться внутри одиночного выра­жения;

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

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

В работах [84, 87, 101] предложены методы построения непрозрачных предикатов и переменных, основанные на "встраивании" в программу вычис­лительно сложных задач.

Возможные способы введения непрозрачных предикатов и непрозрач­ных выражений:

-         использование разных способов доступа к элементам массива;

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

-         конструирование булевых выражений специального вида;

-         построение сложных булевых выражений с помощью эквивалент­ных преобразований;

36 -  использование комбинаторных тождеств.

Трансформация фрагмента кода программы с помощью непрозрачных предикатов приведена на рис. 2.2.

На рис. 2.2(a) блок А программы Pr, разбит на два независимых блока АХ,А2, которые соединены по средством непрозрачного предиката возвра­щающего всегда значение «истина» Н(t). В результате трансформации тако­го рода возникает представление того, что блок А2 не всегда выполняется, поэтому для того чтобы определить условия выполнения блока А2, необхо­димо узнать значение, которое возвращает используемый непрозрачный пре­дикат H{t).

На рис. 2.2(6) помимо блока А2 используется еще один блок, над кото­рым был произведен процесс запутывания блок А2 , то есть блок А2 и А2 имеют различный код, но выполняют одинаковые функции, следовательно, можно утверждать, что А2 = А2 , и поэтому неважно какой из этих блоков бу­дет выполнен в процессе работы программы. Из этого следует, что для со­единения блока Ах с А2 и А2 эффективно будет использовать непрозрачный предикат, который может возвратить любое из значений, а именно «истина» или «ложь» H(t,f).

На рис. 2.2(b) используется новый блок Аъ, который содержит произ­вольный набор, каких либо операций (недостижимый код), так как сами бло­ки А{ и А^ соединены по средством непрозрачного предиката возвращающе­го всегда значение «ложь» H{f) - это затрудняет анализ.

37

A2=\T              A2*A3

а)              б)              в)

Рисунок 2.2 - Способы внесения непрозрачных предикатов

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

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

Внесение недостижимого кода (adding unreachable code) [71, 86]. Если в программу внесены непрозрачные предикаты видов #(/) или H(t), ветки

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

38 быть похожи на действительно выполняемый код. Поскольку недостижимый код никогда не выполняется, данное преобразование влияет только на размер запутанной программы, но не на скорость её выполнения. Общая задача об­наружения недостижимого кода алгоритмически неразрешима. Это значит, что для выявления недостижимого кода должны применяться методы, основанные на статистическом анализе программы.

Внесение мёртвого кода (adding dead code). В отличие от недостижимого кода, мёртвый код в программе выполняется, но его выполнение никак не влияет на результат работы программы. При внесении мёртвого кода обяза­тельно должно выполняться условие, что вставляемый фрагмент не может влиять на код, который вычисляет значение функции. Это значит, что мёрт­вый код не может иметь побочного эффекта, даже в виде модификации гло­бальных переменных, не может изменять окружение работающей програм­мы, не может выполнять никаких операций, которые могут вызвать исклю­чение в работе программы.

Внесение избыточного кода (adding redundant code). Избыточный код, в отличие от мёртвого кода выполняется, и результат его выполнения исполь­зуется в дальнейшем в программе, но такой код можно упростить или совсем удалить, так как вычисляется либо константное значение, либо значение, уже вычисленное ранее. Для внесения избыточного кода можно использовать ал­гебраические преобразования выражений исходной программы или введение в программу математических тождеств.

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

Преобразование сводимого графа потока управления к несводимому (transforming reducible to non-reducible flow graph). Когда целевой язык (байт-код или машинный язык) более выразителен, чем исходный, можно исполь­зовать преобразования, "противоречащие" структуре исходного языка. В ре­зультате таких преобразований получаются последовательности инструкций

39 целевого языка, не соответствующие ни одной из конструкций исходного языка.

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

Устранение библиотечных вызовов (eliminating library calls). Большинст­во программ используют стандартные библиотеки. Поскольку семантика библиотечных функций хорошо известна, такие вызовы могут дать полезную информацию при обратной инженерии программ.

Переплетение функции (function interleaving). Данное преобразование объединяет две или более функций в одну функцию. Списки параметров ис­ходных функций объединяются, и к ним добавляется ещё один параметр, ко­торый позволяет определить, какая функция в действительности выполняет­ся.

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

Развёртка циклов (loop unrolling). Преобразование заключается в том, что тело цикла размножается два или более раз, условие выхода из цикла и оператор приращения счётчика соответствующим образом модифицируются. Если количество повторений цикла известно в момент компиляции, то цикл может быть развёрнут полностью.

40

Разложение циклов (loop fission). Разложение циклов состоит в том, что цикл со сложным телом разбивается на несколько отдельных циклов с про­стыми телами и с тем же пространством интегрирования.

Реструктуризация графа потока управления. Структура графа потока управления, наличие характерных шаблонов для циклов, условных операто­ров и т. д. предоставляет возможность исследования структуры программы при ее анализе. Например, по повторяющимся конструкциям графа потока управления можно легко установить, что над функцией было выполнено пре­образование развёртки циклов, а далее можно проанализировать развёрнутые итерации цикла для выделения индуктивных переменных и свёртки цикла. В качестве меры противодействия может быть применено такое преобразова­ние графа потока управления, которое приводит граф к однородному (плос­кому) виду [71, 84, 102]. Операторы передачи управления на следующие за ними базовые блоки, расположенные на концах базовых блоков, заменяются на операторы передачи управления на специально созданный базовый блок диспетчера, который по предыдущему базовому блоку и управляющим пере­менным вычисляет следующий блок и передаёт на него управление. Техни­чески это может быть сделано перенумерованием всех базовых блоков и вве­дением новой переменной.

В работах [100-102] предлагается метод запутывания, и описывается его реализация в инструменте для запутывания программ на языке Си.

Описание процесса запутывания каждой такой процедуры состоит из трех этапов:

-      создание графа потока управления этой процедуры множеством блоков и множеством связей соединяющих их, после чего граф разбивается, пу­тем замены циклических конструкций в нем на конструкции типа (усло­вие) if  goto, пример для программы на языке Си приведен на рис. 2.3;

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

41

РОССИЙСКАЯ

ГО СУД,Л; "Л П ЕЯ Wf.'-

- приведение графа к однородному (плоскому) виду (рис. 2.4).

Рассмотренный вариант алгоритма запутывания не устойчив к статиче­скому анализу, так как определить следующий выполняемый блок, нетрудно (в приведенном примере он будет храниться в переменной swVar). Поэтому, для того чтобы затруднить статический анализ, номера базовых блоков по­мещаются в массив (например, @gg), каждый элемент которого индексирует­ся несколькими разными способами, например содержащий помимо номеров блоков, не нужную информацию, в результате запись $swVar=S6, можно заменить на $swVar=$gg [$gg [1] +$gg [3] ]. Таким образом, для статиче­ского прослеживания порядка выполнения базовых блоков необходимо про­вести анализ указателей.

ту $а=1; ту $Ь=2;

while ($а<10) {

$b=$a+$b;

if ($b>10)

{b—;}

a++;

}

return $b;

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

Исходный текст про-
              граммы             

Рисунок 2.3 - Разбитый граф потока управления

42