Handling panic exceptions in the concolic fuzzing loop of LibAFL

[tuong]

While running the LibAFL main loop:

symrustc/Dockerfile

Line 536 in 653042a

&& $SYMRUSTC_HOME_RS/libafl_solving_inst_run.sh test; \

the execution of fuzz_one in https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/libafl/src/fuzzer/mod.rs#L573 is repetitively randomly made, in the sense that the input selected from the set of potential corpus candidates appears to be a random choice at each iteration of fuzz_one, e.g. while going from iteration n to iteration n+1. Note that fuzz_one first starts with executing the concolic version (using the LibAFL SymCC Rust backend, and this is done only one time):

symrustc/libfuzzer_rust_concolic_instance/fuzzer/src/main.rs

Line 284 in 653042a

fn spawn_child<I: Input + HasTargetBytes>(&mut self, input: &I) -> Result<Child, Error> {

However, the Z3 mutations m subsequently generated by generate_mutations:
https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/libafl/src/stages/concolic.rs#L94
are always deterministic considered:
https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/libafl/src/stages/concolic.rs#L385
In particular, if a mutation happens to fail with panic at iteration n in the non-concolic version:

symrustc/libfuzzer_rust_concolic_instance/fuzzer/src/main.rs

Line 185 in 653042a

let mut harness = |input: &BytesInput| {

then all remaining mutations in m (not yet considered) are immediately discarded. This is undesired as the unvisited mutations may reveal important concolic paths, that may be important for the overall progress of the concolic binary exploration.

Whereas the fuzzing loop can anyway be persistently configured to resume its computation and start fresh at iteration n+1, this appears to be still unsatisfying, even in the situation where n+1 is generating the same set of mutations m (as the same unvisited mutations would turn out to be all unvisited again).

In this issue, we propose to solve this problem using, among others, the following mutually exclusive solutions:

• Randomize m to hope to increase the probability of n+1 to present mutations randomly more interesting than n.
• Avoid randomization by configuring n+1 to remember which previous mutations failed in n, so that n+1 will never re-execute them again.

[tuong]

In this example:

symrustc/Dockerfile

Line 408 in 12e63ee

&& sed -i 's|if let Some(mutations) = mutations {|use rand::prelude::*; if let Some(mut mutations) = mutations { let mut rng = rand::thread_rng(); mutations.shuffle(\&mut rng);|' ~/libafl/libafl/src/stages/concolic.rs

we solve the problem using the first strategy, by randomizing the generated mutations.

Note that instead of introducing a new dependency to the rand library, a next step would be to rely on this already existing random library of LibAFL:
https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/libafl/src/bolts/rands.rs

[tuong]

Avoid randomization by configuring n+1 to remember which previous mutations failed in n, so that n+1 will never re-execute them again.

Whenever a mutation is failing in n, the use of the following option may perhaps help continuing the execution of the remaining mutations in n:
https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/fuzzers/baby_fuzzer/Cargo.toml#L16
However, our first experiments seem to show that if we enable this option, then the recompilation of our copied rlib might become difficult to be avoided:

symrustc/Dockerfile

Line 442 in 7c1b9ee

&& cargo rustc --release --target-dir ../target \

[momvart]

a next step would be to rely on this already existing random library of LibAFL

As State is responsible for managing the randomization, we can leverage it for this purpose. For example,

if let Some(mut mutations) = mutations {
    state.rand_mut().shuffle(&mut mutations);
    // ...
}

Just note that the shuffle method is not provided by the default Rand in LibAFL and we can easily implement it at libafl/src/bolts/rands.rs as follows:

pub trait Rand: Debug + Serialize + DeserializeOwned {
    // ...

    /// Shuffles the given slice in place.
    fn shuffle<T>(&mut self, target: &mut [T]) {
        // Grabbed from rand library implementation.
        for i in (1..target.len()).rev() {
            // invariant: elements with index > i have been locked in place.
            target.swap(i, self.below((i + 1) as u64) as usize);
        }
    }

    // ...
}

BTW, I'll create a pull request to perform this modification in the Dockerfile (which honestly I don't like the approach).

[tuong]

BTW, I'll create a pull request to perform this modification in the Dockerfile (which honestly I don't like the approach).

You can also directly put your modifications in one of the latest versions of https://github.com/sfu-rsl/LibAFL as the sed patch that I made in the Dockerfile is temporary. The branch containing that patch in symrustc is also temporary, and will have to be removed at some point when ready...

[tuong]

Note: Instead of using shuffle, one may perhaps re-implement the for traversal:
https://github.com/sfu-rsl/LibAFL/blob/59bb8e61856b22047f8e6e2787a3f6d90ae99006/libafl/src/stages/concolic.rs#L385
using swap_remove:
https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove
whenever this is lowering the execution cost...

[momvart]

Instead of using shuffle, one may perhaps re-implement the for traversal

Yeah, this made more sense and I pushed the changes to sfu-rsl/LibAFL#1.

[tuong]

In this issue, we propose to solve this problem using, among others, the following mutually exclusive solutions:

• Randomize m to hope to increase the probability of n+1 to present mutations randomly more interesting than n.

• Avoid randomization by configuring n+1 to remember which previous mutations failed in n, so that n+1 will never re-execute them again.

Note: Adding a non-concolic (pure fuzzing) client to the "concolic client + server" setting does not seem to solve this path exploration problem compared to the above first listed randomization solution (or at least solve it quicker than having to stop it after 3-4 minutes of run).