автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка методики автоматического обнаружения уязвимостей в исходном коде программ на языке Си

Московский государственный университет им. М.В.Ломоносова

На правах рукописи

Маликов Олег Рустэмович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДИКИ АВТОМАТИЧЕСКОГО ОБНАРУЖЕНИЯ УЯЗВИЫОСТБЙ В ИСХОДНОМ КОДЕ ПРОГРАММ НА ЯЗЫКЕ СИ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2006

ОБЯЗАТЕЛЬНЫЙ БЕСПЛАТНЫЙ ЭКЗЕМПЛЯР

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета Ям. М.В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

кандидат физико-математических наук, доцент

Гайсарян Сергей Суренович.

доктор физико-математических наук Галатенко Владимир Антонович; кандидат физико-математических наук Щокуров Александр Владимирович,

Ведущая организация:

Вычислительный центр имени А.А.Дородницына Российской академии наук

Защита диссертации состоится 22 декабря 2006 г. в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу; 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ. С текстом автореферата можно ознакомиться на портале ВМиК МГУ им. М.В.Ломоносова http://cs.msu.su в разделе «Наука»-«Работа диссертационных советов»-«Д 501.001.44».

Автореферат разослан 21 ноября 2006 г.

Ученый се!фетарв диссертационного совета

профессор СТпг^ Н.П. Трифонов

Общая характеристика работы

Актуальность.

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

По оценкам NIST (национального института стандартов и технологий США) общий годовой ущерб США от недостаточного обеспечения информационной безопасности составляет порядка 60 миллиардов долларов в год, причем ущерб в 20 миллиардов долларов может быть устранен при помощи специально разрабатываемых программных инструментов, обнаруживающих уязвимости в программном обеспечении на ранних стадиях жизненного цикла программного обеспечения.

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

Согласно последнему отчету компании Symantec около 69% всех уязвимостей связаны с технологиями web-приложений, являющихся главным источником мест несанкционированного проникновения в компьютерную систему. Также в отчете отмечается изменение характера угроз. Организаторы атак постепенно отказываются от крупных, многоцелевых атак, направленных против периметра сети, и все чаще осуществляют поиск и использование уязвимостей в конкретном системном программном обеспечении.

нчиои,

■ ^ifSIIIUITi л t ( -RortoiVt.

!_

Следует отметить, что согласно отчету Symantec обнаруженная уязвимость в среднем остается не исправленной в течение 42 дней.

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

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

• Исследование проблемной области, существующих подходов и инструментов статического обнаружения уязвимостей.

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

• Обоснование корректности и применимости разработанной методики для анализа реальных программ на языке Си.

• Разработка на базе методики статического анализатора, позволяющего проводить анализ достаточно больших программ.

Основные результаты.

Диссертационная работа содержит ряд результатов, обладающих научной новизной:

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

2. Разработан и обоснован многофазный алгоритм высокоточного обнаружения уязвимостей в исходном коде программ.

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

4. Экспериментальное сравнение разработанной программной системы обнаружения уязвимостей с существующими

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

Практическая ценность работы.

Разработан инструмент «Интегрированная среда поиска уязвимостей в исходном коде программ на языке Си», базирующийся на представленной в диссертационной работе методике. Инструмент позволяет в полностью автоматическом режиме осуществлять анализ исходного текста программы и обнаруживать уязвимости двух типов: «переполнение буфера» и «форматная строка».

Апробация работы.

Основные результаты работы опубликованы в статьях [1-6] и обсуждались на следующих конференциях, семинарах и выставках:

1, Конференция «Технологии Майкрософт в теории и практике программирования», Москва, март 4-5,2004,

2. Международная конференция «Programming Languages and Compilers», Лас-Вегас, июнь 27-30,2005.

■3. Международная конференция «Информационная безопасность-2005», Таганрог, июль 4-8,2005.

4. Международная конференция «Информационная безопасность-2006», Таганрог, июль 3-7,2006,

5. Конференция «Тихоновские чтения 2005», Москва, ВМиК МГУ им. М-ВЛомоносова, октябрь 24-28,2005.

6. Конференция «Тихоновские чтения 2006», Москва, ВМиК МГУ им. М.В.Ломоносова, октябрь 24-27,2006.

7. Научно-технические семинары ИСП РАН и ВМиК МГУ им. М.В. Ломоносова.

8. Выставка «CeBit-2006», Ганновер, март 9-15,2006.

Объем и структура диссертации.

Диссертация состоит из введения, шести разделов, заключения и списка литературы. Список источников насчитывает 86 наименований. Объем диссертации составляет 101 страница текста. Диссертация содержит 3 таблицы и 20 рисунков.

Краткое содержание работы

Во введении дается неформальное определение уязвимости, рассматриваются причины существования уязвимостей в программном

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

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

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

Уязвимости форматной строки возникают из-за недостаточного контроля за содержимым параметров функций форматного ввода-вывода семейства printf/scanf, стандартной библиотеки языка Си. Если пользователь программы может влиять на содержимое форматной строки, то возможно сформировать её таким образом, что по некоторым ячейкам памяти окажутся записанными указанные пользователем значения, что открывает возможности, например, для переписывания адреса возврата функции и исполнения кода, заданного пользователем.

В разделе 2 приводится обзор работ, имеющих отношение к теме диссертации, и их классификация. Дается описание средств динамического анализа и обнаружения уязвимостей в приложениях - FormatGuard, StackGuard, Valgrmd Memcheck и Intel Memory Checker. В обзоре приводится специальный тестовый пример, на котором рассматриваются возможности применения известных инструментов статического обнаружения уязвимостей (FlawFinder, ITS4, RATS, Pscan, BOON, UNO, FlexeLint). Основное внимание в обзоре уделяется средствам статического анализа программ, при этом классифицируются они по глубине производимого анализа:

• Алгоритмы лексического анализа

• Алгоритмы синтаксического анализа

в Алгоритмы, использующие спецификаторы типов

• Алгоритмы анализа потока данных

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

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

• потоково-чувствительные;

• потоково-нечувствительные.

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

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

• контекстно-чувствительный;

• контекстно-нечувствительный.

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

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

В разделе 3 определяются основные используемые понятия и методы.

Предлагаемая в работе модель представления объектов анализируемой программы основана на понятии абстрактного объекта памяти (АОП). АОП ставится в соответствие каждому объекту в памяти, который может быть создан во время работы программы. Целевым объектом АОП называется реальный объект программы, которому соответствует данный АОП.

АОП создаются для следующих целевых объектов программы:

• локальная или глобальная переменная или поле структуры;

• константная строка;

• место динамического выделения памяти.

Для моделирования целочисленных атрибутов АОП используется специальный тип М_1гЛедег, значения которого представляется следующим образом:

• (а, Ь), где а В этом случае объект может принимать любое целочисленное значение на отрезке от а до Ь. При этом а может принимать специальное значение "-«>", а Ь - "+<»".

• Специальное значение (Ч-оо, -со), представляющее собой пустое множество допустимых значений.

Операция сложения двух объектов типа М_1п£едег определяется так, как показано в таблице 1._

+ fell) (Mi) (-»(Ьг) <b,w) (+oo,-so)

