Часть 1. GPU-Based Fuzzing. Что за зверь такой?

Klim Galkin

SSDLC исследователь (почти)

Всем привет! В процессе изучение глобальной темы фаззинга наткнулся на статью ребят из Trail Of Bits (Ссылка). Такое использование видеокарт в фаззинг‑тестировании зацепило меня, на то есть причины. Самая очевидная — большая «масштабируемость» фаззинг‑тестирования для ускорения тестирования. Но в подобной технике не без подводных камней. Об этом подробнее далее.

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

Введение. Пару слов про фаззинг

Примерная схема фаззинга
Источник: 3. GNATfuzz User’s Guide — GNATDAS Manuals [25.0w (20240326)] (adacore.com)

Но перед началом обсуждения GPU‑фаззинга нужно вообще понять, что такое фаззинг. В рамках статьи будем рассматривать только White‑Box фаззинг (когда имеем исходники), если стараться покрыть все фаззинг‑техники — статей получится на год вперед.

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

Ошибки можно найти примерно такие:

Маппинг ошибок на CWE.
Источник: What Bugs Can You Find With Fuzzing? (code‑intelligence.com)

• Логические ошибки — деление на ноль, состояние гонки и др.

• Недостаточное количество проверок — бесконечная рекурсия или цикл, выход за границы массива и др.

• Проблемы при работе с ресурсами

  • Ошибки сегментации

  • Неопределенное поведение

  • Переполнение буфера/кучи

  • Выделение избыточного объема памяти

  • ...

• ...

Компоненты фаззера

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

1. Какие данные? Откуда они берутся?

2. Как мы контролируем действия программы?

Для этого нужно ввести две сущности внутри фаззера — мутатор, «инструментатор».

Мутатор

С первым, исходя из названия, все понятно. Это некоторый интерфейс фаззера, который либо получает первичный набор входных данных (то есть ему передается директория с начальными данными), либо генерирует их сам (например, с использованием гугловских протобуферов). Если фаззеру передаются какие‑то начальные входные данные, то они проходят этап первичной проверки, в котором проверяется, что данные приводят к новому поведению программы, но не приводят к ее аварийному завершению. Набор данных, которые прошли такую проверку называются сидами (seed).

Исходя из этих сидов алгоритм мутатора следующий:

1. Анализ первичных данных. Выход: сиды

2. Передача сидов в очередь (queue). По сути очередь для большинства фаззеров — отдельная директория

3. Для каждого элемента из очереди:

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

   2. Прогон данных из элемента очереди через тестируемую программу.

   3. Получение обратной связи по работе программы от «инструментатора».

   4. Если данные привели к новому поведению — добавляем в очередь и к сидам.

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

Инструментатор

Не смог подобрать подходящее слово для его описания. Была мысль о том, чтобы назвать его «Анализатором», но решил, что слова «анализ» до этого встречалось достаточно много раз, но сути это не меняет.

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

Модификация кода при сборке под фаззинг

Под капотом большинство фаззеров для определения текущего ветвления используют свою разметку. Разметка представляет из себя матрицу, ячейка которой отвечает за определенное ветвление программы. Если программа пошла по новому пути — значение ячейки меняется на основе внутренних правил фаззера ((ОБРАЗНО) например, XOR текущего значения ячейки со значением предыдущей). Подобная матрица так же хранится в виде файла в директории с выходными данными фаззера. Ряд других вставок, используемых фаззером, можно видеть на скриншоте ниже:

Другие переменные для работы фаззера

Пара плохих слов про CUDA память и потоки

Перед началом рассмотрения GPU‑фаззинга так же стоит рассмотреть структуру памяти на карточках. Почему? Дело в том, что в видеокартах скорость работы существенно зависит количества обращений в память. Сильнее, чем при работе с CPU. Более того, понимание принципа организации потоков позволит проанализировать, а как фаззинг можно параллелить на GPU.

Потоки, варпы, блоки

Как написано в большинстве статьей, и в официальной документации CUDA, основное различие CPU и GPU‑ядер в том, что вторые банально проще по своему строению (скриншот ниже). Так же стоит упомянуть, что при работе CUDA мы сталкиваемся с архитектурой, когда одна инструкция выполняется несколькими потоками одновременно (SIMT)

Сравнению CPU и GPU ядер
Источник: CUDA C++ Programming Guide (nvidia.com)

С физической стороны видеокарта объединяет эти ядра (скалярные процессоры) в потоковые мультипроцессоры, которые и будут выполнять параллельные вычисления. Потоки, у которых я упомянул выше, объединяются в более абстрактную структуру — варпы, которые объединяются в блоки, которые объединяются в grid'ы.

