Re: Bug in limit_mt_check()

Re: Bug in limit_mt_check()

[Jan Engelhardt]

Ccd netfilter-devel.

On Saturday 2012-09-22 00:26, Jim Robinson wrote:

> Hello
>
> Apologies if I'm directing this email to the wrong people. You two are major
> contributors to the xt_limit module, so I'm hoping that one of you may be able
> to help in sorting out a fix for upstream. If you're not the right people and
> can point me to someone who is, it would be appreciated.
>
> The bug is that under reproducible conditions, it is possible for
> limit_mt_check() to execute and kmalloc() a structure which does not get
> initialized. Specifically, if 'r->cost' is non-zero, 'priv' is kmalloc()ed but
> not initialized. The result of this is that 'priv->prev' and 'priv->credit'
> have bad values in them, and when limit_mt() later executes, it can incorrectly
> return 'true' (not limited) due to these bad values. [FWIW, we observed
> limit_mt() always returning 'true' under these circumstances, with the same bad
> values being present each time]
>
> Additionally, the circumstances for getting limit_mt_check() to execute with
> non-zero 'r->cost' are quite straightforward. Apparently, changes to iptables
> (insertion of a rate limit rule in a chain or replacing an arbitrary rule in a
> chain, to name the two I observed) causes limit_mt_check() to be called with
> non-zero 'r->cost' for each rate limit rule.
>
> I have attached the patch I put together for this bug. The patch is applied
> against the 2.6.32.8 kernel, however, the bug seems to also be in the 3.5
> kernel.
>
> Also attached is some other information I compiled while looking at the bug,
> including some debug traces.
>
> If any additional information is required do not hesitate to ask.
>
> Thanks
> Jim
>
>
>

Re: Bug in limit_mt_check()

[Jan Engelhardt]

