АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
2219276 статей на русском языкеО РУВИКИ

Фаззинг

Экспертиза РАН

Logo-ran.pngLogo-ran-black.png
Проводится экспертиза
Российской академией наук
Подробнее
Times2.svg

Экспертиза РАН

Arrow-Right.png
Logo-ran.png
Проводится экспертиза
Российской академией наук
Подробнее

Фаззинг (от англ. fuzzing, также фазз-тестирование, от англ. fuzz testing) — автоматизированная технология тестирования программного обеспечения, заключающаяся в подаче программе некорректных, неожиданных или случайных входных данных. За исполнением программы ведётся мониторинг с целью выявления исключительных ситуаций: сбоев, срабатывания встроенных утверждений или потенциальных утечек памяти. Обычно фаззеры применяются к программам, обрабатывающим структурированные входные данные — структура которых задокументирована (например, формат файла или протокол связи) и позволяет отличить валидные данные от невалидных. Эффективный фаззер порождает полу-валидные входные данные: они достаточно правильные, чтобы не отклоняться парсером на ранних этапах обработки, но достаточно необычны, чтобы вызывать неожиданные эффекты в глубине программы и проявлять недоработанные краевые случаи.

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

История

Термин «fuzz» появился в 1988 году как часть студенческого проекта курса Advanced Operating Systems (CS736), который вёл профессор Бартон Миллер в Висконсинском университете в Мадисоне; результаты впервые опубликованы в 1990 году[1]. Для тестирования надёжности утилит UNIX был реализован генератор случайных командных параметров и входных данных; запускались многократные испытания, завершавшиеся падением программы. Команда Миллера смогла вызвать сбои у 25-33 % протестированных утилит. Все сбои были проанализированы и классифицированы; исходные коды инструментов и наборы данных были опубликованы. Такое тестирование теперь принято называть чёрным ящиком, генеративным и неструктурированным (dumb или «классическим») фаззингом.

По словам Бартонa Миллера, термин был выбран специально, чтобы вызывать ассоциацию со случайными неструктурированными данными[1].

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

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

В сентябре 2014 года был раскрыт баг Shellshock — семейство уязвимостей в широко используемой оболочке Bash для UNIX; большинство уязвимостей были найдены с помощью фаззера AFL[2]. Многие сервисы, доступные из интернета (например, веб-серверы), используют Bash для обработки определённых запросов, что позволило злоумышленникам выполнять произвольные команды, эксплуатируя уязвимые версии Bash[3].

В апреле 2015 года Ханно Бёк показал, что уязвимость Heartbleed (раскрыта в апреле 2014 года), позволяющую получить доступ к тайным данным через криптопротокол TLS (реализуемый библиотекой OpenSSL), могла быть найдена с помощью фаззера AFL[4][5]. Shodan в апреле 2016 года всё ещё находил 238 тысяч уязвимых машин[6], а в январе 2017—200 тысяч[7].

В августе 2016 года Агентство перспективных исследовательских проектов обороны (DARPA) провело финал первого Cyber Grand Challenge, полностью автоматизированного соревнования «захвати флаг», длившегося 11 часов[8]. Его целью была разработка автоматических систем защиты, самостоятельно находящих, эксплуатирующих и исправляющих уязвимости в реальном времени. Фаззинг оказался эффективной атакующей стратегией, позволившей выявлять уязвимости в программном обеспечении соперников; победу одержала система «Mayhem»[9], созданная командой ForAllSecure во главе с Дэвидом Брамли.

В сентябре 2016 года Microsoft анонсировала Project Springfield — облачный сервис для фаззинга с прицелом на обнаружение критических по безопасности ошибок.

В декабре 2016 года Google объявила о запуске OSS-Fuzz — платформы для непрерывного фаззинга ряда ключевых открытых проектов.

На конференции Black Hat 2018 Кристофер Домас продемонстрировал применение фаззинга для выявления скрытого ядра RISC в одном из процессоров, имевшего возможность обходить аппаратные разграничения защиты и выполнять команды режима ядра из режима пользователя.

В сентябре 2020 года Microsoft выпустила платформу OneFuzz — саморазвёртываемую систему фаззинг-как-сервиса для автоматизированного поиска ошибок в программном обеспечении, работавшую под Windows и Linux[10][11]. Проект был архивирован 1 ноября 2023 года[12].

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

Использование случайных входных данных для тестирования программ практикуется с 1950-х годов, когда данные хранились на перфокартах. Разработчики использовали случайные перфокарты или стопки карт с числами в качестве входа; если выполнение программы приводило к ошибке, обнаруживался баг.

