Атоматическая генерация эксплойтов на основе патчей

 

 

 

 

 

 

 

Курсовая работа

на тему

"Атоматическая  генерация эксплойтов на основе  патчей"

 

 

 

 

 

       Студентка группы ИУ10-61 

             (Подпись, дата)                           (И.О. Фамилия)

 

           Руководитель курсового проекта 

                             (Подпись, дата)                      (И.О. Фамилия)

 

 

 

 

 

 

 

Москва, 2015 

Содержание:

 

 

1. Введение

 
2. Автоматическая генерация эксплойтов на основе патчей: определение проблемы и подход.

2.1 Определения 
 2.2  Задача автоматической генерации эксплойтов на основе патчей.

2.3  Границы задачи и подход.

 
3. Автоматическая генерация эксплойтов на основе патчей

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

3.2 Генерация формулы ограничений

3.2.1 Ключевые моменты разработки 
  3.2.2 Создание формулы ограничений из образца исполнения

3.2.3 Создание формулы ограничений из CFG

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

   3.3 Генерирование потенциального эксплойта из формулы ограничений

3.4 Генерирование полиморфных эксплойтов

 3.5 Подтверждение потенциального эксплойта

 

4. Оценка

4.1 Описания уязвимостей и эксплойтов

4.2 Генерация эксплойта с использованием динамического анализа

4.3 Генерация эксплойта с использованием статического анализа

  4.4 Генерация эксплойта с использованием комбинированного анализа

 

5. Заключение

 

6. Ссылки

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Введение

 

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

 

Задача автоматической генерации эксплойтов на основе патчей (APEG)  состоит в следующем: дана программа P и пропатченная версия программы P ′ , нужно автоматически сгенерировать эксплойт для потенциальных неизвестных уязвимостей присутствующих в P но исправленных в P ′. Успешная APEG покажет, что атакующий может использовать патч для создания эксплойтов. APEG ранее не была продемонстрирована в литературе. Таким образом, вопрос, осуществима ли APEG для реальных программ, остается без ответа.

 

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

 

Важное следствие полученных результатов состоит в том, что получение доступа к патчу дает значительное преимущество над тем, у кого нет доступа к патчу. Преимущества в безопасности очень важны в свете нынешней практики распространения патчей, которая растягивает распространение на час, день или дольше. Например, такие исследователи как Кристос Гкантсидис и другие, показали, что Центру обновлений Windows требуется около 24 часов чтобы 80% уникальных IP-адресов были проверены на наличие патча.

All inputs	Safe Inputs

 

 

Рис 1.

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

 

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

 

Рис. 2 показывает типичное целочисленное переполнение. Этот пример был выбран исходя из реальной уязвимости в Internet Explorer. Все целочисленные значения в этом примере занимают 32 бита, и более того, все вычисления производятся по модулю 232. В строке 1, целочисленная переменная input проверяется на четность: если это так, временной переменной s присваивается         input+2 (mod 232), если нечетное, то         input+3 (mod 232). Строка шесть вызывает realloc, шаблон ручного управления памятью, который изменяет размер в ptr чтобы указать на выделенные s биты памяти. Например, если s меньше чем размер, который в настоящее время указан ptr, Затем в результате указатель будет указывать на меньшую площадь памяти.

В этом примере, определяются любые входные данные, вызывающие переполнение во 2-ой или 4-ой строке как эксплойты. Таким образом , набор входных значений, являющихся эксплойтами, лежит в диапазоне 232 − 3 ≤ input ≤ 232 − 1. В лучшем случае, любой эксплуатации вызовет после 6-ой строки DoS- атаку, или в худшем случае, позволит атакующему захватить контроль над программой. Пропатченная P ′ добавляет проверки на переполнение в 5-ой строке. Любые входные данные, являющиеся эксплойтами для P не пройдут эти проверки в P ′ .

 

P :   i n p u t   i s   a  u s e r   i n p u t

 

1 . i f ( i n p u t %2 == 0 ) g o t o 2 e l s e g o t o 4 ; 
2 . s : = i n p u t + 2 ;

 

3 .   g o t o   5 ;

 

4 . s : = i n p u t + 3 ; 
5 . <nop>

 

6 . p t r : = r e a l l o c ( p t r , s ) ; 
7 . . . u s e o f p t r . . . ;

 

P ′ :   i n p u t   i s   a  u s e r   i n p u t

1 .	i f ( i n p u t %2  ==  0 )   g o t o  2  e l s e   g o t o   4 ;
2 .	s  : =   i n p u t + 2 ;

 

3.	g o t o	5 ;
4 .   s  : =		i n p u t + 3 ;
5 .	i f   ( s  >  i n p u t )   g o t o  6  e l s e   g o t o  ERROR ;
6 .	p t r   : =   r e a l l o c ( p t r ,   s ) ;
7 .	. . .   u s e  o f   p t r   . . .

 

