Fuzz the API

[gnzlbg]

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]

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]

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]

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]

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]

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]

Thank you for your help @Shnatsel !

[Shnatsel]

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]

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