Bug 197555 - [patch] bsdgrep segfaults with --color and overlapping patterns
Summary: [patch] bsdgrep segfaults with --color and overlapping patterns
Status: Closed FIXED
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: 10.1-RELEASE
Hardware: amd64 Any
: --- Affects Some People
Assignee: Kyle Evans
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-02-12 02:11 UTC by Jason McSweeney
Modified: 2018-04-25 12:43 UTC (History)
3 users (show)

See Also:


Attachments
add an assert to printline to aid debugging (666 bytes, patch)
2015-02-12 02:11 UTC, Jason McSweeney
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jason McSweeney 2015-02-12 02:11:27 UTC
Created attachment 152888 [details]
add an assert to printline to aid debugging

My machine details

uname -a

FreeBSD vagrant-freebsd-10 10.1-RELEASE FreeBSD 10.1-RELEASE #0 r274401: Tue Nov 11 21:02:49 UTC 2014     root@releng1.nyi.freebsd.org:/usr/obj/usr/src/sys/GENERIC  amd64

On my 10.1 x86-64 machine, /usr/bin/bsdgrep segfaults when I use it like this

echo i860 | bsdgrep --color -e i860 -e i86
i860
i860
Segmentation fault (core dumped)

With color disabled, it gives the correct output

echo i860 | bsdgrep -e i860 -e i86 
i860

this is the same binary from the 10.1 x86-64 release iso

openssl md5 /usr/bin/bsdgrep
MD5(/usr/bin/bsdgrep)= 46015e84adebfbaab878a40e8e99ecfd

gdb shows this (for the released binary)

echo i860 > /tmp/p
gdb --args /usr/bin/bsdgrep --color -e i860 -e i86 /tmp/p

Program received signal SIGSEGV, Segmentation fault.
0x00000008011cca60 in memchr () from /lib/libc.so.7
(gdb) bt
#0  0x00000008011cca60 in memchr () from /lib/libc.so.7
#1  0x00000008011cc599 in fwrite () from /lib/libc.so.7
#2  0x00000008011cc43d in fwrite () from /lib/libc.so.7
#3  0x0000000000404d63 in ?? ()
#4  0x00000000004047ca in ?? ()
#5  0x00000000004038a5 in ?? ()
#6  0x00000000004023bf in ?? ()
#7  0x0000000800629000 in ?? ()
#8  0x0000000000000000 in ?? ()

I have built a debug binary from STABLE, here is the svn info

svn info
Path: .
Working Copy Root Path: /usr/home/vagrant/stable/src
URL: http://svn.freebsd.org/base/stable/10/usr.bin/grep
Relative URL: ^/stable/10/usr.bin/grep
Repository Root: http://svn.freebsd.org/base
Repository UUID: ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f
Revision: 278579
Node Kind: directory
Schedule: normal
Last Changed Author: delphij
Last Changed Rev: 278175
Last Changed Date: 2015-02-04 00:45:02 +0000 (Wed, 04 Feb 2015)

gdb gives this backtrace

Starting program: /usr/home/vagrant/stable/src/usr.bin/grep/bsdgrep --color -e i860 -e i86 /tmp/p
i860
i860

Program received signal SIGSEGV, Segmentation fault.
0x00000008011d1a60 in memchr () from /lib/libc.so.7
(gdb) bt
#0  0x00000008011d1a60 in memchr () from /lib/libc.so.7
#1  0x00000008011d1599 in fwrite () from /lib/libc.so.7
#2  0x00000008011d143d in fwrite () from /lib/libc.so.7
#3  0x00000000004062fc in printline (line=0x7fffffffe878, sep=58, matches=0x7fffffffe710, m=2) at util.c:469
#4  0x0000000000405eef in procline (l=0x7fffffffe878, nottext=0) at util.c:366
#5  0x0000000000405588 in procfile (fn=0x7fffffffed69 "/tmp/p") at util.c:231
#6  0x0000000000404292 in main (argc=7, argv=0x7fffffffeab8) at grep.c:738
(gdb) 

valgrind gives a similar result

