Размытие

Фаззинг или фазз-тестирование-это автоматизированный метод тестирования программного обеспечения, который включает в себя предоставление неверных, неожиданных или случайных данных в качестве входных данных для компьютерной программы. Затем программа отслеживается на наличие исключений , таких как сбои, сбои встроенных утверждений кодаили потенциальные утечки памяти. Как правило, фаззеры используются для тестирования программ, которые принимают структурированные входные данные. Эта структура задается, например, в формате файла или протокола и отличает допустимый ввод от недопустимого. Эффективный фаззер генерирует полу-валидные входные данные, которые "достаточно валидны" в том смысле, что они непосредственно не отклоняются синтаксическим анализатором, но создают неожиданное поведение глубже в программе и "достаточно недействительны", чтобы выставить угловые случаи, которые не были должным образом обработаны.

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

История

Термин "fuzz" происходит от осеннего проекта 1988года в классе продвинутых операционных систем graduate Advanced Operating Systems class (CS736), преподаваемого проф. Бартон Миллер в Университете Висконсина, результаты которого были впоследствии опубликованы в 1990 году. утилита предназначена для автоматической генерации случайных файлов и параметров командной строки для этой утилиты. Проект был разработан для проверки надежности программ командной строки UNIX путем выполнения большого количества случайных входов в быстрой последовательности, пока они не разбились. Команда Миллера смогла вывести из строя от 25 до 33 процентов протестированных ими утилит. Затем они отладили каждый из сбоев, чтобы определить причину, и классифицировали каждый обнаруженный сбой. Чтобы другие исследователи могли проводить подобные эксперименты с другим программным обеспечением, исходный код инструментов, процедуры тестирования и исходные данные результатов были доступны общественности. Это раннее фаззирование теперь будет называться черным ящиком, поколенческим, неструктурированным (немым) фаззингом.

В статье fuzz 1990 года также отмечалась связь надежности с безопасностью: "Во-вторых, одна из обнаруженных нами ошибок была вызвана той же практикой программирования, которая обеспечила интернет-червю одну из дыр в безопасности (ошибка "gets finger"). Мы нашли дополнительные ошибки, которые могут указывать на будущие дыры в безопасности." (Имея в виду червя Морриса в ноябре 1988 года.)

Первоначальный проект fuzz продолжал вносить взносы в 1995, 2000, 2006 и совсем недавно в 2020 году:

• 1995:[5] Статья "fuzz revisited" состояла из четырех частей. (1) Воспроизвел оригинальное исследование командной строки, включая более широкий спектр систем UNIX и больше утилит. Исследование показало, что, во всяком случае, надежность стала хуже. Это было первое исследование, которое включало открытый исходный код GNU и Linux утилиты, которые, что интересно, были значительно более надежными, чем утилиты из коммерческих UNIX-систем.

(2) Ввел fuzz-тестирование графических (оконных) приложений под X-Windows. В этом исследовании использовались как неструктурированные, так и структурированные (допустимые последовательности событий мыши и клавиатуры) входные данные. Они смогли вывести из строя 25% приложений X-Windows. Кроме того, они протестировали сервер X-Windows и показали, что он устойчив к сбоям.

(3) Введено нечеткое тестирование сетевых сервисов, опять же основанное на структурированном тестовом вводе. Ни одна из этих служб не потерпела краха.

(4) Введено случайное тестирование возвращаемых значений вызовов системных библиотек, в частности случайное возвращение нуля из семейства функций malloc. Почти половина стандартных UNIX-программ не смогла должным образом проверить такие возвращаемые значения.

• 2000: Применил fuzz-тестирование к недавно выпущенной операционной системе Windows NT, тестируя приложения, работающие под управлением оконной системы Win32. Они смогли разбить 21% приложений и повесить еще 24% тестируемых. Опять же, приложения тестировались как с неструктурированным, так и со структурированным вводом (допустимые события клавиатуры и мыши), что привело к сбою почти половины тестируемых приложений. Они определили причины неудач и обнаружили, что они похожи на предыдущие исследования.
• 2006: Применил fuzz-тестирование к Mac OS X, как для приложений командной строки, так и для оконных приложений. Они протестировали 135 утилит командной строки, разбив 7% из них. Кроме того, они протестировали 30 приложений, которые работали под управлением macOS Aqua window system, разбив 73% из них.
• 2020:[8] Совсем недавно они применили классическое поколение, черный ящик, неструктурированное тестирование к текущим системам UNIX, особенно Linux, FreeBSD и macOS, чтобы увидеть, были ли оригинальные методы все еще актуальны и были ли текущие утилиты устойчивы к этому типу тестирования. Они протестировали около 75 утилит на каждой платформе, с частотой отказов 12% на Linux, 16% на macOS и 19% на FreeBSD. (Обратите внимание, что эти показатели отказов были хуже чем результаты более ранних испытаний тех же систем.) Когда они проанализировали каждый отказ и классифицировали их, они обнаружили, что классические категории отказов, такие как ошибки указателей и массивов и отсутствие проверки кодов возврата, все еще широко присутствовали в новых результатах. Кроме того, новые причины сбоев возникали из-за сложного состояния программы и алгоритмов, которые не масштабировались вместе с размером или сложностью входных данных. Они также протестировали утилиты UNIX, написанные совсем недавно на Rust, и обнаружили, что они обладают такой же надежностью, как и те, что написаны на C, хотя (как и ожидалось) с меньшей вероятностью имеют ошибки памяти.

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

