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

Рисунок 2.4 - Вид графа приведенного к плоскому виду В работе [84] предлагается метод запутывания, основанный на следую­щих запутывающих преобразованиях: каждый базовый блок запутываемой функции разбивается на более мелкие части и клонируется один или не­сколько раз, В каждом фрагменте базового блока переменные локализуются, и для связывания базовых блоков создаются специальные связующие базо­вые блоки. Далее в каждый фрагмент вводится мёртвый код. Источником мёртвого кода может быть, например, фрагмент другого базового блока той же самой функции или фрагмент базового блока другой функции. Далее из таких комбинированных фрагментов собирается новая функция, в которой для переключения между базовыми блоками используется диспетчер. Дис­петчер принимает в качестве параметров номер предыдущего базового блока и набор булевых переменных, которые используются в базовых блоках для вычисления условий перехода, и вычисляет номер следующего блока. При этом следующий блок может выбираться из нескольких эквивалентных бло­ков, полученных в результате клонирования. Выражая функцию перехода в виде булевой формулы, можно добиться того, что задача статического анали­за диспетчера станет не решаемой. Работа [84] описывает алгоритм запуты­вания, но реализация этого алгоритма в какой-либо системе автору не из­вестна.

43

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

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

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

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

44

2.3 Классификация методов анализа программ

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

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

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

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

Методы анализа программ могут быть разделены на 4 группы [71]:

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

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

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

-         динамические - основаны на использовании информации, полученной в результате «наблюдения» за работой программы на конкретных вход­ных данных;

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

2.3.1 Методы статического анализа

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

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

Рассмотрим возможные методы статического анализа [71, 89, 95, 99].

Статический анализ алиасов (alias analysis) необходим в языках, в кото­рых несколько имён могут быть использованы для доступа к одной и той же области памяти. В результате анализа алиасов каждому оператору, выпол­няющему косвенную запись в память или косвенное чтение из памяти, ста-

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

Такой анализ является ключевым для точного анализа свойств програм­мы.

Статическое устранение мёртвого кода (dead-code elimination) имеет це­лью выявить в программе код, который выполняется, но не оказывает влия­ние на результат работы программы.

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

Статическое продвижение констант и копий (constant and copy propagation) заключается в продвижении константных выражений как можно дальше по тексту функции. Если выражение использует только значения пе­ременных, которые в данной точке программы заведомо содержат одно из­вестное значение, такое выражение может быть вычислено. Если в выраже­нии используется переменная, которая в данной точке программы заведомо является копией какой-то другой переменной, в выражение может быть под­ставлена исходная переменная.

Статический анализ доменов (domain analysis) является расширением ал­горитма продвижения констант. Он позволяет определить множество значе­ний, которые может принимать данная переменная в данной точке програм­мы, если это множество не велико.

Статический слайсинг (slicing) - это построение "сокращённой" про­граммы, из которой удалён весь код, не влияющий на вычисление заданной переменной в заданной точке, но при этом программа остаётся синтаксиче­ски и семантически корректной и может быть выполнена.

47

2.3.2 Методы статистического и динамического анализа

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

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

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

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

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

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

Динамическое выделение мёртвого кода позволяет выявить инструк­ции программы, которые выполнялись при данном запуске программы, но не влияли на результат работы программы. Если анализируется совокуп-

48 ность запусков программы на множестве наборов входных данных, можно говорить о статистическом выделении мёртвого кода.

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

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

2.4 Классификация способов запутывания к применяемым ме­тодам анализа и распутывания программ

Сопоставим методы запутывания, и методы анализа программ приве­денные в разделах 2.2 и 2.3.

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

49

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

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

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

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