Skip to contentSkip to conversation

xt_recent: Fix buffer overflow

PATCH In review Tim Gardner 3 participants 4 messages Feb 19, 2010 – Feb 23, 2010

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 xt_recent: Fix buffer overflow

From 478a6cbbd7646c78370da48677e99cc602076dd7 Mon Sep 17 00:00:00 2001
From: Tim Gardner <[email protected]>
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.

---
 net/netfilter/xt_recent.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
net/netfilter/xt_recent.c +1 -1
index fc70a49..1bb0d6c 100644
@@ -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);
 }
 
Signature · 1 line
1.6.2.4
#1 lore raw
Quoted 7 lines · Tim Gardner

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.

net/netfilter/xt_recent.c recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr, · line 181

Quoted 10 lines
net/netfilter/xt_recent.c +1 -1
@@ -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?

#2 lore raw
Quoted 20 lines · Jan Engelhardt
Quoted 6 lines · Tim Gardner

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.

net/netfilter/xt_recent.c recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr, · line 181

Quoted 10 lines
net/netfilter/xt_recent.c +1 -1
@@ -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:

Quoted 5 lines

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.

Quoted 22 lines

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.

Quoted 7 lines

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

Signature · 2 lines
Tim Gardner [email protected] www.tpi.com
OR 503-601-0234 x102 MT 406-443-5357
#3 lore raw
Quoted 25 lines · Tim Gardner
Quoted 18 lines · Jan Engelhardt
Quoted 5 lines · Tim Gardner

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.

net/netfilter/xt_recent.c recent_entry_init(struct recent_table *t, const union nf_inet_addr *addr, · line 181

Quoted 10 lines
net/netfilter/xt_recent.c +1 -1
@@ -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:

Quoted 5 lines

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}.

Quoted 3 lines

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.