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

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

Внутрипроцедурный анализ указателей, основанный на понятии "абстрактной ячейки памяти" (abstract memory location).

Анализ диапазонов для переменных целых типов.

Контекстно-зависимый (context-sensitive) и потоково-зависимый (flow-sensitive) межпроцедурный анализ.

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

Анализ указателей (alias analysis) [10] позволяет для каждой переменной указательного типа в каждой точке программы построить множество объектов, на которые он может указывать. В языке Си анализ указателей является необходимым шагом для выполнения практически любого оптимизирующего преобразования. Кроме того, анализ указателей для языка Си осложняется неразличимостью указателей и массивов, а также присутствием указательной арифметики.

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

Атрибуты абстрактной ячейки памяти, описанные выше, являются стати-ческими, то есть не изменяются всё время жизни абстрактной ячейки памяти.

В каждой точке программы с абстрактной ячейкой памяти могут быть связаны динамические атрибуты, которые описываются ниже.

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

При выполнении операций над интервалами, в особенности операций слияния значений в точках слияния потока управления, может возникнуть ситуация, когда результирующее множество целых значений состоит из нескольких непересекающихся интервалов, например [1,2]+[6,15]. В этом случае берётся минимальный интервал, включающий в себя все непересекающиеся интервалы, то есть в данном случае результатом будет интервал [1,15].

Значения указательных типов представляются множествами пар (AML, offset), где AML - абстрактная ячейка памяти, а offset - смещение от начала ячейки, которое имеет мета-тип M_Integer, то есть представляет собой диапазон смещений указателя внутри данного объекта. Кроме того, поддерживается значение Undef для неопределённых (неинициализированных) переменных, значение Any(type), если указательное выражение может принимать произвольное значение типа type, и значение Any, если указательное выражение может принимать произвольное значение. Значения Any могут возникать как результат слияния значений переменных в точках слияния потока управления, вследствие ограниченной глубины анализа объектов в динамической памяти, и когда указательное значение возвращается функцией, для которой не существует исходного кода и не специфицированы аннотации.

Внутрипроцедурный анализ указателей реализован по стандартной схеме итеративного прямого анализа потоков данных процедуры [11]. Для каждой инструкции процедуры на основании входящих динамических атрибутов абстрактных ячеек памяти вычисляются выходящие атрибуты, которые затем подаются на вход следующей инструкции. В точке слияния потока управления выполняется операция слияния динамических атрибутов (join). Анализ выполняется итеративно до тех пор, пока множества динамических атрибутов не перестанут изменяться.

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

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

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

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

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

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

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

Язык аннотаций строится на расширении синтаксиса языка Си, уже применяющемся в широко распространённом компиляторе GCC. Так, для спецификации того, что возвращаемое значение некоторой функции foo находится в интервале [0,5] используется следующая конструкция:

int foo(int x) __attribute__ ((post(foo >= 0 && foo <= 5)));

Здесь __attribute__((...)) - это синтаксическое расширение GNU C, поддерживаемое нашим инструментальным средством, post - специальный атрибут, позволяющий определять постусловие для функции, а имя функции foo используется в постусловии для обозначения значения, возвращаемого этой функцией. Кроме того, реализуется специальная поддержка для стандартного макроса assert.

Результаты экспериментов

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

Таблица 6. Результаты запуска инструментального средства

В этой таблице, в столбце "Total" приведено общее количество сообщений об обнаруженных ошибках, выведенных нашим инструментальным средством. В столбце "True" дано количество сообщений, указывающих на действительные проблемы в коде. В столбце "Possible" дано количество сообщений, истинность или ложность которых мы не смогли подтвердить из-за недостатка информации о программе. В столбце "False" дано количество ложных срабатываний. Наконец, в столбце "FlexeLint" дано количество истинных сообщений об ошибке, выявленных инструментальным средством FlexeLint.

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

Интегрированная среда

Все направления исследований, описанные в настоящей статье реализуются на базе единой интегрированной среды для изучения алгоритмов анализа и опти-мизации программ [1]. IRE является системой с открытыми исходными кодами и распространяется на условиях Общей публичной лицензии GNU (GNU General Public License). Система доступна для загрузки из сети Интернет [4]. Интегрированная среда построена как набор связанных друг с другом инструментов, работающих над общим промежуточным представлением программ MIF. Для управления инструментами ИС предоставляется графический интерфейс пользователя.

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

Состав среды

Программа на языке Си транслируется в промежуточное представление с помощью компонента "Анализатор Си в MIF". В настоящее время поддерживается стандарт ISO C90 и некоторые расширения GNU. Чтобы обеспечить независимость интегрированной среды от деталей реализации стандартной библиотеки Си для каждой конкретной платформы и обеспечить возможность корректной генерации программы на Си по её внутреннему представлению, анализатор использует собственный набор стандартных заго-ловочных файлов (stdio.h и т. д.). На уровне стандартной библиотеки полностью поддерживается стандарт ISO C90 и некоторые заголовочные файлы POSIX. Внутреннее представление программы находится в памяти инте-грированной среды, но возможно сохранение внутреннего представления в файле.

