О некоторых задачах анализа и трансформации программ

С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маликов, Д.М. Мельник, А.В. Меньшикова

Аннотация.

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

1. Введение

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

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

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

Данная работа имеет следующую структуру: в разделе 2 мы рассматриваем задачу автоматического разбиения программы на нити, в разделе 3 рассматриваются задачи маскировки программ, а в разделе 4 задача автоматического выявления уязвимостей. Далее в разделе 5 кратко описывается интегрированная среда IRE, её состав и внутреннее представление MIF, используемое всеми компонентами IRE. Наконец, в разделе 6 мы формулируем выводы данной работы и даём направления дальнейших исследований.

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

В настоящее время широко распространены рабочие станции и персональные компьютеры, содержащие несколько центральных процессоров. Массовые многопроцессорные системы обычно содержат 2, 4 или 8 процессоров, работающих над общей памятью с одинаковым для всех процессоров временем доступа (SMP). Для максимального использования возможностей SMP-систем в вычислительно-интенсивных приложениях необходимо максимально использовать "легковесные" процессы (нити). В этом случае накладные расходы на коммуникацию минимизированы, так как все нити разделяют одно адресное пространство, а синхронизационные операции выполняются проще и быстрее, чем для обычных ("тяжелых") процессов.

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

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

Системы с разделяемой памятью наиболее удобны для программиста параллельных приложений. Более того, часть работы по распараллеливанию последовательного кода может быть выполнена компилятором. Существует много исследований по автоматическому распараллеливанию циклов и рекурсивных процедур на таких системах. Некоторые разработки реализованы в промышленных компиляторах, например, IBM Visual Age C++, Intel C++ Compiler, SGI MIPSPro, REAPAR и других.

В последнее время проводятся исследования по автоматическому распарал-леливанию любого последовательного кода. Предложено несколько подходов, таких, как управление выполнением нитей (thread-level speculation) [6], коммутативный анализ, динамическое распределение задач на нити (dynamic task scheduling) [5], автоматическое разделение на нити на этапе компиляции. Часть предложенных алгоритмов проверена авторами на эмуляторах, часть реализована в существующих исследовательских компиляторах, например, в компиляторе SUIF Стенфордского университета [7].

Формализация понятия локальности проведена в [8]. Рассматривается два вида событий локальности:

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

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

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

Группировка инструкций, использующих одни и те же данные (locality grouping), для увеличения количества событий временной локальности.

Упаковка данных в памяти (data packing) для увеличения количества событий пространственной локальности.

Перестановка процедур, базовых блоков и т.п.

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

2.1. Алгоритм разбиения программы на нити

В настоящем разделе рассматривается построение промежуточного представления программы, над которым работает алгоритм, а также подробно описывается сам алгоритм разбиения программ на нити. Подробное описание алгоритма можно найти в [3]. Алгоритм состоит из трех частей:

Построение ценовой модели, отражающей свойства локальности

Разбиение программы на нити

Дополнительные оптимизации

Рис. 1. Пример функции и ее DDG.

2.1.1. Граф зависимостей по данным

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

Представлением, обладающим всеми необходимыми нам свойствами, является иерархический граф зависимостей по данным, используемый в [9] (data dependence graph, DDG). Узлом такого графа может являться:

Простой оператор (сложение, умножение, сравнение, присваивание и т.д.)

Более сложный оператор (условный оператор, оператор цикла и т.д.)

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

Дуги графа DDG представляют собой зависимости по данным между узлами. Более формально, пусть u и v - узлы DDG, причем в последовательной программе u предшествует v. Дуга (u, v) входит в граф тогда и только тогда, когда между u и v есть зависимость по данным одного из трех типов:

"запись-чтение" (в узле v необходимы результаты вычислений узла u),

"чтение-запись" (в узле v записывается переменная, значение которой считывается в u),

"запись-запись" (оба узла записывают одну и ту же пере-менную).

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

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

