Re: [bug report] Heap-buffer-overflow issue in build_relations function in src/lalr.c in Bison 3.3

[Akim Demaille]

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.  ##
 ## ----------------- ##