GNU bug report logs - #25390
Segfault with sed 4.3

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 25390 in the body.
You can then email your comments to 25390 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: "S. Gilles" <sgilles <at> math.umd.edu>
To: bug-sed <at> gnu.org
Subject: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 00:07:58 -0500

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

Hi,

I have a reliable segfault with (vanilla) sed 4.3 which does not appear
on (vanilla) 4.2.2. I've pared it down from the ./configure script (for
sed itself) to short working example, but I'm not sure if it's minimal.

I should note that this originally showed up on a bit of a snowflake
machine (armv7a+musl) when attempting to use any sort of nontrivial
./configure, but the my working example triggers the issue on a
boring amd64+glibc machine, even though that machine has no problem
./configure-ing all sorts of things.  That could mean my example is
doing bad things that the original case didn't, in which case I'll try
to cook up another example. Without further ado (please excuse the UUoc):

----8<--------8<--------8<--------8<--------8<--------8<----
#!/bin/sh

# Or wherever you have it
sed="/bin/sed"

cat <<EOF > input.txt
1
1
\$LINENO \$LINEN
2
EOF

cat input.txt |
"${sed}" 's/\$LINENO.*/&-/
t lineno
:lineno
N
:loop
s/\$LINENO\(.*\n\)/\1/' > out.txt
----8<--------8<--------8<--------8<--------8<--------8<----

-- 
S. Gilles

[signature.asc (application/pgp-signature, inline)]

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

From: "S. Gilles" <sgilles <at> math.umd.edu>
To: bug-sed <at> gnu.org
Subject: Re: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 00:31:17 -0500

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

On 2017-01-08T00:07:58-0500, S. Gilles wrote:
> Hi,
> 
> I have a reliable segfault with (vanilla) sed 4.3 which does not appear
> on (vanilla) 4.2.2. I've pared it down from the ./configure script (for
> sed itself) to short working example, but I'm not sure if it's minimal.

Apologies for the immediate follow-up post, but I've bisected (doing a
./bootstrap && ./configure && make at each step, which I hope should be
sufficient) this crash to commit

    5af42765d6d2255a04efa4737870f15e11e149a4

    gnulib: update to latest

Hopefully this is helpful.

-- 
S. Gilles

[signature.asc (application/pgp-signature, inline)]

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

From: Assaf Gordon <assafgordon <at> gmail.com>
To: "S. Gilles" <sgilles <at> math.umd.edu>
Cc: 25390 <at> debbugs.gnu.org, "bug-gnulib <at> gnu.org List" <bug-gnulib <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 12:01:11 -0500

Hello,

> On Jan 8, 2017, at 00:31, S. Gilles <sgilles <at> math.umd.edu> wrote:
> 
>> I have a reliable segfault with (vanilla) sed 4.3 which does not appear
>> on (vanilla) 4.2.2.

Thank you for the report!
I can confirm the segfault is reproducible.
The immediate cause is somewhere in gnulib's DFA module.

A shorter example:

  printf '$LINENO $LINEN\nB\n' | sed -e 'N;s/\$LINENO\(.*\n\)/\1/'

====
$ printf '$LINENO $LINEN\nB\n' > in.txt
$ printf '%s\n' 'N;s/\$LINENO\(.*\n\)/\1/' > prog.sed
$ gdb ./sed/sed
(gdb) r -f prog.sed in.txt
Starting program: /home/gordon/projects/sed/sed/sed -f prog.sed in.txt

Program received signal SIGSEGV, Segmentation fault.
0x0000000000412384 in dfaexec_main (d=0x6250b0, begin=0x623b50 "$LINENO $LINEN\nB\n", end=0x623b60 "\n", 
    allow_nl=true, count=0x0, multibyte=false) at lib/dfa.c:3169
3169                  s1 = t[*p++];
(gdb) bt
#0  0x0000000000412384 in dfaexec_main (d=0x6250b0, begin=0x623b50 "$LINENO $LINEN\nB\n", 
    end=0x623b60 "\n", allow_nl=true, count=0x0, multibyte=false) at lib/dfa.c:3169
#1  0x0000000000412833 in dfaexec_sb (d=0x6250b0, begin=0x623b50 "$LINENO $LINEN\nB\n", 
    end=0x623b60 "\n", allow_nl=true, count=0x0, backref=0x7fffffffbff7) at lib/dfa.c:3266
