[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [bug report] Heap-buffer-overflow issue in build_relations function
From: |
Akim Demaille |
Subject: |
Re: [bug report] Heap-buffer-overflow issue in build_relations function in src/lalr.c in Bison 3.3 |
Date: |
Sat, 30 Mar 2019 08:50:41 +0100 |
Hi!
> Le 28 mars 2019 à 15:47, wcventure <address@hidden> 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 <address@hidden>
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 address@hidden
Troy A. Johnson address@hidden
Tys Lefering address@hidden
Valentin Tolmer address@hidden
+wcventure address@hidden
Victor Khomenko address@hidden
Victor Zverovich address@hidden
Vin Shelton address@hidden
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. ##
## ----------------- ##