search

troydhanson / uthash

C macros for hash tables and more
Other
4.18k stars 926 forks source link

hashscan: Possible heap buffer overflow #183

Closed clemensg closed 5 years ago

clemensg commented 5 years ago

Hi,

I tried to run a cross-compiled hashscan (from the master branch) for 32-Bit ARM and it crashed with the following output:

malloc(): invalid next size (unsorted)
Aborted (core dumped)

I then recompiled with -fsanitize=address and got this at runtime:

=================================================================                                                                                                                                     [7/203]
==500==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x71e007b4 at pc 0x768f5858 bp 0x7eee963c sp 0x7eee9594
WRITE of size 8 at 0x71e007b4 thread T0
    #0 0x768f5854 in __interceptor_read (/lib/libasan.so.5+0x4f854)
    #1 0x13eec in read_mem /home/clemens/foo/hashscan.c:147
    #2 0x15500 in found /home/clemens/foo/hashscan.c:267
    #3 0x16fa4 in sigscan /home/clemens/foo/hashscan.c:474
    #4 0x17fcc in scan /home/clemens/foo/hashscan.c:632
    #5 0x185b8 in main /home/clemens/foo/hashscan.c:673
    #6 0x76279d88 in __libc_start_main (/lib/libc.so.6+0x1ad88)

0x71e007b4 is located 0 bytes to the right of 4-byte region [0x71e007b0,0x71e007b4)
allocated by thread T0 here:
    #0 0x76a337a8 in __interceptor_malloc (/lib/libasan.so.5+0x18d7a8)
    #1 0x153e4 in found /home/clemens/foo/hashscan.c:260
    #2 0x16fa4 in sigscan /home/clemens/foo/hashscan.c:474
    #3 0x17fcc in scan /home/clemens/foo/hashscan.c:632
    #4 0x185b8 in main /home/clemens/foo/hashscan.c:673
    #5 0x76279d88 in __libc_start_main (/lib/libc.so.6+0x1ad88)

SUMMARY: AddressSanitizer: heap-buffer-overflow (/lib/libasan.so.5+0x4f854) in __interceptor_read
Shadow bytes around the buggy address:
  0x2e3c00a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c00b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c00c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c00d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c00e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x2e3c00f0: fa fa fa fa fa fa[04]fa fa fa fa fa fa fa fa fa
  0x2e3c0100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c0110: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c0120: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c0130: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x2e3c0140: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 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
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==500==ABORTING

Operating system is Linux 5.3.5. Glibc is 2.30, GCC is 9.2 and the target is a Cortex A9 with ARMv7-A ISA.

I can't reproduce the issue on my x64 development machine.

Quuxplusone commented 5 years ago

Hashscan is a bit of a hack; it's probably finding a range of bytes that happens to accidentally match the signature a0 11 1f e1, and then everything naturally goes off the rails. Can you post a complete transcript — what command line did you run, what output did you see prior to the crash. Also, please try with a checkout that includes commit 97826f5a37ab3d42a585b1fdc57ad89f0662e5b9, and add -vv to your hashscan command line. That should at least confirm my suspicion that the tbl->num_buckets being inferred in your case is something huge and inappropriate.

clemensg commented 5 years ago

Hi, thanks for the quick response.

I did just run ./hashscan with the PID of the process I wanted to analyze. The linemalloc(): invalid next size (unsorted) was the first output.

I tried again with the latest commit as well as -vvv and interestingly it did not crash.. very odd. Even one -v seems to be enough for it to not crash.

tbl->num_buckets is 32, according to the output:

$ ./hashscan -vvv 271
attaching to peer
waiting for peer to suspend temporarily
opening peer memory map [/proc/271/maps]
listing peer virtual memory areas
peer has 43 virtual memory areas
opening peer memory
scanning peer memory for hash table signatures
found signature at peer 0x22cf910
reading table at peer 0x22cf8e8
reading 32 buckets at peer 0x22c8c38
scanning 32 peer buckets
bucket 0 has 4 items
scanning bucket 0 chain:
bucket 1 has 1 items
scanning bucket 1 chain:
bucket 2 has 4 items
scanning bucket 2 chain:
bucket 3 has 3 items
scanning bucket 3 chain:
bucket 4 has 1 items
scanning bucket 4 chain:
bucket 5 has 1 items
scanning bucket 5 chain:
bucket 6 has 2 items
scanning bucket 6 chain:
bucket 7 has 1 items
scanning bucket 7 chain:
bucket 8 has 1 items
scanning bucket 8 chain:
bucket 9 has 3 items
scanning bucket 9 chain:
bucket 10 has 4 items
scanning bucket 10 chain:
bucket 11 has 3 items
scanning bucket 11 chain:
bucket 12 has 4 items
scanning bucket 12 chain:
bucket 13 has 0 items
scanning bucket 13 chain:
bucket 14 has 2 items
scanning bucket 14 chain:
bucket 15 has 3 items
scanning bucket 15 chain:
bucket 16 has 1 items
scanning bucket 16 chain:
bucket 17 has 2 items
scanning bucket 17 chain:
bucket 18 has 2 items
scanning bucket 18 chain:
bucket 19 has 5 items
scanning bucket 19 chain:
bucket 20 has 5 items
scanning bucket 20 chain:
bucket 21 has 2 items
scanning bucket 21 chain:
bucket 22 has 2 items
scanning bucket 22 chain:
bucket 23 has 2 items
scanning bucket 23 chain:
bucket 24 has 4 items
scanning bucket 24 chain:
bucket 25 has 2 items
scanning bucket 25 chain:
bucket 26 has 0 items
scanning bucket 26 chain:
bucket 27 has 2 items
scanning bucket 27 chain:
bucket 28 has 3 items
scanning bucket 28 chain:
bucket 29 has 0 items
scanning bucket 29 chain:
bucket 30 has 3 items
scanning bucket 30 chain:
bucket 31 has 4 items
scanning bucket 31 chain:
looking for bloom signature at peer 0x22cf914
Address            ideal    items  buckets mc fl bloom   sat fcn keys saved to
------------------ ----- -------- -------- -- -- ----- ----- --- -------------
0x22cf8e8           100%       76       32  5 ok             JEN
detaching and resuming peer
Quuxplusone commented 5 years ago

Hm. Does it reliably crash with no -v, and reliably not-crash with -v? If so, that's very weird. I probably have no further help I can give here... but at least you know a workaround!

clemensg commented 5 years ago

Hm. Does it reliably crash with no -v, and reliably not-crash with -v?

Yes, it does. Very weird indeed.

Yeah, thanks for the help anyway, I now got the information I wanted.