Рис 2.

 

 

Проблемы. Одна из проблем APEG состоит в том, что программное обеспечение часто доступно только в бинарной форме. Таким образом, в предложенном подходе и реализации, мы нацеливаемся на случай, когда P and P ′ представлены в виде двоичного кода. В нашей ситуации, P and P ′ могут быть как исполняемыми программами так и библиотеками. Обращение APEG к библиотекам важно, поскольку 
a) уязвимость библиотеки может быть использована множеством программ, использующих библиотеку  
b) на многих ОС обновления безопасности часто выпускаются для библиотек. Например, была проведена проверка патчей, выпущенных Microsoft в 2006 году и обнаружено, что 84% обновлений, связанных с безопасностью, были изменениями в библиотеках. Если P является библиотекой, то сгенерированный эксплойт Х - действительный набор аргументов для экспортируемой (например, вызываемой) функции в библиотеке, в то время как, если P - программа, то Х - входные данные программы.

Другая проблема - выделить, какие изменения произошли между P and P ′. Чтобы решить эту проблему, был разработан инструмент, такой как bin-diff [33] и EBDS [13], которые сначала дизассемблируют P и P ′ , и затем определяют, какие инструкции были изменены.

 

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

 

Обзор подхода. Предложенный подход к APEG основан на наблюдении, что ошибки входных данных обычно исправляются добавлением отсутствующих проверок. Добавленные проверки P ′ определяют 
a) где есть уязвимость 
b) в каких условиях входные данные могут воспользоваться уязвимостью. Предположение для нашего подхода заключается в том, что входные данные, которые не проходят добавленных проверок в P ′ вероятно являются эксплойтами для P . Цель:

1) Определить проверки, добавленные в P ′  
2) автоматически сгенерировать входные данные которые не пройдут добавленных проверок. На рис. 2, Цель в том, чтобы сначала обнаружить проверку, добавленную в 5-ой строке, затем сгенерировать значения для input, которые не пройдут проверку и вызовут состояние ERROR.

Назовем пути выполнения программы, при которых новая проверка не проходится в P ′ эксплойтными путями. И все входные данные, при которых программа пойдет по этому пути будут. вероятнее всего, являться эксплойтами для P . Может быть много путей эксплойтов, например, есть 2 пригодных пути кода в нашем текущем примере. Однако, количество путей с эксплойтами обычно лишь малая доля от всех возможных путей исполнения программы.

 

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

 

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

 

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

 

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

 

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

 

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

 

• Автоматическая генерация эксплойтов на основе патчей: определение проблемы и подход.
• 2.1 Определения
• Программа определяет отношения между начальным и конечным пространствами состояний. Пространство состояний программы состоит из всех переменных и памяти. Все регистры моделируются как переменные, и каждая ячейка памяти также можно считать отдельной переменной, когда это удобно. На рис. 2, пространство состояний состоит из памяти и переменных s и input. При желании, мы можем также различать переменный по месту их обновления, например переменная s в строке 2 и s в строке 5.
• Политика безопасности φ - логическое утверждение из пространства состояний программы имеющее одно из двух значений: safe или unsafe. В нашей ситуации, мы будем рассматривать только политики безопасности осуществляемые через контроль выполнения. На высоком уровне, такие политики позволяют оценить логическое выражение в пространстве состояний программы на каждом этапе выполнения, а также отслеживать все предыдущие состояния. Общий контроль за исполнением политики безопасности включает динамический анализ заражения, проверка целостности адресов возврата, и динамический тип принуждения.
• Обозначим исполнение программы P с исходными данными x как P (x), и исполнение инструкции i как Pi (x). Мы обозначили проверку политики безопасности на этапе выполнения i как φ(Pi (x)). Точка уязвимости это первая инструкция i такая, что φ(Pi (x)) = unsafe.
• Термин эксплойт используется для обозначения входных данных x для которых политика безопасности возвращает значение unsafe. Например, если мы используем политику динамического анализа заражения, эксплойтом будут любые входные данные вызывающие предупреждения при анализе. Одна из причин, почему мы используем это определение эксплойта - оно не предполагает конкретных целей атак, например раскрытие информации, отказ сервиса или захват контроля. Это имеет смысл в данном контексте, так как уязвимость сама по себе определяет, возможны ли такие специфические атаки. Следует обратить внимание, что потенциально есть много различных эксплойтов, каждый из которых является  полиморфным вариантом.
• Политики безопасности являются достаточно мощными чтобы указать конкретные виды атаки когда это нужно. Например, можно указать политику безопасности, которая нарушается только атакой с целью захвата контроля. Например, можно создать политику безопасности в которой говорится, что адреса возврата в стеке не должны быть перезаписаны входными данными пользователя. Такая политика безопасности может быть нарушена только типичным переполнением буфера для захвата контроля.
• Граф потока управления (CFG) G = (V, E) это граф, где каждая вершина ∈ V это прямолинейный участок кода, и есть дуги (i1, i2) ∈ E если есть возможность передачи управления от инструкции i1 к i2. Путь исполнения это набор вершин в графе потока управления такой, что для каждой вершины существует дуга к следующей вершине в CFG (Заметим, что вершины могут повторяться).

