[dev] [sbase] grep: global-buffer-overflow

[Frank Busse]

Hi,

again found by KLEE:

---
$ printf '\x00\x00\n\x00\x00\x00\x00\x00' > A
$ ./grep -xsf A
ERROR: AddressSanitizer: global-buffer-overflow
$ ./grep -wf A
ERROR: AddressSanitizer: global-buffer-overflow
---


Best,

Frank

[Hiltjo Posthuma]

Patch contributions would be welcome.

--
Kind regards,
Hiltjo

[Rob]

On Sat, 1 Nov 2025 at 09:27, Hiltjo Posthuma <hil...@codemadness.org> wrote:
>
> On Thu, Oct 23, 2025 at 03:28:06PM +0200, Frank Busse wrote:
> > Hi,
> >
> > again found by KLEE:
> >
> > ---
> > $ printf '\x00\x00\n\x00\x00\x00\x00\x00' > A
> > $ ./grep -xsf A
> > ERROR: AddressSanitizer: global-buffer-overflow
> > $ ./grep -wf A
> > ERROR: AddressSanitizer: global-buffer-overflow
> > ---
>

> Patch contributions would be welcome.

I've got a local patch set rewriting in Rust - fixes all the memory
issues and improves the speed, where shall I share them?

Kind regards,
Rob

[Страхиња Радић]

Дана 25/11/01 10:26AM, Rob написа:

> I've got a local patch set rewriting in Rust - fixes all the memory
> issues and improves the speed, where shall I share them?

Rust sucks. C or bust.

[Hiltjo Posthuma]

Feel free to share them.

--
Kind regards,
Hiltjo

[Carlos Torres]

also another backtrace and memory dump for the other grep command 'grep -wf A'

=================================================================
==114878==ERROR: AddressSanitizer: global-buffer-overflow on address
0x55555555a022 at pc 0x555555557621 bp 0x7fffffffd9f0 sp
0x7fffffffd9e0
READ of size 1 at 0x55555555a022 thread T0
#0 0x555555557620 in addpattern /home/cjt/src/sbase/grep.c:68
#1 0x555555557846 in addpatternfile /home/cjt/src/sbase/grep.c:96
#2 0x55555555834a in main /home/cjt/src/sbase/grep.c:213
#3 0x7ffff7427674 (/usr/lib/libc.so.6+0x27674) (BuildId:
4fe011c94a88e8aeb6f2201b9eb369f42b4a1e9e)
#4 0x7ffff7427728 in __libc_start_main
(/usr/lib/libc.so.6+0x27728) (BuildId:
4fe011c94a88e8aeb6f2201b9eb369f42b4a1e9e)
#5 0x5555555572e4 in _start (/home/cjt/src/sbase/grep+0x32e4)
(BuildId: dcb36777af50b79d8f264dfbe66653d14e5aafe5)

0x55555555a022 is located 0 bytes after global variable '*.LC0'
defined in 'grep.c' (0x55555555a020) of size 2
'*.LC0' is ascii string '^'
0x55555555a022 is located 62 bytes before global variable '*.LC1'
defined in 'grep.c' (0x55555555a060) of size 1
'*.LC1' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow
/home/cjt/src/sbase/grep.c:68 in addpattern
Shadow bytes around the buggy address:
0x555555559d80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x555555559e00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x555555559e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x555555559f00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x555555559f80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x55555555a000: 00 00 00 00[02]f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9
0x55555555a080: f9 f9 f9 f9 02 f9 f9 f9 f9 f9 f9 f9 07 f9 f9 f9
0x55555555a100: f9 f9 f9 f9 02 f9 f9 f9 f9 f9 f9 f9 03 f9 f9 f9
0x55555555a180: f9 f9 f9 f9 02 f9 f9 f9 f9 f9 f9 f9 03 f9 f9 f9
0x55555555a200: f9 f9 f9 f9 00 00 01 f9 f9 f9 f9 f9 00 04 f9 f9
0x55555555a280: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 05 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==114878==ABORTING
[Inferior 1 (process 114878) exited with code 01]
(gdb)

