WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |
АНАЛИЗ И ТРАНСФОРМАЦИЯ ПРОГРАММ С.С. Гайсарян, В.П. Иванников, А.И. Аветисян Институт системного программирования РАН 109004, г. Москва, ул. Б. Коммунистическая, д. 25 (ssg@ispras.ru) (ivan@ispras.ru) (arut@ispras.ru) Аннотация. Актуальность данного обзора состоит в том, что развитие многих современных направлений компьютерной индустрии невозможно представить без существенного развития методов анализа и трансформации программ. В обзоре рассматриваются наиболее значимые направления с анализом существующих технологий, исследований по разработке новых технологий и тенденций развития.

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

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

В настоящее время исследования по методам анализа и трансформации программ развиваются особенно интенсивно, на их основе разрабатываются и успешно внедряются новые прогрессивные технологии разработки и верификации ПО. В данном обзоре рассматриваются следующие три категории исследований: (1) исследования по разработке и обоснованию новых подходов к трансформации программ, (2) исследования и практические работы по применению методов анализа и трансформации программ в новых технологиях, связанных с разработкой ПО; (3) создание новых инструментов и систем автоматизации разработки ПО, в которых используются методы анализа и трансформации программ.

Следует отметить, что методы анализа и трансформации программ применяются не только к исходному коду компонентов ПО, но и к их двоичному представлению.

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

Обзор имеет следующую структуру. В разделе 2 рассматриваются основные классы трансформаций программ, на основе которых реализуются остальные трансформации, и внутренние представления программ, удобные для реализации введенных классов трансформаций. В разделе 3 наиболее актуальные проблемы оптимизации программ, направленные на решение новых задач, связанных с учетом специфики современных платформ и тенденциями развития их архитектуры. Раздел посвящен рассмотрению различных аспектов безопасности программного обеспечения и методов анализа и трансформации программ, применяемых для решения проблем, связанных с обеспечением безопасного функционирования ПО. Сюда относятся такие проблемы, как обнаружение дефектов в компонентах ПО, обнаружение недокументированных свойств у компонентов ПО, защита ПО от обратной инженерии и др. В разделе 5 обсуждаются модельно-ориетнированные подходы в разработке ПО, позволяющие свести до минимума «разрыв» между абстрактной моделью ПО и ее реализацией. Генерация выполнимого кода по моделям позволяет быстро создать прототип на ранних этапах проектирования системы. Выполнение такого прототипа помогает обнаружить архитектурные ошибки и, за счет раннего обнаружения, заметно сократить их стоимость. Наконец, в разделе 6 рассматриваются проблемы обратной инженерии и верификации ПО. Эти методы были особенно популярны в 90-е годы прошлого века в связи с проблемой переноса унаследованного кода (т.е. программ, разработанных в прошлые годы, но продолжающих интенсивно эксплуатироваться) на новую аппаратуру. Успехи в области обратной инженерии привели к необходимости разработки методов защиты ПО от обратной инженерии (этот аспект безопасности ПО рассматривается в разделе 4). В настоящее время обратная инженерия направлена на обнаружение дефектов в программах как разрабатываемых, так и готовых и на оптимизацию архитектур программных систем (в частности, это рефакторинг).

2. Теория и техника трансформации программ Трансформация и анализ программ выполняются на различных уровнях: на уровне исходного кода, на промежуточном уровне, когда программа представляется как последовательность инструкций, похожих на ассемблерные, но сохраняет переменные (а не регистры и ячейки), имеющие тип, на ассемблерном уровне, на уровне бинарного кода. Перечисленные представления в том или ином виде реализованы во всех компиляторах. Так в компиляторе Gcc [1] внутреннее представление исходного уровня называется Generic, внутреннее представление промежуточного уровня – Gimple, внутреннее представление ассемблерного уровня – RTL [2]. Следует отметить, что в компиляторах уже давно решены почти все проблемы, связанные с построением внутреннего представления первых двух уровней, но это не значит, что реализация соответствующего ПО не составляет трудностей. Более того, разработка и реализация фаз компилятора, занимающихся построением этих представлений, требует значительных трудозатрат. Поэтому в исследовательских (а иногда и в коммерческих) проектах обычно используются соответствующие фазы свободно распространяемых компиляторов. Обычно их берут из Gcc.