Компонент "Генератор MIF ->C" позволяет по программе во внутреннем представлении получить программу на языке Си. При генерации программы корректно генерируются директивы #include для всех использованных в исходной программе системных заголовочных файлов. Для проведения полустатического анализа программ генератор поддерживает несколько типов инструментирования программы. Инструментирование программы заключается во внесении в ее текст специальных операторов, собирающих информацию о ходе выполнения программы. В настоящее время генератор поддерживает инструментализацию программы для сбора полных трасс выполнения программы, профилирование базовых блоков и дуг, профилирование значений. Собранные в результате выполнения инструментированной программы профили выполнения могут впоследствии использоваться для анализа и преобразования программ.

Компоненты "Анализаторы" реализуют различные методы статического и полустатического анализа программ. При этом сама программа не трансформируется, а во внутреннее представление программы добавляется полученная в результате выполнения анализа информация. В интегрированной среде эти компоненты доступны посредством пункта меню Analyze. Например, алгоритм разбиения программы на базовые блоки, доступный через пункт меню Mark basic blocks, строит граф потока управления программы, создаёт соотвествующие структуры данных в памяти системы и добавляет ссылки на построенный граф в структуры данных внутреннего представления программы.

Компоненты "Трансформаторы" реализуют различные преобразования программ. При этом результатом работы компонента трансформации является новая программа во внутреннем представлении, для которой в интегрированной среде создаётся новое окно. Исходная программа сохраняется неизменной. Трансформационные компоненты доступны в интегрированной среде посредством пунктов меню Optimize, Transform и Obfuscate в зависимости от класса преобразования.

Компоненты "Визуализаторы" реализуют различные алгоритмы визуализации информации о программе. Эти компоненты доступны посредством пункта меню Vizualize интегрированной среды.

Промежуточное представление

Промежуточное представление MIF используется всеми инструментами интегрированной среды. Оно является представлением среднего уровня и спроектировано таким образом, чтобы представлять программы, написанные на широком спектре процедурных и объектно-ориентированных языков программирования.

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

Заключение

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

Накопление библиотеки алгоритмов позволяет с успехом применять интегрированную среду в учебном процессе факультетов ВМиК МГУ и ФПМЭ МФТИ. Студенты, выполняя курсовые и дипломные работы, получают в своё распоряжение развитый инструментарий методов анализа и оптимизации, на основе которых они могут реализовывать новые методы анализа и оптимизации. После включения в интегрированную среду результаты работы станут доступны для дальнейшего использования. Другое учебное применение интегрированной среды заключается в использовании её в качестве пособия для изучающих курсы по методам анализа и оптимизации программ.

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

Список литературы

А. В. Чернов. Интегрированная инструментальная среда Poirot для изучения методов маскировки программ. Препринт Института системного программирования РАН. М.: ИСП РАН, 2003.

A. Chernov. A New Program Obfuscation Method. In Proceedings of the Adrei Ershov Fifth International Conference "Perspectives of Systems Informatics". International Workshop on Program Understanding, Novosibirsk, July 14-16, 2003.

A. Chernov, A. Belevantsev, O. Malikov. A Thread Partitioning Algorithm for Data Locality Improvement. To appear in Proceedings of Fifth International Conference on Parallel Processing and Applied Mathematics (PPAM 2003), Czestochowa, Poland, September 7-10, 2003.

The IRE Home Page. http://www.ispras.ru/groups/ctt/ire.html

J. E. Moreira. On the implementation and effectiveness of autoscheduling for shared-memory multiprocessors. Ph.D. thesis, Department of Electrical and Computer Engineering, Univ. of Illinois at Urbana-Champaign, 1995.

J. G. Steffan, C. B. Colohan, A. Zhai, and T. C. Mowry. Improving Value Communication for Thread-Level Speculation. Computer Science Department Carnegie Mellon University. 2002.

SUIF Compiler System Group (http://suif.stanford.edu)

M. E. Wolf and M. Lam. A data locality optimizing algorithm. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Totonto, CA, June 1991.

X. Tang, J. Wang, K. Theobald, and G. R. Gao. Thread partitioning and scheduling based on cost model. ACAPS Tech. Memo 106, School. of Computer Science, McGill University, Montreal, Quebec. Apr. 1997.

R. P. Wilson, M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 1-12, June 1995.

S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

D. Wagner, J. S. Foster, E. A. Brewer, A. Aiken. A First Step towards Automated Detection of Buffer Overrun Vulnerabilities. In Proceedings of Network and Distributed System Security Symposium, pages 3-17, February 2000.