В сентябре 2014 года, контузия был раскрыт, а семье от ошибок в широко использоваться в Unix Баш оболочки; наиболее уязвимые места контузия были найдены с помощью fuzzer АФТ. (много интернет-служб, таких как веб-сервер развертывания, использовать Bash для обработки определенных запросов, позволяющая злоумышленнику вызвать уязвимые версии Bash для запуска произвольных команд. Это может позволить злоумышленнику получить несанкционированный доступ к компьютерной системе.)

В апреле 2015 года Ханно Бек показал, как fuzzer AFL мог найти уязвимость Heartbleed 2014 года. (Уязвимость Heartbleed была раскрыта в апреле 2014 года. Это серьезная уязвимость, которая позволяет противникам расшифровывать зашифрованные сообщения. Уязвимость была случайно введена в OpenSSL, который реализует TLS и используется большинством серверов в Интернете. Шодан сообщил, что 238 000 машин все еще уязвимы в апреле 2016 года; 200 000 в январе 2017 года.)

В августе 2016 года Агентство перспективных оборонных исследовательских проектов (DARPA) провело финал первого Кибер-гранда-полностью автоматизированного конкурса по захвату флага , который длился 11 часов. Цель состояла в том, чтобы разработать автоматические системы защиты , которые могут обнаруживать, эксплуатироватьи исправлять недостатки программного обеспечения в режиме реального времени. Фаззинг использовался как эффективная стратегия нападения, чтобы обнаружить недостатки в программном обеспечении противников. Он показал огромный потенциал в автоматизации обнаружения уязвимостей. Победителем стала система под названием "Mayhem", разработанная командой ForAllSecure во главе с Дэвидом Брамли.

В сентябре 2016 года Microsoft анонсировала Project Springfield, облачную службу тестирования fuzz для поиска критических ошибок безопасности в программном обеспечении.

В декабре 2016 года Google анонсировала OSS-Fuzz, который позволяет непрерывно размывать несколько критически важных для безопасности проектов с открытым исходным кодом.

На выставке Black Hat 2018 Кристофер Домас продемонстрировал использование фаззинга для выявления существования скрытого RISC-ядра в процессоре.[21] Это ядро смогло обойти существующие проверки безопасности для выполнения команд Ring 0 из Ring 3.

В сентябре 2020 года Microsoft выпустила OneFuzz, автономную платформу fuzzing-as-a-service, которая автоматизирует обнаружение программных ошибок.]

Раннее случайное тестирование

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

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

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

В 1983 году Стив Кэппс из Apple разработал "Обезьяну", инструмент, который будет генерировать случайные входы для классических приложений Mac OS, таких как MacPaint. Образная "обезьяна" относится к теореме о бесконечной обезьяне, которая утверждает, что обезьяна, случайно нажимая клавиши на клавиатуре пишущей машинки в течение бесконечного времени, в конечном итоге напечатает все произведения Шекспира. В случае тестирования обезьяна записывала определенную последовательность входов, которая должна была вызвать сбой.

В 1991 году был выпущен инструмент crashme, который предназначался для проверки надежности Unix и Unix-подобных операционных систем путем случайного выполнения системных вызовов со случайно выбранными параметрами.]

Типы

Фаззер можно классифицировать несколькими способами:[30][1]

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

Повторное использование существующих входных семян

Основанный на мутации фаззер использует существующий корпус исходных данных во время фаззинга. Он генерирует входные данные, модифицируя (или, скорее, мутируя) предоставленные семена.[31] Например, при фаззинге библиотеки изображений libpngпользователь должен предоставить набор допустимых PNG-файлов. файлы изображений в виде семян, в то время как мутационный фаззер модифицировал бы эти семена, чтобы получить полувалидные варианты каждого семени. Корпус исходных файлов может содержать тысячи потенциально похожих входных данных. Автоматизированный отбор семян (или сокращение набора тестов) позволяет пользователям выбирать лучшие семена, чтобы максимизировать общее количество ошибок, обнаруженных во время кампании fuzz.

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

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

