Open tuong opened 1 year ago
In this example: https://github.com/sfu-rsl/symrustc/blob/12e63ee679dc9833dd5df56c97970d2f2514553c/Dockerfile#L408 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
Avoid randomization by configuring
n+1
to remember which previous mutations failed inn
, so thatn+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:
https://github.com/sfu-rsl/symrustc/blob/7c1b9ee38c776400973ac4d1e418581929b3d10b/Dockerfile#L442
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).
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...
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...
Instead of using
shuffle
, one may perhaps re-implement thefor
traversal
Yeah, this made more sense and I pushed the changes to sfu-rsl/LibAFL#1.
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 ofn+1
to present mutations randomly more interesting thann
.Avoid randomization by configuring
n+1
to remember which previous mutations failed inn
, so thatn+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).
While running the LibAFL main loop: https://github.com/sfu-rsl/symrustc/blob/653042a497cca4a8b5be5e0bed675779fc2de77c/Dockerfile#L536 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 theinput
selected from the set of potential corpus candidates appears to be a random choice at each iteration offuzz_one
, e.g. while going from iterationn
to iterationn+1
. Note thatfuzz_one
first starts with executing the concolic version (using the LibAFL SymCC Rust backend, and this is done only one time): https://github.com/sfu-rsl/symrustc/blob/653042a497cca4a8b5be5e0bed675779fc2de77c/libfuzzer_rust_concolic_instance/fuzzer/src/main.rs#L284 However, the Z3 mutationsm
subsequently generated bygenerate_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 withpanic
at iterationn
in the non-concolic version: https://github.com/sfu-rsl/symrustc/blob/653042a497cca4a8b5be5e0bed675779fc2de77c/libfuzzer_rust_concolic_instance/fuzzer/src/main.rs#L185 then all remaining mutations inm
(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 wheren+1
is generating the same set of mutationsm
(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:
m
to hope to increase the probability ofn+1
to present mutations randomly more interesting thann
.n+1
to remember which previous mutations failed inn
, so thatn+1
will never re-execute them again.