WWW.KONF.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Авторефераты, диссертации, конференции
 


Pages:     | 1 || 3 | 4 |

«МОДЕЛЬ, АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ АВТОМАТИЗИРОВАННОГО ПОИСКА УЯЗВИМОСТЕЙ В ИСПОЛНЯЕМОМ КОДЕ ...»

-- [ Страница 2 ] --

Несмотря на все вышеописанные трудности, существует инструментарий, позволяющий автоматизировать процесс анализа бинарного кода под различные платформы, который включает в себя как интерактивные дизассемблеры/декомпиляторы [20, 21], отладчики [22, 23], так и платформы для динамической бинарной инструментации [24, 25]. Этот инструментарий даёт эксперту возможность автоматизированного анализа программного кода. Однако, несмотря на это, идентификация уязвимых мест в бинарном коде современных приложений, состоящих из огромного числа машинных инструкций, вручную является достаточно сложной и трудоёмкой работой.

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

Рисунок 1.7.

Пример потенциально опасного участка обработки данных Необходимо отметить, что помимо ручного и полуавтоматизированного анализа применяются и автоматизированные алгоритмы статического анализа безопасности бинарного кода [26]. Как правило, эти алгоритмы включают следующую последовательность действий при анализе:

дизассемблирование исполняемого модуля;

построение графа потока управления (ГПУ) и графа вызовов функций;

проверка ограничений, наложенных аналитиком.

Определение 1.1. Под графом потока управления программы следует понимать множество всех возможных путей исполнения программы, представленное в виде графa.

В дальнейшем для анализа безопасности бинарного кода было предложено использовать методику символьного исполнения программы [27]. Символьное исполнение программы это интерпретация выполнения программы путём замены конкретных входных значений (как правило, пользовательские данные, передаваемые через какой – либо интерфейс) на символы (обозначающие множество значений входной переменной программы из области её определения), которые затем будут обрабатываться в виде символьных выражений. Такой подход позволяет повысить покрытие кода и активно применяется не только в моделях, выполняющих сугубо статический анализ, но и в гибридных моделях, сочетающих статический и динамический подходы. Основным понятием символьного выполнения является символьное состояние (symbolic state), которое включает множество символьных значений переменных программы A={1,2,3,...an}, условие реализуемости пути – path condition (pc) и счетчик операторов программы. Каждое символьное выполнение программы начинается с инициализации pc значением «истина».

В каждой точке ветвления программы в pc добавляются предположения о входных переменных в порядке выбора между путями выполнения. Рассмотрим тривиальный пример:

1 y = read() 2 y=2*y 3 if (y == 12) 4 fail() 5 print("OK") Листинг 1.1. Пример программы в псевдокоде В рамках символьного исполнения эта программа не имеет конкретных входных данных, таким образом результат исполнения первой строки это множество всех состояний s, а вторая лишь удваивает множество этих состояний и присваивает y. Выражение IF имеет два потенциальных решения: истинное () и ложное. В этом случае символическое выполнение программы разделяется на два () независимых параллельных маршрута с независимыми состояниями, а информация присваивается в pc:

1 2 (1.1) 2 1 () (1.2) () (1.3) Множество всех pc аккумулирует ограничения на входные переменные, которые определяют уникальный путь выполнения в программе, тем самым формируя символическое описание потенциальных путей исполнения программы, которые в дальнейшем могут быть разрешены с помощью решателей логических уравнений [28 - 31].

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

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

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

Определение 1.2. Ошибка первого рода – происходит обнаружение уязвимости в корректном коде.

Определение 1.3. Ошибка второго рода – не происходит обнаружение уязвимости в ошибочном коде.

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

