[PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[Oliver]

From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>

This fixes a serious bug affecting all hash types with a net element -
specifically, if a CIDR value is deleted such that none of the same size
exist any more, all larger (less-specific) values will then fail to
match. Adding back any prefix with a CIDR equal to or more specific than
the one deleted will fix it.

Steps to reproduce:
ipset -N test hash:net
ipset -A test 1.1.0.0/16
ipset -A test 2.2.2.0/24
ipset -T test 1.1.1.1		#1.1.1.1 IS in set
ipset -D test 2.2.2.0/24
ipset -T test 1.1.1.1		#1.1.1.1 IS NOT in set

This is due to the fact that the nets counter was unconditionally
decremented prior to the iteration that shifts up the entries. Now, we
first check if there is a proceeding entry and if not, decrement it and
return. Otherwise, we proceed to iterate and then clean up the last
element afterwards.

Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
---
 kernel/net/netfilter/ipset/ip_set_hash_gen.h | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h b/kernel/net/netfilter/ipset/ip_set_hash_gen.h
index 7a5b776..f0f0c8d 100644
--- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h
+++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h
@@ -311,15 +311,17 @@ mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n)
 
 	for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++)
 		;
-	h->nets[i].nets[n]--;
-
-	if (h->nets[i].nets[n] != 0)
+	if (h->nets[i+1].nets[n] == 0) {
+		h->nets[i].nets[n]--;
 		return;
+	}
 
 	for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) {
 		h->nets[j].cidr[n] = h->nets[j + 1].cidr[n];
 		h->nets[j].nets[n] = h->nets[j + 1].nets[n];
 	}
+	h->nets[j].cidr[n] = 0;
+	h->nets[j].nets[n] = 0;
 }
 #endif
 
-- 
1.8.3.2

Re: [PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[Jozsef Kadlecsik]

On Tue, 10 Sep 2013, Oliver wrote:

> From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> 
> This fixes a serious bug affecting all hash types with a net element -
> specifically, if a CIDR value is deleted such that none of the same size
> exist any more, all larger (less-specific) values will then fail to
> match. Adding back any prefix with a CIDR equal to or more specific than
> the one deleted will fix it.
> 
> Steps to reproduce:
> ipset -N test hash:net
> ipset -A test 1.1.0.0/16
> ipset -A test 2.2.2.0/24
> ipset -T test 1.1.1.1		#1.1.1.1 IS in set
> ipset -D test 2.2.2.0/24
> ipset -T test 1.1.1.1		#1.1.1.1 IS NOT in set
> 
> This is due to the fact that the nets counter was unconditionally
> decremented prior to the iteration that shifts up the entries. Now, we
> first check if there is a proceeding entry and if not, decrement it and
> return. Otherwise, we proceed to iterate and then clean up the last
> element afterwards.
> 
> Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>

Good catch! But unconditionally checking the next entry may point over the 
array.

> ---
>  kernel/net/netfilter/ipset/ip_set_hash_gen.h | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/net/netfilter/ipset/ip_set_hash_gen.h b/kernel/net/netfilter/ipset/ip_set_hash_gen.h
> index 7a5b776..f0f0c8d 100644
> --- a/kernel/net/netfilter/ipset/ip_set_hash_gen.h
> +++ b/kernel/net/netfilter/ipset/ip_set_hash_gen.h
> @@ -311,15 +311,17 @@ mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n)
>  
>  	for (i = 0; i < nets_length - 1 && h->nets[i].cidr[n] != cidr; i++)
>  		;
> -	h->nets[i].nets[n]--;
> -
> -	if (h->nets[i].nets[n] != 0)
> +	if (h->nets[i+1].nets[n] == 0) {

Here the checking of i+1 is missing.

> +		h->nets[i].nets[n]--;
>  		return;
> +	}
>  
>  	for (j = i; j < nets_length - 1 && h->nets[j].nets[n]; j++) {
>  		h->nets[j].cidr[n] = h->nets[j + 1].cidr[n];
>  		h->nets[j].nets[n] = h->nets[j + 1].nets[n];
>  	}
> +	h->nets[j].cidr[n] = 0;
> +	h->nets[j].nets[n] = 0;
>  }
>  #endif
>  
> -- 
> 1.8.3.2

