[src/trunk]: src/lib/libc/gen Switch from a recursive pattern matching algori...

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/6add84883f1e
branches:  trunk
changeset: 353270:6add84883f1e
user:      christos <christos%NetBSD.org@localhost>
date:      Wed Apr 26 14:56:54 2017 +0000

description:
Switch from a recursive pattern matching algorithm to handle '*'
to a backtracking one. Avoids DoS attacks with patterns "a*a*a*a*a*...b"
matching against "aaaaaaaaaaaa..." https://research.swtch.com/glob

diffstat:

 lib/libc/gen/glob.c |  65 ++++++++++++++++++++++++++++++++--------------------
 1 files changed, 40 insertions(+), 25 deletions(-)

diffs (112 lines):

diff -r a864bcafb2e0 -r 6add84883f1e lib/libc/gen/glob.c
--- a/lib/libc/gen/glob.c       Wed Apr 26 14:52:57 2017 +0000
+++ b/lib/libc/gen/glob.c       Wed Apr 26 14:56:54 2017 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: glob.c,v 1.36 2016/09/04 18:27:08 joerg Exp $  */
+/*     $NetBSD: glob.c,v 1.37 2017/04/26 14:56:54 christos Exp $       */
 
 /*
  * Copyright (c) 1989, 1993
@@ -37,7 +37,7 @@
 #if 0
 static char sccsid[] = "@(#)glob.c     8.3 (Berkeley) 10/13/93";
 #else
-__RCSID("$NetBSD: glob.c,v 1.36 2016/09/04 18:27:08 joerg Exp $");
+__RCSID("$NetBSD: glob.c,v 1.37 2017/04/26 14:56:54 christos Exp $");
 #endif
 #endif /* LIBC_SCCS and not lint */
 
@@ -936,39 +936,45 @@
 
 
 /*
- * pattern matching function for filenames.  Each occurrence of the *
- * pattern causes a recursion level.
+ * pattern matching function for filenames.
  */
 static int
 match(const Char *name, const Char *pat, const Char *patend)
 {
        int ok, negate_range;
        Char c, k;
+       const Char *patNext, *nameNext, *nameStart, *nameEnd;
 
        _DIAGASSERT(name != NULL);
        _DIAGASSERT(pat != NULL);
        _DIAGASSERT(patend != NULL);
+       patNext = pat;
+       nameStart = nameNext = name;
+       nameEnd = NULL;
 
-       while (pat < patend) {
-               c = *pat++;
+       while (pat < patend || *name) {
+               c = *pat;
+               if (*name == EOS)
+                       nameEnd = name;
                switch (c & M_MASK) {
                case M_ALL:
-                       while (pat < patend && (*pat & M_MASK) == M_ALL)
-                               pat++;  /* eat consecutive '*' */
-                       if (pat == patend)
-                               return 1;
-                       for (; !match(name, pat, patend); name++)
-                               if (*name == EOS)
-                                       return 0;
-                       return 1;
+                       while (pat[1] == '*') pat++;
+                       patNext = pat;
+                       nameNext = name + 1;
+                       pat++;
+                       continue;
                case M_ONE:
-                       if (*name++ == EOS)
-                               return 0;
-                       break;
+                       if (*name == EOS)
+                               break;
+                       pat++;
+                       name++;
+                       continue;
                case M_SET:
                        ok = 0;
-                       if ((k = *name++) == EOS)
-                               return 0;
+                       if ((k = *name) == EOS)
+                               break;
+                       pat++;
+                       name++;
                        if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
                                ++pat;
                        while (((c = *pat++) & M_MASK) != M_END)
@@ -979,15 +985,24 @@
                                } else if (c == k)
                                        ok = 1;
                        if (ok == negate_range)
-                               return 0;
-                       break;
+                               break;
+                       continue;
                default:
-                       if (*name++ != c)
-                               return 0;
-                       break;
+                       if (*name != c)
+                               break;
+                       pat++;
+                       name++;
+                       continue;
                }
+               if (nameNext != nameStart
+                   && (nameEnd == NULL || nameNext <= nameEnd)) {
+                       pat = patNext;
+                       name = nameNext;
+                       continue;
+               }
+               return 0;
        }
-       return *name == EOS;
+       return 1;
 }
 
 /* Free allocated data belonging to a glob_t structure. */