#2  0x00000000004128a5 in dfaexec (d=0x6250b0, begin=0x623b50 "$LINENO $LINEN\nB\n", end=0x623b60 "\n", 
    allow_nl=true, count=0x0, backref=0x7fffffffbff7) at lib/dfa.c:3287
#3  0x0000000000409359 in match_regex (regex=0x623c10, buf=0x623b50 "$LINENO $LINEN\nB\n", buflen=16, 
    buf_start_offset=0, regarray=0x61ff10 <regs>, regsize=2) at sed/regexp.c:345
#4  0x0000000000407859 in do_subst (sub=0x622500) at sed/execute.c:1030
#5  0x00000000004086d4 in execute_program (vec=0x6224d0, input=0x7fffffffe170) at sed/execute.c:1517
#6  0x0000000000408abc in process_files (the_program=0x6224d0, argv=0x7fffffffe3c0) at sed/execute.c:1687
#7  0x0000000000409d88 in main (argc=4, argv=0x7fffffffe3a8) at sed/sed.c:377
===


Looking into it, hope to have fix soon.


regards,
 - assaf

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Assaf Gordon <assafgordon <at> gmail.com>, "S. Gilles" <sgilles <at> math.umd.edu>
Cc: 25390 <at> debbugs.gnu.org, Gnulib bugs <bug-gnulib <at> gnu.org>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 12:49:42 -0800

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

Assaf Gordon wrote:
> The immediate cause is somewhere in gnulib's DFA module.

The bug was introduced in Gnulib, in commit 
403adf1b40897ba108075008c10bd38d937e1539 dated 2016-11-25 and labeled "dfa: 
addition of new state on demand". It's not a bug that grep runs into, since grep 
doesn't use the newline transition that sed does. I installed the attached patch 
to fix the Gnulib bug. I'll leave Bug#25390 open, as I assume you'll want to 
check it for 'sed' and add a test case for 'sed'.

[0001-dfa-fix-reallocation-bug-when-matching-newlines.patch (text/x-diff, attachment)]

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

From: "S. Gilles" <sgilles <at> math.umd.edu>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 25390 <at> debbugs.gnu.org, Assaf Gordon <assafgordon <at> gmail.com>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 20:17:34 -0500

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

On 2017-01-08T12:49:42-0800, Paul Eggert wrote:
> Assaf Gordon wrote:
> > The immediate cause is somewhere in gnulib's DFA module.
> 
> The bug was introduced in Gnulib, in commit
> 403adf1b40897ba108075008c10bd38d937e1539 dated 2016-11-25 and labeled "dfa:
> addition of new state on demand". It's not a bug that grep runs into, since
> grep doesn't use the newline transition that sed does. I installed the
> attached patch to fix the Gnulib bug. I'll leave Bug#25390 open, as I assume
> you'll want to check it for 'sed' and add a test case for 'sed'.

I applied the patch (after some line number tweaks) on top of the 4.3
release tarball, and I can confirm that this fixes the issue for me.
Thanks for the quick fix!

-- 
S. Gilles

[signature.asc (application/pgp-signature, inline)]

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

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 25390 <at> debbugs.gnu.org, Assaf Gordon <assafgordon <at> gmail.com>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, "S. Gilles" <sgilles <at> math.umd.edu>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Mon, 09 Jan 2017 11:38:40 +0900

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

On Sun, 8 Jan 2017 12:49:42 -0800
Paul Eggert <eggert <at> cs.ucla.edu> wrote:

> Assaf Gordon wrote:
> > The immediate cause is somewhere in gnulib's DFA module.
> 
> The bug was introduced in Gnulib, in commit 403adf1b40897ba108075008c10bd38d937e1539
> dated 2016-11-25 and labeled "dfa: addition of new state on demand".
> It's not a bug that grep runs into, since grep doesn't use the
> newline transition that sed does. I installed the attached patch to
> fix the Gnulib bug. I'll leave Bug#25390 open, as I assume you'll
> want to check it for 'sed' and add a test case for 'sed'.

Thanks for fixing quickly.

I wrote two additional patches for dfa.  First, derive number of
allocation from not argument but number of state in transition table
allocation.  Second, melt down dfastate() into build_state().  Now, I
think that there do not have to be separated.

