Subject: Re: bug#32592: heap-use-after-free in regex module

From: Assaf Gordon <[email-masked]>
Date: Wed, 5 Sep 2018 19:08:24 -0600

Hello,
Assuming the gnulib bugfix is valid (in my previous email),
I suggest adding the following test to sed (after updating gnulib).

comments welcomed,
  - assaf

>From bc2794c76cd4202df5172bdbe364a4006e6edbe6 Mon Sep 17 00:00:00 2001
From: Assaf Gordon <[email-masked]>
Date: Wed, 5 Sep 2018 18:58:55 -0600
Subject: [PATCH] sed: fix heap-use-after-free bug in s/// command

sed would accesses freed memory when given specific backreferences
in 's' command. Reported by Saito Takaaki <[email-masked]>
in https://debbugs.gnu.org/32592 .

This is a gnulib/glibc bug which can be triggered by sed.
If the bug is detected, it is recommended to rebuild sed with the built-in
regex engine (./configure --with-included-regex).

Example:

    echo 'abcdefghijk!!!!!!!!!!abcdefghijk!!!!!!!!!!' \
        | valgrind ./sed/sed -E 's/(.+).*\1//i'

* NEWS: Mention the fix.
* testsuite/bug32592.sh: Test for the bug.
* testsuite/local.mk (T): Add new test.
---
 NEWS                  |   6 +++
 testsuite/bug32592.sh | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++
 testsuite/local.mk    |   1 +
 3 files changed, 147 insertions(+)
 create mode 100755 testsuite/bug32592.sh

diff --git a/NEWS b/NEWS
index e25d26b..ecbba45 100644
--- a/NEWS
+++ b/NEWS
@@ -20,6 +20,12 @@ GNU sed NEWS                                    -*- outline -*-
   sed no longer accesses invalid memory (heap overflow) with s/$//n regexes.
   [bug#32271, present since sed-4.3].
 
+  sed no longer accesses freed memory when given specific backreferences
+  in 's' command. This is a gnulib/glibc bug which can be triggered by sed.
+  If the bug is detected, it is recommended to rebuild sed with the built-in
+  regex engine (./configure --with-included-regex) [bug#32592, present at
+  least since sed-4.0.6].
+
 
 * Noteworthy changes in release 4.5 (2018-03-31) [stable]
 
diff --git a/testsuite/bug32592.sh b/testsuite/bug32592.sh
new file mode 100755
index 0000000..863768e
--- /dev/null
+++ b/testsuite/bug32592.sh
@@ -0,0 +1,140 @@
+#!/bin/sh
+# sed would access freed memory under certain uses.
+# Before sed-4.6, this would result in "Invalid read of size 1" and
+# "Address 0x56096d0 is 16 bytes inside a block of size 42 free'd"
+#
+# The root cause is a gnulib/glibc bug (not sed code).
+# If this test fail, it is recommended to build sed with internal
+# regex implementation (./configure --with-included-regex).
+
+# Copyright (C) 2018 Free Software Foundation, Inc.
+
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <https://www.gnu.org/licenses/>.
+
+## This warning will be shown on top in the test-suite.log file - hopefully
+## users/testers will see it and avoid submitting false-positive bugs.
+printf "%s\n" \
+   "" \
+   "=======================================================" \
+   "=======================================================" \
+   "" \
+   "  If this test failed (bug32592) you are likely using a buggy glibc." \
+   "  consider recompiling with './configure --with-internal-regex'" \
+   "" \
+   "========================================================" \
+   "========================================================" \
+   ""
+
+
+. "${srcdir=.}/testsuite/init.sh"; path_prepend_ ./sed
+print_ver_ sed
+
+require_valgrind_
+
+
+
+##
+## Test 1: minimal reproducer
+##
+
+printf 'abcdefghijk!!!!!!!!!!!!!!!abcdefghijk!!!!!!!!!!!!!!!' > in1 \
+  || framework_failure_
+printf 's/(.+).*\1//i' > prog1 || framework_failure_
+
+valgrind --quiet --error-exitcode=1 \
+  sed -E 's/(.+).*\1//i' in1 > out1 2> err1 || fail=1
+
+echo "valgrind report for 'test1':"
+echo "=================================="
+cat err1
+echo "=================================="
+
+# Work around a bug in CentOS 5.10's valgrind
+# FIXME: remove in 2018 or when CentOS 5 is no longer officially supported
+grep 'valgrind: .*Assertion.*failed' err-posix > /dev/null \
+  && skip_ 'you seem to have a buggy version of valgrind'
+
+compare /dev/null out1 || fail=1
+compare /dev/null err1 || fail=1
+
+
+
+
+##
+## Test 2: The original bug report
+##
+
+cat<<\EOF>prog2 || framework_failure_
+s/$/\nabcdefghijklmnopqrstuvwxyz/
+s/\(\(.\).\+\(.\)\)\(.*\n.*\1\)/\2-\3\4/i
+P
+d
+EOF
+
+cat<<\EOF>in2 || framework_failure_
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!!!!!
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!!!!
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!!!
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!!
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!
+abcdefghijklmns!!!!!!!!!!!!!!!!!!!!!!
+EOF
+
+cat<<\EOF>exp2 || framework_failure_
+a-ns!!!!!!!!!!!!!!!!!!!!!!!!!!
+a-ns!!!!!!!!!!!!!!!!!!!!!!!!!
+a-ns!!!!!!!!!!!!!!!!!!!!!!!!
+a-ns!!!!!!!!!!!!!!!!!!!!!!!
+a-ns!!!!!!!!!!!!!!!!!!!!!!
+a-ns!!!!!!!!!!!!!!!!!!!!!!
+EOF
+
+valgrind --quiet --error-exitcode=1 \
+  sed -f prog2 in2 > out2 2> err2 || fail=1
+
+echo "valgrind report for 'test2':"
+echo "=================================="
+cat err2
+echo "=================================="
+
+compare exp2 out2 || fail=1
+compare /dev/null err2 || fail=1
+
+
+##
+## Test 3: The original bug report
+## This bug was hard to trigger after 4.4, but still existed in 32bit.
+
+printf 'abcdefghijkl' > in3 || framework_failure_
+printf '(abcdefghijkl)' > exp3 || framework_failure_
+
+valgrind --quiet --error-exitcode=1 \
+  sed 'h;G;s/\(a.*\).*\1/(\1)/i' in3 > out3 2> err3 || fail=1
+
+echo "valgrind report for 'test3':"
+echo "=================================="
+cat err3
+echo "=================================="
+
+compare exp3 out3 || fail=1
+compare /dev/null err3 || fail=1
+
+
+# This warning will be shown on the summarized PASS/FAIL list of tests.
+if test -n "$fail" ; then
+  warn_ "If this test failed (bug32592) you are likely using a buggy glibc."
+  warn_ "consider recompiling with './configure --with-internal-regex'"
+fi
+
+Exit $fail
diff --git a/testsuite/local.mk b/testsuite/local.mk
index 6d0a74d..15db72d 100644
--- a/testsuite/local.mk
+++ b/testsuite/local.mk
@@ -46,6 +46,7 @@ T =					\
   testsuite/bug32082.sh		\
   testsuite/bug32271-1.sh		\
   testsuite/bug32271-2.sh		\
+  testsuite/bug32592.sh			\
   testsuite/cmd-l.sh			\
   testsuite/cmd-R.sh			\
   testsuite/colon-with-no-label.sh	\
-- 
2.11.0