[PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[Changli Gao]

use skb_copy_bits() to dereference data safely

the original skb->data dereference isn't safe, as there isn't any skb->len or
skb_is_nonlinear() check. skb_copy_bits() is used instead in this patch. And
when the skb isn't long enough, we terminate the function u32_classify()
immediately with -1.

Signed-off-by: Changli Gao <xiaosuo@gmail.com>
----
 net/sched/cls_u32.c |   40 +++++++++++++++++++++++++++++-----------
 1 file changed, 29 insertions(+), 11 deletions(-)
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 9627542..db35197 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -98,11 +98,11 @@ static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_re
 {
 	struct {
 		struct tc_u_knode *knode;
-		u8		  *ptr;
+		unsigned int	  off;
 	} stack[TC_U32_MAXDEPTH];
 
 	struct tc_u_hnode *ht = (struct tc_u_hnode*)tp->root;
-	u8 *ptr = skb_network_header(skb);
+	unsigned int off = skb_network_header(skb) - skb->data;
 	struct tc_u_knode *n;
 	int sdepth = 0;
 	int off2 = 0;
@@ -134,8 +134,13 @@ next_knode:
 #endif
 
 		for (i = n->sel.nkeys; i>0; i--, key++) {
+			unsigned int toff;
+			__be32 data;
 
-			if ((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {
+			toff = off + key->off + (off2 & key->offmask);
+			if (skb_copy_bits(skb, toff, &data, 4))
+				goto out;
+			if ((data ^ key->val) & key->mask) {
 				n = n->next;
 				goto next_knode;
 			}
@@ -174,29 +179,41 @@ check_terminal:
 		if (sdepth >= TC_U32_MAXDEPTH)
 			goto deadloop;
 		stack[sdepth].knode = n;
-		stack[sdepth].ptr = ptr;
+		stack[sdepth].off = off;
 		sdepth++;
 
 		ht = n->ht_down;
 		sel = 0;
-		if (ht->divisor)
-			sel = ht->divisor&u32_hash_fold(*(__be32*)(ptr+n->sel.hoff), &n->sel,n->fshift);
+		if (ht->divisor) {
+			__be32 data;
 
+			if (skb_copy_bits(skb, off + n->sel.hoff, &data, 4))
+				goto out;
+			sel = ht->divisor & u32_hash_fold(data, &n->sel,
+							  n->fshift);
+		}
 		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
 			goto next_ht;
 
 		if (n->sel.flags&(TC_U32_OFFSET|TC_U32_VAROFFSET)) {
 			off2 = n->sel.off + 3;
-			if (n->sel.flags&TC_U32_VAROFFSET)
-				off2 += ntohs(n->sel.offmask & *(__be16*)(ptr+n->sel.offoff)) >>n->sel.offshift;
+			if (n->sel.flags & TC_U32_VAROFFSET) {
+				__be16 data;
+
+				if (skb_copy_bits(skb, off + n->sel.offoff,
+						  &data, 2))
+					goto out;
+				off2 += ntohs(n->sel.offmask & data) >>
+					n->sel.offshift;
+			}
 			off2 &= ~3;
 		}
 		if (n->sel.flags&TC_U32_EAT) {
-			ptr += off2;
+			off += off2;
 			off2 = 0;
 		}
 
-		if (ptr < skb_tail_pointer(skb))
+		if (off < skb->len)
 			goto next_ht;
 	}
 
@@ -204,9 +221,10 @@ check_terminal:
 	if (sdepth--) {
 		n = stack[sdepth].knode;
 		ht = n->ht_up;
-		ptr = stack[sdepth].ptr;
+		off = stack[sdepth].off;
 		goto check_terminal;
 	}
+out:
 	return -1;
 
 deadloop:

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

Hi Changli,

On Mon, 2010-05-31 at 10:24 +0800, Changli Gao wrote:
> use skb_copy_bits() to dereference data safely
> 
> the original skb->data dereference isn't safe, as there isn't any skb->len or
> skb_is_nonlinear() check. 

I dont see any safety issue in current code in this respect. Do you have
a specific scenario where this would be unsafe? We inspect in 32 bit
chunks walking the packet data and stop when there is no more packet
data.

> skb_copy_bits() is used instead in this patch. And
> when the skb isn't long enough, we terminate the function u32_classify()
> immediately with -1.
> 

That could be a very interesting optimization - but i see it as _very
hard_ to do with current u32 given it has branching and different
branches would have different lengths etc. You'd have to essentially do
some math in user space as to what min length would suffice given
a specified filter and pass that to the kernel. 


cheers,
jamal

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[Changli Gao]

On Tue, Jun 1, 2010 at 8:34 PM, jamal <hadi@cyberus.ca> wrote:
> Hi Changli,
>
> On Mon, 2010-05-31 at 10:24 +0800, Changli Gao wrote:
>> use skb_copy_bits() to dereference data safely
>>
>> the original skb->data dereference isn't safe, as there isn't any skb->len or
>> skb_is_nonlinear() check.
>
> I dont see any safety issue in current code in this respect. Do you have
> a specific scenario where this would be unsafe? We inspect in 32 bit
> chunks walking the packet data and stop when there is no more packet
> data.

I added the following debug code into cls_u32.c

                for (i = n->sel.nkeys; i>0; i--, key++) {
+                       int off;
+
+                       off = key->off+(off2&key->offmask) + (ptr - skb->data);
+                       if (off + 4 > skb->len)
+                               printk("skb->len: %d, off: %d\n",
skb->len, off);

                        if
((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {
                                n = n->next;
@@ -179,8 +186,13 @@ check_terminal:

                ht = n->ht_down;
                sel = 0;
-               if (ht->divisor)
+               if (ht->divisor) {
+                       int off = ptr - skb->data + n->sel.hoff;
+                       if (off + 4 > skb->len)
+                               printk("skb->len: %d, off: %d\n", skb->len,
+                                       off);
                        sel =
ht->divisor&u32_hash_fold(*(__be32*)(ptr+n->sel.hoff),
&n->sel,n->fshift);
+               }

the tc filter command is:

tc filter add dev eth0 parent 8001:0 proto ip  u32 match u32
0x00000000 0x0000ffff at 40

Then I execute nc to connect to an UDP port:

localhost linux # nc -u 192.168.235.1 80

localhost linux #

just press enter.

I got these demsg:

[ 7525.330604] skb->len: 43, off: 54

we are trying to access the memory out of this skb.

>
>> skb_copy_bits() is used instead in this patch. And
>> when the skb isn't long enough, we terminate the function u32_classify()
>> immediately with -1.
>>
>
> That could be a very interesting optimization - but i see it as _very
> hard_ to do with current u32 given it has branching and different
> branches would have different lengths etc. You'd have to essentially do
> some math in user space as to what min length would suffice given
> a specified filter and pass that to the kernel.
>

It isn't an optimization, but an error exit. :)

-- 
Regards,
Changli Gao(xiaosuo@gmail.com)

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

Hi Changli,

On Wed, 2010-06-02 at 01:47 +0800, Changli Gao wrote:

> 
> I added the following debug code into cls_u32.c
> 
>                 for (i = n->sel.nkeys; i>0; i--, key++) {
> +                       int off;
> +
> +                       off = key->off+(off2&key->offmask) + (ptr - skb->data);
> +                       if (off + 4 > skb->len)
> +                               printk("skb->len: %d, off: %d\n",
> skb->len, off);
> 

Ok, makes more sense. And thanks for taking time to construct a
meaningful example.
It is not a common use - but i agree it is a bug.
I am suprised we never caught this all this years and wondering why this
never crashed in your example?
Can we make the fix very simple please? i.e no copy bits, this is the
fast path.

> It isn't an optimization, but an error exit. :)

What i meant was if you can tell immediately what the maximum offset is
then you dont need to go through for loop making comparison with each
key. You could immediately bailout - which is an optimization ;->

cheers,
jamal

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

On Wed, 2010-06-02 at 08:21 -0400, jamal wrote:

> Can we make the fix very simple please? i.e no copy bits, this is the
> fast path.

Example, something along lines of:

---
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 9627542..dde7a23 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -135,6 +135,9 @@ next_knode:
 
 for (i = n->sel.nkeys; i>0; i--, key++) {
 
+        int toff = key->off+(off2&key->offmask)- 4;
+        if (unlikely(toff > skb->len))
+              /* bailout here - needs some thought */
         if ((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->v
             n = n->next;
             goto next_knode;
----


cheers,
jamal

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[David Miller]

From: jamal <hadi@cyberus.ca>
Date: Wed, 02 Jun 2010 08:25:38 -0400

> --- a/net/sched/cls_u32.c
> +++ b/net/sched/cls_u32.c
> @@ -135,6 +135,9 @@ next_knode:
>  
>  for (i = n->sel.nkeys; i>0; i--, key++) {
>  
> +        int toff = key->off+(off2&key->offmask)- 4;
> +        if (unlikely(toff > skb->len))
> +              /* bailout here - needs some thought */
>          if ((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->v

I don't think it's that simple.

You can't dereference from the skb->data linear area if your offset is
beyond "skb->len - skb->data_len" (aka. skb_headlen()) since that's
where the paged or fragmented portion starts.

We really need to use skb_copy_bits() if we want to allow
any offset into the SKB, and because of all the ways
packets can be transformed and constructed we absolutely
have to.

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[David Miller]

From: jamal <hadi@cyberus.ca>
Date: Wed, 02 Jun 2010 08:20:19 -0400

> I am suprised we never caught this all this years and wondering why
> this never crashed in your example?

Well for one thing there is all sorts of "stuff" past the end of the
valid skb->data area.  For example, there is some padding and then
there is skb_shared_info().

Furthermore, the kernel allocator can round up the size it uses for
SLAB objects which gives even more padding past the end of even
skb_shared_info().

Futrhermore, the chance of the page past the page skb->data is in
being invalid is very low.  You'd have to have invalid memory in the
page after the skb->data.

All of this conspires to just letting blind reads work in a large
number of illegal cases.

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[Changli Gao]

On Wed, Jun 2, 2010 at 8:45 PM, David Miller <davem@davemloft.net> wrote:
> From: jamal <hadi@cyberus.ca>
> Date: Wed, 02 Jun 2010 08:25:38 -0400
>
>> --- a/net/sched/cls_u32.c
>> +++ b/net/sched/cls_u32.c
>> @@ -135,6 +135,9 @@ next_knode:
>>
>>  for (i = n->sel.nkeys; i>0; i--, key++) {
>>
>> +        int toff = key->off+(off2&key->offmask)- 4;
>> +        if (unlikely(toff > skb->len))
>> +              /* bailout here - needs some thought */
>>          if ((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->v
>
> I don't think it's that simple.
>
> You can't dereference from the skb->data linear area if your offset is
> beyond "skb->len - skb->data_len" (aka. skb_headlen()) since that's
> where the paged or fragmented portion starts.
>
> We really need to use skb_copy_bits() if we want to allow
> any offset into the SKB, and because of all the ways
> packets can be transformed and constructed we absolutely
> have to.
>

Maybe skb_header_pointer() is lighter.


-- 
Regards,
Changli Gao(xiaosuo@gmail.com)

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[Changli Gao]

On Wed, Jun 2, 2010 at 8:20 PM, jamal <hadi@cyberus.ca> wrote:
>
> What i meant was if you can tell immediately what the maximum offset is
> then you dont need to go through for loop making comparison with each
> key. You could immediately bailout - which is an optimization ;->
>

I got it. But it isn't easy for me.

-- 
Regards,
Changli Gao(xiaosuo@gmail.com)

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[David Miller]

From: Changli Gao <xiaosuo@gmail.com>
Date: Wed, 2 Jun 2010 21:14:55 +0800

> On Wed, Jun 2, 2010 at 8:45 PM, David Miller <davem@davemloft.net> wrote:
>> From: jamal <hadi@cyberus.ca>
>> Date: Wed, 02 Jun 2010 08:25:38 -0400
>>
>>> --- a/net/sched/cls_u32.c
>>> +++ b/net/sched/cls_u32.c
>>> @@ -135,6 +135,9 @@ next_knode:
>>>
>>>  for (i = n->sel.nkeys; i>0; i--, key++) {
>>>
>>> +        int toff = key->off+(off2&key->offmask)- 4;
>>> +        if (unlikely(toff > skb->len))
>>> +              /* bailout here - needs some thought */
>>>          if ((*(__be32*)(ptr+key->off+(off2&key->offmask))^key->v
>>
>> I don't think it's that simple.
>>
>> You can't dereference from the skb->data linear area if your offset is
>> beyond "skb->len - skb->data_len" (aka. skb_headlen()) since that's
>> where the paged or fragmented portion starts.
>>
>> We really need to use skb_copy_bits() if we want to allow
>> any offset into the SKB, and because of all the ways
>> packets can be transformed and constructed we absolutely
>> have to.
>>
> 
> Maybe skb_header_pointer() is lighter.

Yes, it should be.  In fact, it's designed for this kind of situation
and that's why it's used extensively in netfilter.

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

On Wed, 2010-06-02 at 21:14 +0800, Changli Gao wrote:


> Maybe skb_header_pointer() is lighter.

A little worse than skb_copy_bits(). In any case, this change is going
to hurt.
Dave, can we assume the upper layers(qdiscs in this case) are
responsible for any linearizing?

Changli, if you have time - can you also audit tcf_pedit()
since it follows TheLinuxWay(tm).

cheers,
jamal

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[Changli Gao]

On Wed, Jun 2, 2010 at 9:36 PM, jamal <hadi@cyberus.ca> wrote:
> On Wed, 2010-06-02 at 21:14 +0800, Changli Gao wrote:
>
>
>> Maybe skb_header_pointer() is lighter.
>
> A little worse than skb_copy_bits(). In any case, this change is going
> to hurt.

Why? it is an inline function, and in most cases, there isn't any function call.

> Dave, can we assume the upper layers(qdiscs in this case) are
> responsible for any linearizing?
>
> Changli, if you have time - can you also audit tcf_pedit()
> since it follows TheLinuxWay(tm).
>

Yea, pedit has the same issue. Besides this issue, they should use
get_unaligned() instead.


-- 
Regards,
Changli Gao(xiaosuo@gmail.com)

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[David Miller]

From: jamal <hadi@cyberus.ca>
Date: Wed, 02 Jun 2010 09:36:37 -0400

> On Wed, 2010-06-02 at 21:14 +0800, Changli Gao wrote:
> 
> 
>> Maybe skb_header_pointer() is lighter.
> 
> A little worse than skb_copy_bits(). In any case, this change is going
> to hurt.

Umm, Jamal what are you talking about?

Using skb_header_pointer(), if the offset is in range, there is no
change from today other than a comparison.

If it is not in range, we use skb_copy_bits().  It's only for the
case where we have to fetch the value from the fragmented part
of the SKB.

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

On Wed, 2010-06-02 at 06:43 -0700, David Miller wrote:
> From: jamal <hadi@cyberus.ca>

> > 
> > A little worse than skb_copy_bits(). In any case, this change is going
> > to hurt.
> 
> Umm, Jamal what are you talking about?

;->

> Using skb_header_pointer(), if the offset is in range, there is no
> change from today other than a comparison.

Thats the part i glossed over - My eyes just saw "it calls
skb_copy_bits()" ;->

> If it is not in range, we use skb_copy_bits().  It's only for the
> case where we have to fetch the value from the fragmented part
> of the SKB.

cheers,
jamal

Re: [PATCH] cls_u32: use skb_copy_bits() to dereference data safely

[jamal]

On Wed, 2010-06-02 at 21:43 +0800, Changli Gao wrote:

> Yea, pedit has the same issue. Besides this issue, they should use
> get_unaligned() instead.

sounds reasonable - although they are probably different patches with
the offset fix being more important.

cheers,
jamal