Fuzzing stateful systems: noPac, Part 1: blind random search

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…

noPac introduction#

noPac (CVE-2021-42278 / CVE-2021-42287) is a logic bug in Active Directory chaining ambiguous account naming with lenient account mapping during authentication.

More background information can be found e.g. in this writeup from NetEye, this writeup from paloalto, or this writeup.

I purposefully do not go into specific exact commands or why it works, since this is not the focus here. The focus is on methodology/technique.

Detection and mitigation#

The articles linked in the previous paragraph cover in detail how the issue can be detected. First and foremost, the Windows version and installed updates can be matched to identify whether a system is affected. Mitigation is possible by updating Windows to the current version (it has been fixed in the November 2021 Security Updates / Patch Tuesday).

Behavioral detection includes reviewing the event log entries on the domain controllers for the individual steps (computer account creation, account name or spn changes for computer accounts, Kerberos activity like TGT and ST requests), and potential remnants of those steps like computer accounts whose name does not end in a trailing dollar.

Fuzzing semantic actions#

We want to successively translate these manually taken actions into high-level actions that our fuzzer is able to test out against the lab Active Directory, while trying to limit the amount of domain-specific knowledge we hardcode a-priori.

Some of the fuzzer code is available in this git repository in the random-fuzzing subfolder. However, the code 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.

The accompanying rust code has no dependencies, however the terminology and implementations are heavily borrowed from LibAFL concepts and LibAFL (MIT/Apache-2.0) in general. I chose to implement it without dependencies in part to learn more about the architecture, and in part because, given the black-box nature of this fuzzer, many helpers that provide advanced features and require technical sophistication (like VM snapshotting or binary-only code coverage) are not needed here.

Other influences for this approach to stateful fuzzing: I learned first about it from Stevan’s blog about property based testing, syzkaller and fuzzilli.

Refining the assumed initial position#

However, before writing an automated fuzzer, we can define the assumed initial position more specifically. Compared to the PoC described in the linked articles, we can simplify the action space a bit, hopefully without assuming too much bug-specific knowledge.

Since several of the possible actions include changing the names of accounts, i.e. attributes used for authentication of accounts, in order to prevent name-resolution bugs in the fuzzer itself, it is reasonable to split this part and have one stable unchanged account (here the user), that modifies attributes of a second account (here the computer).

Fuzzer input type and action space#

In src/input.rs we define the action space successively on different abstraction levels.

General framework#

First, the overall fuzzer input type is a Program: a sequence of abstract action/function calls, together with a pre-seeded initial environment for any hardcoded parameters:

11
12
13
14
15
16
17

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Program {
    /// Initial environment / resources seeded before execution.
    pub env0: Vec<(Ref, Val)>,
    /// Function / action calls in explicit order.
    pub calls: Vec<Call>,
}

The runtime Env will be a proper HashMap from Refs to Vals, but – since a Program may be serialized to disk – an explicit ordering in a list is nicer here for the initial environment, imho.

Next, we have the abstract action/function signature definition Sig: an action is modeled as something that takes a list of named parameters of a specific type, and optionally returns a value of a specific type:

138
139
140
141
142
143
144

/// Action call signature / schema.
pub struct Sig {
    /// Parameters / arguments (pairs of name and type).
    pub params: &'static [(&'static str, Type)],
    /// Return value.
    pub ret: Option<Type>,
}

Corresponding to a runtime instantiation of such an action, we have the action Call, which mirrors the Sig definition but instead of referencing types in the parameters and return position, these contain Refs (simply a number, an index into the runtime environment) to values of the type that Sig specifies:

146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

/// Opaque symbolic variable / resource reference / handle to dynamically (at
/// execution time) created function / action return values.
#[derive(Hash, PartialEq, Eq, Debug, Clone, Copy)]
pub struct Ref(u32);

impl Ref {
    pub fn new(id: u32) -> Ref {
        Ref(id)
    }
}

/// A specific symbolic action call.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Call {
    pub kind: ActionKind,
    pub params: Vec<Ref>,
    /// Destination reference where the output will be stored under in `Env`.
    pub ret: Option<Ref>,
}

This explicit distinction between signature and instance definition is a more general framework than defining the desired domain-specific actions directly as enums in the host language (here Rust). I took this basic idea from long existing, proper, mature fuzzers like syzkaller or fuzzilli.

Note also the deliberate decision to let these ids represent stable named variables, not position-relative ones (e.g. similar to De-Bruijn indices, referring back to the id-th previously produced result value, or auto-incrementing and referring forward from the start of the environment to the id-th value). The ref is purposefully decoupled from the position in the Program since mutation of inputs – like inserting another action call in between others, or swapping action calls – (without manual repair/adjustment which would complicate the implementation) would change the meaning of references and lead to the fuzzer interpretation problem.

