Hi! > Le 28 mars 2019 à 15:47, wcventure <[email protected]> a écrit : > > Hi there, > > Our fuzzer
Bummer, I meant to run a fuzzer on Bison, but you've been faster :) > found some Heap-buffer-overflow issue in build_relations function in > src/lalr.c in Bison 3.3, the recent release version. > A crafted input file can cause segment faults and I have confirmed them with > address sanitizer too. I was able to reproduce this bug. Yes, it is present in the latest release, but it's also present in the oldest release of Bison :) Here is my fix. It passes successfully the three files you sent. Thanks a lot for this report! commit 8c1d4b2784d638d187ea9c647a2d871a9a9634c8 Author: Akim Demaille <[email protected]> Date: Fri Mar 29 22:37:51 2019 +0100 lalr: fix segmentation violation The "includes" relation [DeRemer 1982] is between gotos, so of course, for a given goto, there cannot be more that ngotos (number of gotos) images. But we manipulate the set of images of a goto as a list, without checking that an image was not already introduced. So we can "register" way more images than ngotos, leading to a crash (heap buffer overflow). Reported by wcventure. http://lists.gnu.org/archive/html/bug-bison/2019-03/msg00007.html For the records, this bug is present in the first committed version of Bison. * src/lalr.c (build_relations): Don't insert the same goto several times. * tests/sets.at (Build Relations): New. diff --git a/THANKS b/THANKS index 6ddfe694..3a8baf3f 100644 --- a/THANKS +++ b/THANKS @@ -176,6 +176,7 @@ Tommy Nordgren [email protected] Troy A. Johnson [email protected] Tys Lefering [email protected] Valentin Tolmer [email protected] +wcventure [email protected] Victor Khomenko [email protected] Victor Zverovich [email protected] Vin Shelton [email protected] diff --git a/src/lalr.c b/src/lalr.c index a1f3903e..c48c726d 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -271,7 +271,7 @@ build_relations (void) int nedges = 0; for (rule **rulep = derives[var - ntokens]; *rulep; ++rulep) { - rule const* r = *rulep; + rule const *r = *rulep; state *s = states[src]; path[0] = s->number; @@ -295,7 +295,19 @@ build_relations (void) for (int p = length - 2; 0 <= p && ISVAR (r->rhs[p]); --p) { symbol_number sym = item_number_as_symbol_number (r->rhs[p]); - edge[nedges++] = map_goto (path[p], sym); + goto_number g = map_goto (path[p], sym); + /* Insert G if not already in EDGE. + FIXME: linear search. A bitset instead? */ + { + bool found = false; + for (int j = 0; !found && j < nedges; ++j) + found = edge[j] == g; + if (!found) + { + assert (nedges < ngotos + 1); + edge[nedges++] = map_goto (path[p], sym); + } + } if (!nullable[sym - ntokens]) break; } diff --git a/tests/sets.at b/tests/sets.at index 3ad1a855..a7db340e 100644 --- a/tests/sets.at +++ b/tests/sets.at @@ -303,6 +303,49 @@ AT_CLEANUP +## ----------------- ## +## Build relations. ## +## ----------------- ## + +AT_SETUP([Build relations]) + +# The "includes" relation [DeRemer 1982] is between gotos, so of +# course, for a given goto, there cannot be more that ngotos (number +# of gotos) images. But we manipulate the set of images of a goto as +# a list, without checking that an image was not already introduced. +# So we can "register" way more images than ngotos, leading to a crash +# (heap buffer overflow). +# +# http://lists.gnu.org/archive/html/bug-bison/2019-03/msg00007.html + +AT_DATA([input.y], +[[%% +expr: term | term | term | term | term | term +term: 'n' +]]) + +AT_BISON_CHECK([[-fcaret input.y]], [], [], +[[input.y: warning: 5 reduce/reduce conflicts [-Wconflicts-rr] +input.y:2.14-17: warning: rule useless in parser due to conflicts [-Wother] + expr: term | term | term | term | term | term + ^~~~ +input.y:2.21-24: warning: rule useless in parser due to conflicts [-Wother] + expr: term | term | term | term | term | term + ^~~~ +input.y:2.28-31: warning: rule useless in parser due to conflicts [-Wother] + expr: term | term | term | term | term | term + ^~~~ +input.y:2.35-38: warning: rule useless in parser due to conflicts [-Wother] + expr: term | term | term | term | term | term + ^~~~ +input.y:2.42-45: warning: rule useless in parser due to conflicts [-Wother] + expr: term | term | term | term | term | term + ^~~~ +]]) + +AT_CLEANUP + + ## ----------------- ## ## Reduced Grammar. ## ## ----------------- ##