[Carlos Torres]

for the benefit of the thread, here is the ASAN backtrace and memory
dump with 'grep -xsf A'

=================================================================
==114090==ERROR: AddressSanitizer: global-buffer-overflow on address
0x55555555a022 at pc 0x5555555574a1 bp 0x7fffffffd9f0 sp

0x7fffffffd9e0
READ of size 1 at 0x55555555a022 thread T0

#0 0x5555555574a0 in addpattern /home/cjt/src/sbase/grep.c:60

#1 0x555555557846 in addpatternfile /home/cjt/src/sbase/grep.c:96
#2 0x55555555834a in main /home/cjt/src/sbase/grep.c:213
#3 0x7ffff7427674 (/usr/lib/libc.so.6+0x27674) (BuildId:
4fe011c94a88e8aeb6f2201b9eb369f42b4a1e9e)
#4 0x7ffff7427728 in __libc_start_main
(/usr/lib/libc.so.6+0x27728) (BuildId:
4fe011c94a88e8aeb6f2201b9eb369f42b4a1e9e)
#5 0x5555555572e4 in _start (/home/cjt/src/sbase/grep+0x32e4)
(BuildId: dcb36777af50b79d8f264dfbe66653d14e5aafe5)

0x55555555a022 is located 0 bytes after global variable '*.LC0'
defined in 'grep.c' (0x55555555a020) of size 2
'*.LC0' is ascii string '^'
0x55555555a022 is located 62 bytes before global variable '*.LC1'
defined in 'grep.c' (0x55555555a060) of size 1
'*.LC1' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow

/home/cjt/src/sbase/grep.c:60 in addpattern

==114090==ABORTING
[Inferior 1 (process 114090) exited with code 01]
(gdb)

[Roberto E. Vargas Caballero]

On Thu, Oct 23, 2025 at 03:28:06PM +0200, Frank Busse wrote:

The following patch should solve these problems. While we were
analyzing the problem it was discovered that the flag -x doesn't
work well, but that is a different topic to be addessed in a different
commit.

-- >8 --

From e285ed315fb47fb3775c4ccdcece24b61ed5403b Mon Sep 17 00:00:00 2001
From: "Roberto E. Vargas Caballero" <k0...@shike2.net>
Date: Wed, 5 Nov 2025 09:59:44 +0100
Subject: [PATCH] grep: Don't modify constant strings

The pattern pointer was assigned to a constant string and later it was
modified, which is UB. But even worse, as we were trusting the patlen
parameter received, patlen was meaningless after that assignment.

The addpattern() had many problems because it trusted the patlen
parameter, but in some places it used string functions that depend of
having a NUL character creating many problems when embedded NUL characters
were found in the pattern. As mandated by POSIX in [1]:

The interfaces specified in POSIX.1-2017 do not permit the
inclusion of a NUL character in an RE or in the string to be
matched. If during the operation of a standard utility a NUL
is included in the text designated to be matched, that NUL may
designate the end of the text string for the purposes of matching.

so, the simples solution is just discard the patlen parameter and call
strlen() in addpattern() and use that as size of the pattern.