The function Program::validate checks the correspondence and type safety of all function calls against their respective Sigs, and additionally performs basic sanity checks on the refs and the environment (e.g. no duplicate return refs, no dangling refs, etc.). In line with “parse, don’t validate”, it returns a dedicated newtype ValidProgram that represents a correct program.

The relationships between these types (and the Ref-into-Env indirection that decouples a value from its position in the program) look like this:

Domain-specific parts#

After these general type definitions, there are problem-domain specific definitions of all possible relevant actions…:

170
171
172
173
174
175
176
177
178

/// Kinds of possible actions.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ActionKind {
    ClearLdapAttribute,
    SetLdapAttribute,
    GetTgt,
    GetSt,
    AuthorizationOracle,
}

… together with their respective call signatures:

180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

impl ActionKind {
    /// Action space / signature table.
    pub fn sig(self) -> Sig {
        match self {
            ActionKind::ClearLdapAttribute => Sig {
                // AuthAccount and TargetAccount are implicit.
                params: &[("attribute", Type::LdapAttribute)],
                ret: None,
            },
            ActionKind::SetLdapAttribute => Sig {
                // AuthAccount and TargetAccount are implicit.
                params: &[
                    ("attribute", Type::LdapAttribute),
                    ("value", Type::SamAccountName),
                ],
                ret: None,
            },
            // AuthAccount password is implicit.
            ActionKind::GetTgt => Sig {
                params: &[("auth_name", Type::SamAccountName)],
                ret: Some(Type::Tgt),
            },
            ActionKind::GetSt => Sig {
                params: &[("auth", Type::Tgt), ("args", Type::GetStArgs)],
                ret: Some(Type::St),
            },
            ActionKind::AuthorizationOracle => Sig {
                params: &[("auth", Type::St)],
                ret: None, // Fails if not admin.
            },
        }
    }

Where not relevant (e.g. not for GetTgt/GetSt/AuthorizationOracle), the authenticating account and target account for operations is hardcoded to fit my local lab environment. The structure of chosen available actions already encodes some prior domain-specific knowledge.

Then we have the type and value definitions, which mirror each other:

249
250
251
252
253
254
255
256
257
258
259
260

/// Kinds/types of values.
#[derive(PartialEq, Eq, Debug, Clone, Copy)]
pub enum Type {
    LdapAttribute,
    SamAccountName,
    /// Kerberos Ticket Granting Ticket.
    Tgt,
    /// Kerberos Service Ticket.
    St,
    /// Structured arguments for requesting a service ticket.
    GetStArgs,
}

270
271
272
273
274
275
276
277
278
279
280

/// A specific runtime instance of `Type`; mirrors its structure.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum Val {
    LdapAttribute(LdapAttribute),
    SamAccountName(String),
    #[allow(dead_code)]
    Tgt(Tgt),
    #[allow(dead_code)]
    St(St),
    GetStArgs(GetStArgs),
}

Next, we dive a bit deeper into the individual fuzzer components.

Getting a symbolic program#

First, we take a look at different operations on the previously defined Program fuzzer input type and its parts.

Generating test inputs#

src/generator.rs implements the generation of test cases as a random sequence of action calls together with randomly selected parameter values from a pre-defined set of values.

In exactly this selection it is probably the part in the fuzzer that encodes the single most bug-specific knowledge a-priori, making the idea of rediscovering noPac not realistic/representative here.

To get the search space small enough I artificially constrain it through a pre-defined execution Budget that limits the length of possible action calls in a program, as well as per-action-kind limits.

444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466

/// Execution budget (artificially bounds the search space)
#[derive(Clone)]
pub struct Budget {
    /// Total program length.
    pub max_calls: usize,
    /// Per action-kind execution budget.
    pub per_kind: [usize; ActionKind::N],
}

impl Budget {
    pub fn default() -> Self {
        let mut per_kind = [0usize; ActionKind::N];
        per_kind[ActionKind::ClearLdapAttribute.index()] = 1;
        per_kind[ActionKind::SetLdapAttribute.index()] = 2;
        per_kind[ActionKind::GetTgt.index()] = 1;
        per_kind[ActionKind::GetSt.index()] = 1;
        per_kind[ActionKind::AuthorizationOracle.index()] = 1;
        Budget {
            max_calls: 6,
            per_kind,
        }
    }
}

Additionally the parameter values are also chosen from a predefined finite set of values, depending on the type of the parameter (type-directed):

• LdapAttribute (to clear or write to).
• SamAccountName (value of account names to set or authenticate as when requesting a TGT).
• GetStArgs: chooses a random instance of arguments for requesting a service ticket; substituting SPNs, altservice and user names.
• Tgt / St: Cannot simply be generated. These types only occur as opaque handles (refs) that are dynamically produced as result of the corresponding action calls GetTgt / GetSt.

