Fuzzing stateful systems: noPac, Part 2: exhaustive enumeration

Here, we take a look at structured fuzzing of stateful systems, specifically using the example of a historical high-level semantic/logic bug (as opposed to low-level memory corruption bug) in Active Directory.

Disclaimer: Goal is understanding how to make software better and more secure through good testing. The bug is old, publicly known, and has been fixed/patched; I did not find it originally. All testing was performed in a dedicated lab environment on own hardware and software instances. If you run affected versions, please update. The accompanying code snippets are for educational purposes only (I’m not publishing a fully runnable version).

With that out of the way…

Re-framing the problem#

Part 1 approached the problem by random blind fuzzing. Here, I chose a different approach that probably fits this problem better: instead of random search, we generate all valid programs given a limit in maximum program length, while pruning the search space by dropping semantically duplicate programs to reduce the number of programs that need to be executed against the crash oracle (which is very expensive).

Components#

Some of the code is available in this git repository in the exhaustive-enumeration subfolder. However, it has purposefully been altered to not be able to execute against a real Active Directory instance and does not contain relevant executor or helper script implementations for doing so.

|-- main.rs         # Program entrypoint
|-- cli.rs          # Commandline argument parsing

|-- input.rs        # Input type definitions (program as list of actions)

|-- enumerator.rs   # Enumerator entry-point
|-- executor.rs     # Execute one input against the lab AD environment
                    #   and collect feedback/coverage (not included)