Please resubmit a fixed patch and I'll apply it. Thanks!

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: [PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[Oliver]

On Tuesday 10 September 2013 23:55:14 Jozsef Kadlecsik wrote:
> On Tue, 10 Sep 2013, Oliver wrote:
> > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> > 
> > This fixes a serious bug affecting all hash types with a net element -
> > specifically, if a CIDR value is deleted such that none of the same size
> > exist any more, all larger (less-specific) values will then fail to
> > match. Adding back any prefix with a CIDR equal to or more specific than
> > the one deleted will fix it.
> > 
> > Steps to reproduce:
> > ipset -N test hash:net
> > ipset -A test 1.1.0.0/16
> > ipset -A test 2.2.2.0/24
> > ipset -T test 1.1.1.1		#1.1.1.1 IS in set
> > ipset -D test 2.2.2.0/24
> > ipset -T test 1.1.1.1		#1.1.1.1 IS NOT in set
> > 
> > This is due to the fact that the nets counter was unconditionally
> > decremented prior to the iteration that shifts up the entries. Now, we
> > first check if there is a proceeding entry and if not, decrement it and
> > return. Otherwise, we proceed to iterate and then clean up the last
> > element afterwards.
> > 
> > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> 
> Good catch! But unconditionally checking the next entry may point over the
> array.

Are you sure? In mtype_del_cidr() we only iterate up to (nets_length - 1) 
rather than nets_length, so I didn't think that i+1 could end up going over 
the end of the array.

Kind Regards,
Oliver.

Re: [PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[Jozsef Kadlecsik]

On Wed, 11 Sep 2013, Oliver wrote:

> On Tuesday 10 September 2013 23:55:14 Jozsef Kadlecsik wrote:
> > On Tue, 10 Sep 2013, Oliver wrote:
> > > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> > > 
> > > This fixes a serious bug affecting all hash types with a net element -
> > > specifically, if a CIDR value is deleted such that none of the same size
> > > exist any more, all larger (less-specific) values will then fail to
> > > match. Adding back any prefix with a CIDR equal to or more specific than
> > > the one deleted will fix it.
> > > 
> > > Steps to reproduce:
> > > ipset -N test hash:net
> > > ipset -A test 1.1.0.0/16
> > > ipset -A test 2.2.2.0/24
> > > ipset -T test 1.1.1.1		#1.1.1.1 IS in set
> > > ipset -D test 2.2.2.0/24
> > > ipset -T test 1.1.1.1		#1.1.1.1 IS NOT in set
> > > 
> > > This is due to the fact that the nets counter was unconditionally
> > > decremented prior to the iteration that shifts up the entries. Now, we
> > > first check if there is a proceeding entry and if not, decrement it and
> > > return. Otherwise, we proceed to iterate and then clean up the last
> > > element afterwards.
> > > 
> > > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> > 
> > Good catch! But unconditionally checking the next entry may point over the
> > array.
> 
> Are you sure? In mtype_del_cidr() we only iterate up to (nets_length - 1) 
> rather than nets_length, so I didn't think that i+1 could end up going over 
> the end of the array.

(nets_length - 1) is the last index in the array. In the first for loop 
"i" can reach this value, so "i+1" is over the array.

Also, your patch decrements the nets[i] value only if the next entry is 
empty, that an error too.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlecsik.jozsef@wigner.mta.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : Wigner Research Centre for Physics, Hungarian Academy of Sciences
          H-1525 Budapest 114, POB. 49, Hungary

Re: [PATCH] netfilter: ipset: Fix serious failure in CIDR tracking

[Oliver]

On Wednesday 11 September 2013 09:05:03 Jozsef Kadlecsik wrote:
> On Wed, 11 Sep 2013, Oliver wrote:
> > On Tuesday 10 September 2013 23:55:14 Jozsef Kadlecsik wrote:
> > > On Tue, 10 Sep 2013, Oliver wrote:
> > > > From: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> > > > 
> > > > This fixes a serious bug affecting all hash types with a net element -
> > > > specifically, if a CIDR value is deleted such that none of the same
> > > > size
> > > > exist any more, all larger (less-specific) values will then fail to
> > > > match. Adding back any prefix with a CIDR equal to or more specific
> > > > than
> > > > the one deleted will fix it.
> > > > 
> > > > Steps to reproduce:
> > > > ipset -N test hash:net
> > > > ipset -A test 1.1.0.0/16
> > > > ipset -A test 2.2.2.0/24
> > > > ipset -T test 1.1.1.1		#1.1.1.1 IS in set
> > > > ipset -D test 2.2.2.0/24
> > > > ipset -T test 1.1.1.1		#1.1.1.1 IS NOT in set
> > > > 
> > > > This is due to the fact that the nets counter was unconditionally
> > > > decremented prior to the iteration that shifts up the entries. Now, we
> > > > first check if there is a proceeding entry and if not, decrement it
> > > > and
> > > > return. Otherwise, we proceed to iterate and then clean up the last
> > > > element afterwards.
> > > > 
> > > > Signed-off-by: Oliver Smith <oliver@8.c.9.b.0.7.4.0.1.0.0.2.ip6.arpa>
> > > 
> > > Good catch! But unconditionally checking the next entry may point over
> > > the
> > > array.
> > 
> > Are you sure? In mtype_del_cidr() we only iterate up to (nets_length - 1)
> > rather than nets_length, so I didn't think that i+1 could end up going
> > over
> > the end of the array.
> 
> (nets_length - 1) is the last index in the array. In the first for loop
> "i" can reach this value, so "i+1" is over the array.

OK, I see.
> 
> Also, your patch decrements the nets[i] value only if the next entry is
> empty, that an error too.

Yep, I've redone it so that we decrement if it's > 1 OR the last possible 
position OR there's nothing beyond it. Otherwise, it's left untouched and we 
loop, which then overwrites it on the first iteration.

Kind Regards,
Oliver.