Пример функции и ее графа зависимостей по данным приведен на Рис. 1. DDG состоит из трех узлов: двух простых узлов и оператора цикла, раскрывающегося в DDG второго уровня.

Граф зависимостей по данным строится для каждой функции программы. Алгоритм построения состоит из следующих этапов:

Построение графа потока управления программы.

Выбор программных блоков, которые будут узлами текущего уровня иерархии DDG.

Нахождение зависимостей по данным между этими узлами с помощью алгоритма достигающих определений.

Если необходимо, продвинуться на следующий уровень иерархии и достроить граф.

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

2.1.2. Ценовая модель

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

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

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

2.1.3. Разбиение на нити

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

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

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

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

Учет времени, необходимого на синхронизацию с другими нитями, если она требуется.

Учет возникающих событий локальности.

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

2.1.3.1. Учет времени на синхронизацию

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

Таким образом, к моменту обработки некоторого узла все узлы, от которых он зависит по данным, уже распределены на нити. Если какие-либо из таких узлов находятся в других нитях, то перед выполнением текущего узла необходимо провести синхронизацию со всеми такими нитями. Для того, чтобы осуществить такую синхронизацию, нужно завести по одной общей переменной для каждой нити. Присваивание значения i такой переменной для некоторой нити j означает, что эта нить выполнила узел i. Нить, ждущая результатов вычисления узла i, должна ждать, пока соответствующая общая переменная не примет нужного значения. Пример такой синхронизации показан на Рис. 2.

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

Рис. 2. Пример синзронизации

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

Рис. 3. Пример эмулирования кэша

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

Пример моделирования событий локальности изображен на Рис. 3.

2.2. Экспериментальные результаты

Мы применили нашу реализацию алгоритма к тестовой функции, решающей алгебраическое уравнение четвертой степени x4+ax3+bx2+cx+d=0.

Функция не содержит циклов и не может быть распараллелена традиционными способами. Полученная многопоточная версия функции была реализована с помощью библиотеки pthread под операционной системой Linux. Экспериментальные запуски были проведены на четырехпроцессорном Intel Itanium, на которых установлена ОС RedHat Linux 7; использовались компиляторы GCC 3.3.1 и ICC 8.00b. Программа запускалась 100 раз, время ее выполнения измерялось с помощью высокоточных аппаратных счетчиков. Вычислялось среднее значение времени выполнения μ и среднеквадратичное отклонение σ. Все значения времени выполнения, не укладывающиеся в промежуток [μ-2σ,μ+2σ] удалялись из выборки, после чего среднее значение пересчитывалось. Эта величина использовалась для подсчета ускорения. Результаты эксперимента приведены на Рис. 4.

Рис. 4. Ускорение, достигнутое на Itanium

3. Маскирующие преобразования программ

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

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

Целью нашего исследования является новый метод маскировки программ, удовлетворяющего следующим требованиям:

Исходная и замаскированная программа записаны на языке Си.

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

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

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

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

3.1. Методология анализа маскирующих преобразований программ

Для оценки действия маскирующих преобразований на программу мы используем несколько показателей сложности кода программ. Традиционно, подобного рода показатели называются "метрики", в дальнейшем мы будем придерживаться этого термина и в нашей работе. Метрики сложности кода программы ставят в соответствие любой программе некоторое число, которое тем больше, чем "сложнее" программа. Простейшая метрика LC размера процедуры равна количеству инструкций промежуточного представления MIF в записи процедуры. Метрика YC сложности циклической структуры равна мощности транзитивного замыкания отношения достижимости в графе потока управления процедуры. Метрика DC сложности потока данных определяется как количество дуг в графе зависимостей по данным, строящемся по результатам анализа достигающих определений программы. Метрика UC количества недостижимого кода определяется как количество инструкций в программе, которые не выполняются ни при каких наборах входных данных. Известно, что точное вычисление метрик DC и UC является алгоритмически неразрешимой задачей.