Осведомленность о структуре входных

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

Интеллектуальный (основанный на модели,[34] грамматике,[33][35] или протоколе[36]) фаззер использует входную модель для генерации большей доли допустимых входных данных. Например, если входные данные можно смоделировать в виде абстрактного синтаксического дерева, то интеллектуальный фаззер на основе мутаций[35] будет использовать случайные преобразования для перемещения полных поддеревьев из одного узла в другой. Если входные данные могут быть смоделированы формальной грамматикой, то интеллектуальный фаззер на основе генерации[33] будет создавать экземпляры производственных правил для генерации входных данных, которые являются допустимыми по отношению к грамматике. Однако, как правило, входная модель должна быть явно предоставлена, что трудно сделать, когда модель является частной, неизвестной или очень сложной. Если имеется большой корпус допустимых и недопустимых входных данных, то метод грамматической индукции, такой как алгоритм Angluin's L*, сможет генерировать входную модель.]

Тупой фаззер не требует входной модели и, таким образом, может быть использован для фаззирования более широкого спектра программ. Например, AFL-это тупой мутационный фаззер , который изменяет начальный файл, переворачивая случайные биты, заменяя случайные байты "интересными" значениями и перемещая или удаляя блоки данных. Однако тупой фаззер может генерировать меньшую долю допустимых входных данных и подчеркивать код парсера, а не основные компоненты программы. Недостаток тупых фаззеров можно проиллюстрировать построением допустимой контрольной суммы для циклической проверки избыточности (CRC). CRC-это код обнаружения ошибок, который обеспечивает сохранение целостности данных, содержащихся во входном файле, во время передачи Контрольная сумма вычисляется по входным данным и записывается в файл. Если программа обрабатывает полученный файл и записанная контрольная сумма не совпадает с пересчитанной контрольной суммой, то файл отклоняется как недопустимый. Теперь фаззер, который не знает о CRC, вряд ли сгенерирует правильную контрольную сумму. Тем не менее, есть попытки идентифицировать и повторно вычислить потенциальную контрольную сумму в мутированных входных данных, как только тупой мутационный фаззер изменил защищенные данные.]

Осведомленность о структуре программы

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

Фаззер черного ящика рассматривает программу как черный ящик и не знает о внутренней структуре программы. Например, случайное тестирование инструмент, который генерирует входы случайным образом, считается blackbox fuzzer. Таким образом, blackbox fuzzer может выполнять несколько сотен входов в секунду, может легко распараллеливаться и масштабироваться до программ произвольного размера. Тем не менее, blackbox fuzzers может только поцарапать поверхность и выявить "неглубокие" ошибки. Следовательно, есть попытки разработать блэкбокс-фуззеры, которые могут постепенно узнавать о внутренней структуре (и поведении) программы во время фуззинга, наблюдая выход программы при заданном входе. Например, LearnLib использует активное обучение для создания автомата это представляет собой поведение веб-приложения.

Фаззер белого ящика использует анализ программ для систематического увеличения охвата кода или достижения определенных критических мест программы. Например, SAGE использует символическое выполнение для систематического изучения различных путей в программе. Если спецификация программы доступна, то фуззер whitebox может использовать методы тестирования на основе моделей для генерации входных данных и проверки выходных данных программы в соответствии со спецификацией программы. Фуззер whitebox может быть очень эффективным для выявления ошибок, которые скрываются глубоко в программе. Однако время, затрачиваемое на анализ (программы или ее спецификации), может стать непомерно большим. Если фуззер whitebox занимает относительно слишком много времени для генерации входных данных, то фуззер blackbox будет более эффективным. Таким образом, предпринимаются попытки объединить эффективность фуззеров blackbox и эффективность фуззеров whitebox.

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

Использование

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

Разоблачение ошибок

Чтобы выявить ошибки, fuzzer должен уметь отличать ожидаемое (нормальное) от неожиданного (багги) поведения программы. Однако машина не всегда может отличить ошибку от признака. В автоматизированном тестировании программногообеспечения это также называется проблемой тестового оракула

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

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

• для обнаружения ошибок, связанных с памятью, таких как переполнение буфера и use-after-free (с помощью отладчиков памяти, таких как AddressSanitizer),
• для обнаружения условий гонки и тупиков (ThreadSanitizer),
• для обнаружения неопределенного поведения (UndefinedBehaviorSanitizer),
• для обнаружения утечек памяти (LeakSanitizer), или
• для проверки целостности потока управления (CFISanitizer).

