2025-11-16T07:49:19.632070

Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing

Liu, Zhang, Cheng et al.
Fuzzing has become a cornerstone technique for uncovering vulnerabilities and enhancing the security of OS kernels. However, state-of-the-art kernel fuzzers, including the de facto standard Syzkaller, struggle to generate valid syscall sequences that respect implicit Syscall Dependency Relations (SDRs). Consequently, many generated seeds either fail kernel validation or cannot penetrate deep execution paths, resulting in significant inefficiency. We hypothesize that SDRs can be effectively learned from both historic and present kernel execution data, and that incorporating these learned relations into fuzzing can substantially improve seed validity and diversity. To validate this, we propose an approach that utilizes the N-gram model to mine SDRs from the Dongting dataset-one of the largest Linux kernel execution datasets available-as well as from execution traces collected on the fly during fuzzing. The resulting model is used to continuously augment the Choice Table of Syzkaller to improve its seed generation and demonstrably increases the Shannon Entropy of the Choice Table throughout fuzzing, reflecting more empirically-grounded choices in expanding syscall sequences into valid and diverse seeds. In addition, we introduce a Random Walk strategy that instructs Syzkaller to construct seeds in a bidirectional manner to further diversify the generated seeds. We implement our approach in a prototype, Psyzkaller, built on top of Syzkaller. Experiments on three representative Linux kernel versions show that Psyzkaller improves Syzkaller's code coverage by 4.6%-7.0% in 48-hour fuzzing, while triggering 110.4%-187.2% more crashes. Moreover, our investigation shows that Psyzkaller discovered eight previously unknown kernel vulnerabilities, compared to only one found by Syzkaller.
academic

Psyzkaller: Обучение на исторических и оперативных данных выполнения для более умного генерирования начальных значений при фаззинге ядра ОС

Основная информация

  • ID статьи: 2510.08918
  • Название: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • Авторы: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • Классификация: cs.CR (Криптография и безопасность)
  • Дата публикации: 13 октября 2025
  • Ссылка на статью: https://arxiv.org/abs/2510.08918v1

Аннотация

Фаззинг стал краеугольным камнем технологии обнаружения уязвимостей ядра операционной системы и повышения безопасности. Однако передовые фаззеры ядра, включая де-факто стандарт Syzkaller, испытывают трудности при генерировании эффективных последовательностей системных вызовов, которые соответствуют неявным зависимостям между системными вызовами (SDRs). Следовательно, многие сгенерированные начальные значения либо не проходят проверку ядра, либо не могут глубоко проникнуть в пути выполнения, что приводит к значительной неэффективности. В данной работе предполагается, что SDRs могут быть эффективно изучены из исторических и текущих данных выполнения ядра, и что включение этих изученных отношений в фаззинг может значительно повысить валидность и разнообразие начальных значений. Для проверки этого предположения авторы предлагают метод, использующий N-граммовую модель для извлечения SDRs из набора данных DongTing (одного из крупнейших наборов данных выполнения ядра Linux) и траекторий выполнения, собираемых в реальном времени во время фаззинга.

Исследовательский контекст и мотивация

Определение проблемы

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

  1. Сложность идентификации зависимостей системных вызовов (SDRs): Многие сгенерированные последовательности системных вызовов (SCS) являются недействительными из-за нарушения SDRs
  2. Неэффективность генерирования начальных значений: Недействительные тестовые случаи преждевременно завершаются, внося минимальный вклад в исследование кода
  3. Сложность достижения глубоких путей выполнения: Отсутствие понимания семантических ограничений между системными вызовами

Ограничения существующих методов

  • Syzkaller: Использует шаблоны системных вызовов для обеспечения синтаксической корректности, но не может захватить более глубокие зависимости
  • Методы статического анализа: Высокие вычислительные затраты, сложность развертывания в среде высокопроизводительного фаззинга
  • Существующие методы машинного обучения: Ограниченные данные, доступные во время фаззинга, не могут полностью захватить SDRs

Исследовательская мотивация

Авторы предлагают новый подход к изучению SDRs непосредственно из траекторий выполнения ядра, сочетая широкое покрытие исторических данных с адаптивностью онлайн-обучения.

Основные вклады

  1. Предложена новая стратегия изучения SDRs путем объединения исторических и оперативных данных выполнения ядра, сочетающая широкое покрытие и адаптивность к версиям ядра
  2. Разработан прототип Psyzkaller, интегрирующий обучение SDRs на основе Bigram и стратегию RandomWalk в рабочий процесс Syzkaller
  3. Использован предварительный тренинг на крупнейшем историческом наборе данных выполнения ядра Linux (DongTing) для модели Bigram
  4. Подтверждена эффективность на трех репрезентативных версиях ядра Linux, демонстрирующая превосходство в покрытии ветвей и обнаружении уязвимостей

Подробное описание метода

Определение задачи

Входные данные: Исторический набор данных выполнения ядра C и результаты фаззинга в реальном времени Выходные данные: Улучшенная таблица выбора для направления более эффективного генерирования последовательностей системных вызовов Цель: Повышение валидности начальных значений, разнообразия и способности обнаружения уязвимостей