I also wrote a simple test, but the issue are not always caused, as it
depends on state of memory.  Should we rely to complate the test on
valgrind?

[0001-dfa-simplify-transition-table-allocation.patch (text/plain, attachment)]

[0002-dfa-melt-down-dfastate-into-build_state.patch (text/plain, attachment)]

[0001-tests-new-test-for-dfa-crash-bug.patch (text/plain, attachment)]

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 25390 <at> debbugs.gnu.org, Assaf Gordon <assafgordon <at> gmail.com>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, "S. Gilles" <sgilles <at> math.umd.edu>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Sun, 8 Jan 2017 22:12:02 -0800

Norihiro Tanaka wrote:
> I wrote two additional patches for dfa.  First, derive number of
> allocation from not argument but number of state in transition table
> allocation.  Second, melt down dfastate() into build_state().  Now, I
> think that there do not have to be separated.

Thanks, I installed those two patches into Gnulib.

> I also wrote a simple test, but the issue are not always caused, as it
> depends on state of memory.  Should we rely to complate the test on
> valgrind?

Yes, I expect the 'sed' folks would prefer the test to use valgrind. You can 
look at testsuite/invalid-mb-seq-UMR.sh for an example of a test that does that.

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

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 25390 <at> debbugs.gnu.org, Assaf Gordon <assafgordon <at> gmail.com>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, "S. Gilles" <sgilles <at> math.umd.edu>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Mon, 09 Jan 2017 23:04:05 +0900

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

On Sun, 8 Jan 2017 22:12:02 -0800
Paul Eggert <eggert <at> cs.ucla.edu> wrote:

> Norihiro Tanaka wrote:
> > I wrote two additional patches for dfa.  First, derive number of
> > allocation from not argument but number of state in transition table
> > allocation.  Second, melt down dfastate() into build_state().  Now, I
> > think that there do not have to be separated.
> 
> Thanks, I installed those two patches into Gnulib.

Thanks.

> > I also wrote a simple test, but the issue are not always caused, as it
> > depends on state of memory.  Should we rely to complate the test on
> > valgrind?
> 
> Yes, I expect the 'sed' folks would prefer the test to use valgrind. You can look at testsuite/invalid-mb-seq-UMR.sh for an example of a test that does that.

Thanks, I updated the test.  The new test uses valgrind.

[0001-tests-new-test-for-dfa-crash-bug.patch (text/plain, attachment)]

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

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: 25390 <at> debbugs.gnu.org
Cc: Assaf Gordon <assafgordon <at> gmail.com>, Paul Eggert <eggert <at> cs.ucla.edu>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, "S. Gilles" <sgilles <at> math.umd.edu>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Mon, 09 Jan 2017 23:11:38 +0900

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

On Mon, 09 Jan 2017 23:04:05 +0900
Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:

> Thanks, I updated the test.  The new test uses valgrind.

Sorry, I adjusted commit log, New patch does not change
testsuite/Makefile.tests.

[0001-tests-new-test-for-dfa-crash-bug.patch (text/plain, attachment)]

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

From: Assaf Gordon <assafgordon <at> gmail.com>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 25390 <at> debbugs.gnu.org, Paul Eggert <eggert <at> cs.ucla.edu>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, "S. Gilles" <sgilles <at> math.umd.edu>,
 GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Tue, 10 Jan 2017 00:27:09 -0500

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

Hello all,

> On Jan 9, 2017, at 09:11, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> 
> Sorry, I adjusted commit log, New patch does not change
> testsuite/Makefile.tests.
> <0001-tests-new-test-for-dfa-crash-bug.patch>


Paul,
Thank you for the quick fix.

Norihiro,
Thank you for the dfa improvements and sed-tests.

Using your example of:
   printf '0123456789abcd\nx\n' | valgrind ./sed/sed 'N;s/0123456789abcd\n//'
I wasn't able to trigger the segfault (or even a valgrind warning) on sed-4.3 / x86_64.

I suggest modifying the input just a bit, making it slightly more similar to the original bug report - with it I'm able to always reproduce the segfault:
   printf "abcdefg abcdefg\nB\n" | valgrind ./sed/sed 'N;s/abcdefg.*\n//'

What do you think ?

