[PATCH] xt_recent: Fix buffer overflow

[PATCH] xt_recent: Fix buffer overflow

[Tim Gardner]

>From 478a6cbbd7646c78370da48677e99cc602076dd7 Mon Sep 17 00:00:00 2001
From: Tim Gardner <tim.gardner@canonical.com>
Date: Thu, 18 Feb 2010 20:04:51 -0700
Subject: [PATCH] xt_recent: Fix buffer overflow

e->index overflows e->stamps[] every ip_pkt_list_tot
packets.

Consider the case when ip_pkt_list_tot==1; the first packet received is stored
in e->stamps[0] and e->index is initialized to 1. The next received packet
timestamp is then stored at e->stamps[1] in recent_entry_update(),
a buffer overflow because the maximum e->stamps[] index is 0.

Signed-off-by: Tim Gardner <tim.gardner@canonical.com>
Cc: stable@kernel.org
---
 net/netfilter/xt_recent.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/netfilter/xt_recent.c b/net/netfilter/xt_recent.c
index fc70a49..1bb0d6c 100644
--- a/net/netfilter/xt_recent.c
+++ b/net/netfilter/xt_recent.c
@@ -173,10 +173,10 @@ recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr,
 
 static void recent_entry_update(struct recent_table *t, struct recent_entry *e)
 {
+	e->index %= ip_pkt_list_tot;
 	e->stamps[e->index++] = jiffies;
 	if (e->index > e->nstamps)
 		e->nstamps = e->index;
-	e->index %= ip_pkt_list_tot;
 	list_move_tail(&e->lru_list, &t->lru_list);
 }
 
-- 
1.6.2.4

Re: [PATCH] xt_recent: Fix buffer overflow

[Jan Engelhardt]

On Friday 2010-02-19 18:48, Tim Gardner wrote:
>
>Consider the case when ip_pkt_list_tot==1; the first packet received is stored
>in e->stamps[0] and e->index is initialized to 1. The next received packet
>timestamp is then stored at e->stamps[1] in recent_entry_update(),
>a buffer overflow because the maximum e->stamps[] index is 0.

>@@ -173,10 +173,10 @@ recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr,
> 
> static void recent_entry_update(struct recent_table *t, struct recent_entry *e)
> {
>+	e->index %= ip_pkt_list_tot;
> 	e->stamps[e->index++] = jiffies;
> 	if (e->index > e->nstamps)
> 		e->nstamps = e->index;
>-	e->index %= ip_pkt_list_tot;
> 	list_move_tail(&e->lru_list, &t->lru_list);
> }

Let's analyze in 3-step manner:

Claim: writes always happen to e->stamps[0]
Prereqs: ip_pkt_list_tot==1
Proof:
 Start with assumption that e->index's possible values at the
 start of the function are {0}.
 The timestamp is thus always stored in e->stamps[0].
 e->index is bumped from 0 to 1.
 The %= op clamps it back to 0.
 The possible values at the end of the function are thus {0}.
 Assumption holds and matches the result set exactly.
 Outside of the function you will thus never see e->index != 0.

This does not seem much different from your proposed patch,
which reads like:

Claim: same
Prereq: same
Proof:
 e->index's possible start values are {0,1}.
 The %= op clamps this to {0}.
 The timestamp is always stored in e->stamps[0].
 e->index is increased by one.
 The possible values at the end of the function are {1}.
 Assumption holds, but is a superset of the result set.
 Outside of the function, you may see e->index != 0.


So both variations of the code do the same, except yours seems to
have the additional potential pitfall that e->index is not within the
ring of modulus after the function has been executed.


Where would the thinko be?

Re: [PATCH] xt_recent: Fix buffer overflow

[Tim Gardner]

Jan Engelhardt wrote:
> On Friday 2010-02-19 18:48, Tim Gardner wrote:
>> Consider the case when ip_pkt_list_tot==1; the first packet received is stored
>> in e->stamps[0] and e->index is initialized to 1. The next received packet
>> timestamp is then stored at e->stamps[1] in recent_entry_update(),
>> a buffer overflow because the maximum e->stamps[] index is 0.
> 
>> @@ -173,10 +173,10 @@ recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr,
>>
>> static void recent_entry_update(struct recent_table *t, struct recent_entry *e)
>> {
>> +	e->index %= ip_pkt_list_tot;
>> 	e->stamps[e->index++] = jiffies;
>> 	if (e->index > e->nstamps)
>> 		e->nstamps = e->index;
>> -	e->index %= ip_pkt_list_tot;
>> 	list_move_tail(&e->lru_list, &t->lru_list);
>> }
> 
> Let's analyze in 3-step manner:
> 
> Claim: writes always happen to e->stamps[0]
> Prereqs: ip_pkt_list_tot==1
> Proof:
>  Start with assumption that e->index's possible values at the
>  start of the function are {0}.

This assumption is the root of the bug. e->index is initialized to 1 in
recent_entry_init() which means that its already out of bounds when next
recent_entry_update() is called.

>  The timestamp is thus always stored in e->stamps[0].
>  e->index is bumped from 0 to 1.
>  The %= op clamps it back to 0.
>  The possible values at the end of the function are thus {0}.
>  Assumption holds and matches the result set exactly.
>  Outside of the function you will thus never see e->index != 0.
> 
> This does not seem much different from your proposed patch,
> which reads like:
> 
> Claim: same
> Prereq: same
> Proof:
>  e->index's possible start values are {0,1}.
>  The %= op clamps this to {0}.
>  The timestamp is always stored in e->stamps[0].
>  e->index is increased by one.
>  The possible values at the end of the function are {1}.
>  Assumption holds, but is a superset of the result set.
>  Outside of the function, you may see e->index != 0.
> 
> 
> So both variations of the code do the same, except yours seems to
> have the additional potential pitfall that e->index is not within the
> ring of modulus after the function has been executed.
> 
> 
> Where would the thinko be?
> 

rtg
-- 
Tim Gardner timg@tpi.com www.tpi.com
OR 503-601-0234 x102 MT 406-443-5357

Re: [PATCH] xt_recent: Fix buffer overflow

[Patrick McHardy]

Tim Gardner wrote:
> Jan Engelhardt wrote:
>> On Friday 2010-02-19 18:48, Tim Gardner wrote:
>>> Consider the case when ip_pkt_list_tot==1; the first packet received is stored
>>> in e->stamps[0] and e->index is initialized to 1. The next received packet
>>> timestamp is then stored at e->stamps[1] in recent_entry_update(),
>>> a buffer overflow because the maximum e->stamps[] index is 0.
>>> @@ -173,10 +173,10 @@ recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr,
>>>
>>> static void recent_entry_update(struct recent_table *t, struct recent_entry *e)
>>> {
>>> +	e->index %= ip_pkt_list_tot;
>>> 	e->stamps[e->index++] = jiffies;
>>> 	if (e->index > e->nstamps)
>>> 		e->nstamps = e->index;
>>> -	e->index %= ip_pkt_list_tot;
>>> 	list_move_tail(&e->lru_list, &t->lru_list);
>>> }
>> Let's analyze in 3-step manner:
>>
>> Claim: writes always happen to e->stamps[0]
>> Prereqs: ip_pkt_list_tot==1
>> Proof:
>>  Start with assumption that e->index's possible values at the
>>  start of the function are {0}.
> 
> This assumption is the root of the bug. e->index is initialized to 1 in
> recent_entry_init() which means that its already out of bounds when next
> recent_entry_update() is called.

This patch looks correct to me. Applied, thanks Tim.