Это связано и с тем, что в последнее время вокруг внутренних представлений различного уровня разрабатываются инфраструктуры, включающие API, упрощающие разработку программ, реализующих соответствующие трансформации (так, вокруг Gimple реализована инфраструктура TreeSSA [4], пользующаяся заслуженной популярностью у программистов). Вокруг нового представления LLVM [3], используемого в компиляторах компании Apple, которое разработано по мотивам JavaVM и имеет более низкий уровень, чем Gimple, но более высокий уровень, чем RTL, тоже реализована обширная инфраструктура, быстро завоевывающая популярность.

Наиболее предпочтительными для реализации и исследования новых методов и алгоритмов анализа и трансформации программ в настоящее время являются внутреннее представление Gimple и инфраструктура TreeSSA компилятора Gсс, исходя из следующих соображений:

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

Промежуточное представление Gimple является языково-независимым и машинно-независимым, а следовательно, трансформации программ, реализованные на нем с помощью Tree SSA, будут работать для всех языков и целевых архитектур, поддерживаемых компилятором Gcc. В настоящий момент поддерживаются языки C, C++, Fortran 95, Java, Ada и некоторые другие, а также большинство популярных архитектур (Intel x86, IBM PowerPC, Intel Itanium, Sun SPARC, ARM и т.д.).

Компилятор Gcc является стабильным компилятором промышленного уровня и используется как стандартный компилятор в UNIX-подобных системах, а также популярных дистрибутивах ОС Linux. Инфраструктура TreeSSA доступна в Gcc уже более трех лет и также является стабильной и хорошо отлаженной.

Работа над инфраструктурой, промежуточным представлением, а также другими частями компилятора (переводчиком с языков программирования в промежуточное представление и кодогенератором) ведется группой высококвалифицированных программистов из Red Hat, Novell, IBM, Intel, AMD, HP и ряда других компаний. Задача поддержки альтернативной инфраструктуры, сравнимой по набору возможностей и стабильности с TreeSSA, требует очень больших затрат труда высококвалифицированных программистов и представляется невыполнимой.

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

Далее в разделе будут рассмотрены некоторые методы анализа и трансформации программ, завоевавшие популярность в последнее время и нашедшие применение в новых исследованиях и программных продуктах: трансформации, основанные на распространении атрибутов и на решении задач о потоке данных, анализ алиасов, а также подходы к обнаружению и устранению избыточного кода (нумерация значений, частичная избыточность) [5,6].

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

Некоторые вопросы планирования команд для современных архитектур будут рассмотрены в разделе 3.

Можно выделить следующие типы анализов и трансформаций: выполняющиеся над отдельными инструкциями, локальные – выполняющиеся в пределах одного базового блока, глобальные – выполняющиеся на всей процедуре, межпроцедурные – выполняющиеся на нескольких процедурах [5, с.705, 1061]. Примером трансформации, выполняющейся над отдельной инструкцией, является сворачивание констант (вычисление выражений, все элементы которых константы). Как правило, эта трансформация используется вместе с распространением констант и копий, хотя иногда ее применяют и отдельно.

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

Среди глобальных трансформаций выделяют следующие:

основанные на анализе потока данных (удаление частичной избыточности, унификация выражений) [5, §9.5];

основанные на распространении атрибутов (удаление мертвого кода, распространение констант и копий, распространение диапазонов значений) [5, §§9.1, 9.4; 6, §12.5];

основанные на SSA-представлении [6, §8.11] (нумерация значений [6, §12.4]);

цикловые – трансформации, применяемые лишь к циклическим участкам кода программы [6, глава 14]. Можно выделить две группы цикловых трансформаций: (1) основанные на выделении индуктивных переменных (т.е.





таких, которые на каждой итерации цикла изменяются на постоянную величину) – вынос инвариантных выражений из циклов [6, §13.2], сокращение сложности вычислений (strength reduction), и (2) преобразования циклов и гнезд циклов, как правило, для достижения наилучшего использования кэша [5, глава 11]. Преобразования циклов, применяемые для распараллеливания программ, представляют собой отдельный большой класс трансформаций, рассмотрение которых выходит за рамки настоящего обзора.