Так как практически все уязвимости в ПО так или иначе связаны с обработкой некорректных пользовательских данных, существует возможность искусственно создать эти данные и автоматически передать их в тестируемое приложение с последующим мониторингом результата. Эта методика впервые была использована для тестирования Unix программ профессором Бартоном Миллером в 1988 году и названа термином «fuzz testing» или «fuzzing» [34]. В русскоязычной литературе термин «fuzzing» получил распространение в транслитерации [32, 35 - 37] и записывается как фаззинг или фазз – тестирование, а инструменты для проведения такого тестирования как фаззеры.

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

Монитор состояния тестируемого приложения

–  –  –

Каждый шаг анализа сопровождается мониторингом тестируемого приложения на предмет появления в нём исключительных ситуаций. В дальнейшем методика фаззинга получила широкое распространение и сегодня используется для выполнения тестирования различных типов приложений: взаимодействующих по сети [38], выполняющих обработку файлов [39], веб – браузеров и многих других [40].

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

Takanen в своей работе [41] выделил следующие подходы к формированию тестовых данных:

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

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

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

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

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

Существуют работы, в которых используются дополнительные подходы для повышения качества генерируемых данных [42 - 45]. Основная идея заключается в том, что существует возможность осуществлять генерацию, основываясь на анализе того, как определенные данные обрабатываются тестируемым приложением (анализ потока управления и потока данных). Такой подход получил название динамический taint – анализ или метод анализа помеченных значений [46].

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

В некоторых исследованиях авторы пытаются применять эволюционные и генетические алгоритмы для эффективной генерации данных c целью повышения эффективности тестирования [47-50]. При этом начальный набор данных может задаваться как с использованием эволюционной грамматики [47], так и с использованием ранее описанной в этой главе методики символического исполнения.

Помимо генерации, важным вопросом является выбор функции пригодности для тестовых данных. В [48] функция пригодности для каждого генома рассчитывается как инверсия оценки вероятности пути исполнения этого генома для ГПУ.

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

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

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

= =1 wj вес ассоциированный с тестовыми данными i, а fij частота исполнения функции f с набором этих данных. Таким образом выбор веса wj становится ключевым при формировании эффективной функции пригодности.

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

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

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

Для решения вышеописанной проблемы могут применяться схожие подходы с теми, которые применяются при наличии доступа к исходному коду. Например, в работе [51] используется оценка покрытия бинарного кода тестовыми данными для оценки эффективности проведенного тестирования. Sutton и Amini в [52] определили покрытие кода как количество состояний, которые фаззер может вызвать в тестируемом приложении. Таким образом интуитивно понятно, что для успешного обнаружения уязвимостей необходимо выполнение следующих двух условий:

покрытие должно включать участок с уязвимостью;

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

Идеальной ситуацией можно считать 100% покрытие кода, однако полное покрытие практически невозможно и для большинства приложений в этом нет необходимости [53]. На практике большинство приложений включают код, на который не могут повлиять внешние данные. Таким образом, так как этот код не может быть протестирован, то и его покрытие не должно учитываться при оценке эффективности тестирования.

Необходимо отметить, что покрытие кода даёт лишь ответ на вопрос, какое количество кода было протестировано с помощью заданного набора данных, но не даёт возможность оценить, насколько эффективно были сгенерированы тестовые данные [54]. Например если для абстрактного приложения было обеспечено 100% покрытие кода на заданном наборе тестовых данных, это лишь означает, что для заданного набора данных в приложении ошибок/уязвимостей нет, однако это не означает, что их нет в принципе.

Таким образом, все вышеописанные критерии можно свести к следующим базовым критериям для оценки эффективности системы автоматизированного поиска уязвимостей в исполняемом коде:

количество детектируемых типов уязвимостей за промежуток времени;

количество ошибок первого и второго рода;

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

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

– сервер). В такой ситуации исследователи часто стараются выбрать наиболее «интересные» с точки зрения потенциальных уязвимостей функции в тестируемом приложении. Для поиска таких функций используется как ручной анализ, так и автоматизированные подходы.

