GNU bug report logs - #19061
[PATCH] dfa: building superset, access to unallocated memory

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 19061 in the body.
You can then email your comments to 19061 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: bug-grep <at> gnu.org
Subject: [PATCH] dfa: building superset, access to unallocated memory
Date: Sat, 15 Nov 2014 18:11:32 +0900

[Message part 1 (text/plain, inline)]

If original DFA does not have any CSETs, no memory allocated for CSET.
Even then DFA try to copy CSET from original DFA to the superset.  As
a result, it is caused to access to unallocated memory.  We have no test
case so that it is very difficult that we always reproduce this bug, as
CSET may be added only one in building superset.

[0001-dfa-building-superset-access-to-unallocated-memory.patch (text/plain, attachment)]

Message #8 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 19061 <at> debbugs.gnu.org
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sat, 15 Nov 2014 10:00:49 -0800

On Sat, Nov 15, 2014 at 1:11 AM, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> If original DFA does not have any CSETs, no memory allocated for CSET.
> Even then DFA try to copy CSET from original DFA to the superset.  As
> a result, it is caused to access to unallocated memory.  We have no test
> case so that it is very difficult that we always reproduce this bug, as
> CSET may be added only one in building superset.

Thank you for the patch.
That seems like a fine change, but so far, I cannot see how
it avoids accessing uninitialized memory.
I do see that it fixes an error whereby memcpy was being
called with its 2nd argument NULL, though in each case,
the third argument is always 0.  Passing a NULL pointer as
the 2nd argument to memcpy is officially "undefined
behavior", and I confirmed that building with gcc and its
"undefined behavior sanitizer", the problem was exposed,
and that your patch fixes it.

Do you know of a way to make grep crash, as stated in your
proposed NEWS entry?  If so, please give details.

It is UB after all.  Perhaps you found a system whose memcpy
dereferences the source pointer even when the size is 0?

Message #11 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 19061 <at> debbugs.gnu.org
Subject: Re: bug#19061: [PATCH] dfa: building superset, access to unallocated
 memory
Date: Sat, 15 Nov 2014 12:59:13 -0800

Jim Meyering wrote:
> Perhaps you found a system whose memcpy
> dereferences the source pointer even when the size is 0?

That seems pretty unlikely, on a flat-address-space machine.  And grep already 
assumes a flat address space, since gnulib does.

Message #14 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 19061 <at> debbugs.gnu.org
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sun, 16 Nov 2014 10:06:41 +0900

On Sat, 15 Nov 2014 10:00:49 -0800
Jim Meyering <jim <at> meyering.net> wrote:
> Thank you for the patch.
> That seems like a fine change, but so far, I cannot see how
> it avoids accessing uninitialized memory.
> I do see that it fixes an error whereby memcpy was being
> called with its 2nd argument NULL, though in each case,
> the third argument is always 0.  Passing a NULL pointer as
> the 2nd argument to memcpy is officially "undefined
> behavior", and I confirmed that building with gcc and its
> "undefined behavior sanitizer", the problem was exposed,
> and that your patch fixes it.
> 
> Do you know of a way to make grep crash, as stated in your
> proposed NEWS entry?  If so, please give details.
> 
> It is UB after all.  Perhaps you found a system whose memcpy
> dereferences the source pointer even when the size is 0?

Thanks for the review.

I ran accross this problem when I made next improvement.  If size is 0,
when dfa_charclass_index has been called, the crash was caused.  And If
I fixed it, the crash was not caused.  So I think that it is a bug.

However, I deleted the branch as the improvement was bad.  And I cannot
see cause of the bug in the source code.  I seem that the code has no bug.
Further more, I could not reproduce it, though I re-wrote a similar code
to the branch.

Possibly other changes which I made are bad, and it might cause a
buffer-overrun and override memory range for characlasses in the branch.

Message #17 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 19061 <19061 <at> debbugs.gnu.org>
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sat, 15 Nov 2014 22:27:50 -0800

[Message part 1 (text/plain, inline)]

