[PATCH 0/3] wildmatch: fix exponential behavior

[Phillip Wood <phillip.wood123@gmail.com>]

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