2. Задача автоматической генерации эксплойтов на основе патчей.

4. У нас есть две версии программы P и P ′, где P ′ исправляет неизвестные уязвимости, имеющиеся в P . Цель состоит в генерации эксплойта для P для уязвимости, исправленной в P ′ . Более формально, задается политика безопасности φ, и программы P и P ′ . Цель φ состоит в шифровании того что является эксплойтом. Наша цель - сгенерировать входные данные x такие что φ(P (x)) = unsafe, но φ(P ′ (x)) = safe.
6. 2.3 Границы задачи и подход.
8. Уязвимости, рассматриваемые в этом документе. Работа сосредоточена на уязвимости в приеме входных данных когда пользовательские входные данные недостаточно проверяются в P , но устраняются через новые проверки в P ′. Например, если P уязвима к атаке целочисленного переполнения, то в P ′ можно вставить проверку на это переполнение, и в конечном счете мы будем использовать эту вставленную проверку чтобы помочь устранить эксплойт. Другой пример, когда P содержит типичное переполнение буфера, где входные строки могут быть слишком большими, но это решается в P ′ с помощью добавления проверки на слишком длинные входные данные. Однако, исправление, в котором P ′ увеличивает размер буфера адресов для вмещения очень длинных входных данных, в настоящее время находится за пределами нашей постановки задачи. Мы планируем сосредоточиться на других уязвимостях в этой работе.
10. Обзор подхода. Предлагаемый подход к APEG основан на наблюдении, что новые проверки, добавленные в P ′ часто 
    1) определяют точку уязвимости, где происходит уязвимость, и 2) определяют условия, в которых P может быть атакована эксплойтом . Таким образом, входные данные x, которые не прошли дополнительных проверок в точке уязвимости в P ′ являются кандидатами в эксплойт для P . Мы называем x кандидатом в эксплойт, потому что новые проверки могут не подтвердить реальной уязвимости. Эксплойт подтверждается с помощью поверки checking φ(P (x)). Поэтому мы пытаемся сгенерировать входные данные, которые не пройдут новых проверок, вставленных в точке уязвимости программы.
12. Можно использовать готовые средства обнаружения точки уязвимости и добавленных проверок. В предлагаемой реализации, используется EBDS [13], средство, которое автоматически сравнивает два исполняемых файла и докладывает о различиях. Также можно использовать готовые проверки для политики безопасности φ. Например, динамический анализ заражения это тип контроля за исполнением обычно используемый для обнаружения широкого спектра эксплойтов.
14. Таким образом, данная работа фокусируется на технической задаче автоматической генерации кандидатов в эксплойты которые достигнут и не пройдут новых проверок в пропатченной версии программы. Для решения этой технической задачи, предлагается подход, который 1) генерирует набор ограничений на входные данные, и 2) находит с помощью этих ограничений шаблоны кандидатов в эксплойты
16. Более формально, вычисляются слабейшие предусловия [11] на пространстве состояний входных данных P, чтобы они выполнили и не прошли нужные проверки Слабейшим предусловием является формула F : I → {true, false } где I это пространство состояний входных данных, и положительным ответом будет являться наш образец эксплойта. например, формула ограничения

