[v2,07/11] ls-refs: ignore very long ref-prefix counts

Because each "ref-prefix" capability from the client comes in its own
pkt-line, there's no limit to the number of them that a misbehaving
client may send. We read them all into a strvec, which means the client
can waste arbitrary amounts of our memory by just sending us "ref-prefix
foo" over and over.

One possible solution is to just drop the connection when the limit is
reached. If we set it high enough, then only misbehaving or malicious
clients would hit it. But "high enough" is vague, and it's unfriendly if
we guess wrong and a legitimate client hits this.

But we can do better. Since supporting the ref-prefix capability is
optional anyway, the client has to further cull the response based on
their own patterns. So we can simply ignore the patterns once we cross a
certain threshold. Note that we have to ignore _all_ patterns, not just
the ones past our limit (since otherwise we'd send too little data).

The limit here is fairly arbitrary, and probably much higher than anyone
would need in practice. It might be worth limiting it further, if only
because we check it linearly (so with "m" local refs and "n" patterns,
we do "m * n" string comparisons). But if we care about optimizing this,
an even better solution may be a more advanced data structure anyway.

I didn't bother making the limit configurable, since it's so high and
since Git should behave correctly in either case. It wouldn't be too
hard to do, but it makes both the code and documentation more complex.

Signed-off-by: Jeff King <peff@peff.net>
---
 ls-refs.c            | 20 ++++++++++++++++++--
 t/t5701-git-serve.sh | 31 +++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 2 deletions(-)

On Tue, Sep 14, 2021 at 07:51:35PM -0400, Jeff King wrote:
> @@ -156,15 +162,25 @@ int ls_refs(struct repository *r, struct packet_reader *request)
>  			data.peel = 1;
>  		else if (!strcmp("symrefs", arg))
>  			data.symrefs = 1;
> -		else if (skip_prefix(arg, "ref-prefix ", &out))
> -			strvec_push(&data.prefixes, out);
> +		else if (skip_prefix(arg, "ref-prefix ", &out)) {
> +			if (data.prefixes.nr < TOO_MANY_PREFIXES)
> +				strvec_push(&data.prefixes, out);
> +		}
>  		else if (!strcmp("unborn", arg))
>  			data.unborn = allow_unborn;
>  	}
>
>  	if (request->status != PACKET_READ_FLUSH)
>  		die(_("expected flush after ls-refs arguments"));
>
> +	/*
> +	 * If we saw too many prefixes, we must avoid using them at all; as
> +	 * soon as we have any prefix, they are meant to form a comprehensive
> +	 * list.
> +	 */
> +	if (data.prefixes.nr >= TOO_MANY_PREFIXES)
> +		strvec_clear(&data.prefixes);
> +

Great, I find this version even better than what I suggested where the
case where the list already has too many prefixes `continue`s through
the loop before calling strvec_add().

Just noting aloud, the `>` part of this conditional will never happen
(since data.prefixes.nr will be at most equal to TOO_MANY_PREFIXES, but
never larger than it).

Obviously not wrong, but I figured it'd be worth mentioning in case it
caught the attention of other reviewers.

Thanks,
Taylor

On Tue, Sep 14, 2021 at 7:51 PM Jeff King <peff@peff.net> wrote:
> diff --git a/t/t5701-git-serve.sh b/t/t5701-git-serve.sh
> @@ -158,6 +158,37 @@ test_expect_success 'refs/heads prefix' '
> +test_expect_success 'ignore very large set of prefixes' '
> +       # generate a large number of ref-prefixes that we expect
> +       # to match nothing; the value here exceeds TOO_MANY_PREFIXES
> +       # from ls-refs.c.
> +       {
> +               echo command=ls-refs &&
> +               echo object-format=$(test_oid algo)
> +               echo 0001 &&
> +               perl -le "print \"ref-prefix refs/heads/\$_\" for (1..65536)" &&
> +               echo 0000
> +       } |
> +       test-tool pkt-line pack >in &&

Broken &&-chain in {...}.

(Granted, it doesn't matter in this case since the exit code gets lost
down the pipe, but better to be consistent about it.)

On Wed, Sep 15, 2021 at 12:16:04AM -0400, Taylor Blau wrote:

> > +	/*
> > +	 * If we saw too many prefixes, we must avoid using them at all; as
> > +	 * soon as we have any prefix, they are meant to form a comprehensive
> > +	 * list.
> > +	 */
> > +	if (data.prefixes.nr >= TOO_MANY_PREFIXES)
> > +		strvec_clear(&data.prefixes);
> > +
> 
> Great, I find this version even better than what I suggested where the
> case where the list already has too many prefixes `continue`s through
> the loop before calling strvec_add().
> 
> Just noting aloud, the `>` part of this conditional will never happen
> (since data.prefixes.nr will be at most equal to TOO_MANY_PREFIXES, but
> never larger than it).
> 
> Obviously not wrong, but I figured it'd be worth mentioning in case it
> caught the attention of other reviewers.

Yeah, your analysis is right. Long ago I read some advice (I think from
K&R, either the C book or a related article) that suggested always using
bounding checks like this rather than equality, because they do the
right thing even if the variable ends up with a surprising value.

I can certainly see an argument against it (like that if you're so
worried about it, maybe you ought to detect it and figure out who is
setting the variable to be unexpectedly high). But it seems like a
reasonable defensive measure to me (against an off-by-one mis-analysis,
or against the earlier code changing in the future).

-Peff

On Wed, Sep 15, 2021 at 01:00:01AM -0400, Eric Sunshine wrote:

> On Tue, Sep 14, 2021 at 7:51 PM Jeff King <peff@peff.net> wrote:
> > diff --git a/t/t5701-git-serve.sh b/t/t5701-git-serve.sh
> > @@ -158,6 +158,37 @@ test_expect_success 'refs/heads prefix' '
> > +test_expect_success 'ignore very large set of prefixes' '
> > +       # generate a large number of ref-prefixes that we expect
> > +       # to match nothing; the value here exceeds TOO_MANY_PREFIXES
> > +       # from ls-refs.c.
> > +       {
> > +               echo command=ls-refs &&
> > +               echo object-format=$(test_oid algo)
> > +               echo 0001 &&
> > +               perl -le "print \"ref-prefix refs/heads/\$_\" for (1..65536)" &&
> > +               echo 0000
> > +       } |
> > +       test-tool pkt-line pack >in &&
> 
> Broken &&-chain in {...}.

Thanks, will fix.

> (Granted, it doesn't matter in this case since the exit code gets lost
> down the pipe, but better to be consistent about it.)

Yep. I think what happened is that I started to convert this to a
here-doc to match the nearby tests, but then realized that expanding the
multi-line bit was weird (even more so when it was a shell loop with a
pipe, before I switched it to perl).

-Peff