Архитектура модели

1. Выбор N-граммовой модели

Используется модель Bigram (N=2) для изучения SDRs на основе следующих соображений:

  • Эффективность данных: N-граммовые модели показывают лучшие результаты на небольших наборах данных по сравнению с моделями DNN
  • Вычислительная эффективность: Минимальные вычислительные затраты на обновление матрицы Bigram
  • Интерпретируемость: SDRs представлены как вероятности переходов между системными вызовами, легко понимаются и проверяются

Расчет вероятности Bigram:

P(wj|wi) = count(wiwj) / count(wi)

2. Матрица вероятностей отношений (RPM)

Построение матрицы RPM, где RPM[i]j записывает вероятность вызова системного вызова wj сразу после wi.

Алгоритм 1: LearnSDR

Входные данные: C (корпус последовательностей системных вызовов), CallNum (общее количество системных вызовов в ядре)
Выходные данные: M (N-граммовая модель, изученная из C)

1. Инициализировать матрицу M и массив счетчиков Count
2. Для каждой последовательности sc в корпусе C:
   - Подсчитать последовательно появляющиеся пары системных вызовов
   - Обновить статистику счетчиков
3. Вычислить вероятности переходов: M[i][j] = M[i][j] / Count[i]

3. Выбор источников данных

Объединение двух типов данных выполнения:

  • Исторические данные: Набор данных DongTing (85 ГБ, 18 966 последовательностей системных вызовов)
    • Нормальные последовательности: 6 850 (из тестовых наборов LTP, Kselftests и т.д.)
    • Аномальные последовательности: 12 116 (из отчетов о сбоях Syzbot)
  • Данные в реальном времени: Траектории выполнения, собираемые во время фаззинга

4. Интеграция улучшенной таблицы выбора

Построение улучшенной таблицы выбора (ACT):

ACT[i][j] = CTst[i][j] + CTdyn[i][j] + DTN[i][j] + CorpusN[i][j]

где:

  • CTst: Статические значения (знания разработчика)
  • CTdyn: Динамические значения (обратная связь ядра)
  • DTN: RPM, обученная на исторических данных
  • CorpusN: RPM, обученная на данных в реальном времени

5. Стратегия RandomWalk

Введение двусторонней стратегии расширения для увеличения разнообразия начальных значений:

Алгоритм 2: GenRandomWalk

  • Дана частичная последовательность w1·w2...wk
  • Возможно прямое расширение: выбрать w такой, что ACT[wk]w > 0
  • Возможно обратное расширение: выбрать w такой, что ACT[w]w1 > 0
  • Случайно выбрать направление расширения (вероятность каждого 0.5)

Технические инновации

  1. Двусточный синтез данных: Первая систематическая интеграция крупномасштабных исторических данных и онлайн-обучения
  2. Повышение энтропии Шеннона: Значительное повышение энтропии Шеннона таблицы выбора (с 1.50 до 3.30-3.50 бит) благодаря изучению SDRs
  3. Стратегия балансировки весов: Сбалансированное влияние нормальных и аномальных траекторий через настраиваемые веса
  4. Двусторонее генерирование начальных значений: Стратегия RandomWalk преодолевает ограничения традиционного одностороннего расширения

Экспериментальная установка

Наборы данных

  • Набор данных DongTing: 85 ГБ, охватывающий версии Linux 4.13-5.17
  • Тестируемые версии ядра: Linux 5.19, 6.1, 6.12
  • Предварительная обработка: Использование инструмента trace2syz для преобразования в формат Syzkaller

Метрики оценки

  • Покрытие ветвей: Измерение глубины исследования кода
  • Количество сбоев: Оценка способности обнаружения уязвимостей
  • Энтропия Шеннона: Количественная оценка разнообразия таблицы выбора
  • Обнаружение уязвимостей: Количество вновь обнаруженных неизвестных уязвимостей

Методы сравнения

  • Syzkaller: Базовый метод
  • Healer: Передовой фаззер ядра с изучением SDRs

Детали реализации

  • Продолжительность экспериментов: 48 часов для каждого запуска, усреднение по 3 повторениям
  • Соотношение весов: Тестирование трех соотношений весов нормальных/аномальных траекторий 1:1, 1:2, 2:1
  • Аппаратная среда: Использование одного сервера для всех версий ядра для обеспечения справедливости

Результаты экспериментов

Основные результаты

Повышение покрытия ветвей

  • По сравнению с Syzkaller: Повышение на 4.6%-7.0%
  • По сравнению с Healer: Значительное превосходство над повышением Healer на 0.4%-4.0%

Способность обнаружения сбоев

  • Увеличение количества сбоев: 110.4%-187.2% (1 206 против 516)
  • Генерирование PoC: 355 действительных PoC (Syzkaller только 70)