Через O(p,e) мы обозначим применение метода маскировки O к программе p. e - это параметр, который позволяет выбрать единственную программу p' = O(p,e) из множества функционально эквивалентных замаскированных программ O(p). В частности, параметр e может быть случайным числом. Множество изменения параметра e обозначим через E. Тогда LC(p) - значение метрики LC до маскировки, а LC(O(p,e)) - после маскировки.

Композитная метрика цены TC преобразования O(p,e) вычисляется по метрикам LC и UC следующим образом:

Для конечного множества D программ цена маскирующего преобразования определяется как .

Метод маскировки называется допустимым для множества D, если , где константа TCMAX устанавливается директивно, исходя из эксплуатационных требований к замаскированной программе.

Композитная метрика MC усложнения программы вычисляется по метрикам YC и DC следующим образом:

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

Для оценки сложности самого маскирующего преобразования вводится оценка OC сложности маскирующего преобразования, которая определяется как требуемая для выполнения данного маскирующего преобразования глубина анализа программы согласно таблице 1.

Требуемая глубина анализа

Значение OC

Лексический анализ

Синтаксический анализ

Семантический анализ

Анализ потока управления

Консервативный анализ потока данных

Полустатический анализ

Точный анализ потока данных

Таблица 1. Шкала оценки сложности маскирующих преобразований

Для оценки степени различия текстов программ вводится расстояние ρ(p1,p2) между текстами программ p1 и p2, которое используется для оценки устойчивости маскирующего преобразования. Введём расстояние ρC между графами потока управления двух процедур, равное минимальному количеству операций удаления и добавления рёбер и дуг, переводящих один граф в граф, изоморфный другому. Аналогично введём расстояние ρD между графами зависимостей по данным двух процедур. Обозначим через ρCD(f1,f2) сумму ρC(f1,f2)+ρD(f1,f2). Тогда расстояние ρ(p1,p2) вычисляется по формуле

Здесь минимум берётся по всевозможным множествам M, состоящим из пар (f1,f2), где f1 - процедура из программы p1, f2 - процедура из программы p2. Все процедуры f1 и f2 встречаются в M не более одного раза. Через M1 обозначено множество процедур программы p1, отсутствующих в M, а через M2 - множество процедур программы p2, отсутствующих в M. E - это пустой граф.

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

Пусть - это множество маскирующих преобразований и необходимых для их выполнения алгоритмов анализа программ. Тогда метод маскировки - это цепочка . Все алгоритмы анализа, необходимые для выполнения маскирующего преобразования oi, находятся в цепочке O перед oi. Пусть - заданный набор демаскирующих преобразований и необходимых для их выполнения алгоритмов анализа программ. Метод демас-кировки - это цепочка . Все алгоритмы анализа, необходимые для выполнения маскирующего преобразования aj, находятся в цепочке A перед aj. Длину |A| строки A назовём сложностью метода демаскировки. Метод маскировки O называется устойчивым для множества программ D по отношению к множеству демаскирующих преобразований с порогом устойчивости Δ, если выполняются следующие условия:

Метод маскировки O является допустимым, то есть .