(ll.ll) (ii+ъ, h+h) Oi+b,li+hz) (-«U+ВД (li+b,«0 (-00,CO) (+CO, -00)

(1ьЬ,) (I1+I2, hi+Ъ) (I1+I2, hi+h2) (-00, hi+h2) (I1+I2,«0 (-to, to) (+00, -00)

(-со, hi) (-СО, hi+l2) (-co, h|+h2) (-»,hi+h2) (-00,00) (-co, 00) (+00,-00)

0ь«>) Oi+Ь.«) Oi+b,») (-CO, 00) (li+lj, «) (-00, CO) (+«0, -co)

("«,<») (-00,00) (-00,») (-co, 00) (-00,00) (-00, CO) (+co, -co)

(+00,-00) (+00, -00) (+00,-00) (+co,-oo) (+0Э, -00) (+оэ, -00) (+00, -00)

Таблица 1. Таблица операции «+» для модельного типа

Кроме арифметических операций над значениями модельного типа, вводится специальная операция слияния U, которая выполняется в точках слияния потока управления из нескольких возможных путей для нахождения возможных значений переменной. Если вдоль одного пути переменная могла иметь значения из отрезка (li, h2), а вдоль другого -из отрезка (12, h2), то операция слияния возвращает ограничивающий отрезок - минимальный отрезок, содержащий оба отрезка-аргумента: (h, hi)U(h, h2) = (min(llr I2}, max(ht, h2)).

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

Атрибуты АОП, необходимые для поиска уязвимостей представляются в виде кортежа:

<паше, size, overlap, aset, len, value, input> в паше - уникальная строка-"имя" АОП.

« size - имеет тип M_Integer. Это размер, занимаемый АОП в байтах.

• overlap - представляет собой множество nap { (AML, Offset)}. Такой тип данных в дальнейшем будет называться AMLSet. AMLi представляет собой тот АОП, целевой объект которого может перекрываться при размещении в памяти с некоторым смещением Offsett типа M_mteger с целевым объектом АОП, которому принадлежит данный атрибут, о aset - множество AMLSet, содержащее АОП, на которые может указывать данный АОП с некоторым смещением Offset типа

M_Integer (так называемое points-to множество для данного АОП).

• 1еп - длина строки, которая содержится в данном АОП. Этот атрибут имеет тип M_lnteger.

• value - значение, хранящееся в данном АОП. Этот атрибут также имеет тип M_Integer.

• input - логический атрибут, принимающий значения TRUE/FALSE который показывает, что в данной точке программы значение целевого объекта для данного АОП может зависеть от ввода пользователя (либо от внешнего окружения программы, на которое может влиять пользователь). Атрибут используется при диагностике уязвимости форматной строки.

Определение 1. Контекстом называется множество кортежей атрибутов,

С={<namei,sizei,overlaps,asetuleni,valuei,lnputi> | i=l..N}

Поскольку атрибуты name, size, overlap для каждого АОП являются статическими и АОП однозначно определяется значением атрибута паше, то под СпятеСО будем понимать кортеж определенных в точке I атрибутов АОП, имеющего заданное значение атрибута паше.

Далее обозначения значений отдельных атрибутов АОП в некоторой точке I программы будут производиться в соответствии с первыми буквами имен атрибутов. Так, значение атрибута aset АОП, идентифицируемого атрибутом паше, в точке будет обозначаться как:

CiLeW, а атрибута input -

СмтеСО -

Определение 2. Полурешеткой называется множество L с введенной на нем операцией □ такой, что для V a,b,c^L выполняются следующие условия:

1. аОа^а (идемпотентность)

2. aUb^bQa (коммутативность)

3. аО(ЬОс)=(аОЬ)Пс (ассоциативность)

Определение 3. Порядок £ задается на множестве L для элементов a,b^L следующим образом:

a£b в том случае, если аОйай а <6 в том случае, если аОЬ=Ь и эфЬ.

Определение 4. Полурешетка обладает элементом единицей T*Lt если для V a^L выполняется: ТПэ=7.

Определение 5. Возрастающей цепочкой элементов полурешетки xi,x2,„.,xn называется последовательность XJ,X2,...,X„^L, такая, что для 1 £i<n верноXi< Xi+i.

Определение б. Полурешегка называется ограниченной, если для V В б; любая возрастающая цепочка в Ц начинающаяся сх имеет не более Ь элементов.

Определение 7. Введем понятие операции слияния контекстов и. Пусть даны контексты А и В, тогда слиянием Л и 8 называется контекст С, вычисляемый по следующим правилам:

С/ = А, и В, =< I, АЬ А?, А? и ВЛ и В\, АГ и вГ, А] и В1, >, где/=:*../V.

Для атрибутов азеЬ