On Saturday 2012-09-22 00:26, Jim Robinson wrote:
>
>The bug is that under reproducible conditions, it is possible for
>limit_mt_check() to execute and kmalloc() a structure which does not
>get initialized. Specifically, if 'r->cost' is non-zero, 'priv' is
>kmalloc()ed but not initialized. The result of this is that
>'priv->prev' and 'priv->credit' have bad values in them
>
>--8<-- (Jim's patch)
Without this patch the allocated 'priv' structure could be used without initializing. This
was causing premature rate-limit matches (i.e. limit_mt() returning 'true' when it shouldn't
have). This patch is a best guess as to how to initialize 'priv', and seems to work.

diff -Nur linux-2.6.32.8/net/netfilter/xt_limit.c.ORIG linux-2.6.32.8/net/netfilter/xt_limit.c
--- linux-2.6.32.8/net/netfilter/xt_limit.c.ORIG	2012-09-12 17:14:19.758371942 -0700
+++ linux-2.6.32.8/net/netfilter/xt_limit.c	2012-09-19 12:09:00.238416282 -0700
@@ -114,6 +114,32 @@
 	if (priv == NULL)
 		return false;
 
+    // Start of Infoblox patch.
+    // Zero out 'priv' for good measure.
+    memset(priv, 0, sizeof(*priv));
+    // This seems to fix the problem of priv not being initialized when
+    // r->cost is non-zero.
+    if (r->cost != 0) {
+        // Note that non-zero r->cost seems to imply non-null
+        // r->master, however, better safe than sorry, so check r->master.
+        if (r->master != NULL) {
+            spin_lock_bh(&limit_lock);
+            priv->prev = r->master->prev;
+            priv->credit = r->master->credit;
+            spin_unlock_bh(&limit_lock);
+        } else {
+            // Not sure if this can ever happen. And definitely not sure
+            // if this is the right thing to do, however, priv needs to be
+            // initialized to something.
+            printk("limit_mt_check: unexpected non-zero cost and null master\n");
+            priv->prev = jiffies;
+            priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
+        }
+        r->master = priv;
+        return true;
+    }
+    // End of Infoblox patch.
+
 	/* For SMP, we only want to use one set of state. */
 	r->master = priv;
 	if (r->cost == 0) {

Re: Bug in limit_mt_check()

[Jan Engelhardt]

>On Saturday 2012-09-22 00:26, Jim Robinson wrote:
>>
>>The bug is that under reproducible conditions, it is possible for
>>limit_mt_check() to execute and kmalloc() a structure which does not
>>get initialized. Specifically, if 'r->cost' is non-zero, 'priv' is
>>kmalloc()ed but not initialized. The result of this is that
>>'priv->prev' and 'priv->credit' have bad values in them
>>
>>--8<-- (Jim's patch)
>Without this patch the allocated 'priv' structure could be used without initializing. This
>was causing premature rate-limit matches (i.e. limit_mt() returning 'true' when it shouldn't
>have). This patch is a best guess as to how to initialize 'priv', and seems to work.
>
>diff -Nur linux-2.6.32.8/net/netfilter/xt_limit.c.ORIG linux-2.6.32.8/net/netfilter/xt_limit.c
>--- linux-2.6.32.8/net/netfilter/xt_limit.c.ORIG	2012-09-12 17:14:19.758371942 -0700
>+++ linux-2.6.32.8/net/netfilter/xt_limit.c	2012-09-19 12:09:00.238416282 -0700
>@@ -114,6 +114,32 @@
> 	if (priv == NULL)
> 		return false;
> 
>+    // Start of Infoblox patch.
>+    // Zero out 'priv' for good measure.
>+    memset(priv, 0, sizeof(*priv));
>+    // This seems to fix the problem of priv not being initialized when
>+    // r->cost is non-zero.
>+    if (r->cost != 0) {
>+        // Note that non-zero r->cost seems to imply non-null
>+        // r->master, however, better safe than sorry, so check r->master.
>+        if (r->master != NULL) {

r->master does not have any sensical value when it's coming from userspace.

>+            spin_lock_bh(&limit_lock);
>+            priv->prev = r->master->prev;
>+            priv->credit = r->master->credit;
>+            spin_unlock_bh(&limit_lock);
>+        } else {
>+            // Not sure if this can ever happen. And definitely not sure
>+            // if this is the right thing to do, however, priv needs to be
>+            // initialized to something.
>+            printk("limit_mt_check: unexpected non-zero cost and null master\n");
>+            priv->prev = jiffies;
>+            priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
>+        }
>+        r->master = priv;
>+        return true;
>+    }
>+    // End of Infoblox patch.
>+
> 	/* For SMP, we only want to use one set of state. */
> 	r->master = priv;
> 	if (r->cost == 0) {

A patch I think is better comes as reply to this message.

[PATCH] netfilter: have r->cost != 0 case work

[Jan Engelhardt]

Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
a running state is saved to userspace and then reinstated from there.

Make sure that priv is initialized with some values when that happens.

Signed-off-by: Jan Engelhardt <jengelh@inai.de>
---
 net/netfilter/xt_limit.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/net/netfilter/xt_limit.c b/net/netfilter/xt_limit.c
index 5c22ce8..a4c1e45 100644
--- a/net/netfilter/xt_limit.c
+++ b/net/netfilter/xt_limit.c
@@ -117,11 +117,11 @@ static int limit_mt_check(const struct xt_mtchk_param *par)
 
 	/* For SMP, we only want to use one set of state. */
 	r->master = priv;
+	/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
+	   128. */
+	priv->prev = jiffies;
+	priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
 	if (r->cost == 0) {
-		/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
-		   128. */
-		priv->prev = jiffies;
-		priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
 		r->credit_cap = priv->credit; /* Credits full. */
 		r->cost = user2credits(r->avg);
 	}
-- 
1.7.10.4

Re: [PATCH] netfilter: have r->cost != 0 case work

[Patrick McHardy]

Jan Engelhardt <jengelh@inai.de> schrieb:

>Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
>a running state is saved to userspace and then reinstated from there.
>
>Make sure that priv is initialized with some values when that happens.
>
>Signed-off-by: Jan Engelhardt <jengelh@inai.de>
>---
> net/netfilter/xt_limit.c |    8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
>diff --git a/net/netfilter/xt_limit.c b/net/netfilter/xt_limit.c
>index 5c22ce8..a4c1e45 100644
>--- a/net/netfilter/xt_limit.c
>+++ b/net/netfilter/xt_limit.c
>@@ -117,11 +117,11 @@ static int limit_mt_check(const struct
>xt_mtchk_param *par)
> 
> 	/* For SMP, we only want to use one set of state. */
> 	r->master = priv;
>+	/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>+	   128. */
>+	priv->prev = jiffies;
>+	priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
> 	if (r->cost == 0) {
>-		/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>-		   128. */
>-		priv->prev = jiffies;
>-		priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
> 		r->credit_cap = priv->credit; /* Credits full. */
> 		r->cost = user2credits(r->avg);
> 	}

I don't think we can do any better than this. We could reuse the old state from userspace, but that might have changed in the kernel as well.

Perhaps for the future we can find some way to optionally associate elements of the new ruleset with the old one and keep states when parameters haven't changed. Probably hard though since the new ruleset is constructed in the kernel while the old one is still active.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Jan Engelhardt]

On Sunday 2012-09-23 14:43, Patrick McHardy wrote:
>Jan Engelhardt <jengelh@inai.de> schrieb:
>
>>Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
>>a running state is saved to userspace and then reinstated from there.
>>
>>Make sure that priv is initialized with some values when that happens.
>>
>>Signed-off-by: Jan Engelhardt <jengelh@inai.de>
>>---
>> net/netfilter/xt_limit.c |    8 ++++----
>> 1 file changed, 4 insertions(+), 4 deletions(-)
>>
>>diff --git a/net/netfilter/xt_limit.c b/net/netfilter/xt_limit.c
>>index 5c22ce8..a4c1e45 100644
>>--- a/net/netfilter/xt_limit.c
>>+++ b/net/netfilter/xt_limit.c
>>@@ -117,11 +117,11 @@ static int limit_mt_check(const struct
>>xt_mtchk_param *par)
>> 
>> 	/* For SMP, we only want to use one set of state. */
>> 	r->master = priv;
>>+	/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>>+	   128. */
>>+	priv->prev = jiffies;
>>+	priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
>> 	if (r->cost == 0) {
>>-		/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>>-		   128. */
>>-		priv->prev = jiffies;
>>-		priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
>> 		r->credit_cap = priv->credit; /* Credits full. */
>> 		r->cost = user2credits(r->avg);
>> 	}
>
>I don't think we can do any better than this.

"This" being the state as of 3.5, or this patch?
priv-> really should be initialized, somehow.
Being a kernel-only structure, can't rely on userspace to do it.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Patrick McHardy]

On Mon, 24 Sep 2012, Jan Engelhardt wrote:

>
> On Sunday 2012-09-23 14:43, Patrick McHardy wrote:
>> Jan Engelhardt <jengelh@inai.de> schrieb:
>>
>>> Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
>>> a running state is saved to userspace and then reinstated from there.
>>>
>>> Make sure that priv is initialized with some values when that happens.
>>>
>>> Signed-off-by: Jan Engelhardt <jengelh@inai.de>
>>> ---
>>> net/netfilter/xt_limit.c |    8 ++++----
>>> 1 file changed, 4 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/net/netfilter/xt_limit.c b/net/netfilter/xt_limit.c
>>> index 5c22ce8..a4c1e45 100644
>>> --- a/net/netfilter/xt_limit.c
>>> +++ b/net/netfilter/xt_limit.c
>>> @@ -117,11 +117,11 @@ static int limit_mt_check(const struct
>>> xt_mtchk_param *par)
>>>
>>> 	/* For SMP, we only want to use one set of state. */
>>> 	r->master = priv;
>>> +	/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>>> +	   128. */
>>> +	priv->prev = jiffies;
>>> +	priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
>>> 	if (r->cost == 0) {
>>> -		/* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
>>> -		   128. */
>>> -		priv->prev = jiffies;
>>> -		priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
>>> 		r->credit_cap = priv->credit; /* Credits full. */
>>> 		r->cost = user2credits(r->avg);
>>> 	}
>>
>> I don't think we can do any better than this.
>
> "This" being the state as of 3.5, or this patch?
> priv-> really should be initialized, somehow.
> Being a kernel-only structure, can't rely on userspace to do it.

"This" as in your patch.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Jim Robinson]

[Retry with text formatting to try to make the vger.kernel.org spam 
filter happy this time]


Patrick McHardy wrote:
 >
 > Jan Engelhardt <jengelh@inai.de> schrieb:
 >
 >> Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
 >> a running state is saved to userspace and then reinstated from there.
 >>
 >> Make sure that priv is initialized with some values when that happens.
 >>
 >> Signed-off-by: Jan Engelhardt <jengelh@inai.de>
 >> ---
 >> net/netfilter/xt_limit.c |    8 ++++----
 >> 1 file changed, 4 insertions(+), 4 deletions(-)
 >>
 >> diff --git a/net/netfilter/xt_limit.c b/net/netfilter/xt_limit.c
 >> index 5c22ce8..a4c1e45 100644
 >> --- a/net/netfilter/xt_limit.c
 >> +++ b/net/netfilter/xt_limit.c
 >> @@ -117,11 +117,11 @@ static int limit_mt_check(const struct
 >> xt_mtchk_param *par)
 >>
 >>     /* For SMP, we only want to use one set of state. */
 >>     r->master = priv;
 >> +    /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
 >> +       128. */
 >> +    priv->prev = jiffies;
 >> +    priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
 >>     if (r->cost == 0) {
 >> -        /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
 >> -           128. */
 >> -        priv->prev = jiffies;
 >> -        priv->credit = user2credits(r->avg * r->burst); /* Credits 
full. */
 >>         r->credit_cap = priv->credit; /* Credits full. */
 >>         r->cost = user2credits(r->avg);
 >>     }
 > I don't think we can do any better than this. We could reuse the old 
state from userspace, but that might have changed in the kernel as well.
 >
 > Perhaps for the future we can find some way to optionally associate 
elements of the new ruleset with the old one and keep states when 
parameters haven't changed. Probably hard though since the new ruleset 
is constructed in the kernel while the old one is still active.
 >

Can you possibly elaborate on why my initial patch does not actually fix 
the problem? Specifically, the concern seems to be that the values in 
'r->master' in limit_mt_check() may not be reliable. In my testing I saw 
that r->master was the same (both address and values) as had been being 
used in limit_mt() calls for the rule. So if you could elaborate on the 
circumstances that could cause the values to not be the same, it would 
be appreciated.  In particular I don't understand the reference to 
'userspace'.

Below is the debugging trace I included as one the attachments I sent. 
It shows the calls applied to the same rate limit rule. Note that 
'r->master' in limit_mt_check() is the same address as 'r->master' in 
the previous limit_mt() calls. My testing indicated that the values were 
the same as well. Also note that the call to limit_mt_check() was 
triggered by an iptables change unrelated to that rule.

BTW, I am not at all saying you're wrong - you're the experts here. I'm 
just trying to understand why my patch doesn't actually fix the problem. 
This is for my own benefit and also because I'll have to explain it to 
my own powers-that-be, since the proposed fix basically resets the 
values and will guarantee a match in the next mt_limit() call(s) 
regardless of what should actually happen.

And as something of an aside, can you say why limit_mt_check() is called 
on all the rate limit rules when an unrelated iptables change occurs? 
This is what I observed.

Thanks
Jim

     limit_mt(): par=ffff880028203bd0 r=ffffc90003cfb138 
master=ffff88020f930fa0
     limit_mt(): par=ffff880028203bd0 r=ffffc90003cfb138 
master=ffff88020f930fa0
     limit_mt(): par=ffff880028203bd0 r=ffffc90003cfb138 
master=ffff88020f930fa0
     # bug triggered here
     limit_mt_check(): par=ffff880176a3bd98 r=ffffc90003d39138 
master=ffff88020f930fa0
                       new-master=ffff88020f930140 [this is the 
kmalloc()ed 'priv']
     limit_mt_destroy(): par=ffff880176a3bd38 r=ffffc90003cfb138 
master=ffff88020f930fa0
     limit_mt(): par=ffff880028203bd0 r=ffffc90003d39138 
master=ffff88020f930140
     limit_mt(): par=ffff880028203bd0 r=ffffc90003d39138 
master=ffff88020f930140
     limit_mt(): par=ffff880028203bd0 r=ffffc90003d39138 
master=ffff88020f930140

Re: [PATCH] netfilter: have r->cost != 0 case work

[Jan Engelhardt]

On Monday 2012-09-24 22:34, Jim Robinson wrote:
>
>Can you possibly elaborate on why my initial patch does not actually
>fix the problem? Specifically, the concern seems to be that the
>values in 'r->master' in limit_mt_check() may not be reliable. In my
>testing I saw that r->master was the same (both address and values)
>as had been being used in limit_mt() calls for the rule.

The ruleset may have already changed by the time the iptables
userspace process gets to send in the modified ruleset (with
an old r->master).

1. iptables instance 1 fetches ruleset
2. iptables instance 2 flushes the ruleset
3. iptables instance 1 reuploads the ruleset, now with a
   r->master pointing into the woods.
4. ???
5. boom.

Or, for extra giggles:

1. iptables instance 1 fetches ruleset
2. iptables instance 1 uploads ruleset
3. the new temporary table, i.e. the limit match inside it,
   (wrongly) reuses r->master
4. the old table frees all its private data.
   the new limit rule's r->master now points into the woods.
5. ???
6. boom.

>And as something of an aside, can you say why limit_mt_check() is called on all
>the rate limit rules when an unrelated iptables change occurs? This is what I
>observed.

First the new table is constructed, then atomically swapped with
the old one, after which the old one is freed.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Pablo Neira Ayuso]

On Sat, Sep 22, 2012 at 10:26:52AM +0200, Jan Engelhardt wrote:
> Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
> a running state is saved to userspace and then reinstated from there.
> 
> Make sure that priv is initialized with some values when that happens.

Just to clarify: With this patch, we go back to the situation in which
the state is reset on unrelated rule updates, right?

Re: [PATCH] netfilter: have r->cost != 0 case work

[Jan Engelhardt]

On Tuesday 2012-09-25 16:39, Pablo Neira Ayuso wrote:
>On Sat, Sep 22, 2012 at 10:26:52AM +0200, Jan Engelhardt wrote:
>> Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
>> a running state is saved to userspace and then reinstated from there.
>> 
>> Make sure that priv is initialized with some values when that happens.
>
>Just to clarify: With this patch, we go back to the situation in which
>the state is reset on unrelated rule updates, right?

Before this patch, when userspace updated a rule, random things 
would happen on matching due to use of uninitialized memory.

Now, the values are initialized, and implies that the credit is reset on 
table update.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Pablo Neira Ayuso]

On Tue, Sep 25, 2012 at 04:52:32PM +0200, Jan Engelhardt wrote:
> On Tuesday 2012-09-25 16:39, Pablo Neira Ayuso wrote:
> >On Sat, Sep 22, 2012 at 10:26:52AM +0200, Jan Engelhardt wrote:
> >> Commit v2.6.19-rc1~1272^2~41 tells us that r->cost != 0 can happen when
> >> a running state is saved to userspace and then reinstated from there.
> >> 
> >> Make sure that priv is initialized with some values when that happens.
> >
> >Just to clarify: With this patch, we go back to the situation in which
> >the state is reset on unrelated rule updates, right?
> 
> Before this patch, when userspace updated a rule, random things 
> would happen on matching due to use of uninitialized memory.

I know that ;-)

