[PATCH 0/3] wildmatch: fix exponential behavior

[PATCH 0/3] wildmatch: fix exponential behavior

[Phillip Wood]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

The wildmatch implementation in git suffers from exponential behavior as
described in [1] where the time taken for a failing match is exponential
in the number of wildcards it contains. The original implementation
imported from rsync is immune but the optimizations introduced by [2.3]
failed to prevent unnecessary backtracking when handling '*' and '/**/'.

This bug was were discussed on the security list and the conclusion was
that it only affects operations that are already potential DoS vectors.

In the long term it would be nice to get rid of the recursion in the
wildmatch() code but the patches here focus on a minimal fix.

This series is based on maint. Unfortunately it conflicts with
my/wildmatch-cleanups when merged with seen. There are sematic
conflicts with the removal of dowild() in  e303cf8092 (wildmatch:
more cleanups after killing uchar, 2023-02-26) as well as textual
conflicts around the change of uchar->char.

[1] https://research.swtch.com/glob
[2] 6f1a31f0aa (wildmatch: advance faster in <asterisk> + <literal> patterns, 2013-01-01)
[3] 46983441ae (wildmatch: make a special case for "*/" with FNM_PATHNAME, 2013-01-01)

Published-As: https://github.com/phillipwood/git/releases/tag/wildmatch-fixes%2Fv1
View-Changes-At: https://github.com/phillipwood/git/compare/73876f486...a74ab7138
Fetch-It-Via: git fetch https://github.com/phillipwood/git wildmatch-fixes/v1

Phillip Wood (3):
  wildmatch: fix exponential behavior
  wildmatch: avoid undefined behavior
  wildmatch: hide internal return values

 t/t3070-wildmatch.sh |  9 +++++++++
 wildmatch.c          | 23 ++++++++++++++++-------
 wildmatch.h          |  2 --
 3 files changed, 25 insertions(+), 9 deletions(-)

-- 
2.39.2

[PATCH 1/3] wildmatch: fix exponential behavior

[Phillip Wood]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

When dowild() cannot match a '*' or '/**/' wildcard then it must return
WM_ABORT_TO_STARSTAR or WM_ABORT_ALL respectively. Failure to observe
this results in unnecessary backtracking and the time taken for a failed
match increases exponentially with the number of wildcards in the
pattern [1]. Unfortunately in some instances dowild() returns WM_NOMATCH
for a failed match resulting in long match times for patterns containing
multiple wildcards as can be seen in the following benchmark.
(Note that the timings in the Benchmark 1 are really measuring the time
to execute test-tool rather than the time to match the pattern)

Benchmark 1: t/helper/test-tool wildmatch wildmatch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab "*a"
  Time (mean ± σ):      22.8 ms ±   1.7 ms    [User: 12.1 ms, System: 10.6 ms]
  Range (min … max):    19.4 ms …  26.9 ms    113 runs

  Warning: Ignoring non-zero exit code.

Benchmark 2: t/helper/test-tool wildmatch wildmatch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab "*a*a*a*a*a*a*a*a*a"
  Time (mean ± σ):      5.244 s ±  0.228 s    [User: 5.229 s, System: 0.010 s]
  Range (min … max):    4.969 s …  5.707 s    10 runs

  Warning: Ignoring non-zero exit code.

Summary
  't/helper/test-tool wildmatch wildmatch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab "*a"' ran
  230.37 ± 20.04 times faster than 't/helper/test-tool wildmatch wildmatch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab "*a*a*a*a*a*a*a*a*a"'

The security implications are limited as it only affects operations that
are potentially DoS vectors. For example by creating a blob containing
such a pattern a malicious user can exploit this behavior to use large
amounts of CPU time on a remote server by pushing the blob and then
creating a new clone with --filter=sparse:oid. However this filter type
is usually disabled as it is known to consume large amounts of CPU time
even without this bug.

The WM_MATCH changed in the first hunk of this patch comes from the
original implementation imported from rsync in 5230f605e1 (Import
wildmatch from rsync, 2012-10-15). Compared to the others converted here
it is fairly harmless as it only triggers at the end of the pattern and
so will only cause a single unnecessary backtrack. The others introduced
by 6f1a31f0aa (wildmatch: advance faster in <asterisk> + <literal>
patterns, 2013-01-01) and 46983441ae (wildmatch: make a special case for
"*/" with FNM_PATHNAME, 2013-01-01) are more pernicious and will cause
exponential behavior.

A new test is added to protect against future regressions.

[1] https://research.swtch.com/glob

Helped-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 t/t3070-wildmatch.sh |  9 +++++++++
 wildmatch.c          | 12 ++++++++----
 2 files changed, 17 insertions(+), 4 deletions(-)

diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
index 5d871fde96..b91a7cb712 100755
--- a/t/t3070-wildmatch.sh
+++ b/t/t3070-wildmatch.sh
@@ -431,4 +431,13 @@ match 1 1 1 1 'a' '[B-a]'
 match 0 1 0 1 'z' '[Z-y]'
 match 1 1 1 1 'Z' '[Z-y]'
 
+test_expect_success 'matching does not exhibit exponential behavior' '
+	test-tool wildmatch wildmatch \
+		aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
+		"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
+	pid=$! &&
+	sleep 2 &&
+	! kill $!
+'
+
 test_done
diff --git a/wildmatch.c b/wildmatch.c
index 7e5a7ea1ea..06861bd8bc 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -114,7 +114,7 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 				 * only if there are no more slash characters. */
 				if (!match_slash) {
 					if (strchr((char *)text, '/'))
-						return WM_NOMATCH;
+						return WM_ABORT_TO_STARSTAR;
 				}
 				return WM_MATCH;
 			} else if (!match_slash && *p == '/') {
@@ -125,7 +125,7 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 				 */
 				const char *slash = strchr((char*)text, '/');
 				if (!slash)
-					return WM_NOMATCH;
+					return WM_ABORT_ALL;
 				text = (const uchar*)slash;
 				/* the slash is consumed by the top-level for loop */
 				break;
@@ -153,8 +153,12 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 							break;
 						text++;
 					}
-					if (t_ch != p_ch)
-						return WM_NOMATCH;
+					if (t_ch != p_ch) {
+						if (match_slash)
+							return WM_ABORT_ALL;
+						else
+							return WM_ABORT_TO_STARSTAR;
+					}
 				}
 				if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
 					if (!match_slash || matched != WM_ABORT_TO_STARSTAR)
-- 
2.39.2

[PATCH] t3070: make chain lint tester happy

[Michael J Gruber]

1f2e05f0b7 ("wildmatch: fix exponential behavior", 2023-03-20)
introduced a new test with a background process. Backgrounding
necessarily gives a result of 0, so that a seemingly broken && chain is
not really broken.

Adjust t3070 slightly so that our chain list test recognizes the
construct for what it is and does not raise a false positive.

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t3070-wildmatch.sh | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
index b91a7cb712..4dd42df38c 100755
--- a/t/t3070-wildmatch.sh
+++ b/t/t3070-wildmatch.sh
@@ -432,10 +432,12 @@ match 0 1 0 1 'z' '[Z-y]'
 match 1 1 1 1 'Z' '[Z-y]'
 
 test_expect_success 'matching does not exhibit exponential behavior' '
-	test-tool wildmatch wildmatch \
-		aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
-		"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
-	pid=$! &&
+	{
+		test-tool wildmatch wildmatch \
+			aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
+			"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
+		pid=$!
+	} &&
 	sleep 2 &&
 	! kill $!
 '
-- 
2.40.0.355.gd681773fb6

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Fri, Mar 24, 2023 at 11:17:11PM +0100, Michael J Gruber wrote:

> 1f2e05f0b7 ("wildmatch: fix exponential behavior", 2023-03-20)
> introduced a new test with a background process. Backgrounding
> necessarily gives a result of 0, so that a seemingly broken && chain is
> not really broken.
> 
> Adjust t3070 slightly so that our chain list test recognizes the
> construct for what it is and does not raise a false positive.

Good catch. While I agree that there's no missed exit code here, I'd say
that this is more than just a false positive. If there were any lines
above the "&", like:

  foo &&
  bar &
  pid=$! &&
  ...etc...

then we'd be losing the exit value of "foo". It's OK here because the
backgrounded command is the first line of the test, but it definitely
violates our guidelines.

Which isn't to say that your patch needs to do anything differently. I
just wondered if it meant we should be improving the chain linter, but I
think it is doing the right thing to alert us here.

> diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
> index b91a7cb712..4dd42df38c 100755
> --- a/t/t3070-wildmatch.sh
> +++ b/t/t3070-wildmatch.sh
> @@ -432,10 +432,12 @@ match 0 1 0 1 'z' '[Z-y]'
>  match 1 1 1 1 'Z' '[Z-y]'
>  
>  test_expect_success 'matching does not exhibit exponential behavior' '
> -	test-tool wildmatch wildmatch \
> -		aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
> -		"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
> -	pid=$! &&
> +	{
> +		test-tool wildmatch wildmatch \
> +			aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
> +			"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
> +		pid=$!
> +	} &&
>  	sleep 2 &&
>  	! kill $!

This looks like the right solution. I do wonder how Phillip managed to
miss it, though, since the test script complains loudly.

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Eric Sunshine]

On Sat, Mar 25, 2023 at 2:38 AM Jeff King <peff@peff.net> wrote:
> On Fri, Mar 24, 2023 at 11:17:11PM +0100, Michael J Gruber wrote:
> > 1f2e05f0b7 ("wildmatch: fix exponential behavior", 2023-03-20)
> > introduced a new test with a background process. Backgrounding
> > necessarily gives a result of 0, so that a seemingly broken && chain is
> > not really broken.
> >
> > Adjust t3070 slightly so that our chain list test recognizes the