Фаззинг также может быть использован для обнаружения "дифференциальных" ошибок, если имеется эталонная реализация. Для автоматизированного регрессионного тестирования сгенерированные входные данные выполняются на двух версиях одной и той же программы. Для автоматизированного дифференциального тестирования[52] сгенерированные входные данные выполняются на двух реализациях одной и той же программы (например, lighttpd и httpd являются реализациями веб-сервера). Если два варианта дают разные выходные данные для одного и того же входа, то один из них может быть ошибочным и должен быть изучен более внимательно.

Проверка отчетов статического анализа

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

Безопасность браузера

Современные веб-браузеры подвергаются обширному размыванию. Код Chromium в Google Chrome постоянно размывается командой безопасности Chrome с 15 000 ядрами. Для Microsoft Edge и Internet ExplorerMicrosoft провела нечеткое тестирование с 670 машинными годами во время разработки продукта , генерируя более 400 миллиардов манипуляций DOM из 1 миллиарда HTML-файлов.

Цепочка инструментов

Фаззер производит большое количество входов за относительно короткое время. Например, в 2016 году проект Google OSS-fuzz производил около 4 трлн входных данных в неделю. Следовательно, многие фаззеры предоставляют цепочку инструментов, которая автоматизирует в остальном ручные и утомительные задачи, которые следуют за автоматизированной генерацией вызывающих отказ входных данных.

Автоматизированная сортировка ошибок

Основная статья: Сортировка ошибок

Автоматизированная сортировка ошибок используется для группировки большого количества входных данных, вызывающих сбои, по первопричине и приоритизации каждой отдельной ошибки по степени серьезности. Фаззер производит большое количество входов, и многие из них, вызывающие сбои, могут эффективно выявлять одну и ту же программную ошибку. Только некоторые из этих ошибок критичны для безопасности и должны быть исправлены с более высоким приоритетом. Например, Координационный центр CERT предоставляет инструменты сортировки Linux, которые группируют входы сбоев по произведенной трассировке стека и перечисляют каждую группу в соответствии с их вероятностью использования.] Исследовательский центр Microsoft Security Research Centre (MSEC) разработал инструмент !exploitable, который сначала создает хэш для аварийного ввода, чтобы определить его уникальность, а затем присваивает рейтинг эксплуатируемости:[

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

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

Автоматизированная минимизация входных данных

Автоматизированный ввод минимизации (или тестовый случай сокращения) является автоматизированной отладки метод, чтобы изолировать ту часть сбой, вызывая ввод, что на самом деле, вызывая сбой.[58][59] Если сбой, вызывая ввод большие и в основном неправильно, это может быть трудно для разработчиков, чтобы понять, что именно вызывает ошибку. Учитывая ввод, вызывающий сбой, автоматизированный инструмент минимизации удалит как можно больше входных байтов, все еще воспроизводя исходную ошибку. Например, дельта-отладка-это автоматизированный метод минимизации входных данных, который использует расширенный алгоритм бинарного поиска для поиска такого минимального входного сигнала[60]

См. также

• Американский fuzzy lop (fuzzer)
• Конколическое тестирование
• Обезьянье тестирование
• Случайное тестирование
• Ответственное раскрытие информации
• Обнаружение ошибок во время выполнения
• Тестирование безопасности
• Тестирование дыма (программное обеспечение)
• Символическое исполнение
• Тестирование системы
• Автоматизация тестирования

Дальнейшее чтение

• Ари Таканен, Джаред Д. Демотт, Чарльз Миллер, Fuzzing for Software Security Testing and Quality Assurance, 2008, ISBN 978-1-59693-214-2
• Майкл Саттон, Адам Грин и Педрам Амини. Fuzzing: Brute Force Vulnerability Discovery, 2007, ISBN 0-321-44611-9.
• Поль, Экономически эффективная идентификация уязвимостей нулевого дня с помощью моделирования угроз и фаззинга, 2011
• Фабьен Дюшен, Обнаружение веб-уязвимостей с помощью модельного вывода с помощью эволюционного фаззинга, 2014, Кандидатская диссертация
• Bratus, S., Darley, T., Locasto, M., Patterson, M. L., Shapiro, R. B., Shubina, A., Beyond Planted Bugs in "Trusting Trust": The Input-Processing Frontier, IEEE Security & Privacy Vol 12, Issue 1, (Jan-Feb 2014), pp. 83-87—В основном подчеркивает, почему фаззинг работает так хорошо: потому что вход-это управляющая программа интерпретатора.

Пруф

//docs.google.com/viewer?url=https%3A%2F%2Fgithub.com%2Fs7ephen%2FRuxxer%2Fraw%2Fmaster%2Fpresentations%2FRuxxer.ppt

• /youtu.be/KAoBCe9coIM
• //pages.cs.wisc.edu/~bart/fuzz/
• fuzzing-project.org/

\\