|-- error.rs        # Error types
|-- feedback.rs     # Feedback information (behavioral coverage map)
`-- stats.rs        # Statistics (number of execs, number of program prunes, ...)

Enumerating programs#

The input type definitions are essentially the same as in the previous part.

enumerator.rs implements the main component: a simple depth-first search among all syntactically valid and semantically unique programs, which is finite / bounded by the execution budget and parameter value space.

Operation Modes#

The whole tool has basically three modes of operation:

12
13
14
15
16
17
18
19
20
21
22

fn main() -> Result<(), error::Error> {
    let args = cli::Args::parse();
    println!("[+] Running with args {args:?}\n");
    if args.dry_run {
        enumerator::test_all_dry_run()
    } else if let Some(idx) = args.repro_testcase {
        enumerator::repro(idx)
    } else {
        enumerator::test_all()
    }
}

• with --dry-run it computes some statistics about the effectiveness of search space pruning, which is explained in detail in a later section.
• without an argument, it enumerates programs and executes them against a hardcoded lab AD instance (code for this is purposefully not part of the repository);
• with --repro-testcase <idx> it enumerates programs until the idx-th program is hit, which is then executed against the lab AD;

Whether to perform search space pruning or not maps to the following enum:

140
141
142
143
144
145
146
147

/// Whether the enumerator applies semantic search-space pruning or yields the
/// full finite search space (unpruned ground baseline, for statistics /
/// comparison).
#[derive(Debug, Clone, Copy)]
enum EnumMode {
    Prune,
    Baseline,
}

The entrypoint called from main constructs a new Iterator with default execution budget:

149
150
151
152
153
154
155
156

fn enumerate(mode: EnumMode) -> Enumerator {
    Enumerator {
        budget: Budget::default(),
        stack: vec![Program::default()],
        stats: Stats::default(),
        mode,
    }
}

The DFS state is held inside the Enumerator struct:

158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

struct Enumerator {
    budget: Budget,
    /// Pending partial programs (DFS pre-order stack).
    stack: Vec<Program>,
    stats: Stats,
    mode: EnumMode,
}

impl Iterator for Enumerator {
    type Item = Program;

    /// Iterates over all semantically relevant programs.
    /// Search space pruning happens in two places: ...
    fn next(&mut self) -> Option<Program> {
        while let Some(pgm) = self.stack.pop() {
            // ... properties on program prefixes (partials): at child expansion
            // for properties easily expressible/depending only on a partial
            // program / call prefix (as part of depth-first pre-order traversal
            // of search space tree).
            let children = successors(
                &pgm,
                &self.budget,
                self.mode,
                &mut self.stats.pruned,
            );
            self.stack.extend(children.into_iter().rev());

            // ... properties on whole programs: filter for the remaining
            // properties.
            if let EnumMode::Prune = self.mode
                && let Some(reason) = prune_reason_whole(&pgm)
            {
                self.stats.pruned.tally(reason);
                continue;
            }

            return Some(pgm);
        }
        None
    }
}

Search space pruning#

Programs are built call-by-call. For each next call to choose, all ActionKinds are iterated. Then for each parameter, all possible values (either from the existing environment, or from the (finite) space of possible type-directed leaf-values) are iterated.

The environment is by-design constructed to avoid unnecessary semantic duplicates regarding both alpha-renaming of variables and leaf values.

For pruning based on the call sequence, the tool implements pruning strategies that fall into the following two categories:

• pruning based on properties that can be expressed depending only on partial programs / call prefixes: at each program node, child/successor expansions are filtered. This prunes as early as possible, discarding whole subtrees of the space, and is therefore very effective. This is the preferred method, however, not all properties can (easily) be expressed in that way.
• pruning based on properties on whole programs: this applies filtering at the latest possible stage, when a full program has already been constructed. It is therefore not as effective as early search space pruning.

More specifically, the tool implements six strategies, whose effectiveness is tracked together with number of executed programs, and programs that produced the desired behavior, as part of a Stats struct:

1
2
3
4
5
6
7
8
9

/// Statistics.
#[derive(Default)]
pub struct Stats {
    pub pruned: PruneStats,
    /// Number of programs executed against the system under test.
    pub execs: usize,
    /// Number of programs that achieved crash/objective.
    pub crashes: usize,
}

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

// Search-space pruning rules/strategies; each maps 1:1 to a counter in
// `PruneStats`.
pub enum PruneReason {
    // Partial-program / prefix rules (prune a whole search-space subtree).
    AuthOracleTerminal,
    PartialOrderReductionWriteBatch,
    DeadStoreBatch,
    RedundantStore,
    // Whole-program rules (prune individual programs).
    TrailingDeadWrite,
    UnusedRet,
}

#[derive(Default)]
pub struct PruneStats {
    /// Subtrees pruned because they extend the crash oracle.
    pub auth_oracle_terminal: usize,
    /// Subtrees pruned by partial-order reduction of commutative write-batches.
    pub partial_order_reduction_write_batch: usize,
    /// Subtrees pruned by dead-store elimination within a write-batch.
    pub dead_store_batch: usize,
    /// Subtrees pruned by redundant-store (same value) elimination.
    pub redundant_store_batch: usize,
    /// Whole programs pruned for trailing writes which are never read.
    pub trailing_dead_write: usize,
    /// Whole programs pruned for producing a ref handle that is never consumed.
    pub unused_ret: usize,
}

The specific counters map to the following strategy implementations:

• auth_oracle_terminal:

  src/enumerator.rs

  206 207 208 209 210 211 212

  if let EnumMode::Prune = mode && let Some(c) = pgm.calls.last() && c.kind == ActionKind::AuthorizationOracle { prune_stats.tally(PruneReason::AuthOracleTerminal); return Vec::new(); }

• partial_order_reduction_write_batch: identify the previous write (inside the current write-batch), if the written attributes are not sorted (with respect to an arbitrary but fixed ordering), the current call is unnecessary.

  src/enumerator.rs

  419 420 421 422 423 424 425 426 427 428 429 430 431 432

  fn prune_reason_partial(cand: &Program) -> Option<PruneReason> { // All the filters here only apply when the last call was a write. let last = cand.calls.len() - 1; let (a, v) = write_effect(cand, &cand.calls[last])?; if let Some(b) = cand.calls[..last] .iter() .rev() .take_while(|c| !c.kind.is_read_barrier()) .find_map(|c| write_attr(cand, c)) && a < b { return Some(PruneReason::PartialOrderReductionWriteBatch); }

• dead_store_batch: if there is a previous write inside the current write-batch to the same attribute, that call was unnecessary (last-write-wins).

  src/enumerator.rs

  434 435 436 437 438 439 440 441

  if cand.calls[..last] .iter() .rev() .take_while(|c| !c.kind.is_read_barrier()) .any(|c| write_attr(cand, c).is_some_and(|b| b == a)) { return Some(PruneReason::DeadStoreBatch); }

• redundant_store_batch: identify the previous write (even across read-boundaries) to the same attribute, if it writes the same value, the current call is unnecessary.

  src/enumerator.rs

  443 444 445 446 447 448 449 450 451 452

  let prev = cand.calls[..last].iter().rev().find_map(|c| { match write_effect(cand, c) { Some((b, w)) if a == b => Some(w), _ => None, } }); if prev == Some(v) { return Some(PruneReason::RedundantStore); }

• trailing_dead_write: on the whole program, identify the last read; any writes after that are unnecessary since their effect is never observed. Note that this only works incidentally here, since all resource-producing calls do not have side-effects (writes), and vice-versa. Note also that the read is identified regardless of the read attribute; it would be another improvement to compare per-attribute reads/writes.

  src/enumerator.rs

  457 458 459 460 461 462 463 464 465 466 467 468

  fn prune_reason_whole(pgm: &Program) -> Option<PruneReason> { let after_last_read = pgm .calls .iter() .rposition(|c| c.kind.is_read_barrier()) .map_or(0, |i| i + 1); if pgm.calls[after_last_read..] .iter() .any(|c| c.kind.is_write()) { return Some(PruneReason::TrailingDeadWrite); }

• unused_ret: on the whole program, check if any return value is unused.

  src/enumerator.rs

  470 471 472 473 474 475 476

  for (i, c) in pgm.calls.iter().enumerate() { if let Some(r) = c.ret && !pgm.calls[i + 1..].iter().any(|c2| c2.params.contains(&r)) { return Some(PruneReason::UnusedRet); } }

All these strategies are relatively general and independent of the specific problem domain; they do not require much a-priori knowledge of the bug.

With smarter pruning, even more could be expressed as prefix-dependent properties, allowing more early pruning; but the current code strikes a good balance between being understandable and easy to express, and the resulting effectiveness, imho. Especially since overall the oracle execution times dominate compute time. Nonetheless, in general, with exponentially (in program length) large subtrees, (especially early) pruning is important.

Feedback#

Similar to part 1, feedback is a rudimentary behavioral coverage map. It is not really needed here since programs are enumerated in the same order exhaustively, regardless of any runtime dynamic feedback. But it can nonetheless be used to potentially classify different programs by the response of the system under test.

5
6
7
8

/// Behavioral feedback signature / fuzzy semantic coverage of system-under-test
/// responses.
#[derive(Debug, Default)]
pub struct Feedback(pub HashSet<ActionOutcome>);

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/// Result of a single action: which action ran, its control-flow status, and a
/// behavioral signature used to extend the coverage map.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct ActionOutcome {
    pub kind: ActionKind,
    pub status: Status,
    pub sig: String,
}

/// Control-flow status of an executed action.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[allow(dead_code)]
pub enum Status {
    Continue,
    Abort,
    Crash,
}

Example runs#

Now we can test each operation mode of the tool.

Running through all 6-call programs#

Exhaustive enumeration of all 6-call programs triggers the desired behavior.

Reproducing a single program#

This can also be reproduced directly, by supplying the index of the program in the enumeration:

./exhaustive-enumeration$ cargo run -- --repro-testcase <idx>
[+] Running with args Args { repro_testcase: Some(<idx>), dry_run: false }

[+] Running program:
...

[+] RunResult { exit: Crash, cov: Feedback( ... ) }

All programs before it have to be generated and are simply discarded. I also thought about implementing indexable generation (bijection mapping between a number and a structured representation), but found this to be not easily doable. The approach would be similar to e.g. Rust’s arbitrary or QuickCheck, but surjective and injective; in arbitrary, several possible byte strings can map to the same value; e.g. booleans are generated by consuming a full random byte, and making the decision based on one bit only.

There are ways of generating syntactically valid programs (or more generally algebraic datatypes) in an indexable way like with “Feat: functional enumeration of algebraic types”.¹ However, extending that with variously-expressed semantic properties (the whole point of search space pruning) re-introduces gaps and breaks the bijection again. Overall, I found simple DFS with manually expressed (arbitrary) properties the easier way here.

Quantifying search space pruning effectiveness#

In hindsight search space pruning is absolutely essential, but at first I just didn’t think of it. To underline how hopeless naive blind fuzzing without any search space reduction (or stronger guiding feedback) is, here are some numbers: (Since enumeration/generation is completely independent of dynamic runtime feedback, these experiments can be run fully isolated without any real AD lab environment)

With execution budget of a maximum of 6 calls per program, we get these numbers:

./exhaustive-enumeration$ cargo run --release -- --dry-run
[+] Running with args Args { repro_testcase: None, dry_run: true }

[+] Enumerating Baseline
[=] subtree-prunes          0 | program-prunes          0 | execs     756434 | crashes          0
...
[=] subtree-prunes          0 | program-prunes          0 | execs    4972299 | crashes          0
...

[+] Enumerating Prune
[=] subtree-prunes     131903 | program-prunes     531062 | execs       2217 | crashes          0
...
[=] subtree-prunes     587620 | program-prunes    1916769 | execs       3896 | crashes          0
...

[=] Final statistics comparison
[=] baseline: subtree-prunes          0 | program-prunes          0 | execs    5607403 | crashes          0
[=] pruned:   subtree-prunes     838800 | program-prunes    2499378 | execs       4051 | crashes          0

================================================================================
[=] Summarized impact of search space pruning on number of executions / oracle invocations
[=] would-be executed:      5607403 (no pruning) |       4051 (pruning)
[=] total pruned programs: 5603352 (99.928% of all programs)
[=] executions are reduced by a factor of 1384.20
========================================
[=] pruned by partial program properties 3103974 (55.395% of all prunes)
[=] pruned by whole-program properties   2499378 (44.605% of all prunes)

Modifying the default execution budget, and running it with an execution budget of 7 calls (the per-action-kind limits are unchanged), yields:

./exhaustive-enumeration$ cargo run --release -- --dry-run
[+] Running with args Args { repro_testcase: None, dry_run: true }

[+] Enumerating Baseline
[=] subtree-prunes          0 | program-prunes          0 | execs     715439 | crashes          0
...
[=] subtree-prunes          0 | program-prunes          0 | execs   55599831 | crashes          0
...

[+] Enumerating Prune
[=] subtree-prunes     229613 | program-prunes     722701 | execs        947 | crashes          0
...
[=] subtree-prunes    7372984 | program-prunes   14159623 | execs       4694 | crashes          0
...

[=] Final statistics comparison
[=] baseline: subtree-prunes          0 | program-prunes          0 | execs   56283595 | crashes          0
[=] pruned:   subtree-prunes    7712784 | program-prunes   14542458 | execs       4699 | crashes          0

================================================================================
[=] Summarized impact of search space pruning on number of executions / oracle invocations
[=] would-be executed:     56283595 (no pruning) |       4699 (pruning)
[=] total pruned programs: 56278896 (99.992% of all programs)
[=] executions are reduced by a factor of 11977.78
========================================
[=] pruned by partial program properties 41736438 (74.160% of all prunes)
[=] pruned by whole-program properties   14542458 (25.840% of all prunes)

With a maximum of 8 calls per program (the per-action-kind limits are unchanged) we get:

./exhaustive-enumeration$ cargo run --release -- --dry-run
[+] Running with args Args { repro_testcase: None, dry_run: true }

[+] Enumerating Baseline
[=] subtree-prunes          0 | program-prunes          0 | execs     740090 | crashes          0
...
[=] subtree-prunes          0 | program-prunes          0 | execs  412896251 | crashes          0
...

[+] Enumerating Prune
[=] subtree-prunes     257826 | program-prunes     707059 | execs        285 | crashes          0
...
[=] subtree-prunes   35659268 | program-prunes   46543943 | execs       4698 | crashes          0
...

[=] Final statistics comparison
[=] baseline: subtree-prunes          0 | program-prunes          0 | execs  413284939 | crashes          0
[=] pruned:   subtree-prunes   35854128 | program-prunes   46711770 | execs       4699 | crashes          0

================================================================================
[=] Summarized impact of search space pruning on number of executions / oracle invocations
[=] would-be executed:    413284939 (no pruning) |       4699 (pruning)
[=] total pruned programs: 413280240 (99.999% of all programs)
[=] executions are reduced by a factor of 87951.68
========================================
[=] pruned by partial program properties 366568470 (88.697% of all prunes)
[=] pruned by whole-program properties   46711770 (11.303% of all prunes)

Summarized across the three execution budgets:

This underlines the importance of pruning subtrees early.

Conclusion#

Compared to what I did in part 1, the end result this time is a much better implementation in almost all regards. It is easier to understand. It takes much less code to write. It achieves a better result on the metric I care about (number of executed programs / search space size reduction, since the oracle is prohibitively expensive). It is more efficient regarding runtime (time-complexity) – since search space pruning happens incrementally, as early as possible, not after the fact – and regarding memory (space-complexity) – there is no explicit visited set keeping track of all (normalized) programs. And it explores a larger semantically meaningful search space than the implementation from part 1 (here we have longer programs, and more possible leaf values).

There are of course still things to improve, but overall I think it’s an OK state to stop in.