Mutating test inputs#

src/mutator.rs implements mutating operations on the action sequence, e.g. insertion/removal of calls, changing a call type, and rebinding/swapping parameter values, as well as LibAFL-inspired insert- and replace-crossover-mutations with another selected individual from the corpus.

The implementation is a bit verbose / laborious, especially keeping the references and vals/types in sync.

Assisting mutation (and also generation) is a ProgramBuilder, which manages the initial environment and the program calls and allows for type-safe program generation without keeping all the parts in sync manually; the returned programs validate correctly.

Shrinking test inputs#

src/minimizer.rs finally implements the last important operation on test cases: shrinking/minimizing an input, which reproduced a “crash” (i.e. the desired behavior) by modifying it as long as the resulting program still crashes.

Here, this is done in a very naive way by iterating over the action sequence, trying to remove each call individually (and cascading removes to the environment e.g. by pruning dangling references), executing the result and assessing the outcome. This is a naive strategy, but for this example problem, anything more is probably overkill.

Interpreting/executing a symbolic program#

Each call of a program can be interpreted / executed by performing the corresponding symbolically represented actions, resolving input/parameter references from a runtime environment mapping of references to values, and writing handles/references, that are dynamically created/returned at runtime, back to that environment.

13
14
15
16

/// Runtime environment: mapping from symbolic `Ref` to concrete `Val`. Seeded
/// from `env0`. Extended during execution from action outputs `Call.ret`.
#[allow(dead_code)]
struct Env(HashMap<Ref, Val>);

This is implemented in executor.rs (omitted here to not publish an operational fuzzer).

Since the fuzzer operates essentially black-box against the AD, we do not really have a good way of formulating a guiding heuristic like traditional binary fuzzers do with code/branch coverage.

One could collect whole-system code coverage of the Windows domain controller machine and go the route of snapshot fuzzing, but I doubt that it will be useful here without employing much heavier machinery like a fully deterministic hypervisor like Antithesis provides: I think that in a larger system with many components like Active Directory Domain Services there is probably so much nondeterministic noise in nonrelevant code paths that distilling a useful signal out of it is not likely (I could be wrong, however).

Absent full system/vm-snapshots, to get a suitable baseline initial state, I hardcode a reset before executing each symbolic program, that deletes the test user and computer (matching by their stable identifiers / SIDs), and re-creates them with the expected permissions.

What we nonetheless can do, is at least closely looking at the responses the domain controller gives us and recording that into a kind of behavioral coverage map:

3
4
5
6

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

Here I chose possibly the simplest approach, by recording a set of runtime-generated, fully untyped strings that represent the outcome of each action, e.g. something similar to “ticket request as user user was successful”, or “rename operation succeeded”, or “operation at step N failed because of reason”.

It doesn’t provide a strong guiding heuristic, but a very rough direction to e.g. not propagate programs as interesting if they fail on the first call is probably nonetheless useful.

Incorporating this feedback information is then implemented in the usual way by keeping a corpus of programs which led to novel coverage (i.e. are considered “interesting”) and then, during subsequent mutation, selecting candidates from this corpus:

 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#[derive(Default)]
pub struct Corpus {
    programs: Vec<Program>,
    global_cov: Coverage,
}

impl Corpus {
    pub fn add_if_new(&mut self, pgm: Program, cov: &Coverage) -> bool {
        // Register coverage in global coverage.
        let mut novel = false;
        for c in &cov.0 {
            novel |= self.global_cov.insert(c.clone());
        }

        if novel {
            self.programs.push(pgm);
        }

        novel
    }

    pub fn select<'a>(&'a self, rng: &mut Rng) -> &'a Program {
        // Here: simple random selection (without priority / weighting).
        rng.choice(&self.programs)
    }

Search space pruning#

Trying to run the fuzzer at this stage doesn’t succeed. The search space is simply too large, and there are too many uninteresting programs / input candidates. Coupled with a very expensive oracle which takes usually more than 5s to execute, there is – even with the already baked in domain knowledge for test input generation/mutation – no hope of actually finding such an input in an acceptable time.

Fortunately, this whole problem area is nothing new and we can apply known techniques e.g. from model checkers and compiler optimizations to drastically reduce the size of the search space. search_space_reducer.rs implements multiple such strategies in a rather ad-hoc manner, and not really a structured approach (since I’m still learning on the go). Part 2 however will explore search space reduction a bit more systematically with a more efficient implementation, and quantify the effectiveness of search space pruning exactly.

The very first observation we should note is that the type-directed limited allowed leaf values (parameters to calls) chosen in the generator and mutator already gives a finite domain of values, and a finite environment. Additionally, the execution budget limits the number of calls in a program. Together, as both parts of a Program, these parts define the search space size overall as finite.

