ОРИГИНАЛЬНАЯ СТАТЬЯ
ПЕРЕВЕДЕНО СПЕЦИАЛЬНО ДЛЯ xss.pro
КАМНЯМИ КИДАТЬ Jolah Milovski
Одна из основных идей Fuzzing заключается в использовании большого количества входов для запуска различных ветвей логики в программе, поэтому успех Fuzzing тесно связан с генерацией входов, которые могут быть в различных форматах, таких как файлы, код, json-данные и т.д. Но все виды данных имеют свой формат, так же как и вход в программу. Для того чтобы хорошо подобрать входные данные программы, необходимо разработать некоторую синтаксическую спецификацию для входных данных. То же самое справедливо и для Fuzzing, где часто бывает полезно определить синтаксическую спецификацию для входа в программу, чтобы достичь хорошего результата Fuzzing.
Вообще говоря, регулярные выражения часто являются хорошим выбором для фаззинга простых программ, поскольку их свойства конечного автомата состояния позволяют легко рассуждать о них, чтобы получить удовлетворительный вход, но они могут быть немного сложными, если объект фаззингадостаточно сложный.
Я видел языки, разработанные для лучшего выполнения определенных функций, что, очевидно, очень полезно с точки зрения компьютерной теории, и некоторые специальные функции выполняются качественно с помощью специального языка, но это действительно слишком сложно для Fuzzing, а грамматика - это действительно нечто среднее между регулярными выражениями и специализированными языками. Она проста в понимании и делает то, что ожидается от нее. Fuzzing - генерирует большое количество входов - потому что грамматика могут определять большое количество свойств входов, идеально выражая синтаксическую структуру сложного входа.
Грамматика обычно состоит из символов и набора выражений, например, A = 10 | 9 | 0 | 1. Символизация делает возможной рекурсию, и если предположить, что B = A | AB, то это, несомненно, увеличивает диапазон, предоставленный символами. Следуя этой идее, мы можем получить арифметическое выражение.
Затем, расширяя символы внутри <start> один за другим и рандомизируя процесс, вы получаете большое количество законных арифметических выражений. Как и большинство грамматик, Грамматика должна иметь свой Тип, чтобы проверить ее легитимность, и приведенная выше Грамматика может быть определена на примере Python.
Первые три строки кода определяют, как должна быть составлена грамматика в Python. Доступ к компонентам текущей грамматики и манипуляции с ними можно осуществлять с помощью EXPR_GRAMMAR["<цифра>"] в коде.
Итак, разбираемся на примере? Один из самых простых способов — замена строк, потому что в Grammar : Левая и правая стороны сами по себе являются отношениями отображения, поэтому наиболее интуитивно понятным выбором является использование замены строк для непрерывной итерации.
Используя приведенное выше выражение, можно сделать простую грамматическую ошибку. В процессе написания Fuzz-тестов на самом деле сталкиваемся со многими компромиссами между удобством и скоростью или различной осуществимостью. Взяв приведенное выше выражение в качестве примера, мы абсолютно не хотим провала теста из-за, бесконечной рекурсии или анализ большого количества символов.Однако такой Grammar Fuzz сталкивается с рядом проблем: большое количество строковых операций поиска и замены приводит к неэффективности, и видно, что происходит сбой генерации ввода (ExpansionError), а это типичный контекстно-свободный Fuzz. Однако, в зависимости от вышеперечисленных функций, мы можем очень хорошо генерировать большое количество некоторых входных данных, пока мы пишем грамматически - правильные тесты.
Или аналогично протоколу HTTP (но это не подготовлено для вышеупомянутого Fuzz, просто для справки):
На данный момент мы понимаем важность грамматики для фаззинга. Правильная грамматика может эффективно генерировать большое количество допустимых входных данных, но это только с точки зрения состава входных данных (синтаксиса). В конце концов, это огромный диапазон, хотя иногда он удовлетворяет входному формату программы, но может не работать для фаззинга, который встречается очень часто. Снова взяв компилятор в качестве примера, ваша программа должна иметь правильную семантику, удовлетворяющую синтаксису языка. Но семантику уже трудно выразить в грамматике. Взяв в качестве примера грамматику генерации URL, трудно определить диапазон портов просто с помощью грамматики. Столкнувшись с такой проблемой, самое простое решение — ограничить ее в Fuzz вместо Grammar. Взяв в качестве примера грамматику URL-адресов, прежде чем URL-адрес, сгенерированный Grammar, будет фактически передан цели в качестве входных данных, он должен оцениваться по «законности» URL-адреса в системе Fuzz. Суждение здесь может быть ограничено автором в соответствии с на собственные нужды.
Потребность в грамматике в проекте фаззинга не статична, поэтому одно из основных требований к грамматике - быть расширяемой.
Иногда мы хотим расширить функциональность программы, не затрагивая исходную часть (аналог наследования в программировании), что представляет собой следующую очень простую операцию.
Проще говоря - как-то так:
В то же время, при написании Fuzz точно не хочется постоянно писать лишку, поэтому в помощь нам понадобится немного грамматики.Вот метод анализа ENBF:
Для Grammar мы должны определить его легитимность, иначе мы неизбежно столкнемся с различными ошибками в использовании, поэтому проверка синтаксиса необходима, так же как очень важна проверка синтаксиса компилятора:
Инструменты, перечисленные выше, являются широко используемыми инструментами.В процессе написания Fuzz должны быть написаны различные инструменты в соответствии с актуальными проблемами.
Приведенный выше simple_grammar_fuzzer на самом деле имеет много проблем, таких как низкая производительность, ограниченное количество парсинга символов, легкость возникновения ошибок и т. д. Поэтому требуется более сложный алгоритм. Дерево вывода было выбрано здесь, потому что древовидную структуру легко проследить, а ветви можно легко добавлять и удалять. Написание Fuzz на самом деле является непрерывным анализом дерева вывода и непрерывным расширением дочерних узлов.
Из приведенного выше простого алгоритма видно, что ядром всего Grammar Fuzz является формирование соответствующей структуры данных с помощью большого количества расширений символов, поэтому структура данных, используемая для хранения или расширения символов, на самом деле особенно важна. Древовидная структура дерева вывода действительно полностью отвечает нашим требованиям, а расширение древовидной структуры сверху вниз соответствует расширению символов, а также производные деревья позволяют нам контролировать состояние всего процесса расширения, например те узлы, которые были расширены, или требуется ли расширение узла и т. д. При этом скорость добавления новых узлов в процессе расширения намного выше, чем процесс замены символа значением, поэтому использование этой структуры данных также дает некоторый прирост производительности.
В качестве примера:
С точки зрения алгоритма дерева вывода, сначала <start> является начальным узлом, а затем находит соответствующее ему выражение, поэтому он выберет <url> в качестве дочернего узла цикл повторяется до тех пор, пока у узла больше не будет соответствующего дочернего узла, а затем анализируется вся древовидная структура и выводятся соответствующие структурированные данные.
Соответствующие данные представлены следующим образом:
SYMBOL_NAME представляет символ, CHILDREN представляет дочерний узел, а конкретная структура данных: DerivationTree = Tuple[str, Optional[List[Any]]]. Наследование тут представлено двумя моментами:
Иногда полностью случайное расширение выражений на самом деле будет тратить много времени и ресурсов, поэтому вы можете добавлять значения вероятности к выражениям. Это связано с множеством проблем вероятности, и некоторые данные исходят из статистических законов, таких как после данного leaddigit вероятность, соответствующая символу, в углубленном анализе отсутствует.
Большое отличие от предыдущей Грамматики заключается в том, что текущая Грамматика может добавлять к значениям в списке случайные вероятности, добавляя аннотации, чтобы автор мог получать информацию из других каналов через реверс и ее можно было использовать в Fuzz. Теперь вопрос очевиден, как определить вероятность? Когда автор Fuzz не может прямо указать конкретную вероятность всех элементов, соответствующих символу, наиболее прямыми правилами, которым можно следовать, являются следующие три формулы:
Общий смысл также хорошо понятен, то есть а представляет элемент с известной вероятностью, а элемент с неизвестной вероятностью, представленный u, с известной вероятностью может быть естественно пропущен через opts метод добавляет вероятность к соответствующему элементу, а элементу с неизвестной вероятностью присваивается вероятность в соответствии с принципом выравнивания вероятностей. После этого естественно ввести вероятность в Fuzz, чтобы при генерации начальных значений можно было придавать веса выбору анализа символов, тем самым повышая эффективность Fuzz.
Что касается конкретной реализации Fuzz, на самом деле, по сравнению с вышеупомянутой Grammar Fuzz, она только добавляет доступ к аннотации opts, так что вес значения вероятности может быть добавлен во время случайного анализа. Но преимущества, которые дает это, очевидны, и вы даже можете управлять Func, заданной входной целью Fuzz и т. д. Но есть и другая ситуация: когда я разбираю грамматический символ в первый раз, я надеюсь, что его вероятность равна 0,3, а когда я разбираю грамматический символ во второй раз, я надеюсь, что его вероятность равна 0,5. на самом деле может использовать контекст в разных символах копии контекста, которым вы хотите назначить разные вероятности, в качестве примера возьмем IP_ADDRESS_GRAMMAR:
Для того, чтобы сделать каждый разбор <octet>При использовании разных вероятностей его можно расширить, чтобы сформировать следующий синтаксис:
IP_ADDRESS_GRAMMAR: Grammar = {
"<start>": ["<address>"],
"<address>": ["<octet-1>.<octet-2>.<octet-3>.<octet-4>"],
# ["0", "1", "2", ..., "255"]
"<octet-1>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-2>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-3>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-4>": decrange(0, 256) #ну вы поняли что он там обозначает))
}
Таким образом, когда выполняется синтаксический анализ, к каждому синтаксическому анализу может быть привязана разная вероятность. Вот функции, которые помогут с реализацией:
После копирования контекста мы можем получить желаемый результат, выполнив что-то вроде следующего:
Однако возникает другой вопрос: действительно ли уместно, чтобы вероятность оставалась неизменной после того, как она была присвоена символу? В реальном фаззе, с нашим непрерывным пониманием цели, или некоторых других ситуациях, например, когда желаемый результат не появляется в течение длительного времени, также необходимо вовремя менять стратегию, но если фазз может разумно подстраиваться настройка различных символов сама по себе. Если используется значение вероятности, это значительно уменьшит нагрузку и даст лучшие результаты тестирования программного обеспечения. Лучший способ — позволить Fuzz узнать, насколько большое значение вероятности должно быть присвоено определенным символам, изначально задав их входными данными.Этот метод очень полезен в определенных сценариях:
Теория уже существует, так как же ее реализовать? Первым шагом должно быть восстановление существующих входных начальных значений в дерево вывода, а затем вычисление будущего значения вероятности соответствующего значения каждого символа вида дерева вывода.
Как и выше, предположим, я задаю seed 127.0.0.1, тогда после разбора значение вероятности 0 в <octet> будет ограничено 50% и 25% для 127 и 1 соответственно, затем соответствующие значения вероятности могут быть присвоены <octet> при выполнении Fuzz. Что же произойдет, если вы протестируете некоторые менее распространенные функции? Фактически, вероятности получаются из исходных входов часто используемых функций, а затем переворачиваются, например, вероятности часто используемых входов выглядят следующим образом.
Тогда после перелистывания это:
Вышеизложенное является основной идеей сосредоточения внимания на тестировании общих функций или очень полезных функций, упомянутых ранее. Еще один ключевой момент здесь - помочь нам сосредоточиться на конкретных функциях цели через входы. Разница между этим и тестированием общих функций заключается в что мы должны сначала найти пакет специальных входных данных, которые можно использовать в качестве начальных значений для выполнения вероятностного анализа и ограничений на процесс синтаксического анализа, чтобы последующие мутации всегда могли иметь более высокую целевую частоту попаданий.
Когда некоторые входы сгенерированы, автор Fuzz может захотеть настроить некоторые ограничения на них и получить другие операции, доступ к которым можно получить через pre funcЗаканчивать. Это похоже на хук, поэтому время срабатывания func обычно делится на два типа.До или после генерации входных данных выражение в грамматике выглядит следующим образом:
Другой после генерации Seed:
Например, если сгенерированные цифры не соответствуют потребностям Fuzz, мы можем использовать это для своевременного внесения исправлений, чтобы повысить эффективность Fuzz.
В дополнение к проблемам производительности Fuzzing, еще одной проблемой является проблема вариационного руководства. Хотя внутренний разбор грамматики является случайным во время генерации входов Grammars Fuzz, большое количество входов может вызвать одну и ту же ветвь для цели Fuzz, что затрудняет достижение желаемого значения покрытия кода. Для AFL-подобного покрытия bootstrap Fuzz, можно подсчитать покрытие кода для хорошего bootstrap из-за заглушек исходного кода white-box Fuzz, но есть много случаев, таких как black-box или даже WebServer-targeted Fuzz, где подсчет покрытия кода не является простой задачей, и мера, которую необходимо принять, заключается в постоянном увеличении покрытия кода. разнообразие при генерации входных данных, например, путем подсчета процесса расширения дочерних узлов в вышеупомянутом дереве деривации таким образом, чтобы он был смещен в сторону узлов, которые еще не были расширены при генерации входного корпуса. Здесь возникает новая проблема: как быстро улучшить покрытие кода?
При выполнении Fuzz некоторые части входного корпуса иногда идентифицируются как ключевые слова, например, int в C. Если Fuzz сказать использовать эти ключевые слова, покрытие кода может быть значительно улучшено за короткое время, но в долгосрочной перспективе общее покрытие кода будет хуже, чем если словарь ключевых слов не используется. Вот вариант генератора Inputs, который использует словарь ключевых слов.
Но проблема в том, что случайное введение ключевых слов через словарь, скорее всего, разрушит исходную правильную структуру ввода Input и вызовет ненужные потери. Решение на самом деле очень простое: Fuzzing with Input Fragments.
Все вышеперечисленные операции выполняются над деревом вывода. Для более удобной операции компиляции может быть создан пул фрагментов производных деревьев, каждый фрагмент состоит из поддеревьев, а поддеревья включают в себя символы и соответствующие узлы Node и их дочерние узлы. Однако анализ дерева вывода на самом деле занимает очень много времени, поэтому вы можете установить некоторые ограничения по времени, чтобы скорость не была слишком низкой. Однако, хотя мутации на основе фрагментов могут хорошо соответствовать юридическим требованиям входных данных, они не являются выдающимися с точки зрения улучшения покрытия кода. и исходя из этого LangFuzzНа самом деле скорость генерации входов намного ниже, чем у обычного структурированного черного ящика Fuzz. Ниже приведены два набора сравнительных данных:
Можно видеть, что преимущество мутации на основе фрагментов заключается в том, что она может хорошо генерировать мутации, соответствующие структурированной грамматике. Итак, теперь вопрос заключается в том, как улучшить покрытие кода, обеспечив корректность входного синтаксиса?
Один из методов заключается в использовании руководства по покрытию, подобному AFL, с использованием покрытия кода в качестве обратной связи для изменения, чтобы постоянно добавлять семена для улучшения покрытия кода, обеспечивая при этом structural mutationsа также 32 byte-level mutations. Есть два варианта, а именно:
Разобрались с Seed и количеством мутаций, результаты теста:
В то же время, наблюдается огромное улучшение скорости генерации входов, высокий показатель покрытия кода, но худшие показатели с точки зрения легальности входов. Как же решить эту проблему? Ответ - Fuzzing with Input Regions, вариант Fuzz, который больше не использует разбиение и сборку узлов дерева деривации, а вместо этого разбивает и собирает различные области легального семени напрямую, где области - это последовательности последовательных байтов, которые могут соответствовать символам дерева деривации, что фактически имеет преимущество в том, что объекты, которыми он манипулирует, могут быть больше или меньше, чем Фрагменты могут быть больше или меньше, и тестовая структура для мутации таким образом, при тех же условиях мутации, что и выше, выглядит следующим образом.
Видно, что имеет место высокий показатель покрытия кода, хотя по скорости он лучше, чем Fragments Fuzz, но все же слабее, чем обычный черный ящик Fuzz. Однако основная причина заключается в том, что доля легальных входных данных на самом деле очень мала. Итак, как решить эту проблему? Сначала позвольте фаззеру сосредоточиться на законных входных данных. На самом деле, это обсуждалось ранее, просто используйте scheduleПридайте больший вес соответствующей структуре законных входных данных. Результаты теста следующие:
Можно видеть, что легитимность входных данных также значительно улучшилась, когда скорость покрытия кода остается высокой, но с точки зрения скорости генерации входных данных она все еще намного слабее, чем обычный GrammarFuzz.
Как видно из вышеизложенного, выбор самого Fuzz — это вопрос компромисса, только путем вторичной разработки или отбора для разных сценариев мы можем лучше достичь желаемых результатов.
Предположим, вы выполняете нечеткий тест, будь то Grammar Fuzz или другой Fuzz, если нет подходящего семени, очень сложно сформировать подходящие входные данные путем непрерывной мутации.Конечно, автор AFL показал, что с помощью простого ввода непрерывно цель Возможность эволюции, но ведь это пустая трата времени и производительности, а эффект во многих сценариях оценивается как неудовлетворительный.
Поэтому, если вы можете получить некоторые pocs или другие хорошие seed при фаззинге, например, общепринятой практикой в интерпретаторе Fuzz js является создание некоторых общедоступных pocs, как показано ниже:
Целью фазинга является выбор подходящего метода и лучшего исходного seed"а. Только путем постоянного изменения/подбора и целенаправленного развития в соответствии с целью тестирования можно получить идеальные результаты.
ПЕРЕВЕДЕНО СПЕЦИАЛЬНО ДЛЯ xss.pro
КАМНЯМИ КИДАТЬ Jolah Milovski
Входные данные для фаззинга
Одна из основных идей Fuzzing заключается в использовании большого количества входов для запуска различных ветвей логики в программе, поэтому успех Fuzzing тесно связан с генерацией входов, которые могут быть в различных форматах, таких как файлы, код, json-данные и т.д. Но все виды данных имеют свой формат, так же как и вход в программу. Для того чтобы хорошо подобрать входные данные программы, необходимо разработать некоторую синтаксическую спецификацию для входных данных. То же самое справедливо и для Fuzzing, где часто бывает полезно определить синтаксическую спецификацию для входа в программу, чтобы достичь хорошего результата Fuzzing.
Вообще говоря, регулярные выражения часто являются хорошим выбором для фаззинга простых программ, поскольку их свойства конечного автомата состояния позволяют легко рассуждать о них, чтобы получить удовлетворительный вход, но они могут быть немного сложными, если объект фаззингадостаточно сложный.
Я видел языки, разработанные для лучшего выполнения определенных функций, что, очевидно, очень полезно с точки зрения компьютерной теории, и некоторые специальные функции выполняются качественно с помощью специального языка, но это действительно слишком сложно для Fuzzing, а грамматика - это действительно нечто среднее между регулярными выражениями и специализированными языками. Она проста в понимании и делает то, что ожидается от нее. Fuzzing - генерирует большое количество входов - потому что грамматика могут определять большое количество свойств входов, идеально выражая синтаксическую структуру сложного входа.
Встречают по одежке а провожаютпо умению правильно связывать слова в предложениях
Грамматика обычно состоит из символов и набора выражений, например, A = 10 | 9 | 0 | 1. Символизация делает возможной рекурсию, и если предположить, что B = A | AB, то это, несомненно, увеличивает диапазон, предоставленный символами. Следуя этой идее, мы можем получить арифметическое выражение.
Код:
<start> ::= <expr>
<expr> ::= <term> + <expr> | <term> - <expr> | <term>
<term> ::= <term> * <factor> | <term> / <factor> | <factor>
<factor> ::= +<factor> | -<factor> | (<expr>) | <integer> | <integer>.<integer>
<integer> ::= <digit><integer> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Затем, расширяя символы внутри <start> один за другим и рандомизируя процесс, вы получаете большое количество законных арифметических выражений. Как и большинство грамматик, Грамматика должна иметь свой Тип, чтобы проверить ее легитимность, и приведенная выше Грамматика может быть определена на примере Python.
Код:
Option = Dict[str, Any]
Expansion = Union[str, Tuple[str, Option]]
Grammar = Dict[str, List[Expansion]]
EXPR_GRAMMAR: Grammar = {
"<start>":
["<expr>"],
"<expr>":
["<term> + <expr>", "<term> - <expr>", "<term>"],
"<term>":
["<factor> * <term>", "<factor> / <term>", "<factor>"],
"<factor>":
["+<factor>",
"-<factor>",
"(<expr>)",
"<integer>.<integer>",
"<integer>"],
"<integer>":
["<digit><integer>", "<digit>"],
"<digit>":
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
}Первые три строки кода определяют, как должна быть составлена грамматика в Python. Доступ к компонентам текущей грамматики и манипуляции с ними можно осуществлять с помощью EXPR_GRAMMAR["<цифра>"] в коде.
Образец грамматики FUZZ
Итак, разбираемся на примере? Один из самых простых способов — замена строк, потому что в Grammar : Левая и правая стороны сами по себе являются отношениями отображения, поэтому наиболее интуитивно понятным выбором является использование замены строк для непрерывной итерации.
Код:
START_SYMBOL = "<start>"
# обычный gramar fuzzer
def simple_grammar_fuzzer(grammar: Grammar,
start_symbol: str = START_SYMBOL,
max_nonterminals: int = 10,
max_expansion_trials: int = 100,
log: bool = False) -> str:
"""Produce a string from `grammar`.
`start_symbol`: use a start symbol other than `<start>` (default).
`max_nonterminals`: the maximum number of nonterminals
still left for expansion
`max_expansion_trials`: maximum # of attempts to produce a string
`log`: print expansion progress if True"""
term = start_symbol
expansion_trials = 0
while len(nonterminals(term)) > 0: # Определяет, присутствует ли <> в строке и возвращает все элементы, обернутые в <>, отмечая, что если это <dsad<abc>>, то возвращается <abc>.
symbol_to_expand = random.choice(nonterminals(term))
expansions = grammar[symbol_to_expand]
expansion = random.choice(expansions)
# In later chapters, we allow expansions to be tuples,
# with the expansion being the first element
if isinstance(expansion, tuple):
expansion = expansion[0]
new_term = term.replace(symbol_to_expand, expansion, 1) #Парсинг следующего символа
if len(nonterminals(new_term)) < max_nonterminals: # Количество разбираемых символов за один раз должно быть меньше, чем максимальное количество одиночных разборов
term = new_term
if log:
print("%-40s" % (symbol_to_expand + " -> " + expansion), term)
expansion_trials = 0
else:
expansion_trials += 1
if expansion_trials >= max_expansion_trials: # Существует также ограничение на общее количество резолюций
raise ExpansionError("Cannot expand " + repr(term))
return termИспользуя приведенное выше выражение, можно сделать простую грамматическую ошибку. В процессе написания Fuzz-тестов на самом деле сталкиваемся со многими компромиссами между удобством и скоростью или различной осуществимостью. Взяв приведенное выше выражение в качестве примера, мы абсолютно не хотим провала теста из-за, бесконечной рекурсии или анализ большого количества символов.Однако такой Grammar Fuzz сталкивается с рядом проблем: большое количество строковых операций поиска и замены приводит к неэффективности, и видно, что происходит сбой генерации ввода (ExpansionError), а это типичный контекстно-свободный Fuzz. Однако, в зависимости от вышеперечисленных функций, мы можем очень хорошо генерировать большое количество некоторых входных данных, пока мы пишем грамматически - правильные тесты.
Код:
URL_GRAMMAR: Grammar = {
"<start>":
["<url>"],
"<url>":
["<scheme>://<authority><path><query>"],
"<scheme>":
["http", "https", "ftp", "ftps"],
"<authority>":
["<host>", "<host>:<port>", "<userinfo>@<host>", "<userinfo>@<host>:<port>"],
"<host>": # В большинстве случаев можно указать URL
["cispa.saarland", "www.google.com", "fuzzingbook.com"],
"<port>":
["80", "8080", "<nat>"],
"<nat>":
["<digit>", "<digit><digit>"],
"<digit>":
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
"<userinfo>": # Just one
["user:password"],
"<path>": # Just a few
["", "/", "/<id>"],
"<id>": # Just a few
["abc", "def", "x<digit><digit>"],
"<query>":
["", "?<params>"],
"<params>":
["<param>", "<param>&<params>"],
"<param>": # Just a few
["<id>=<id>", "<id>=<nat>"],
}Или аналогично протоколу HTTP (но это не подготовлено для вышеупомянутого Fuzz, просто для справки):
Код:
{
"<A>": [["<START_LINE>", "\r\n", "<HEADERS>", "<BODY>", "\r\n\r\n"]],
"<START_LINE>": [["<METHOD>", " ", "<URI>", " ", "<VERSION>"]],
"<METHOD>": [["GET"], ["HEAD"], ["POST"], ["PUT"], ["DELETE"], ["CONNECT"], ["OPTIONS"], ["TRACE"], ["PATCH"], ["ACL"], ["BASELINE-CONTROL"], ["BIND"], ["CHECKIN"], ["CHECKOUT"], ["COPY"], ["LABEL"], ["LINK"], ["LOCK"], ["MERGE"], ["MKACTIVITY"], ["MKCALENDAR"], ["MKCOL"], ["MKREDIRECTREF"], ["MKWORKSPACE"], ["MOVE"], ["ORDERPATCH"], ["PRI"], ["PROPFIND"], ["PROPPATCH"], ["REBIND"], ["REPORT"], ["SEARCH"], ["UNBIND"], ["UNCHECKOUT"], ["UNLINK"], ["UNLOCK"], ["UPDATE"], ["UPDATEREDIRECTREF"], ["VERSION-CONTROL"]],
"<URI>": [["<SCHEME>" , ":", "<HIER>", "<QUERY>", "<FRAGMENT>"]],
"<SCHEME>": [["http"], ["https"], ["shttp"], ["dav"], ["about"], ["attachment"], ["cid"], ["data"], ["file"], ["ftp"], ["ssh"], ["sip"]],
"<HIER>": [["//", "<AUTHORITY>", "<PATH>"]],
"<AUTHORITY>": [["<USERINFO>", "<HOST>"]],
"<PATH>": [["/", "<DIR>"]],
"<DIR>": [[], ["<CHAR>", "/", "<DIR>"]],
"<USERINFO>": [[], ["<CHAR>", ":", "<CHAR>", "@"]],
"<HOST>": [["127.0.0.1:8080"]],
"<QUERY>": [[], ["?", "<CHAR>" , "=", "<CHAR>"]],
"<FRAGMENT>": [[], ["#", "<CHAR>"]],
"<VERSION>": [["HTTP/0.9"], ["HTTP/1.0"], ["HTTP/1.1"], ["HTTP/2.0"], ["HTTP/3.0"]],
"<HEADERS>": [[], ["<HEADER>", "\r\n", "<HEADERS>"]],
"<HEADER>": [["<HEADER_FIELD>", ": ", "<ANY>"]],
"<HEADER_FIELD>": [["A-IM"], ["Accept"], ["Accept-Charset"], ["Accept-Datetime"], ["Accept-Encoding"], ["Accept-Language"], ["Access-Control-Request-Method"], ["Access-Control-Request-Headers"], ["Authorization"], ["Cache-Control"], ["Connection"], ["Content-Encoding"], ["Content-Length"], ["Content-MD5"], ["Content-Type"], ["Cookie"], ["Date"], ["Expect"], ["Forwarded"], ["From"], ["Host"], ["HTTP2-Settings"], ["If-Match"], ["If-Modified-Since"], ["If-None-Match"], ["If-Range"], ["If-Unmodified-Since"], ["Max-Forwards"], ["Origin"], ["Pragma"], ["Proxy-Authorization"], ["Range"], ["Referer"], ["TE"], ["Trailer"], ["Transfer-Encoding"], ["User-Agent"], ["Upgrade"], ["Via"], ["Warning"]],
"<BODY>": [[], ["<CHAR>"]],
"<ANY>": [[], ["<DATE>"], ["<CHAR>"], ["<HOST>"], ["<URI>"]],
"<DATE>": [["Sat, 29 Oct 1994 19:43:31 GMT"]],
"<CHAR>": [["0"], ["1"], ["2"], ["3"], ["4"], ["5"], ["6"], ["7"], ["8"], ["9"], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"], ["m"], ["n"], ["o"], ["p"], ["q"], ["r"], ["s"], ["t"], ["u"], ["v"], ["w"], ["x"], ["y"], ["z"], ["A"], ["B"], ["C"], ["D"], ["E"], ["F"], ["G"], ["H"], ["I"], ["J"], ["K"], ["L"], ["M"], ["N"], ["O"], ["P"], ["Q"], ["R"], ["S"], ["T"], ["U"], ["V"], ["W"], ["X"], ["Y"], ["Z"]]
}На данный момент мы понимаем важность грамматики для фаззинга. Правильная грамматика может эффективно генерировать большое количество допустимых входных данных, но это только с точки зрения состава входных данных (синтаксиса). В конце концов, это огромный диапазон, хотя иногда он удовлетворяет входному формату программы, но может не работать для фаззинга, который встречается очень часто. Снова взяв компилятор в качестве примера, ваша программа должна иметь правильную семантику, удовлетворяющую синтаксису языка. Но семантику уже трудно выразить в грамматике. Взяв в качестве примера грамматику генерации URL, трудно определить диапазон портов просто с помощью грамматики. Столкнувшись с такой проблемой, самое простое решение — ограничить ее в Fuzz вместо Grammar. Взяв в качестве примера грамматику URL-адресов, прежде чем URL-адрес, сгенерированный Grammar, будет фактически передан цели в качестве входных данных, он должен оцениваться по «законности» URL-адреса в системе Fuzz. Суждение здесь может быть ограничено автором в соответствии с на собственные нужды.
Набор инструментов по грамматике
Потребность в грамматике в проекте фаззинга не статична, поэтому одно из основных требований к грамматике - быть расширяемой.
Код:
simple_nonterminal_grammar: Grammar = {
"<start>": ["<nonterminal>"],
"<nonterminal>": ["<left-angle><identifier><right-angle>"],
"<left-angle>": ["<"],
"<right-angle>": [">"],
"<identifier>": ["id"] # for now
}Иногда мы хотим расширить функциональность программы, не затрагивая исходную часть (аналог наследования в программировании), что представляет собой следующую очень простую операцию.
Код:
nonterminal_grammar = copy.deepcopy(simple_nonterminal_grammar)
nonterminal_grammar["<identifier>"] = ["<idchar>", "<identifier><idchar>"]
nonterminal_grammar["<idchar>"] = ['a', 'b', 'c', 'd'] # for nowПроще говоря - как-то так:
Код:
def set_opts(grammar: Grammar, symbol: str, expansion: Expansion,
opts: Option = {}) -> None:
"""Set the options of the given expansion of grammar[symbol] to opts"""
expansions = grammar[symbol]
for i, exp in enumerate(expansions):
if exp_string(exp) != exp_string(expansion):
continue
new_opts = exp_opts(exp)
if opts == {} or new_opts == {}:
new_opts = opts
else:
for key in opts:
new_opts[key] = opts[key]
if new_opts == {}:
grammar[symbol][i] = exp_string(exp)
else:
grammar[symbol][i] = (exp_string(exp), new_opts)
return
raise KeyError(
"no expansion " +
repr(symbol) +
" -> " +
repr(
exp_string(expansion)))В то же время, при написании Fuzz точно не хочется постоянно писать лишку, поэтому в помощь нам понадобится немного грамматики.Вот метод анализа ENBF:
Код:
# Разбор синтаксиса ebnf
def new_symbol(grammar: Grammar, symbol_name: str = "<symbol>") -> str:
"""Return a new symbol for `grammar` based on `symbol_name`"""
if symbol_name not in grammar:
return symbol_name
count = 1
while True:
tentative_symbol_name = symbol_name[:-1] + "-" + repr(count) + ">"
if tentative_symbol_name not in grammar:
return tentative_symbol_name
count += 1
# Извлекает часть выражения, соответствующую синтаксису EBNF, ? , * , + , ()
def parenthesized_expressions(expansion: Expansion) -> List[str]:
RE_PARENTHESIZED_EXPR = re.compile(r'\([^()]*\)[?+*]')
# In later chapters, we allow expansions to be tuples,
# with the expansion being the first element
if isinstance(expansion, tuple):
expansion = expansion[0]
return re.findall(RE_PARENTHESIZED_EXPR, expansion)
# Разбор синтаксических скобок EBNF в грамматике
def convert_ebnf_parentheses(ebnf_grammar: Grammar) -> Grammar:
"""Convert a grammar in extended BNF to BNF"""
grammar = extend_grammar(ebnf_grammar)
for nonterminal in ebnf_grammar:
expansions = ebnf_grammar[nonterminal]
for i in range(len(expansions)):
expansion = expansions[i]
if not isinstance(expansion, str):
expansion = expansion[0]
while True:
parenthesized_exprs = parenthesized_expressions(expansion)
if len(parenthesized_exprs) == 0:
break
for expr in parenthesized_exprs:
operator = expr[-1:]
contents = expr[1:-2]
new_sym = new_symbol(grammar)
exp = grammar[nonterminal][i]
opts = None
if isinstance(exp, tuple):
(exp, opts) = exp
assert isinstance(exp, str)
expansion = exp.replace(expr, new_sym + operator, 1)
if opts:
grammar[nonterminal][i] = (expansion, opts)
else:
grammar[nonterminal][i] = expansion
grammar[new_sym] = [contents]
return grammar
# Расширения символов ENBF
def extended_nonterminals(expansion: Expansion) -> List[str]:
RE_EXTENDED_NONTERMINAL = re.compile(r'(<[^<> ]*>[?+*])')
# In later chapters, we allow expansions to be tuples,
# with the expansion being the first element
if isinstance(expansion, tuple):
expansion = expansion[0]
return re.findall(RE_EXTENDED_NONTERMINAL, expansion)
# Расширения символов ENBF
def convert_ebnf_operators(ebnf_grammar: Grammar) -> Grammar:
"""Convert a grammar in extended BNF to BNF"""
grammar = extend_grammar(ebnf_grammar)
for nonterminal in ebnf_grammar:
expansions = ebnf_grammar[nonterminal]
for i in range(len(expansions)):
expansion = expansions[i]
extended_symbols = extended_nonterminals(expansion)
for extended_symbol in extended_symbols:
operator = extended_symbol[-1:]
original_symbol = extended_symbol[:-1]
assert original_symbol in ebnf_grammar, \
f"{original_symbol} is not defined in grammar"
new_sym = new_symbol(grammar, original_symbol)
exp = grammar[nonterminal][i]
opts = None
if isinstance(exp, tuple):
(exp, opts) = exp
assert isinstance(exp, str)
new_exp = exp.replace(extended_symbol, new_sym, 1)
if opts:
grammar[nonterminal][i] = (new_exp, opts)
else:
grammar[nonterminal][i] = new_exp
if operator == '?':
grammar[new_sym] = ["", original_symbol]
elif operator == '*':
grammar[new_sym] = ["", original_symbol + new_sym]
elif operator == '+':
grammar[new_sym] = [
original_symbol, original_symbol + new_sym]
return grammar
def convert_ebnf_grammar(ebnf_grammar: Grammar) -> Grammar:
return convert_ebnf_operators(convert_ebnf_parentheses(ebnf_grammar))Для Grammar мы должны определить его легитимность, иначе мы неизбежно столкнемся с различными ошибками в использовании, поэтому проверка синтаксиса необходима, так же как очень важна проверка синтаксиса компилятора:
Код:
# Поиск nonterminals
def def_used_nonterminals(grammar: Grammar, start_symbol:
str = START_SYMBOL) -> Tuple[Optional[Set[str]],
Optional[Set[str]]]:
"""Return a pair (`defined_nonterminals`, `used_nonterminals`) in `grammar`.
In case of error, return (`None`, `None`)."""
defined_nonterminals = set()
used_nonterminals = {start_symbol}
for defined_nonterminal in grammar:
defined_nonterminals.add(defined_nonterminal)
expansions = grammar[defined_nonterminal]
if not isinstance(expansions, list):
print(repr(defined_nonterminal) + ": expansion is not a list",
file=sys.stderr)
return None, None
if len(expansions) == 0:
print(repr(defined_nonterminal) + ": expansion list empty",
file=sys.stderr)
return None, None
for expansion in expansions:
if isinstance(expansion, tuple):
expansion = expansion[0]
if not isinstance(expansion, str):
print(repr(defined_nonterminal) + ": "
+ repr(expansion) + ": not a string",
file=sys.stderr)
return None, None
for used_nonterminal in nonterminals(expansion):
used_nonterminals.add(used_nonterminal)
return defined_nonterminals, used_nonterminals
def reachable_nonterminals(grammar: Grammar,
start_symbol: str = START_SYMBOL) -> Set[str]:
reachable = set()
def _find_reachable_nonterminals(grammar, symbol):
nonlocal reachable
reachable.add(symbol)
for expansion in grammar.get(symbol, []):
for nonterminal in nonterminals(expansion):
if nonterminal not in reachable:
_find_reachable_nonterminals(grammar, nonterminal)
_find_reachable_nonterminals(grammar, start_symbol)
return reachable
def unreachable_nonterminals(grammar: Grammar,
start_symbol=START_SYMBOL) -> Set[str]:
return grammar.keys() - reachable_nonterminals(grammar, start_symbol)
def opts_used(grammar: Grammar) -> Set[str]:
used_opts = set()
for symbol in grammar:
for expansion in grammar[symbol]:
used_opts |= set(exp_opts(expansion).keys())
return used_opts
# аналогична проверке синтаксиса в компиляторе
def is_valid_grammar(grammar: Grammar,
start_symbol: str = START_SYMBOL,
supported_opts: Set[str] = set()) -> bool:
"""Check if the given `grammar` is valid.
`start_symbol`: optional start symbol (default: `<start>`)
`supported_opts`: options supported (default: none)"""
defined_nonterminals, used_nonterminals = \
def_used_nonterminals(grammar, start_symbol)
if defined_nonterminals is None or used_nonterminals is None:
return False
# Do not complain about '<start>' being not used,
# even if start_symbol is different
if START_SYMBOL in grammar:
used_nonterminals.add(START_SYMBOL)
for unused_nonterminal in defined_nonterminals - used_nonterminals:
print(repr(unused_nonterminal) + ": defined, but not used",
file=sys.stderr)
for undefined_nonterminal in used_nonterminals - defined_nonterminals:
print(repr(undefined_nonterminal) + ": used, but not defined",
file=sys.stderr)
# Symbols must be reachable either from <start> or given start symbol
unreachable = unreachable_nonterminals(grammar, start_symbol)
msg_start_symbol = start_symbol
if START_SYMBOL in grammar:
unreachable = unreachable - \
reachable_nonterminals(grammar, START_SYMBOL)
if start_symbol != START_SYMBOL:
msg_start_symbol += " or " + START_SYMBOL
for unreachable_nonterminal in unreachable:
print(repr(unreachable_nonterminal) + ": unreachable from " + msg_start_symbol,
file=sys.stderr)
used_but_not_supported_opts = set()
if len(supported_opts) > 0:
used_but_not_supported_opts = opts_used(
grammar).difference(supported_opts)
for opt in used_but_not_supported_opts:
print(
"warning: option " +
repr(opt) +
" is not supported",
file=sys.stderr)
return used_nonterminals == defined_nonterminals and len(unreachable) == 0Инструменты, перечисленные выше, являются широко используемыми инструментами.В процессе написания Fuzz должны быть написаны различные инструменты в соответствии с актуальными проблемами.
Эффективная грамматика Fuzz
Приведенный выше simple_grammar_fuzzer на самом деле имеет много проблем, таких как низкая производительность, ограниченное количество парсинга символов, легкость возникновения ошибок и т. д. Поэтому требуется более сложный алгоритм. Дерево вывода было выбрано здесь, потому что древовидную структуру легко проследить, а ветви можно легко добавлять и удалять. Написание Fuzz на самом деле является непрерывным анализом дерева вывода и непрерывным расширением дочерних узлов.
алгоритм дерева вывода
Из приведенного выше простого алгоритма видно, что ядром всего Grammar Fuzz является формирование соответствующей структуры данных с помощью большого количества расширений символов, поэтому структура данных, используемая для хранения или расширения символов, на самом деле особенно важна. Древовидная структура дерева вывода действительно полностью отвечает нашим требованиям, а расширение древовидной структуры сверху вниз соответствует расширению символов, а также производные деревья позволяют нам контролировать состояние всего процесса расширения, например те узлы, которые были расширены, или требуется ли расширение узла и т. д. При этом скорость добавления новых узлов в процессе расширения намного выше, чем процесс замены символа значением, поэтому использование этой структуры данных также дает некоторый прирост производительности.
В качестве примера:
Код:
# URL Grammar
URL_GRAMMAR: Grammar = {
"<start>":
["<url>"],
"<url>":
["<scheme>://<authority><path><query>"],
"<scheme>":
["http", "https", "ftp", "ftps"],
"<authority>":
["<host>", "<host>:<port>", "<userinfo>@<host>", "<userinfo>@<host>:<port>"],
"<host>": # В большинстве случаев вы можете указать URL
["cispa.saarland", "www.google.com", "fuzzingbook.com"],
"<port>":
["80", "8080", "<nat>"],
"<nat>":
["<digit>", "<digit><digit>"],
"<digit>":
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
"<userinfo>": # Just one
["user:password"],
"<path>": # Just a few
["", "/", "/<id>"],
"<id>": # Just a few
["abc", "def", "x<digit><digit>"],
"<query>":
["", "?<params>"],
"<params>":
["<param>", "<param>&<params>"],
"<param>": # Just a few
["<id>=<id>", "<id>=<nat>"],
}С точки зрения алгоритма дерева вывода, сначала <start> является начальным узлом, а затем находит соответствующее ему выражение, поэтому он выберет <url> в качестве дочернего узла цикл повторяется до тех пор, пока у узла больше не будет соответствующего дочернего узла, а затем анализируется вся древовидная структура и выводятся соответствующие структурированные данные.
Соответствующие данные представлены следующим образом:
Код:
SYMBOL_NAME, CHILDREN)
DerivationTree = Tuple[str, Optional[List[Any]]]
derivation_tree: DerivationTree = ("<start>",
[("<expr>",
[("<expr>", None),
(" + ", []),
("<term>", None)]
)])SYMBOL_NAME представляет символ, CHILDREN представляет дочерний узел, а конкретная структура данных: DerivationTree = Tuple[str, Optional[List[Any]]]. Наследование тут представлено двумя моментами:
- None означает, что текущий узел может продолжать расширяться вниз, что означает, что узел теперь имеет расширяемый символ.
- [] означает, что нет дочернего узла
Код:
def g_rammar_fuzzer():
f = GrammarFuzzer(URL_GRAMMAR)
f.fuzz()ProbabilisticGrammarFuzzer
Иногда полностью случайное расширение выражений на самом деле будет тратить много времени и ресурсов, поэтому вы можете добавлять значения вероятности к выражениям. Это связано с множеством проблем вероятности, и некоторые данные исходят из статистических законов, таких как после данного leaddigit вероятность, соответствующая символу, в углубленном анализе отсутствует.
Код:
PROBABILISTIC_EXPR_GRAMMAR: Grammar = {
"<start>":
["<expr>"],
"<expr>":
[("<term> + <expr>", opts(prob=0.1)),
("<term> - <expr>", opts(prob=0.2)),
"<term>"],
"<term>":
[("<factor> * <term>", opts(prob=0.1)),
("<factor> / <term>", opts(prob=0.1)),
"<factor>"
],
"<factor>":
["+<factor>", "-<factor>", "(<expr>)",
"<leadinteger>", "<leadinteger>.<integer>"],
"<leadinteger>":
["<leaddigit><integer>", "<leaddigit>"],
# Benford's law: frequency distribution of leading digits
"<leaddigit>":
[("1", opts(prob=0.301)),
("2", opts(prob=0.176)),
("3", opts(prob=0.125)),
("4", opts(prob=0.097)),
("5", opts(prob=0.079)),
("6", opts(prob=0.067)),
("7", opts(prob=0.058)),
("8", opts(prob=0.051)),
("9", opts(prob=0.046)),
],
# Remaining digits are equally distributed
"<integer>":
["<digit><integer>", "<digit>"],
"<digit>":
["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"],
}Большое отличие от предыдущей Грамматики заключается в том, что текущая Грамматика может добавлять к значениям в списке случайные вероятности, добавляя аннотации, чтобы автор мог получать информацию из других каналов через реверс и ее можно было использовать в Fuzz. Теперь вопрос очевиден, как определить вероятность? Когда автор Fuzz не может прямо указать конкретную вероятность всех элементов, соответствующих символу, наиболее прямыми правилами, которым можно следовать, являются следующие три формулы:
Общий смысл также хорошо понятен, то есть а представляет элемент с известной вероятностью, а элемент с неизвестной вероятностью, представленный u, с известной вероятностью может быть естественно пропущен через opts метод добавляет вероятность к соответствующему элементу, а элементу с неизвестной вероятностью присваивается вероятность в соответствии с принципом выравнивания вероятностей. После этого естественно ввести вероятность в Fuzz, чтобы при генерации начальных значений можно было придавать веса выбору анализа символов, тем самым повышая эффективность Fuzz.
Что касается конкретной реализации Fuzz, на самом деле, по сравнению с вышеупомянутой Grammar Fuzz, она только добавляет доступ к аннотации opts, так что вес значения вероятности может быть добавлен во время случайного анализа. Но преимущества, которые дает это, очевидны, и вы даже можете управлять Func, заданной входной целью Fuzz и т. д. Но есть и другая ситуация: когда я разбираю грамматический символ в первый раз, я надеюсь, что его вероятность равна 0,3, а когда я разбираю грамматический символ во второй раз, я надеюсь, что его вероятность равна 0,5. на самом деле может использовать контекст в разных символах копии контекста, которым вы хотите назначить разные вероятности, в качестве примера возьмем IP_ADDRESS_GRAMMAR:
Код:
IP_ADDRESS_GRAMMAR: Grammar = {
"<start>": ["<address>"],
"<address>": ["<octet>.<octet>.<octet>.<octet>"],
# ["0", "1", "2", ..., "255"]
"<octet>": decrange(0, 256) # 其实代表的就是0-256
}Для того, чтобы сделать каждый разбор <octet>При использовании разных вероятностей его можно расширить, чтобы сформировать следующий синтаксис:
IP_ADDRESS_GRAMMAR: Grammar = {
"<start>": ["<address>"],
"<address>": ["<octet-1>.<octet-2>.<octet-3>.<octet-4>"],
# ["0", "1", "2", ..., "255"]
"<octet-1>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-2>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-3>": decrange(0, 256) # Вообще-то он обозначает 0-256
"<octet-4>": decrange(0, 256) #ну вы поняли что он там обозначает))
}
Таким образом, когда выполняется синтаксический анализ, к каждому синтаксическому анализу может быть привязана разная вероятность. Вот функции, которые помогут с реализацией:
Код:
def _duplicate_context(grammar: Grammar,
orig_grammar: Grammar,
symbol: str,
expansion: Optional[Expansion],
depth: Union[float, int],
seen: Dict[str, str]) -> None:
"""Helper function for `duplicate_context()`"""
for i in range(len(grammar[symbol])):
if expansion is None or grammar[symbol][i] == expansion:
new_expansion = ""
for (s, c) in expansion_to_children(grammar[symbol][i]):
if s in seen: # Duplicated already
new_expansion += seen[s]
elif c == [] or depth == 0: # Terminal symbol or end of recursion
new_expansion += s
else: # Nonterminal symbol - duplicate
# Add new symbol with copy of rule
new_s = new_symbol(grammar, s)
grammar[new_s] = copy.deepcopy(orig_grammar[s])
# Duplicate its expansions recursively
# {**seen, **{s: new_s}} is seen + {s: new_s}
_duplicate_context(grammar, orig_grammar, new_s, expansion=None,
depth=depth - 1, seen={**seen, **{s: new_s}})
new_expansion += new_s
grammar[symbol][i] = new_expansion
def duplicate_context(grammar: Grammar,
symbol: str,
expansion: Optional[Expansion] = None,
depth: Union[float, int] = float('inf')):
"""Duplicate an expansion within a grammar.
In the given grammar, take the given expansion of the given `symbol`
(if `expansion` is omitted: all symbols), and replace it with a
new expansion referring to a duplicate of all originally referenced rules.
If `depth` is given, limit duplication to `depth` references
(default: unlimited)
"""
orig_grammar = extend_grammar(grammar)
_duplicate_context(grammar, orig_grammar, symbol,
expansion, depth, seen={})
# After duplication, we may have unreachable rules; delete them
for nonterminal in unreachable_nonterminals(grammar):
del grammar[nonterminal]После копирования контекста мы можем получить желаемый результат, выполнив что-то вроде следующего:
Код:
set_prob(probabilistic_ip_address_grammar, "<octet-1>", "127", 1.0)
set_prob(probabilistic_ip_address_grammar, "<octet-2>", "0", 1.0)Однако возникает другой вопрос: действительно ли уместно, чтобы вероятность оставалась неизменной после того, как она была присвоена символу? В реальном фаззе, с нашим непрерывным пониманием цели, или некоторых других ситуациях, например, когда желаемый результат не появляется в течение длительного времени, также необходимо вовремя менять стратегию, но если фазз может разумно подстраиваться настройка различных символов сама по себе. Если используется значение вероятности, это значительно уменьшит нагрузку и даст лучшие результаты тестирования программного обеспечения. Лучший способ — позволить Fuzz узнать, насколько большое значение вероятности должно быть присвоено определенным символам, изначально задав их входными данными.Этот метод очень полезен в определенных сценариях:
- Тестируйте часто используемые функции, потому что многие тесты программного обеспечения предпочитают часто используемые функции для обеспечения безопасности, но это может не быть целью исследователей интеллектуального анализа уязвимостей.
- Чтобы протестировать необычные функции, обойдя символы, проанализированные во входных данных, Fuzz будет более склонен тестировать некоторые необычные функции.
- Сосредоточьтесь на указанных входных данных, некоторые исследования уязвимостей могут захотеть сосредоточиться на существующих очень ценных входных данных poc. Сосредоточившись на этих входных данных, Fuzz может протестировать некоторые слабые звенья программного обеспечения для достижения хороших результатов.
Теория уже существует, так как же ее реализовать? Первым шагом должно быть восстановление существующих входных начальных значений в дерево вывода, а затем вычисление будущего значения вероятности соответствующего значения каждого символа вида дерева вывода.
Как и выше, предположим, я задаю seed 127.0.0.1, тогда после разбора значение вероятности 0 в <octet> будет ограничено 50% и 25% для 127 и 1 соответственно, затем соответствующие значения вероятности могут быть присвоены <octet> при выполнении Fuzz. Что же произойдет, если вы протестируете некоторые менее распространенные функции? Фактически, вероятности получаются из исходных входов часто используемых функций, а затем переворачиваются, например, вероятности часто используемых входов выглядят следующим образом.
Код:
[('http', {'prob': 0.2222222222222222}),
('https', {'prob': 0.6666666666666666}),
('ftp', {'prob': 0.0}),
('ftps', {'prob': 0.1111111111111111})]Тогда после перелистывания это:
Код:
[('http', {'prob': 0.1111111111111111}),
('https', {'prob': 0.0}),
('ftp', {'prob': 0.6666666666666666}),
('ftps', {'prob': 0.2222222222222222})]Вышеизложенное является основной идеей сосредоточения внимания на тестировании общих функций или очень полезных функций, упомянутых ранее. Еще один ключевой момент здесь - помочь нам сосредоточиться на конкретных функциях цели через входы. Разница между этим и тестированием общих функций заключается в что мы должны сначала найти пакет специальных входных данных, которые можно использовать в качестве начальных значений для выполнения вероятностного анализа и ограничений на процесс синтаксического анализа, чтобы последующие мутации всегда могли иметь более высокую целевую частоту попаданий.
Генератор с функцией Pre или Post или Order Func
Когда некоторые входы сгенерированы, автор Fuzz может захотеть настроить некоторые ограничения на них и получить другие операции, доступ к которым можно получить через pre funcЗаканчивать. Это похоже на хук, поэтому время срабатывания func обычно делится на два типа.До или после генерации входных данных выражение в грамматике выглядит следующим образом:
Код:
CHARGE_GRAMMAR: Grammar = {
"<start>": ["Charge <amount> to my credit card <credit-card-number>"],
"<amount>": ["$<float>"],
"<float>": ["<integer>.<digit><digit>"],
"<integer>": ["<digit>", "<integer><digit>"],
"<digit>": crange('0', '9'),
"<credit-card-number>": ["<digits>"],
"<digits>": ["<digit-block><digit-block><digit-block><digit-block>"],
"<digit-block>": ["<digit><digit><digit><digit>"],
}
CHARGE_GRAMMAR.update({
"<float>": [("<integer>.<digit><digit>", opts(pre=high_charge))], # high_charge是函数名称
})
CHARGE_GRAMMAR.update({
"<float>": [("<integer>.<digit><digit>",
opts(pre=lambda: random.randint(10000000, 90000000) / 100.0))] # 或者选择使用lambda表达式
})Другой после генерации Seed:
Код:
CHARGE_GRAMMAR.update({
"<credit-card-number>": [("<digits>", opts(post=lambda digits: fix_credit_card(digits)))]
})Например, если сгенерированные цифры не соответствуют потребностям Fuzz, мы можем использовать это для своевременного внесения исправлений, чтобы повысить эффективность Fuzz.
Greybox Fuzzing с использованием грамматики
В дополнение к проблемам производительности Fuzzing, еще одной проблемой является проблема вариационного руководства. Хотя внутренний разбор грамматики является случайным во время генерации входов Grammars Fuzz, большое количество входов может вызвать одну и ту же ветвь для цели Fuzz, что затрудняет достижение желаемого значения покрытия кода. Для AFL-подобного покрытия bootstrap Fuzz, можно подсчитать покрытие кода для хорошего bootstrap из-за заглушек исходного кода white-box Fuzz, но есть много случаев, таких как black-box или даже WebServer-targeted Fuzz, где подсчет покрытия кода не является простой задачей, и мера, которую необходимо принять, заключается в постоянном увеличении покрытия кода. разнообразие при генерации входных данных, например, путем подсчета процесса расширения дочерних узлов в вышеупомянутом дереве деривации таким образом, чтобы он был смещен в сторону узлов, которые еще не были расширены при генерации входного корпуса. Здесь возникает новая проблема: как быстро улучшить покрытие кода?
При выполнении Fuzz некоторые части входного корпуса иногда идентифицируются как ключевые слова, например, int в C. Если Fuzz сказать использовать эти ключевые слова, покрытие кода может быть значительно улучшено за короткое время, но в долгосрочной перспективе общее покрытие кода будет хуже, чем если словарь ключевых слов не используется. Вот вариант генератора Inputs, который использует словарь ключевых слов.
Код:
class DictMutator(Mutator):
"""Mutate strings using keywords from a dictionary"""
def __init__(self, dictionary: List[str]) -> None:
"""Constructor. `dictionary` is the list of keywords to use."""
super().__init__()
self.dictionary = dictionary
self.mutators.append(self.insert_from_dictionary)
def insert_from_dictionary(self, s: str) -> str:
"""Returns s with a keyword from the dictionary inserted"""
pos = random.randint(0, len(s))
random_keyword = random.choice(self.dictionary)
return s[:pos] + random_keyword + s[pos:]Но проблема в том, что случайное введение ключевых слов через словарь, скорее всего, разрушит исходную правильную структуру ввода Input и вызовет ненужные потери. Решение на самом деле очень простое: Fuzzing with Input Fragments.
- Проанализируйте исходный ввод, чтобы сформировать дерево вывода.
- Выполнение таких операций, как замена узла или замена узла в дереве вывода.
- Восстановите дерево вывода, чтобы сформировать новый вход.
Все вышеперечисленные операции выполняются над деревом вывода. Для более удобной операции компиляции может быть создан пул фрагментов производных деревьев, каждый фрагмент состоит из поддеревьев, а поддеревья включают в себя символы и соответствующие узлы Node и их дочерние узлы. Однако анализ дерева вывода на самом деле занимает очень много времени, поэтому вы можете установить некоторые ограничения по времени, чтобы скорость не была слишком низкой. Однако, хотя мутации на основе фрагментов могут хорошо соответствовать юридическим требованиям входных данных, они не являются выдающимися с точки зрения улучшения покрытия кода. и исходя из этого LangFuzzНа самом деле скорость генерации входов намного ниже, чем у обычного структурированного черного ящика Fuzz. Ниже приведены два набора сравнительных данных:
Код:
LangFuzz
From the 300 generated inputs, 152 (50.67%) can be parsed.In total, 91 statements are covered.
BlackFuzz
From the 300 generated inputs, 36 (12.00%) can be parsed.In total, 161 statements are covered.Можно видеть, что преимущество мутации на основе фрагментов заключается в том, что она может хорошо генерировать мутации, соответствующие структурированной грамматике. Итак, теперь вопрос заключается в том, как улучшить покрытие кода, обеспечив корректность входного синтаксиса?
Один из методов заключается в использовании руководства по покрытию, подобному AFL, с использованием покрытия кода в качестве обратной связи для изменения, чтобы постоянно добавлять семена для улучшения покрытия кода, обеспечивая при этом structural mutationsа также 32 byte-level mutations. Есть два варианта, а именно:
Код:
class GreyboxGrammarFuzzer(GreyboxFuzzer):
"""Greybox fuzzer using grammars."""
def __init__(self, seeds: List[str],
byte_mutator: Mutator, tree_mutator: FragmentMutator,
schedule: PowerSchedule) -> None:
"""Constructor.
`seeds` - set of inputs to mutate.
`byte_mutator` - a byte-level mutator.
`tree_mutator` = a tree-level mutator.
`schedule` - a power schedule.
"""
super().__init__(seeds, byte_mutator, schedule)
self.tree_mutator = tree_mutator
def create_candidate(self) -> str:
"""Returns an input generated by structural mutation
of a seed in the population"""
seed = cast(SeedWithStructure, self.schedule.choose(self.population))
# Structural mutation
trials = random.randint(0, 4)
for i in range(trials):
seed = self.tree_mutator.mutate(seed)
# Byte-level mutation
candidate = seed.data
if trials == 0 or not seed.has_structure or random.randint(0, 1) == 1:
dumb_trials = min(len(seed.data), 1 << random.randint(1, 5))
for i in range(dumb_trials):
candidate = self.mutator.mutate(candidate)
return candidateРазобрались с Seed и количеством мутаций, результаты теста:
Код:
From the 300 generated inputs, 1 (0.33%) can be parsed.
In total, 180 statements are covered.В то же время, наблюдается огромное улучшение скорости генерации входов, высокий показатель покрытия кода, но худшие показатели с точки зрения легальности входов. Как же решить эту проблему? Ответ - Fuzzing with Input Regions, вариант Fuzz, который больше не использует разбиение и сборку узлов дерева деривации, а вместо этого разбивает и собирает различные области легального семени напрямую, где области - это последовательности последовательных байтов, которые могут соответствовать символам дерева деривации, что фактически имеет преимущество в том, что объекты, которыми он манипулирует, могут быть больше или меньше, чем Фрагменты могут быть больше или меньше, и тестовая структура для мутации таким образом, при тех же условиях мутации, что и выше, выглядит следующим образом.
Код:
It took the structural greybox fuzzer with region mutator
11.35 seconds to generate and execute 300 inputs.
From the 300 generated inputs, 4 (1.33%) can be parsed.
In total, 168 statements are covered.
On average, 9.1% of a seed in the population can be successfully parsed.Видно, что имеет место высокий показатель покрытия кода, хотя по скорости он лучше, чем Fragments Fuzz, но все же слабее, чем обычный черный ящик Fuzz. Однако основная причина заключается в том, что доля легальных входных данных на самом деле очень мала. Итак, как решить эту проблему? Сначала позвольте фаззеру сосредоточиться на законных входных данных. На самом деле, это обсуждалось ранее, просто используйте scheduleПридайте больший вес соответствующей структуре законных входных данных. Результаты теста следующие:
Код:
It took AFLSmart 20.75 seconds to generate and execute 300 inputs.
From the 300 generated inputs, 46 (15.33%) can be parsed.
In total, 162 statements are covered.
On average, 23.7% of a seed in the population can be successfully parsed.Можно видеть, что легитимность входных данных также значительно улучшилась, когда скорость покрытия кода остается высокой, но с точки зрения скорости генерации входных данных она все еще намного слабее, чем обычный GrammarFuzz.
Как видно из вышеизложенного, выбор самого Fuzz — это вопрос компромисса, только путем вторичной разработки или отбора для разных сценариев мы можем лучше достичь желаемых результатов.
Вход парсера
Предположим, вы выполняете нечеткий тест, будь то Grammar Fuzz или другой Fuzz, если нет подходящего семени, очень сложно сформировать подходящие входные данные путем непрерывной мутации.Конечно, автор AFL показал, что с помощью простого ввода непрерывно цель Возможность эволюции, но ведь это пустая трата времени и производительности, а эффект во многих сценариях оценивается как неудовлетворительный.
Поэтому, если вы можете получить некоторые pocs или другие хорошие seed при фаззинге, например, общепринятой практикой в интерпретаторе Fuzz js является создание некоторых общедоступных pocs, как показано ниже:
Код:
var haystack = "foo";
var re_text = "^foo";
haystack += "x";
re_text += "(x)";
var re = new RegExp(re_text);
re.test(haystack);
RegExp.input = Number();
print(RegExp.$1);Подведем итог
Целью фазинга является выбор подходящего метода и лучшего исходного seed"а. Только путем постоянного изменения/подбора и целенаправленного развития в соответствии с целью тестирования можно получить идеальные результаты.