.	32	)
F(input) = input%2 == 0 ∧ s = input + 2(mod2

∧ ¬(s > input)

 

удовлетворяет всем входным данным которые выполняют ветвь true в P на рис. 2 и переполняются. Наконец, задавая формулу ограничения, мы запрашиваем генерацию ответа, удовлетворяющего формуле (т.е входных данных x таких, что F(x) = true). Если нам возвращается решение, то оно будет считать кандидатом в эксплойт.

 

Таким образом, данный подход можно разделить на этапы:

1. Обнаружить новые проверки, добавленные в P ′ . Остальные шаги выполняются для каждой новой проверки индивидуально..
2. Сгенерировать потенциальный эксплойт x, который не пройдет новую проверку в P ′ используя:
1. Вычисления предусловий чтобы провалить новую поверку в P ′ . Результато будет вормула ограничения F. Мы представляем три подхода к генерации формулы ограничения, описанных в части 3.2.1.
3. Использование решателя (поиска решений) для обнаружения x таких, что F(x) = true. x это потенциальный эксплойт.
4. Подтвердить, является ли x реальным эксплойтом, с помощью запуска проверки политики безопасности
5. φ(P (x)).
7. если нужно, мы можем генерировать полиморфные варианты. Пусть x будет известным эксплойтом.  
   Пусть F′ (X ) = F(X ) ∧ (X <> x). тогда x′ такой, что F′ (x′ ) = true будет полиморфным вариантом потенциального эксплойта. Процесс может быть повторен для перечисления полиморфных вариантов.

• Автоматическая генерация эксплойтов на основе патчей

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

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

3. Первый этап в нашей генерации эксплойтов на основе патчей это нахождение отличий в P и P ′ чтобы найти новые проверки, добавленные в P ′ . Существует несколько инструментов для вычисления различий в бинарных кодах, которые являются достаточно точными и могут быть использованы для определения, какие новые проверки появились в коде. Ищутся новые проверки, которые вводят новые пути исполнения программы. В работе используется eEyE’s Binary Diffing Suite (EBDS) [13] поскольку она находится в свободном доступе.
5. Данный подход не предполагает, что будут обнаружены только семантические различия. Фактически, данное средство (EBDS) основано практически только на синтаксическом анализе дизассемблированного бинарного кода. В результате, список новых проверок, основанных на синтаксическом анализе является расширением значимых проверок. Этот способ не подходит для генерации эксплойтов для семантически бессмысленных различий. Например, если P имеет проверку i > 10, и P ′ имеет проверку i − 1 > 9, EBDS может доложить о новой проверке. Различия, не имеющие семантического значения, отсеиваются на этапе проверки. EBDS возвращает список отличий; мы фильтруем его с помощью новых проверок. EBDS также выясняет, какая ветвь новой проверки (true or false) соответствует новому пути исполнения кода. Мы предполагаем, что новый путь соответствует провалу проверки. Например, на рис. 2 EBDS доложит, что новый путь представлен ветвью false в новой проверке в строке 5, и мы сделаем вывод, что s > input это проверка, которая не должна быть пройдена.
7. Напомним, что оставшиеся шаги в данном процессе генерации эксплойтов на основе патчей выполняются для каждой новой обнаруженной проверки. Конечно, для этого подхода было бы неплохо использовать более совершенные инструменты для вычисления различий, которые дают на выходе меньше проверок, которые при этом имеют большее семантическое значение, а итераций необходимо меньше. В оценке работы, мы измеряем количество новых проверок, о которых доложило средство EBDS, но предполагаем, что злоумышленник может параллельно обнаруживать эти проверки. Это реально, поскольку злоумышленники часто имеют много скомпрометированных хостов, которые они могут использовать для проверки каждого обнаруженного различия
8. 3.2 Генерация формулы ограничений
10. В данном разделе обсуждаются средства для автоматической генерации формул ограничений. Для начала определяется, почему нужно рассмотреть несколько различных подходов. Затем проводится подготовку к генерации формулы, используя динамический и статический анализ. И наконец, показывается, как адаптировать эти идеи для соединения статического и динамического анализа.
12. 3.2.1 Ключевые моменты разработки
14. Наиболее важный вопрос при построении формулы - выяснить, какие инструкции включить в формулу. Нужно включить инструкции для всех эксплойтных путей, чтобы сгенерировать потенциальный эксплойт. Однако, количество эксплойтных путей обычно лишь часть всех путей, ведущих к новой проверке. Должна ли формула охватывать все такие пути, некоторые из них, или только один? Рассмотрим три подхода к ответу на этот вопрос: динамический подход, который рассматривает только один путь за раз, статический подход, который рассматривает множество путей в CFG не перечисляя их, и комбинирование статического и динамического подходов.
16. Динамический подход: Создание формулы ограничений из образца исполнения  
    В некоторых случаях, новые проверки появляются на программном пути, который выполняется с известными входными данными. Такие нормальные входные данные можно найти, исследуя логи нормальных входных данных, используя фаззинг, или другие средства. Конечно, нормальные входные данные будут, скорее всего, удовлетворять новым проверкам; в противном случае, это будет потенциальным эксплойтом.
18. Для таких входных данных i, где P ′ (i) выполняет новую проверку, используется средство для динамического анализа, чтобы сгенерировать ограничивающую формулу, представляющую ограничения на входные данные для любого исполнения части кода, вплоть до новой проверки.
20. Динамический подход дает формулу, которая обычно является наименьшей из трех подходов. Благодаря этому, динамический подход обычно быстрее генерирует потенциальный эксплойт.
22. Уязвимость ASPNet Filter, по нашей оценке это пример, демонстрирующий реальную пользу динамического подхода. В ASPNet Filter, уязвимость находится на веб-сервере и новая проверка добавляется на общем пути кода, который выполняется большинством URI запросов. Таким образом, достаточно просто получить по крайне мере одни "доброкачественные" входные данные, которые дойдут до места новой проверки, поэтому имеет смысл начать анализ с этого пути и посмотреть, можно ли сгенерировать эксплойт на этом пути.
24. Статический подход: создание формулы ограничений из графа потока управления . Другой подход состоит в создании формулы из CFG [6]. В частности, в статическом случае имеем дело с CFG, который включает все пути из инструкции, где входные данные считываются для новой проверки. Задача состоит в создании CFG, который включает только пути к новой проверке. Вычисление формулы через CFG является более эффективным чем вычисление отдельной формулы для каждого пути в CFG по отдельности [6].
26. Статический подход будет генерировать потенциальный эксплойт если какая-то часть CFG может быть атакована. Так как статическая формула потенциально включает все инструкции в фрагменте CFG, формула обычно больше и следовательно требует больше времени на решение. Примером работы этого подхода является уязвимость в DSA SetItem.
28. Создание формулы ограничений с использованием комбинирования динамического и статического подхода.
29.     Если фрагмент CFG содержит большое число инструкций (так как охватывает большое количество путей), сгенерированная формула может быть слишком большой для поиска решений. С другой стороны, эксплойт может никогда не пойти по тому же пути исполнения что и известные входные данные, Таким образом, чисто динамический подход может не работать.
30. Предлагается третий подход, который смешивает динамический и статический подход для создания ограничений. Комбинированный подход заключается в объединении информации о путях кода, которые мы знаем как выполняются с известными входными данными, и о дополнительных путях кода, которые мы хотим изучить, используя статический анализ. Например, могут быть известны входные данные, которые не достигают места новой проверки, но доходят до середины. Можно использовать динамический анализ в точке посередине пути, и затем использовать статический подход для всех путей от середины до новой проверки.
32. Преимущество комбинированного подхода состоит в том, что он обеспечивает способ рассмотрения подмножества путей таким образом, чтобы создаваемая формула была достаточно мала для поиска решений чтобы сгенерировать потенциальный эксплойт. Уязвимость IGMP это пример такого случая, когда ни статический, ни динамический подход не работают по отдельности, но комбинирование методов создает рабочий эксплойт.
2. Создание формулы ограничений из образца исполнения
4. Здесь предлагается повторение общего метода для создания формулы из исполняемого пути
6. Динамический подход создания формулы берет на вход P ′ , новую проверку, и входные данные i. Выполняем P ′ (i) и записывается каждая инструкция, которая выполняется до проверки образца. Формулу ограничений генерируется по инструкциям, выполненным на этом пути. Для эффективности, записываются только инструкции, зависящие от входных данных, так как берутся в расчет только те уязвимости, которые могут быть использованы через пользовательских входных данные.
8. Табл. 1.
11. Моделирование исполняемых инструкций х86. Чтобы получить формулу ограничений, нам нужно знать эффект от каждой исполняемой инструкции. X86 это сложный набор инструкций. Чтобы точно построить формулу ограничения, нужно правильно смоделировать эффект от инструкции x86, в том числе все неявные побочные эффекты такие как обновления регистров состояния. Таким образом, используется ассемблерный язык моделирования, называемый Vine [2]. Возможность точного моделирования эффектов от каждой инструкции x86 имеет большое значение для автоматической генерации эксплойтов.
13. Была создана модель, которая проверяет каждую инструкцию с помощью Vine. Все объекты, которые не зависят от входных данных, заменяются на конкретные значения. В конце, утверждается, что каждая ветвь состояний будет оценена так же как и исполняемый путь.
15. Создание формулы ограничений по модели пути. Результат выполнения P ′ (i) определяет один путь программы, который так же является действующей моделью в Vine. Формула ограничений вычисляется по модели прямой линии с помощью вычисления слабейших предусловий [11]. Вычисляется слабейшее предусловие используя эффективный алгоритм и реализацию, приведенные в Brumley и др. [6].
17. Табл. 1 показывает правила для вычисления слабейшего предусловия. если фрагмент программы соответствует шаблону, показанному ниже горизонтальной линии слева от символа (⊢), выполняется расчет, показанный сверху. Полученная формула находится справа от (⊢).Правила индуктивно образуют алгоритм. Алгоритм инициализируется с помощью wp(P ′ (i), Q), где Q это предикат, утверждающий, что новая проверка не пройдена.
3. Создание формулы ограничений из CFG
5. Так как рассматриваются только те пути, на которых производится новая проверка, то нужно убрать отчеты Vine для других путей. Используется метод, который создает уменьшенную модель, которая включает только заявления, относящиеся к выполнению синхронизации узла из данного начального узла в CFG. В статическом случае, начальный узел это входная инструкция, а синхронизируемый узел это новая проверка.
6. Таким образом, меньший, более компактный CFG как правило приводит к меньшей и более легкой в решении формуле.. Опыт показал три распространенных причины, по которым формула может решаться дольше: 1) “мертвый” код в модели, где значения вычисляются, но нигде не используются, 2) алгебраические упрощения которые могут быть выполнены, и 3) перерасчет часто используемых подвыражений. Была внедрена общая оптимизация компилятора в используемый язык для оптимизации модели: убран мертвый код, проделано как можно больше алгебраических упрощений, и убраны избыточные подвыражения. Показано, что эта оптимизация может удвоить скорость вычисления формулы.
8. Вычисление слабейшего предусловия используется для динамического случая и в равной степени относится к любому из ациклических CFG [6]. Был создан ациклический CFG, "разворачивая" петли и используя рекурсию фиксированное количество раз..
4. Создание формулы с помощью комбинирования статического и динамического подхода
6. Формула должна охватывать все инструкции для эксплоитных путей, чтобы можно было сгенерировать потенциальный эксплойт. Динамический подход рассматривает только один путь программы до новой проверки, но генерирует небольшую формулу и требует входные данные, которые выполняют проверку. Статический подход охватывает больше путей, но может создавать большую формулу. На высоком уровне единственное отличие между ними состоит в том, динамический подход использует трассировку для создания линейной программы, в течение которой мы создаем формулу, в то время как статический
7. подход использует программу для создания разветвленной ациклической программы. Хотя оба метода по отдельности уже использовались ранее для создания формулы, впервые предлагается скомбинировать динамический и статический подход и продемонстрировать его осуществимость на практике.