Специалисты Microsoft Research провели анализ ошибок, возникавших в пяти поколениях ОС Microsoft Windows, и пришли к выводу, что количество дефектов статистически коррелирует со сложностью кода, который приводил к ошибке или уязвимости [55]. Для вычисления сложности авторы использовали комплекс различных метрик оценки сложности программного кода для объектно – ориентированных и структурных программ. Необходимо отметить, что авторы в своей работе оперировали на уровне исходного кода Windows.

В [56] автор адаптировал вышеописанный подход для поиска потенциально «опасных» функций (оперируя на уровне исполняемого кода), используя метрику цикломатической сложности программы [57]. При этом автор проводит тестирование этих функций напрямую в памяти исполняемого процесса в обход стандартного интерфейса обработки пользовательских данных (рисунок 1.11). Такой

–  –  –

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

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

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

1 int main() 2 { 3 char buffer[10];

4 char overflow_string[9];

5 int a = 0;

6 fgets(buffer, sizeof buffer, stdin);

7 strcpy(overflow_string, buffer);

8 if (a == 0) 9 printf("expected behavior");

10 else 11 printf("overflow occurred");

12 return 0;

13 } Листинг 1.2. Пример переполнения 1 байта в памяти Согласно листингу 1.2 в случае передачи этому приложению строки длиной в 10 байт произойдёт переполнение в строке 7, так как принимающий буфер на 1 байт меньше, чем исходящий буфер. Произойдёт переполнение одного байта, что может привести к перезаписи следующих за ним данных. Такая ситуация может и не привести к вызову исключения и приложение продолжит свою работу штатно.

Например, в вышеизложенном примере может произойти вывод строки «overflow occurred» в зависимости от того, как будут располагаться данные в стеке.

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

недоступная память. Память, которая недоступна приложению;

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

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

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

Обобщим все вышеописанные подходы поиска уязвимостей в бинарном коде в виде единой классификационной схемы (рисунок 1.10):

–  –  –

Данная классификация является условной и многие авторы, дабы избежать недостатков одного подхода, комбинируют их, дополняя результаты статического анализа результатами динамического анализа и наоборот [44, 60, 61, 62]. Например, ГПУ, построенный статическим анализатором, является неполным – неизвестными остаются значения операндов инструкций передачи управления с косвенной адресацией. Посредством динамического анализа соответствующие значения операндов могут быть найдены.

Обзор и сравнение существующих инструментальных средств для 1.4.

автоматизированного поиска уязвимостей в исполняемом коде

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

а) Valgrind и Memcheck [63] - система поиска ошибок в процессе работы программы с памятью, построенная на базе системы Valgrind. Memcheck поддерживает приложения только для Unix – систем. Утилита подменяет системные вызовы выделения памяти, позволяя выполнять обнаружения следующих типов ошибок:

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

б) Avalanche [64] - разработка Института системного программирования РАН, Россия, которая реализует подход смешанного исполнения и является инструментом для обнаружения программных ошибок при помощи динамического анализа.

В своей основе Avalanche использует возможности Valgrind [63] для сбора и анализа трассы исполнения программы. Результатом такого анализа становится либо набор входных данных, на которых в программе возникла ошибка, либо новый набор тестовых данных, позволяющий выполнять ранее не выполнявшиеся участки бинарного кода. В качестве системы детектирования ошибок используется Memcheck.

в) Flayer [65] – система фаззинга, разрабатываемая в Google, которая также основана на системе динамической бинарной инструментации Valgrind и подсистеме детектирования ошибок Memcheck. Система выполняет низкоуровневый анализ того, как входные данные преобразуются в приложении и на основании этого предоставляет пользователю возможность контролировать поток управления в программе при помощи библиотеки LibFlayer с целью выявления уязвимостей.

г) DrMemory [66] система поиска ошибок работы с памятью в исполняемом коде, реализованная на базе системы динамической бинарной инструментации DynamoRIO [67]. Drmemory позволяет выполнять обнаружения следующих типов ошибок: использование неинициализированной памяти, обращения по недопустимому адресу в памяти, использование освобожденной памяти, утечки памяти, а также ошибки при работе с Windows API. Система может осуществлять работу в ОС Windows и Linux.

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

