orangeduck / tgc

A Tiny Garbage Collector for C
Other
968 stars 64 forks source link

Stack Buffer Overflow in `tgc_mark_stack` #26

Closed RolandMarchand closed 1 year ago

RolandMarchand commented 1 year ago

I am using tgc in my linked lists, and line 12 of my project causes me issues. This test fails randomly when running the program.

Running the test through --undef-value-errors=no returns no error.

Running the test through Asan returns this, there seems to be a stack buffer overflow in tgc_mark_stack:

=================================================================
==144486==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffff1081db8 at pc 0x00000040377f bp 0x7ffff1081d50 sp 0x7ffff1081d48
READ of size 8 at 0x7ffff1081db8 thread T0
    #0 0x40377e in tgc_mark_stack ../modules/tgc/tgc.c:202
    #1 0x403d8a in tgc_mark ../modules/tgc/tgc.c:231
    #2 0x404fa9 in tgc_run ../modules/tgc/tgc.c:330
    #3 0x40519f in tgc_add ../modules/tgc/tgc.c:347
    #4 0x405573 in tgc_alloc_opt ../modules/tgc/tgc.c:418
    #5 0x4052b9 in tgc_alloc ../modules/tgc/tgc.c:364
    #6 0x4019c4 in list_push ../src/linked_list.c:12
    #7 0x4019a3 in list_make ../src/linked_list.c:7
    #8 0x40132a in main /home/roland/Programming/c/lisp/test/test_linked_list.c:15
    #9 0x7f46c604a50f in __libc_start_call_main (/lib64/libc.so.6+0x2750f)
    #10 0x7f46c604a5c8 in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x275c8)
    #11 0x4011c4 in _start (/home/roland/Programming/c/lisp/test/a.out+0x4011c4)

Address 0x7ffff1081db8 is located in stack of thread T0 at offset 40 in frame
    #0 0x403641 in tgc_mark_stack ../modules/tgc/tgc.c:187

  This frame has 1 object(s):
    [32, 40) 'stk' (line 189) <== Memory access at offset 40 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow ../modules/tgc/tgc.c:202 in tgc_mark_stack
Shadow bytes around the buggy address:
  0x10007e208360: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208370: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208380: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208390: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e2083a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007e2083b0: 00 00 f1 f1 f1 f1 00[f3]f3 f3 00 00 00 00 00 00
  0x10007e2083c0: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f1 f1 00 f2
  0x10007e2083d0: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e2083e0: 00 00 00 00 00 00 00 00 00 00 00 f3 f3 f3 f3 f3
  0x10007e2083f0: f3 f3 f3 f3 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007e208400: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
==144486==ABORTING

Is this an issue on my end, or on tgc's end?

Specs:

orangeduck commented 1 year ago

Hard to say exactly - it could well be an issue with how tgc is doing things. However you should first try making sure your tests are running one function call deeper than main:

https://github.com/orangeduck/tgc#tgc-isnt-working-when-optimisations-are-enabled

RolandMarchand commented 1 year ago

This fix seems to work. Asan still returns a stack buffer overflow error, but my tests now consistently succeed. Thank you for such a quick response.

orangeduck commented 1 year ago

The way tgc scans the stack is probably causing Asan to report it as an overflow. In general it does so safely but it definitely makes tools like memory sanitizers worried!