[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html
---
grep.c | 19 +++++++++----------
1 file changed, 9 insertions(+), 10 deletions(-)

diff --git a/grep.c b/grep.c
index 1c97807..9b9f5a9 100644
--- a/grep.c
+++ b/grep.c
@@ -10,7 +10,7 @@

enum { Match = 0, NoMatch = 1, Error = 2 };

-static void addpattern(const char *, size_t);
+static void addpattern(const char *);
static void addpatternfile(FILE *);
static int grep(FILE *, const char *);

@@ -37,20 +37,19 @@ struct pattern {
static SLIST_HEAD(phead, pattern) phead;

static void
-addpattern(const char *pattern, size_t patlen)
+addpattern(const char *pattern)
{
struct pattern *pnode;
- char *tmp;
+ char *tmp, beg[] = "^";
int bol, eol;
- size_t len;
-
- if (!patlen)
- return;
+ size_t len, patlen;

/* a null BRE/ERE matches every line */
- if (!Fflag)
+ if (!Fflag) {
if (pattern[0] == '\0')
- pattern = "^";
+ pattern = beg;
+ }
+ patlen = strlen(pattern);

if (!Fflag && xflag) {
tmp = enmalloc(Error, patlen + 3);
@@ -93,7 +92,7 @@ addpatternfile(FILE *fp)
while ((len = getline(&buf, &size, fp)) > 0) {
if (len > 0 && buf[len - 1] == '\n')
buf[len - 1] = '\0';
- addpattern(buf, (size_t)len);
+ addpattern(buf);
}
if (ferror(fp))
enprintf(Error, "read error:");
--
2.45.4

[Santtu Lakkala]

Hi,

On 5.11.2025 11.28, Roberto E. Vargas Caballero wrote:
> On Thu, Oct 23, 2025 at 03:28:06PM +0200, Frank Busse wrote:
>> Hi,
>>
>> again found by KLEE:
>>
>> ---
>> $ printf '\x00\x00\n\x00\x00\x00\x00\x00' > A
>> $ ./grep -xsf A
>> ERROR: AddressSanitizer: global-buffer-overflow
>> $ ./grep -wf A
>> ERROR: AddressSanitizer: global-buffer-overflow
>
> The following patch should solve these problems. While we were
> analyzing the problem it was discovered that the flag -x doesn't
> work well, but that is a different topic to be addessed in a different
> commit.

Even this change actually fixes issues with -x:

Before:
$ printf 'foo\nfoo$\n' | ./grep -x 'foo$'
foo$

After:
$ printf 'foo\nfoo$\n' | ./grep -x 'foo$'
foo

While the real issue of using 'strlen() + 1' with 'fmemopen()' is not
fixed, the use of 'strlen()' in addpattern ignores the (extra) string
terminator included by getline().

> /* a null BRE/ERE matches every line */
> - if (!Fflag)
> + if (!Fflag) {
> if (pattern[0] == '\0')
> - pattern = "^";
> + pattern = beg;

This is not needed, the problem always was READ access due to patlen
mismatch:

==1109644==ERROR: AddressSanitizer: global-buffer-overflow on address
0x0000004060a2 at pc 0x000000404354 bp 0x7ffcf6cd3f70 sp 0x7ffcf6cd3f68
READ of size 1 at 0x0000004060a2 thread T0
#0 0x404353 in addpattern /home/inz/Projects/sbase/grep.c:60
#1 0x404353 in addpatternfile /home/inz/Projects/sbase/grep.c:96
#2 0x402b2e in main /home/inz/Projects/sbase/grep.c:213

> + }
> + patlen = strlen(pattern);

--
Cheers,
Santtu

[Roberto E. Vargas Caballero]

Hi,

On Wed, Nov 05, 2025 at 12:14:03PM +0200, Santtu Lakkala wrote:
> Even this change actually fixes issues with -x:
>
> Before:
> $ printf 'foo\nfoo$\n' | ./grep -x 'foo$'
> foo$
>
> After:
> $ printf 'foo\nfoo$\n' | ./grep -x 'foo$'
> foo

Nice! I didn't realize about it xD

> While the real issue of using 'strlen() + 1' with 'fmemopen()' is not fixed,
> the use of 'strlen()' in addpattern ignores the (extra) string terminator
> included by getline().

Yes, I decided not changing the fmemopen() calls because we are protected
against NUL characters now. But thinking now, why adding a byte to ignore it
later? I think I am going to remove the +1 in every call.

> > /* a null BRE/ERE matches every line */
> > - if (!Fflag)
> > + if (!Fflag) {
> > if (pattern[0] == '\0')
> > - pattern = "^";
> > + pattern = beg;
>
> This is not needed, the problem always was READ access due to patlen
> mismatch:

Yes, you are right, an empty regex should match always. I am going
to remove the full if.

Regards,