е) Peach [69] это кросс – платформенный программный комплекс для выполнения фаззинга. Пользователь генерирует набор XML – файлов, которые описывают протокол (используется подход схожий со SPIKE) и то, каким образом должно выполняться тестирование. Peach поддерживает большой объем встроенных функций, таких как вычисление контрольной суммы или длины базового блока.

Также комплекс включает в себя приложение для мониторинга состояния тестируемого приложения и его перезапуска в случае сбоя.

ж) Авторы Sulley [70] продолжают идею генерации данных на основе базовых блоков, предложенную авторами SPIKE, однако в значительной степени упрощают её за счёт использования собственного языка описания протокола и поддержки его формирования с помощью перехваченных сетевых данных в pcap – файле (специальный формат для хранения сетевых данных).

з) American Fuzzy Lop (AFL) [71] это система фаззинга, разрабатываемая в Google, использующая инструментацию на этапе компиляции (система также поддерживает тестирование и без инструментации) и генетические алгоритмы для автоматической генерации тестовых данных с целью увеличения покрытия в исполняемом коде.

<

–  –  –

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

Выводы 1.5.

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

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

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

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

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

Глава 2. Модель и алгоритмы автоматизированного поиска уязвимостей в трассе программы с оценкой эффективности

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

Представим состояние регистров программы после выполнения каждой инструкции в трассе в виде вектора = (,,,,,,,, ), описывающего значения регистров процессора после выполнения машинной инструкции, где eax, ebx, ecx, edx, esi, edi, ebp, esp, eip – рассматриваемые в работе регистры процессора. Представим трассу программы в виде системы упорядоченных векторов: = (0, 1, …, ), где – количество выполненных инструкций, 0

– начальное состояние, – заключительное состояние.

Для поиска уязвимостей определим L как множество всех адресов в памяти, доступных программе для обращения. Также определим = ( ) как множество фактических указателей в память из состояния и, [0; ]. Отметим, что функция будет задана алгоритмически в разделе 2.1.1.

В свою очередь пусть имеется - множество доступных адресов в памяти из состояния и. Алгоритм определения этого множества будет описан позднее в разделе 2.1.1.

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

Обозначив, и, можно записать вектор состояния следующим образом:

= (,,,,,,,,,,, ).

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

= [ ]

Обозначим через функцию, которая позволяет определить, является ли состояние допустимым или недопустимым следующим образом:

–  –  –

работу с памятью и составить множество фактических указателей, позволяя выполнять обнаружение уязвимостей в случаях некорректной работы тестируемого кода с этим системным вызовом. Затем на итерации 7-8 выполняется выделение памяти в куче размером в 10 байт, после чего производится сохранение полученных данных от scanf в выделенной области памяти. При этом в состоянии 13 производится запись за границами кучи, что определяется как ошибка.

–  –  –

Рисунок 2.2.

Алгоритм автоматизированного поиска уязвимостей в трассе На первом этапе алгоритма производится определение участков памяти, которые задействованы в обработке защищаемой информации (алгоритм определения таких участков будет приведен в разделе 2.3). Затем программа выполняется на тестовых данных, в результате чего имеем трассу размером n инструкций.

На следующем этапе вступает в работу алгоритм определения границ доступной памяти (ОГДП). Рассмотрим его детально на рисунке 2.3. В качестве параметра передается итератор i равный нулю.

Рисунок 2.3.

