[Bug-readline] Readline fuzz testing

[Ben Wong]

Readline is causing bash to dump core every once in a bluemoon. It's
extremely infrequent and hard to reproduce, so, to debug it, I'm using
random input from fuzz(1). It turns out, libreadline *consistently*
crashes (segmentation fault) or hangs (infinite loop using all CPU)
under fuzz testing.

IMPACT

I'm hoping I'm mistaken, but it seems that memory allocation errors in
a major library like this could be more than a nuisance; they could be
a security problem.

TO REPRODUCE:

1) Compile Readline 7.0 from ftp.gnu.org, enable AddressSanitizer:

    wget ftp://ftp.gnu.org/gnu/readline/readline-7.0.tar.gz
    tar -zxvpf readline-7.0.tar.gz
    mv readline-7.0 readline
    cd readline
    CFLAGS="-g -fsanitize=address" ./configure
    make
    cd ..

2) Create a super basic readline program (see attached file):

    main() {
      char *line;
      while ((line=rl_gets()) != NULL)
          ;
    }

3) Compile rltest using AddressSanitizer:

    gcc -o rltest -g -fsanitize=address rltest.c -I. \
        readline/lib{readline,history}.a -lncurses

4) Make sure your .inputrc is not confusing matters:

    HOME=/tmp bash -i

5) Run fuzz thusly to make readline barf,

    export ASAN_OPTIONS=handle_segv=0
    fuzz -n80 `pwd`/rltest

Fuzz will run the program with a myriad of input streams. Either the
countdown will freeze, which means readline is hung, or it will
eventually segfault. Check what input stream caused the error by
looking in /tmp/rltest.*.

You can get more information by trying the input stream again.

    cp /tmp/rltest.9798 crash.me
    unset ASAN_OPTIONS
    cat crash.me | ./rltest >/dev/null

EXAMPLE INPUT STREAMS

I've attached three input streams that cause different errors.

Example A causes readline to access a NULL pointer.
Example B causes a heap buffer overflow.
Example C causes readline to go into an infinite loop, using up CPU.

Actually, example C is a bit unnecessary as it is very easy to make
readline go into an infinite loop, even without fuzzing.

    wget https://cnswww.cns.cwru.edu/php/chet/readline/rl.c
    gcc rl.c -lreadline -o rl
    printf '\e\n\eRgy\000' | ./rl

ARCHITECTURE & REPRODUCIBILITY

I've tested Readline-7.0 on both an x86_64 Debian stable (8.4) box and
a 32-bit i686 Ubuntu LTS (16.04) laptop.

Of course, since memory regions can change size when libraries are
compiled, it's possible you might not see the same results. As a test,
I tried compiling my test program by linking it with the precompiled
libreadline (6.3) on a 32-bit Ubuntu-16.04 machine. In that case,
examples A and B do not report any errors (likely due to the lack of
AddressSanitizer). Example C, however, instead of hanging, shows a
heap-buffer-overflow.

I believe compiling libreadline with -fsanitize=address to do runtime
memory checking should minimize this problem.

SAMPLE OUTPUT

This is the output for examples A, B, and C on an x86_64 machine.
The output from my 32-bit i686 box is equivalent.

$ cat A-nullpointer.data | ./rltest > /dev/null
  ASAN:SIGSEGV
  =================================================================
  ==13761==ERROR: AddressSanitizer: SEGV on unknown address 0x00000000
(pc 0xb70a eb86 sp 0xbf8dd2f4 bp 0xbf8dd348 T0)
    #0 0xb70aeb85 (/lib/i386-linux-gnu/i686/cmov/libc.so.6+0x83b85)
    #1 0xb725075f in __interceptor_strlen
(/usr/lib/i386-linux-gnu/libasan.so.1+0x2c75f)
    #2 0x808f8e1 in _rl_copy_to_kill_ring
/home/hackerb9/foo/readline-7.0/kill.c:137
    #3 0x8090f52 in region_kill_internal
/home/hackerb9/foo/readline-7.0/kill.c:421
    #4 0x809104c in rl_kill_region /home/hackerb9/foo/readline-7.0/kill.c:444
    #5 0x804b52b in _rl_dispatch_subseq
/home/hackerb9/foo/readline-7.0/readline.c:859
    #6 0x804b0ed in _rl_dispatch /home/hackerb9/foo/readline-7.0/readline.c:802
    #7 0x804a90e in readline_internal_char
/home/hackerb9/foo/readline-7.0/readline.c:629
    #8 0x804a9a2 in readline_internal_charloop
/home/hackerb9/foo/readline-7.0/readline.c:656
    #9 0x804a9c3 in readline_internal
/home/hackerb9/foo/readline-7.0/readline.c:670
    #10 0x8049fc7 in readline /home/hackerb9/foo/readline-7.0/readline.c:376
    #11 0x8049d48 in rl_gets /home/hackerb9/foo/rltest.c:73
    #12 0x8049cf6 in main /home/hackerb9/foo/rltest.c:45
    #13 0xb7044a62 in __libc_start_main
