Wed Apr 26 14:56:54 2017 UTC ()
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


(christos)
diff -r1.36 -r1.37 src/lib/libc/gen/glob.c

cvs diff -r1.36 -r1.37 src/lib/libc/gen/glob.c (expand / switch to unified diff)

--- src/lib/libc/gen/glob.c 2016/09/04 18:27:08 1.36
+++ src/lib/libc/gen/glob.c 2017/04/26 14:56:54 1.37
@@ -1,14 +1,14 @@ @@ -1,14 +1,14 @@
1/* $NetBSD: glob.c,v 1.36 2016/09/04 18:27:08 joerg Exp $ */ 1/* $NetBSD: glob.c,v 1.37 2017/04/26 14:56:54 christos Exp $ */
2 2
3/* 3/*
4 * Copyright (c) 1989, 1993 4 * Copyright (c) 1989, 1993
5 * The Regents of the University of California. All rights reserved. 5 * The Regents of the University of California. All rights reserved.
6 * 6 *
7 * This code is derived from software contributed to Berkeley by 7 * This code is derived from software contributed to Berkeley by
8 * Guido van Rossum. 8 * Guido van Rossum.
9 * 9 *
10 * Redistribution and use in source and binary forms, with or without 10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions 11 * modification, are permitted provided that the following conditions
12 * are met: 12 * are met:
13 * 1. Redistributions of source code must retain the above copyright 13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer. 14 * notice, this list of conditions and the following disclaimer.
@@ -27,27 +27,27 @@ @@ -27,27 +27,27 @@
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE. 32 * SUCH DAMAGE.
33 */ 33 */
34 34
35#include <sys/cdefs.h> 35#include <sys/cdefs.h>
36#if defined(LIBC_SCCS) && !defined(lint) 36#if defined(LIBC_SCCS) && !defined(lint)
37#if 0 37#if 0
38static char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93"; 38static char sccsid[] = "@(#)glob.c 8.3 (Berkeley) 10/13/93";
39#else 39#else
40__RCSID("$NetBSD: glob.c,v 1.36 2016/09/04 18:27:08 joerg Exp $"); 40__RCSID("$NetBSD: glob.c,v 1.37 2017/04/26 14:56:54 christos Exp $");
41#endif 41#endif
42#endif /* LIBC_SCCS and not lint */ 42#endif /* LIBC_SCCS and not lint */
43 43
44/* 44/*
45 * glob(3) -- a superset of the one defined in POSIX 1003.2. 45 * glob(3) -- a superset of the one defined in POSIX 1003.2.
46 * 46 *
47 * The [!...] convention to negate a range is supported (SysV, Posix, ksh). 47 * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
48 * 48 *
49 * Optional extra services, controlled by flags not defined by POSIX: 49 * Optional extra services, controlled by flags not defined by POSIX:
50 * 50 *
51 * GLOB_MAGCHAR: 51 * GLOB_MAGCHAR:
52 * Set in gl_flags if pattern contained a globbing character. 52 * Set in gl_flags if pattern contained a globbing character.
53 * GLOB_NOMAGIC: 53 * GLOB_NOMAGIC:
@@ -926,78 +926,93 @@ globextend(const Char *path, glob_t *pgl @@ -926,78 +926,93 @@ globextend(const Char *path, glob_t *pgl
926 926
927 if ((pglob->gl_flags & GLOB_LIMIT) && 927 if ((pglob->gl_flags & GLOB_LIMIT) &&
928 (newsize + limit->l_string) >= GLOB_LIMIT_STRING) 928 (newsize + limit->l_string) >= GLOB_LIMIT_STRING)
929 goto nospace; 929 goto nospace;
930 930
931 return copy == NULL ? GLOB_NOSPACE : 0; 931 return copy == NULL ? GLOB_NOSPACE : 0;
932nospace: 932nospace:
933 errno = 0; 933 errno = 0;
934 return GLOB_NOSPACE; 934 return GLOB_NOSPACE;
935} 935}
936 936
937 937
938/* 938/*
939 * pattern matching function for filenames. Each occurrence of the * 939 * pattern matching function for filenames.
940 * pattern causes a recursion level. 
941 */ 940 */
942static int 941static int
943match(const Char *name, const Char *pat, const Char *patend) 942match(const Char *name, const Char *pat, const Char *patend)
944{ 943{
945 int ok, negate_range; 944 int ok, negate_range;
946 Char c, k; 945 Char c, k;
 946 const Char *patNext, *nameNext, *nameStart, *nameEnd;
947 947
948 _DIAGASSERT(name != NULL); 948 _DIAGASSERT(name != NULL);
949 _DIAGASSERT(pat != NULL); 949 _DIAGASSERT(pat != NULL);
950 _DIAGASSERT(patend != NULL); 950 _DIAGASSERT(patend != NULL);
951 951 patNext = pat;
952 while (pat < patend) { 952 nameStart = nameNext = name;
953 c = *pat++; 953 nameEnd = NULL;
 954
 955 while (pat < patend || *name) {
 956 c = *pat;
 957 if (*name == EOS)
 958 nameEnd = name;
954 switch (c & M_MASK) { 959 switch (c & M_MASK) {
955 case M_ALL: 960 case M_ALL:
956 while (pat < patend && (*pat & M_MASK) == M_ALL) 961 while (pat[1] == '*') pat++;
957 pat++; /* eat consecutive '*' */ 962 patNext = pat;
958 if (pat == patend) 963 nameNext = name + 1;
959 return 1; 964 pat++;
960 for (; !match(name, pat, patend); name++) 965 continue;
961 if (*name == EOS) 
962 return 0; 
963 return 1; 
964 case M_ONE: 966 case M_ONE:
965 if (*name++ == EOS) 967 if (*name == EOS)
966 return 0; 968 break;
967 break; 969 pat++;
 970 name++;
 971 continue;
968 case M_SET: 972 case M_SET:
969 ok = 0; 973 ok = 0;
970 if ((k = *name++) == EOS) 974 if ((k = *name) == EOS)
971 return 0; 975 break;
 976 pat++;
 977 name++;
972 if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS) 978 if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
973 ++pat; 979 ++pat;
974 while (((c = *pat++) & M_MASK) != M_END) 980 while (((c = *pat++) & M_MASK) != M_END)
975 if ((*pat & M_MASK) == M_RNG) { 981 if ((*pat & M_MASK) == M_RNG) {
976 if (c <= k && k <= pat[1]) 982 if (c <= k && k <= pat[1])
977 ok = 1; 983 ok = 1;
978 pat += 2; 984 pat += 2;
979 } else if (c == k) 985 } else if (c == k)
980 ok = 1; 986 ok = 1;
981 if (ok == negate_range) 987 if (ok == negate_range)
982 return 0; 988 break;
983 break; 989 continue;
984 default: 990 default:
985 if (*name++ != c) 991 if (*name != c)
986 return 0; 992 break;
987 break; 993 pat++;
 994 name++;
 995 continue;
988 } 996 }
 997 if (nameNext != nameStart
 998 && (nameEnd == NULL || nameNext <= nameEnd)) {
 999 pat = patNext;
 1000 name = nameNext;
 1001 continue;
 1002 }
 1003 return 0;
989 } 1004 }
990 return *name == EOS; 1005 return 1;
991} 1006}
992 1007
993/* Free allocated data belonging to a glob_t structure. */ 1008/* Free allocated data belonging to a glob_t structure. */
994void 1009void
995globfree(glob_t *pglob) 1010globfree(glob_t *pglob)
996{ 1011{
997 size_t i; 1012 size_t i;
998 char **pp; 1013 char **pp;
999 1014
1000 _DIAGASSERT(pglob != NULL); 1015 _DIAGASSERT(pglob != NULL);
1001 1016
1002 if (pglob->gl_pathv != NULL) { 1017 if (pglob->gl_pathv != NULL) {
1003 pp = pglob->gl_pathv + pglob->gl_offs; 1018 pp = pglob->gl_pathv + pglob->gl_offs;