Алгоритм определения границ доступной памяти (ОГДП) На первом шаге производится вход в цикл считывания инструкций и выполняется декомпиляция инструкции по адресу. Затем, если выполняется выделение или освобождение памяти, определяется множество адресов, которые затем добавляются или исключаются из +1. Затем, если размер выделенного участка стека увеличивается или уменьшается, то в множество +1 добавляется или исключается из него множество новых доступных/недоступных адресов. В том случае, если инструкция является вызовом процедуры, производится определение множества передаваемых адресов памяти в качестве аргументов процедуры, а затем производится рекурсивный вызов алгоритма ОГДП с параметром i = i+1. Таким образом, описанный на рисунке 2.3. алгоритм является рекурсивным. Возврат из рекурсии происходит при достижении инструкции retn, для которой определяется множество возвращаемых адресов памяти, которые сохраняются в +1. Переменная j определяет количество проанализированных инструкций в рекурсии и позволяет выполнить переход к последующему после вызова call состоянию.

На следующем этапе согласно алгоритму выполняется последовательное считывание состояний. Для каждого состояния последовательно выполняются два алгоритма: определение множества указателей (ОМУ) и анализ состояния (АС) на основе и с помощью выражения 2.1. Рассмотрим детально оба этих алгоритма.

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

Рисунок 2.4. Алгоритм определения множества указателей (ОМУ)

На первом шаге алгоритма ОМУ выполняется считывание и дизассемблирование инструкции по адресу. Затем в том случае, если инструкция работает с памятью, выполняется определение адреса в памяти первого байта, к которому осуществляется доступ (обозначим его как ), а затем определяется количество считываемых или записываемых байт (обозначим это количество через ). Тогда элементы множества будут определены следующим образом: { | ( + ) 0 }.

Получив множества и, алгоритм переходит к анализу состояния (АС).

Рассмотрим этот алгоритм на рисунке 2.5.

Рисунок 2.5.

Алгоритм анализа состояния (АС) На вход алгоритму поступают множества и. Затем последовательно выполняется проверка принадлежности множества фактических указателей в соответствии с критериями из формулы 2.1. В том случае, если один из критериев определяет факт наличия ошибки или уязвимости, информация об этом сохраняется и анализ продолжается для следующего состояния до тех пор, пока не будут считаны все состояния в трассе. Отметим, что после определения допустимости состояния выполняется анализ помеченных данных и расчёт +1 (при = не выполняется) для того, чтобы учесть возможные изменения во множестве защищаемых участков памяти при переходе в следующее состояние.

2.2. Методика трансляции исполняемого кода

2.2.1. Общий алгоритм частичной декомпиляции Необходимо отметить, что для поиска участков памяти, хранящих защищаемую информацию, необходимо выполнять трансляцию исполняемого кода в промежуточный язык. Решением этой задачи является декомпиляция бинарного кода [74].

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

Бинарный ASM Вход Дизассемблирование Интерпретация код Листинг

–  –  –

Рисунок 2.6.

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

–  –  –

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

Определение 2.1. Под линейным блоком (базовым блоком) будем понимать участок бинарного кода, на котором отсутствуют машинные инструкции условного и безусловного переходов за исключением вызова процедур.

Определение 2.2. Рассматриваемый участок бинарного кода является нелинейным тогда, когда на анализируемом участке присутствуют инструкции передачи управления на другой участок бинарного кода (за исключением вызова процедур).

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

Найден новый линейный блок

–  –  –

Для интерпретации декомпилированного кода в рамках работы была предложена следующая схема: ресурс, соответствующий регистру, обозначается фигурными скобками, в которые заключён его номер. Ресурс оперативной памяти обозначается квадратными скобками, в которые заключён адрес ресурса. Номер такого ресурса выносится за скобки. Результат отделяется знаком «=». Операции и константы записываются без изменения. Представленная форма записи позволяет представлять инструкции в виде математических формул. Например, инструкции add eax,[ecx] и inc eax запишутся в виде, R2 = R1 +[R0]; R3 = R2 + 1.

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

R2 = R0 + R1 R4 = R2 * R3

В результате итоговое выражение будет иметь вид:

R4 = (R0+R1)*R3

А синтаксическое дерево примет следующий вид (рисунок 2.8):