Такое тестирование также называют рандомизированным тестированием или monkey testing.

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

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

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

Типы

Фаззеры классифицируются по разным признакам:

  1. По способу генерации входных данных: генеративные (generation-based) создают данные с нуля, мутационные (mutation-based) — модифицируют существующие образцы.
  2. По учёту структуры входных данных: dumb (неструктурированные) не учитывают формат, smart (структурированные) — опираются на правила формата.
  3. По знанию внутреннего устройства программы: white-box (белые ящики) используют анализ кода, black-box (чёрные ящики) — тестируют «вслепую», grey-box (серые ящики) — оперируют косвенной информацией (инструментация).

Повторное использование стартовых образцов (seed)

Мутационный фаззер использует набор образцов входных данных (seed corpus), создавая новые варианты путём их мутации[13]. Например, при фаззинге библиотеки libpng используют набор валидных PNG-изображений, а фаззер порождает их случайные модификации. Чем больше разнообразных seed-файлов, тем выше вероятность открытия уязвимостей. Автоматизированный отбор образцов позволяет максимизировать количество найденных багов[14].

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

Некоторые системы совмещают оба подхода — и генерацию с нуля, и мутацию seed-файлов.

Учёт структуры входных данных

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

Smart (структурированный) фаззер (на базе модели или грамматики) использует модель для генерации большей доли валидных входных данных. Например, если ввод моделируется через абстрактное синтаксическое дерево, smart-мутационный фаззер будет переставлять целые поддеревья. При наличии формальной грамматики generation-based фаззер строит корректные строки, исходя из правил продукции. Однако требует наличия формализованной модели, что не всегда осуществимо на практике; если доступна большая коллекция примеров, применяются методы индукции грамматик и синтеза модели.

Dumb-фаззеры не используют знания о формате; например, AFL — мутационный dumb-фаззер, случайно инвертирующий биты, подставляющий «интересные» значения, удаляя или перемещая блоки данных. Недостаток: низкая доля валидных данных, тестируется преимущественно парсер. Пример — необходимость учёта контрольной суммы в файлах с CRC: dumb-фаззер, не пересчитывающий checksum, породит множество «заведомо невалидных» тестов, которые программа отвергнет. Некоторые инструменты умеют автоматически пересчитывать контрольные суммы после мутирования данных[15].

Учёт структуры тестируемой программы

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

Black-box-фаззеры не используют данные о внутреннем устройстве программы, что позволяет тестировать множество входных данных за короткое время и хорошо масштабироваться, однако такие фаззеры особенно эффективны только для «поверхностных» ошибок. Существуют попытки обучать black-box-фаззеры по ответам программы: например, LearnLib реализует активное обучение для построения автомата поведения веб-приложения.

White-box-фаззеры используют анализ кода для систематического увеличения покрытия или достижения критичных точек. Например, SAGE применяет символьное исполнение и конколичное исполнение для восхождения по путям кода. Если доступна модель спецификации, применяются методы тестирования на модели. White-box-подход очень эффективен для выявления сложных багов, однако требует значительного времени на анализ. Если расходы на анализ велики, black-box может быть продуктивнее. Совмещённые подходы сочетают эффективность анализа с производительностью случайного тестирования.

Gray-box-фаззеры используют инструментацию для косвенного сбора информации о структуре. Например, AFL и libFuzzer используют легковесную трассировку переходов между базовыми блоками — что даёт баланс между скоростью и качеством тестирования, делая gray-box-методы одними из самых эффективных в поиске уязвимостей.

Применение

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

Поиск ошибок

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

Как правило, основным критерием в отсутствие спецификаций является различение падений (crash) и «нормальных» завершений. Крэши легко выделить и часто указывают на уязвимости (DOS, исполнение произвольного кода), но их отсутствие не гарантирует безопасность: например, переполнение буфера в C не обязательно приводит к падению, поведение может быть неопределённым.

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

В случае наличия эталонной реализации фаззинг применяют для поиска «дифференциальных» ошибок: в рамках регрессионного[21] или дифференциального тестирования[22] одинаковый вход подаётся разным версиям или аналогичным программам (например, lighttpd и httpd), различие в ответах указывает на потенциальную ошибку.

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

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

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

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

Инструментарий

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

Автоматическое распределение багов (triage)

