[PATCH] fix use of pointer after free in unsetenv

[PATCH] fix use of pointer after free in unsetenv

[Alexander Cherepanov]

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

Hi!

The code in [1] uses a pointer which was freed and hence has an 
indeterminate value. Patch attached.

[1] http://git.musl-libc.org/cgit/musl/tree/src/env/unsetenv.c#n23

-- 
Alexander Cherepanov

[-- Attachment #2: 0001-fix-use-of-pointer-after-free-in-unsetenv.patch --]
[-- Type: text/x-patch, Size: 897 bytes --]

From f446b5811a8abc08bcc8202aa241dce82d4c917d Mon Sep 17 00:00:00 2001
From: Alexander Cherepanov <cherepan@mccme.ru>
Date: Mon, 4 Jan 2016 01:40:03 +0300
Subject: [PATCH] fix use of pointer after free in unsetenv

the value of a pointer becomes indeterminate after free() so delay free()
until the pointer is not needed anymore.

---
 src/env/unsetenv.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/env/unsetenv.c b/src/env/unsetenv.c
index 3569335..b5d8b19 100644
--- a/src/env/unsetenv.c
+++ b/src/env/unsetenv.c
@@ -19,9 +19,10 @@ again:
 	if (__environ[i]) {
 		if (__env_map) {
 			for (j=0; __env_map[j] && __env_map[j] != __environ[i]; j++);
-			free (__env_map[j]);
+			char *t =__env_map[j];
 			for (; __env_map[j]; j++)
 				__env_map[j] = __env_map[j+1];
+			free (t);
 		}
 		for (; __environ[i]; i++)
 			__environ[i] = __environ[i+1];
-- 
1.7.10.4

Re: [PATCH] fix use of pointer after free in unsetenv

[Rich Felker]

On Mon, Jan 04, 2016 at 02:09:44AM +0300, Alexander Cherepanov wrote:
> Hi!
> 
> The code in [1] uses a pointer which was freed and hence has an
> indeterminate value. Patch attached.
> 
> [1] http://git.musl-libc.org/cgit/musl/tree/src/env/unsetenv.c#n23

The bug sounds a lot scarier than it actually is. I don't think any
compilers will break this yet but it is indeed UB.

> >From f446b5811a8abc08bcc8202aa241dce82d4c917d Mon Sep 17 00:00:00 2001
> From: Alexander Cherepanov <cherepan@mccme.ru>
> Date: Mon, 4 Jan 2016 01:40:03 +0300
> Subject: [PATCH] fix use of pointer after free in unsetenv
> 
> the value of a pointer becomes indeterminate after free() so delay free()
> until the pointer is not needed anymore.
> 
> ---
>  src/env/unsetenv.c |    3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/src/env/unsetenv.c b/src/env/unsetenv.c
> index 3569335..b5d8b19 100644
> --- a/src/env/unsetenv.c
> +++ b/src/env/unsetenv.c
> @@ -19,9 +19,10 @@ again:
>  	if (__environ[i]) {
>  		if (__env_map) {
>  			for (j=0; __env_map[j] && __env_map[j] != __environ[i]; j++);
> -			free (__env_map[j]);
> +			char *t =__env_map[j];
>  			for (; __env_map[j]; j++)
>  				__env_map[j] = __env_map[j+1];
> +			free (t);

Wouldn't something like this be simpler:

	do __env_map[j] = __env_map[j+1];
	while (__env_map[++j]);

Rich

Re: [PATCH] fix use of pointer after free in unsetenv

[Markus Wichmann]

On Mon, Jan 04, 2016 at 02:09:44AM +0300, Alexander Cherepanov wrote:
> Hi!
> 
> The code in [1] uses a pointer which was freed and hence has an
> indeterminate value. Patch attached.
> 
> [1] http://git.musl-libc.org/cgit/musl/tree/src/env/unsetenv.c#n23
> 

What are you talking about? free() ends the lifetime of the object
pointed to by the argument given. However, after the free() only the
pointer itself is used. It won't be dereferenced again, and instead will
be immediately overwritten with a valid pointer. And while it is
possible that the pointer becomes so invalid that even loading it causes
undefined behavior, this doesn't happen on any of the supported systems
(it might happen on i386 with segmentation, but Linux/i386, which is the
only supported OS for musl, doesn't use segmentation).

So it looks like unnecessary complexity to me to apply this patch.

Ciao,
Markus

Re: [PATCH] fix use of pointer after free in unsetenv

[Alexander Cherepanov]

On 2016-01-04 06:05, Rich Felker wrote:
> On Mon, Jan 04, 2016 at 02:09:44AM +0300, Alexander Cherepanov wrote:
>> The code in [1] uses a pointer which was freed and hence has an
>> indeterminate value. Patch attached.
>>
>> [1] http://git.musl-libc.org/cgit/musl/tree/src/env/unsetenv.c#n23
>
> The bug sounds a lot scarier than it actually is.

Sure. I have tried at least not to use the term "use after free" but 
mentioning directly that the pointer is not dereferenced would be even 
better.

> I don't think any
> compilers will break this yet but it is indeed UB.

I think so too.

>> >From f446b5811a8abc08bcc8202aa241dce82d4c917d Mon Sep 17 00:00:00 2001
>> From: Alexander Cherepanov <cherepan@mccme.ru>
>> Date: Mon, 4 Jan 2016 01:40:03 +0300
>> Subject: [PATCH] fix use of pointer after free in unsetenv
>>
>> the value of a pointer becomes indeterminate after free() so delay free()
>> until the pointer is not needed anymore.
>>
>> ---
>>   src/env/unsetenv.c |    3 ++-
>>   1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/src/env/unsetenv.c b/src/env/unsetenv.c
>> index 3569335..b5d8b19 100644
>> --- a/src/env/unsetenv.c
>> +++ b/src/env/unsetenv.c
>> @@ -19,9 +19,10 @@ again:
>>   	if (__environ[i]) {
>>   		if (__env_map) {
>>   			for (j=0; __env_map[j] && __env_map[j] != __environ[i]; j++);
>> -			free (__env_map[j]);
>> +			char *t =__env_map[j];
>>   			for (; __env_map[j]; j++)
>>   				__env_map[j] = __env_map[j+1];
>> +			free (t);
>
> Wouldn't something like this be simpler:
>
> 	do __env_map[j] = __env_map[j+1];
> 	while (__env_map[++j]);

This depends on whether our __env_map[j] could be 0. The condition 
"__env_map[j]" in the previous loop hints that it could. Then it should 
be something like this:

if (__env_map[j]) {
	free (__env_map[j]);
	do __env_map[j] = __env_map[j+1];
	while (__env_map[++j]);
}

-- 
Alexander Cherepanov

Re: [PATCH] fix use of pointer after free in unsetenv

[Alexander Monakov]

On Mon, 4 Jan 2016, Alexander Cherepanov wrote:
> This depends on whether our __env_map[j] could be 0. The condition
> "__env_map[j]" in the previous loop hints that it could. Then it should be
> something like this:
> 
> if (__env_map[j]) {
> 	free (__env_map[j]);
> 	do __env_map[j] = __env_map[j+1];
> 	while (__env_map[++j]);
> }

True, but it wouldn't solve the problem in its entirety.  There's a similar
issue further down (line 26 atm), where __environ[i] is tested in a loop.
However, if we executed free(__env_map[j]), then __env_map[j]==__environ[i]
had held.  Thus, entering the loop invokes the same UB.

To me the implementation looks weird due to how it restarts scanning __environ
with 'goto again' from position 0 instead of current position. I can propose
the following rewrite (untested):

for (i=0; __environ[i]; i++) {
	char *e = __environ[i];
	if (!memcmp(name, e, l) && e[l] == '=') {
		for (j=i--; __environ[j]; j++)
			__environ[j] = __environ[j+1];
		if (__env_map) {
			for (j=0; __env_map[j] && __env_map[j] != e; j++);
			if (__env_map[j]) {
				free(__env_map[j]);
				do __env_map[j] = __env_map[j+1];
				while (__env_map[++j]);
			}
		}
	}
}

Alexadner

Re: [PATCH] fix use of pointer after free in unsetenv

[Alexander Cherepanov]

On 2016-01-04 10:42, Markus Wichmann wrote:
> On Mon, Jan 04, 2016 at 02:09:44AM +0300, Alexander Cherepanov wrote:
>> Hi!
>>
>> The code in [1] uses a pointer which was freed and hence has an
>> indeterminate value. Patch attached.
>>
>> [1] http://git.musl-libc.org/cgit/musl/tree/src/env/unsetenv.c#n23
>>
>
> What are you talking about? free() ends the lifetime of the object
> pointed to by the argument given.

Right, and C11, 6.2.4p2, adds: "The value of a pointer becomes 
indeterminate when the object it points to (or just past) reaches the 
end of its lifetime."

> However, after the free() only the
> pointer itself is used. It won't be dereferenced again, and instead will
> be immediately overwritten with a valid pointer. And while it is
> possible that the pointer becomes so invalid that even loading it causes
> undefined behavior, this doesn't happen on any of the supported systems
> (it might happen on i386 with segmentation, but Linux/i386, which is the
> only supported OS for musl, doesn't use segmentation).

You presume that the bits would be loaded that were there before free(). 
But this is not mandated by the C standard. A compiler is permitted to 
completely replace the value of the pointer with, e.g., NULL (as a 
hardening measure, to catch use-after-free) or just use NULL as the 
pointer's value in the first comparison in the loop (as an 
optimization). It's permitted by the rules of the C standard and makes 
the program faster and smaller (the whole "for" loop is eliminated), so 
why not?

IOW even if it's technically not undefined behavior (this could be 
debated) and not broken by current compilers it's wrong C, could be 
broken by future compilers, will trigger sanitizers/verifiers (I hope at 
least some of them will be able to catch this) etc.

> So it looks like unnecessary complexity to me to apply this patch.

It has its pros and cons. IMHO it's better to fix this problem (with my 
patch or in any other way) but that's just MHO and I appreciate that 
POVs vary.

-- 
Alexander Cherepanov

Re: [PATCH] fix use of pointer after free in unsetenv

[Alexander Monakov]

On Mon, 4 Jan 2016, Alexander Monakov wrote:
> To me the implementation looks weird due to how it restarts scanning __environ
> with 'goto again' from position 0 instead of current position. I can propose
> the following rewrite (untested):
> 
> for (i=0; __environ[i]; i++) {
> 	char *e = __environ[i];
> 	if (!memcmp(name, e, l) && e[l] == '=') {
> 		for (j=i--; __environ[j]; j++)
> 			__environ[j] = __environ[j+1];
> 		if (__env_map) {
> 			for (j=0; __env_map[j] && __env_map[j] != e; j++);
> 			if (__env_map[j]) {
> 				free(__env_map[j]);
> 				do __env_map[j] = __env_map[j+1];
> 				while (__env_map[++j]);
> 			}
> 		}
> 	}
> }

Hm, there's no need to preserve relative order of env entries, is there?

for (i=0; __environ[i]; i++);
for (int im=i-1; i-->0; )
	if (!memcmp(name, __environ[i], l) && __environ[i][l] == '=') {
		if (__env_map) {
			for (j=0; __env_map[j]; j++);
			for (int jm=j-1; j-->0; )
				if (__env_map[j] == __environ[i]) {
					__env_map[j] = __env_map[jm];
					__env_map[jm] = 0;
					free(__environ[i]);
					break;
				}
		}
		if (i != im)
			__environ[i] = __environ[im];
		__environ[im--] = 0;
	}

(in practice I'd rather spell i-->0 as --i>=0 above)

Alexander

Re: [PATCH] fix use of pointer after free in unsetenv

[Rich Felker]

On Mon, Jan 04, 2016 at 06:47:36PM +0300, Alexander Monakov wrote:
> On Mon, 4 Jan 2016, Alexander Monakov wrote:
> > To me the implementation looks weird due to how it restarts scanning __environ
> > with 'goto again' from position 0 instead of current position. I can propose
> > the following rewrite (untested):

The "goto again" is for the rare (generally malicious) case of
duplicate definitions, to ensure that unsetenv removes them all.

> > for (i=0; __environ[i]; i++) {
> > 	char *e = __environ[i];
> > 	if (!memcmp(name, e, l) && e[l] == '=') {
> > 		for (j=i--; __environ[j]; j++)
> > 			__environ[j] = __environ[j+1];
> > 		if (__env_map) {
> > 			for (j=0; __env_map[j] && __env_map[j] != e; j++);
> > 			if (__env_map[j]) {
> > 				free(__env_map[j]);
> > 				do __env_map[j] = __env_map[j+1];
> > 				while (__env_map[++j]);
> > 			}
> > 		}
> > 	}
> > }
> 
> Hm, there's no need to preserve relative order of env entries, is there?

Yes, there is. If FOO=x and FOO=y both appear in environ[],
unsetenv("BAR") must not cause getenv("FOO") to change from "x" to
"y". However the order in __env_map is irrelevant. Its only purpose is
to track which slots are allocated so we can free them.

Rich

Re: [PATCH] fix use of pointer after free in unsetenv

[Alexander Monakov]

On Mon, 4 Jan 2016, Rich Felker wrote:
> On Mon, Jan 04, 2016 at 06:47:36PM +0300, Alexander Monakov wrote:
> > On Mon, 4 Jan 2016, Alexander Monakov wrote:
> > > To me the implementation looks weird due to how it restarts scanning __environ
> > > with 'goto again' from position 0 instead of current position. I can propose
> > > the following rewrite (untested):
> 
> The "goto again" is for the rare (generally malicious) case of
> duplicate definitions, to ensure that unsetenv removes them all.

Yes, but my point was that rewinding all the way back to i=0 looks odd -- I
understood the need to scan all entries.

> > Hm, there's no need to preserve relative order of env entries, is there?
> 
> Yes, there is. If FOO=x and FOO=y both appear in environ[],
> unsetenv("BAR") must not cause getenv("FOO") to change from "x" to
> "y".

Thanks, I did not consider that. I'm curious, is that just from QoI
perspective, or also required somewhere?

Alexander

Re: [PATCH] fix use of pointer after free in unsetenv

[Rich Felker]

On Tue, Jan 05, 2016 at 12:28:12AM +0300, Alexander Monakov wrote:
> On Mon, 4 Jan 2016, Rich Felker wrote:
> > On Mon, Jan 04, 2016 at 06:47:36PM +0300, Alexander Monakov wrote:
> > > On Mon, 4 Jan 2016, Alexander Monakov wrote:
> > > > To me the implementation looks weird due to how it restarts scanning __environ
> > > > with 'goto again' from position 0 instead of current position. I can propose
> > > > the following rewrite (untested):
> > 
> > The "goto again" is for the rare (generally malicious) case of
> > duplicate definitions, to ensure that unsetenv removes them all.
> 
> Yes, but my point was that rewinding all the way back to i=0 looks odd -- I
> understood the need to scan all entries.

Oh. In that case I guess it's unnecessary to rewind, yes.

BTW what might be best to do is something like:

	char *tmp = __environ[i];
	for (j=i ; __environ[j]; j++)
		__environ[j] = __environ[j+1];
	__env_free(tmp);

where __env_free has a weak def as a nop and gets its strong def from
setenv.c or putenv.c. This refactoring would make it possible for
unsetenv not to pull in free, and the reordering might make it less
likely for dangerous things to happen in a broken program that reads
the environment concurrently with unsetenv.

> > > Hm, there's no need to preserve relative order of env entries, is there?
> > 
> > Yes, there is. If FOO=x and FOO=y both appear in environ[],
> > unsetenv("BAR") must not cause getenv("FOO") to change from "x" to
> > "y".
> 
> Thanks, I did not consider that. I'm curious, is that just from QoI
> perspective, or also required somewhere?

It is a requirement, and it's simply a consequence of the fact that
functions cannot have random side effects they're not specified to
have. unsetenv can't change the value of FOO from x to y any more than
calling strlen can. The fact that the issue arises at all when
environ[] was not setup manually by the program is a consequence of
the kernel not enforcing uniqueness of env var names, which (AFAIK) is
an implementation detail anyway.

Rich