s/list/lint/

> > construct for what it is and does not raise a false positive.
>
> Good catch. While I agree that there's no missed exit code here, I'd say
> that this is more than just a false positive. If there were any lines
> above the "&", like:
>
>   foo &&
>   bar &
>   pid=$! &&
>   ...etc...
>
> then we'd be losing the exit value of "foo". It's OK here because the
> backgrounded command is the first line of the test, but it definitely
> violates our guidelines.

This is one of a few cases chainlint recognizes specially by
suppressing the complaint about the broken &&-chain since "&" can
never fail. The fact that a broken &&-chain prior to the "&" would be
missed was considered a reasonable tradeoff rather than complaining
and asking the test author to jump through hoops just to pacify the
linter. So, there are a few known cases when a broken &&-chain is
allowed to slip through, and tightening linting to disallow those
cases would require too many churn-like changes with little or no
benefit.

> Which isn't to say that your patch needs to do anything differently. I
> just wondered if it meant we should be improving the chain linter, but I
> think it is doing the right thing to alert us here.

Now it gets confusing (for me, at least).

> > +     {
> > +             test-tool wildmatch wildmatch \
> > +                     aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
> > +                     "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
> > +             pid=$!
> > +     } &&
>
> This looks like the right solution. I do wonder how Phillip managed to
> miss it, though, since the test script complains loudly.

I am unable to reproduce any linting errors when running this script
through chainlint, which is why I was more than a little confused by
this patch when I read it, and I was just about to ask for more
information, such as the actual error message.

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 02:54:45AM -0400, Eric Sunshine wrote:

> > > +     {
> > > +             test-tool wildmatch wildmatch \
> > > +                     aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
> > > +                     "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
> > > +             pid=$!
> > > +     } &&
> >
> > This looks like the right solution. I do wonder how Phillip managed to
> > miss it, though, since the test script complains loudly.
> 
> I am unable to reproduce any linting errors when running this script
> through chainlint, which is why I was more than a little confused by
> this patch when I read it, and I was just about to ask for more
> information, such as the actual error message.

It's not your chain-lint script, but rather the builtin one that sticks
"(exit 117) &&" in front of the snippet and evals it. So it creates the
exact "foo && bar &" situation by prepending a line to the snippet.

So running (on seen, which has 1f2e05f0b79):

  ./t3070-wildmatch.sh

gives me:

  ok 1890 - ipathmatch (via ls-files): match '[Z-y]' 'Z'
  error: bug in the test script: broken &&-chain or run-away HERE-DOC:
  	test-tool wildmatch wildmatch \
  		aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
  		"*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
  	pid=$! &&
  	sleep 2 &&
  	! kill $!

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 03:58:32AM -0400, Jeff King wrote:

> > > This looks like the right solution. I do wonder how Phillip managed to
> > > miss it, though, since the test script complains loudly.
> > 
> > I am unable to reproduce any linting errors when running this script
> > through chainlint, which is why I was more than a little confused by
> > this patch when I read it, and I was just about to ask for more
> > information, such as the actual error message.
> 
> It's not your chain-lint script, but rather the builtin one that sticks
> "(exit 117) &&" in front of the snippet and evals it. So it creates the
> exact "foo && bar &" situation by prepending a line to the snippet.

And btw, I think that is the answer to "how did Phillip not notice it?".
When running "make test" these days, we rely on chainlint.pl to detect
any problems, and then set GIT_TEST_CHAIN_LINT=0 so that the scripts do
not invoke it again. But that variable also suppresses the internal
linter, and thus "make test" passes, but running the script individually
does not.

It does seem like a recipe for confusion if the two linters are not in
agreement. I think we might want to either:

  1. Say that the internal linter still has value, and tweak the
     suppression so it only turns off the extra per-script run of
     chainlint.pl, and not the internal one (which is cheap-ish to run).

  2. Say that the internal linter does not have value, and we should
     rely on chainlint.pl. In which case we might as well ditch the
     internal one completely.

     I'm OK with this direction, if we're comfortable that there are no
     real problems that would be caught by the internal one but not the
     script.

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Eric Sunshine]

On Sat, Mar 25, 2023 at 4:04 AM Jeff King <peff@peff.net> wrote:
> On Sat, Mar 25, 2023 at 03:58:32AM -0400, Jeff King wrote:
> > It's not your chain-lint script, but rather the builtin one that sticks
> > "(exit 117) &&" in front of the snippet and evals it. So it creates the
> > exact "foo && bar &" situation by prepending a line to the snippet.
>
> And btw, I think that is the answer to "how did Phillip not notice it?".
> When running "make test" these days, we rely on chainlint.pl to detect
> any problems, and then set GIT_TEST_CHAIN_LINT=0 so that the scripts do
> not invoke it again. But that variable also suppresses the internal
> linter, and thus "make test" passes, but running the script individually
> does not.

