During fuzzing I found that small grammars using explicit repetition (e.g. {63}) combined with * and + quantifiers trigger unbounded memory growth in check_for_ambiguity(), causing the process to exceed 2 GB RAM.
Confirmed on the Try-Owl playground (ianh.github.io/owl/try/) which shows "critical error: out of memory".
PoC (54 bytes):
x = '���'string'�'+
'���'string'�'+
{64}{36}
libFuzzer output:
==ERROR: libFuzzer: out-of-memory (used: 2112Mb; limit: 2048Mb)
#1 checked_calloc alloc.h:9
#2 state_pair_table_rehash 4-check-for-ambiguity.c:833
#3 state_pair_table_add 4-check-for-ambiguity.c:780
#4 search_state_pairs 4-check-for-ambiguity.c:402
#5 check_for_ambiguity 4-check-for-ambiguity.c:258
Root cause: the state-pair table in search_state_pairs() grows without bound. A warning when large repetition counts are detected, or a cap on the number of state pairs, would prevent users from accidentally freezing their build pipeline.
During fuzzing I found that small grammars using explicit repetition (e.g. {63}) combined with * and + quantifiers trigger unbounded memory growth in check_for_ambiguity(), causing the process to exceed 2 GB RAM.
Confirmed on the Try-Owl playground (ianh.github.io/owl/try/) which shows "critical error: out of memory".
PoC (54 bytes):
x = '���'string'�'+
'���'string'�'+
{64}{36}
libFuzzer output:
==ERROR: libFuzzer: out-of-memory (used: 2112Mb; limit: 2048Mb)
Root cause: the state-pair table in search_state_pairs() grows without bound. A warning when large repetition counts are detected, or a cap on the number of state pairs, would prevent users from accidentally freezing their build pipeline.