[PATCH] Fix off-by-one buffer overflow in getdelim

[PATCH] Fix off-by-one buffer overflow in getdelim

[Felix Janda]

when deciding whether to resize the buffer, the terminating null byte
was not taken into account
---
 src/stdio/getdelim.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
index a88c393..3077490 100644
--- a/src/stdio/getdelim.c
+++ b/src/stdio/getdelim.c
@@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
 	for (;;) {
 		z = memchr(f->rpos, delim, f->rend - f->rpos);
 		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
-		if (i+k >= *n) {
+		if (i+k+1 >= *n) {
 			if (k >= SIZE_MAX/2-i) goto oom;
 			*n = i+k+2;
 			if (*n < SIZE_MAX/4) *n *= 2;
-- 
2.4.9

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 1283 bytes --]

On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> when deciding whether to resize the buffer, the terminating null byte
> was not taken into account
> ---
>  src/stdio/getdelim.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> index a88c393..3077490 100644
> --- a/src/stdio/getdelim.c
> +++ b/src/stdio/getdelim.c
> @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
>  	for (;;) {
>  		z = memchr(f->rpos, delim, f->rend - f->rpos);
>  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> -		if (i+k >= *n) {
> +		if (i+k+1 >= *n) {
>  			if (k >= SIZE_MAX/2-i) goto oom;
>  			*n = i+k+2;
>  			if (*n < SIZE_MAX/4) *n *= 2;
> -- 
> 2.4.9

I think you're mistaken. i+k is the space needed so far in the buffer
(not counting the terminating null byte) and *n is the usable space.
The equality case of the i+k >= *n conditional covers the need to
expand the buffer when the new content of length k would exactly fit
but would not leave room for null termination.

Just to make sure I wrote a quick test program, which I've attached,
that should crash in free if the overflow occurs. It does not crash
and the output demonstrates correct resizing.

Rich

[-- Attachment #2: getdelim.c --]
[-- Type: text/plain, Size: 422 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int main()
{
	int i;
	FILE *f = tmpfile();
	putc('\n', f);
	for (i=1; i<32; i++) {
		fseek(f, -1, SEEK_END);
		fputs("x\n", f);
		rewind(f);
		ungetc(getc(f), f);
		size_t n = i+1;
		char *s = malloc(n);;
		printf("%zu %zu ", n, malloc_usable_size(s));
		size_t ret = getline(&s, &n, f);
		printf("%zu %zu %zu\n", ret, n, malloc_usable_size(s));
		free(s);
	}
}

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Felix Janda]

Rich Felker wrote:
> On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > when deciding whether to resize the buffer, the terminating null byte
> > was not taken into account
> > ---
> >  src/stdio/getdelim.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > index a88c393..3077490 100644
> > --- a/src/stdio/getdelim.c
> > +++ b/src/stdio/getdelim.c
> > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> >  	for (;;) {
> >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > -		if (i+k >= *n) {
> > +		if (i+k+1 >= *n) {
> >  			if (k >= SIZE_MAX/2-i) goto oom;
> >  			*n = i+k+2;
> >  			if (*n < SIZE_MAX/4) *n *= 2;
> > -- 
> > 2.4.9
> 
> I think you're mistaken. i+k is the space needed so far in the buffer
> (not counting the terminating null byte) and *n is the usable space.
> The equality case of the i+k >= *n conditional covers the need to
> expand the buffer when the new content of length k would exactly fit
> but would not leave room for null termination.
> 
> Just to make sure I wrote a quick test program, which I've attached,
> that should crash in free if the overflow occurs. It does not crash
> and the output demonstrates correct resizing.

Thanks for the test program!

I did not see the 'if (z) break;'. The off-by-one should only occur
when memchr returns 0 but the byte from getc_unlocked is the delimiter.
(This makes it not so easy to observe the bug.)

Felix

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sun, Oct 25, 2015 at 12:25:52AM +0200, Felix Janda wrote:
> Rich Felker wrote:
> > On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > > when deciding whether to resize the buffer, the terminating null byte
> > > was not taken into account
> > > ---
> > >  src/stdio/getdelim.c | 2 +-
> > >  1 file changed, 1 insertion(+), 1 deletion(-)
> > > 
> > > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > > index a88c393..3077490 100644
> > > --- a/src/stdio/getdelim.c
> > > +++ b/src/stdio/getdelim.c
> > > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> > >  	for (;;) {
> > >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> > >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > > -		if (i+k >= *n) {
> > > +		if (i+k+1 >= *n) {
> > >  			if (k >= SIZE_MAX/2-i) goto oom;
> > >  			*n = i+k+2;
> > >  			if (*n < SIZE_MAX/4) *n *= 2;
> > > -- 
> > > 2.4.9
> > 
> > I think you're mistaken. i+k is the space needed so far in the buffer
> > (not counting the terminating null byte) and *n is the usable space.
> > The equality case of the i+k >= *n conditional covers the need to
> > expand the buffer when the new content of length k would exactly fit
> > but would not leave room for null termination.
> > 
> > Just to make sure I wrote a quick test program, which I've attached,
> > that should crash in free if the overflow occurs. It does not crash
> > and the output demonstrates correct resizing.
> 
> Thanks for the test program!
> 
> I did not see the 'if (z) break;'. The off-by-one should only occur
> when memchr returns 0 but the byte from getc_unlocked is the delimiter.
> (This makes it not so easy to observe the bug.)

Are you saying you still think there is a bug, that's only triggered
when the byte from getc_unlocked causes the loop to break? I'll have
to review that but it seems plausible. Do you have any ideas for
adapting the test program to check this case?

Rich

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sat, Oct 24, 2015 at 07:35:15PM -0400, Rich Felker wrote:
> On Sun, Oct 25, 2015 at 12:25:52AM +0200, Felix Janda wrote:
> > Rich Felker wrote:
> > > On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > > > when deciding whether to resize the buffer, the terminating null byte
> > > > was not taken into account
> > > > ---
> > > >  src/stdio/getdelim.c | 2 +-
> > > >  1 file changed, 1 insertion(+), 1 deletion(-)
> > > > 
> > > > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > > > index a88c393..3077490 100644
> > > > --- a/src/stdio/getdelim.c
> > > > +++ b/src/stdio/getdelim.c
> > > > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> > > >  	for (;;) {
> > > >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> > > >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > > > -		if (i+k >= *n) {
> > > > +		if (i+k+1 >= *n) {
> > > >  			if (k >= SIZE_MAX/2-i) goto oom;
> > > >  			*n = i+k+2;
> > > >  			if (*n < SIZE_MAX/4) *n *= 2;
> > > > -- 
> > > > 2.4.9
> > > 
> > > I think you're mistaken. i+k is the space needed so far in the buffer
> > > (not counting the terminating null byte) and *n is the usable space.
> > > The equality case of the i+k >= *n conditional covers the need to
> > > expand the buffer when the new content of length k would exactly fit
> > > but would not leave room for null termination.
> > > 
> > > Just to make sure I wrote a quick test program, which I've attached,
> > > that should crash in free if the overflow occurs. It does not crash
> > > and the output demonstrates correct resizing.
> > 
> > Thanks for the test program!
> > 
> > I did not see the 'if (z) break;'. The off-by-one should only occur
> > when memchr returns 0 but the byte from getc_unlocked is the delimiter.
> > (This makes it not so easy to observe the bug.)
> 
> Are you saying you still think there is a bug, that's only triggered
> when the byte from getc_unlocked causes the loop to break? I'll have
> to review that but it seems plausible. Do you have any ideas for
> adapting the test program to check this case?

Never mind; I can produce the expected crash just by adding
setbuf(f,0) right after the file is opened.

Rich

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Felix Janda]

Thanks for committing the fix.

Felix

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> when deciding whether to resize the buffer, the terminating null byte
> was not taken into account
> ---
>  src/stdio/getdelim.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> index a88c393..3077490 100644
> --- a/src/stdio/getdelim.c
> +++ b/src/stdio/getdelim.c
> @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
>  	for (;;) {
>  		z = memchr(f->rpos, delim, f->rend - f->rpos);
>  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> -		if (i+k >= *n) {
> +		if (i+k+1 >= *n) {
>  			if (k >= SIZE_MAX/2-i) goto oom;
>  			*n = i+k+2;
>  			if (*n < SIZE_MAX/4) *n *= 2;
> -- 
> 2.4.9

This patch raised a potential conformance issue, that by a strict
reading of the spec, getdelim is only permitted to realloc if the
caller-provided buffer length is insufficient:

    "If *lineptr is a null pointer or if the object pointed to by
    *lineptr is of insufficient size, an object shall be allocated as
    if by malloc() or the object shall be reallocated as if by
    realloc(), respectively, ..."

I'm going to change the +1 to +!z and add a comment. The idea is that
the +1 was only needed in order for the result to fit if the delimiter
has not already been found; if the memchr found it, an exact-sized
buffer was being expanded unnecessarily.

I'm replying to this thread and CC'ing in case there are any problems
I'm missing in my new fix.

Rich

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sun, Sep 16, 2018 at 02:25:42PM -0400, Rich Felker wrote:
> On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > when deciding whether to resize the buffer, the terminating null byte
> > was not taken into account
> > ---
> >  src/stdio/getdelim.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > index a88c393..3077490 100644
> > --- a/src/stdio/getdelim.c
> > +++ b/src/stdio/getdelim.c
> > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> >  	for (;;) {
> >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > -		if (i+k >= *n) {
> > +		if (i+k+1 >= *n) {
> >  			if (k >= SIZE_MAX/2-i) goto oom;
> >  			*n = i+k+2;
> >  			if (*n < SIZE_MAX/4) *n *= 2;
> > -- 
> > 2.4.9
> 
> This patch raised a potential conformance issue, that by a strict
> reading of the spec, getdelim is only permitted to realloc if the
> caller-provided buffer length is insufficient:
> 
>     "If *lineptr is a null pointer or if the object pointed to by
>     *lineptr is of insufficient size, an object shall be allocated as
>     if by malloc() or the object shall be reallocated as if by
>     realloc(), respectively, ..."
> 
> I'm going to change the +1 to +!z and add a comment. The idea is that
> the +1 was only needed in order for the result to fit if the delimiter
> has not already been found; if the memchr found it, an exact-sized
> buffer was being expanded unnecessarily.
> 
> I'm replying to this thread and CC'ing in case there are any problems
> I'm missing in my new fix.

This fix actually looks insufficient; it doesn't fix the case where
the getc produces EOF rather than a character.

Rich

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sun, Sep 16, 2018 at 02:34:47PM -0400, Rich Felker wrote:
> On Sun, Sep 16, 2018 at 02:25:42PM -0400, Rich Felker wrote:
> > On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > > when deciding whether to resize the buffer, the terminating null byte
> > > was not taken into account
> > > ---
> > >  src/stdio/getdelim.c | 2 +-
> > >  1 file changed, 1 insertion(+), 1 deletion(-)
> > > 
> > > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > > index a88c393..3077490 100644
> > > --- a/src/stdio/getdelim.c
> > > +++ b/src/stdio/getdelim.c
> > > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> > >  	for (;;) {
> > >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> > >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > > -		if (i+k >= *n) {
> > > +		if (i+k+1 >= *n) {
> > >  			if (k >= SIZE_MAX/2-i) goto oom;
> > >  			*n = i+k+2;
> > >  			if (*n < SIZE_MAX/4) *n *= 2;
> > > -- 
> > > 2.4.9
> > 
> > This patch raised a potential conformance issue, that by a strict
> > reading of the spec, getdelim is only permitted to realloc if the
> > caller-provided buffer length is insufficient:
> > 
> >     "If *lineptr is a null pointer or if the object pointed to by
> >     *lineptr is of insufficient size, an object shall be allocated as
> >     if by malloc() or the object shall be reallocated as if by
> >     realloc(), respectively, ..."
> > 
> > I'm going to change the +1 to +!z and add a comment. The idea is that
> > the +1 was only needed in order for the result to fit if the delimiter
> > has not already been found; if the memchr found it, an exact-sized
> > buffer was being expanded unnecessarily.
> > 
> > I'm replying to this thread and CC'ing in case there are any problems
> > I'm missing in my new fix.
> 
> This fix actually looks insufficient; it doesn't fix the case where
> the getc produces EOF rather than a character.

OK, the problem here is actually a lot more fundamental than I
realized. If you read the standard as disallowing realloc unless it's
necessary for the result to fit, then there's a circular dependency
here. You can't realloc without knowing whether the next getc will
succeed, but you can't getc without knowing there'll be at least 2
additional bytes to store the result and the null terminator.

If you could fit one additional byte without allocating, but not two,
there's no way to proceed.

The only way out I see is to do the first reallocation speculatively:
instead of realloc, malloc a new buffer that will be large enough,
attempt the getc, and then either switch to it (freeing the original
buffer) or free it (keeping the original buffer) depending on whether
EOF is returned.

In almost all cases, this logic can be skipped. It's not necessary at
all if the stdio stream is buffered, since we can just unget back.
(Using unget works mechanically for unbuffered streams too, but it
violates the invariant that no interface except ungetc or scanf
families should leave logical FILE position not equal to underlying
open file descriptor's offset). It's also not necessary for additional
growth after the first time, since enlarging is already committed.

Rich

Re: [PATCH] Fix off-by-one buffer overflow in getdelim

[Rich Felker]

On Sun, Sep 16, 2018 at 07:32:42PM -0400, Rich Felker wrote:
> On Sun, Sep 16, 2018 at 02:34:47PM -0400, Rich Felker wrote:
> > On Sun, Sep 16, 2018 at 02:25:42PM -0400, Rich Felker wrote:
> > > On Sat, Oct 24, 2015 at 10:43:39PM +0200, Felix Janda wrote:
> > > > when deciding whether to resize the buffer, the terminating null byte
> > > > was not taken into account
> > > > ---
> > > >  src/stdio/getdelim.c | 2 +-
> > > >  1 file changed, 1 insertion(+), 1 deletion(-)
> > > > 
> > > > diff --git a/src/stdio/getdelim.c b/src/stdio/getdelim.c
> > > > index a88c393..3077490 100644
> > > > --- a/src/stdio/getdelim.c
> > > > +++ b/src/stdio/getdelim.c
> > > > @@ -27,7 +27,7 @@ ssize_t getdelim(char **restrict s, size_t *restrict n, int delim, FILE *restric
> > > >  	for (;;) {
> > > >  		z = memchr(f->rpos, delim, f->rend - f->rpos);
> > > >  		k = z ? z - f->rpos + 1 : f->rend - f->rpos;
> > > > -		if (i+k >= *n) {
> > > > +		if (i+k+1 >= *n) {
> > > >  			if (k >= SIZE_MAX/2-i) goto oom;
> > > >  			*n = i+k+2;
> > > >  			if (*n < SIZE_MAX/4) *n *= 2;
> > > > -- 
> > > > 2.4.9
> > > 
> > > This patch raised a potential conformance issue, that by a strict
> > > reading of the spec, getdelim is only permitted to realloc if the
> > > caller-provided buffer length is insufficient:
> > > 
> > >     "If *lineptr is a null pointer or if the object pointed to by
> > >     *lineptr is of insufficient size, an object shall be allocated as
> > >     if by malloc() or the object shall be reallocated as if by
> > >     realloc(), respectively, ..."
> > > 
> > > I'm going to change the +1 to +!z and add a comment. The idea is that
> > > the +1 was only needed in order for the result to fit if the delimiter
> > > has not already been found; if the memchr found it, an exact-sized
> > > buffer was being expanded unnecessarily.
> > > 
> > > I'm replying to this thread and CC'ing in case there are any problems
> > > I'm missing in my new fix.
> > 
> > This fix actually looks insufficient; it doesn't fix the case where
> > the getc produces EOF rather than a character.
> 
> OK, the problem here is actually a lot more fundamental than I
> realized. If you read the standard as disallowing realloc unless it's
> necessary for the result to fit, then there's a circular dependency
> here. You can't realloc without knowing whether the next getc will
> succeed, but you can't getc without knowing there'll be at least 2
> additional bytes to store the result and the null terminator.
> 
> If you could fit one additional byte without allocating, but not two,
> there's no way to proceed.
> 
> The only way out I see is to do the first reallocation speculatively:
> instead of realloc, malloc a new buffer that will be large enough,
> attempt the getc, and then either switch to it (freeing the original
> buffer) or free it (keeping the original buffer) depending on whether
> EOF is returned.
> 
> In almost all cases, this logic can be skipped. It's not necessary at
> all if the stdio stream is buffered, since we can just unget back.
> (Using unget works mechanically for unbuffered streams too, but it
> violates the invariant that no interface except ungetc or scanf
> families should leave logical FILE position not equal to underlying
> open file descriptor's offset). It's also not necessary for additional
> growth after the first time, since enlarging is already committed.

Reading the glibc source, it looks like in the event of realloc
failure, the character that should have been read remains in the stdio
buffer for an "unbuffered" file (equivalent to my ungetc method above,
violating the invariant) and the output buffer is not null-terminated.

I was a bit surprised at the latter aspect at first, but it's what
we're doing too, and reviewing the spec it seems correct:

    "The characters read, including any delimiter, shall be stored in
    the object, and a terminating NUL added when the delimiter or
    end-of-file is encountered."

It's not even clear to me that there's *any* contract on the output
buffer contents when an error (ENOMEM or otherwise) happens, but
morally/QoI there's a principle that not losing data is a good thing,
and the least lossy behavior is that, on ENOMEM, the entire output
buffer (up to the size) contains bytes read from the file.

This can be achieved without the above fancy allocation juggling. The
following looks like it should work:

1. Always skip allocating the extra byte for the getc (reverting the
   above patch).
2. After the getc, if there's no room to store it in the output
   buffer without taking the last spot the null would go in, unget and
   continue the loop.
3. If reallocation fails, copy as much as fits from the stdio buffer
   into the output buffer before returning. This will always be at
   least 1 byte (because 1 byte was being saved for the nul), and thus
   will consume any ungetc from 2.

I'll see if I can work out a patch and test this.

Rich