buzz-lang/Buzz

parse_modulo in buzzparser.c can seg fault due to stack size

rwhitworth opened this issue · 4 comments

I was able to craft an input that triggered parse_modulo tons of times and eventually causes a segmentation fault because the stack is fully consumed.

I found this can 'resolve' the problem inside the parse_modulo function, but I'm sure it isn't the correct resolution. Is this something worth spending more time on? I mistakenly did not save the input file but could probably recreate it if it is needed.

static int counter = 0;
counter++;
if (counter > 1000) {
  return NULL;
}

I am aware that stack bombs will cause a segfault. I'd like to see the input file to verify if the input you tried is a likely occurrence or just a corner case. In principle I wouldn't like to hardcode a stack limit, I'd keep that as a final option.

output.txt

gdb bt output looks like:

#0  0x00007f4e18273c8b in _int_malloc (av=av@entry=0x7f4e18594b00 <main_arena>, bytes=bytes@entry=40)
    at malloc.c:3387
#1  0x00007f4e18275f34 in __GI___libc_malloc (bytes=40) at malloc.c:2928
#2  0x000000000040e71f in buzzlex_newtok (type=BUZZTOK_PAROPEN, line=25, col=<optimized out>,
    fname=<optimized out>, value=<optimized out>) at buzzlex.c:183
#3  buzzlex_nexttok (lex=<optimized out>) at buzzlex.c:378
#4  0x000000000041ffaa in parse_operand (par=0x18a0010) at buzzparser.c:933
#5  0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#6  parse_modulo (par=0x18a0010) at buzzparser.c:882
#7  0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#8  0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#9  0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#10 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#11 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#12 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#13 parse_modulo (par=0x18a0010) at buzzparser.c:882
#14 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#15 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#16 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#17 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#18 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#19 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#20 parse_modulo (par=0x18a0010) at buzzparser.c:882
#21 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#22 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#23 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#24 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#25 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#26 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#27 parse_modulo (par=0x18a0010) at buzzparser.c:882
#28 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#29 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#30 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#31 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#32 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#33 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#34 parse_modulo (par=0x18a0010) at buzzparser.c:882
#35 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#36 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#37 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#38 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#39 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#40 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#41 parse_modulo (par=0x18a0010) at buzzparser.c:882
#42 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#43 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#44 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#45 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#46 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#47 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892
#48 parse_modulo (par=0x18a0010) at buzzparser.c:882
#49 0x000000000041f82a in parse_product (par=0x18a0010) at buzzparser.c:866
#50 0x000000000041c580 in parse_expression (par=0x18a0010) at buzzparser.c:854
#51 0x000000000041f354 in parse_comparison (par=0x18a0010) at buzzparser.c:734
#52 0x000000000041da7b in parse_condition (par=0x18a0010) at buzzparser.c:722
#53 0x000000000041ffdf in parse_operand (par=0x18a0010) at buzzparser.c:934
#54 0x000000000041fa59 in parse_power (par=0x18a0010) at buzzparser.c:892

Wow, that input is seriously evil 😄 I guess I'll add something to newtok to make the parser fail gracefully. Working on it...

So, judging from the output, this is due to the fact that the parser is recursive, and with the input you're trying the stack gets past the maximum size and overflows. Fixing this would entail changing the code so the parser iterates rather than recurs. I'd say that I leave this change for future work, since the parser will get redone with LLVM at some point anyway 😄