14. Рис. 3
16. Предположим, что у нас есть трассировка, содержащая исполняемые инструкции 0..n. Пусть инструкции 0 ≤ i ≤ n выполняются динамически, и пусть будет путь от i до новой проверки, как показано на рис. 2. Строится комбинированная модель, состоящая из двух частей. Первая - это линейная часть до i-той инструкции, а с i до новой проверки есть несколько путей. На втором участке выполняется статический анализ нескольких путей. Затем, на основе этой модели вычисляется слабейшее предусловие. В худшем случае, все пути от i до новой проверки являются неосуществимыми, т. е нет таких входных данных, которые проходят путь 0..i и затем переходят на i+1 к новой проверке. Таким образом, комбинированный метод берет две модели и последовательно объединяет их, создавая новую модель.
17. Например, по оценке уязвимости IGMP, можно объединить исполняемый путь, который не может стать эксплойтом, с частью процедуры, содержащей новую проверку, чтобы создать комбинированную модель. Генерирование формулы и решение этой модели, produces создает рабочий эксплойт для для данного примера, но ни динамический, ни статический подход по отдельности не могут сделать это.
19. Автоматически комбинируемое исполнение. Процесс автоматического комбинирования требует автоматического определения точки, где соприкасаются модели. На рис. 3, задача состоит в выборе точки i. Конечно, следует выбирать i так, чтобы был путь в статической модели от i до новой проверки. Однако, таких путей может быть много.
21. Прямой подход состоит в выборе i, которая ближе всего к новой проверке. И если формула, сгенерированная комбинированной моделью, не имеет эксплойта, следует выбрать инструкцию i − 1 и повторить все снова.
23. В процессе эксперимента выяснилось, что более быстрым чем итеративный подход является выбор i на границе процедуры. Процедуры предназначены для выполнения специальных задач, независимых от остального кода. Более того, при выборе точки процедуры, комбинированная модель включает общие задачи, вместо специфических путей кода. Одно из преимуществ выбор границы процедуры это относительная простота воплощения автоматического комбинирования: нужно просто установить вызов статической модели процедуры в нужной точке.
3. Генерирование потенциального эксплойта из формулы ограничений
5. Была использована STP, процедура, поддерживающая битовые операции, в качестве генератора потенциального эксплойта из формулы. Выполняющий будет гарантировать, что принятые им входные данные заставят выполнение программы придти к новой проверке и провалить ее.
7. Необходимость поддержки битового уровня необходима, поскольку ассемблерный код обычно использует битовые операции. Например, для обнуления регистра r как правило используется не mov r, 0, а его эквивалент xor r, r.
9. Если возвращается ответ, что нет подходящего решения для данной формулы, это означает, что невозможно получить такие входные данные, которые проходят пути, охваченные формулой, and и проваливают проверку. Таким образом, необходимо получить новую формулу, охватывающую другие пути исполнения программы.
11. В некоторых случаях ответ может возвращаться слишком долго. В таком случае устанавливается таймаут а затем переход к построению другой формулы.
4. Генерирование полиморфных эксплойтов
6. Этот подход позволяет перечислить все полиморфные варианты потенциальных эксплойтов на путях исполнения, охватываемых F. Предположим, что x удовлетворяет F. пусть F′ (X ) = F(X ) ∧ (X <> x). F′ удовлетворяет всем входным данным, кроме x которые провалили проверку в F. Следовательно, удовлетворительный ответ x′ такой, что F′ (x′ ) = true это полиморфный вариант эксплойта. Этот процесс может быть повторен столько раз, сколько потребуется.
5. Подтверждение потенциального эксплойта
7. Потенциальный эксплойт x  подтверждается проверкой нарушения политики безопсности φ во время исполнения P (x). Был использован готовый детектор эксплойтов с динамическим анализом заражения кк черный ящик для φ для уязвимостей безопасности памяти. Также возможно использование других обнаружителей эксплойтов. Потенциальный эксплойт подтверждается, когда детектор возвращает значение unsafe. Если возвращается safe, и все пути к новой проверке еще не проанализированы, тогда попытка повторяется на других путях кода пока не будет сгенерирован эксплойт, или пока все пути не будут исчерпаны.
9. 4. Оценка
11. Данный подход оценен на пяти различных уязвимостях программ Microsoft, имеющих доступные патчи. Эксперимент подчеркивает, что все три подхода к получению формулы ограничений — динамический статический и комбинированный — является ценным в различных условиях.
13. 4.1 Описания уязвимостей и эксплойтов
14. DSA SetItem уязвимость целочисленного переполнения. The DSA SetItem в comctl32.dll выполняет управление памятью, похожее на realloc [35]. Процедура принимает указатель p, размер для каждого объекта s, и общее число объектов n. Процедура вызывает realloc(p, s ∗ n). Переполнение может произойти в результате умножения s ∗n, в результате чего возващаемый размер указателя будет меньше, чем ожидалось. Последующее использование указателя в лучшем случае приведет к краху приложения, и в худшем - может быть использовано для захвата управления приложением. DSA SetItem может быть вызван непосредственно, или косвенно через вредоносную страницу с помощью метода setSlice JScript. На практике, эта уязвимость широко используется в сети открыто вредоносными или взломанными сайтами [29].
16. Модифицированная версия добавляет логику для защиты от целочисленного переполнения. В частности, добавляется проверка на то, что переполнение никогда не произойдет и результат будет меньше 231
18. EBDS потребовалось 371.9 секунд для обнаружения различий. 21 функция была определена как измененная, и 5 новых функций было добавлено. Сгенерированный при этом эксплойт вызывал DoS-атаку, т.е крах Internet Explorer. Любая φ, которая может обнаружить злоупотребление указателем подходит: в эксперименте использовалась TEMU [2]. Также были указаны конкретные места памяти для перезаписи. Определение конкретного адреса для успешного захвата контроля требуется прогнозирования распределения памяти процесса, которое изменяется при каждом вызове процесса. Злоумышленники делают это, многократно вызывая атаку, пока контроль над приложением не будет успешно захвачен.
20. Уязвимость ASPNet Filter раскрытия информации (MS06-033; Bugtraq ID#18920; CVE-2006-1300).
22. ASPNet Filter DLL отвечает за фильтрацию ASP-запросов для Microsoft .NET IIS Server, и уязвим к атаке с целью раскрытия информации. Модуль фильтрует имена конфиденциальных папок из URI-запросов во время обработки так, что информация из этих папок не раскрывается при ответе. Эти папки строятся автоматически, используя шаблон по умолчанию в ASP. например, App Data, App Code, и Bin используются для хранения файлов данных, динамически компилируемого кода и компилируемых сборок соответственно. Эксплойт для этой уязвимости позволяет атакующему видеть файлы в этих папках. Это серьезная уязвимость потому что скрипты в этих директориях часто содержат конфиденциальную информацию, такую как пароли, схемы БД, и др.
24. Не модифицированная версия выполняет надлежащую фильтрацию для URI-запросов, использующих прямой слэш (’/’), но не обратный (’\’). Модифицированная версия исправляет эту уязвимость с помощью проверки на’\’ изменение его на ’/’.
26. EBDS потребовалось 16.6 секунд для определения различий. Одна новая функция была добавлена, а аткже 4 изменения были внесены в существующие функции для вызова новой. Первая же попытка создать эксплот была успешной.
28. Сгенерированный эксплойт позволял читать файлы в защищенных директориях. В настоящее время нет реализованной политики безопасности φ, которая обнаруживает такие атаки, поэтому потенциальный эксплойт был подтвержден вручную.
30. IGMP уязвимость отказа сервиса (MS06-007; Bugtraq ID#16645; CVE-2006-0021). Протокол IGMP (In-ternet Group Management Protocol) протокол используется для управления членства в группах многоадресной рассылки. Эксплойт для этой уязвимости - это IGMP пакет запроса с неверными опциями IP. Это может привести к входу в бесконечный цикл. Поскольку IGMP это услуга сети на уровне системы, эксплойт "заморозит" всю уязвимую систему. Патч добавляет проверку в IGMP для неверных опций IP.
32. EBDS потребовалось 157.08 секунд для сравнениях двух версий tcpip.sys. одна функция была изменена.
34. Сгенерированный эксплойт успешно вызвал отказ сервиса. Нет разработанной политики безопасности φ, которая обнаруживает тупик из-за бесконечного цикла, поэтому потенциальный эксплойт был подтвержден вручную.
36. GDI уязвимость целочисленного переполнения (MS07-046; Bugtraq ID#25302; CVE-2007-3034). Windows Graphic Device Interface (GDI) это основное средство для отображения графики на экране. GDI ответственен за отображение метафайла графики, который уязвим к целочисленному переполнению. Целочисленное переполнение может впоследствии привести к переполнению динамической памяти, которое в лучшем случае вызовет крах системы, и в худшем - приведет к захвату контроля.
38. Патч устраняет целочисленное переполнение добавляя 5 дополнительных проверок при загрузке метафайла. Эксплойт может быть создан когда хотя бы одна из проверок не пройдена.
40. EBDS потребовалось 109 секунд для сравнения версий. было выявлено пять дополнительных проверок.
42. Сгенерированный эксплойт вызвал отказ сервиса. Эта уязвимость схожа с DSA SetItem: успешный захват контроля требует многократного повторения атаки. Подходит любая φ, которая обнаруживает злоупотребление указателем : в эксперименте использовалась TEMU [2].
44. PNG уязвимость переполнения буфера (MS05-025; Bugtraq ID#13941; CAN-2005-1211). PNG (Portable Network Graphics) формат файла изображений, который используется многими программами, такими как Internet Explorer и Microsoft Office. Каждое PNG изображение содержит набор записей, которые определяют различные свойства избражения. В режиме индексированных цветов, формат записи определяет значение дополнительного бита альфа-канала для каждого индексированного цвета. переполнение буфера происходит в ранних реализациях Microsoft, когда число битов альфа-каналов превышает количество заранее заданных цветов.
46. Патч добавляет дополнительную проверку для поля записи PNG.
48. Общее время на вычисление различий составило 27.05 секунд. Изменения были найдены только в уязвимой процедуре
50. Сгенерированный эксплойт вызвал крах программы, схожий с GDI и DSA SetItem. Снова использовалось TEMU [2] для подтверждения потенциального эксплойта, но любая φ, которая обнаруживает злоупотребление указателем также подходит. Это атака на динамически распределяемую память и так же требует повторения атаки для успешного захвата контроля.
2. Генерация эксплойта с использованием динамического анализа

	DSA		SetItem	ASPNet		Filter	GDI
Trace	4.99			4.50			9.92
Formula	0.52			0.14			0.41
Solver	0.17			6.93			0.01
Total	5.68			11.57			10.34

Используя динамический анализ, были успешно сгенерированы эксплойты для уязвимостей DSA SetItem, ASPNet_Filter и GDI. Для DSA SetItem, была записана трассировка IE 6 при загрузке вебстаницы, которая вызывает метод setSlice ActiveX, который в свою очередь вызывает DSA SetItem. Для ASPNet Filter, была записана IIS обработка HTTP запросов из лога файла. Для GDI, было создано изображение в PowerPoint презентации, затем изображение было сохранено в формате метафайла Windows. Было записано выполнение небольшого GDI приложения, загружающего сохраненный файл. все трассировки были записаны, используя TEMU [2].

4. Таблица 2. Динамический подход
6. Таблица 2 показывает обзор результатов. Все время представлено в секундах. Строка “Trace” показывает время, затраченное на генерацию трассировки в TEMU. Строка “Formula” показывает время на генерацию формулы. Строка “Solver” показывает, сколько было затрачено на решение формулы
8. Общее время на генерацию эксплойта после вычисления различий составило менее 12 секунд во всех экспериментах. Если включить время сравнения, тогда общее время для генерации эксплойта для DSA SetItem - 377.58 сек., для ASPNet Filter - 28.17 сек. , и для GDI - 119.34 сек.
10. Для уязвимостей IGMP и PNG Невозможно было сгенерировать эксплойт, используя динамический подход.