–  –  –

Рисунок 2.9.

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

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

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

Под помеченными данными понимаются тестовые защищаемые данные, а под непомеченными соответственно любые другие данные используемые в программе. Таким образом, в том случае если эти данные сохраняются или обрабатываются в участке памяти, этот участок памяти также становится помеченным. Будем обозначать помеченные данные как Ta, а непомеченные соответственно UTa. Рассмотрим алгоритм анализа помеченных и непомеченных данных на рисунке 2.10.

–  –  –

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

Опишем алгоритмы подсчета метрик сложности для функций в программе. Для этого опишем алгоритм преобразования программы в граф на рисунке 2.12.

–  –  –

Рисунок 2.12.

Алгоритм преобразования процедур программы в граф Таким образом, каждая вершина графа ассоциируется со следующей информацией: индекс вершины, адреса начала и конца вершины, адрес конца вершины, адрес перехода #1 + индекс вершины (при наличии), адрес перехода #2 + индекс вершины (при наличии).

2.4.2. Описание метрик оценки сложности кода Помимо расчета полноты тестирования необходимо иметь способ, позволяющий учитывать разницу между ГПУ в программе, который также позволяет сделать некоторое предположение о вероятности появления уязвимости на них. При условии наличия исходного кода эта задача решается с использованием метрик оценки сложности программы или тестируемой функции. Так в работах Базили В.Р. и др. [82], Хошгуфтар Т. М. и др. [83], Олаг Н.М. и др. [84] было показано, что в общем случае с ростом сложности программного кода растет и вероятность ошибки на этом участке.

Эта гипотеза подтверждается и статистическими данными. Как было отмечено в главе 1, компания Coverity в своем ежегодном статистическом исследовании [3] числа ошибок/уязвимостей в 741 продукте с открытым исходным кодом отмечает, что с ростом кодовой базы растёт и среднее количество ошибок/уязвимостей (таблица 2.4). Исключение составляют лишь проекты с числом строк более 1 миллиона, что может быть обусловлено как статистической погрешностью, так и повышением требований к качеству кода для крупных проектов (повышение требований к покрытию кода тестами, использование статических и динамических средств анализа исходного кода).

Таблица 2.4.

Статистика числа ошибок/уязвимостей для программ на C/C++ Размер кодовой базы Среднее количество ошибок/уязвимостей на 1000 строк кода Менее 100 000 0.35 От 100 000 до 500 000 0.5 От 500 000 до 1 000 000 0.7 Более 1 000 000 0.65 Среднее по всем проектам 0.59 (252 010 232 строк кода) В главе 1 была отмечена сложность применения методик оценки покрытия и сложности для исходного кода в задаче оценки покрытия и сложности бинарного кода. Несмотря на это проведенный в следующих разделах данной главы анализ показал, что существует возможность применять частичную декомпиляцию и ряд метрик сложности также и для оценки сложности бинарного кода. Рассмотрим анализ и адаптацию метрик к задаче оценки сложности бинарного кода (базовый список метрик был получен из [85] и в рамках собственного исследования).

Перед описанием адаптированных метрик необходимо отметить, что обозначения и символы в формулах, которые используются для них, никак не связаны с предыдущими обозначениями в работе и используются в разделах 2.3.3.1 – 2.3.3.4 обособлено.

2.4.2.1. Количественные метрики А. Количество строк исходного кода (LOC).

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

Б. Метрика Холстеда [86]

Основу этой метрики составляют следующие измеряемые характеристики программы:

n1 – число уникальных операторов программы, включая символы – разделители, имена процедур и знаки операций (словарь операторов). В рамках бинарного кода будем рассматривать число уникальных ассемблерных инструкций.

n2 – число уникальных операндов программы (словарь операндов), будем рассматривать число уникальных операндов в инструкциях (регистры процессора, адреса в памяти и константы).

N1 – общее число операторов в программе.

N2 – общее число операндов в программе.

