ИИтог

Google Project Zero выпустила MAccConc для поиска гонок в ядре Linux

безопасностьРедакция ИИтогHacker News🔥49Рейтинг ИИтог49Влияние65Новизна70Релевантность55Неожиданность45Участники60Достоверность88

Автор поста в блоге Google Project Zero (Янн Хорн) опубликовал новый набор инструментов для поиска гонок (race conditions), багов, которые проявляются только при определённом порядке выполнения потоков в многопоточном коде. Проект называется MAccConc, сокращение от «Memory Access Concurrency» («конкурентность обращений к памяти»), и нацелен на ядро Linux.

Гонки, трудноуловимый класс уязвимостей: подтвердить их после ручного или статического обнаружения сложно, надёжный регрессионный тест для них почти невозможно написать, а фаззерам тяжело перебрать все интересные переплетения параллельных операций. До этого проекта для ядра Linux автор диагностировал такие баги вручную, пересобирая ядро с условными вызовами mdelay() (программной задержкой) в нужных местах, что требует проб и ошибок; на macOS и Windows с поддержкой DTrace для той же цели годится функция chill(), но с ограничением: DTrace трассирует только границы невстраиваемых функций и явные точки трассировки, а не каждую инструкцию.

MAccConc состоит из трёх частей: инструмента, который автоматически проверяет все возможные A-B-A-переплетения тестового сценария; терминального интерфейса для ручного исследования переплетений; и графического интерфейса с той же целью. Часть для ядра также задумана как основа для будущего поиска гонок фаззингом, но пользовательские инструменты для этого ещё предстоит написать. Все компоненты выложены в открытый доступ на GitHub.

Технически подход опирается на то, что уже есть в ядре. Обращения к памяти отслеживаются инструментированием ASAN в режиме «outline» (флаг компилятора asan-instrumentation-with-call-threshold=0, включаемый опцией ядра CONFIG_KASAN_OUTLINE), так на каждое обращение к памяти генерируется вызов вспомогательной функции. Передачей этих данных в пользовательское пространство занимается уже встроенный в ядро механизм KCOV (обычно используемый для покрытия кода при фаззинге), а не ftrace, по впечатлению автора, KCOV устроен проще и рассчитан на более частые события трассировки. Отдельная сложность в том, что ASAN по умолчанию объединяет вызовы для соседних обращений к памяти и не всегда фиксирует обращения к стеку и к глобальным переменным, эти оптимизации пришлось точечно отключать флагами компилятора asan-opt-same-temp и asan-opt-globals. Рассматривалась и альтернатива, инструментирование TSAN, которое даёт больше данных об атомарности доступа, но компиляторы не умеют одновременно включать хуки ASAN и TSAN, так что для этого пришлось бы либо пожертвовать проверкой use-after-free, либо переносить реализацию ASAN в ядре поверх хуков TSAN.

Чтобы задавать порядок выполнения потоков напрямую, автор добавил в KCOV новый ioctl, KCOV_SET_DI. Через него пользовательское пространство расставляет на конкретных обращениях к памяти команды «выставить флаг» или «дождаться флага», до или после обращения, в общем массиве флагов, с ограничением на число итераций активного ожидания (spin-wait). На этой основе работают два способа принудительного упорядочивания: более простые ограничения вида «A обязательно раньше B» (сейчас на них построены терминальный и графический интерфейсы) и полностью заданный порядок с явным переключением контекста между потоками (на нём построен автоматический A-B-A-тестер).

Отдельная техническая проблема, как стабильно ссылаться на одно и то же место в коде между разными запусками теста, если адрес данных каждый раз меняется (объект выделяется заново), а адрес инструкции может совпадать для разных вызовов одной и той же функции вроде memcpy() или spin_lock(). Решение, которое автор называет «count-augmented stack traces» («стек вызовов со счётчиками»): каждый элемент стека вызовов помечается не только адресом функции, но и порядковым номером этого вызова внутри вызывающего кадра, например, «второй вызов __x64_sys_recvfrom, а внутри него первый вызов __sys_recvfrom» и так далее. Для этого потребовалось научить KCOV передавать в пользовательское пространство события входа и выхода из функций; соответствующий патч для LLVM (компонент SanitizerCoverage) автор отправил в проект несколько месяцев назад, и он вошёл в релиз LLVM 23.1.0.