Various pruning strategies reduce the search space size further. The basic idea is to normalize/canonicalize the symbolic program representation, and then for each semantic equivalence class only execute one representative program. Here this is done by first constructing a full program, and then normalizing and possibly rejecting it before execution (generate then reject). For that we memoize a visited set of each such canonical program representation to filter out duplicates that probably lead to the same behavior.

The specific observations and strategies implemented here are: For the action calls pgm.calls:

• Inside a batch of consecutive writes, writes to different attributes are independent of each other, therefore they commute (it doesn’t matter which one is applied first). That means the exponential number of interleavings all have the same semantic effect. Therefore, we can pick a single canonical ordering of these write operations and ignore all others. (Partial-order reduction)
• Inside a batch of consecutive writes, multiple writes to the same attribute have the effect of the last write (last write wins). So we can drop earlier writes. (Dead-store elimination)
• Consecutive writes (even with a read operation in between) of the same value to the same attribute are fully redundant; all but the first one can be dropped. (Redundant-store elimination)
• Writes whose effects are never observed by a corresponding read operation (trailing writes) can be dropped. (Dead-store elimination)
• Calls that return a value and do not have any other side-effects, whose return value is never observed / used as parameter, can be dropped.

For the runtime environment pgm.env0:

• Remove duplicate let bindings / variables referring to the same actual value and only keep one assignment.
• Normalize variable names, i.e. normalize the program under alpha-equivalence (e.g. pick a canonical naming by sorting based on value, and then numbering this order starting from 0).

I’m sure there are other patterns and symmetries which could be used to implement smarter pruning strategies, but these ones are easy to understand and implement, and I’d rather err on the side of having false negatives (a larger search space than necessary because of unpruned irrelevant programs) than introducing false positives during pruning (an actually relevant program was not tested).

Summary of fuzzer components#

After having covered each component we can give a summarized overview.

`-- src         # Fuzzer source code

    |-- main.rs                 # Program entrypoint

    |-- fuzzer.rs               # The fuzzing tying everything together

    |-- cli.rs                  # Commandline argument parsing
    |-- error.rs                # Error types
    |-- rng.rs                  # Pseudo-random number generator

    |-- input.rs                # Input type definitions (program as list of actions)
    |-- input                   #
    |   `-- serde.rs            # Encoding into/decoding from textual DSL

    |-- generator.rs            # Generate one fuzzer input
    |-- mutator.rs              # Mutate one fuzzer input (including crossover)
    |-- minimizer.rs            # Minimize a given test input as long as it crashes

    |-- feedback.rs             # Feedback/coverage information types
    |-- executor.rs             # Execute one input against the lab AD environment
    |                           #   and collect feedback/coverage (not included)

    |-- search_space_reducer.rs # Search space reduction/pruning by omitting
    |                           #   execution of semantic duplicates.
    |-- corpus.rs               # Corpus as a list of executed test inputs with
    |                           #   their resulting coverage information
    `-- stats.rs                # Statistics like number of executions/crashes

Example fuzzer run#

With these pruning strategies implemented, the fuzzer can be started with cargo run and loops until an input leading to the desired behavior is found. (Again, the published code is not runnable). After letting it run unattended in a loop overnight, restarting every 15 minutes, it finally succeeded.

Conclusion#

Is the fuzzer successful? In the sense that it can reproduce the target behavior: yes. In the sense that it can do so realistically without introducing/encoding bug-specific knowledge a-priori in the generation/mutation pipeline itself: not really.

Also, there are some key factors that make this problem not a good fit for this approach and deviate quite a bit from more typical fuzzing setups (in hindsight, they seem obvious, but I didn’t know before trying it out):

• Executing the crash oracle is very expensive: fundamentally, programs can only be executed serially one after another, no easy parallel execution. Additionally, executing each program call takes several seconds.
• The current implementation only uses very weak – almost nonexistent – feedback for guiding the fuzzer. Not at all comparable to something like edge coverage in traditional binary fuzzing.

Because of that, I think the form presented here (blind random undirected search) is probably not the best fit for this problem.

Things to do better and an outlook on the next iteration#

This naturally shifts the perspective from traditional fuzzing more to something like exhaustive enumeration of a finite search space, combined with aggressive pruning of semantic duplicates.

This will be the approach for the next iteration in part 2. Specific points that will also be improved upon:

• Currently search space pruning is done by generate-then-filter. A more efficient approach would be valid-by-construction program generation, and search space pruning as soon as possible (including partial programs).
• In the same vein, the current implementation keeps track of a set of executed programs for semantic deduplication, which costs space/memory. If we are smarter during generation, and introduce pruning on partial programs (whole subtrees of the search space), we do not need that anymore.

Both these should not be that important here specifically, since the oracle execution times dwarf any input case compute. But they are nonetheless important improvements.