[PATCH xt-addons] xt_geoip: fix possible out-of-bounds access

[PATCH xt-addons] xt_geoip: fix possible out-of-bounds access

[Florian Westphal]

It is possible for geoip_bsearch() to pick mid == sizeof(subnets).

Consider a set with a single entry and a "address to test"
higher than the range:

1st call: lo = 0, hi = 1 -> mid will be 0
2nd call: lo = 1, hi = 1 -> mid will be 1

On the 2nd call, we'll examine random data.

Fix is to use the maximum valid index instead of the number of elements
in the first geoip_bsearch call.
---
 extensions/xt_geoip.c |   16 +++++++++-------
 1 files changed, 9 insertions(+), 7 deletions(-)

diff --git a/extensions/xt_geoip.c b/extensions/xt_geoip.c
index 4c6b29f..5b2e237 100644
--- a/extensions/xt_geoip.c
+++ b/extensions/xt_geoip.c
@@ -33,7 +33,7 @@ struct geoip_country_kernel {
 	struct list_head list;
 	struct geoip_subnet *subnets;
 	atomic_t ref;
-	unsigned int count;
+	unsigned int max;
 	unsigned short cc;
 };
 
@@ -51,24 +51,26 @@ geoip_add_node(const struct geoip_country_user __user *umem_ptr)
 	if (copy_from_user(&umem, umem_ptr, sizeof(umem)) != 0)
 		return ERR_PTR(-EFAULT);
 
+	if (umem.count == 0)
+		return ERR_PTR(-EINVAL);
+
 	p = kmalloc(sizeof(struct geoip_country_kernel), GFP_KERNEL);
 	if (p == NULL)
 		return ERR_PTR(-ENOMEM);
 
-	p->count   = umem.count;
-	p->cc      = umem.cc;
-
-	s = vmalloc(p->count * sizeof(struct geoip_subnet));
+	s = vmalloc(umem.count * sizeof(struct geoip_subnet));
 	if (s == NULL) {
 		ret = -ENOMEM;
 		goto free_p;
 	}
 	if (copy_from_user(s, (const void __user *)(unsigned long)umem.subnets,
-	    p->count * sizeof(struct geoip_subnet)) != 0) {
+	    umem.count * sizeof(struct geoip_subnet)) != 0) {
 		ret = -EFAULT;
 		goto free_s;
 	}
 
+	p->max     = umem.count - 1;	/* last valid index in ->subnets[] */
+	p->cc      = umem.cc;
 	p->subnets = s;
 	atomic_set(&p->ref, 1);
 	INIT_LIST_HEAD(&p->list);
@@ -163,7 +165,7 @@ xt_geoip_mt(const struct sk_buff *skb, struct xt_action_param *par)
 			continue;
 		}
 
