FRET-LibAFL/fuzzers/FRET/ARCH.md

FRET Fuzzer Software Architecture

FRET (FreeRTOS Real-Time) is a sophisticated greybox fuzzer designed for testing real-time operating systems, specifically FreeRTOS kernels. It leverages QEMU system-mode emulation to provide binary-only coverage-guided fuzzing with advanced system state tracking and real-time analysis capabilities.

High-Level Architecture

The FRET fuzzer follows a multi-layered architecture with the following key components:

┌─────────────────────────────────────────────────────────────────┐
│                        FRET Fuzzer                             │
├─────────────────────────────────────────────────────────────────┤
│ CLI Interface (cli.rs) & Configuration (config.rs)             │
├─────────────────────────────────────────────────────────────────┤
│ Main Fuzzer Loop (fuzzer.rs)                                   │
│ ├── LibAFL Framework Integration                               │
│ ├── QEMU System-Mode Emulation                                 │
│ └── Target Binary Loading & Symbol Resolution                  │
├─────────────────────────────────────────────────────────────────┤
│ System State Tracking (systemstate/)                           │
│ ├── Target OS Abstraction (target_os/)                        │
│ │   └── FreeRTOS Implementation (freertos/)                   │
│ ├── State Transition Graph (stg.rs)                           │
│ ├── System State Feedbacks (feedbacks.rs)                     │
│ ├── Custom Mutation Strategies (mutational.rs)                │
│ └── Specialized Schedulers (schedulers.rs)                    │
├─────────────────────────────────────────────────────────────────┤
│ Timing Analysis (time/)                                         │
│ ├── Clock Management (clock.rs)                               │
│ ├── QEMU State Management (qemustate.rs)                      │
│ └── Basic Worst-Case Heuristics (worst.rs)             │
└─────────────────────────────────────────────────────────────────┘

Core Components

1. Main Fuzzer Engine (fuzzer.rs)

The main fuzzer engine coordinates all components and implements the core fuzzing loop:

• QEMU Integration: Uses LibAFL's QEMU integration for system-mode emulation
• Symbol Resolution: Resolves kernel symbols and sets up memory mappings
• Input Generation: Manages interrupt timing and system inputs
• Corpus Management: Maintains test cases with execution time metadata
• Feedback Orchestration: Coordinates multiple feedback mechanisms

2. System State Tracking (systemstate/)

This is the heart of FRET's innovation - tracking and analyzing real-time system states:

2.1 Target OS Abstraction (target_os/)

Provides a generic interface for different RTOS implementations:

trait TargetSystem {
    type State: SystemState;
    type TCB: TaskControlBlock;  
    type TraceData: SystemTraceData;
}

2.2 FreeRTOS Implementation (target_os/freertos/)

• QEMU Module (qemu_module.rs): Hooks into QEMU execution to capture system states
• State Capture: Records task control blocks, ready queues, delay lists
• Symbol Resolution (config.rs): Maps kernel symbols to addresses
• Post-processing: Converts raw states into refined system representations

2.3 System State Representation

Hierarchical Data Structures:

• RawFreeRTOSSystemState: Raw data captured from QEMU at specific instants
• FreeRTOSSystemState: Refined system state without execution context
• ExecInterval: Execution intervals between system state changes
• AtomicBasicBlock: Single-entry multiple-exit code regions
• RTOSJob: Complete task execution with timing information
• RTOSTask: Generalized task representation

3. State Transition Graph (STG) (stg.rs)

The STG is a key innovation that models system execution as a directed graph:

• Nodes: Represent system states with associated atomic basic blocks
• Edges: Represent state transitions with execution timing
• Path Analysis: Tracks execution paths and identifies worst-case scenarios
• Scheduling Analysis: Models task scheduling decisions and preemption

STG Features:

• State deduplication using hash-based node identification
• Edge weight tracking for timing analysis
• Path-based coverage feedback
• Integration with corpus scheduling

4. Feedback Mechanisms (feedbacks.rs)

FRET implements multiple specialized feedback mechanisms:

• STG-based Feedback: Uses state transition graph coverage
• Timing Feedback: Focuses on worst-case execution time
• System State Feedback: Tracks unique system configurations
• Traditional Coverage: Standard edge coverage for comparison

5. Custom Mutation Strategies (mutational.rs)

Specialized mutation operators for real-time systems:

• Interrupt Timing Mutation: Modifies interrupt arrival times
• STG-guided Mutation: Uses state transition graph to guide mutations
• System State Mutation: Targets specific system configurations

6. Timing Analysis (time/)

Comprehensive timing analysis for real-time systems:

• Clock Management: Tracks QEMU instruction counts and timing
• WCET Analysis: Identifies worst-case execution times
• Response Time Analysis: Measures task response times
• Temporal Schedulers: Prioritize inputs based on timing properties

Information Flow

System State Capture Flow

1. Symbol Resolution (target_os::freertos::config.rs):

   • Resolves kernel symbols (task control blocks, queues, etc.)
   • Creates address ranges for API functions and ISR handlers

2. Runtime Capture (target_os::freertos::qemu_module::FreeRTOSSystemStateHelper):

   • Hooks QEMU execution at critical points (syscalls, interrupts)
   • Captures RawFreeRTOSSystemState snapshots
   • Records memory reads and execution intervals

3. State Processing:

   • Converts raw states to FreeRTOSSystemState (refined representation)
   • Generates ExecInterval objects for execution flow
   • Identifies AtomicBasicBlock regions

4. STG Construction (stg::StgFeedback):

   • Core Classes:
     • STGFeedbackState<SYS>: Maintains the state transition graph and metadata
     • STGNode<SYS>: Represents graph nodes containing system state hash and atomic basic block
     • STGEdge: Represents graph edges with execution timing and transition information
     • StgFeedback<SYS>: Main feedback mechanism that builds and updates the STG
   • Process:
     • Analyzes ExecInterval sequences from trace data
     • Creates STGNode instances for unique system state + ABB combinations
     • Adds STGEdge instances for state transitions with timing weights
     • Uses HashMap<u64, NodeIndex> for efficient node deduplication
     • Integrates with DiGraph<STGNode<SYS>, STGEdge> from petgraph library

5. Feedback Integration:

   • Timing-Based Feedbacks:
     • ClockTimeFeedback<SYS>: Tracks QEMU instruction count increases
     • QemuClockIncreaseFeedback<SYS>: Monitors clock progression patterns
     • ExecTimeIncFeedback<SYS>: Focuses on execution time improvements
   • Corpus Schedulers:
     • TimeMaximizerCorpusScheduler<CS, O>: Prioritizes inputs with longer execution times
     • TimeStateMaximizerCorpusScheduler<CS, O, SYS>: Combines timing and system state coverage
     • LongestTraceScheduler<CS, SYS>: Schedules based on trace length metrics
     • GenerationScheduler<S>: Implements generation-based scheduling strategies
   • Mutation Strategies:
     • InterruptShiftStage<E, EM, Z, SYS>: Mutates interrupt timing sequences
     • STGSnippetStage<E, EM, Z, SYS>: Uses STG paths to guide mutation decisions
   • Integration Process:
     • Multiple feedback mechanisms run in parallel during corpus evaluation
     • StgFeedback updates the state transition graph with new paths
     • Timing feedbacks identify inputs that trigger longer execution paths
     • Schedulers use combined metrics to prioritize corpus entries for mutation

Execution Flow

1. Initialization:

   • Load target kernel binary
   • Resolve symbols and setup memory mappings
   • Initialize QEMU system-mode emulation
   • Setup hooks for system state capture

2. Fuzzing Loop:

   • Generate/mutate input (interrupt timing sequence)
   • Execute target in QEMU with system state tracking
   • Capture execution trace and timing information
   • Build/update state transition graph
   • Evaluate feedback mechanisms
   • Update corpus and select next input

3. Runtime Monitoring and Analysis:

   • Display fuzzing progress, coverage metrics, and timing statistics
   • Maintain and prioritize test cases based on coverage and timing feedback

4. Output Generation

   • Time Dumps (--dump-times, -t): Export execution timing data for offline analysis
   • Worst-Case Dumps (--dump-cases, -a): Save inputs that trigger worst-case execution scenarios
   • Trace Dumps (--dump-traces, -r): Export detailed execution traces including system state transitions
   • Graph Dumps (--dump-graph, -g): Output state transition graphs in DOT format for visualization
   • Task-Specific Analysis (--select-task, -s): Focus measurements on specific RTOS tasks
   • Configurable Output Prefix (--dump-name, -n): Set custom prefixes for all output files