Bug#776671: glibc: integer overflow in bsearch(3)

[Jakub Wilk <jwilk@debian.org>]

Source: glibc
Version: 2.19-13
Tags: patch

The way bsearch() computes indices is subject to integer overflow. This 
should be only a problem on 32-bit systems, where it's possible to 
allocate more than SIZE_MAX/2 bytes of memory.

The attached patch should fix this bug, but it was only lightly tested.

I also attached test case, which currently loops forever on 32-bit 
systems. (Beware that it allocates 3GB of memory. Don't run it on a 
system that is short of RAM!)

--
Jakub Wilk

diff --git a/bits/stdlib-bsearch.h b/bits/stdlib-bsearch.h
--- a/bits/stdlib-bsearch.h
+++ b/bits/stdlib-bsearch.h
@@ -28,7 +28,7 @@
   __u = __nmemb;
   while (__l < __u)
     {
-      __idx = (__l + __u) / 2;
+      __idx = __l + (__u - __l) / 2;
       __p = (void *) (((const char *) __base) + (__idx * __size));
       __comparison = (*__compar) (__key, __p);
       if (__comparison < 0)

#include <assert.h>
#include <stdlib.h>

int cmp(const void *this, const void *other)
{
	return 
		*((const char *)this) -
		*((const char *)other);
}

int main(int argc, char **argv)
{
	char key = 42;
	size_t size = 3UL << 30;
	char* base = calloc(1, size);
	base[size - 1] = key + 1;
	base[size - 2] = key;
	void *found = bsearch(&key, base, size, 1, cmp);
	assert(found == base + size - 2);
	return 0;
}