Для любой программы p`, полученной из p, любой метод демаскировки A сложности не более C получает программу p" отстоящую от p более чем на Δ, то есть:

Константа Δ называется порогом устойчивости.

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

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

В рамках нашего исследования нам удалось получить качественную и количественную характеристику опубликованных другими исследователями и разработчиками систем маскировки маскирующих преобразований. Был проведён сравнительный анализ их цены TC, усложнения маскируемой программы MC и оценки сложности OC. На примере программы, вычисляющей функцию Фибоначчи, проводится ранжирование маскирующих преобразований по соотношению усложнение/цена.

3.2. Анализ маскирующих преобразований

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

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

Int fib(int n)

{

int a, b, c;

a = 1;

b = 1;

if (n <= 1) return 1;

for (; n > 1; n--) {

c = a + b;

a = b;

b = c;

}

return c;

}

int fib(int n)

{

int a, b, c, i;

long long t;

a = 1;

b = 1;

if (n <= 1) return 1;

while (1) {

t = n * n % 65537;

for (i = 0; i < 15; i++)

t = t * t % 65537;

if (n * t <= 1) break;

c = a + b;

a = b;

b = c;

n--;

}

return c;

}

(a) исходная программа

(b) замаскированная программа

Рис. 5. Пример применения маскирующего преобразования внесения тождеств

На Рис. 5 показан пример применения маскирующего преобразования внесения тождеств к программе, вычисляющей функцию Фибоначчи. Преобразование основано на малой теореме Ферма для любого целого a, такого, что , и простого числа p). В таблице 2 приведена цена применения маскирующего преобразования и полученное усложнение программы. Для этого примера цена равна 3.83, а усложнение программы - 4.85. Расстояние между исходной и замаскированной программой равно 21.

Исх. процедура fib

0.1111

Замаскированная fib

0.3086

Таблица 2. Оценка влияния маскирующего преобразования внесения тождеств

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

На основании определения устойчивости маскирующих преобразований, дан-ного выше, становится возможным провести анализ всех опубликованных маскирующих преобразований для выявления их устойчивости по отношению к нашему множеству демаскирующих преобразований и алгоритмов анализа. Мы можем ввести количественную классификацию маскирующих преобразований и выявить наиболее устойчивые маскирующие преобразования. Для этого вводятся - эвристическая оценка CL сложности анализа, которая устанавливает глубину анализа замаскированной программы, необходимого для выполнения демаскирующего преобразования, и эвристическая оценка SL степени поддержки демаскировки, устанавливающая необходимую степень участия человека в процессе демаскировки. Для оценки CL используется шкала, приведённая в таблице 1. Для оценки SL используется шкала: "автоматический анализ" (0 баллов), "полуавтоматический анализ" (1 балл), "ручной анализ с развитой инструментальной поддержкой" (2 балла), "только ручной анализ" (3 балла). Итоговая оценка DL трудоёмкости анализа равна

DC=CL+SL

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

Таким образом можно получить количественную классификацию маскирующих преобразований. Для каждого маскирующего преобразования приводится оценка сложности маскировки и оценка трудоёмкости демаскировки. Значение, получаемое как разность оценки трудоёмкости демаскировки и оценки сложности маскировки, позволяет оценить насколько демаскировка данного маскирующего преобразования сложнее, чем маскировка. Исходя из этого определяются маскирующие преобразования, применение которых неоправдано, например, переформатирование программы, разложение циклов, локализация переменных; методы маскировки, которые следует применять только в комплексе с другими методами, например, изменение идентификаторов, внесение дублирующего кода и методы маскировки, применение которых наиболее оправдано, например, внесение тождеств, переплетение процедур, построение диспетчера, повышение косвенности. Сравнение двух маскирующих преобразований приведено в таблице 3. Через D обозначена разность OC-DL, через ρ1 обозначено расстояние между текстами замаскированной и исходной программ fib, а через ρ2 - расстояние между текстами демаскированной и исходной программ. Из таблицы следует, что маскирующее преобразование построения диспетчера предпочтительнее, так как, при равных с методом внесения тождеств трудо-затратах на демаскировку, обеспечивает лучшее соотношение усложнения программы к цене преобразования.

Преобразование

ρ1

ρ2

Внесение тождеств

3.83

4.85

4 - 5

1.27

Построение диспетчера

3.83

6.14

1.60

Таблица 3. Сравнение методов маскировки

3.3. Новый метод маскировки программ

Новый метод маскировки программ мы далее обозначим аббревиатурой "ММ". Его более подробное описание можно найти в [2]. Метод ММ применяется к функциям маскируемой программы по отдельности, при этом структура маскируемой программы в целом не изменяется. Для изменения структуры маскируемой программы могут применяться стандартные методы открытой вставки и выноса функции, которые, однако, не являются частью предлагаемого метода маскировки.

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

Метод М

Вернуться