Проект вдохновлён обсуждениями с Недом Уильямсоном, автором sockfuzzer, который для похожего исследования гонок использовал собственный планировщик, умеющий переключать потоки на примитивах синхронизации. Ближайший технический аналог, система SKI: она тоже ищет «точки коммуникации», пары обращений к памяти на разных потоках, где хотя бы одно обращение, запись, а диапазоны памяти пересекаются, но собирает данные патченной версией QEMU в режиме TCG и переигрывает разные переплетения через снимки состояния виртуальной машины. MAccConc решает обе задачи иначе, инструментированием прямо в ядре, без эмулятора, что в перспективе допускает тестирование и на «голом железе», а не только в виртуальных машинах.

У метода есть известные ограничения. Основанное на ASAN отслеживание может пропускать часть гонок, связанных с объектами на стеке, например, с очередями ожидания (wait queues). Часть фоновой активности ядра, например, обработку loopback-пакетов или колбэки RCU, механизм удалённого покрытия KCOV пока не охватывает почти нигде в апстриме: сейчас он используется в основном для фаззинга Bluetooth и USB, хотя автор считает расширение этого механизма на другие части ядра несложным и уже подготовил черновой патч для RCU-колбэков. Автор также отмечает, что перенос сбора данных в ядро оправдан ещё и тем, что в перспективе ядро сможет отдавать более высокоуровневую информацию, например, о захвате и освобождении блокировок, хотя на момент публикации это не реализовано. В середине поста, перед самими демонстрациями, автор обещает показать работу автоматического тестера на практике, «два наглядных демо», а во вступлении советует тем, кто интересуется прежде всего теорией, сразу перейти к разделу про стек вызовов со счётчиками.

Ключевые факты

  • Google Project Zero выложила на GitHub набор MAccConc («Memory Access Concurrency»), три инструмента для ядра Linux: автоматический тестер всех A-B-A-переплетений потоков, терминальный интерфейс и графический интерфейс для ручного разбора гонок.
  • Обращения к памяти отслеживаются инструментированием ASAN в режиме «outline» (флаг компилятора asan-instrumentation-with-call-threshold=0, опция ядра CONFIG_KASAN_OUTLINE), а передачей данных в пользовательское пространство занимается уже встроенный в ядро механизм KCOV, вместо ftrace, который, по впечатлению автора, хуже подходит для таких частых событий.
  • Новый ioctl KCOV_SET_DI позволяет из пользовательского пространства принудительно навязывать порядок выполнения потоков, через простые ограничения «A раньше B» или через полностью заданное переключение контекста между потоками (инъекция задержек, delay injection).
  • Для устойчивой идентификации одного и того же обращения к памяти между запусками теста автор предложил «стек вызовов со счётчиками» (count-augmented stack traces); потребовавшийся патч для LLVM (SanitizerCoverage) вошёл в релиз LLVM 23.1.0.
  • Проект вдохновлён обсуждениями с Недом Уильямсоном (автором sockfuzzer) и системой SKI, которая ищет гонки через патченный QEMU и снимки состояния виртуальной машины; MAccConc делает то же самое инструментированием прямо в ядре, без эмулятора.

Почему это важно

Гонки (race conditions), один из самых неудобных классов багов: они проявляются только при определённом стечении обстоятельств в многопоточном коде, поэтому их трудно подтвердить после ручного обнаружения, для них почти невозможно написать надёжный регрессионный тест, а фаззерам тяжело перебрать все интересные переплетения параллельных операций. До сих пор для ядра Linux с этим боролись вручную, например, пересобирая ядро с условными программными задержками (mdelay()) в нужных местах методом проб и ошибок. Более системный инструмент существовал, SKI, но он требовал патченной версии QEMU и работы через снимки состояния виртуальной машины. MAccConc решает ту же задачу, опираясь на то, что уже есть в самом ядре Linux (ASAN, KCOV), без эмулятора и вне зависимости от виртуализации, и выходит готовым, работающим инструментом в открытом доступе, а не просто описанием метода.

Кому это важно