On Sat, Nov 15, 2014 at 5:06 PM, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> On Sat, 15 Nov 2014 10:00:49 -0800
> Jim Meyering <jim <at> meyering.net> wrote:
>> Thank you for the patch.
>> That seems like a fine change, but so far, I cannot see how
>> it avoids accessing uninitialized memory.
>> I do see that it fixes an error whereby memcpy was being
>> called with its 2nd argument NULL, though in each case,
>> the third argument is always 0.  Passing a NULL pointer as
>> the 2nd argument to memcpy is officially "undefined
>> behavior", and I confirmed that building with gcc and its
>> "undefined behavior sanitizer", the problem was exposed,
>> and that your patch fixes it.
>>
>> Do you know of a way to make grep crash, as stated in your
>> proposed NEWS entry?  If so, please give details.
>>
>> It is UB after all.  Perhaps you found a system whose memcpy
>> dereferences the source pointer even when the size is 0?
>
> Thanks for the review.
>
> I ran accross this problem when I made next improvement.  If size is 0,
> when dfa_charclass_index has been called, the crash was caused.  And If
> I fixed it, the crash was not caused.  So I think that it is a bug.
>
> However, I deleted the branch as the improvement was bad.  And I cannot
> see cause of the bug in the source code.  I seem that the code has no bug.
> Further more, I could not reproduce it, though I re-wrote a similar code
> to the branch.
>
> Possibly other changes which I made are bad, and it might cause a
> buffer-overrun and override memory range for characlasses in the branch.

Thanks for confirming.
In that case, since I see no harm in calling xnmalloc with N = 0, I
will use a more conservative change: guard only the undefined use of
memcpy.
I've left your name on this amended patch.

[0001-dfa-avoid-undefined-behavior.patch (application/octet-stream, attachment)]

Message #20 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 19061 <19061 <at> debbugs.gnu.org>
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sun, 16 Nov 2014 18:18:04 +0900

On Sat, 15 Nov 2014 22:27:50 -0800
Jim Meyering <jim <at> meyering.net> wrote:
> Thanks for confirming.
> In that case, since I see no harm in calling xnmalloc with N = 0, I
> will use a more conservative change: guard only the undefined use of
> memcpy.
> I've left your name on this amended patch.

Thanks for the ajustment.  You are right, but the purpose of the code
is to make a clone of original DFA.  If we do not guard xnmalloc, when
calloc is 0, charclasses is NULL in original DFA, and it is *NOT* NULL
in the superset.  I think that it is not right logically.

Message #23 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 19061 <19061 <at> debbugs.gnu.org>
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sun, 16 Nov 2014 07:48:34 -0800

On Sun, Nov 16, 2014 at 1:18 AM, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> On Sat, 15 Nov 2014 22:27:50 -0800
> Jim Meyering <jim <at> meyering.net> wrote:
>> Thanks for confirming.
>> In that case, since I see no harm in calling xnmalloc with N = 0, I
>> will use a more conservative change: guard only the undefined use of
>> memcpy.
>> I've left your name on this amended patch.
>
> Thanks for the ajustment.  You are right, but the purpose of the code
> is to make a clone of original DFA.  If we do not guard xnmalloc, when
> calloc is 0, charclasses is NULL in original DFA, and it is *NOT* NULL
> in the superset.  I think that it is not right logically.

Does some code assume that V->charclasses != NULL implies
0 < V->calloc? I would argue that such code is incorrect.  I.e.,
in the degenerate case (calloc == 0), the code should not
distinguish between a NULL charclasses member and one
that points to a malloc'd buffer of length 0.

Message #28 received at 19061-done <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 19061 <19061-done <at> debbugs.gnu.org>
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Sun, 16 Nov 2014 07:49:37 -0800

I have pushed that change and am preparing another snapshot.

Message #31 received at 19061 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 19061 <19061 <at> debbugs.gnu.org>
Subject: Re: bug#19061: [PATCH] dfa: building superset,
 access to unallocated memory
Date: Mon, 17 Nov 2014 07:56:13 +0900

On Sun, 16 Nov 2014 07:48:34 -0800
Jim Meyering <jim <at> meyering.net> wrote:
> Does some code assume that V->charclasses != NULL implies
> 0 < V->calloc? I would argue that such code is incorrect.  I.e.,
> in the degenerate case (calloc == 0), the code should not
> distinguish between a NULL charclasses member and one
> that points to a malloc'd buffer of length 0.

Thanks for the pushing.  I understood that you said.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.