(/lib/i386-linux-gnu/i686/cmov/libc.so.6+0x19a62)
    #14 0x8049bb0 (/home/hackerb9/foo/rltest+0x8049bb0)

  AddressSanitizer can not provide additional info.
  SUMMARY: AddressSanitizer: SEGV ??:0 ??
  ==13761==ABORTING

$ cat B-heap-overflow.data | ./rltest >/dev/null
  ==13764==ERROR: AddressSanitizer: heap-buffer-overflow on address
0xb4700a78 at pc 0x808f735 bp 0xbfaaa858 sp 0xbfaaa84c
  READ of size 4 at 0xb4700a78 thread T0
    #0 0x808f734 in _rl_copy_to_kill_ring
/home/hackerb9/foo/readline-7.0/kill.c:120
    #1 0x8090f52 in region_kill_internal
/home/hackerb9/foo/readline-7.0/kill.c:421
    #2 0x809104c in rl_kill_region /home/hackerb9/foo/readline-7.0/kill.c:444
    #3 0x804b52b in _rl_dispatch_subseq
/home/hackerb9/foo/readline-7.0/readline.c:859
    #4 0x804b0ed in _rl_dispatch /home/hackerb9/foo/readline-7.0/readline.c:802
    #5 0x804a90e in readline_internal_char
/home/hackerb9/foo/readline-7.0/readline.c:629
    #6 0x804a9a2 in readline_internal_charloop
/home/hackerb9/foo/readline-7.0/readline.c:656
    #7 0x804a9c3 in readline_internal
/home/hackerb9/foo/readline-7.0/readline.c:670
    #8 0x8049fc7 in readline /home/hackerb9/foo/readline-7.0/readline.c:376
    #9 0x8049d48 in rl_gets /home/hackerb9/foo/rltest.c:73
    #10 0x8049cf6 in main /home/hackerb9/foo/rltest.c:45
    #11 0xb7010a62 in __libc_start_main
(/lib/i386-linux-gnu/i686/cmov/libc.so.6+0x19a62)
    #12 0x8049bb0 (/home/hackerb9/foo/rltest+0x8049bb0)

  0xb4700a78 is located 0 bytes to the right of 40-byte region
[0xb4700a50,0xb4700a78)
  allocated by thread T0 here:
    #0 0xb723e954 in realloc (/usr/lib/i386-linux-gnu/libasan.so.1+0x4e954)
    #1 0x80b29ae in xrealloc /home/hackerb9/foo/readline-7.0/xmalloc.c:74
    #2 0x808f7aa in _rl_copy_to_kill_ring
/home/hackerb9/foo/readline-7.0/kill.c:125
    #3 0x808fb78 in rl_kill_text /home/hackerb9/foo/readline-7.0/kill.c:183
    #4 0x80902c6 in rl_kill_full_line /home/hackerb9/foo/readline-7.0/kill.c:303
    #5 0x804b52b in _rl_dispatch_subseq
/home/hackerb9/foo/readline-7.0/readline.c:859
    #6 0x804b0ed in _rl_dispatch /home/hackerb9/foo/readline-7.0/readline.c:802
    #7 0x804a90e in readline_internal_char
/home/hackerb9/foo/readline-7.0/readline.c:629
    #8 0x804a9a2 in readline_internal_charloop
/home/hackerb9/foo/readline-7.0/readline.c:656
    #9 0x804a9c3 in readline_internal
/home/hackerb9/foo/readline-7.0/readline.c:670
    #10 0x8049fc7 in readline /home/hackerb9/foo/readline-7.0/readline.c:376
    #11 0x8049d48 in rl_gets /home/hackerb9/foo/rltest.c:73
    #12 0x8049cf6 in main /home/hackerb9/foo/rltest.c:45
    #13 0xb7010a62 in __libc_start_main
(/lib/i386-linux-gnu/i686/cmov/libc.so.6+0x19a62)
 SUMMARY: AddressSanitizer: heap-buffer-overflow
/home/hackerb9/foo/readline-7.0/kill.c:120 _rl_copy_to_kill_ring
 Shadow bytes around the buggy address:
  0x368e00f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x368e0100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x368e0110: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x368e0120: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x368e0130: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x368e0140: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00[fa]
  0x368e0150: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x368e0160: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fd
  0x368e0170: fa fa fd fd fd fd fd fd fa fa 00 00 00 00 03 fa
  0x368e0180: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x368e0190: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
 Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Contiguous container OOB:fc
  ASan internal:           fe
  ==13764==ABORTING

$ cat C-infiniteloop.data | ./rltest > /dev/null
  [No output. Process just goes into an infinite loop.]

rltest.c
Description: Text Data

A-nullpointer.data
Description: Binary data

B-heap-overflow.data
Description: Binary data

C-infiniteloop.data
Description: Binary data