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: Aprendizaje de Datos de Ejecución Históricos y en Tiempo Real para Generación Inteligente de Semillas en Fuzzing de Núcleo del SO

Información Básica

  • ID del Artículo: 2510.08918
  • Título: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • Autores: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • Clasificación: cs.CR (Criptografía y Seguridad)
  • Fecha de Publicación: 13 de octubre de 2025
  • Enlace del Artículo: https://arxiv.org/abs/2510.08918v1

Resumen

El fuzzing se ha convertido en una tecnología fundamental para descubrir vulnerabilidades en núcleos de sistemas operativos y mejorar la seguridad. Sin embargo, los fuzadores de núcleo más avanzados, incluyendo el estándar de facto Syzkaller, enfrentan dificultades para generar secuencias de llamadas al sistema efectivas que respeten las relaciones de dependencia de llamadas al sistema implícitas (SDRs). Por consiguiente, muchas semillas generadas fallan en la validación del núcleo o no pueden ejecutar rutas profundas, resultando en ineficiencia significativa. Este artículo postula que las SDRs pueden aprenderse efectivamente de datos históricos y actuales de ejecución del núcleo, y que incorporar estas relaciones aprendidas en el fuzzing puede mejorar significativamente la validez y diversidad de las semillas. Para verificar esto, los autores proponen un método que utiliza modelos N-gram para extraer SDRs del conjunto de datos DongTing (uno de los mayores conjuntos de datos de ejecución del núcleo Linux) así como de trazas de ejecución recopiladas en tiempo real durante el proceso de fuzzing.

Antecedentes de Investigación y Motivación

Definición del Problema

El núcleo del sistema operativo es un componente crítico de las plataformas informáticas modernas, y un compromiso de seguridad a nivel de núcleo permite a los atacantes obtener control total del sistema. Los problemas centrales enfrentados por los fuzadores de núcleo actuales son:

  1. Dificultad en la Identificación de Relaciones de Dependencia de Llamadas al Sistema (SDRs): Muchas secuencias de llamadas al sistema (SCS) generadas son inválidas por violar SDRs
  2. Baja Eficiencia en la Generación de Semillas: Los casos de prueba inválidos fallan prematuramente, contribuyendo poco a la exploración de código
  3. Dificultad para Alcanzar Rutas de Ejecución Profundas: Falta de comprensión de restricciones semánticas entre llamadas al sistema

Limitaciones de Métodos Existentes

  • Syzkaller: Utiliza plantillas de llamadas al sistema para forzar corrección sintáctica, pero no puede capturar dependencias más profundas
  • Métodos de Análisis Estático: Alto costo computacional, difícil de desplegar en entornos de fuzzing de alto rendimiento
  • Métodos de Aprendizaje Automático Existentes: Datos limitados disponibles durante fuzzing, incapaces de capturar SDRs de manera integral

Motivación de la Investigación

Los autores proponen una nueva perspectiva de aprender SDRs directamente de trazas de ejecución del núcleo, combinando la cobertura amplia de datos históricos con la adaptabilidad del aprendizaje en línea.

Contribuciones Principales

  1. Propone una nueva estrategia que combina aprendizaje de SDRs de datos históricos y de ejecución del núcleo en tiempo real, con cobertura amplia y adaptabilidad a versiones del núcleo
  2. Desarrolla el prototipo Psyzkaller, integrando aprendizaje de SDRs basado en Bigram y estrategia RandomWalk en el flujo de trabajo de Syzkaller
  3. Preentrenamiento del modelo Bigram utilizando el mayor conjunto de datos histórico de ejecución del núcleo Linux (DongTing)
  4. Valida la efectividad en tres versiones representativas del núcleo Linux, demostrando superioridad en cobertura de ramas y detección de vulnerabilidades

Explicación Detallada del Método

Definición de la Tarea

Entrada: Conjunto de datos histórico de ejecución del núcleo C y resultados de fuzzing en tiempo real Salida: Tabla de Elección mejorada para guiar la generación más efectiva de secuencias de llamadas al sistema Objetivo: Mejorar la validez de semillas, diversidad y capacidad de descubrimiento de vulnerabilidades

Arquitectura del Modelo

1. Selección del Modelo N-gram

Se adopta el modelo Bigram (N=2) para aprender SDRs, basado en las siguientes consideraciones:

  • Eficiencia de Datos: Los modelos N-gram funcionan mejor que los modelos DNN en conjuntos de datos pequeños
  • Eficiencia Computacional: El costo computacional de actualizar la matriz Bigram es mínimo
  • Interpretabilidad: Las SDRs se representan como probabilidades de transición entre llamadas al sistema, fáciles de entender e inspeccionar

Cálculo de Probabilidad Bigram:

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

2. Matriz de Probabilidad de Relaciones (RPM)

Se construye la matriz RPM, donde RPM[i]j registra la probabilidad de que la llamada al sistema wj se invoque inmediatamente después de wi.

Algoritmo 1: LearnSDR

Entrada: C (corpus de secuencias de llamadas al sistema), CallNum (número total de llamadas al sistema en el núcleo)
Salida: M (modelo N-gram aprendido de C)

