Re: [PATCH 1/3] dfa: fix dfa-heap-overrun failure

[Norihiro Tanaka]

On Sun, 13 Sep 2020 18:41:49 -0700
Paul Eggert <eggert@cs.ucla.edu> wrote:

> * lib/dfa.c (reorder_tokens): When setting
> map[d->follows[i].elems[j].index], instead of incorrectly assuming
> that (i < d->follows[i].elems[j].index), use two loops, one to set
> the map array and the other to use it.  The incorrect assumption
> caused some elements to be missed, and this in turn caused grep's
> dfa-heap-overrun test to fail on Solaris 10 sparc when compiled
> with GCC.  I found this bug while investigating
> https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183
> and I think the bug also occurs on GNU/Linux but with more-subtle
> symptoms.  The bug predates the recent dfa.c changes; perhaps the
> recent changes make the bug more likely.
> ---
>  ChangeLog | 15 +++++++++++++++
>  lib/dfa.c | 12 ++++++------
>  2 files changed, 21 insertions(+), 6 deletions(-)
> 
> diff --git a/ChangeLog b/ChangeLog
> index a5c14c45e..1b5720761 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,18 @@
> +2020-09-13  Paul Eggert  <eggert@cs.ucla.edu>
> +
> +     dfa: fix dfa-heap-overrun failure
> +     * lib/dfa.c (reorder_tokens): When setting
> +     map[d->follows[i].elems[j].index], instead of incorrectly assuming
> +     that (i < d->follows[i].elems[j].index), use two loops, one to set
> +     the map array and the other to use it.  The incorrect assumption
> +     caused some elements to be missed, and this in turn caused grep's
> +     dfa-heap-overrun test to fail on Solaris 10 sparc when compiled
> +     with GCC.  I found this bug while investigating
> +     
> https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183
> +     and I think the bug also occurs on GNU/Linux but with more-subtle
> +     symptoms.  The bug predates the recent dfa.c changes; perhaps the
> +     recent changes make the bug more likely.
> +
>  2020-09-13  Bruno Haible  <bruno@clisp.org>
>  
>       parse-datetime: Make the build rule work with parallel 'make'.
> diff --git a/lib/dfa.c b/lib/dfa.c
> index 0f0764887..4992bcaf2 100644
> --- a/lib/dfa.c
> +++ b/lib/dfa.c
> @@ -2519,6 +2519,11 @@ reorder_tokens (struct dfa *d)
>    else
>      multibyte_prop = NULL;
>  
> +  for (idx_t i = 0; i < d->tindex; i++)
> +    for (idx_t j = 0; j < d->follows[i].nelem; j++)
> +      if (map[d->follows[i].elems[j].index] == -1)
> +        map[d->follows[i].elems[j].index] = nleaves++;
> +
>    for (idx_t i = 0; i < d->tindex; i++)
>      {
>        if (map[i] == -1)
> @@ -2537,12 +2542,7 @@ reorder_tokens (struct dfa *d)
>          multibyte_prop[map[i]] = d->multibyte_prop[i];
>  
>        for (idx_t j = 0; j < d->follows[i].nelem; j++)
> -        {
> -          if (map[d->follows[i].elems[j].index] == -1)
> -            map[d->follows[i].elems[j].index] = nleaves++;
> -
> -          d->follows[i].elems[j].index = map[d->follows[i].elems[j].index];
> -        }
> +        d->follows[i].elems[j].index = map[d->follows[i].elems[j].index];
>  
>        qsort (d->follows[i].elems, d->follows[i].nelem,
>               sizeof *d->follows[i].elems, compare);
> -- 
> 2.17.1
> 

Thanks for adjusting and fixing.  I don't know why your patch fixes the
bug.

When setting map[d->follows[i].elems[j].index], the assumption that
(i < d->follows[i].elems[j].index) is incorrect.  However when
(i >= d->follows[i].elems[j].index), it seems that
map[d->follows[i].elems[j].index] has been already set a value more than 0.

What case violates this assumption?

In fact, in dfa-heap-overrun test, assign as following sequencely.  It
seems that follows the assumption and it does not crush.

 0:BEG 1:BEGLINE 2:0x20 3:OR 4:STAR 5:0x61 6:0x62 7:OR 8:STAR 9:CAT
10:0x63 11:0x64 12:OR 13:STAR 14:CAT 15:0x20 16:ENDLINE 17:OR 18:CAT 19:END
20:CAT 21:CAT

at i = 0
d->follows[0].elems[0].index = 2 -> map[2] = 1
d->follows[0].elems[1].index = 5 -> map[5] = 2
d->follows[0].elems[2].index = 6 -> map[6] = 3
d->follows[0].elems[3].index = 10 -> map[10] = 4
d->follows[0].elems[4].index = 11 -> map[11] = 5
d->follows[0].elems[5].index = 15 -> map[15] = 6

Thanks,
Norihiro