GNU bug report logs - #28417
ptx does not terminate when matching a zero length sentence regex

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 28417 in the body.
You can then email your comments to 28417 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: Julian Büning <julian.buening <at> rwth-aachen.de>
To: <bug-coreutils <at> gnu.org>
Cc: Oscar Soria Dustmann <Oscar.SoriaDustmann <at> comsys.rwth-aachen.de>,
 Daniel Schemmel <daniel.schemmel <at> comsys.rwth-aachen.de>
Subject: ptx does not terminate when matching a zero length sentence regex
Date: Mon, 11 Sep 2017 17:04:43 +0200

observed behavior:

$ echo | ptx -S $ &
[1] 1000
$ jobs
[1]+  Running                 echo | ptx -S $ &

expected behavior:

$ echo | ptx -S $ &
[1] 1000
[1]+  Done                    echo | ptx -S $

ptx does not terminate in case the specified sentence regex can be
matched but has a match of length zero on input that is non-empty.

The following test cases show the same behavior:
$ echo | ptx -S ^
$ echo | ptx -S "a*"
$ echo | ptx -S "\(\)"
$ echo test | ptx -S "\n*"
$ echo foo > non_empty; ptx non_empty -S $
...

In ptx.c, find_occurs_in_text() calls re_search() and uses the length of
a match (which is falsely assumed to be greater than zero) to advance a
cursor through the input. For a match length of zero, the cursor is
never advanced.

When switching on the results of re_search(), a case 0 could be added.
One possible fix would be to then abort with an error message.

We found this behavior in version 8.27 and can reproduce it in version
8.25 as well as version 8.28.

This behavior was found using Symbolic Execution techniques developed in
the course of the SYMBIOSYS research project at COMSYS, RWTH Aachen
University. This research is supported by the European Research Council
(ERC) under the EU's Horizon 2020 Research and Innovation Programme
grant agreement n. 647295 (SYMBIOSYS).

Best regards,
Julian

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

From: Bernhard Voelker <mail <at> bernhard-voelker.de>
To: Julian Büning <julian.buening <at> rwth-aachen.de>,
 28417 <at> debbugs.gnu.org
Cc: Oscar Soria Dustmann <Oscar.SoriaDustmann <at> comsys.rwth-aachen.de>,
 Daniel Schemmel <daniel.schemmel <at> comsys.rwth-aachen.de>
Subject: Re: bug#28417: ptx does not terminate when matching a zero length
 sentence regex
Date: Wed, 13 Sep 2017 23:40:42 +0200

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

On 09/11/2017 05:04 PM, Julian Büning wrote:
> observed behavior:
> 
> $ echo | ptx -S $ &
> [1] 1000
> $ jobs
> [1]+  Running                 echo | ptx -S $ &
> 
> expected behavior:
> 
> $ echo | ptx -S $ &
> [1] 1000
> [1]+  Done                    echo | ptx -S $
> 
> ptx does not terminate in case the specified sentence regex can be
> matched but has a match of length zero on input that is non-empty.
> 
> The following test cases show the same behavior:
> $ echo | ptx -S ^
> $ echo | ptx -S "a*"
> $ echo | ptx -S "\(\)"
> $ echo test | ptx -S "\n*"
> $ echo foo > non_empty; ptx non_empty -S $
> ...
> 
> In ptx.c, find_occurs_in_text() calls re_search() and uses the length of
> a match (which is falsely assumed to be greater than zero) to advance a
> cursor through the input. For a match length of zero, the cursor is
> never advanced.
> 
> When switching on the results of re_search(), a case 0 could be added.
> One possible fix would be to then abort with an error message.
> 
> We found this behavior in version 8.27 and can reproduce it in version
> 8.25 as well as version 8.28.
> 
> This behavior was found using Symbolic Execution techniques developed in
> the course of the SYMBIOSYS research project at COMSYS, RWTH Aachen
> University. This research is supported by the European Research Council
> (ERC) under the EU's Horizon 2020 Research and Innovation Programme
> grant agreement n. 647295 (SYMBIOSYS).

Good catch!
The attached patch fixes it; please check.

Have a nice day,
Berny

[0001-ptx-avoid-infloop-due-to-zero-length-matches-with-S-.patch (text/x-patch, attachment)]

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

From: Pádraig Brady <P <at> draigBrady.com>
To: Bernhard Voelker <mail <at> bernhard-voelker.de>,
 Julian Büning <julian.buening <at> rwth-aachen.de>,
 28417 <at> debbugs.gnu.org
Cc: Oscar Soria Dustmann <Oscar.SoriaDustmann <at> comsys.rwth-aachen.de>,
 Daniel Schemmel <daniel.schemmel <at> comsys.rwth-aachen.de>
Subject: Re: bug#28417: ptx does not terminate when matching a zero length
 sentence regex
Date: Wed, 13 Sep 2017 17:16:29 -0700

On 13/09/17 14:40, Bernhard Voelker wrote:
> On 09/11/2017 05:04 PM, Julian Büning wrote:
>> observed behavior:
>>
>> $ echo | ptx -S $ &
>> [1] 1000
>> $ jobs
>> [1]+  Running                 echo | ptx -S $ &
>>
>> expected behavior:
>>
>> $ echo | ptx -S $ &
>> [1] 1000
>> [1]+  Done                    echo | ptx -S $
>>
>> ptx does not terminate in case the specified sentence regex can be
>> matched but has a match of length zero on input that is non-empty.
>>
>> The following test cases show the same behavior:
>> $ echo | ptx -S ^
>> $ echo | ptx -S "a*"
>> $ echo | ptx -S "\(\)"
>> $ echo test | ptx -S "\n*"
>> $ echo foo > non_empty; ptx non_empty -S $
>> ...
>>
>> In ptx.c, find_occurs_in_text() calls re_search() and uses the length of
>> a match (which is falsely assumed to be greater than zero) to advance a
>> cursor through the input. For a match length of zero, the cursor is
>> never advanced.
>>
>> When switching on the results of re_search(), a case 0 could be added.
>> One possible fix would be to then abort with an error message.
>>
>> We found this behavior in version 8.27 and can reproduce it in version
>> 8.25 as well as version 8.28.
>>
>> This behavior was found using Symbolic Execution techniques developed in
>> the course of the SYMBIOSYS research project at COMSYS, RWTH Aachen
>> University. This research is supported by the European Research Council
>> (ERC) under the EU's Horizon 2020 Research and Innovation Programme
>> grant agreement n. 647295 (SYMBIOSYS).
> 
> Good catch!
> The attached patch fixes it; please check.

+1

Thanks to both of you

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

From: Bernhard Voelker <mail <at> bernhard-voelker.de>
To: Pádraig Brady <P <at> draigBrady.com>,
 Julian Büning <julian.buening <at> rwth-aachen.de>,
 28417-done <at> debbugs.gnu.org
Cc: Oscar Soria Dustmann <Oscar.SoriaDustmann <at> comsys.rwth-aachen.de>,
 Daniel Schemmel <daniel.schemmel <at> comsys.rwth-aachen.de>
Subject: Re: bug#28417: ptx does not terminate when matching a zero length
 sentence regex
Date: Thu, 14 Sep 2017 08:38:49 +0200

On 09/14/2017 02:16 AM, Pádraig Brady wrote:
> +1

thanks for the review, pushed.

Have a nice day,
Berny

Previous Next

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