А1~з1 = {(/ш оЯзе^) | к = 1.л}, 8? = эг = {(/а, t = l..m}

операция слияния и вводится следующим образом: а=а1Цаг=51ЦЗг\353, где

51={0т offsetlk\Joffset2t)\ :

5г={(11ь о/Йе&,;1 1<5<п : ИШ<.т

отеЬгь)I 1<Ь<т : Ь*!^

Рассмотрим множество всех контекстов Ц для анализируемой программы.

Утверждение 1. Множество контекстов £. обладает следующими свойствами:

• для V х,уе ¿. существует единственное ге I такое, что х11 У=г;

• для V имеет место идемпотентность операции и, т.е. хЦх=х;

• для V имеет место коммутативность операции и, т.е. хиу=у1)х;

• для V хгу,ге1 имеет место ассоциативность операции и, т.е. (хЦуЮг=хи(уИ2)

» существует максимальный элемент полурещетки - контекст такой, что для V х1)7=7. Утверждение 2. Множество контекстов с введенной на нем операцией слияния и является полурешеткой.

Утверждение 3. Полурешетка контекстов I является ограниченной. Определение 8. Говорят, что на полурешетке I введено отношение частичного порядка <, если для V х,у^1 хйу тогда и только тогда, когда хи у=у.

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

множество значений атрибутов соответствующего кортежа второго контекста.

Определение 9. Функция преобразования потока Р: называется монотонной, если для V таких, что х<,у выполняется утверждение:

Например, рассмотрим функцию F для оператора присваивания '1=0', действующей в рамках решетки контекстов. Смысл данной операции заключается в установлении значения АОП с целевым объектом i в 0, при этом множество aset устанавливается пустым, атрибут 1еп устанавливается в 0, поскольку, рассматривая данный объект как строку, его длина равна 0, зависимость от ввода пользователя при этом отсутствует, так что атрибут input равен false.

Утверждение 4, Функция преобразования потока F для инструкции присваивания li=0':

является монотонной.

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

Предлагаемая общая схема методики обнаружения уязвимостей в исходном коде программ состоит из нескольких групп алгоритмов.

Алгоритмы межпроцедурного анализа описаны в разделе 4.2.

Задачей межпроцедурного анализа является построение и поддержка модификации графа вызовов в процессе анализа. На контекстно-независимый межпроцедурный анализ также возлагается задача выбора стратегии обхода функций программы на каждой межпроцедурной итерации и задача отображения АОП фактических параметров вызова функции в АОП формальных параметров. В разделе 4.2 приводится также алгоритм анализа отдельной вершины графа вызовов.

Внутрипроцедурный анализ описан в разделе 4.1. На внутрипроцедурной стадии итеративно анализируется отдельная функция с заданным входным контекстом С. Задачей внутрипроцедурного анализа является начальное построение дерева областей функции, а также выбор порядка обхода отдельных инструкций на каждой внутрипроцедурной итерации. Общая схема внутрипроцедурного анализа показана на рисунке 1. Алгоритм является итеративным и по теореме Кама-Ульмана для обеспечения его сходимости достаточно обеспечить монотонность функций преобразования потока данных для всех инструкций функции.

F(x) < F(y).

<>,Х,,К ,{У,(0,0),(0,0),fa\se>, при /=/

Выходящий контекст

Рисунок 1. Схема алгоритлш внутрипроцедурного анализа

Определение 10. Графом потока управления функции F называется четверка В, entry, exit), где

/V - конечное множество вершин графа

Е — подмножество множества пар NxN, именуемое множеством ребер графа, при этом дня каждого ребра (х,у)*Е х называет предком у, а у -потомком х.

entry - начальная вершина графа (заголовок функции)

exit - единственная вершина графа, не имеющая потомков.

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

i= U ouruh

jePred(/)

здесь, в случае если ребро 0,1) - одна из ветвей условного перехода, под OUT(j) подразумевается та дуга графа потока управления, которая соединяет j с I.

Анализ инструкций и вызовов библиотечных функций является самым нижним уровнем общей методики обнаружения уязвимостей. На данном уровне происходит преобразование потока данных в соответствии с определенными функциями Flow дпя каждой инструкции.

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

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

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

Например, если в случае инструкции I='p ti]=0' имеет место:

Cp'<(^(ofo))h

то выполняется проверка условия:

cl>cl

что означает, что размер буфера s, на который указывает р, должен быть больше значения переменной 1.

Ошибки форматной строки обнаруживаются при анализе вызовов функций семейства printf/syslog. Предупреждение выдается, если у АОП, соответствующего форматной строке при вызове, атрибут input имеет значение TRUE, что означает, что аргумент форматной строки может зависеть от ввода пользователя, т.е. для объекта потенциальной форматной строки s безопасность выполнения операции с форматной строкой проверяется выполнением следующего условия:

c's = FALSE

Обратный анализ, описанный в разделе 4.4, заключается в выполнении обратного прохода по графу потока управления программы с

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

В разделе 5 приводится описание реализации предложенных для обнаружения уязвимостей методов.

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

В качестве входного текста среда поддерживает тексты на языке Си стандарта ISO С90. Также среда обладает набором базовых средств работы с внутренним представлением. В качестве внутреннего представления программы в программной среде используется представление MIF. Пример программы на языке Си, вычисляющей числа Фибоначчи, и соответствующего представления на языке MIF показан на рисунке 2.

int fib(int n) L2: DISPLAY

{ L3: VAR $int,n,

int а, b, o; END L2

a = 1) L4: DISPLAY

b = 1; L5: VAR $int,a,

if (n<=l)return 1; L6; VAR $int,b,

£or {; П > 1; n--) L7i VAR $int,с,

{ BHD L4

с = a + b; LS: FUHC $int,®l,L2,L2,L4,fib

а я b; LOAD LS,$int,1

b = с; LOAD LS,$int,l

} JGT L3,1,L22,

return с,- LOAD @1,$int,1

} JMP LS,

L22: JLE L3,1,L23,

ADD L7,LS,L6

MOVE LS, LS

MOVE L6,L7

DECR L3

JMP L22,

L23: MOVE @1,L7

L9: END LS

EXPORT L8,fib

Рисунок 2. Внутреннее представление MF.

Подготовка программы к анализу состоит из трех частей. Сначала программа на языке Си транслируется во внутреннее представление среднего уровня MIF, Транслятором поддерживается стандарт ISO С90, а также отдельные возможности стандарта ISO С99 (в частности, массивы переменного размера) и некоторые расширения GNU. На уровне стандартной библиотеки полностью поддерживается стандарт ISO С90 и некоторые заголовочные файлы POSEÍ.

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

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

