С.С. Гайсарян, А.В. Чернов, А.А. Белеванцев, О.Р. Маликов, Д.М. Мельник, А.В. Меньшикова
Аннотация.
В настоящей статье обсуждаются некоторые перспективные направления исследований, проводимые в отделе компиляторных технологий Института системного программирования РАН. Методы анализа и трансформации программ, ранее применявшиеся в основном в оптимизирующих компиляторах, в настоящее время находят применение при решении множества смежных задач, таких как обеспечение безопасности программ, генерация тестов для программ и т. д.
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.
Требуемая глубина анализа
