[PATCH] Prevent reading uninitialized memory with socket filters

[PATCH] Prevent reading uninitialized memory with socket filters

[Dan Rosenberg]

The "mem" array used as scratch space for socket filters is not
initialized, allowing unprivileged users to leak kernel stack bytes.

Signed-off-by: Dan Rosenberg <drosenberg@vsecurity.com>

---
 net/core/filter.c               |    2 ++
 1 file changed, 2 insertions(+), 0 deletions(-)

diff --git a/net/core/filter.c b/net/core/filter.c
index 7beaec3..2749ba0 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -121,6 +121,8 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int
 	int k;
 	int pc;
 
+	memset(mem, 0, sizeof(mem));
+
 	/*
 	 * Process array of filter instructions.
 	 */

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[Joe Perches]

On Tue, 2010-11-09 at 17:28 -0500, Dan Rosenberg wrote:
> The "mem" array used as scratch space for socket filters is not
> initialized, allowing unprivileged users to leak kernel stack bytes.

Hi Dan.

Using
	type var[count] = {};
instead of
	type var[count];
	...
	memset(var, 0, sizeof(var));

at least for gcc 4.4 and 4.5 generally results in smaller code.

$ size net/core/filter.o*
   text	   data	    bss	    dec	    hex	filename
   6751	     56	   1736	   8543	   215f	net/core/filter.o.memset
   6749	     56	   1736	   8541	   215d	net/core/filter.o.init

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[David Miller]

From: Dan Rosenberg <drosenberg@vsecurity.com>
Date: Tue, 09 Nov 2010 17:28:44 -0500

> The "mem" array used as scratch space for socket filters is not
> initialized, allowing unprivileged users to leak kernel stack bytes.
> 
> Signed-off-by: Dan Rosenberg <drosenberg@vsecurity.com>

Prove it.

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[Eric Dumazet]

Le mardi 09 novembre 2010 à 21:28 -0800, David Miller a écrit :
> From: Dan Rosenberg <drosenberg@vsecurity.com>
> Date: Tue, 09 Nov 2010 17:28:44 -0500
> 
> > The "mem" array used as scratch space for socket filters is not
> > initialized, allowing unprivileged users to leak kernel stack bytes.
> > 
> > Signed-off-by: Dan Rosenberg <drosenberg@vsecurity.com>
> 
> Prove it.

And once done, add the checks in sk_chk_filter() ?

Allow a load of mem[X] only if a prior store of mem[X] is proven.

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[Eric Dumazet]

Le mercredi 10 novembre 2010 à 06:53 +0100, Eric Dumazet a écrit :
> Le mardi 09 novembre 2010 à 21:28 -0800, David Miller a écrit :
> > From: Dan Rosenberg <drosenberg@vsecurity.com>
> > Date: Tue, 09 Nov 2010 17:28:44 -0500
> > 
> > > The "mem" array used as scratch space for socket filters is not
> > > initialized, allowing unprivileged users to leak kernel stack bytes.
> > > 
> > > Signed-off-by: Dan Rosenberg <drosenberg@vsecurity.com>
> > 
> > Prove it.
> 
> And once done, add the checks in sk_chk_filter() ?
> 
> Allow a load of mem[X] only if a prior store of mem[X] is proven.
> 
> 

This seems complex, and might fail on some valid filters.

What about the following patch then ?

[PATCH] filter: make sure filters dont read uninitialized memory

There is a possibility malicious users can get limited information about
uninitialized stack mem array. Even if sk_run_filter() result is bound
to packet length (0 .. 65535), we could imagine this can be used by
hostile user.

Initializing mem[] array, like Dan Rosenberg suggested in his patch is
expensive since most filters dont even use this array.

Its hard to make the filter validation in sk_chk_filter(), because of
the jumps. This might be done later.

In this patch, I use a bitmap (a single long var) so that only filters
using mem[] loads/stores pay the price of added security checks.