I'm also considering duplicating the test - once with and once without valgrind.
Is this warranted or an overkill ?

Attach patch contains updated tests (and slightly modified git-comment).
The second commit updates gnulib (comes after adding the tests just temporarily, to make testing before/after gnulib update easier).

comments welcomed,
 - assaf

[newline-bug.patch (application/octet-stream, attachment)]

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

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

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Assaf Gordon <assafgordon <at> gmail.com>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 25390 <at> debbugs.gnu.org, Gnulib bugs <bug-gnulib <at> gnu.org>,
 "S. Gilles" <sgilles <at> math.umd.edu>, GNU grep developers <grep-devel <at> gnu.org>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Tue, 10 Jan 2017 01:11:36 -0800

Assaf Gordon wrote:
> I'm also considering duplicating the test - once with and once without valgrind.
> Is this warranted or an overkill ?

Sounds like overkill to me. If it works with valgrind, it'll work without.

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

From: Jim Meyering <jim <at> meyering.net>
To: Assaf Gordon <assafgordon <at> gmail.com>
Cc: 25390 <at> debbugs.gnu.org, GNU grep developers <grep-devel <at> gnu.org>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>,
 "S. Gilles" <sgilles <at> math.umd.edu>
Subject: Re: [Grep-devel] bug#25390: Segfault with sed 4.3
Date: Sat, 14 Jan 2017 15:40:31 -0800

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

On Mon, Jan 9, 2017 at 9:27 PM, Assaf Gordon <assafgordon <at> gmail.com> wrote:
> Hello all,
>
>> On Jan 9, 2017, at 09:11, Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
>>
>> Sorry, I adjusted commit log, New patch does not change
>> testsuite/Makefile.tests.
>> <0001-tests-new-test-for-dfa-crash-bug.patch>
>
>
> Paul,
> Thank you for the quick fix.
>
> Norihiro,
> Thank you for the dfa improvements and sed-tests.
>
> Using your example of:
>    printf '0123456789abcd\nx\n' | valgrind ./sed/sed 'N;s/0123456789abcd\n//'
> I wasn't able to trigger the segfault (or even a valgrind warning) on sed-4.3 / x86_64.
>
> I suggest modifying the input just a bit, making it slightly more similar to the original bug report - with it I'm able to always reproduce the segfault:
>    printf "abcdefg abcdefg\nB\n" | valgrind ./sed/sed 'N;s/abcdefg.*\n//'
>
> What do you think ?
>
> I'm also considering duplicating the test - once with and once without valgrind.
> Is this warranted or an overkill ?
>
> Attach patch contains updated tests (and slightly modified git-comment).
> The second commit updates gnulib (comes after adding the tests just temporarily, to make testing before/after gnulib update easier).

Hi Assaf,

Thank you for adjusting the tests and commit log. Those look fine.

The only problem is that the new newline-valgrind.sh test would fail
when run against an ASAN-enabled sed. That is because valgrind just
doesn't work when the binary is ASAN-enabled. So I have extemded
init.cfg's require_valgrind_ function so that it also detects this
case and skips the test. I will push the attached shortly, after which
you are welcome to push your commits.

[sed-ASAN-vs-valgrind.diff (text/plain, attachment)]

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

From: Assaf Gordon <assafgordon <at> gmail.com>
To: "S. Gilles" <sgilles <at> math.umd.edu>
Cc: 25390 <at> debbugs.gnu.org, GNU grep developers <grep-devel <at> gnu.org>,
 Gnulib bugs <bug-gnulib <at> gnu.org>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>,
 Jim Meyering <jim <at> meyering.net>
Subject: Re: bug#25390: Segfault with sed 4.3
Date: Mon, 16 Jan 2017 23:53:08 -0500

tag 25390 fixed
close 25390
thanks

Hello,

Thanks again for everyone who reported, fixed and improved sed and dfa/gnulib.


sed's update to latest gnulib is pushed here:
 http://git.savannah.gnu.org/cgit/sed.git/commit/?id=44d99bf5c98ea77de0addf55ad7fe281396de996

followed by the new test:
 http://git.savannah.gnu.org/cgit/sed.git/commit/?id=0f98f0055e4b505de2696bf862798e88a14956f9


I'm thus closing this bug,
but discussion can continue by replying to this thread.

regards,
 - assaf
 

Previous Next

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