Hacker News new | ask | show | jobs
by StephanTLavavej 2247 days ago
I believe that fuzz testing would have found it, yes. I'm not sure if fuzz testing would have been guided towards highly repetitive patterns, given the relative lack of branches in the table construction code, but the incorrectly handled patterns can be very short so fuzz testing should have stumbled upon them (given a pattern that generated an incorrect table, finding a haystack which doesn't work is merely a matter of having the needle occur at a specific offset).

Currently we don't fuzz test MSVC's STL, but that is an extremely interesting area to explore in the future. I played around with this a little while working on std::from_chars() (and found no bugs), but it involved actually porting the code to Linux to be compiled with American Fuzzy Lop, so I didn't permanently add such test coverage to our repo.
2 comments
marvy 2246 days ago
It seems AFL might have been ported to Windows:

https://github.com/ivanfratric/winafl

(don't know; just found this two minutes ago)

link
StephanTLavavej 2246 days ago
Very interesting, thanks!
link
hyperpape 2247 days ago
A technique that I've used while fuzz testing string algorithms is to run all tests first with small alphabets (perhaps 4-6 characters), then with full alphabets. It seems to increase the probability of finding bugs with relatively small runs.

My work is on a personal project, not algorithms that have been in production for years, so it's possible that this wouldn't be that productive.

link
StephanTLavavej 2246 days ago
Indeed, the randomized test in this PR uses alphabets from AB to ABCDEF, because I noticed the same thing - small alphabets make repetitions more likely, which are the tricky cases.
link