Indeed, that would explain it.

> It does seem like a recipe for confusion if the two linters are not in
> agreement. I think we might want to either:
>
>   1. Say that the internal linter still has value, and tweak the
>      suppression so it only turns off the extra per-script run of
>      chainlint.pl, and not the internal one (which is cheap-ish to run).

This is appealing since the internal linter is nearly zero-cost,
though doing this would not fully address the "recipe for confusion"
since the two linters would still not be in agreement. This approach
does have the benefit that it gives at least _some_ protection (minus
caveats mentioned below) on platforms where it may be common to
disable chainlint.pl due to slowness, such as Windows.

>   2. Say that the internal linter does not have value, and we should
>      rely on chainlint.pl. In which case we might as well ditch the
>      internal one completely.

The value of the internal linter is fairly limited in that it only
checks top-level &&-chain; it doesn't check inside subprocesses,
blocks, or any compound statement (case/esac, if/fi, while/done,
etc.).

>      I'm OK with this direction, if we're comfortable that there are no
>      real problems that would be caught by the internal one but not the
>      script.

I retained the internal linter in place "just in case" (i.e. in the
event the script missed something legitimate), but I don't feel
strongly about it.

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 04:18:54AM -0400, Eric Sunshine wrote:

> >   1. Say that the internal linter still has value, and tweak the
> >      suppression so it only turns off the extra per-script run of
> >      chainlint.pl, and not the internal one (which is cheap-ish to run).
> 
> This is appealing since the internal linter is nearly zero-cost,
> though doing this would not fully address the "recipe for confusion"
> since the two linters would still not be in agreement. This approach
> does have the benefit that it gives at least _some_ protection (minus
> caveats mentioned below) on platforms where it may be common to
> disable chainlint.pl due to slowness, such as Windows.

I think it's OK if they're not in agreement, as long as both are run.
Then the set of problems you need to fix is the union of their outputs.
That's conservative, but everybody gets the same answer.

The bigger confusion to me is when "make test" and "./t1234-foo.sh" do
not agree in their output, which is what happened here. Some people say
"everything is good" and some say "no, it is broken", depending on how
they ran it.

> >   2. Say that the internal linter does not have value, and we should
> >      rely on chainlint.pl. In which case we might as well ditch the
> >      internal one completely.
> 
> The value of the internal linter is fairly limited in that it only
> checks top-level &&-chain; it doesn't check inside subprocesses,
> blocks, or any compound statement (case/esac, if/fi, while/done,
> etc.).

Right, the chainlint.pl one is much more thorough. I just wondered if
there were any cases we were worried about it missing, that the internal
one catches. We found one in this thread, but as discussed, it is not a
problem (presumably chainlint.pl catches a "real" case where an
earlier line is hidden by the "&", but I wouldn't mind seeing it
complain here as a matter of style/future-proofing).

> I retained the internal linter in place "just in case" (i.e. in the
> event the script missed something legitimate), but I don't feel
> strongly about it.

Certainly the output from chainlint.pl is much nicer, too. :) I think
I'd be comfortable dropping the internal one at this point in terms of
quality. The bigger question to me is whether there are setups where it
isn't run (you mentioned Windows, but I'd have thought the
single-process invocation made things nice and fast there).

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 04:41:08AM -0400, Jeff King wrote:

> Right, the chainlint.pl one is much more thorough. I just wondered if
> there were any cases we were worried about it missing, that the internal
> one catches. We found one in this thread, but as discussed, it is not a
> problem (presumably chainlint.pl catches a "real" case where an
> earlier line is hidden by the "&", but I wouldn't mind seeing it
> complain here as a matter of style/future-proofing).

Hmm, actually chainlint.pl does not seem to catch this:

-- >8 --
test_expect_success 'ok, first line cannot break &&-chain' '
	true &
	pid=$!
'

test_expect_success 'not ok, failure is lost' '
	false &&
	true &
	pid=$!
'
-- >8 --

It's a little funny, because we actually background the whole "false &&
true" chain. So if you did "wait $pid" at the end, you would see the
failure. But the test in this thread doesn't actually do that (it
depends on kill after 2 seconds not finding the pid). Plus in general
this seems like an accident that we should be flagging.

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Eric Sunshine]

On Sat, Mar 25, 2023 at 4:51 AM Jeff King <peff@peff.net> wrote:
> On Sat, Mar 25, 2023 at 04:41:08AM -0400, Jeff King wrote:
> > Right, the chainlint.pl one is much more thorough. I just wondered if
> > there were any cases we were worried about it missing, that the internal
> > one catches. We found one in this thread, but as discussed, it is not a
> > problem (presumably chainlint.pl catches a "real" case where an
> > earlier line is hidden by the "&", but I wouldn't mind seeing it
> > complain here as a matter of style/future-proofing).
>
> Hmm, actually chainlint.pl does not seem to catch this:
>
> -- >8 --
> test_expect_success 'ok, first line cannot break &&-chain' '
>         true &
>         pid=$!
> '
>
> test_expect_success 'not ok, failure is lost' '
>         false &&
>         true &
>         pid=$!
> '
> -- >8 --

