I used AFL (fast) on the TXR language and fixed a few issues as a result in release 148. None of them were corruption issues. Several were degenerate behavior. One was a termination via abort, due to something not being checked. I just fuzzed the parser, not even delving into semantics very much. Still, the parser involves expansion of macros and special operators, and is complicated enough in itself, so things can go wrong.
One issue that was uncovered was that the defvarl macro was improperly implemented. It is supposed to be like defvar, but not mark the symbol as special, giving rise to a global lexical variable (hence the "l"). However, it was actually behaving as a synonym for defvar. How AFL helped uncover this is that its fuzzing generated the form (defvarl) with no parameters. Now defvarl was marking the symbol special at expansion time. There was no error checking for the missing name, and so the symbol nil was passed to an internal function to mark a symbol special; and that asserted on nil being a non-bindable symbol. Of course, my reaction was, huh? How do we end up in mark_special when defvarl is being expanded? Oh shit ...
Another thing AFL found was degenerate behavior in the op operator for generating anonymous functions. op scans its body for numeric parameters, and then generates a lambda with a number of arguments based on the highest numeric parameter: (op whatever @1 @2) gives you, ignoring certain other details, (lambda (arg1 arg2) (whatever arg1 arg2)). AFL figured out that there is a problem if we do something like (op whatever @1111111111111111111111111111111). The expander wants to create lambda syntax with a huge number of parameters, which blows up memory. Though nobody would do this in a normal program, suppose that you have some application which accepts code and interprets it. Of course, you sandbox all the stuff which could let the code access the system---but issues like this means that you're open to DoS before the code even runs, just from parsing it and expanding its macros. You wouldn't sandbox off a useful programming feature like op. I just put in a hard maximum on the integer that can be used in the op syntax.
One more degenerate behavior AFL uncovered was in backquote nesting. The TXR Lisp backquote is spelled ^ (caret). AFL uncovered that ^^^^^^...FORM nesting blows up memory exponentially in the number of rounds, due to each round of nested backquote expansion multiplying the size of the expansion. This prompted me to finally add some optimization of the generated code to the sloppy backquote expander, which reduces the expansion growth to linear in the number of rounds.
After these fixes, I noticed speed increase in "make tests" in excess of 7%, too.
One issue that was uncovered was that the defvarl macro was improperly implemented. It is supposed to be like defvar, but not mark the symbol as special, giving rise to a global lexical variable (hence the "l"). However, it was actually behaving as a synonym for defvar. How AFL helped uncover this is that its fuzzing generated the form (defvarl) with no parameters. Now defvarl was marking the symbol special at expansion time. There was no error checking for the missing name, and so the symbol nil was passed to an internal function to mark a symbol special; and that asserted on nil being a non-bindable symbol. Of course, my reaction was, huh? How do we end up in mark_special when defvarl is being expanded? Oh shit ...
Another thing AFL found was degenerate behavior in the op operator for generating anonymous functions. op scans its body for numeric parameters, and then generates a lambda with a number of arguments based on the highest numeric parameter: (op whatever @1 @2) gives you, ignoring certain other details, (lambda (arg1 arg2) (whatever arg1 arg2)). AFL figured out that there is a problem if we do something like (op whatever @1111111111111111111111111111111). The expander wants to create lambda syntax with a huge number of parameters, which blows up memory. Though nobody would do this in a normal program, suppose that you have some application which accepts code and interprets it. Of course, you sandbox all the stuff which could let the code access the system---but issues like this means that you're open to DoS before the code even runs, just from parsing it and expanding its macros. You wouldn't sandbox off a useful programming feature like op. I just put in a hard maximum on the integer that can be used in the op syntax.
One more degenerate behavior AFL uncovered was in backquote nesting. The TXR Lisp backquote is spelled ^ (caret). AFL uncovered that ^^^^^^...FORM nesting blows up memory exponentially in the number of rounds, due to each round of nested backquote expansion multiplying the size of the expansion. This prompted me to finally add some optimization of the generated code to the sloppy backquote expander, which reduces the expansion growth to linear in the number of rounds.
After these fixes, I noticed speed increase in "make tests" in excess of 7%, too.
I look forward to more fuzzing.