[PATCH 0/3] wildmatch: fix exponential behavior

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(-)