В данной работе исследуется проблема
В данной работе исследуется проблема анализа запутывающих преобразований графа потока управления функций на языке Си. В работе сделана попытка анализа запутывающих преобразований, опубликованных в открытой печати, с точки зрения их устойчивости к различным видам статического и динамического анализа программ. Запутывание изучается на уровне языка Си, то есть и исходная программа написана на языке Си, и целевая запутанная программа генерируется также на языке Си.
В работе приведена классификация запутывающих преобразований с точки зрения методов анализа программ, которые могут быть использованы для их распутывания. Показано, что для каждого класса рассмотренных запутывающих преобразований существуют методы анализа, которые позволяют эффективно противодействовать таким преобразованиям. Для иллюстрации этого приведены несколько практических примеров распутывания программ, запутанных как вручную, так и автоматическими запутывателями.
Задачи запутывания и анализа запутанных программ имеют три аспекта: теоретический, включающий в себя разработку новых алгоритмов преобразования графа потока управления или трансформации данных программы, а также теоретическую оценку сложности их анализа и раскрытия. Прикладной аспект включает в себя разработку конкретных методов запутывания (распутывания), то есть наилучших комбинаций алгоритмов, эмпирический сравнительный анализ различных методов, эмпирический анализ устойчивости методов, и т. д.
Третий аспект, психологический пока не поддаётся формализации, но не может игнорироваться. Обратная инженерия (понимание) программ - это процесс, результатом которого является некоторое знание субъекта, изучающего программу, который является неотъемлемой частью процесса понимания [18]. Методы запутывания должны максимально использовать свойства (точнее, слабости) человеческой психики.
Не умаляя ценности теоретических исследований, следует заметить, что теоретические выводы должны подтверждаться результатами практического применения предложенных методов.
В данной работе исследуется прикладной аспект задачи запутывания.
В настоящее время широко распространены языки программирования, такие как Java, в которых "исполняемой" формой программы является не машинный код для некоторого типа процессоров, но машинно-нейтральное представление. Задача декомпиляции программы из такого представления обратно в программу на языке Java значительно проще, чем декомпиляция из машинного кода. Существует большое число декомпиляторов для языка Java как распространяемых свободно, так и коммерческих, например [20], что упрощает несанкционированное использование, обратную инженерию и модификацию Java-программ. В качестве одного из способов борьбы с этим рассматривается запутывание программ.
Уже разработано около двух десятков различных запутывателей Java-программ, среди которых есть и коммерческие, например [25]. Простые запутыватели удаляют таблицы символов и отладочную информацию из скомпилированных классов и заменяют исходные имена методов бессмысленными короткими именами. В результате размер файлов уменьшается (до 50\%), а скорость выполнения программы значительно возрастает, поэтому такое запутывание может рассматриваться и как один из способов оптимизации программ. Более развитые запутыватели программ на языке Java, а также запутыватели программ на других языках программирования выполняют преобразования графа потока управления программы и её структур данных. Методы, используемые в них, как правило, подобраны эмпирически и слабо обоснованы теоретически. Сравнительный анализ запутывателей Java-программ, доступных через Интернет, проведён в работе [14].
Возможны разные уровни постановки задачи запутывания и анализа запутывающих преобразований. Во-первых, запутывание может рассматриваться в рамках языка Java. В этом случае исходная программа написана на языке Java, и запутанная программа также написана на языке Java. Однако язык Java допускает только структурные программы, то есть графы потока управления Java-программ всегда сводимые, что существенно ограничивает диапазон применимых преобразований графа потока управления.
Мы рассматриваем задачу анализа запутывающих преобразований в рамках языка Си. Поскольку Си - язык более низкого уровня, чем Java или даже байт-код Java, задачи запутывания и анализа для этих языков оказываются вложенными в соответствующие задачи для языка Си.
Возможна постановка задачи запутывания на ещё более низком уровне, когда запутывается программа на языке ассемблера или даже объектная программа в машинном коде (в последнем случае она должна генерироваться специальным запутывающим компилятором). В ассемблерных и объектных программах можно использовать специфические особенности работы целевой машины, добившись того, что восстановление программы на Си будет крайне затруднено [17]. Но с другой стороны, методы запутывания, применимые к одной архитектуре, могут оказаться неприменимы к другой архитектуре. Заметим, что проблема низкоуровневого запутывания в настоящее время исследована слабо. Нам не известно каких-либо опубликованных методов низкоуровневого запутывания программ, поэтому проблему низкоуровневого запутывания мы в этой работе рассматривать не будем.
Если программа для анализа представлена в исполняемом или объектном коде, и известно, что к программе не применялись низкоуровневые методы запутывания, задача анализа таких программ может быть разбита на две относительно независимых подзадачи. На первом этапе программа декомпилируется [4] в программу на языке Си, затем программа на языке Си распутывается, то есть применяются алгоритмы анализа программ, которые приводят к её возможной перестройке, выделению в ней циклов, условных операторов и других конструкций высокого уровня. Декомпиляция программ - самостоятельная задача, которая может решаться отдельно.
В данной работе мы ограничим класс запутываемых программ программами пакетной обработки, то есть программами, которые получают все исходные данные в начале работы и выдают результат по ходу работы. Во время работы программа не взаимодействует с пользователем и другими программами. Кроме того, потребуем, чтобы программа не использовала аппарат исключений в работе.
Появление исключительной ситуации приводит к завершению работы программы. Эти ограничения связаны с тем, что все опубликованные методы запутывания применимы только к таким программам.
Запутывание программ - достаточно молодое направление исследований. Обзор (таксономия) запутывающих преобразований, известных на тот момент, был опубликован в работе [5] группы, возглавляемой К. Колбергом и К. Томборсоном. В дальнейших работах [6], [7],[8], [9], [15] этой группы опубликованы результаты исследований конкретных алгоритмов запутывания графа потока управления и данных программы, а также приложения запутывания программ к смежным областям, таким как обеспечение устойчивости программы к несанкционированной модификации (tamper-resistance) или внесение в программу "водяных знаков" (watermarking).
Классификация, введённая в работе [5], широко используется, и получила дальнейшее развитие в работах [10], [13], [22].
В работах [23], [24] был предложен новый подход к запутыванию графа потока управления программы, который заключается в преобразовании графа в "плоскую" форму. Чтобы затруднить статическое определение порядка следования базовых блоков используется преобразование, вводящее в программу алиасы. Показывается, что статический анализ запутанной программы с целью восстановления порядка следования базовых блоков является NP-трудной задачей.
В дальнейшем этот подход был развит в работе [3], которая дополнительно предлагает использовать переплетение базовых блоков совместно запутываемых функций и недетерминированный выбор следующего базового блока из множества эквивалентных альтернатив. Доказывается, что статический анализ запутанной программы с целью восстановления порядка следования базовых блоков является PSPACE-трудной задачей.
В работе [2] получен результат, который определяет верхний предел силы запутывающих преобразований. Авторы доказали, что универсального запутывателя не существует. Под универсальным понимается такой запутыватель, который для любой программы строит запутанную программу, такую что определение любого свойства программы, легко определимого по исходной программе, неэффективно по запутанной программе.
Тем не менее, можно показать, что если взять некоторое специальное свойство программ, то запутыватель для этого свойства всё же существует. Вопрос о том, для каких классов программ и каких свойств запутыватель существует, остаётся открытым. В данной работе рассматриваются только запутывающие преобразования графа потока управления программы. Мы сознательно оставляем в стороне преобразования данных программы, а также так называемые превентивные преобразования, которые нацелены против определённых методик декомпиляции программы, реализованных в определённых декомпиляторах.
Мы не пытаемся подтвердить или опровергнуть тезис работы [2] о невозможности запутывания программ, но мы делаем попытку показать, что для всех опубликованных в открытой печати методов запутывания программ существуют достаточно эффективные практически, хотя, возможно, пока не совсем обоснованные теоретически способы противодействия.
Данная работа имеет следующую структуру. В разделе 2 даётся формальное определение понятия запутывания, приводится классификация запутывающих преобразований, описываются запутывающие преобразования графа потока управления. В разделе 3 описываются наиболее важные методы, которые применяются на различных стадиях работы компилятора и могут быть использованы для получения информации о запутанной программе, а также специальные методы анализа запутанных программ. В разделе 4 методы запутывания программ сопоставляются с методами их анализа, вводится классификация методов запутывания по уровню необходимых преобразований распутывания. В разделе 0 приводятся примеры применения некоторых методов анализа программы для распутывания программ. Наконец, в разделе 5.3 подводятся итоги и указываются направления дальнейшей работы.