Обнаружение уязвимостей

  • Обнаружение новых уязвимостей: 8 неизвестных уязвимостей (Syzkaller только 1)
  • Типы уязвимостей: Главным образом связанные с дедлоками (6/8)

Абляционные эксперименты

Влияние соотношения весов (RQ1)

  • Оптимальная конфигурация: Соотношение весов 1:1 показывает лучшие результаты на всех версиях ядра
  • Эффект балансировки: Равные веса уравновешивают исследование путей и целевое обнаружение уязвимостей

Эффект комбинации стратегий (RQ2)

  • Лучшая комбинация: Включение всех стратегий (C+R+D) достигает оптимальной производительности
  • Отдельные вклады:
    • Онлайн-обучение (C): Более высокое покрытие ветвей
    • Исторические данные (D): Больше обнаружений сбоев
    • RandomWalk (R): Повышенное разнообразие начальных значений

Анализ случаев

Уязвимость тройного дедлока

Обнаруженная типичная уязвимость включает три потока, конкурирующих за блокировку ресурса:

  • Поток A: blk_mq_freeze_queue → loop_reconfigure_limits
  • Потоки B и C: Формирование сложных отношений зависимостей блокировок
  • Условие срабатывания: Требуется точная последовательность системных вызовов

Обнаружение таких сложных уязвимостей демонстрирует эффективность изучения SDRs в Psyzkaller.

Связанные работы

Генерирование спецификаций системных вызовов

  • DIFUZE: Статический анализ для вывода описаний интерфейсов устройств
  • SyzGen: Объединение динамического инструментирования и статического анализа
  • SyzDescribe: Анализ приоритетов модулей ядра

Извлечение SDRs

  • HFL: Гибридный фаззинг в сочетании с символическим выполнением
  • Healer: Итеративное удаление системных вызовов для оценки влияния на покрытие
  • MOCK: Нейросетевая языковая модель для направления мутации начальных значений
  • ACTOR: Изучение зависимостей системных вызовов на общих объектах ядра

Преимущества данной работы

По сравнению с существующими методами, данная работа обеспечивает:

  • Лучшую интерпретируемость (представление вероятностей переходов)
  • Более высокую вычислительную эффективность (легкие матричные операции)
  • Тонкое управление (относительное влияние нормального/аномального выполнения)

Заключение и обсуждение

Основные выводы

  1. Эффективность изучения SDRs: Изучение SDRs из исторических и оперативных данных значительно повышает эффективность фаззинга
  2. Преимущества синтеза данных: Стратегия, объединяющая историческую широту и оперативную адаптивность, является оптимальной
  3. Проверка практичности: Демонстрация значительного повышения производительности на реальных версиях ядра

Ограничения

  1. Ограничения семантических зависимостей: Последовательные системные вызовы, захватываемые Bigram, не всегда соответствуют истинным семантическим зависимостям
  2. Эволюция версий ядра: Эффективность исторических данных может снизиться на новых версиях ядра
  3. Вычислительная сложность: Сложность N-граммов растет экспоненциально с увеличением N

Будущие направления

  1. Улучшение семантического понимания: Интеграция исходного кода системных вызовов и документации для извлечения более точных SDRs
  2. Расширение области применения: Применение изученных SDRs к мутации начальных значений, планированию и другим этапам
  3. Интеграция обучения с подкреплением: Объединение с стратегиями фаззинга на основе обучения с подкреплением

Глубокая оценка

Преимущества

  1. Высокая инновационность метода: Первая систематическая интеграция крупномасштабных исторических данных и онлайн-обучения
  2. Полные и всесторонние эксперименты: Три версии ядра, множество конфигураций, подробные абляционные эксперименты
  3. Высокая практическая ценность: Обнаружение 8 новых уязвимостей, демонстрирующее реальную ценность безопасности
  4. Прочная теоретическая база: Использование энтропии Шеннона для количественной оценки улучшений

Недостатки

  1. Ограничения метода: Зависимость от последовательных отношений системных вызовов, возможность пропуска дальних зависимостей
  2. Зависимость от данных: Сильная зависимость от качества набора данных DongTing
  3. Проблемы масштабируемости: Размер матрицы растет квадратично с количеством системных вызовов

Влияние

  1. Академический вклад: Предоставление нового метода, управляемого данными, для области фаззинга ядра
  2. Практическая ценность: Может быть непосредственно интегрирован в существующий рабочий процесс Syzkaller
  3. Воспроизводимость: Основан на открытых инструментах и общедоступных наборах данных

Применимые сценарии

  • Тестирование безопасности ядра Linux
  • Оптимизация генерирования последовательностей системных вызовов
  • Улучшение инструментов фаззинга ядра
  • Исследования безопасности операционных систем

Библиография

Статья ссылается на 44 связанные работы, охватывающие:

  • Инструменты фаззинга ядра (Syzkaller, Healer и т.д.)
  • Методы машинного обучения (N-граммы, Word2Vec, Transformers)
  • Наборы данных выполнения ядра (DongTing, ADFA-LD и т.д.)
  • Методы извлечения зависимостей системных вызовов

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