From: Jeff King <peff@peff.net>
Date: Thu, 25 Sep 2025 02:50:40 GMT
Subject: Re: [PATCH v2 2/4] string-list: replace negative index encoding with "exact_match" parameter
Message-ID: <20250925025040.GB3202669@coredump.intra.peff.net>
In-Reply-To: <xmqqwm5om1gy.fsf@gitster.g>

On Wed, Sep 24, 2025 at 06:20:13AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > I agree that size_t is much more than one needs for counting most
> > things. But the problem is that "int" is much too small, if you are
> > worried about malicious input causing integer overflows that could cause
> > memory access errors.
> 
> Well, a malicious input can cause overflow/wraparound size_t while
> parsing, so I do not think that is really an argument.
> 
> The code need to be protected against such overflows either way.

Yes, but it's much harder to wrap a size_t, especially if the code is
allocating as it goes (e.g., a loop expanding an array). Because if
expanding your allocation from "n" to "n+k" items will overflow, then
that implies the current allocation is within "k" items of filling up
the entire memory space.

In many cases "k" is 1, or a small-ish number (like the size of a
struct). In cases where the size is computed purely from untrusted
input, we do need overflow checks (and have added them over the years).
We do those checks in the size_t space, since that's how we count
allocated bytes, even if the thing we are storing is not 1 byte per
item.

If a data structure uses a smaller type (like "int") to do book-keeping
for its allocation, it risks the case where the smaller type wraps, but
is still valid as a size_t. For a signed type and a small "k" this is
often OK (if you wrap 2^31-1 around to -2^31, that ends up as an
implausibly large size_t and the allocation will fail). But there are
cases where you can wrap straight back around to "0", underallocate, and
have an unexpectedly small allocation.

I don't _think_ we have any cases of those anymore, but it's hard to
audit for. And IMHO easier to reason about if we use size_t for
book-keeping.

But if we use size_t inside string_list, say, and you do this:

   for (int i = 0; i < list.nr; i++)
	printf("got: %s", list->items[i].string);

Now we have another problem. The string list can store more than 2^31
items (even if we do not expect it to). And at some point you start
looking at list->items[-2147483648]. It's at least an out-of-bounds
read, rather than a write, but it's still rather ugly (and a clever
attacker can often stuff buffers to convince it to read whatever values
they want).

If the iterator is a size_t, then overflow in that loop is impossible
(because it implies we've allocated the entire address space). And ditto
if it is a signed 64-bit value (which would implies we've allocated half
of the entire address space).

So yes, I'd agree we need to protect against overflows, and that's what
I'm advocating for. But I think consistently using integer types that
are sized along with our memory is an important part of our strategy
there.

-Peff