Далее Холстед, опираясь на эти характеристики, выводит следующие оценки:

n = n1 + n2 – словарь программы;

N = N1 + N2 – длина программы;

V = N log2n – объем программы;

N* = n1 log2n1 + n2 log2n2 – расчетная длина программы;

–  –  –

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

В. Метрика Джилба [87]

Метрика Джилба вычисляется по следующей формуле:

cl = CL/n, где CL – количество управляющих операторов. Для бинарного кода этими операторами будут являться такие инструкции, как JXX/CALL и другие инструкции передачи управления, n – общее количество операторов программы.

Г. ABC – метрика Применяется для оценки количества присваиваний значений переменным (Assignment), явных передач управления за пределы области видимости, т.е. вызовов функций (Branch) и логических проверок (Condition). Рассчитывается как:

= 2 + 2 + 2 Для этой метрики количество вызовов функций может быть рассчитано по количеству call для анализируемой функции, количество логических проверок по количеству логических конструкций типа cmp/test и jxx, а для учета количества присваиваний достаточно подсчитать количество присваиваний после этапа интерпретации.

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

2.4.2.2. Метрики сложности потока управления А. Цикломатическая сложность по Маккейбу [57] Метрика рассчитывается как цикломатическая сложность функции бинарного кода или, как ее еще называют, цикломатическое число Маккейба, характеризующее трудоемкость тестирования программы:

() = + 2, где e - число дуг ориентированного графа G;

v - число вершин;

p - число компонентов связности графа.

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

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

Б. Метрика Пивоварского [87]

Еще одной модификацией цикломатической сложности является метрика Пивоварского, представленная в виде:

() = () +, где =0 () – модифицированная цикломатическая сложность, рассчитывающаяся с учетом того, что один оператор case с д выходами, должен рассматриваться, как один логический оператор, а не как д-1 операторов.

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

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

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

–  –  –

Рисунок 2.13.

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

Г. Метрика граничных значений [87] Для определения данной метрики необходимо ввести несколько дополнительных определений. Пусть дан граф с единственной начальной и конечной вершинами. В этом графе число входящих дуг в вершину называется отрицательной степенью вершины, а число исходящих из вершины дуг - положительной степенью вершины. Тогда набор вершин графа можно разбить на две группы: вершины, у которых положительная степень меньше или равна 1 и вершины, у которых положительная степень больше либо равна 2. Вершины первой группы назовем принимающими вершинами, а вершины второй группы - вершинами отбора. Каждая принимающая вершина имеет приведенную сложность, равную 1, кроме конечной вершины, приведенная сложность которой равна 0. Приведенные сложности всех вершин графа G суммируются, образуя абсолютную граничную сложность программы. После этого определяется относительная граничная сложность программы:



Pages:     | 1 || 3 | 4 |

Похожие работы:

«Марченко Василий Сергеевич Методика оценки чрезвычайного локального загрязнения оксидами азота приземной воздушной среды вблизи автодорог 05.26.02 – безопасность в чрезвычайных ситуациях (транспорт) Диссертация на соискание учёной степени кандидата технических наук Научный руководитель: к.х.н., доцент Ложкина Ольга Владимировна Санкт-Петербург Оглавление Введение 1 Аналитический обзор...»

«Музалевская Екатерина Николаевна ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ ПРИМЕНЕНИЯ МАСЛА СЕМЯН АМАРАНТА ДЛЯ КОРРЕКЦИИ ОСЛОЖНЕНИЙ, ВЫЗЫВАЕМЫХ ИЗОНИАЗИДОМ 14.03.06 Фармакология, клиническая фармакология ДИССЕРТАЦИЯ на соискание ученой степени кандидата фармацевтических наук Научный руководитель: д.м.н., профессор Николаевский Владимир...»

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







 
2016 www.konf.x-pdf.ru - «Бесплатная электронная библиотека - Авторефераты, диссертации, конференции»

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