1. Inicializar matriz M y matriz de conteo Count
2. Iterar sobre cada secuencia sc en el corpus C:
   - Contar pares de llamadas al sistema que aparecen consecutivamente
   - Actualizar estadísticas de conteo
3. Calcular probabilidades de transición: M[i][j] = M[i][j] / Count[i]

3. Selección de Fuentes de Datos

Se combinan dos clases de datos de ejecución:

  • Datos Históricos: Conjunto de datos DongTing (85GB, 18,966 secuencias de llamadas al sistema)
    • Secuencias normales: 6,850 (de suites de prueba LTP, Kselftests, etc.)
    • Secuencias anómalas: 12,116 (de reportes de fallos de Syzbot)
  • Datos en Tiempo Real: Trazas de ejecución recopiladas durante el proceso de fuzzing

4. Integración de Tabla de Elección Mejorada

Se construye la Tabla de Elección Mejorada (ACT):

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

Donde:

  • CTst: Valores estáticos (conocimiento del desarrollador)
  • CTdyn: Valores dinámicos (retroalimentación del núcleo)
  • DTN: RPM entrenada con datos históricos
  • CorpusN: RPM entrenada con datos en tiempo real

5. Estrategia RandomWalk

Se introduce una estrategia de extensión bidireccional para aumentar la diversidad de semillas:

Algoritmo 2: GenRandomWalk

  • Dada una secuencia parcial w1·w2...wk
  • Puede extenderse hacia adelante: seleccionar w tal que ACT[wk]w > 0
  • Puede extenderse hacia atrás: seleccionar w tal que ACT[w]w1 > 0
  • Seleccionar aleatoriamente la dirección de extensión (probabilidad 0.5 cada una)

Puntos de Innovación Técnica

  1. Fusión de Datos de Dos Fuentes: Primera integración sistemática de datos históricos a gran escala y aprendizaje en tiempo real
  2. Mejora de Entropía de Shannon: Aumento significativo de la entropía de Shannon de la Tabla de Elección (de 1.50 a 3.30-3.50 bits) mediante aprendizaje de SDRs
  3. Estrategia de Equilibrio de Pesos: Equilibrio configurable del impacto de trazas normales y anómalas
  4. Generación de Semillas Bidireccional: La estrategia RandomWalk supera las limitaciones de extensión unidireccional tradicional

Configuración Experimental

Conjuntos de Datos

  • Conjunto de Datos DongTing: 85GB, cubriendo versiones del núcleo Linux 4.13-5.17
  • Versiones del Núcleo de Prueba: Linux 5.19, 6.1, 6.12
  • Preprocesamiento: Uso de la herramienta trace2syz para convertir al formato Syzkaller

Métricas de Evaluación

  • Cobertura de Ramas: Mide la profundidad de exploración de código
  • Número de Fallos: Evalúa la capacidad de descubrimiento de vulnerabilidades
  • Entropía de Shannon: Cuantifica la diversidad de la Tabla de Elección
  • Descubrimiento de Vulnerabilidades: Número de vulnerabilidades desconocidas recién descubiertas

Métodos de Comparación

  • Syzkaller: Método de línea base
  • Healer: Fuzador de núcleo de aprendizaje de SDRs más avanzado

Detalles de Implementación

  • Duración de Experimentos: 48 horas por ejecución, promediadas en 3 repeticiones
  • Proporciones de Peso: Prueba de tres proporciones de peso de trazas normales/anómalas: 1:1, 1:2, 2:1
  • Entorno de Hardware: Se utiliza el mismo servidor para diferentes versiones del núcleo para garantizar equidad

Resultados Experimentales

Resultados Principales

Mejora en Cobertura de Ramas

  • Comparado con Syzkaller: Mejora de 4.6%-7.0%
  • Comparado con Healer: Significativamente superior a la mejora de 0.4%-4.0% de Healer

Capacidad de Detección de Fallos

  • Aumento en Número de Fallos: 110.4%-187.2% (1,206 vs 516)
  • Generación de PoC: 355 PoC válidos (Syzkaller solo 70)

Descubrimiento de Vulnerabilidades

  • Vulnerabilidades Nuevas Descubiertas: 8 vulnerabilidades desconocidas (Syzkaller solo 1)
  • Tipos de Vulnerabilidades: Principalmente relacionadas con bloqueos (6/8)

Experimentos de Ablación

Impacto de Proporciones de Peso (RQ1)

  • Configuración Óptima: Proporción de peso 1:1 muestra el mejor rendimiento en todas las versiones del núcleo
  • Efecto de Equilibrio: El peso igual equilibra la exploración de rutas y la orientación específica de vulnerabilidades

Efecto de Combinación de Estrategias (RQ2)

  • Mejor Combinación: Habilitar todas las estrategias (C+R+D) logra el mejor rendimiento
  • Contribuciones Individuales:
    • Aprendizaje en Tiempo Real (C): Mayor cobertura de ramas
    • Datos Históricos (D): Más detección de fallos
    • RandomWalk (R): Mejora la diversidad de semillas