Right, that's one of the "special cases" I mentioned earlier; an
intentional simplification of implementation to keep the complexity
level down. Although the linter is genuinely parsing the shell code,
it doesn't really understand or check shell semantics, and is just
using simple heuristics to detect the common types of &&-breakage and
missing `return 1`.

This particular simplification is that if it encounters one of the
special cases in which some construct (such as "&") should not be
considered as a break in the &&-chain, it clears all "??AMP??" flags
which come before that point in the current parse context.

More specifically, it's not even building a parse tree; it's just
trying to detect problems on-the-fly as it parses, so when it finds
something like "&" which is _not_ a breakage, it can't easily go back
and recheck which earlier "??AMP??" annotations are still needed. So,
it just clears the earlier ones unconditionally with the hope of not
letting too many false-negatives through. It would certainly be
possible to make it do a better job of detection, but doing so would
complicate the code quite a bit. (Eventually, I think it would be best
to build a parse tree, which would make it easier to incorporate other
linting ideas I have in mind, but I don't have any immediate plans to
do so.)

> It's a little funny, because we actually background the whole "false &&
> true" chain. So if you did "wait $pid" at the end, you would see the
> failure. But the test in this thread doesn't actually do that (it
> depends on kill after 2 seconds not finding the pid). Plus in general
> this seems like an accident that we should be flagging.

As above, it was a judgement call regarding linter implementation
complexity versus letting a few potential breakages slip through
undetected. As it stands, we get a pretty big pay off detecting >99.9%
of real-world breakage without the additional complexity. (That is not
an argument against improving its accuracy in the future, but rather
an explanation of the current state of the linter.)

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 05:09:15AM -0400, Eric Sunshine wrote:

> > Hmm, actually chainlint.pl does not seem to catch this:
> >
> > -- >8 --
> > test_expect_success 'ok, first line cannot break &&-chain' '
> >         true &
> >         pid=$!
> > '
> >
> > test_expect_success 'not ok, failure is lost' '
> >         false &&
> >         true &
> >         pid=$!
> > '
> > -- >8 --
> 
> Right, that's one of the "special cases" I mentioned earlier; an
> intentional simplification of implementation to keep the complexity
> level down. Although the linter is genuinely parsing the shell code,
> it doesn't really understand or check shell semantics, and is just
> using simple heuristics to detect the common types of &&-breakage and
> missing `return 1`.

Ah, OK. I thought the special case was ignoring the first one (which you
probably need to do to make "{ cmd & pid=$!; }" work inside braces), not
the second.

> This particular simplification is that if it encounters one of the
> special cases in which some construct (such as "&") should not be
> considered as a break in the &&-chain, it clears all "??AMP??" flags
> which come before that point in the current parse context.

That makes sense, though it does mean that an easy typo ("&" for "&&")
wouldn't get caught. I don't recall this case happening a lot, though.

It does make me inclined to keep the built-in checker, just because we
know it can catch this case (at least at the top-level of the snippet).

> More specifically, it's not even building a parse tree; it's just
> trying to detect problems on-the-fly as it parses, so when it finds
> something like "&" which is _not_ a breakage, it can't easily go back
> and recheck which earlier "??AMP??" annotations are still needed. So,
> it just clears the earlier ones unconditionally with the hope of not
> letting too many false-negatives through. It would certainly be
> possible to make it do a better job of detection, but doing so would
> complicate the code quite a bit. (Eventually, I think it would be best
> to build a parse tree, which would make it easier to incorporate other
> linting ideas I have in mind, but I don't have any immediate plans to
> do so.)

Yeah, I certainly don't think this case merits all that effort. I'm
thinking it is worth tweaking CHAINLINTSUPPRESS so that the internal one
is run by "make test", though.

-Peff

Re: [PATCH] t3070: make chain lint tester happy

[Eric Sunshine]

On Sat, Mar 25, 2023 at 4:41 AM Jeff King <peff@peff.net> wrote:
> On Sat, Mar 25, 2023 at 04:18:54AM -0400, Eric Sunshine wrote:
> > This approach
> > does have the benefit that it gives at least _some_ protection (minus
> > caveats mentioned below) on platforms where it may be common to
> > disable chainlint.pl due to slowness, such as Windows.
>
> Certainly the output from chainlint.pl is much nicer, too. :) I think
> I'd be comfortable dropping the internal one at this point in terms of
> quality. The bigger question to me is whether there are setups where it
> isn't run (you mentioned Windows, but I'd have thought the
> single-process invocation made things nice and fast there).