Автоматическое распределение багов (bug triage) группирует найденные входы по причинам и приоритезирует ошибки по степени критичности. Многие входные данные могут приводить к одному багу; только часть из багов действительно критична для безопасности и требует безотлагательного исправления. Например, CERT Coordination Center предоставляет инструменты triage для Linux, группирующие краш-данные по стеку исполнения и вычисляющие показатель вероятности эксплуатации[26]. Microsoft Security Research Centre разработал инструмент «!exploitable», который хеширует данные о сбое и выставляет рейтинг эксплуатируемости входа[27]:

  • Exploitable (эксплуатируемый),
  • Probably Exploitable (вероятно эксплуатируемый),
  • Probably Not Exploitable (вероятно не эксплуатируемый),
  • Unknown (не определено).

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

Автоматическое минимизирование входных данных

Автоматическое минимизирование (reduction, минимизация тест-кейса) — автоматизированная отладочная техника, выделяющая ту часть входных данных, которая реально вызывает сбой. Если вход обширен и содержит много шума, анализ затруднён; минимизация удаляет как можно больше байтов без потери воспроизводимости бага. Методы дельта-отладки (Delta Debugging) используют пошаговый двоичный поиск для нахождения минимального триггера ошибки[28].

Список популярных фаззеров

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

Название Белый/серый/чёрный ящик Smart/dumb Язык реализации Лицензия
AFL Серый ящик Dumb C Apache 2.0
AFL++ Серый ящик Dumb C Apache 2.0
AFLFast Серый ящик Dumb C Apache 2.0
Angora Серый ящик Dumb C++ Apache 2.0
honggfuzz Серый ящик Dumb C Apache 2.0
QSYM (нет данных) (нет данных) (нет данных) (нет данных)
SymCC Белый ящик (нет данных) C++ GPL, LGPL
T-Fuzz (нет данных) (нет данных) (нет данных) (нет данных)
VUzzer (нет данных) (нет данных) (нет данных) (нет данных)