For other filters, additional cost is a single instruction.

Reported-by: Dan Rosenberg <drosenberg@vsecurity.com>
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
---
 net/core/filter.c |   10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/net/core/filter.c b/net/core/filter.c
index 7beaec3..4d84dc2 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -117,10 +117,12 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int
 	u32 A = 0;			/* Accumulator */
 	u32 X = 0;			/* Index Register */
 	u32 mem[BPF_MEMWORDS];		/* Scratch Memory Store */
+	unsigned long memvalid = 0;
 	u32 tmp;
 	int k;
 	int pc;
 
+	BUILD_BUG_ON(BPF_MEMWORDS > BITS_PER_LONG);
 	/*
 	 * Process array of filter instructions.
 	 */
@@ -264,10 +266,12 @@ load_b:
 			X = fentry->k;
 			continue;
 		case BPF_S_LD_MEM:
-			A = mem[fentry->k];
+			A = (memvalid & (1UL << fentry->k)) ?
+				mem[fentry->k] : 0;
 			continue;
 		case BPF_S_LDX_MEM:
-			X = mem[fentry->k];
+			X = (memvalid & (1UL << fentry->k)) ?
+				mem[fentry->k] : 0;
 			continue;
 		case BPF_S_MISC_TAX:
 			X = A;
@@ -280,9 +284,11 @@ load_b:
 		case BPF_S_RET_A:
 			return A;
 		case BPF_S_ST:
+			memvalid |= 1UL << fentry->k;
 			mem[fentry->k] = A;
 			continue;
 		case BPF_S_STX:
+			memvalid |= 1UL << fentry->k;
 			mem[fentry->k] = X;
 			continue;
 		default:

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[Tetsuo Handa]

Just I thought...

> unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int flen)
> {
> 	struct sock_filter *fentry;     /* We walk down these */
Can't this be "const struct sock_filter *"?
> (...snipped...)
> 	for (pc = 0; pc < flen; pc++) {
> 		fentry = &filter[pc];
Can't we do
		u32 f_k = fentry->k;
and replace 27 repetition of fentry->k with f_k?

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[David Miller]

From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Date: Wed, 10 Nov 2010 23:25:08 +0900

> Just I thought...
> 
>> unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int flen)
>> {
>> 	struct sock_filter *fentry;     /* We walk down these */
> Can't this be "const struct sock_filter *"?
>> (...snipped...)
>> 	for (pc = 0; pc < flen; pc++) {
>> 		fentry = &filter[pc];
> Can't we do
> 		u32 f_k = fentry->k;
> and replace 27 repetition of fentry->k with f_k?

Yes, this feedback seems reasonable, I'll make these changes when I
apply Eric's patch, thanks!

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[David Miller]

From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Date: Wed, 10 Nov 2010 23:25:08 +0900

> Just I thought...
> 
>> unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int flen)
>> {
>> 	struct sock_filter *fentry;     /* We walk down these */
> Can't this be "const struct sock_filter *"?
>> (...snipped...)
>> 	for (pc = 0; pc < flen; pc++) {
>> 		fentry = &filter[pc];
> Can't we do
> 		u32 f_k = fentry->k;
> and replace 27 repetition of fentry->k with f_k?

Ok, here is what I'm adding to net-2.6 (and will submit to -stable),
if anyone can spot any silly errors let me know now.

Thanks!

--------------------
filter: make sure filters dont read uninitialized memory

There is a possibility malicious users can get limited information about
uninitialized stack mem array. Even if sk_run_filter() result is bound
to packet length (0 .. 65535), we could imagine this can be used by
hostile user.

Initializing mem[] array, like Dan Rosenberg suggested in his patch is
expensive since most filters dont even use this array.

Its hard to make the filter validation in sk_chk_filter(), because of
the jumps. This might be done later.

In this patch, I use a bitmap (a single long var) so that only filters
using mem[] loads/stores pay the price of added security checks.

For other filters, additional cost is a single instruction.

[ Since we access fentry->k a lot now, cache it in a local variable
  and mark filter entry pointer as const. -DaveM ]

Reported-by: Dan Rosenberg <drosenberg@vsecurity.com>
Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
---
 net/core/filter.c |   64 +++++++++++++++++++++++++++++------------------------
 1 files changed, 35 insertions(+), 29 deletions(-)

diff --git a/net/core/filter.c b/net/core/filter.c
index 7beaec3..23e9b2a 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -112,39 +112,41 @@ EXPORT_SYMBOL(sk_filter);
  */
 unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int flen)
 {
-	struct sock_filter *fentry;	/* We walk down these */
 	void *ptr;
 	u32 A = 0;			/* Accumulator */
 	u32 X = 0;			/* Index Register */
 	u32 mem[BPF_MEMWORDS];		/* Scratch Memory Store */
+	unsigned long memvalid = 0;
 	u32 tmp;
 	int k;
 	int pc;
 
+	BUILD_BUG_ON(BPF_MEMWORDS > BITS_PER_LONG);
 	/*
 	 * Process array of filter instructions.
 	 */
 	for (pc = 0; pc < flen; pc++) {
-		fentry = &filter[pc];
+		const struct sock_filter *fentry = &filter[pc];
+		u32 f_k = fentry->k;
 
 		switch (fentry->code) {
 		case BPF_S_ALU_ADD_X:
 			A += X;
 			continue;
 		case BPF_S_ALU_ADD_K:
-			A += fentry->k;
+			A += f_k;
 			continue;
 		case BPF_S_ALU_SUB_X:
 			A -= X;
 			continue;
 		case BPF_S_ALU_SUB_K:
-			A -= fentry->k;
+			A -= f_k;
 			continue;
 		case BPF_S_ALU_MUL_X:
 			A *= X;
 			continue;
 		case BPF_S_ALU_MUL_K:
-			A *= fentry->k;
+			A *= f_k;
 			continue;
 		case BPF_S_ALU_DIV_X:
 			if (X == 0)
@@ -152,49 +154,49 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int
 			A /= X;
 			continue;
 		case BPF_S_ALU_DIV_K:
-			A /= fentry->k;
+			A /= f_k;
 			continue;
 		case BPF_S_ALU_AND_X:
 			A &= X;
 			continue;
 		case BPF_S_ALU_AND_K:
-			A &= fentry->k;
+			A &= f_k;
 			continue;
 		case BPF_S_ALU_OR_X:
 			A |= X;
 			continue;
 		case BPF_S_ALU_OR_K:
-			A |= fentry->k;
+			A |= f_k;
 			continue;
 		case BPF_S_ALU_LSH_X:
 			A <<= X;
 			continue;
 		case BPF_S_ALU_LSH_K:
-			A <<= fentry->k;
+			A <<= f_k;
 			continue;
 		case BPF_S_ALU_RSH_X:
 			A >>= X;
 			continue;
 		case BPF_S_ALU_RSH_K:
-			A >>= fentry->k;
+			A >>= f_k;
 			continue;
 		case BPF_S_ALU_NEG:
 			A = -A;
 			continue;
 		case BPF_S_JMP_JA:
-			pc += fentry->k;
+			pc += f_k;
 			continue;
 		case BPF_S_JMP_JGT_K:
-			pc += (A > fentry->k) ? fentry->jt : fentry->jf;
+			pc += (A > f_k) ? fentry->jt : fentry->jf;
 			continue;
 		case BPF_S_JMP_JGE_K:
-			pc += (A >= fentry->k) ? fentry->jt : fentry->jf;
+			pc += (A >= f_k) ? fentry->jt : fentry->jf;
 			continue;
 		case BPF_S_JMP_JEQ_K:
-			pc += (A == fentry->k) ? fentry->jt : fentry->jf;
+			pc += (A == f_k) ? fentry->jt : fentry->jf;
 			continue;
 		case BPF_S_JMP_JSET_K:
-			pc += (A & fentry->k) ? fentry->jt : fentry->jf;
+			pc += (A & f_k) ? fentry->jt : fentry->jf;
 			continue;
 		case BPF_S_JMP_JGT_X:
 			pc += (A > X) ? fentry->jt : fentry->jf;
@@ -209,7 +211,7 @@ unsigned int sk_run_filter(struct sk_buff *skb, struct sock_filter *filter, int
 			pc += (A & X) ? fentry->jt : fentry->jf;
 			continue;
 		case BPF_S_LD_W_ABS:
-			k = fentry->k;
+			k = f_k;
 load_w:
 			ptr = load_pointer(skb, k, 4, &tmp);
 			if (ptr != NULL) {
@@ -218,7 +220,7 @@ load_w:
 			}
 			break;
 		case BPF_S_LD_H_ABS:
-			k = fentry->k;
+			k = f_k;
 load_h:
 			ptr = load_pointer(skb, k, 2, &tmp);
 			if (ptr != NULL) {
@@ -227,7 +229,7 @@ load_h:
 			}
 			break;
 		case BPF_S_LD_B_ABS:
-			k = fentry->k;
+			k = f_k;
 load_b:
 			ptr = load_pointer(skb, k, 1, &tmp);
 			if (ptr != NULL) {
@@ -242,32 +244,34 @@ load_b:
 			X = skb->len;
 			continue;
 		case BPF_S_LD_W_IND:
-			k = X + fentry->k;
+			k = X + f_k;
 			goto load_w;
 		case BPF_S_LD_H_IND:
-			k = X + fentry->k;
+			k = X + f_k;
 			goto load_h;
 		case BPF_S_LD_B_IND:
-			k = X + fentry->k;
+			k = X + f_k;
 			goto load_b;
 		case BPF_S_LDX_B_MSH:
-			ptr = load_pointer(skb, fentry->k, 1, &tmp);
+			ptr = load_pointer(skb, f_k, 1, &tmp);
 			if (ptr != NULL) {
 				X = (*(u8 *)ptr & 0xf) << 2;
 				continue;
 			}
 			return 0;
 		case BPF_S_LD_IMM:
-			A = fentry->k;
+			A = f_k;
 			continue;
 		case BPF_S_LDX_IMM:
-			X = fentry->k;
+			X = f_k;
 			continue;
 		case BPF_S_LD_MEM:
-			A = mem[fentry->k];
+			A = (memvalid & (1UL << f_k)) ?
+				mem[f_k] : 0;
 			continue;
 		case BPF_S_LDX_MEM:
-			X = mem[fentry->k];
+			X = (memvalid & (1UL << f_k)) ?
+				mem[f_k] : 0;
 			continue;
 		case BPF_S_MISC_TAX:
 			X = A;
@@ -276,14 +280,16 @@ load_b:
 			A = X;
 			continue;
 		case BPF_S_RET_K:
-			return fentry->k;
+			return f_k;
 		case BPF_S_RET_A:
 			return A;
 		case BPF_S_ST:
-			mem[fentry->k] = A;
+			memvalid |= 1UL << f_k;
+			mem[f_k] = A;
 			continue;
 		case BPF_S_STX:
-			mem[fentry->k] = X;
+			memvalid |= 1UL << f_k;
+			mem[f_k] = X;
 			continue;
 		default:
 			WARN_ON(1);
-- 
1.7.3.2

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[Ben Hutchings]

On Wed, 2010-11-10 at 10:39 -0800, David Miller wrote:
[...]
> In this patch, I use a bitmap (a single long var) so that only filters
> using mem[] loads/stores pay the price of added security checks.
> 
> For other filters, additional cost is a single instruction.
> 
> [ Since we access fentry->k a lot now, cache it in a local variable
>   and mark filter entry pointer as const. -DaveM ]
[...]

I don't see the justification for combining these changes.  One patch,
one fix, right?

Ben.

-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[David Miller]

From: Ben Hutchings <bhutchings@solarflare.com>
Date: Wed, 10 Nov 2010 20:57:44 +0000

> On Wed, 2010-11-10 at 10:39 -0800, David Miller wrote:
> [...]
>> In this patch, I use a bitmap (a single long var) so that only filters
>> using mem[] loads/stores pay the price of added security checks.
>> 
>> For other filters, additional cost is a single instruction.
>> 
>> [ Since we access fentry->k a lot now, cache it in a local variable
>>   and mark filter entry pointer as const. -DaveM ]
> [...]
> 
> I don't see the justification for combining these changes.  One patch,
> one fix, right?

I'm minimizing the performance impact of the new bitmap checks.

Re: [PATCH] Prevent reading uninitialized memory with socketfilters

[Ben Hutchings]

On Wed, 2010-11-10 at 12:59 -0800, David Miller wrote:
> From: Ben Hutchings <bhutchings@solarflare.com>
> Date: Wed, 10 Nov 2010 20:57:44 +0000
> 
> > On Wed, 2010-11-10 at 10:39 -0800, David Miller wrote:
> > [...]
> >> In this patch, I use a bitmap (a single long var) so that only filters
> >> using mem[] loads/stores pay the price of added security checks.
> >> 
> >> For other filters, additional cost is a single instruction.
> >> 
> >> [ Since we access fentry->k a lot now, cache it in a local variable
> >>   and mark filter entry pointer as const. -DaveM ]
> > [...]
> > 
> > I don't see the justification for combining these changes.  One patch,
> > one fix, right?
> 
> I'm minimizing the performance impact of the new bitmap checks.

This seems like an entirely separate optimisation, since fentry->k was
*already* being used all over the place.  (And a smart compiler should
optimise that anyway... though I realise gcc is often not that smart.)

Ben.

-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[Dan Rosenberg]

> 
> Prove it.

I hope this was a joke.  In either case, my reply is a joke:

http://lists.grok.org.uk/pipermail/full-disclosure/2010-November/077321.html

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[Dan Rosenberg]

For reasons I don't understand, this code seems to cause some people's
machines to lock up:

BUG: soft lockup - CPU#0 stuck for 10s! [dz:11844]

I haven't been able to reproduce this myself.  Very strange.  I'll send
a stack trace if I can reproduce.

-Dan

On Wed, 2010-11-10 at 06:12 -0500, Dan Rosenberg wrote:
> > 
> > Prove it.
> 
> I hope this was a joke.  In either case, my reply is a joke:
> 
> http://lists.grok.org.uk/pipermail/full-disclosure/2010-November/077321.html

Re: [PATCH] Prevent reading uninitialized memory with socket filters

[David Miller]

From: Dan Rosenberg <drosenberg@vsecurity.com>
Date: Wed, 10 Nov 2010 06:12:47 -0500

> 
>> 
>> Prove it.
> 
> I hope this was a joke.

It absolutely is not.

You are very much not the first person ever to try and add an
expensive memset() here.

So the onus is really on you to prove this assertion and show the
exact code path by which the user can actually see any uninitialized
kernel stack memory (he can't, he can peek at certain values in a
certain extremely contrived range, making the leak useless), rather
than point us at some web external site archive of a list posting
which we cannot easily quote and reply to here.

I think you cannot do it, really.  Except in the AF_PACKET case, the
sockets can only see "0" or a negative error code, not the actual
sk_run_filter() return value.

In the one exception, AF_PACKET, the range of values the user can
see are in the range of MTU of the device being accessed, which
realistically is 1500 bytes.  This means the user cannot see any
kernel stack value outside of the range 0 to 1500, which isn't
worth using this expensive memset to guard against at all.

I don't even think it's worth adding all of the extra cpu cycles
incurred by Eric Dumazet's scheme of using a bitmap test on every
single memory buffer access.