Разработанный на основе предложенной методики программный инструмент обладает следующими характеристиками:

• Входной язык - Си

» Пакет размером 300000 строк кода анализируется около 27 часов на ПК Pentium-IV 2.бГГц

в Использует внутреннее представление MIF

• Графический интерфейс

• Возможность в интерактивном режиме исследовать пути возникновения уязвимостей

« Механизм подкачки результатов

• Язык программирования - Java

в Объем исходного кода инструмента - порядка 50000 строк

Результаты численных экспериментов обсуждаются в разделе 6.

В таблицах 2 и 3 показаны результаты анализа 12 пакетов свободно распространяемого ПО. Для каждого пакета приведены его название и номер версии, количество строк исходного кода пакета без учета пустых строк (колонка LOC), количество функций в пакете (колонка NOF), количество истинных, ложных предупреждений и общее количество предупреждений (колонки TP, FP и Total соответственно). Также приведена доля истинных предупреждений в процентах (колонка ТР%) и время работы анализа и объем памяти, занимаемый системой (колонки Time и Mem). В таблице 2 показаны результаты для двух видов уязвимостей - переполнение буфера и форматная строка, в среднем доля истинных предупреждений составила 35,1%.

Ргоггаш ьос МОР ТоЫ ТР ТР% ЕР Тнве, 5СС Мет, тЬ

Ыфй-1Л24 3126 114 10 4 40% 6 55,37 35,49

ШНр<3-0Л 934 17 12 10 83% 2 5,29 7,32

рц)4рше-1.7б 4003 68 69 28 41% 41 39,67 39,72

ро1ушогрЬ-0.4.0 605 15 4 3 75% 1 3,47 3,61

&йрс1-2.23Ъ 1701 36 26 6 23% 20 318,98 67,40

з11агиШ5-4.2.1 6015 70 6 4 67% 2 33,43 34,36

Б5ПИр-2.бО 2224 33 4 1 25% 3 26,34 12,95

5игйюаг<1-1Л.8 718 18 14 5 36% 9 4,89 6,76

|рыр-1,2.4 5832 111 21 4 19% 17 103,71 50,08

нои-йра-иб 2354 50 24 4 17% 20 74,67 23,65

сй^егс!-1.4.3 3699 233 14 4 29% 10 127,95 55,64

рсге-3.9 5625 80 7 1 14% 6 624,61 67,48

ТоЫ 36836 845 211 74 35Д% 137 1418^8 404,46

Табмща 2, результаты работы дляуязвимостей защиты

Рп^гат ЬОС Ж)Р ТоЫ ТР ТР% РР Типе, $ес Мет, тЬ

Ьйр<1-1.0.24 3126 114 128 86 67% 42 55,37 35,49

ШПрсЮЛ 934 17 55 53 96% 2 5,29 7,32

pgp4pine-l,7б 4003 68 93 63 68% 30 39,67 39,72

ро1утогрЫ)А0 605 15 10 9 90% 1 3,47 3,61

Шйр<1-2.23Ь 1701 36 182 44 24% 138 318,98 67,40

8ЬапиЩ-4.2Д 6015 70 52 8 15% 44 33,43 34,36

Бзтф-2.б0 2224 33 34 16 47% 18 26,34 12,95

