Author: cem Date: Wed May 3 15:55:29 2017 New Revision: 317749 URL: https://svnweb.freebsd.org/changeset/base/317749
Log: libc glob: Avoid pathological exponential behavior Adapt glob's match() routine to use a greedy algorithm that avoids exponential runtime in byzantine inputs. While here, add a testcase for the byzantine input. Prompted by: https://research.swtch.com/glob Authored by: Yves Orton <demerphq at gmail.com> Obtained from: Perl (33252c318625f3c6c89b816ee88481940e3e6f95) Sponsored by: Dell EMC Isilon Added: head/lib/libc/tests/gen/glob2_test.c (contents, props changed) Modified: head/lib/libc/gen/glob.c head/lib/libc/tests/gen/Makefile Modified: head/lib/libc/gen/glob.c ============================================================================== --- head/lib/libc/gen/glob.c Wed May 3 15:20:40 2017 (r317748) +++ head/lib/libc/gen/glob.c Wed May 3 15:55:29 2017 (r317749) @@ -903,61 +903,73 @@ globextend(const Char *path, glob_t *pgl } /* - * pattern matching function for filenames. Each occurrence of the * - * pattern causes a recursion level. + * pattern matching function for filenames. */ static int match(Char *name, Char *pat, Char *patend) { int ok, negate_range; - Char c, k; + Char c, k, *nextp, *nextn; struct xlocale_collate *table = (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE]; - while (pat < patend) { - c = *pat++; - switch (c & M_MASK) { - case M_ALL: - if (pat == patend) - return (1); - do - if (match(name, pat, patend)) - return (1); - while (*name++ != EOS); - return (0); - case M_ONE: - if (*name++ == EOS) - return (0); - break; - case M_SET: - ok = 0; - if ((k = *name++) == EOS) - return (0); - if ((negate_range = ((*pat & M_MASK) == M_NOT)) != 0) - ++pat; - while (((c = *pat++) & M_MASK) != M_END) - if ((*pat & M_MASK) == M_RNG) { - if (table->__collate_load_error ? - CHAR(c) <= CHAR(k) && - CHAR(k) <= CHAR(pat[1]) : - __wcollate_range_cmp(CHAR(c), - CHAR(k)) <= 0 && - __wcollate_range_cmp(CHAR(k), - CHAR(pat[1])) <= 0) + nextn = NULL; + nextp = NULL; + + while (1) { + while (pat < patend) { + c = *pat++; + switch (c & M_MASK) { + case M_ALL: + if (pat == patend) + return (1); + if (*name == EOS) + return (0); + nextn = name + 1; + nextp = pat - 1; + break; + case M_ONE: + if (*name++ == EOS) + goto fail; + break; + case M_SET: + ok = 0; + if ((k = *name++) == EOS) + goto fail; + if ((negate_range = ((*pat & M_MASK) == M_NOT)) != 0) + ++pat; + while (((c = *pat++) & M_MASK) != M_END) + if ((*pat & M_MASK) == M_RNG) { + if (table->__collate_load_error ? + CHAR(c) <= CHAR(k) && + CHAR(k) <= CHAR(pat[1]) : + __wcollate_range_cmp(CHAR(c), + CHAR(k)) <= 0 && + __wcollate_range_cmp(CHAR(k), + CHAR(pat[1])) <= 0) + ok = 1; + pat += 2; + } else if (c == k) ok = 1; - pat += 2; - } else if (c == k) - ok = 1; - if (ok == negate_range) - return (0); - break; - default: - if (*name++ != c) - return (0); - break; + if (ok == negate_range) + goto fail; + break; + default: + if (*name++ != c) + goto fail; + break; + } } + if (*name == EOS) + return (1); + + fail: + if (nextn == NULL) + break; + pat = nextp; + name = nextn; } - return (*name == EOS); + return (0); } /* Free allocated data belonging to a glob_t structure. */ Modified: head/lib/libc/tests/gen/Makefile ============================================================================== --- head/lib/libc/tests/gen/Makefile Wed May 3 15:20:40 2017 (r317748) +++ head/lib/libc/tests/gen/Makefile Wed May 3 15:55:29 2017 (r317749) @@ -8,6 +8,7 @@ ATF_TESTS_C+= fmtmsg_test ATF_TESTS_C+= fnmatch2_test ATF_TESTS_C+= fpclassify2_test ATF_TESTS_C+= ftw_test +ATF_TESTS_C+= glob2_test ATF_TESTS_C+= popen_test ATF_TESTS_C+= posix_spawn_test ATF_TESTS_C+= wordexp_test Added: head/lib/libc/tests/gen/glob2_test.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/lib/libc/tests/gen/glob2_test.c Wed May 3 15:55:29 2017 (r317749) @@ -0,0 +1,114 @@ +/* + * Copyright (c) 2017 Dell EMC Isilon + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/param.h> +#include <errno.h> +#include <fcntl.h> +#include <glob.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <unistd.h> + +#include <atf-c.h> + +/* + * Derived from Russ Cox' pathological case test program used for the + * https://research.swtch.com/glob article. + */ +ATF_TC_WITHOUT_HEAD(glob_pathological_test); +ATF_TC_BODY(glob_pathological_test, tc) +{ + struct timespec t, t2; + glob_t g; + const char *longname = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; + char pattern[1000], *p; + double dt; + unsigned i, j, k, mul; + int fd, rc; + + fd = open(longname, O_CREAT | O_RDWR, 0666); + ATF_REQUIRE(fd >= 0); + + /* + * Test up to 100 a* groups. Exponential implementations typically go + * bang at i=7 or 8. + */ + for (i = 0; i < 100; i++) { + /* + * Create a*...b pattern with i 'a*' groups. + */ + p = pattern; + for (k = 0; k < i; k++) { + *p++ = 'a'; + *p++ = '*'; + } + *p++ = 'b'; + *p = '\0'; + + clock_gettime(CLOCK_REALTIME, &t); + for (j = 0; j < mul; j++) { + memset(&g, 0, sizeof g); + rc = glob(pattern, 0, 0, &g); + if (rc == GLOB_NOSPACE || rc == GLOB_ABORTED) { + ATF_REQUIRE_MSG(rc == GLOB_NOMATCH, + "an unexpected error occurred: " + "rc=%d errno=%d", rc, errno); + /* NORETURN */ + } + + ATF_CHECK_MSG(rc == GLOB_NOMATCH, + "A bogus match occurred: '%s' ~ '%s'", pattern, + g.gl_pathv[0]); + globfree(&g); + } + clock_gettime(CLOCK_REALTIME, &t2); + + t2.tv_sec -= t.tv_sec; + t2.tv_nsec -= t.tv_nsec; + dt = t2.tv_sec + (double)t2.tv_nsec/1e9; + dt /= mul; + + ATF_CHECK_MSG(dt < 1, "glob(3) took far too long: %d %.9f", i, + dt); + + if (dt >= 0.0001) + mul = 1; + } +} + +ATF_TP_ADD_TCS(tp) +{ + + ATF_TP_ADD_TC(tp, glob_pathological_test); + + return (atf_no_error()); +} _______________________________________________ [email protected] mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "[email protected]"