It was my hope and intention that the single-process invocation would
be fast on Windows, but that proved not to be the case, and I've
pretty much given up hope that it will ever be fast on that platform.
Quoting from [1]:

    Somehow Windows manages to be unbelievably slow no matter what. I
    mentioned elsewhere ... that I tested on a five or six year old
    8-core dual-boot machine. Booted to Linux, running a single
    chainlint.pl invocation using all 8 cores to check all scripts in
    the project took under 1 second walltime. The same machine booted
    to Windows using all 8 cores took just under two minutes(!)
    walltime for the single Perl invocation to check all scripts in
    the project.

[1]: https://lore.kernel.org/git/CAPig+cTge7kp9bH+Xd8wpqmEZuuEFE0xQdgqaFP1WAQ-F+xyHA@mail.gmail.com/

Re: [PATCH] t3070: make chain lint tester happy

[Phillip Wood]

On 25/03/2023 08:04, Jeff King wrote:
> On Sat, Mar 25, 2023 at 03:58:32AM -0400, Jeff King wrote:
> 
>>>> This looks like the right solution. I do wonder how Phillip managed to
>>>> miss it, though, since the test script complains loudly.
>>>
>>> I am unable to reproduce any linting errors when running this script
>>> through chainlint, which is why I was more than a little confused by
>>> this patch when I read it, and I was just about to ask for more
>>> information, such as the actual error message.
>>
>> It's not your chain-lint script, but rather the builtin one that sticks
>> "(exit 117) &&" in front of the snippet and evals it. So it creates the
>> exact "foo && bar &" situation by prepending a line to the snippet.
> 
> And btw, I think that is the answer to "how did Phillip not notice it?".
> When running "make test" these days, we rely on chainlint.pl to detect
> any problems, and then set GIT_TEST_CHAIN_LINT=0 so that the scripts do
> not invoke it again. But that variable also suppresses the internal
> linter, and thus "make test" passes, but running the script individually
> does not.

Ah, that explains it, I was wondering how the CI run had passed. Thanks 
to Michael for the patch and Peff and Eric for digging into cause of the 
problem

Best Wishes

Phillip

> It does seem like a recipe for confusion if the two linters are not in
> agreement. I think we might want to either:
> 
>    1. Say that the internal linter still has value, and tweak the
>       suppression so it only turns off the extra per-script run of
>       chainlint.pl, and not the internal one (which is cheap-ish to run).
> 
>    2. Say that the internal linter does not have value, and we should
>       rely on chainlint.pl. In which case we might as well ditch the
>       internal one completely.
> 
>       I'm OK with this direction, if we're comfortable that there are no
>       real problems that would be caught by the internal one but not the
>       script.
> 
> -Peff

Re: [PATCH] t3070: make chain lint tester happy

[Michael J Gruber]

Phillip Wood venit, vidit, dixit 2023-03-26 16:30:31:
> On 25/03/2023 08:04, Jeff King wrote:
> > On Sat, Mar 25, 2023 at 03:58:32AM -0400, Jeff King wrote:
> > 
> >>>> This looks like the right solution. I do wonder how Phillip managed to
> >>>> miss it, though, since the test script complains loudly.
> >>>
> >>> I am unable to reproduce any linting errors when running this script
> >>> through chainlint, which is why I was more than a little confused by
> >>> this patch when I read it, and I was just about to ask for more
> >>> information, such as the actual error message.
> >>
> >> It's not your chain-lint script, but rather the builtin one that sticks
> >> "(exit 117) &&" in front of the snippet and evals it. So it creates the
> >> exact "foo && bar &" situation by prepending a line to the snippet.
> > 
> > And btw, I think that is the answer to "how did Phillip not notice it?".
> > When running "make test" these days, we rely on chainlint.pl to detect
> > any problems, and then set GIT_TEST_CHAIN_LINT=0 so that the scripts do
> > not invoke it again. But that variable also suppresses the internal
> > linter, and thus "make test" passes, but running the script individually
> > does not.
> 
> Ah, that explains it, I was wondering how the CI run had passed. Thanks 
> to Michael for the patch and Peff and Eric for digging into cause of the 
> problem
> 
> Best Wishes
> 
> Phillip
> 
> > It does seem like a recipe for confusion if the two linters are not in
> > agreement. I think we might want to either:
> > 
> >    1. Say that the internal linter still has value, and tweak the
> >       suppression so it only turns off the extra per-script run of
> >       chainlint.pl, and not the internal one (which is cheap-ish to run).
> > 
> >    2. Say that the internal linter does not have value, and we should
> >       rely on chainlint.pl. In which case we might as well ditch the
> >       internal one completely.
> > 
> >       I'm OK with this direction, if we're comfortable that there are no
> >       real problems that would be caught by the internal one but not the
> >       script.
> > 
> > -Peff

