Re: binary search debugging of compilers

On 2023-05-17, gah4 <gah4@u.washington.edu> wrote:
> As to the problem of debugging by miscompiled code, this reminds
> me of stories of debugging compilers by feeding them cards from
> the card recycling bin. It seems that cards were especially high grade
> paper and so worth keeping separate for recycling. I never actually
> saw anyone do that, though.


Obviously, the card recycling bin is going to be a source of garbage
that is invalid inputs to the compiler, with perhaps some valid bits.


This was effectively an early form of fuzzing.


> In my younger days, some said that I was especially good at finding
> compiler errors. Maybe not as good now.


Fuzzing has matured now. There are tools now which instrument the
executable, and monitor what is going on in terms of the program
control flow in response to random inputs. Then they adjust the bits
to try to stimulate paths not taken to tickle bugs. That's the
jist of it.


> I would try things that were
> allowed, but others might not have thought about doing.


I've not used fuzzing in a while ... since 2016 it turns out! I played with it
in the summer of that year. The software was AFL (American Fuzzy Lop) 2.30b.


I had found three bugs in a short timespan back then.


One of them was exponential memory explosion in nested quasiquoting syntax like
^^^....^^exr. (TXR Lisp's quasiquoting operator is written ^ rather than the
usual backtick ` used in most traditional Lisp dialects, otherwise it is the
same thing).


AFL also discovered that if it puts a huge number into the op syntax like this:
(op list @123455234), the op expander will obligingly generate a lambda with
that many arguments! E.g. (op list @3) generates something similar to
(lambda (arg0 arg1 arg3) (list arg3)). So imagine if we replace @3 with a
large integer.


AFL also found a crash in the regex parser. It was not doing a range check on
numeric character escapes, making it possible for the program to sneak a
negatively valued character code into the regex copiler, where it resulted in
an out-of-bounds array access problem.


I have been meaning brush the dust off this technique again.


> Only one I remember now, is a C compiler that miscompiled the ++
> operator on a double variable. Allowed in C, but maybe not often used.


Oh, stepping doubles with ++ is, I would say, not *that* uncommon.
I doubt that if such a bug were introduced as an easter egg into GCC,
it would go very long without being discovered by the FOSS distros and
other downstream users.


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Return to the comp.compilers page.
Search the comp.compilers archives again.