4 ms·
Fuzzing is awesome. I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it: https://github.com/elves/elvish/commit/9cda3f643ef
by xiaq 5y ago
Fuzzing is awesome. I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it: https://github.com/elves/elvish/commit/9cda3f643efafce2df5671bbdd609b11b4b910d5 https://github.com/elves/elvish/commit/9cda3f643efafce2df567...
Edit: shortly after I wrote this comment, fuzzing discovered another pathological input - and that was fixed in https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e793f70a1e3b58b82d3728 https://github.com/elves/elvish/commit/04173ee8ab3c7fc4a9e79...
(In case people are curious, the project is a Unix shell, Elvish: https://elv.sh https://elv.sh)
- omginternets 5y ago> I just discovered an accidental O(2^n) code path in my project with fuzzing and fixed it I've used fuzzing to find crash/panic conditions in Go, but never to find slow paths. How does that work?
- xiaq 5y agoIt timed out. Since this case is O(2^n) the fuzzer managed to build a relatively short input that caused the function to not terminate for a few minutes.
- ninkendo 5y agoOh wow, I misread your original post as O(n^2) and thought “no way a fuzz test would notice mere quadratic time complexity”, but exponential is another beast entirely :-D
- val_deleplace 5y agoMere quadratic time complexity is something I would expect to timeout and catch at fuzzing time, as long as we do encourage non-tiny inputs, say 10K and beyond.
- omginternets 5y agoOh, fair. I wonder if there is a practical, general way to test for expected time complexity using fuzz tests…