Примечания

  1. ↑ 1 2 Miller, Barton Foreword for Fuzz Testing Book (англ.). UW-Madison Computer Sciences (апрель 2008). Дата обращения: 29 марта 2024.
  2. ↑ Zalewski, Michał Bash bug: the other two RCEs, or how we chipped away at the original fix (CVE-2014-6277 and '78) (англ.). lcamtuf's blog (1 октября 2014). Дата обращения: 13 марта 2017.
  3. ↑ Seltzer, Larry Shellshock makes Heartbleed look insignificant (англ.). ZDNet (29 сентября 2014). Дата обращения: 29 сентября 2014.
  4. ↑ Böck, Hanno Fuzzing: Wie man Heartbleed hätte finden können (нем.). Golem.de. Дата обращения: 13 марта 2017.
  5. ↑ Böck, Hanno How Heartbleed could've been found (англ.). Hanno's blog. Дата обращения: 13 марта 2017.
  6. ↑ Search engine for the internet of things – devices still vulnerable to Heartbleed (англ.). shodan.io. Дата обращения: 13 марта 2017.
  7. ↑ Heartbleed Report (2017-01) (англ.). shodan.io. Дата обращения: 10 июля 2017. Архивировано 23 января 2017 года.
  8. ↑ Walker, Michael DARPA Cyber Grand Challenge (англ.). darpa.mil. Дата обращения: 12 марта 2017.
  9. ↑ Mayhem comes in first place at CGC (англ.). Дата обращения: 12 марта 2017.
  10. ↑ Microsoft: Windows 10 is hardened with these fuzzing security tools – now they're open source (англ.). ZDNet (15 сентября 2020).
  11. ↑ Microsoft open-sources fuzzing test framework (англ.). InfoWorld (17 сентября 2020).
  12. ↑ microsoft/onefuzz. Microsoft (3 марта 2024). Дата обращения: 6 марта 2024.
  13. ↑ Offutt, Jeff; Xu, Wuzhi (2004). “Generating test cases for web services using data perturbation”. ACM SIGSOFT Software Engineering Notes. 29 (5): 1—10. DOI:10.1145/1022494.1022529. S2CID 52854851.
  14. ↑ Rebert, Alexandre; Cha, Sang Kil; Avgerinos, Thanassis; Foote, Jonathan; Warren, David; Grieco, Gustavo; Brumley, David (2014). “Optimizing Seed Selection for Fuzzing” (PDF). Proceedings of the 23rd USENIX Conference on Security Symposium [англ.]: 861—875.
  15. ↑ Wang, T. TaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection // 2010 IEEE Symposium on Security and Privacy / T. Wang, T. Wei, G. Gu … [и др.]. — май 2010. — P. 497–512. — ISBN 978-1-4244-6894-2. — doi:10.1109/SP.2010.37.
  16. ↑ Hamlet, Richard G.; Taylor, Ross (декабрь 1990). “Partition testing does not inspire confidence”. IEEE Transactions on Software Engineering. 16 (12): 1402—1411. DOI:10.1109/32.62448. Проверьте дату в |date= (справка на английском)
  17. ↑ Weyuker, Elaine J. (1 ноября 1982). “On Testing Non-Testable Programs”. The Computer Journal. 25 (4): 465—470. DOI:10.1093/comjnl/25.4.465.
  18. ↑ Barr, Earl T.; Harman, Mark; McMinn, Phil; Shahbaz, Muzammil; Yoo, Shin (1 мая 2015). “The Oracle Problem in Software Testing: A Survey” (PDF). IEEE Transactions on Software Engineering. 41 (5): 507—525. DOI:10.1109/TSE.2014.2372785.
  19. ↑ Clang compiler documentation (англ.). clang.llvm.org. Дата обращения: 13 марта 2017.
  20. ↑ GNU GCC sanitizer options (англ.). gcc.gnu.org. Дата обращения: 13 марта 2017.
  21. ↑ Orso, Alessandro. BERT: BEhavioral Regression Testing // Proceedings of the 2008 international workshop on dynamic analysis: Held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008) : [англ.] / Alessandro Orso, Tao Xie. — ACM, 2008. — P. 36–42. — ISBN 9781605580548. — doi:10.1145/1401827.1401835.
  22. ↑ McKeeman, William M. (1998). “Differential Testing for Software” (PDF). Digital Technical Journal [англ.]. 10 (1): 100—107. Архивировано из оригинала (PDF) 2006-10-31.
  23. ↑ Babić, Domagoj. Statically-directed dynamic automated test generation // Proceedings of the 2011 International Symposium on Software Testing and Analysis : [англ.] / Domagoj Babić, Lorenzo Martignoni, Stephen McCamant … [et al.]. — ACM, 2011. — P. 12–22. — ISBN 9781450305624. — doi:10.1145/2001420.2001423.
  24. ↑ 1 2 Sesterhenn, Eric; Wever, Berend-Jan; Orrù, Michele; Vervier, Markus Browser Security WhitePaper (англ.). X41D SEC GmbH (19 сентября 2017).
  25. ↑ Security enhancements for Microsoft Edge (Microsoft Edge for IT Pros) (англ.). Microsoft (15 октября 2017). Дата обращения: 31 августа 2018.
  26. ↑ CERT Triage Tools (англ.). CERT Division of the Software Engineering Institute (SEI) at Carnegie Mellon University (CMU). Дата обращения: 14 марта 2017.
  27. ↑ Microsoft !exploitable Crash Analyzer (англ.). CodePlex. Дата обращения: 14 марта 2017.
  28. ↑ Zeller, Andreas; Hildebrandt, Ralf (февраль 2002). “Simplifying and Isolating Failure-Inducing Input”. IEEE Transactions on Software Engineering [англ.]. 28 (2): 183—200. CiteSeerX 10.1.1.180.3357. DOI:10.1109/32.988498. ISSN 0098-5589. Дата обращения 2017-03-14. Проверьте дату в |date= (справка на английском)

Литература

  • Nappa, A. Fuzzing Against the Machine: Automate Vulnerability Research with Emulated IoT Devices on Qemu : [англ.] / A. Nappa, E. Blázquez. — Packt Publishing, Limited, 2023. — ISBN 9781804614976. — Полное руководство по автоматизированному анализу уязвимостей с помощью эмуляции IoT-устройств.
  • Zeller, Andreas. The Fuzzing Book : [англ.] / Andreas Zeller, Rahul Gopinath, Marcel Böhme … [et al.]. — Saarbrücken : CISPA + Saarland University, 2019. — Бесплатный онлайн-учебник по фаззингу.
  • Ари Таканен, Джаред Д. ДеМотт, Чарльз Миллер. «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.
  • H. Pohl. «Cost-Effective Identification of Zero-Day Vulnerabilities with the Aid of Threat Modeling and Fuzzing», 2011 (архив)
  • Фабиен Дюшен. «Detection of Web Vulnerabilities via Model Inference assisted Evolutionary Fuzzing», диссертация, 2014 ([1]).
  • Bratus, Sergey; Darley, Trey; Locasto, Michael; Patterson, Meredith L.; Shapiro, Rebecca Bx; Shubina, Anna (2014). “Beyond Planted Bugs in "Trusting Trust": The Input-Processing Frontier”. IEEE Security & Privacy. 12 (1): 83—87. DOI:10.1109/MSP.2014.1. — Рассматривается механизм, почему фаззинг эффективен: потому что ввод определяет поведение интерпретатора.

Ссылки

Категории