Hacker News Reader

Comment by skyde | Hacker News Reader

This guy is a hero! I have so much respect for his work.

By i’m still wondering if this bug could have been detected by automatic fuzzing testing ?

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.

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.

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.

It seems AFL might have been ported to Windows:

https://github.com/ivanfratric/winafl

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

Very interesting, thanks!

I know him as the cpp pirate

Reply on news.ycombinator.com