Межпроцедурные трансформации можно разделить на два класса: глобальные трансформации, расширившие контекст применения до нескольких процедур (так, существует межпроцедурный анализ алиасов, распространение констант, распределение регистров), и трансформации, возможные только на межпроцедурном уровне – здесь наиболее ярким примером является встраивание процедур и оптимизация хвостовой рекурсии [6, §§15.2, 15.3]. Кроме того, межпроцедурные трансформации могут применяться как к процедурам из одного модуля, так и к процедурам из всех модулей программы (например, при связывании объектных модулей в один исполняемый файл программы). В последнем случае межпроцедурные трансформации особенно эффективны, т.к. опираются на максимально точную информацию о программе, однако время их выполнения может оказаться неприемлемо большим для промышленного применения.

При дальнейшем изложении мы будем пользоваться понятием графа потока управления процедуры [5, §8.4]. Базовым блоком будем называть четверку Bi, P, In, Out, где – номер (имя) базового блока, P – последовательность инструкций программы, составляющих блок Bi (по определению P может начать выполняться только с первой, а закончить – только на последней инструкции), In – множество входных переменных (переменных, определенных вне блока Bi, но используемых в нем), Out – множество выходных переменных (переменных, определенных в блоке Bi, но используемых вне него); отметим, что в отечественных публикациях базовые блоки иногда называются линейными участками. Графом потока управления для некоторой процедуры программы будем называть четверку V, E, Entry, Exit, где V – множество E V V вершин графа, соответствующих базовым блокам процедуры, – множество дуг, соответствующих передачам управления между базовыми блоками, Entry и Exit – две специально выделенных вершины, соответствующие базовым блокам, представляющим соответственно точку входа управления и точку выхода управления из процедуры.

2.2. Трансформации, основанные на анализе потока данных Задачей анализа потока данных является получение информации о том, каким образом некоторая процедура обрабатывает свои данные. Например, на основе информации о том, что в некоторой точке (инструкции) процедуры значение некоторой переменной всегда постоянно, можно заменить использования переменной в этой инструкции на значения соответствующей константы. Как правило, анализом рассматривается множество некоторых объектов (констант, переменных, выражений и т.п.), при этом необходимо для каждой точки процедуры определить множество «корректных» в некотором смысле объектов.

Рассмотрим в качестве примера задачу достигающих определений (reaching definitions) [5, пункт 9.2.4]. Определением переменной назовем присваивание этой переменной некоторого значения. Некоторое определение достигает данной точки процедуры, если существует путь выполнения между определением и данной точкой такой, что в этой точке переменная все еще содержит значение, присвоенное при определении. Для решения этой задачи рассмотрим граф потока управления программы, и для каждой вершины i графа определим четыре множества определений переменных: GEN(i) –определения, которые генерируются в базовом блоке Bi; KILL(i) – определения, которые переопределяются в базовом блоке Bi (т.е. той же переменной присваивается иное значение); REACHin(i) и REACHout(i) – определения, достигающие соответственно входа и выхода в базовый блок Bi. Тогда для каждой вершины графа потока управления будут верны следующие уравнения:

REACHout(i) = (REACHin(i)-KILL(i)) GEN(i), REACHin(i) REACHout( j).

jPr ed (i) Систему уравнений для всей процедуры можно решить, вычислив множества GEN и KILL для каждой вершины Bi по виду инструкции, а также положив для каждой вершины REACHin(i)=. После этого достаточно итеративно вычислять множества REACHin и REACHout для каждой вершины графа в порядке сверху вниз до тех пор, пока они не перестанут изменяться. Полученные множества REACHin дадут решение исходной задачи о достигающих определениях.

Также результаты анализа достигающих определений удобно представлять с помощью DU- и UD-цепочек [6, §8.10] – структур данных, связывающих определение некоторой переменной с его использованиями, а также использование переменной с достигающими его определениями. DU/UD-цепочки являются эффективным способом представления информации о потоке данных через переменные программы, поэтому на их основе часто строят трансформации, как показано в следующем разделе.

Аналогичным образом можно формулировать и более сложные задачи потока данных: необходимо задать множества объектов GEN и KILL для каждой вершины графа потока управления процедуры, а также определить, как связаны множества интересующих объектов DATAin (на входе) и DATAout (на выходе из вершины). Однако описанный выше итерационный процесс сойдется и даст требуемое решение не для любой задачи. Достаточным условием является монотонность функций потока, описываемых уравнениями для множеств DATAin.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.