valgrind --db-attach=yes --track-origins=yes ./bsdgrep --color -e i860 -epi86 /tmp/ 
==60168== Memcheck, a memory error detector
==60168== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==60168== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==60168== Command: ./bsdgrep --color -e i860 -e i86 /tmp/p
==60168== 
i860
==60168== Conditional jump or move depends on uninitialised value(s)
==60168==    at 0x1020E54: memchr (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==60168==    by 0x1BC8598: ??? (in /lib/libc.so.7)
==60168==    by 0x1BC843C: fwrite (in /lib/libc.so.7)
==60168==    by 0x4062FB: printline (util.c:469)
==60168==    by 0x405EEE: procline (util.c:366)
==60168==    by 0x405587: procfile (util.c:231)
==60168==    by 0x404291: main (grep.c:738)
==60168==  Uninitialised value was created by a heap allocation
==60168==    at 0x101D2B3: malloc (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==60168==    by 0x405814: grep_malloc (util.c:390)
==60168==    by 0x402CBA: grep_open (file.c:285)
==60168==    by 0x40535A: procfile (util.c:194)
==60168==    by 0x404291: main (grep.c:738)
==60168== 
==60168==

After poking around in the code, it appears that the bug manifests inside printline util.c:469

i is 1
matches[i].rm_so is a reg_off_t (int) with value 0
a is a size_t with value 4

so fwrite gets handed a really large bogus size parameter of size_t (-4)

464 		putchar(sep);
465 	/* --color and -o */
466 	if ((oflag || color) && m > 0) {
467 		for (i = 0; i < m; i++) {
468 			if (!oflag)
469 				fwrite(line->dat + a, matches[i].rm_so - a, 1,
470 				    stdout);
471 			if (color) 
472 				fprintf(stdout, "\33[%sm\33[K", color);
473 
474 				fwrite(line->dat + matches[i].rm_so, 

It appears that printline is not expecting any overlapping matches, but it has been handed two with these offsets

rm_so 0 rm_eo 4 
rm_so 0 rm_eo 3

So, either the bug is in the handling printing of the matches, or in the generation of them. 
It possibly relates to https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=197531

I have attached a patch to aid in debugging.

As a side note, I first ran into this bug on Mac OSX, where they are using a variant of bsdgrep as the the default grep
Comment 1 Jason McSweeney 2015-02-12 02:30:36 UTC
This bug also occurs on CURRENT

svn info

Path: .
Working Copy Root Path: /usr/src
URL: http://svn.freebsd.org/base/head/usr.bin/grep
Relative URL: ^/head/usr.bin/grep
Repository Root: http://svn.freebsd.org/base
Repository UUID: ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f
Revision: 278611
Node Kind: directory
Schedule: normal
Last Changed Author: ngie
Last Changed Rev: 277939
Last Changed Date: 2015-01-30 18:07:46 +0000 (Fri, 30 Jan 2015)
Comment 2 David Carlier 2015-02-19 21:17:32 UTC
Is this small patch would fix this ?
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=181263
Comment 3 Ed Maste freebsd_committer freebsd_triage 2016-03-14 15:31:49 UTC
Confirmed at r296724; I'll try to have a look at the patch in PR181263.
Comment 4 Kyle Evans freebsd_committer freebsd_triage 2017-01-21 05:07:49 UTC
(In reply to Ed Maste from comment #3)

The issue in this bug is also fixed by my partial rework of procline() bits in bug #195763. Bug #181263, on the other hand, yields some strange behavior in test case 1. Test cases 2 and 3 are indeed also fixed by my partial rework.

I will address bug #181263 separately with another patch, likely after bug #195763 gets sorted out and in.
Comment 5 commit-hook freebsd_committer freebsd_triage 2017-04-03 23:17:30 UTC
A commit references this bug:

Author: emaste
Date: Mon Apr  3 23:16:51 UTC 2017
New revision: 316477
URL: https://svnweb.freebsd.org/changeset/base/316477

Log:
  bsdgrep: fix matching behaviour

  - Set REG_NOTBOL if we've already matched beginning of line and we're
    examining later parts

  - For each pattern we examine, apply it to the remaining bits of the
    line rather than (potentially) smaller subsets

  - Check for REG_NOSUB after we've looked at all patterns initially
    matching the line

  - Keep track of the last match we made to later determine if we're
    simply not matching any longer or if we need to proceed another byte
    because we hit a zero-length match

  - Match the earliest and longest bit of each line before moving the
    beginning of what we match to further in the line, past the end of the
    longest match; this generally matches how gnugrep(1) seems to behave,
    and seems like pretty good behavior to me

  - Finally, bail out of printing any matches if we were set to print all
    (empty pattern) but -o (output matches) was set

  PR:		195763, 180990, 197555, 197531, 181263, 209116
  Submitted by:	"Kyle Evans" <kevans91@ksu.edu>
  Reviewed by:	cem
  MFC after:	1 month
  Relnotes:	Yes
  Differential Revision:	https://reviews.freebsd.org/D10104

Changes:
  head/usr.bin/grep/util.c
Comment 6 commit-hook freebsd_committer freebsd_triage 2017-04-05 18:42:04 UTC
A commit references this bug:

Author: emaste
Date: Wed Apr  5 18:41:47 UTC 2017
New revision: 316536
URL: https://svnweb.freebsd.org/changeset/base/316536

Log:
  bsdgrep: create additional tests for coverage on recent fixes

  Create additional tests to cover regressions that were discovered by
  PRs linked to reviews D10098, D10102, and D10104.

  It is worth noting that neither bsdgrep(1) nor gnugrep(1) in the base
  system currently pass all of these tests, and gnugrep(1) not quite being
  up to snuff was also noted in at least one of the PRs.

  PR:		175314 202022 195763 180990 197555 197531 181263 209116
  Submitted by:	Kyle Evans <kevans91@ksu.edu>
  Reviewed by:	cem, ngie, emaste
  MFC after:	1 month
  Differential Revision:	https://reviews.freebsd.org/D10112

Changes:
  head/contrib/netbsd-tests/usr.bin/grep/d_color_a.in
  head/contrib/netbsd-tests/usr.bin/grep/d_color_a.out
  head/contrib/netbsd-tests/usr.bin/grep/d_color_b.in
  head/contrib/netbsd-tests/usr.bin/grep/d_color_b.out
  head/contrib/netbsd-tests/usr.bin/grep/d_color_c.out
  head/contrib/netbsd-tests/usr.bin/grep/d_escmap.in
  head/contrib/netbsd-tests/usr.bin/grep/d_f_file_empty.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_d.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.out
  head/contrib/netbsd-tests/usr.bin/grep/t_grep.sh
  head/usr.bin/grep/tests/Makefile
Comment 7 commit-hook freebsd_committer freebsd_triage 2017-08-16 00:13:47 UTC
A commit references this bug:

Author: kevans
Date: Wed Aug 16 00:12:25 UTC 2017
New revision: 322555
URL: https://svnweb.freebsd.org/changeset/base/322555

Log:
  bsdgrep: Fix matching behavior and add regression tests

  MFC r316477: bsdgrep: fix matching behaviour

  - Set REG_NOTBOL if we've already matched beginning of line and we're
    examining later parts

  - For each pattern we examine, apply it to the remaining bits of the
    line rather than (potentially) smaller subsets

  - Check for REG_NOSUB after we've looked at all patterns initially
    matching the line

  - Keep track of the last match we made to later determine if we're
    simply not matching any longer or if we need to proceed another byte
    because we hit a zero-length match

  - Match the earliest and longest bit of each line before moving the
    beginning of what we match to further in the line, past the end of the
    longest match; this generally matches how gnugrep(1) seems to behave,
    and seems like pretty good behavior to me

  - Finally, bail out of printing any matches if we were set to print all
    (empty pattern) but -o (output matches) was set

  MFC r316489: bsdgrep: Initialize vars to avoid a false positive GCC warning

  MFC r316491: bsdgrep: revert color changes from r316477

  r316477 changed the color output to match exactly the in-tree GNU grep,
  but introduces unnecessary escape sequences.

  MFC r316536: bsdgrep: create additional tests for coverage on recent fixes

  Create additional tests to cover regressions that were discovered by
  PRs linked to reviews D10098, D10102, and D10104.

  It is worth noting that neither bsdgrep(1) nor gnugrep(1) in the base
  system currently pass all of these tests, and gnugrep(1) not quite being
  up to snuff was also noted in at least one of the PRs.

  MFC r317052: bsdgrep: fix zero-length matches without the -o flag

  r316477 broke zero-length matches when not using the -o flag, by
  skipping over them entirely.

  Add a regression test so that it doesn't break again in the future.

  PR:		175314, 180990, 181263, 195763, 197531, 197555, 202022, 209116
  Approved by:	emaste (mentor, blanket MFC)
  Relnotes:	yes

Changes:
_U  stable/11/
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_a.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_a.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_b.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_b.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_c.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_escmap.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_f_file_empty.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_d.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/t_grep.sh
  stable/11/usr.bin/grep/tests/Makefile
  stable/11/usr.bin/grep/util.c
Comment 8 Baptiste Daroussin freebsd_committer freebsd_triage 2018-04-25 11:47:14 UTC
seems like this issue is fixed now and should be closed, no?