зигй)оаг(1-1.1.8 718 18 33 23 70% 10 4,89 6,76

цар-1.2.4 5832 111 28 8 29% 20 103,71 50,08

1го11-йр<М.2б 2354 50 37 11 30% 26 74,67 23,65

с&щегеИ.4.3 3699 233 206 169 82% 37 127,95 55,64

рсге-3.9 5625 80 112 28 25% 84 624,61 67,48

ТоЫ 36836 845 970 518 53,4% 452 141838 404,46

Таблица 3, результаты работы для дополнительных ошибок

Таблица 3 соответствует результатам, полученным для двух типов уязвимостеб и дополнительных видов ошибок разыменования неопределенного или нулевого указателя и утечек памяти. В этом случае доля истинных предупреждений составила 53,4%.

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

На базе описанной методики по контракту с федеральным агентством по науке и инновациям РФ был разработан инструмент обнаружения уязвимостей, который был представлен на выставке СеВи-2006, проходившей в г. Ганновере в марте 2006-го года.

Разработанный на базе описанной в диссертационной работе методики инструмент был внедрен в Институте системного программирования Российской академии наук и на факультете ВМиК МГУ им. М.В. Ломоносова, в будущем предполагается осуществить внедрение в Научно-исследовательском вычислительном центре при МГУ им. М.В. Ломоносова.

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

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

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

• Расширение методики за счет использования пользовательских аннотаций исходного текста программы.

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

Основные результаты работы

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

2. Разработан и обоснован многофазный алгоритм высокоточного обнаружения уязвимостей в исходном коде программ.

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

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

Работы автора по теме диссертации

1. Маликов O.P., Автоматическое обнаружение уязвимостей в исходном коде программ, Известия ТРТУ, №4, с. 48-53,2005

2. Несов B.C., Маликов O.P., Использование информации о линейных зависимостях для обнаружения уязвимостей в исходном коде программ, Труды ИСП РАН, №9, с. 51-57,2006

3. Маликов O.P., Несов B.C., Автоматический поиск уязвимостей в больших программах, Известия ТРТУ, Тематический выпуск ((Информационная безопасность», Ка7 (62), с. 114-120,2006

4. Oleg Malikov, Andrey Belevantsev, Using Data Flow Analysis for Detecting Security Vulnerabilities, PLC05: Proceedings of the International Conference on Programming Languages and Compilers, 2005

5. Маликов O.P., Белеванцев A.A., Автоматическое обнаружение уязвимостей в программах, Материалы конференции «Технологии Майкрософт в теории и практике программирования», Москва, 2004

6. Гайсарян С.С., Чернов A.B., Белеванцев A.A., Маликов O.P., Мельник Д.М., Меньшикова A.B., О некоторых задачах анализа и трансформации программ, Труды ИСП РАН, Xs5, с.7-41,2004

Напечатано о готового оригинал-макета

Издательство ООО "МАКС Пресс" ЛтшзияИДИ 00510 ot01.12.99 г. Подписано к печати 17.11.2006 г. Формат 60x901/16.Усл.псчл, 1,0. Тираж 70 экз. Заказ 811. Тел. 939-3890. ТелУФакс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-Й учебный корпус, 627 к.

Введение.

1. Постановка задачи.

2. Обзор работ и классификация.

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

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

2.3 Использование спецификаторов типов.

2.4 Анализ потока данных.

3. Используемые понятия и методы.

3.1 Абстрактный объект памяти (АОП).

3.2 Модельный целочисленный тип.

3.3 Атрибуты АОП.

3.4 Полурешетка контекстов.

4. Общая схема методики поиска уязвимостей.

4.1 Внутрипроцедурный анализ.

4.1.1 Представление функции.

4.1.2 Анализ циклов.

4.1.3 Компактное представление потока данных.

4.1.4 Алгоритм работы с представлением потока данных.

4.1.5 Вычисление контекстов инструкций.

4.1.6 Инструкции увеличения счетчика в цикле.

4.1.7 Условные переходы.

4.1.8 Прямые вызовы функций.

4.1.9 Вызовы функций по указателю.

4.1.10 Остальные инструкции.

4.1.11 Входной и выходной контексты функции.

4.2 Межпроцедурный анализ.

4.2.1 Общий межпроцедурный алгоритм.

4.2.2 Стратегия обхода графа вызовов.

4.2.3 Анализ вершины графа вызовов.

4.2.4 Интерфейс для внутрипроцедурного анализа.

4.3 Обнаружение уязвимостей на основе вычисленных атрибутов.

4.4 Реализация уточнения уязвимостей и обнаружения их источников

5. Реализация методов.

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

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

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

С 1983 по 1988 год Министерство обороны США и Национальный комитет компьютерной безопасности разработали систему стандартов в области компьютерной безопасности, известную как «Оранжевая книга»[46]. В рамках этих стандартов операционные системы делятся на 4 основных класса - А, В, С, D:

• Класс D. К данному классу относятся все системы, не удовлетворяющие требованием более высокого класса. Примерами таких ОС являются MS-DOS[48], Palm OS[47].

• Класс С. Имеет подклассы С1 и С2:

• Подкласс С1. Требуется наличие избирательного разграничения доступа и подсистемы аутентификации при начале работы с ОС. К операционным системам данного подкласса относятся ранние версии UNIX[50], IBM RACF[49].

• Подкласс С2. ОС должна удовлетворять требованием подкласса

С1. Кроме того, все субъекты и объекты ОС должны иметь идентификаторы. Запрещены действия субъектов, способные нарушить безопасность системы. Вся информация, удаляемая из оперативной памяти и с внешних носителей, не может быть доступна в дальнейшем ни одному субъекту. VMS[51], IBM 3

C)S/400[52](c некоторого времени называется i5/OS), Windows NT[53], Novell NetWare 4.11 [54] являются примерами ОС, относящихся к данному подклассу.

• Класс В. Имеет подклассы В1, В2, ВЗ:

• Подкласс В1. Кроме того, поддерживается разграничение доступа к объектам ОС на основе полномочий. К данному подклассу относятся ОС HP-UX BLS, Cray Research Trusted Unicos 8.0, Digital SEVMS, Harris CS/SX, SGI Trusted IRIX[57].

• Подкласс B2. ОС должна удовлетворять требованиям подкласса В1. Подсистема защиты ОС должна иметь формально определенную и хорошо документированную модель безопасности. Интерфейс подсистемы защиты должен быть четко и формально определен. Более жесткие по сравнению с подклассом В1 требования к разграничению доступа. Существует по крайней мере одна ОС - Multics[55], принадлежащая к этому подклассу.

• Подкласс ВЗ. ОС должна удовлетворять требованиям подкласса В2. Должны иметься средства восстановления после сбоев без нарушения защиты. Для произвольного управления доступом должны использоваться списки с указанием разрешенных режимов. Единственной известной на данный момент ОС подкласса ВЗ является XTS-300[56].

• Класс А. Должно иметься формальное доказательство модели подсистемы безопасности и доказательство того, что реализация соответствует модели. К данному классу относятся специализированные ОС Boeing MLS LAN, Gemini Trusted Network Processor, Honeywell SCOMP.

Принадлежащие к классу D системы являются самыми незащищенными, в то время как для систем класса А безопасность должна быть доказана формально. Наиболее существенная разница с точки зрения безопасности находится между классами В и С. Так, операционные системы класса В должны поддерживать маркировку и проверку доступа для всех объектов системы - будь то внешние накопители или отдельные объекты в оперативной памяти. Например, отличие между классами В и С состоит в том, что в рамках ОС класса С имеется возможность делегировать только полностью все полномочия суперпользователя, а не часть полномочий для выполнения той или иной операции, как это должно быть для ОС класса В. Первой ОС имеющей класс В2 (основные классы безопасности разбиты на подклассы) была операционная система Multics.

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

Отдельно стоит сказать о безопасности сетевых подсистем операционных систем, которые практически никак не нашли отражения в «Оранжевой книге», хотя в последнее время именно сетевые коммуникации стали средой возникновения большей части уязвимостей ОС. Многие проблемы, появившиеся в связи с возможностью удаленного доступа, не осознавались во время проектирования операционной системы UNIX, разрабатывавшейся в 60-70-х годах 20-го века, когда не существовало локальных сетей и сети Интернет. Естественно, что операционные системы семейства UNIX, Windows и др. создавались с учетом необходимой функциональности и достижения определенной производительности, в связи с чем, к примеру, невозможно было обеспечить идеальную систему разграничения прав доступа в рамках операционной системы.

Первым известным случаем использования уязвимостей в программном обеспечении был вирус Морриса. В 1988-м году студентом Карнельского университета Робертом Моррисом была написана программа, использующая уязвимость типа «переполнение буфера» в программном коде сервиса fingerd операционной системы 4.3BSD. Вирус использовал данную уязвимость для получения контроля над атакуемым компьютером, сканирования локальной сети и распространения своего тела на другие компьютеры, на которых имелась данная уязвимость.

Программный код системного демона fingerd содержал в себе примерно такие же строки, как и изображенные на рисунке 1. void f () { char buf[512]; gets(buf);

Рисунок 1. Примерный фрагмент кода демона fingerd.

Библиотечная функция gets считывает в буфер по адресу первого параметра buf строку символов со стандартного ввода. При этом длина строки никак не контролируется. На рисунке 2 упрощенно показано расположение данных на стеке в момент вызова функции f, характерное для подавляющего большинства операционных систем. Адрес возврата соответствует адресу, по которому будет передаваться управление после окончания выполнения кода функции f. Легко заметить, что адрес возврата из функции располагается за локальным массивом s и в начале выполнения функции f указывает на некоторый корректный код выполняемой программы. Таким образом, в случае если функция gets считает строку длиною больше 512 байт, возникнет ставшая классической ситуация «переполнения буфера», когда введенные пользователем данные, записываемые в строку s «заденут» адрес возврата. Моррису оставалось лишь подобрать вводимую пользовательскую строку таким образом, чтобы адрес возврата указывал на необходимый участок программного кода. Таким кодом в случае вируса Морриса было выполнение командного интерпретатора с правами суперпользователя, что позволяло выполнить любые операции на пораженной вирусом машине.

Направление роста адресов -►

Локальный массив s

Направление роста стека

Рисунок 2. Схематичное расположение данных на стеке.

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

Именно поэтому большинство UNIX-подобных операционных систем имеет класс безопасности по терминологии «Оранжевой книги» не выше С1. Заметим, что такой механизм не может иметь места в ОС класса В и выше.

В ОС семейства UNIX изначально существует механизм SUID-процессов. Наличие флага SUID у исполняемого файла означает, что при запуске файл будет наследовать права его владельца, а не того пользователя, который его запускает. Такой механизм крайне опасен, так как в случае, если в программе с таким флагом имеется ошибка, позволяющая совершить некие непредусмотренные действия, то они могут быть совершены с гораздо более высокими правами, чем те, которые имеет запускающий программу пользователь. Если же владельцем программы являлся суперпользователь (как часто и бывает), то круг возможных действий пользователя после использования ошибки в программе становится неограниченным.

Другие распространенные операционные системы также имеют похожие механизмы, нарушающие идеальную модель разграничения прав. Поэтому некоторые ОС семейства Windows, а также ОС Solaris[61] имеют класс безопасности С2, что недостаточно для гарантии отсутствия уязвимых механизмов операционной системы.

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

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

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

• Угрозы компьютерным системам и сетям все возрастают

• Возрастает размер ущерба, вызванного злоумышленными атаками

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

По оценкам NIST [7] (национального института стандартов и технологий США), общий годовой ущерб США от недостаточного обеспечения информационной безопасности составляет порядка 60 миллиардов долларов в год, причем ущерб в 20 миллиардов долларов может быть устранен при помощи специально разрабатываемых программных инструментов, обнаруживающих уязвимости в программном обеспечении на самых ранних стадиях жизненного цикла программного обеспечения.

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

Согласно последнему отчету компании Symantec[8] около 69% всех уязвимостей связаны с технологиями web-приложений, являющихся главным источником мест несанкционированного проникновения в компьютерную систему. Также в отчете отмечается изменение характера угроз. Организаторы атак постепенно отказываются от крупных, многоцелевых атак, направленных против периметра сети, и все чаще осуществляют небольшие, фокусированные атаки против клиентских систем. На общей ситуации безопасности будет сказываться появление новых типов угроз, таких как сети бот-модулей, настраиваемые модульные вредоносные коды, а также атаки, направленные против веб-приложений и веб-браузеров. Если раньше традиционные атаки организовывались из любопытства и из-за желания атакующего проявить собственное техническое мастерство, то теперь во многих случаях современные атаки объясняются стремлением получить выгоду. Вполне логично, что в 2005 году основной целью атак с использованием уязвимостей впервые стали предприятия финансовой сферы. Далее по количеству направленных против них атак идут образовательные и правительственные учреждения.

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

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

• Исследование проблемной области, существующих подходов и инструментов статического обнаружения уязвимостей.

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

• Обоснование корректности и применимости разработанной методики для анализа реальных программ на языке Си.

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

Основные результаты. Диссертационная работа содержит ряд результатов, обладающих научной новизной:

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

2. Разработан и обоснован многофазный алгоритм высокоточного обнаружения уязвимостей в исходном коде программ.

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

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

Практическая ценность работы.

Разработан инструмент «Интегрированная среда поиска уязвимостей в исходном коде программ на языке Си», базирующаяся на представленной в диссертационной работе методике. Инструмент позволяет в полностью автоматическом режиме осуществлять анализ исходного текста программы и обнаруживать уязвимости двух типов: «переполнение буфера» и «форматная строка».

Апробация работы.

Основные результаты работы опубликованы в статьях [1-6] и обсуждались на следующих конференциях, семинарах и выставках:

1. Конференция «Технологии Майкрософт в теории и практике программирования», Москва, март 4-5,2004.

2. Международная конференция «Programming Languages and Compilers», JIac-Berac, июнь 27-30,2005.

3. Международная конференция «Информационная безопасность-2005», Таганрог, июль 4-8,2005.

4. Международная конференция «Информационная безопасность-2006», Таганрог, июль 3-7,2006.

5. Конференция «Тихоновские чтения 2005», Москва, ВМиК МГУ им. М.В.Ломоносова, октябрь 24-28,2005.

6. Конференция «Тихоновские чтения 2006», Москва, ВМиК МГУ им. М.В.Ломоносова, октябрь 24-27,2006.

7. Научно-технические семинары ИСП РАН и ВМиК МГУ им. М.В. Ломоносова.

8. Международная выставка «CeBit-2006», Ганновер, март 9-15,2006.

Краткое содержание работы.

Диссертация состоит из введения, шести разделов и заключения. Список источников насчитывает 86 наименований. Диссертация содержит 3 таблицы и 20 рисунков.

Основные результаты диссертационной работы опубликованы в [1]-[6].

На базе описанной методики по контракту с Федеральным агентством по науке и инновациям РФ был разработан инструмент обнаружения уязвимостей, который был представлен на выставке CeBit-2006[64], проходившей в г. Ганновере в марте 2006-го года.

Разработанный на базе описанной в диссертационной работе методики инструмент был внедрен в Институте системного программирования Российской академии наук и на факультете ВМиК МГУ им. Ломоносова, в будущем предполагается осуществить внедрение в Научно-исследовательском вычислительном центре при МГУ им. М.В. Ломоносова.

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

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

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

• Расширение методики за счет использования пользовательских аннотаций исходного текста программы.

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

Заключение

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

Основными результатами диссертационной работы являются:

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

2. Разработан и обоснован многофазный алгоритм высокоточного обнаружения уязвимостей в исходном коде программ.

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

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

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

• Утечка памяти

• Неинициализированный указатель

Средняя доля истинных предупреждений в этом случае составила около 53% (Таблица 3).

1. Маликов О.Р., Автоматическое обнаружение уязвимостей в исходном коде программ, Известия ТРТУ, №4, с. 48-53,2005

2. Несов B.C., Маликов О.Р., Использование информации о линейных зависимостях для обнаружения уязвимостей в исходном коде программ, Труды ИСП РАН, №9, с. 51-57,2006

3. Маликов О.Р., Несов B.C., Автоматический поиск уязвимостей в больших программах, Известия ТРТУ, Тематический выпуск «Информационная безопасность», №7 (62), с. 114-120,2006

4. Oleg Malikov, Andrey Belevantsev, Using Data Flow Analysis for Detecting Security Vulnerabilities, PLC'05: Proceedings of the International Conference on Programming Languages and Compilers, 2005

5. Маликов O.P., Белеванцев A.A., Автоматическое обнаружение уязвимостей в программах, Материалы конференции «Технологии Майкрософт в теории и практике программирования», Москва, 2004

6. Гайсарян С.С., Чернов А.В., Белеванцев А.А., Маликов О.Р., Мельник Д.М., Меньшикова А.В., О некоторых задачах анализа и трансформации программ, Труды ИСП РАН, №5, с.7-41,2004

7. National Institute of Standards and Technology, The Economic Impacts of the Inadequate Infrastructure for Software Testing, May, 2002, http://www.nist.gov/director/prog-ofc/report02-3.pdf

8. Symantec, Symantec Internet Security Threat Report, Volume IX, March, 2006, httп://www.symantec.com/enteфrise/threatreport/index.isp

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

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

11. Steve Bellovin, Buffer Overflows and Remote Root Exploits, Personal Communications, October, 1999

12. Колищак А., Атаки на переполнение буфера, ноябрь, 1999, http://securitv.nnov.ru/articles/bo.asp

13. Tim Newsham, Format String Attacks, September, 2000, http://www.thenewsh.com/~newsham/format-string-attacks.pdf

14. David Wheeler, Flawfinder Home Page, http://www.dwheeler.com/flawfinder/

15. J. Viega, J.T. Bloch, T. Kohno, and G. McGraw, ITS4: A Static Vulnerability Scanner for С and С++ Code, In Proceedings of the 16th Annual Computer Security Applications Conference, December, 2000

16. RATS checker, http://www.securesoftware.com/downloadrats.htm

17. PScan Home Page, http://www.striker.ottawa.on.ca/~aland/pscan/

18. Umesh Shankar, Kunal Talwar, Jeffrey S. Foster, and David Wagner, Detecting Format String Vulnerabilities with Type Qualifiers, In Proceedings of the 10th Usenix Security Symposium, Washington, D.C., August, 2001

19. The Perl Directory, http://www.perl.org

20. J. S. Foster, R. Johnson, J. Kodumal, T. Terauchi, U. Shankar, K. Talwar, D. Wagner, A. Aiken, M. Elsman, and C. Harrelson, Cqual: A tool for adding type qualifiers to C, http://www.cs.umd.edu/~jfoster/cqual/, 2003

21. N. Dor, M. Rodeh, and M. Sagiv, Cleanness checking of string manipulations in С programs via integer analysis, In Static Analysis Symposium,volume 2126 of Lecture Notes in Computer Science, pages 194--212. Springer Verlag, June 2001

22. D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken, A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities, In Proceedings of 7th Network and Distributed System Security Symposium, February, 2000

23. BOON Home Page, http://www.cs.berkeley.edu/~daw/boon/

24. Uno Tool Synopsis, http://spinroot.com/uno/

25. Gerard J.Holzmann, UNO: Static Source Code Checking for User-Defined Properties, in Proc. 6th World Conference on Integrated Design and Process Technology (IDPT2002), 26-30 June 2002, Pasadena, CA

26. D. Larochelle and D. Evans, Statically detecting likely buffer overflow vulnerabilities, In USENIX Security Symposium, pages 177-190,2001

27. Splint Home Page, http://lclint.cs.virginia.edu/

28. W. R. Bush, J. D. Pincus, and D. J. Sielaff, A static analyzer for finding dynamic programming errors, In Proceedings of Software Practice and Experience, pages 775-802,2000

29. A. Milanova. Precise and Practical Flow Analysis of Object-Oriented Software. PhD thesis, Rutgers University, Available as Techical Report DCS-TR-539, August, 2003

30. J. B. Kam and J. D. Ullman, Monotone data flow analysis frameworks, Acta Informatica, vol. 7, pp. 305-317,1977, Springer-Verlag

31. Flexelint static checker, http://www.gimpel.com/html/products.htm

32. Coverity: Automated Error Prevention and Source Code Analysis, http://www.coverity.com

33. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997,3rd edition

34. Carl D. Offner. Notes on Graph Algorithms Used in Optimizing Compilers, http://www.cs.umb.edu/~offner/files/flowgraph.ps

35. Crispin Cowan. StackGuard Mechanism: Emsi's Vulnerability. http://www.immunix.org/StackGuard/emsivuln.html, November 1999

36. Bulba and Kil3r. Bypassing StackGuard and StackShield. Phrack Magazine Volume 10, Issue 56 http://www.phrack.org/phrack/56/p56-0x05, May 2000

37. Richarte, G. Four different tricks to bypass stackshield and stackguard protection, http://www.c0rest.c0m/f1les/f1les/l 1/StackguardPaper.pdf, June 2002

38. Cowan, C., Barringer, M., Beattie, S., Kroah-Hartman, G., Frantzen, M., and Lokier, J. Formatguard: Automatic Protection from Printf Format String Vulnerabilities. USENIX Security Symposium, pp. 191--199, Washington, DC, August 2001

39. J. Seward. Valgrind, an open-source memory debugger for x86gnu /linux. In http://valgrind.kde.org/, 2004

40. Julian Seward and Nicholas Nethercote. Using Valgrind to detect undefined value errors with bit-precision. In USENIX Annual Technical Conference, Anaheim, CA, April 2005

41. Valgrind Developers: Valgrind. Web page at http://valgrind.org

42. Gelato ICE (Itanium Conference and Expo), April 2006, http://www.gelato.org/pdf/apr2006/gelato ICE06apr pin kampermanintel.pdf

43. Trusted Computer System Evaluation Criteria (TCSEC), US DoD 5200.28-STD, 1983

44. Palm OS home page, http://www.palmsource.com/palmos/

45. MS-DOS Reference, http://www.nukesoft.co.uk/msdos/

46. RACF, http://www-03.ibm.com/servers/eserver/zseries/zos/racf/

47. The UNIX System, http://www.unix.org/

48. HP OpenVMS Systems Site, http://www.hp.com/go/openvms/

49. IBM System i operating systems i5/0S, http://www-03.ibm.eom/systems/i/os/i5os/

50. Microsoft TechNet: Windows NT Server 4.0, http://www.microsoft.com/technet/archive/winntas/default.mspx?mfr=true

51. Novell NetWare, http://www.novell.com/products/netware/

52. Multics OS, http://www.multicians.org/

53. DigitalNet Solutions, http://www.digitalnet.com/solutions/informationassurance/xts400 trusted sys.htm

54. SGI-Products: IRIX http://www.sgi.com/products/software/irix/

55. Lawrie Brown, Trusted Computer Systems, http://williamstallings.com/Extras/Securitv-Notes/lectures/trusted.html

56. ISO/IEC 9899/1999, http://www.iso.org/iso/en/CatalogueDetailPage.CatalogueDetail?CSNUMBER=17782

57. GNU General Public License, http://www.gnu.org/licenses/gpl.html

58. Solaris Enterprise System, http://www.sun.com/software/solaris/index.isp

59. Stack Checking GNU Compiler Collection (GCC) Internals, http://gcc.gnu.org/onlinedocs/gccint/Stack-Checking.html

60. Stack Smashing Protection GNU Compiler Collection (GCC) Internals, http://gcc.gnu.org/onlinedocs/gccint/Stack-Smashing-Protection.html

61. CeBIT Homepage, http://www.cebit.de

62. D. Avots, M. Dalton, V. B. Livshits, and M. S. Lam. Improving software security with а С pointer analysis. In ICSE '05: Proceedings of the 27th International Conference on Software Engineering. ACM Press, 2005

63. Antoine Mine, Field-Sensitive Value Analysis of Embedded С Programs with Union Types and Pointer Arithmetic, Proceedings of LCTES'06, June 2006

64. Kildall, G. A., Global expression optimization during compilation, Proceedings ACM Conference on Principles of Programming Languages, Boston (Mass.), pp. 194-206, October 1973

65. W. Landi. Undecidability of static analysis. ACM Letters on Programming Languages and Systems, l(4):323-337, December 1992

66. G. Ramalingam. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems, 16(5): 1467-1471, September 1994

67. L. 0. Andersen. Program Analysis and Specialization for the С Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994

68. M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. Lecture Notes in Computer Science, 892, pages 234-250. Springer-Verlag, 1995

69. J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In 20th Annual ACM SIGACT-SIGPLAN Symposium on the Principles of Programming Languages, pages 232-245, January 1993

70. M. Hind, М. Burke, P. Carini, and J.-D. Choi. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 21(4):848-894, July 1999

71. B. Steensgaard. Points-to analysis in almost linear time. In 23rd Annual ACM SIGACT-SIGPLAN Symposium on the Principles of Programming Languages, pages 32-41, January 1996

72. T. J. Marlowe, B. G. Ryder, and M. G. Burke. Defining flow sensitivity in data flow problems. Technical Report RC20138, IBM T. J. Watson Research Center, July 1995

73. M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive point-to analysis. In 24th Annual ACMSIGACT-SIGPLAN Symposium on the Principles of Programming Languages, pages 1-14, January 1997

74. P. A. Stocks, B. G. Ryder, W. A. Landi, and S. Zhang. Comparing flow and context sensitivity on the modifications-side-effects problem. In International Symposium on Software Testing and Analysis, pages 21-31, March 1998

75. A. Diwan, K. S. McKinley, and J. E. B. Moss. Type-based alias analysis. In SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 106-117, June 1998

76. D. Liang and M. J. Harrold. Efficient points-to analysis for whole-program analysis. In 0. Nierstrasz and M. Lemoine, editors, Lecture Notes in Computer Science, 1687, pages 199-215. Springer-Verlag, September 1999

77. S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer aliasing: A step toward practical analyses. In 4th Symposium on the Foundations of Software Engineering, pages 81-92, October 1996

78. J. D. Morgenthaler. Static Analysis for a Software Transformation Tool. PhD thesis, UCSD, August 1997

79. D. С. Atkinson and W. G. Griswold. Effective whole-program analysis in the presence of pointers. In ACM SIGSOFT 1998 Symposium on the Foundations of Software Engineering, pages 131-142, November 1998

80. P. Cousot and R. Cousot, Static determination of dynamic properties of programs, In Proceedings of the Second International Symposium on Programming, pages 106—130, Dunod, Paris, France, 1976

81. M. Emami, R. Ghiya, and L. Hendren, Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers, In Proceedings of the SIGPLAN '94 Conference on Program Language Design and Implementation, Orlando, US, 1994

82. E. Haugh and M. Bishop. Testing С Programs for Buffer Overflow Vulnerabilities, In Proceedings of the Network and Distributed System Security Symposium, San Diego, CA, February, 2003

83. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.