Принцип исполнения потоков на видеокарте
Источник: CUDA Programming: THREAD AND BLOCK HEURISTICS in CUDA Programming (cuda‑programming.blogspot.com)

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

Типы памяти в CUDA

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

1. Регистровая память. Самая быстрая среди всех. Используется для хранения данных потоков в процессе их исполнения. На каждый поток выделяется определенное количество регистров, которое можно рассчитать, зная количество потоков в блоке и количество блоков в гриде. Все регистры 32-битные, CUDA не предусматривает API для работы с данным типом памяти

2. Локальная память (или секция памяти потока в глобальной памяти). Самый медленный тип памяти, позволяющий хранить локальные данные функции, если они не поместились в регистровую память (например, массивы). По сути является частью глобальной памяти и ничем от нее не отличается.

3. Глобальная память. Память, доступная для всех потоков. Предназначена для хранения больших объемов данных. Самая медленная память.

4. Разделяемая память. Быстрый тип памяти. Используется для хранения данных, используемых несколькими потоками в рамках одного блока.

5. Константная память. Быстрый тип памяти. Используется для хранения неизменяемых данных, переданных с хоста. Каждый поток может только читать из этой памяти

6. Память текстур. Предназначена, очевидно, для работы с текстурами, из‑за чего имеет ряд особенностей с точки зрения адресации

Начинаем скрещивать. Подводные камни

После того, как мы рассмотрели теорию по двум важным аспектам GPU‑фаззинга, стоит «на берегу» договориться о том, что задача создания GPU‑фаззера не из легких. Почему? Так как возникает много вопросов:

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

• В какую память нам пихать данные, чтобы не терять в скорости?

• Что нам нужно хранить на девайсе, а что на хосте?

• Из самого первого пункта вылетает еще больше проблем: как определять ветвления, как отлавливать ошибки работы программы, если ОС на видеокарте нет, а значит сигнал об аварийном завершении нам никто не пошлет:(

Большинство из этих проблем каким‑то образом решили господа из Trail Of Bits и описали их в статье, ссылку на которую я прикрепил выше (дублирую, чтобы вы, мои хорошие, не листали: ссылка). Однако альтернативные решения так же существуют, и думать над ними можно вечно, поэтому давайте пофантазируем над архитектурой GPU‑фаззера.

Первые наброски по архитектуре

Очень плохая архитектура GPU-фаззера

Hidden text

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

Поясню по схеме. Слева имеем зону хоста, в которой изначально есть скомпилированное под GPU приложение. Мы понимаем, что в процессе фаззинга есть ряд задач, выполняющихся единожды для инициации процесса фаззинга: получение сидов, и трансляция CPU‑кода в PTX код для GPU, получение результатов. Именно эти операции выполняет хост однократно. Помимо этого, хост передает информацию, необходимую для цикла фаззинга в память карточки: сиды, исполняемый файл. Больше от хоста не требуется ничего, все остальные операции выполняет GPU.

Исходя из раннее изученного материала, нужно понять, как сущность «Kernel» будет параллелиться. Самое очевидное, что код приложения попал в константную память, а значит инструкции и операции неизменяемые, и такую сущность, как «Загрузчик приложения» можно исполнять параллельно, создавая, например, еще одно ядро (по идее в CUDA последних версиях так можно делать). На вход загрузчику будут передаваться мутированные данные из мутатора, ядро будет запускаться, а его ошибки будут отлавливаться благодаря cudaAssert. Если данная функция стриггерилась, значит можно потенциально считать это ошибкой, и отложить в долгий ящик, то есть в глобальную память.

Hidden text

Использование глобальной памяти обуславливается двумя параметрами: вероятность возникновения ошибки и ограниченность разделямой памяти (16 — 48 Кб в среднем).

Если мутированные данные привели к новому поведению, то необходимо изменить матрицу покрытия. Как это сделать — пока не ясно, скорее всего придется думать над инструментацией PTX кода.

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

Мутация данных. Картинка взята из статьи Trail Of Bits

Промежуточный итог

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

Что мы имеем:

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

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

• До конца не понятно, как контролировать и ловить ошибки, которые возникают при работе программы с мутированными данными

• Аналогичная предыдущей ситуация, когда неизвестен механизм сбора покрытия. Да, можно придумать инструментацию PTX кода, и сделать сбор покрытия на GPU‑код, но как потом это покрытие накладывать на CPU‑код?

Как‑то так, много неточностей и неизвестного, но попытка есть попытка. Надеюсь вам понравился данный материал. Всем еще раз спасибо!