Yes, I learned quite a bit from that ;)

In fact, as a list-irregular these days, I was neither aware of the
second linter, nor did I learn it from the test lib code: That gave me
the impression that chainlint.pl was merely a self-test of our linter
(which I guess was half-true for the invocation that I spotted).

I second that we should either settle for one (if one is strictly
superior) or else always run both (if we run any of them). They don't
cause a noticable overhead, do they?

Cheers
Michael

Re: [PATCH] t3070: make chain lint tester happy

[Eric Sunshine]

On Sat, Mar 25, 2023 at 3:58 AM Jeff King <peff@peff.net> wrote:
> On Sat, Mar 25, 2023 at 02:54:45AM -0400, Eric Sunshine wrote:
> > I am unable to reproduce any linting errors when running this script
> > through chainlint, which is why I was more than a little confused by
> > this patch when I read it, and I was just about to ask for more
> > information, such as the actual error message.
>
> It's not your chain-lint script, but rather the builtin one that sticks
> "(exit 117) &&" in front of the snippet and evals it. So it creates the
> exact "foo && bar &" situation by prepending a line to the snippet.

Thanks for clarifying that. I failed to infer that from the commit message.

> So running (on seen, which has 1f2e05f0b79):
>
>   ./t3070-wildmatch.sh
>
> gives me:
>
>   ok 1890 - ipathmatch (via ls-files): match '[Z-y]' 'Z'
>   error: bug in the test script: broken &&-chain or run-away HERE-DOC:
>         test-tool wildmatch wildmatch \
>                 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab \
>                 "*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a" &
>         pid=$! &&
>         sleep 2 &&
>         ! kill $!

Yes, I can reproduce it now. My mistake was that I tested 'seen'
rather than 1f2e05f0b79, not realizing that Junio had already applied
Michael's patch. (I meant to check if it had been applied, but forgot
to do so.)

Re: [PATCH] t3070: make chain lint tester happy

[Jeff King]

On Sat, Mar 25, 2023 at 04:06:39AM -0400, Eric Sunshine wrote:

> On Sat, Mar 25, 2023 at 3:58 AM Jeff King <peff@peff.net> wrote:
> > On Sat, Mar 25, 2023 at 02:54:45AM -0400, Eric Sunshine wrote:
> > > I am unable to reproduce any linting errors when running this script
> > > through chainlint, which is why I was more than a little confused by
> > > this patch when I read it, and I was just about to ask for more
> > > information, such as the actual error message.
> >
> > It's not your chain-lint script, but rather the builtin one that sticks
> > "(exit 117) &&" in front of the snippet and evals it. So it creates the
> > exact "foo && bar &" situation by prepending a line to the snippet.
> 
> Thanks for clarifying that. I failed to infer that from the commit message.

To be fair, I didn't figure it out from the commit either. It's just
that running it stand-alone was the first thing I happened to try. ;)

> Yes, I can reproduce it now. My mistake was that I tested 'seen'
> rather than 1f2e05f0b79, not realizing that Junio had already applied
> Michael's patch. (I meant to check if it had been applied, but forgot
> to do so.)

Oof. I got lucky twice, then, because I did run "seen" but I hadn't
fetched recently enough.

-Peff

[PATCH 2/3] wildmatch: avoid undefined behavior

[Phillip Wood]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

