Hello,

On 07/07/18 05:01 AM, bugs@feusi.co wrote:
> I am working on a project in which I use the afl fuzzer to fuzz
> different open-source software. In doing so, I discovered a
> heap buffer overflow in sed/execute.c, line 992. 

Thank you for this interesting bug report, and for providing such easy
way to reproduce. I can confirm this is reproducible, and in fact is
a very old bug! fantastic work.

It took some time and lots of squinting to track it down, so I'll write
it here in details for others.

Your sed script file was:
====
10s11\91
\0^0s1011
\00a
\0^0s111w0
====

The input file content doesn't matter for the bug, so I won't focus on it.

Interested readers - If you like challenges, stop reading this email and
spend couple of minutes trying to understand the above script.
fun a-plenty :)

I assume that all the 1's and 0's are because AFL mutated bit by bit
until something was triggered. They aren't critical for the bug, so
here's a simpler and more concise buggy program:

====
    seq 2 | valgrind sed -e '/^/s///p ; 2s//\9/'
====

It might still not be immediately clear why there is a bug here.
An even simpler version of the above program does not seem buggy at
first, because the invalid backref is detected:
===
   $ seq 2 | sed -e '/^/p; 2s//\9/'
   1
   1
   2
   sed: -e expression #1, char 0: invalid reference \9 on `s' command
===

However, this detection suppressed under "--posix", so the bug is
actually there:
====
   $ seq 2 | valgrind sed --posix -e '/^/p; 2s//\9/' 

   1
   1
   2
   ==19663== Invalid read of size 4
   ==19663==    at 0x10FD51: ??? (in /bin/sed)
   ==19663==    by 0x110402: ??? (in /bin/sed)
   ==19663==    by 0x10B106: ??? (in /bin/sed)
   ==19663==    by 0x50802E0: (below main) (libc-start.c:291)
   ==19663==  Address 0x5a9df74 is 20 bytes after a block of size 16 in
   [....]
====

The novelty of this bug report is that using few more "previous regexes"
and the ^/$ optimization [1], the safety check is bypassed even when not
using "--posix".
[1] https://git.savannah.gnu.org/cgit/sed.git/commit/?id=6dea75e7


Attached is a suggested fix.
It seems very simple, but I encourage everyone to double-check my logic
and perhaps detect more problems.

comments very welcomed,
  - assaf


P.S.
1. You haven't provided a name, so I credited you as "bugs@feusi.co" in
the commit message. If you'd like something else, let me know.

2. Out of curiosity, are you using stock AFL or a modified one?
If stock AFL, how long did you run it before something was triggered,
and how was it configured (and which input files) ?
I used AFL on previous version of sed for 24 hours without any bug detected.