В первую очередь, разработчикам и мейнтейнерам ядра Linux, которые ищут причину конкретного зависания или падения и хотят убедиться, что нашли именно гонку, а не что-то другое. Дальше, исследователям безопасности и авторам фаззеров, которые строят автоматический поиск похожих уязвимостей и заинтересованы в готовой инфраструктуре трассировки вместо самодельной. Отдельно, разработчикам компиляторов и системы LLVM: проект уже привёл к реальному патчу в SanitizerCoverage, вошедшему в LLVM 23.1.0, и похожие доработки могут понадобиться другим подобным инструментам. И, конечно, самой команде Google Project Zero и другим публичным группам, которые ищут уязвимости в ядре Linux и делятся инструментарием, это часть их обычной работы.

Как это применить

Все три инструмента выложены на GitHub под именем MAccConc, там же, README с инструкциями по установке и использованию. Для работы нужно ядро, собранное с ASAN в режиме «outline» (опция CONFIG_KASAN_OUTLINE и флаг компилятора asan-instrumentation-with-call-threshold=0) и с патчем автора, добавляющим ioctl KCOV_SET_DI, этот патч пока лежит в отдельной ветке ядра автора, а не в официальном дереве. Также нужен достаточно новый LLVM, не ниже 23.1.0, где появилась поддержка событий входа и выхода из функций для SanitizerCoverage. Дальше, два сценария использования: если гонка уже заподозрена в конкретном тестовом случае, автоматический тестер сам переберёт все A-B-A-переплетения и подтвердит или опровергнет баг; если нужно вручную проиграть конкретный сценарий (например, чтобы построить регрессионный тест), для этого, терминальный или графический интерфейс. Автоматический поиск гонок фаззингом пока не готов: ядерная часть для этого подходит, но пользовательские инструменты для фаззинга, по словам автора, «ещё предстоит реализовать».

Можно ли доверять

Источник, официальный блог Google Project Zero, одной из самых авторитетных публичных команд по поиску уязвимостей, обычно публикующей подробные и проверяемые технические разборы. Здесь это подтверждается: описаны конкретные флаги компилятора, конкретная опция ядра, конкретный дизайн нового ioctl, а ключевой побочный результат, патч в LLVM, реально вошёл в релиз 23.1.0, и это можно проверить независимо от самого поста. Весь инструментарий открыт на GitHub, что тоже снижает пространство для голословных заявлений. Из оговорок: автор поста назван, это Янн Хорн из Google Project Zero, а не аноним, что для оценки доверия скорее плюс; а вот ни числа найденных этим методом ошибок, ни цифр по производительности в тексте действительно нет, доступный нам текст обрывается на заголовке «Demo: automatic testing», ещё до вывода kcov-autorace на тестовом примере со статистикой и раздела «Demo: GUI». Также стоит помнить, что новый ioctl существует пока только в личной ветке ядра автора, это исследовательский прототип, а не принятый в апстрим Linux код.

Риски и подводные камни

У метода есть встроенные слепые зоны. Слежка на основе ASAN может не заметить часть гонок с объектами на стеке, например, с очередями ожидания (wait queues), потому что ASAN не всегда генерирует вызов на обращение к стеку или к глобальным переменным без специальных дополнительных флагов. Между ASAN и TSAN приходится выбирать: компиляторы не умеют одновременно включать хуки обоих санитайзеров, поэтому получить богатую TSAN-картину атомарности доступа, не потеряв текущую ASAN-детекцию use-after-free, без дополнительной инженерной работы не выйдет. Слабое место, фоновая и асинхронная работа ядра: удалённое покрытие KCOV для такого кода (например, обработки loopback-пакетов или колбэков RCU) в апстриме Linux почти не реализовано и сейчас используется в основном для фаззинга Bluetooth и USB; для RCU-колбэков у автора есть только черновой патч. Наконец, сам инструмент годится сегодня для проверки уже подозреваемых багов и написания регрессионных тестов, но не для слепого автоматического поиска новых гонок фаззингом, пользовательская часть для этого, по словам автора, «ещё предстоит реализовать».

«Некоторые гонки с участием объектов на стеке, например, очередей ожидания (wait queues), этим методом могут остаться незамеченными.»

— автор поста в блоге Google Project Zero