Re:Go Fuzzing
by xiaq on Saturday January 01, 2022 @06:38PM
(#29764055)
It 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.
[ Parent
| on HN ]
Oh 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
Re:Go Fuzzing
by val_deleplace on Sunday January 02, 2022 @09:52AM
(#29769144)
Mere 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.
Re:Go Fuzzing
by omginternets on Sunday January 02, 2022 @12:39AM
(#29766172)
Oh, fair. I wonder if there is a practical, general way to test for expected time complexity using fuzz tests…