Subject: Re: bug#24161: [PATCH 2/2] sed: speed up matching by reguler expression with dfa matcher

From: Jim Meyering <[email-masked]>
Date: Mon, 8 Aug 2016 18:33:26 -0700

On Mon, Aug 8, 2016 at 5:53 PM, Jim Meyering <[email-masked]> wrote:
> On Mon, Aug 8, 2016 at 4:29 PM, Norihiro Tanaka <[email-masked]> wrote:
...
>> Thanks for adjusting.  I agree the all changes.
>
> Pushed.

Oops. I had not run ASAN-enabled tests with this patch.
Doing that exposed many test failures like this:

LC_ALL=C  ./sed/sed -f ./testsuite/madding.sed \
        < ./testsuite/madding.inp | LC_ALL=C tr -d \\r > madding.out
=================================================================
==8797==ERROR: AddressSanitizer: heap-buffer-overflow on address
0x622000019646 at pc 0x0000004e98ce bp 0x7ffee5d23130 sp
0x7ffee5d23128
READ of size 1 at 0x622000019646 thread T0
    #0 0x4e98cd in dfaexec_main sed/dfa.c:3078
    #1 0x4e98cd in dfaexec_sb sed/dfa.c:3242
    #2 0x4ece9f in dfaexec sed/dfa.c:3263
    #3 0x4f64ba in match_regex sed/regexp.c:270
    #4 0x4f46ac in do_subst sed/execute.c:1024
    #5 0x4f46ac in execute_program sed/execute.c:1510
    #6 0x4f5997 in process_files sed/execute.c:1678
    #7 0x4f6f64 in main sed/sed.c:363
    #8 0x7fe665f89730 in __libc_start_main (/lib64/libc.so.6+0x20730)
    #9 0x407118 in _start (/home/j/w/co/sed/sed/sed+0x407118)

which I am fixing with this patch:
From 7862a8a5aa282f8f414157d550d9fe65f42488b9 Mon Sep 17 00:00:00 2001
From: Jim Meyering <[email-masked]>
Date: Mon, 8 Aug 2016 18:29:00 -0700
Subject: [PATCH] sed: avoid one-byte heap buffer overrun

* sed/execute.c (DFA_SLOP): Define.
(resize_line): Use it in each line-related allocation.
(line_init): Likewise.
(line_copy): Likewise.
---
 sed/execute.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/sed/execute.c b/sed/execute.c
index 3fe15cb..b1083a8 100644
--- a/sed/execute.c
+++ b/sed/execute.c
@@ -47,7 +47,11 @@
 # define UNUSED
 #endif

-
+/* The number of extra bytes that must be allocated/usable, beyond
+   the declared "end" of each line buffer that may be passed to
+   match_regex.  This is imposed by its use of dfaexec.  */
+#define DFA_SLOP 1
+
 /* Sed operates a line at a time. */
 struct line {
   char *text;		/* Pointer to line allocated by malloc. */
@@ -157,7 +161,7 @@ resize_line (struct line *lb, size_t len)
   if (lb->alloc < INITIAL_BUFFER_SIZE)
     lb->alloc = INITIAL_BUFFER_SIZE;

-  lb->text = REALLOC(lb->text, inactive + lb->alloc, char);
+  lb->text = REALLOC(lb->text, inactive + lb->alloc + DFA_SLOP, char);
   lb->active = lb->text + inactive;
 }

@@ -285,7 +289,7 @@ str_append_modified(struct line *to, const char *string, size_t length,
 static void
 line_init(struct line *buf, struct line *state, size_t initial_size)
 {
-  buf->text = MALLOC(initial_size, char);
+  buf->text = MALLOC(initial_size + DFA_SLOP, char);
   buf->active = buf->text;
   buf->alloc = initial_size;
   buf->length = 0;
@@ -333,7 +337,7 @@ line_copy(struct line *from, struct line *to, int state)
       /* Use free()+MALLOC() instead of REALLOC() to
          avoid unnecessary copying of old text. */
       free(to->text);
-      to->text = MALLOC(to->alloc, char);
+      to->text = MALLOC(to->alloc + DFA_SLOP, char);
     }

   to->active = to->text;
-- 
2.7.4