The code changed in this commit is designed to check if the pattern
starts with "**/" or contains "/**/" (see 3a078dec33 (wildmatch: fix
"**" special case, 2013-01-01)). Unfortunately when the pattern begins
with "**/" `prev_p = p - 2` is evaluated when `p` points to the second
"*" and so the subtraction is undefined according to section 6.5.6 of
the C standard because the result does not point within the same object
as `p`. Fix this by avoiding the subtraction unless it is well defined.

Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 wildmatch.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/wildmatch.c b/wildmatch.c
index 06861bd8bc..694d2f8e40 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -83,12 +83,12 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 			continue;
 		case '*':
 			if (*++p == '*') {
-				const uchar *prev_p = p - 2;
+				const uchar *prev_p = p;
 				while (*++p == '*') {}
 				if (!(flags & WM_PATHNAME))
 					/* without WM_PATHNAME, '*' == '**' */
 					match_slash = 1;
-				else if ((prev_p < pattern || *prev_p == '/') &&
+				else if ((prev_p - pattern < 2 || *(prev_p - 2) == '/') &&
 				    (*p == '\0' || *p == '/' ||
 				     (p[0] == '\\' && p[1] == '/'))) {
 					/*
-- 
2.39.2

[PATCH 3/3] wildmatch: hide internal return values

[Phillip Wood]

From: Phillip Wood <phillip.wood@dunelm.org.uk>

WM_ABORT_ALL and WM_ABORT_TO_STARSTAR are used internally to limit
backtracking when a match fails, they are not of interest to the caller
and so should not be public.

Suggested-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
---
 wildmatch.c | 7 ++++++-
 wildmatch.h | 2 --
 2 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/wildmatch.c b/wildmatch.c
index 694d2f8e40..372aa6ea54 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -14,6 +14,10 @@
 
 typedef unsigned char uchar;
 
+/* Internal return values */
+#define WM_ABORT_ALL -1
+#define WM_ABORT_TO_STARSTAR -2
+
 /* What character marks an inverted character class? */
 #define NEGATE_CLASS	'!'
 #define NEGATE_CLASS2	'^'
@@ -278,5 +282,6 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
 /* Match the "pattern" against the "text" string. */
 int wildmatch(const char *pattern, const char *text, unsigned int flags)
 {
-	return dowild((const uchar*)pattern, (const uchar*)text, flags);
+	int res = dowild((const uchar*)pattern, (const uchar*)text, flags);
+	return res == WM_MATCH ? WM_MATCH : WM_NOMATCH;
 }
diff --git a/wildmatch.h b/wildmatch.h
index 5993696298..0c890cb56b 100644
--- a/wildmatch.h
+++ b/wildmatch.h
@@ -6,8 +6,6 @@
 
 #define WM_NOMATCH 1
 #define WM_MATCH 0
-#define WM_ABORT_ALL -1
-#define WM_ABORT_TO_STARSTAR -2
 
 int wildmatch(const char *pattern, const char *text, unsigned int flags);
 #endif
-- 
2.39.2

Re: [PATCH 0/3] wildmatch: fix exponential behavior

[Junio C Hamano]

Phillip Wood <phillip.wood123@gmail.com> writes:

> This series is based on maint. Unfortunately it conflicts with
> my/wildmatch-cleanups when merged with seen. There are sematic
> conflicts with the removal of dowild() in  e303cf8092 (wildmatch:
> more cleanups after killing uchar, 2023-02-26) as well as textual
> conflicts around the change of uchar->char.

Thanks.  What's not in 'next' are fair game to break and force
reroll ;-)

> Phillip Wood (3):
>   wildmatch: fix exponential behavior
>   wildmatch: avoid undefined behavior
>   wildmatch: hide internal return values

Re: [PATCH 0/3] wildmatch: fix exponential behavior

[Derrick Stolee]

On 3/20/2023 12:09 PM, Phillip Wood wrote:
> From: Phillip Wood <phillip.wood@dunelm.org.uk>
> 
> The wildmatch implementation in git suffers from exponential behavior as
> described in [1] where the time taken for a failing match is exponential
> in the number of wildcards it contains. The original implementation
> imported from rsync is immune but the optimizations introduced by [2.3]
> failed to prevent unnecessary backtracking when handling '*' and '/**/'.
> 
> This bug was were discussed on the security list and the conclusion was
> that it only affects operations that are already potential DoS vectors.
> 
> In the long term it would be nice to get rid of the recursion in the
> wildmatch() code but the patches here focus on a minimal fix.

Thanks for these changes. The patches look good to me.

I particularly appreciate that there is a regression test to avoid
this accidentally happening again in the future. The two second
timeout is a reasonable balance between "not taking too long" and
"will not be flaky, assuming the code is correct". I could imagine
that it might _pass_ unexpectedly if it runs on fast-enough hardware,
but that's not a huge concern right now. CI machines are not normally
powered significantly more than a typical developer machine.

Thanks,
-Stolee

Re: [PATCH 0/3] wildmatch: fix exponential behavior

[Phillip Wood]

Hi Stolee

On 23/03/2023 14:19, Derrick Stolee wrote:
> On 3/20/2023 12:09 PM, Phillip Wood wrote:
>> From: Phillip Wood <phillip.wood@dunelm.org.uk>
>>
>> The wildmatch implementation in git suffers from exponential behavior as
>> described in [1] where the time taken for a failing match is exponential
>> in the number of wildcards it contains. The original implementation
>> imported from rsync is immune but the optimizations introduced by [2.3]
>> failed to prevent unnecessary backtracking when handling '*' and '/**/'.
>>
>> This bug was were discussed on the security list and the conclusion was
>> that it only affects operations that are already potential DoS vectors.
>>
>> In the long term it would be nice to get rid of the recursion in the
>> wildmatch() code but the patches here focus on a minimal fix.
> 
> Thanks for these changes. The patches look good to me.
> 
> I particularly appreciate that there is a regression test to avoid
> this accidentally happening again in the future. The two second
> timeout is a reasonable balance between "not taking too long" and
> "will not be flaky, assuming the code is correct". I could imagine
> that it might _pass_ unexpectedly if it runs on fast-enough hardware,
> but that's not a huge concern right now. CI machines are not normally
> powered significantly more than a typical developer machine.

Thanks for taking the time to look at these again and for prompting me 
to add the regression test in the first place.

Best Wishes

Phillip

> Thanks,
> -Stolee