Análisis de Casos

Vulnerabilidad de Bloqueo Triple

Una vulnerabilidad típica descubierta implica tres hilos compitiendo por bloqueos de recursos:

  • Thread A: blk_mq_freeze_queue → loop_reconfigure_limits
  • Thread B y C: Forman relaciones complejas de dependencia de bloqueos
  • Condición de Disparo: Requiere una secuencia precisa de llamadas al sistema

El descubrimiento de este tipo de vulnerabilidades complejas demuestra la efectividad del aprendizaje de SDRs de Psyzkaller.

Trabajo Relacionado

Generación de Especificaciones de Llamadas al Sistema

  • DIFUZE: Análisis estático para inferir descripciones de interfaces de dispositivos
  • SyzGen: Combinación de instrumentación dinámica y análisis estático
  • SyzDescribe: Análisis de prioridades de módulos del núcleo

Extracción de SDR

  • HFL: Fuzzing híbrido combinado con ejecución simbólica
  • Healer: Eliminación iterativa de llamadas al sistema evaluando impacto en cobertura
  • MOCK: Modelo de lenguaje neuronal guiando mutación de semillas
  • ACTOR: Aprendizaje de dependencias de llamadas al sistema en objetos del núcleo compartidos

Ventajas de Este Artículo

Comparado con métodos existentes, este artículo proporciona:

  • Mayor interpretabilidad (representación de probabilidades de transición)
  • Mayor eficiencia computacional (operaciones de matriz ligeras)
  • Control de grano fino (impacto relativo de ejecuciones normales/anómalas)

Conclusiones y Discusión

Conclusiones Principales

  1. Efectividad del Aprendizaje de SDRs: El aprendizaje de SDRs de datos históricos y en tiempo real mejora significativamente la efectividad del fuzzing
  2. Ventajas de Fusión de Datos: La estrategia que combina amplitud histórica y adaptabilidad en tiempo real es óptima
  3. Validación de Practicidad: Demuestra mejoras de rendimiento significativas en versiones reales del núcleo

Limitaciones

  1. Limitaciones de Dependencia Semántica: Las relaciones de llamadas al sistema consecutivas capturadas por Bigram no siempre corresponden a dependencias semánticas verdaderas
  2. Evolución de Versiones del Núcleo: La validez de datos históricos en nuevas versiones del núcleo puede disminuir
  3. Complejidad Computacional: La complejidad de N-gram crece exponencialmente con N

Direcciones Futuras

  1. Comprensión Semántica Mejorada: Combinación con código fuente de llamadas al sistema y documentación para extraer SDRs más precisas
  2. Expansión del Rango de Aplicación: Aplicación de SDRs aprendidas a otras etapas como mutación de semillas y programación
  3. Integración de Aprendizaje Reforzado: Combinación con estrategias de fuzzing basadas en aprendizaje reforzado

Evaluación Profunda

Fortalezas

  1. Fuerte Innovación Metodológica: Primera integración sistemática de datos históricos a gran escala y aprendizaje en tiempo real
  2. Experimentación Completa y Exhaustiva: Tres versiones del núcleo, múltiples configuraciones, experimentos de ablación detallados
  3. Alto Valor Práctico: Descubrimiento de 8 nuevas vulnerabilidades, demostrando valor de seguridad real
  4. Base Teórica Sólida: Uso de entropía de Shannon para cuantificar mejoras

Deficiencias

  1. Limitaciones Metodológicas: Dependencia de relaciones de llamadas al sistema consecutivas, posible pérdida de dependencias de larga distancia
  2. Dependencia de Datos: Dependencia severa de la calidad del conjunto de datos DongTing
  3. Problemas de Escalabilidad: El tamaño de la matriz crece cuadráticamente con el número de llamadas al sistema

Impacto

  1. Contribución Académica: Proporciona nuevo método impulsado por datos para el campo del fuzzing de núcleo
  2. Valor Práctico: Puede integrarse directamente en el flujo de trabajo existente de Syzkaller
  3. Reproducibilidad: Basado en herramientas de código abierto y conjuntos de datos públicos

Escenarios Aplicables

  • Pruebas de seguridad del núcleo Linux
  • Optimización de generación de secuencias de llamadas al sistema
  • Mejora de herramientas de fuzzing de núcleo
  • Investigación de seguridad del sistema operativo

Referencias

El artículo cita 44 referencias relacionadas, abarcando:

  • Herramientas de fuzzing de núcleo (Syzkaller, Healer, etc.)
  • Métodos de aprendizaje automático (N-gram, Word2Vec, Transformers)
  • Conjuntos de datos de ejecución del núcleo (DongTing, ADFA-LD, etc.)
  • Métodos de extracción de relaciones de dependencia de llamadas al sistema

Evaluación General: Este es un artículo de investigación de seguridad de sistemas de alta calidad que propone un método innovador impulsado por datos para resolver problemas clave en fuzzing de núcleo. El diseño experimental es riguroso, los resultados son convincentes y posee importante valor académico y práctico significativo.