-		if (geoip_bsearch(node->subnets, ip, 0, node->count)) {
+		if (geoip_bsearch(node->subnets, ip, 0, node->max)) {
 			rcu_read_unlock();
 			return !(info->flags & XT_GEOIP_INV);
 		}
-- 
1.6.3.3

Re: [PATCH xt-addons] xt_geoip: fix possible out-of-bounds access

[Jan Engelhardt]

On Tuesday 2010-06-01 10:51, Florian Westphal wrote:

>It is possible for geoip_bsearch() to pick mid == sizeof(subnets).
>
>Consider a set with a single entry and a "address to test"
>higher than the range:
>
>1st call: lo = 0, hi = 1 -> mid will be 0
>2nd call: lo = 1, hi = 1 -> mid will be 1
>
>On the 2nd call, we'll examine random data.

Isn't this simpler?

diff --git a/extensions/xt_geoip.c b/extensions/xt_geoip.c
index 4c6b29f..44e489d 100644
--- a/extensions/xt_geoip.c
+++ b/extensions/xt_geoip.c
@@ -126,13 +126,13 @@ static bool geoip_bsearch(const struct geoip_subnet *range,
 {
 	int mid;
 
-	if (hi < lo)
+	if (hi <= lo)
 		return false;
 	mid = (lo + hi) / 2;
 	if (range[mid].begin <= addr && addr <= range[mid].end)
 		return true;
 	if (range[mid].begin > addr)
-		return geoip_bsearch(range, addr, lo, mid - 1);
+		return geoip_bsearch(range, addr, lo, mid);
 	else if (range[mid].end < addr)
 		return geoip_bsearch(range, addr, mid + 1, hi);
 


Seems to work on paper.

bsearch(lo=0, hi=1)
	inspects mid=0
	bsearch(lo=0, hi=0) stops
	bsearch(lo=1, hi=1) stops

bsearch(lo=0, hi=2)
	inspects mid=1
	bsearch(lo=0, hi=1) as above
	bsearch(lo=2, hi=2) stops

bsearch(lo=0, hi=3)
	inspects mid=1
	bsearch(lo=0, hi=1) as above
	bsearch(lo=2, hi=3)
		inspects mid=2
		bsearch(lo=2, hi=2) stops
		bsearch(lo=3, hi=3) stops

bsearch(lo=0, hi=4)
	inspects mid=2
	bsearch(lo=0, hi=2) as above
	bsearch(lo=3, hi=4)
		inspects mid=3
		bsearch(lo=3, hi=3) stops
		bsearch(lo=4, hi=4) stops

Re: [PATCH xt-addons] xt_geoip: fix possible out-of-bounds access

[Florian Westphal]

Jan Engelhardt <jengelh@medozas.de> wrote:
> On Tuesday 2010-06-01 10:51, Florian Westphal wrote:
> 
> >It is possible for geoip_bsearch() to pick mid == sizeof(subnets).
> >
> >Consider a set with a single entry and a "address to test"
> >higher than the range:
> >
> >1st call: lo = 0, hi = 1 -> mid will be 0
> >2nd call: lo = 1, hi = 1 -> mid will be 1
> >
> >On the 2nd call, we'll examine random data.
> 
> Isn't this simpler?

Guess that is a matter of taste :-)
To me, lo and hi are indexes into range[] and thus should not
exceed sizeof(range). This is what my patch fixes.

> diff --git a/extensions/xt_geoip.c b/extensions/xt_geoip.c
> index 4c6b29f..44e489d 100644
> --- a/extensions/xt_geoip.c
> +++ b/extensions/xt_geoip.c
> @@ -126,13 +126,13 @@ static bool geoip_bsearch(const struct geoip_subnet *range,
>  {
>  	int mid;
>  
> -	if (hi < lo)
> +	if (hi <= lo)
>  		return false;
>  	mid = (lo + hi) / 2;
>  	if (range[mid].begin <= addr && addr <= range[mid].end)
>  		return true;
>  	if (range[mid].begin > addr)
> -		return geoip_bsearch(range, addr, lo, mid - 1);
> +		return geoip_bsearch(range, addr, lo, mid);
>  	else if (range[mid].end < addr)
>  		return geoip_bsearch(range, addr, mid + 1, hi);
>  
> Seems to work on paper.

Yes, this works as well.

I do not have a strong preference on how this is fixed; if you
consider your patch to be the better choice then please, by all means,
apply it :-)

Thanks,
Florian

Re: [PATCH xt-addons] xt_geoip: fix possible out-of-bounds access

[Jan Engelhardt]

On Sunday 2010-06-13 10:38, Florian Westphal wrote:
>> diff --git a/extensions/xt_geoip.c b/extensions/xt_geoip.c
>> index 4c6b29f..44e489d 100644
>> --- a/extensions/xt_geoip.c
>> +++ b/extensions/xt_geoip.c
>> @@ -126,13 +126,13 @@ static bool geoip_bsearch(const struct geoip_subnet *range,
>>  {
>>  	int mid;
>>  
>> -	if (hi < lo)
>> +	if (hi <= lo)
>>  		return false;
>>  	mid = (lo + hi) / 2;
>>  	if (range[mid].begin <= addr && addr <= range[mid].end)
>>  		return true;
>>  	if (range[mid].begin > addr)
>> -		return geoip_bsearch(range, addr, lo, mid - 1);
>> +		return geoip_bsearch(range, addr, lo, mid);
>>  	else if (range[mid].end < addr)
>>  		return geoip_bsearch(range, addr, mid + 1, hi);
>>  
>> Seems to work on paper.
>
>Yes, this works as well.
>
>I do not have a strong preference on how this is fixed; if you
>consider your patch to be the better choice then please, by all means,
>apply it :-)

The initial call is
	geoip_bsearch(x, ip, 0, count);
which already shows that the original intent was to make hi
the exclusive upper barrier.