> Now, the values are initialized, and implies that the credit is reset on 
> table update.

This is what I wanted to confirm. Thanks Jan.

I'll pass this to David. Let's see if we can get this into 3.6-rc.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Jan Engelhardt]

On Wednesday 2012-09-26 01:27, Pablo Neira Ayuso wrote:
>
>> Now, the values are initialized, and implies that the credit is reset on 
>> table update.
>
>This is what I wanted to confirm. Thanks Jan.
>
>I'll pass this to David. Let's see if we can get this into 3.6-rc.

This would even be -stable material.

Re: [PATCH] netfilter: have r->cost != 0 case work

[Pablo Neira Ayuso]

On Wed, Sep 26, 2012 at 03:28:27PM +0200, Jan Engelhardt wrote:
> 
> On Wednesday 2012-09-26 01:27, Pablo Neira Ayuso wrote:
> >
> >> Now, the values are initialized, and implies that the credit is reset on 
> >> table update.
> >
> >This is what I wanted to confirm. Thanks Jan.
> >
> >I'll pass this to David. Let's see if we can get this into 3.6-rc.
> 
> This would even be -stable material.

Yes. Likely that we missed 3.6-rc7, so David may pass this to -stable
himself.

I have a long queue of things to pass to -stable. My plan is to spend
time on getting things into it now that the merge window will be
closed.