Фаззинг ядра Linux

Идея первая: для генерации вводов использовать подход coverage-guided — на основе сборки покрытия кода.

Как он работает? Помимо генерирования случайных вводов с нуля, мы поддерживаем набор ранее сгенерированных «интересных» вводов — корпус. И иногда, вместо случайного ввода, мы берем один ввод из корпуса и его слегка модифицируем.

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

Таким образом, мы постепенно проникаем все глубже и глубже, а в корпусе собираются все более и более интересные программы.

Этот подход используется в двух основных инструментах для фаззинга приложений в юзерспейсе: AFL и libFuzzer.

Coverage-guided-подход можно скомбинировать с использованием грамматики. Если мы модифицируем структуру, можем делать это в соответствии с ее грамматикой, а не просто случайно выкидывать байты. А если вводом является последовательность сисколов, то изменять ее можно, добавляя или удаляя вызовы, переставляя их местами или меняя их аргументы.

Для coverage-guided-фаззинга ядра нам нужен способ собирать информацию о покрытии кода. Для этой цели был разработан инструмент KCOV. Он требует доступа к исходникам, но для ядра у нас они есть.

Чтобы включить KCOV, нужно пересобрать ядро с включенной опцией CONFIG_KCOV, после чего покрытие кода ядра можно собирать через /sys/kernel/debug/kcov.

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

Ловим баги

Теперь придумаем что‑нибудь получше для обнаружения багов, чем выпадение в kernel panic.

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

Для решения этих проблем придумали динамические детекторы багов. Слово «динамические» означает, что они работают в процессе исполнения программы. Они анализируют ее действия в соответствии со своим алгоритмом и пытаются поймать момент, когда произошло что‑то плохое.

Для ядра таких детекторов несколько. Самый крутой из них — KASAN. Крут он не потому, что я над ним работал, а потому, что он находит главные типы повреждений памяти: выходы за границы массива и use-after-free. Для его использования достаточно включить опцию CONFIG_KASAN, и KASAN будет работать в фоне, записывая репорты об ошибках в лог ядра при обнаружении.

Больше о динамических детекторах для ядра можно узнать из доклада Mentorship Session: Dynamic Program Analysis for Fun and Profit Дмитрия Вьюкова (слайды).

Автоматизация

Что касается автоматизации, то тут можно придумать много всего интересного. Автоматически можно:

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

Как это все сделать? Написать код и включить его в наш фаззер. Исключительно инженерная задача.

Все вместе

Возьмем эти три идеи — coverage-guided-подход, использование динамических детекторов и автоматизацию процесса фаззинга — и включим в наш фаззер. У нас получится следующая картина.

Как запускать ядро?	В QEMU или на реальном железе
Что будет входными данными?	Системные вызовы
Как входные данные передавать ядру?	Через запуск исполняемого файла
Как генерировать вводы?	Знание API + KCOV
Как определять наличие багов?	KASAN и другие детекторы
Как автоматизировать?	Все перечисленные выше штуки

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

Иногда можно услышать, что KASAN является неотделимой частью syzkaller. Это не так. KASAN можно использовать и с Trinity, а syzkaller — и без KASAN.

Другой способ фаззинга ядра Linux

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

Вытаскиваем код в юзерспейс

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

Для некоторых подсистем это сделать несложно. Если подсистема просто выделяет память с помощью kmalloc и освобождает ее через kfree и на этом привязка к ядерным функциям заканчивается, тогда мы можем заменить kmalloc на malloc и kfree на free. Дальше мы компилируем код как библиотеку и фаззим с помощью того же libFuzzer.

Для большинства подсистем с этим подходом возникнут сложности. Требуемая подсистема может использовать API, которые в юзерспейсе попросту недоступны. Например, RCU.

RCU (Read-Copy-Update) — механизм синхронизации в ядре Linux.

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

Этот подход использовался для фаззинга eBPF, ASN.1-парсеров и сетевой подсистемы ядра XNU.

Фаззинг внешних внешних интерфейсов

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

Другими словами, ядро обрабатывает данные, приходящие через Ethernet, USB, Bluetooth, NFC, мобильные сети и прочие железячные протоколы.

Например, мы послали на систему TCP-пакет. Ядро должно его распарсить, чтобы понять, на какой порт он пришел и какому приложению его доставить. Отправляя случайно сгенерированные TCP-пакеты, мы можем фаззить сетевую подсистему с внешней стороны.

Возникает вопрос: как доставлять в ядро данные со стороны внешних интерфейсов? Сисколы мы просто звали из бинарника, а если мы хотим общаться с ядром по USB, то такой подход не пройдет.

Доставлять данные можно через реальное железо: например, отправлять сетевые пакеты по сетевому кабелю или использовать Facedancer для USB. Но такой подход плохо масштабируется: хочется иметь возможность фаззить внутри виртуалки.

Здесь есть два решения.

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

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

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

Такой подход применяется в фаззере vUSBf. В нем использовали QEMU и протокол usbredir, который позволяет с хоста подключать USB-устройства внутрь виртуалки.

За пределами API-aware-фаззинга

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

Пример: clone и sigaction. Да, они тоже принимают аргументы, тоже могут вернуть результат, но при этом они порождают еще один поток исполнения. clone создает новый процесс, а sigaction позволяет настроить обработчик сигнала, которому передастся управление, когда этот сигнал придет.

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

О сложных подсистемах

