Содержание к диссертации
Введение
1 Маскирующие преобразования программ 11
1.1 Задача маскировки программ 11
1.2 Используемая терминология 14
1.3 Метрики сложности программ 17
1.4 Расстояние между программами 19
1.5 Определение устойчивости маскирующего преобразования 22
1.6 Методы анализа и трансформации программ 23
1.7 Маскирующие преобразования программ 25
1.7.1 Текстуальные маскирующие преобразования 25
1.7.2 Преобразования управляющей структуры 26
1.7.3 Преобразования реструктуризации всей программы 27
1.7.4 Преобразования маскировки одной процедуры 31
1.7.5 Непрозрачные предикаты 42
1.7.6 Трансформация графа потока управления («диспетчер») 46
1.7.7 Сравнение свойств разных маскирующих преобразований 49
1.8 Использование маскирующих преобразований программ 51
2 Анализ маскирующих преобразований программ 52
2.1 Анализ маскирующих преобразований 52
2.1.1 Анализ лексических преобразований 53
2.1.2 Анализ маскирующих преобразований графа потока управления . 54
2.2 Классификация маскирующих преобразований программ 65
2.3 Применение методов демаскировки 66
2.3.1 Анализ замаскированных вручную программ 66
2.3.2 Анализ программ, замаскированных автоматически 67
2.4 Выводы 70
3 Новый метод маскировки программ 72
3.1 Общее описание метода маскировки 73
3.1.1 Увеличение размера графа потока управления 74
3.1.2 Разрушение структурности графа потока управления 76
3.1.3 Генерация несущественного кода 77
3.1.4 Перемешивание программ 78
3.2 Реализация метода маскировки 78
3.2.1 Увеличение графа потока управления процедуры 80
3.2.2 Преобразования разрушения структурности 88
3.2.3 Генерация несущественного кода 92
3.2.4 «Зацепление» холостой и основной программы 95
3.3 Устойчивость метода 98
3.3.1 Формальная устойчивость метода 98
3.3.2 Неформальная устойчивость метода 105
3.4 Пример применения метода 106
3.5 Выводы 115
4 Интегрированная среда Poirot 116
4.1 Архитектура системы 116
4.2 Промежуточное представление 118
4.3 Интерфейс пользователя 119
4.3.1 Меню Analyze 121
4.3.2 Меню Optimize 122
4.3.3 Меню Transform 123
4.3.4 Меню Obfuscate 123
4.3.5 Меню Generate 124
4.3.6 Меню Execute 124
4.3.7 Меню Visualize 125
4.3.8 Меню Traces 125
4.3.9 Меню Options 126
Заключение 127
Список литературы 128
- Преобразования реструктуризации всей программы
- Анализ маскирующих преобразований графа потока управления
- Увеличение графа потока управления процедуры
- «Зацепление» холостой и основной программы
Введение к работе
В настоящее время особенную актуальность приобрели задачи, связанные с защитой информации. Компьютерные программы как один из видов информации также нуждаются в защите. Проблематика защиты программ включает в себя как защиту от копирования и (или) нелицензионного использования, так и защиту от обратной инженерии и несанкционированной модификации.
В диссертации рассматривается проблема защиты программ от обратной инженерии, проводимой с целью модификации и/или включения фрагментов защищаемой программы во вновь разрабатываемый программный код. Защита в данном случае состоит в том, чтобы затруднить понимание деталей реализации компонент большой программной системы, сделав его настолько дорогим, чтобы дешевле было разработать оригинальное программное обеспечение. Одним из способов такой защиты является маскировка программ, заключающаяся в применении к исходному тексту программы цепочки маскирующих преобразований, то есть преобразований, сохраняющих реализуемую программой функцию (являющихся функционально эквивалентными), но затрудняющих понимание этой функции.
Необходимость разработки средств защиты программ от обратной инженерии диктуется многочисленными примерами несанкционированного использования чужого кода при разработке больших программных систем, аналогичных уже имеющимся на рынке. Среди современных систем программирования уже имеются системы, поддерживающие различные методы маскировки программ. Рассмотрение реализованных методов маскировки приводит к следующим наблюдениям.
Цепочки маскирующих преобразований, предлагаемые тем или иным методом, могут приводить к увеличению синтаксической и временной характеристик исходной программы. Крайне желательным является решение фиксировать заранее границы допустимых их увеличений и генерировать только такие цепочки, называя их допустимыми, для которых характеристики замаскированной программы не выходят за установленные границы.
Напрашивается и введение качественной характеристики самого метода маскировки. Подходящей, на наш взгляд, может быть характеристика, построенная на следующих соображениях. Замаскированная программа подвергается атаке демаскирующих преобразований, являющихся тоже функционально эквивалентными и стремящихся восстановить исходный вид программы. Отбросим как маловероятные демаскирующие преобразования, основанные на анализе программ, проводимом вручную. Тогда остаются оптимизационные преобразования, опирающиеся на алгоритмы автоматического анализа программ. Ограничившись некоторым набором таких оптимизационных преобразований и используемых ими алгоритмов анализа программ, можно говорить об устойчивости метода маскировки по отношению к данному набору демаскирующих преобразований. Для этого вводится понятие расстояния между функционально эквивалентными программами, и требуется, чтобы расстояние между исходной программой и программой, полученной действием произвольной цепочки оптимизационных преобразований из фиксированного набора на замаскированную программу, было не меньше заданной пороговой величины, называемой порогом устойчивости.
Цель исследования. Основной задачей диссертационной работы является разработка нового метода маскировки программ, удовлетворяющего следующим требованиям:
Исходная и замаскированная программа записаны на языке Си [8].
В методе применяются цепочки маскирующих преобразований, элементы которых берутся из некоторого заранее зафиксированного множества параметризированных маскирующих преобразований.
Все цепочки таких преобразований порождаются автоматически поддерживающими метод инструментальными средствами и являются допустимыми по своим характеристикам.
Метод маскировки устойчив относительно современных методов статического и полустатического анализа программ, развитых для языка Си.
Необходимым условием достижения цели исследования является разработка подходящей инструментальной системы и глубокий анализ применяемых на практике методов маскировки программ. Такой анализ должен выявить практически разумные величины всех ограничений, а именно: на границы допустимых увеличений характеристик маскируемой программы, на сложность реализации демаскирующих преобразований и на порог устойчивости.
Актуальность темы. Необходимость разработки средств защиты программ от обратной инженерии подтверждается следующими наблюдениями. Во-первых, для обеспечения переносимости программ на разные платформы в ряде случаев они распространяются в исходных кодах на языке высокого уровня. Например, система статического анализа программ на Си и Си++[15] FlexeLint [42] распространяется в замаскированных исходных файлах. Во-вторых, широко распространены языки программирования, такие как Java [2], в которых «исполняемой» формой программы является не машинный код для некоторого типа процессоров, а машинно-нейтральное представление. Задача декомпиляции программы из такого представления обратно в программу на языке Java значительно проще, чем декомпиляция из машинного кода, и успешно решена [71].
Основные результаты работы. В диссертации получены следующие основные результаты:
Предложен новый подход к построению методов маскировки программ, включающий такую характеристику метода, как его устойчивость по отношению к заданному набору демаскирующих преобразований, основанную на понятии расстояния между функционально эквивалентными программами.
Установлена степень устойчивости опубликованных методов маскировки программ по отношению к фиксированному набору современных методов статического и полустатического анализа программ и основанных на них демаскирующих преобразований. На этом основании предложена классификация методов маскировки.
Предложен и обоснован новый метод маскировки программ, устойчивый к этому набору методов анализа программ и демаскирующих преобразований. Предложенный метод основан на разрушении структурности графа потока управления и внесении в текст несущественных операций, объединяемых с основными операциями с помощью тождеств.
4. Разработана и реализована прототипная версия инструментальной среды Poirot, обеспечивающей возможность маскировки и демаскировки программ, а также поддерживающей анализ маскирующих преобразований программ и разработку новых маскирующих преобразований.
Интегрированная среда Poirot, являясь расширяемой, позволяет добавлять новые методы анализа и трансформации программ. Прототипная версия среды Poirot носит предварительный характер и является базовым средством, обеспечившим проведение исследований.
Научная новизна работы. Все полученные в диссертационной работе результаты являются новыми.
Практическая ценность работы. Система Poirot позволяет демаскировать замаскированные программы и маскировать программы устойчивым образом. Она помещена в открытый доступ в Internet и может использоваться для анализа существующих методов маскировки программ и разработки новых методов маскировки программ, непосредственно для маскировки программ и анализа замаскированных программ, а также для решения некоторых проблем обратной инженерии. С помощью интегрированной среды Poirot исследованы методы маскировки программ, используемые одним из коммерческих маскировщиков, и выявлены слабые стороны этого метода. Интегрированная среда используется в учебном процессе на факультетах ВМиК МГУ и ФПМЭ МФТИ.
С помощью интегрированной среды Poirot разработан новый метод автоматического разбиения последопательной программы на нити, который учитывает локальность доступов к данным [29].
Апробация работы. Основные результаты работы опубликованы в работах [16, 17, 18, 19, 28]. Результаты работы обсуждались на следующих конференциях и семинарах:
Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М. Р. Шуры-Буры.
Конференции, посвященной 90-летию со дня рождения А. А. Ляпунова, Россия, Новосибирск, 8—11 октября 2001 года.
Школе-семинаре молодых учёных факультета ВМиК МГУ, Дубна, октябрь 2001.
Тихоновских чтениях факультета ВМиК МГУ, 30 октября 2002 года.
Семинаре "International Workshop on Program Understanding" в рамках Пятой международная конференции «Перспективы систем информатики», 9—12 июля 2003 г., Россия, Новосибирск.
Объём и структура диссертации. Работа состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации — 133 страницы, в том числе 49 иллюстраций и 9 таблиц. Список литературы содержит 81 наименование.
Краткое содержание диссертации. Глава 1 посвящена построению аппарата понятий, используемых в диссертационной работе, классификации элементарных маскирующих преобразований по типам, анализу маскирующих преобразований, а также обзору существующих инструментальных средств маскировки программ. В разделе 1.1 очерчивается круг задач, связанных с маскировкой программ, и связь задачи маскировки программ с задачами защиты информации и трансляции программ. В разделе 1.2 вводятся стандартные термины, используемые в тексте работы. В разделе 1.3 вводятся метрики сложности кода программы. В разделе 1.4 вводится расстояние между текстами программ. В разделе 1.5 предлагается определение устойчивости метода маскировки программ. Раздел 1.6 фиксирует используемый в настоящей работе набор А алгоритмов анализа программ и основанных на них демаскирующих преобразований. В разделе 1.7 даётся сравнительный анализ и классификация опубликованных маскирующих преобразований программ. В разделе 1.8 даётся краткий обзор существующих реализаций маскировщиков для языков Java и Си.
Преобразования реструктуризации всей программы
Для того, чтобы быть полезной, любая программа взаимодействует со своим окружением посредством вызовов библиотечных процедур ввода/вывода. Кроме того, стандартная библиотека языка, как правило, содержит реализации повсеместно используемых концепций, например, контейнеров. Поскольку имена и семантика стандартных процедур библиотеки известны, точки вызова библиотечных процедур легко могут быть прослежены, а это может дать ценную информацию для анализа программы.
Для устранения этого слабого звена программа может содержать свой набор библиотечных процедур с семантикой стандартных процедур. Эти процедуры могут маскироваться вместе со всей программой. Такое преобразование позволяет резко сократить количество вызовов внешних библиотек, сохранив только необходимый минимум (например, вызовы процедур ввода/вывода). Обратной стороной этого преобразования является увеличение размера программы (размер программы увеличивается на достаточно большую константу), и, возможно, потеря переносимости.
Метрики цены применения преобразования и усложнения программы растут пропорционально количеству добавленных функций. Для выполнения данного маскирующего преобразования достаточно семантического анализа маскируемой программы. 1. Значение переменной на стадии маскировки программы может быть определено по самой программе и по дополнительной информации, которая известна на стадии маскировки программы, но отсутствует в тексте программы. 2. Только по тексту замаскированной программы определить значение непрозрачной переменной «сложно» (в том или ином смысле). Непрозрачный предикат — это предикат (выражение, вырабатывающее результат булевского типа), удовлетворяющий вышеуказанным двум признакам. Непрозрачные предикаты могут быть одного из трёх типов: PF — предикат, всегда принимающий значение «ложь»; Рт — предикат, принимающий всегда значение «истина»; Р1 — предикат, который может принимать оба значения.
Внесение в программу непрозрачных переменных и предикатов представляется нам одним из важнейших методов маскировки программ. От устойчивости непрозрачных предикатов зависит устойчивость многих методов маскировки программы, например, внесения недостижимого кода. Непрозрачные предикаты рассматриваются подробно в разделе 1.7.5.
Данное маскирующее преобразование состоит во внесении в программу инструкций, которые на самом деле никогда не выполняются. Недостижимый код может вноситься только совместно с маскирующими преобразованиями, которые создают новые дуги в графе потока управления процедуры: с непрозрачными предикатами или диспетчеризацией графа потока управления.
Маскирующий потенциал этого преобразования состоит в том, что, хотя недостижимые инструкции никогда не выполняются, задача статического определения достижимости кода является алгоритмически неразрешимой. Таким образом, в достаточно сложных случаях (например, если непрозрачный предикат имеет достаточно сложную структуру) статический анализатор программы окажется не в состоянии определить достижимость кода и будет вынужден предполагать, что инструкции выполняются при некоторых входных данных. Таким образом, замаскированная программа и с точки зрения человека, и для автоматического анализа будет значительно отличаться от исходной программы.
Один из способов введения недостижимого кода — одновременно с непрозрачным предикатом. Например, если в программу внесён непрозрачный предикат типа PF, то операторы, размещённые в ветке «then» условного оператора, будут недостижимыми. В качестве недостижимого кода можно взять произвольные инструкции (или даже целые базовые блоки) исходной процедуры. Кроме того, могут быть добавлены новые дуги графа потока управления, которые существенно замаскируют управляющую структуру программы.
Для выполнения маскирующего преобразования требуется семантический анализ маскируемой программы. Пример внесения недостижимого кода приведён на рис. 6. В этом примере через PF обозначен некоторый непрозрачный предикат. В таблице 5 приведены значения базовых метрик для этого примера. Цена маскирующего преобразования в данном случае равна ТС — 2.58, а усложнение текста программы в результате маскировки — МС — 3.63. Расстояние между исходной и замаскированной процедурами равно р(/і,/г) = 16. Внесение «мёртвого» кода. Инструкция программы называется «мёртвой», если при всех значениях входных данных, при которых она выполняется, её выполнение не оказывает влияния на результат работы программы. Такая инструкция может быть безболезненно удалена из текста программы.
Данное маскирующее преобразование состоит во внесении в существующие базовые блоки процедуры новых мёртвых инструкций. Маскирующий потенциал этого преобразования состоит в том, что, как и задача о достижимости инструкции, задача о выявлении мёртвых инструкций алгоритмически неразрешима. Поэтому при достаточно сложной структуре программы статический анализ может оказаться не в состоянии выявить и устранить мёртвые инструкции. В итоге замаскированная программа будет значительно отличаться от исходной программы.
В одном из вариантов мёртвый код вносится совместно с непрозрачными предикатами и недостижимым кодом. В отличие от недостижимого кода, который добавляется на никогда не выполняющиеся ветви графа потока управления процедуры, недостижимый код вносится в уже существующие базовые блоки таким образом, чтобы инструкции вносимого мёртвого кода зависели по данным от недостижимого базового блока.
Второй вариант внесения мёртвого кода состоит в том, что инструкции вносимого мёртвого кода создают и используют некоторые динамические структуры данных. Поскольку задача анализа указателей в динамической памяти является алгоритмически неразрешимой, автоматически выявить в результате статического анализа такой мёртвый код при достаточно сложной структуре динамических данных крайне затруднительно.
В отличие от недостижимого кода, который никогда не выполняется, и, соответственно, не накладывает никаких ограничений на составляющие его инструкции, мёртвый код выполняется хотя бы при некоторых входных данных. Поэтому все свойства вносимого мёртвого кода должны быть известны при маскировке программы. Например, выполнение инструкций мёртвого кода никогда не должно приводить к возникновению исключительных ситуаций.
При выполнении преобразования внесения мёртвого кода вносимый код может как генерироваться маскирующим компилятором, так и браться из самой маскируемой программы. В первом случае компилятор может вставлять инструкции, которые манипулируют со специальными переменными, введёнными маскирующим компилятором и не используемыми в исходной программе. Тогда отсутствие побочного эффекта, влияющего на основную программу, и исключительных ситуаций может быть гарантировано.
Анализ маскирующих преобразований графа потока управления
В данном разделе мы опишем демаскирующие преобразования и построенные на их основе методы демаскировки программ, замаскированных с помощью маскирующих преобразований и методов маскировки, описанных в разделе 1.7. Для каждого маскирующего преобразования подбирается метод демаскировки, который позволяет существенно ослабить маскировку, а во многих случаях и вовсе от неё избавиться.
Сложность анализа замаскированной программы оценивается по двум показателям: глубине необходимого анализа замаскированной программы и степени автоматизируемости.
Оценка CL сложности анализа позволяет оценить глубину анализа замаскированной программы, необходимого для выполнения демаскирующего преобразования. Оценка сложности анализа даётся по той же шкале, что и оценка ОС сложности маскирующего преобразования (см. раздел 1.3), приведённой в таблице 1. Для многих видов маскирующих преобразований оценка CL зависит от того, какой из видом данного маскирующего преобразования был использован. Например, маскирующее преобразование внесения непрозрачных предикатов может добавлять в программу непрозрачные предикаты самого разного вида, от простейших (if (0)), до очень сложных. Для анализа и устранения простейших непрозрачных предикатов достаточно инструментов уровня синтаксического анализа, которые работают автоматически, а для устранения сложных непрозрачных предикатов требуется статистический анализ, либо сложные инструменты, подобные интерактивному доказателю теорем. В таких случаях мы будем оценивать максимальную и минимальную сложность анализа.
Оценка SL степени поддержки показывает степень автоматизируемое процесса демаскировки и оценивается по следующей шкале: Автоматическая демаскировка (0 баллов) — демаскировка программы производится полностью автоматически. Инструментальная среда демаскировки реализует алгоритмы поиска замаскированных фрагментов, точного определения параметров маскировки и демаскировки фрагмента. При этом никакое вмешательство пользователя не требуется. Полуавтоматическая демаскировка (1 балл) — для демаскировки программы требуется незначительное участие пользователя. Инструментальная среда демаскировки реализует алгоритмы поиска замаскированных фрагментов, точного определения параметров маскировки и демаскировки фрагмента. Однако алгоритмы поиска замаскированных фрагментов являются неточными, то есть могут либо пропускать замаскированные фрагменты, либо срабатывать на незамаскированных фрагментах программы. Поэтому от пользователя требуется подтверждение применения демаскирующего преобразования на каждом опознанном фрагменте программы. Поддерживаемая демаскировка (2 балла) — для демаскировки программы требуется существенное участие пользователя. Это значит, что инструментальная среда демаскировки не содержит точных алгоритмов поиска замаскированных фрагментов и/или их демаскировки. Вместо них пользователь использует инструменты общего назначения для анализа и трансформации программ (например, стандартные методы оптимизации или профилирования). Неавтоматизируемая демаскировка (3 балла) — автоматическая демаскировка программы принципиально невозможна. Каждой новой замаскированной программы пользователь должен использовать каждый раз разный набор инструментальных средств, или каждый раз использовать новые эвристики анализирующих алгоритмов. Введём также итоговую оценку DL трудоёмкости анализа, которая равна DL = CL + SL. Лексические методы маскировки программ (1.7.1.1, 1.7.1.2) очень просты, но не обеспечивают качественной маскировки программ. Хотя удалённые комментарии и переименованные идентификаторы восстановить невозможно, это обстоятельство не является серьёзным препятствием для анализа программы. Как показывает практика обратной инженерии унаследованных систем, комментарии в унаследованных системах часто неадекватны, а имена сущностей программы не отражают их назначения и использования [65]. Для восстановления форматирования программы может применяться широко распространённая утилита indent [13], которая позволяет переформатировать текст программы в соответствии с одним из десятков стилей кодирования программ на Си. Поэтому для восстановления форматирования достаточно лексического анализа программы (CL = О баллов), который выполняется автоматически (SL = 0 баллов). Для маскирующего преобразования изменения идентификаторов необходимо провести семантический анализ (CL = 2 балла), демаскирующее преобразование переименования выполняется в полуавтоматическом (SL = 1 балл) режиме. В данном разделе мы подвергнем анализу маскирующие преобразования, описанные в разделе Каждому маскирующему преобразованию посвящен отдельный параграф. Для анализа замаскированных программ используются как известные методы полустатического и статического анализа программ, так и новые алгоритмы, разработанные автором. Открытая вставка процедур Преобразование открытой вставки (1.7.3.1) — одностороннее. После того, как тело одной процедуры было добавлено в другую процедуру, и над получившейся процедурой были проведены маскирующие преобразования, однозначно определить исходные границы процедур становится невозможно. Однако, при выполнении открытой вставки в маскирующем компиляторе существуют ограничения, которые ослабляют маскирующий потенциал преобразования и помогают при демаскировке: 1. Если маскирующий компилятор не может определить все точки вызова процедуры, включаемой открытой вставкой, то есть или эта процедура доступна из других модулей, или где-либо в данном модуле берётся адрес процедуры, маскирующий компилятор должен сохранить в выходной программе копию процедуры. 2. Рекурсивные процедуры, как правило, не могут включаться открытой вставкой в другие процедуры. 3. Преобразование открытой вставки значительно увеличивает размер программы, поэтому обычно для открытой вставки выбираются либо маленькие процедуры, либо процедуры, которые вызываются один раз.
Изложенные выше прагматические ограничения на преобразование открытой вставки упрощают анализ замаскированных программ. Выявление процедур, раскрытых с помощью открытой вставки, следует проводить уже тогда, когда все другие демаскирующие преобразования проведены. Все процедуры, присутствующие в программе, размеры которых невелики, являются потенциальными кандидатами в процедуры, которые подвергались открытой вставке при маскировке. Большие процедуры затем просматриваются в поисках похожих фрагментов.
Увеличение графа потока управления процедуры
На рис. 35 приведён интерфейс генератора счётчиков, поддерживаемый интегрированной средой Poirot. Для каждого нового счётчика должен присутствовать класс-фабрика, реализующий интерфейс CounterFactory.
Метод getCounterKindName возвращает строку символов, позволяющую идентифицировать вид счётчиков, реализуемый данным классом. Например, простейший счётчик по модулю возвращает строку "ModuloCounter". Эта строка используется в маскирующем компиляторе для случайного выбора из нескольких доступных счётчиков, а также в интерфейсе пользователя.
Метод getCounterKindDescription используется в интерфейсе пользователя для вывода краткого описания данного вида счётчиков. Метод hasGetAndNext позволяет маскирующему компилятору определить, поддерживает ли данный вид счётчиков раздельные операции get и next, или же обе операции реализуются одновременно. Метод ma yGener ate Jumps позволяет маскирующему выбрать режим, в котором будет вызываться генерация операции next. Если метод mayGenerateJumps возвращает false, при генерации операции next соответствующему методу будет передаваться ссылка на переменную или псевдорегистр, в который должно быть помещено значение, выработанное операцией. Если же метод возвращает true, будет передан массив меток, на которые должно попадать управление в зависимости от результата операции. Метод newlnstance основной — он создаёт новый экземпляр генератора счётчика. Каждому счётчику, вставляемому в маскируемую программу соответствует отдельный экземпляр класса, реализующего интерфейс CounterGenerator, и все операции по генерации кода для каждого счётчика ведутся через его соответствующий генерирующий класс. Параметр lim метода newlnstance определяет предел изменения значения счётчика, а параметр env позволяет задать класс, содержащий методы доступа к окружению маскируемой процедуры. Интерфейс CounterGenerator определяет требования со стороны маскирующего компилятора непосредственно к генератору кода для счётчика. В интерфейсе предусмотрены следующие методы: getFactory — позволяет получить ссылку на класс фабрики генераторов счётчиков, породивший данный генератор. emitType вызывается для того, чтобы в маскируемую процедуру были добавлены определения типов данных, необходимых данному счётчику. Параметр р задаёт инструкцию, после которой могут быть добавлены определения типов. Метод должен вернуть ссылку на последнюю добавленную инструкцию. Если метод не добавил в маскируемую программу определений типов, должно быть возвращено значение параметра р. emitGlobalDecl вызывается, чтобы в маскируемую процедуру были добавлены определения глобальных переменных, необходимых данному счётчику. Параметры метода и его возвращаемое значение аналогичны методу emitType. emitLocalDecl вызывается, чтобы в маскируемую процедуру были добавлены определения локальных переменных, необходимых данному счётчику. Параметры метода и его возвращаемое значение аналогичны методу emitType. Как правило, каждый экземпляр счётчика добавляет определения либо только на локальный, либо только на глобальный уровень. emitlnit вызывается, чтобы в маскируемую процедуру были добавлены инструкции инициализации счётчика. Параметры метода и его возвращаемое значение аналогичны методу emitType. emitGet вызывается, когда в маскируемую процедуру вставляется операция get. Па раметр р определяет точку в маскируемой процедуре, в которую нужно вставить ин струкции. Параметр е задаёт ссылку на переменную или псевдорегистр, в котором в результате выполнения инструкций операции get должно оказаться её значение. Пара метр d — это массив меток, на которые должно попасть управление в зависимости от результата вычисления операции get в замаскированной программе. При вызове метода emitGet только один из параметров е или d отличен от null в зависимости от значения, возвращаемого методом mayGenerateJumps класса-фабрики. Метод emitGet должен возвращать ссылку на последнюю добавленную в тело процедуры инструкцию. emitNext вызывается, когда в маскируемую процедуру вставляется операция next. Параметр р определяет точку в маскируемой процедуре, в которую нужно вставить инструкции. Параметр і определяет номер операции next в семействе операций. Метод должен возвращать ссылку на последнюю добавленную в тело процедуры инструкцию. emitGetAndNext является комбинацией методов emitGet и emitNext. Он вызывается маскирующим компилятором, только если метод hasGetAndNext класса-фабрики возвращает true. emitFini вызывается маскирующим компилятором для того, чтобы в конец замаскированной процедуры были добавлены инструкции, освобождающие ресурсы, занятые счётчиком. Параметр р определяет точку в маскируемой процедуре, в которую должны вставляться инструкции. Метод должен возвращать ссылку на последнюю добавленную инструкцию или значение параметра р, если инструкций не было добавлено. В настоящее время в интегрированной среде Poirot реализованы некоторые простейшие виды счётчиков, которые описаны ниже. Счётчик по модулю. Это — простейший вид счётчика. Состояние счётчика хранится в переменной целого типа, которая размещается на уровне статических переменных единицы компиляции. Операция init заключается в записи в переменную счётчика произвольного числа, например, значения какого-либо параметра процедуры или какой-либо глобальной переменной. Операция get заключается в взятии остатка от деления на к текущего значения переменной счётчика. Причём остаток от деления может проверяться разными способами (например, если к — степень числа 2, у текущего значения счётчика с помощью побитовой операции «и» сохраняются только log к младших битов числа). Операция next заключается в прибавлении или вычитании произвольного числа, не кратного к, причём семейство операций next порождается различным выбором этого числа. Линейный конгруэнтный счётчик. Этот вид счётчика, по сути, реализует хорошо известный линейный конгруэнтный метод получения псевдослучайных чисел [9]. Операции init и get не изменяются, а операция next определяется как next(cntr) = (Сі -cntr-VC-i) mod C3 где Сг и Сз — взаимно простые числа. Кроме этого можно применять и полиномиальные конгруэнтные счётчики, а также любой другой алгоритм получения псевдослучайных равномерно распределённых чисел [9]. Криптографические хэш-функции Для реализации счётчиков могут использоваться криптографические хэш-функции, например, MD5 или SHA [72], или симметричные криптосистемы. Тогда операция next может выглядеть следующим образом Здесь / — хэш-функция, а х — некоторые произвольные данные, например, значение какой-либо локальной переменной или параметра процедуры. Нужно отметить, что алгоритмы вычисления криптографических хэш-функций имеют специфический вид, так как состоят из побитовых операций с использованием табличных данных, поэтому могут быть достаточно легко опознаны опытным пользователем.
Динамические структуры данных. Для реализации счётчиков могут использоваться и динамические структуры данных. Например (в простейшем случае) может быть создан кольцевой список, который заполняется числами от 0 до к — 1 в произвольном порядке. Операция get состоит в чтении значения текущего элемента списка, а операция next — в продвижении указателя на следующий элемент списка.
«Зацепление» холостой и основной программы
На предыдущих этапах граф потока управления процедуры был значительно увеличен в размерах, затем в него было добавлено большое количество несущественного кода. И предикаты, добавленные в расширенный граф потока управления для моделирования исходного графа потока управления, и несущественный код используют множество переменных, не пересекающихся с основными переменными маскируемой процедуры. В результате процедура может быть расслоена на существенную и несущественную часть, хотя это может быть и затруднено необходимостью проведения анализа указателей.
Чтобы затруднить отделение несущественной части замаскированной процедуры в неё добавляется большое количество искусственных зависимостей по данным между существенной и несущественной частью. Для этого в настоящее время используются следующие механизмы: Использование булевских тождеств. Использование числовых тождеств. Использование комбинаторных тождеств. Использование массивов и динамических структур данных. Использование динамических структур данных. Булевские тождества. Булевские тождества применяются для усложнения булевских выражений, которые определяют условные переходы. В отличие от других видов тождеств, булевские тождества произвольной сложности легко могут получаться автоматически. Рассмотрим в качестве примера основной метод получения булевских тождеств, реализованный в настоящее время.
Булевские тождества произвольной сложности могут быть получены из булевских тождеств относительно простой структуры при помощи набора эквивалентных преобразований. Пусть мы хотим составить булевское тождество с переменными vi, V2, ... v/с, среди которых есть как переменные исходной процедуры, так и несущественные переменные, внесённые при маскировке. Пусть е — выражение, подвергаемое усложнению. Тогда строится выражение е-о, где о = (vi VvT)A"-A(v Vvjt). Далее к получившемуся выражению применяются т шагов эквивалентных преобразовании, которые можно найти, например, в [20]. В результате получается выражение е1, эквивалентное е, которое используется для условного перехода в замаскированной программе.
Такой метод получения булевских тождеств аналогичен методу получения непрозрачных предикатов, рассмотренному в 1.7.4.5, но в данном случае использование тождеств не приводит к появлению «мёртвой» дуги графа потока управления, которая достаточно легко может быть обнаружена. Поэтому использование булевских тождеств в нашем случае обнаруживается значительно сложнее.
Комбинаторные тождества. Все рассматриваемые далее тождества, как комбинаторные, так и теоретико-числовые взяты, в основном, из [7]. Рассмотрим в качестве примера следующее биномиальное тождество.
Тождество может использоваться следующим образом: в качестве п берётся несущественная переменная, принимающая целые значения в небольшом интервале (например, от 0 до 5). Генерируются инструкции, вычисляющие сумму биномиальных коэффициентов и помещающие результат во временную переменную, для определённости @ 1. Генерируется инструкция сдвига, вычисляющая 2" и помещающая результат в другую временную переменную, например @2. Далее в исходной процедуре выбирается аддитивное целое выражение, результат которого сохраняется в некоторой временной переменной, например, @3, и строится новое выражение @1 + @3 - @2. Это выражение всегда будет равно выражению @3, но содержит зависимость по данным от переменной п.
Некоторые другие тождества, которые могут использоваться аналогичным образом, приведены ниже для любого целого а ф 0 (mod р) и простого р. При маскировке генерируется случайное простое число р. Далее генерируются инструкции для вычисления ap l mod р, причём возведение в степень вычисляется с помощью разложения р — 1 в двоичную систему. Эти инструкции образуют достаточно длинную линейную последовательность, которая может быть распределена по базовым блокам маскируемой процедуры. Результат вычисления выражения добавляется как множитель в какое-либо мультипликативное выражение исходной программы, либо как множитель к переменной.
Другие теоретико-числовые тождества, которые также могут использоваться для внесения зависимостей по данным, приведены ниже. Обобщением малой теоремы Ферма является теорема Эйлера: где п и х произвольные целые числа, ф(и) — функция Эйлера, которая равна количеству взаимно простых с п целых чисел, меньших п. тогда и только тогда, когда п — простое число.
Использование массивов и динамических структур данных Динамические структуры данных могут использоваться и для создания искусственных зависимостей по данным. Главный расчёт здесь делается на то, что в настоящее время не существует удовлетворительного алгоритма анализа алиасов, возникающих при использовании указателей и индексов массивов.
В качестве простейшего способа можно предложить размещение всех локальных переменных одного типа в массиве. В тексте процедуры вместо имени переменной теперь будет использоваться индекс массива. Даже случаев, когда индекс всегда представляет собой литеральную константу, будет достаточно, чтобы поставить в тупик простейшие алгоритмы анализа алиасов, которые рассматривают массив как единое целое.
В момент маскировки программы известно, какие элементы массива заняты существенными, а какие — несущественными переменными. Более того, распределение несущественных переменных по массиву может выбираться произвольным образом. Это может использоваться для построения зависимостей по данным. Пусть / — функция, ставящая в соответствие произвольному целому значению некоторый индекс в массиве, по которому находится несущественная переменная. Тогда искусственные зависимости по данным строятся с помощью выражений вида vars[f(e\)] — ег или \ars[f{e\)] = vars\f(e2)\. Здесь vars — это массив переменных, е\, ei — выражения, которые включают в себя как существенные, так и несущественные переменные.
Один из простых способов использования динамических структур данных для внесения зависимостей по данным заключается в том, что все значения переменных всех типов хранятся в списке, размещаемом в динамической памяти. Для доступа к переменным вместо их имени используется разыменование специальных указателей. Кроме того, указатели на несущественные переменные время от времени меняют своё положение в списке.
В результате окажется, что все обращения к бывшим локальным переменным процедуры обращаются к объектам в области динамической памяти. Для разделения существенных и несущественных переменных потребуется анализ алиасов в динамической памяти, способный работать с динамическими структурами данных произвольной глубины. В настоящее время не существует такого метода статического анализа алиасов. Этот подход проиллюстрирован на рис. 42. На этом рисунке процедура содержит четыре переменных а, Ь, с и d. Пусть, для определённости, переменные а и b — существенные, а с и d — несущественные. В замаскированной процедуре вместо этих локальных переменных вводятся переменные pi и р2, указывающие на звенья списка, размещённого в динамической памяти. Переменная а доступна как pl- prev или как p2- next, а переменная с — как pl- next или как p2- prev.
