Поиск уязвимостей в программном обеспечении с использованием технологии поиска клонов кода (1133536)
Текст из файла
Московский государственный университет имени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиКафедра системного программированияАСИРЯН Александр КамоевичПоиск узявимостей в программном обеспечении сиспользованием технологии поиска клонов кодаКУРСОВАЯ РАБОТАНаучный руководитель:к.ф.-м.н., профессорС.С.ГайсарянМосква, 2015ОглавлениеВведение3Постановка задачи41 Метод поиска уязвимостей с помощью технологии поискаклонов кода1.1 Представление кода с помощью Program Dependence Graph . .
.1.2 Технология поиска клонов кода в программном обеспечении . .1.3 Использование технологии поиска клонов для поиска уязвимостей55782 Исполнение102.1 Уязвимость в HTTP-сервере nginx . . . . . . . . . . . . . . . . . 112.2 Уязвимость в библиотеке для работы с растровой графикой libpng 123 Результаты13Заключение16Литература17A PDG шаблона buffer underrun19B PDG шаблона buffer overflow202ВведениеРабота посвящена проверке программного обеспечения на существованиенебезопасного кода. Данный подход основан на выделении шаблона конкретного класса уязвимости для последующего анализа проектов.
Зачастую, программисты при написании программ копируют те или иные участки кода дляиспользования, например, в разных функциях, которые отличаются именамиили входными параметрами, но схожи по выполнению. Такое явление может встречаться как в одной программе, так и в больших проектах. Возможно, спустя некоторое время, при тестировании найдется уязвимость именно втом участке кода, который использовался для копирования. И если в маленькой программе разработчик еще сможет вспомнить, где использовал данныйфрагмент, и исправить весь небезопасный код, то в большом проекте такое непредставляется возможным. Тем более что часть скопированного кода моглаизменяться, как с помощью добавления, так и удаления некоторых фрагментов.
С помощью выделения шаблона найденной уязвимости можно будет легко найти все фрагменты кода, в которых она повторилась. Подход применимтакже для проверки устранения уязвимостей в программах. В этом случаеисправленная версия не должна быть выявлена при сравнении с шаблономнебезопасного кода.Анализ проводится с помощью инструмента поиска клонов кода (CCD)[3],описанным в секции 1.2. В секции 1.1 определяется представление программв виде Program Dependence Graph (PDG), которое является ключевым дляданной технологии и часто применяется в различных методах статическогоанализа программного кода.
Об использовании инструмента CCD для поискауязвимостей в программном обеспечении рассказывается в секции 1.3. Исполнение и результаты представлены в главах 2 и 3 соответвтенно. В заключенииописаны планы дальнейшего исследования метода поиска уязвимостей.3Постановка задачиДля статического анализа проектов необходимо такое представление программного кода, которое будет одновременно и эффективным, и достаточным.
Таким образом представление должно позволять анализировать программное обеспечение за относительно небольшой промежуток времени и приэтом не хранить много излишних данных. Program Dependence Graph делаетэто возможным.Существует множество методов поисков клонов кода, они отличаются посложности клонов, быстроте нахождения и проценту верно найденных фрагментов, использованных при копировании.
Представление программы с помощью Program Dependence Graph дает возможность свести задачу к поискуизоморфных подграфов, что делает подход более точным по сравнению сдругими, о которых также вкратце будет рассказано далее в секции 1.2.Целью работы является создание подхода для анализа проектов, которыйиспользует технологию поиска клонов кода. С помощью шаблона уязвимостии инструмента CCD, реализующего данную технологию, анализ становитсябыстрым и расширяемым на большие проекты с миллионами строк программного кода.4Глава 1Метод поиска уязвимостей спомощью технологии поискаклонов кода1.1Представление кода с помощью ProgramDependence GraphГраф зависимостей программы – это ориентированный, атрибутированный граф, представляющий зависимости между выражениями и предикатами.Вершинам отвечают инструкции программы.Ребра с помощью атрибутовпоказывают зависимости между ними.
Зависимости могут быть по данным ипо управлению:1. Вершина P зависит по данным от вершины N, если значение, вычисленное в P, используется в N. Вершины соединяются ребром в направленииот P к N с атрибутом Dx , где x – имя переменной.2. Вершина P зависит по управлению от вершины N, если предикат из Pопределяет выполнение выражения в N. Ребрам присваивается атрибутCb , где b – true или false, в зависимости от того по какому значениюпредиката происходит переход в N.При этом зависимость по данным является таковой, если между вершинамиP и N нет другой вершины в пути по управлению, которая переопределяетзначение переменной, вычисленное в P.
Ребра, отвечающие зависимости поуправлению, проводятся не только к первой инструкции базового блока, а ковсем инструкциям, которые он содержит [1, стр. 5-6].5Рис. 1.1: Пример PDGНа рисунке 1.1 представлен пример Program Dependence Graph для функции foo. В этом PDG ребра синего цвета отвечают зависимости по управлению, а черного - по данным:int foo() {int x = source();if (x < MAX) {int y = 2 * x;sink(y);return y;}elsereturn x;}Преимущество представления кода с помощью PDG по сравнению с другими стандартными представлениями, такими как Abstract Syntax Tree (AST)и Control Flow Graph (CFG), заключается в том, что Program DependenceGraph явно показывает зависимость данных в отличие от CFG, а также передачу управления, что представлено в AST лишь неявным образом [2, стр.
2-3].61.2Технология поиска клонов кода в программном обеспеченииИнструмент поиска клонов кода основан на семантическом анализе программы [3]. Выделяются три типа клонов: к первому типу относят фрагментыкода, отличающиеся только пробелами и комментариями, ко второму - первый тип и отличия в именах переменных, их типах, к третьему - второй типи добавление и удаление строк. Также существуют другие методы анализа:• Текстовый – подсчет значений для каждой строки по некоторой хешфункции для последующего анализа совпадающих последовательностейв программе. Находит клоны только первого типа, поэтому не можетбыть применим.• Лексический – разбор программы на токены. Анализ представляет собой поиск одинаковых последовательностей токенов.
Не может бытьприменим, так как определяет клоны только 1-го и 2-го типов.• Синтаксический – использование представление кода в виде AST. Задача сводится к поиску одинаковых поддеревьев или совпадения векторов,отвечающих поддеревьям. Выявляет клоны всех типов, но 3-й с маленькой точностью.• Метрический – подсчет метрик для PDG или AST. Определяет все типыклонов с большой скоростью, но меньшей точностью, чем предыдущийи следующий подход.• Семантический – поиск изоморфных поддеревьев в PDG.
Находит также все типы, но в отличии от остальных имеет высокую точность [7].Таким образом использование PDG представления обосновано. Но так какзадача изоморфности графов является NP-полной, то подход имеет большуювычислительную сложность. Для ее уменьшения на первом этапе большинство кандидатов отсеивается с помощью более быстрых алгоритмов.CCD использует компилятор Clang [5] для получения промежуточногопредставления LLVM [6]. Далее для каждой функции в проекте строитсяPDG, использующийся в анализе. Полученные PDG делятся на слабо связанные компоненты в зависимости от параметра length, подающегося на входпрограмме. Один из алгоритмов деления – MII, основан на интервальныхграфах [4].
Дальше происходит сам анализ всех компонент, о котором говорилось ранее. После анализа происходит фильтрация выявленных клонов напредмет большой удаленности кода клона внутри программы.7В данном инструменте реализованы такие классы, как: Dependence,содержит информацию о ребре PDG; DepGraphNode, отвечающий отдельной вершине в PDG и содержащий набор объектов класса Dependence;DependenceGraph – класс PDG, являющийся вектором из объектов классаDepGraphNode.
Полностью строка команды выполнения выглядит так:/path/to/ccd -pdg-dump-root=/path/to/dump -algorithm=PDG -filter=0.9-result-path=/path/where/to/save/result -length=10 -split-method=MIIгде в -pdg-dum-root подается директория, содержащая полученные PDG;-algorithm – алгоритм нахождения клонов; -filter – доля схожести клонов; -length – длина для алгоритма деления, который указывается в-split-method.1.3Использование технологии поиска клоновдля поиска уязвимостейМодифицировав инструмент поиска клонов, можно реализовать поискшаблона уязвимости в проекте. Шаблон из себя представляет PDG, содержащий инструкции, ведущие к уязвимости в программе, то есть небезопасныйкод.Паттерн можно получить несколькими способами.
Например, пользуясьтолько классами Dependence, DepGraphNode и DependenceGraph, создаваявершины, отвечающие инструкциям небезопасного кода, и соединяя их зависимостями по данным или по управлению, можно добиться нужного результата. Однако с помощью данного подхода можно получить лишь небольшие шаблоны, где интуитивно понятно какие инструкции присутствуют, икак они связаны. Проблема паттернов небольшого размера заключается втом, что они приводят к большому проценту false positive случаев или ошибок первого рода.
Это объясняется тем, что при неизменном коде кандидатовстановится гораздо больше. Второй подход заключается в использовании готового шаблона, то есть PDG, полученного из программы, содержащей уязвимость. Существование в программе помимо небезопасного кода других фрагментов, никак не связанных с уязвимостью, как и в первом случае ведет кнебольшой точности. Последний подход является объединением первых двух:выделяется шаблон из PDG на основе программы с заранее известным классом уязвимости, шаблон корректируется для дальнейшего анализа основногопроекта на предмет существования небезопасного кода. Коррекция шаблонапредставляет собой удаление, и добавление строчек кода, а также изменениемPDG через существующие классы.
Полученный паттерн может как делиться8алгоритмами инструмента CCD, так и оставаться единым. Код уязвимостииз-за зависимости скорее всего поделен не будет, а остальные фрагменты программы не влияют на изоморфность подграфа, отвечающему небезопасныминструкциям, PDG из анализируемого проекта.Таким образом, совместив два подхода, в результате представляется возможным простое создание как маленького, так и большого шаблона на некоторый класс уязвимости. Хотелось бы заметить, что изменение PDG черезвышеупомянутые классы должно быть автоматизированным, о чем будет рассказано в заключении. На данный момент модифицирование индивидуальнодля каждого проекта с уязвимостью.9Глава 2ИсполнениеВ качестве шаблонов для уязвимости были выбраны два проекта: nginx[8] версии 0.6.38 и libpng [9] версии 1.2.5.
В качестве анализируемых на существование уязвимостей взяты следующие проекты:• openmpi (версия 1.6.5)• openssh (версия 6.6-p1)• openssl (версия 1.0.1f)а также сами проекты с уязвимостями. Алгоритм деления PDG принимал параметр length со значениями: 3, 5, 10. Процент схожести во всех тестах былравен 90%. Были рассмотрены случаи, когда PDG анализируемого проекта ипроекта с шаблоном не делились. PDG создавался со всеми ребрами управления, то есть проводились зависимости между инструкциями внутри базовогоблока. Все проекты проверялись на ноутбуке с 4-х ядерным процессором IntelCore i7-3610QM, 3000 MHz и 8 ГБ оперативной памяти. Время анализа длявсех проектов составило меньше двух минут.Программный код с шаблоном подгружается с помощью конструкторакласса LoadPDG, который принимает на вход строку, отвечающую названию файла, в котором указан путь к шаблону.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