Есть еще подсистемы eBPF и KVM. В качестве вводов вместо простых структур они принимают последовательность исполняемых инструкций. Сгенерировать корректную цепочку инструкций — это гораздо более сложная задача, чем сгенерировать корректную структуру. Для фаззинга таких подсистем нужно разрабатывать специальные фаззеры. Навроде фаззера JavaScript-интерпретаторов fuzzilli.

Структурирование внешних вводов

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

Пример: пусть мы фаззим TCP и у нас на хосте есть сокет, с которым мы хотим установить соединение извне. Казалось бы, мы посылаем SYN, хост отвечает SYN/ACK, мы посылаем ACK — все, соединение установлено. Но в полученном нами пакете SYN/ACK содержится номер подтверждения, который мы должны вставить в пакет ACK. В каком‑то смысле это возврат значения из ядра, но с внешней стороны.

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

Про USB

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

Помимо KCOV

Как еще можно собирать покрытие кода, кроме как с помощью KCOV?

Во‑первых, можно использовать эмуляторы. Представьте, что виртуалка эмулирует ядро инструкция за инструкцией. Мы можем внедриться в цикл эмуляции и собирать оттуда адреса инструкций. Этот подход хорош тем, что, в отличие от KCOV, тут не нужны исходники ядра. Как следствие, этот способ можно использовать для закрытых модулей, которые доступны в виде бинарников. Так делают фаззеры TriforceAFL и UnicoreFuzz.

Еще один способ собирать покрытие — использовать аппаратные фичи процессора. Например, kAFL использует Intel PT.

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

Сборка релевантного покрытия

Для coverage-guided-фаззинга нам нужно собирать покрытие с кода подсистемы, которую мы фаззим.

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

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

За пределами сбора покрытия кода

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

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

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

Сборка корпуса вводов

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

Я видел такой подход в проекте Moonshine: авторы запускали системные утилиты под strace, собирали с них лог и использовали полученную последовательность сисколов как ввод для фаззинга с помощью syzkaller.

Ловим больше багов

Существующие динамические детекторы неидеальны и могут не замечать некоторые ошибки. Как находить такие ошибки? Улучшать детекторы.

Можно, к примеру, взять KASAN (напомню, он ищет повреждения памяти) и добавить аннотации для какого‑нибудь нового аллокатора. По умолчанию KASAN поддерживает стандартные аллокаторы ядра, такие как slab и page_alloc. Но некоторые драйверы выделяют здоровенный кусок памяти и потом самостоятельно его нарезают на блоки помельче (привет, Android!). KASAN в таком случае не сможет найти переполнение из одного блока в другой. Нужно добавлять аннотации вручную.

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

Можно делать свои баг‑детекторы с нуля. Самый простой способ — добавить в исходники ядра ассерты. Если мы знаем, что в определенном месте всегда должно выполняться определенное условие, — добавляем BUG_ON и начинаем фаззить. Если BUG_ON сработал — баг найден. А мы сделали элементарный детектор логической ошибки. Такие детекторы особенно интересны в контексте фаззинга BPF, потому что ошибка в BPF обычно не приводит к повреждению памяти и остается незамеченной.

Итого

Давайте подведем итоги.

Глобально подходов к фаззингу ядра Linux три:

Использовать юзерспейсный фаззер. Либо берете фаззер типа AFL или libFuzzer и его переделываете, чтобы он звал сисколы вместо функций юзерспейсной программы. Либо вытаскиваете ядерный код в юзерспейс и фаззите его там. Эти способы прекрасно работают для подсистем, обрабатывающих структуры, потому что в основном юзерспейсные фаззеры ориентированы на мутацию массива байтов. Примеры: фаззинг файловых систем и Netlink. Для coverage-guided-фаззинга вам придется подключить сборку покрытия с ядра к алгоритму фаззера.
Использовать syzkaller. Он идеально подходит для API-aware-фаззинга. Для описания сисколов и их возвращаемых значений и аргументов он использует специальный язык — syzlang.
Написать свой фаззер с нуля. Это отличный способ разобраться, как работает фаззинг изнутри. А еще с помощью этого подхода можно фаззить подсистемы с необычными интерфейсами.

Советы по syzkaller

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

Не используйте syzkaller на стандартном ядре со стандартным конфигом — ничего не найдете. Много людей фаззят ядро руками и с помощью syzkaller. Кроме того, есть syzbot, который фаззит ядро в облаке. Лучше сделайте что‑нибудь новое: напишите новые описания сисколов или возьмите нестандартный конфиг ядра.

Syzkaller можно улучшать и расширять. Когда я делал фаззинг USB, я сделал его поверх syzkaller, написав дополнительный модуль.

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

Как понять, что ваш фаззер работает хорошо? Очевидно, что если он находит новые баги, то все отлично. Но вот что делать, если не находит?

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

Откатите патчи для исправленных багов и убедитесь, что фаззер их находит.

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

И еще пара советов:

Пишите фаззер на основе кода, а не документации. Документация может быть неточна. Источником истины всегда будет код. Я на это натолкнулся, когда делал фаззер USB: ядро обрабатывало другое подмножество протоколов, чем описанное в документации.

В первую очередь делайте фаззер умным, а уже потом делайте его быстрым. «Умный» означает генерировать более точные вводы, лучше собирать покрытие или что‑нибудь еще в таком роде, а «быстрый» — иметь больше исполнений в секунду.

Выводы

Создание фаззеров — инженерная работа. И основана она на инженерных умениях: проектировании, программировании, тестировании, дебаггинге и бенчмаркинге.

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

Надеюсь, я скоро увижу новый необычный фаззер, который напишите именно вы!

Еще по теме: Как взломать программу в формате MSI