search

gnzlbg / slice_deque

A contiguous-in-memory double-ended queue that derefs into a slice
https://docs.rs/crate/slice-deque/
Other
154 stars 21 forks source link

Fuzz the API #59

Open gnzlbg opened 5 years ago

gnzlbg commented 5 years ago

The std::collections::VecDeque tests are not really enough to catch all bugs with SliceDeque. @Shnatsel had some posts about how to set up fuzzing.

aldanor commented 5 years ago

I've actually caught #57 while quickchecking / fuzzing some downstream crate that depended on slice-deque lightly. As a simple test for the quality of the fuzz suite, I'd like to suggest testing if it can catch #57 (were it to be reintroduced).

Shnatsel commented 5 years ago

There is already a fuzzing setup designed to check correctness of stdlib VecDeque, which was also created after a security bug in it was discovered. The big selling point is that it includes an unoptimized but obviously correct implementation of the same API against which the optimized implementation can be verified. It can be found at https://github.com/blt/bughunt-rust. It might not be 100% functional yet, but adapting it is probably easier than writing a comprehensive fuzzing setup from scratch.

gnzlbg commented 5 years ago

I've adapted @Shnatsel suggestion to slice-deque here: https://github.com/gnzlbg/slice_deque/tree/fuzz

Fuzzing hasn't found any bugs for me yet.

Shnatsel commented 5 years ago

With capacity capped to maximum value of u8 you will never allocate more than one page of memory and never exercise the actually interesting codepaths

Shnatsel commented 5 years ago

I gave it at about 2 million executions (approx. 8 core-hours on my machine) and it also turned up nothing. And it plateau'd pretty hard in discovering new paths through the code.

I'll run the version with u16 capacity for a while more, but I don't expect it to turn up anything.

gnzlbg commented 5 years ago

Thank you for your help @Shnatsel !

Shnatsel commented 5 years ago

u8_capacity_seeds.zip u16_capacity_seeds.zip

These are the fuzzer findings in release mode with u8 and u16 capacities. I've run the u16 capacity for at about 10 million executions. I think the u16 version is much more compact because the fuzzer had enough time to minify the inputs.

Potential next steps would be running it without model validation but with overflow checking, and also without model validation but with address sanitizer. However, trying stuff blindly might not be a great idea. A much better idea would be to run these inputs through some kind of coverage tool to see what code is not excercised, and/or get a reproduction of the issue #57 from @zimond and then alter the fuzzing setup so that it could detect it.

Shnatsel commented 5 years ago

To clarify, the archives above contain the generated corpus with the most code coverage, not crashing inputs - it didn't find any of those.