linux-kernel - Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <200911122336.11033.rusty@rustcorp.com.au>
Date:	Thu, 12 Nov 2009 23:36:10 +1030
From:	Rusty Russell <rusty@...tcorp.com.au>
To:	André Goddard Rosa <andre.goddard@...il.com>
Cc:	tabbott@...lice.com, alan-jenkins@...fmail.co.uk,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v4 2/2] bsearch: prevent overflow when computing middle comparison element

On Wed, 11 Nov 2009 01:30:25 am André Goddard Rosa wrote:
> It's really difficult to occur in practice because the sum of the lower
> and higher limits must overflow an int variable, but it can occur when
> working with large arrays. We'd better safe than sorry by avoiding this
> overflow situation when computing the middle element for comparison.

I applied all these, after testing.  In future would have been nice for you
to have posted a test patch so I didn't have make my own...

Thanks,
Rusty.

diff --git a/lib/bsearch.c b/lib/bsearch.c
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -51,3 +51,50 @@ void *bsearch(const void *key, const voi
 	return NULL;
 }
 EXPORT_SYMBOL(bsearch);
+
+#if 1
+static int test_cmp(const void *_key, const void *_elt)
+{
+	int key = *(int *)_key, elt = *(int *)_elt;
+
+	if (key < elt)
+		return -1;
+	else if (key > elt)
+		return 1;
+	return 0;
+}
+
+static int test_bsearch(void)
+{
+	const int arr[] = { INT_MIN, 0, 1, 2, 3, 4, 5, 6, INT_MAX };
+	unsigned int start, num, i, total = 0;
+	int key;
+
+	for (start = 0; start < ARRAY_SIZE(arr); start++) {
+		for (num = 0; num < ARRAY_SIZE(arr) - start; num++) {
+			key = 7;
+			BUG_ON(bsearch(&key, &arr[start], num, sizeof(arr[0]),
+				       test_cmp));
+			total++;
+			for (i = start; i < start+num; i++) {
+				int *ret;
+				key = arr[i];
+				ret = bsearch(&key, &arr[start], num,
+					      sizeof(arr[0]), test_cmp);
+				if (!ret) {
+					printk("Could not find %i in %u-%u"
+					       "(between %i and %i)\n",
+					       key, start, start+num,
+					       arr[start], arr[start+num]);
+				}
+				BUG_ON(!ret);
+				BUG_ON(*ret != key);
+				total++;
+			}
+		}
+	}
+	printk("Tested %u bsearches\n", total);
+	return 0;
+}
+module_init(test_bsearch);
+#endif
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/