News for hackers. Stuff that matters.
Re:Fix Boyer-Moore searcher with the Rytter correction by skyde on Friday April 17, 2020 @01:00AM (#22896341)
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 ?

Re:Fix Boyer-Moore searcher with the Rytter correction by StephanTLavavej on Friday April 17, 2020 @09:13AM (#22898657)
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.

Re:Fix Boyer-Moore searcher with the Rytter correction by marvy on Friday April 17, 2020 @03:27PM (#22902138)
It seems AFL might have been ported to Windows:

https://github.com/ivanfratric/winafl

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

Re:Fix Boyer-Moore searcher with the Rytter correction by StephanTLavavej on Friday April 17, 2020 @06:55PM (#22903765)
Very interesting, thanks!
Re:Fix Boyer-Moore searcher with the Rytter correction by hyperpape on Friday April 17, 2020 @11:11AM (#22899668)
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.

Re:Fix Boyer-Moore searcher with the Rytter correction by StephanTLavavej on Friday April 17, 2020 @06:52PM (#22903742)
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.
Re:Fix Boyer-Moore searcher with the Rytter correction by typon on Friday April 17, 2020 @01:32AM (#22896502)
I know him as the cpp pirate