From: Derrick Stolee <derrickstolee@github.com>
To: Phillip Wood <phillip.wood@dunelm.org.uk>, git@vger.kernel.org
Cc: Jeff King <peff@peff.net>
Subject: Re: [PATCH 0/3] wildmatch: fix exponential behavior
Date: Thu, 23 Mar 2023 10:19:21 -0400 [thread overview]
Message-ID: <f6e3ae73-daae-3cc1-eb16-d4a24a2612db@github.com> (raw)
In-Reply-To: <cover.1679328580.git.phillip.wood@dunelm.org.uk>
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
next prev parent reply other threads:[~2023-03-23 14:20 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-20 16:09 [PATCH 0/3] wildmatch: fix exponential behavior Phillip Wood
2023-03-20 16:10 ` [PATCH 1/3] " Phillip Wood
2023-03-24 22:17 ` [PATCH] t3070: make chain lint tester happy Michael J Gruber
2023-03-25 6:37 ` Jeff King
2023-03-25 6:54 ` Eric Sunshine
2023-03-25 7:58 ` Jeff King
2023-03-25 8:04 ` Jeff King
2023-03-25 8:18 ` Eric Sunshine
2023-03-25 8:41 ` Jeff King
2023-03-25 8:51 ` Jeff King
2023-03-25 9:09 ` Eric Sunshine
2023-03-25 19:47 ` Jeff King
2023-03-25 9:17 ` Eric Sunshine
2023-03-26 14:30 ` Phillip Wood
2023-03-26 14:54 ` Michael J Gruber
2023-03-25 8:06 ` Eric Sunshine
2023-03-25 8:36 ` Jeff King
2023-03-20 16:10 ` [PATCH 2/3] wildmatch: avoid undefined behavior Phillip Wood
2023-03-20 16:10 ` [PATCH 3/3] wildmatch: hide internal return values Phillip Wood
2023-03-20 17:58 ` [PATCH 0/3] wildmatch: fix exponential behavior Junio C Hamano
2023-03-23 14:19 ` Derrick Stolee [this message]
2023-03-24 14:04 ` Phillip Wood
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f6e3ae73-daae-3cc1-eb16-d4a24a2612db@github.com \
--to=derrickstolee@github.com \
--cc=git@vger.kernel.org \
--cc=peff@peff.net \
--cc=phillip.wood@dunelm.org.uk \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).