git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 03/11] reftable/basics: fix OOB read on binary search of empty range

From
Patrick Steinhardt <ps@pks.im>
Date
Jun 24, 2026, 08:23 UTC
Message-ID
<20260624-pks-reftable-hardening-v1-3-66e4ce87c6b9@pks.im>
In-Reply-To
<20260624-pks-reftable-hardening-v1-0-66e4ce87c6b9@pks.im>

`binsearch()` performs a binary search over a range of `sz` elements by repeatedly calling the comparison function with indices into that range. When the range is empty though, there is no valid index to call the comparison function with. We still end up executing the comparison function though with an index of 0, which of course will cause an out-of-bounds read.

Return early when the range is empty.
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/basics.c                |  3 +++
 t/unit-tests/u-reftable-basics.c | 11 +++++++++++
 2 files changed, 14 insertions(+)
diff --git a/reftable/basics.c b/reftable/basics.c
index e969927b61..f0442a46cf 100644
--- a/reftable/basics.c
+++ b/reftable/basics.c
@@ -152,6 +152,9 @@ size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)
 	size_t lo = 0;
 	size_t hi = sz;
 
+	if (!sz)
+		return 0;
+
 	/* Invariants:
 	 *
 	 *  (hi == sz) || f(hi) == true
diff --git a/t/unit-tests/u-reftable-basics.c b/t/unit-tests/u-reftable-basics.c
index 73566ed0eb..c5d83b6714 100644
--- a/t/unit-tests/u-reftable-basics.c
+++ b/t/unit-tests/u-reftable-basics.c
@@ -60,6 +60,17 @@ void test_reftable_basics__binsearch(void)
 	}
 }
 
+static int unreachable_lesseq(size_t i UNUSED, void *args UNUSED)
+{
+	cl_fail("comparison function called for empty range");
+	return 0;
+}
+
+void test_reftable_basics__binsearch_empty(void)
+{
+	cl_assert_equal_i(binsearch(0, &unreachable_lesseq, NULL), 0);
+}
+
 void test_reftable_basics__names_length(void)
 {
 	const char *a[] = { "a", "b", NULL };
-- 
2.55.0.rc1.745.g43192e7977.dirty
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 4 of 48 in “reftable: harden against corrupted tables”
  1. 00/11 reftable: harden against corrupted tablesPatrick Steinhardt, Jun 24, 2026
  2. 01/11 meson: support building fuzzers with libFuzzerPatrick Steinhardt, Jun 24, 2026
  3. 02/11 oss-fuzz: add fuzzer for parsing reftablesPatrick Steinhardt, Jun 24, 2026
  4. 03/11 reftable/basics: fix OOB read on binary search of empty rangePatrick Steinhardt, Jun 24, 2026
  5. 04/11 reftable/record: don't abort when decoding invalid ref value typePatrick Steinhardt, Jun 24, 2026
  6. 05/11 reftable/block: fix OOB write with bogus inflated log sizePatrick Steinhardt, Jun 24, 2026
  7. Christian CouderJun 26, 2026
  8. Patrick SteinhardtJun 29, 2026
  9. 06/11 reftable/block: fix OOB read with bogus block sizePatrick Steinhardt, Jun 24, 2026
  10. 07/11 reftable/block: fix OOB read with bogus restart countPatrick Steinhardt, Jun 24, 2026
  11. 08/11 reftable/block: fix use of uninitialized memory when binsearch failsPatrick Steinhardt, Jun 24, 2026
  12. 09/11 reftable/block: fix OOB read with bogus restart offsetPatrick Steinhardt, Jun 24, 2026
  13. 10/11 reftable/table: fix NULL pointer access when seeking to bogus offsetsPatrick Steinhardt, Jun 24, 2026
  14. 11/11 reftable/table: fix OOB read on truncated tablePatrick Steinhardt, Jun 24, 2026
  15. 00/12 reftable: harden against corrupted tablesPatrick Steinhardt, Jun 29, 2026
  16. 01/12 meson: support building fuzzers with libFuzzerPatrick Steinhardt, Jun 29, 2026
  17. 02/12 oss-fuzz: add fuzzer for parsing reftablesPatrick Steinhardt, Jun 29, 2026
  18. 03/12 reftable/basics: fix OOB read on binary search of empty rangePatrick Steinhardt, Jun 29, 2026
  19. 04/12 reftable/record: don't abort when decoding invalid ref value typePatrick Steinhardt, Jun 29, 2026
  20. 05/12 t/unit-tests: introduce test helper to write reftable blocksPatrick Steinhardt, Jun 29, 2026
  21. Junio C HamanoJun 30, 2026
  22. Christian CouderJul 2, 2026
  23. Junio C HamanoJul 3, 2026
  24. 06/12 reftable/block: fix OOB write with bogus inflated log sizePatrick Steinhardt, Jun 29, 2026
  25. Toon ClaesJul 3, 2026
  26. Patrick SteinhardtJul 3, 2026
  27. 07/12 reftable/block: fix OOB read with bogus block sizePatrick Steinhardt, Jun 29, 2026
  28. Toon ClaesJul 3, 2026
  29. Patrick SteinhardtJul 3, 2026
  30. 08/12 reftable/block: fix OOB read with bogus restart countPatrick Steinhardt, Jun 29, 2026
  31. 09/12 reftable/block: fix use of uninitialized memory when binsearch failsPatrick Steinhardt, Jun 29, 2026
  32. 10/12 reftable/block: fix OOB read with bogus restart offsetPatrick Steinhardt, Jun 29, 2026
  33. 11/12 reftable/table: fix NULL pointer access when seeking to bogus offsetsPatrick Steinhardt, Jun 29, 2026
  34. 12/12 reftable/table: fix OOB read on truncated tablePatrick Steinhardt, Jun 29, 2026
  35. 00/12 reftable: harden against corrupted tablesPatrick Steinhardt, Jul 3, 2026
  36. 01/12 meson: support building fuzzers with libFuzzerPatrick Steinhardt, Jul 3, 2026
  37. 02/12 oss-fuzz: add fuzzer for parsing reftablesPatrick Steinhardt, Jul 3, 2026
  38. 03/12 reftable/basics: fix OOB read on binary search of empty rangePatrick Steinhardt, Jul 3, 2026
  39. 04/12 reftable/record: don't abort when decoding invalid ref value typePatrick Steinhardt, Jul 3, 2026
  40. 05/12 t/unit-tests: introduce test helper to write reftable blocksPatrick Steinhardt, Jul 3, 2026
  41. 06/12 reftable/block: fix OOB write with bogus inflated log sizePatrick Steinhardt, Jul 3, 2026
  42. 07/12 reftable/block: fix OOB read with bogus block sizePatrick Steinhardt, Jul 3, 2026
  43. 08/12 reftable/block: fix OOB read with bogus restart countPatrick Steinhardt, Jul 3, 2026
  44. 09/12 reftable/block: fix use of uninitialized memory when binsearch failsPatrick Steinhardt, Jul 3, 2026
  45. 10/12 reftable/block: fix OOB read with bogus restart offsetPatrick Steinhardt, Jul 3, 2026
  46. 11/12 reftable/table: fix NULL pointer access when seeking to bogus offsetsPatrick Steinhardt, Jul 3, 2026
  47. 12/12 reftable/table: fix OOB read on truncated tablePatrick Steinhardt, Jul 3, 2026
  48. Toon ClaesJul 8, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.