/* $OpenBSD: tests.c,v 1.10 2026/05/31 04:20:58 djm Exp $ */ /* * Regress test for matching functions * * Placed in the public domain */ #include "includes.h" #include #include #include #include #include #include "../test_helper/test_helper.h" #include "match.h" /* Original match_pattern() implementation; has bad worst-case behaviour */ static int match_pattern_original(const char *s, const char *pattern) { for (;;) { /* If at end of pattern, accept if also at end of string. */ if (!*pattern) return !*s; if (*pattern == '*') { /* Skip this and any consecutive asterisks. */ while (*pattern == '*') pattern++; /* If at end of pattern, accept immediately. */ if (!*pattern) return 1; /* If next character in pattern is known, optimize. */ if (*pattern != '?' && *pattern != '*') { /* * Look instances of the next character in * pattern, and try to match starting from * those. */ for (; *s; s++) if (*s == *pattern && match_pattern_original(s + 1, pattern + 1)) return 1; /* Failed. */ return 0; } /* * Move ahead one character at a time and try to * match at each position. */ for (; *s; s++) if (match_pattern_original(s, pattern)) return 1; /* Failed. */ return 0; } /* * There must be at least one more character in the string. * If we are at the end, fail. */ if (!*s) return 0; /* Check if the next character of the string is acceptable. */ if (*pattern != '?' && *pattern != *s) return 0; /* Move to the next character, both in string and in pattern. */ s++; pattern++; } /* NOTREACHED */ } /* n^x for size_t */ static size_t pow_size(size_t base, size_t exp) { size_t r = 1; ASSERT_SIZE_T_NE(base, 0); while (exp-- != 0) { ASSERT_SIZE_T_LE(r, SIZE_MAX / base); r *= base; } return r; } static void make_word(size_t v, const char *alphabet, size_t alphabet_len, char *word, size_t wordlen) { size_t i; for (i = 0; i < wordlen; i++) { word[i] = alphabet[v % alphabet_len]; v /= alphabet_len; } word[wordlen] = '\0'; } #define PATTERN_LEN 8 #define INPUT_LEN 7 static void match_pattern_check_one_input(const char *input, const char *pattern_alphabet) { char pattern[PATTERN_LEN]; size_t len, i, npatterns; int actual, expected; for (len = 0; len < sizeof(pattern); len++) { /* Check with all patterns of this size using alphabet */ npatterns = pow_size(strlen(pattern_alphabet), len); for (i = 0; i < npatterns; i++) { make_word(i, pattern_alphabet, strlen(pattern_alphabet), pattern, len); actual = match_pattern(input, pattern); expected = match_pattern_original(input, pattern); test_subtest_info("input=\"%s\" pattern=\"%s\"", input, pattern); ASSERT_INT_EQ(actual, expected); } } } /* * Check current match_pattern against original one with an exhaustive * combination of patterns and inputs. */ static void match_pattern_exhaustive_original(void) { const char *pattern_alphabet = "abx?*"; const char *input_alphabet = "abc"; char input[INPUT_LEN]; size_t len, i, ninputs; for (len = 0; len < sizeof(input); len++) { /* Check every possible input from alphabet of this size */ ninputs = pow_size(strlen(input_alphabet), len); for (i = 0; i < ninputs; i++) { make_word(i, input_alphabet, strlen(input_alphabet), input, len); match_pattern_check_one_input(input, pattern_alphabet); } } } void tests(void) { TEST_START("match_pattern"); ASSERT_INT_EQ(match_pattern("", ""), 1); ASSERT_INT_EQ(match_pattern("", "aaa"), 0); ASSERT_INT_EQ(match_pattern("aaa", ""), 0); ASSERT_INT_EQ(match_pattern("aaa", "aaaa"), 0); ASSERT_INT_EQ(match_pattern("aaaa", "aaa"), 0); ASSERT_INT_EQ(match_pattern("abc", "abc"), 1); ASSERT_INT_EQ(match_pattern("abc", "abd"), 0); ASSERT_INT_EQ(match_pattern("abc", "abcd"), 0); ASSERT_INT_EQ(match_pattern("abcd", "abc"), 0); TEST_DONE(); TEST_START("match_pattern wildcard"); ASSERT_INT_EQ(match_pattern("", "*"), 1); ASSERT_INT_EQ(match_pattern("", "**"), 1); ASSERT_INT_EQ(match_pattern("", "***"), 1); ASSERT_INT_EQ(match_pattern("", "?"), 0); ASSERT_INT_EQ(match_pattern("", "*?"), 0); ASSERT_INT_EQ(match_pattern("", "?*"), 0); ASSERT_INT_EQ(match_pattern("", "**a*"), 0); ASSERT_INT_EQ(match_pattern("a", "?"), 1); ASSERT_INT_EQ(match_pattern("aa", "a?"), 1); ASSERT_INT_EQ(match_pattern("a", "*"), 1); ASSERT_INT_EQ(match_pattern("aa", "a*"), 1); ASSERT_INT_EQ(match_pattern("aa", "?*"), 1); ASSERT_INT_EQ(match_pattern("aa", "?a"), 1); ASSERT_INT_EQ(match_pattern("aa", "*a"), 1); ASSERT_INT_EQ(match_pattern("ba", "a?"), 0); ASSERT_INT_EQ(match_pattern("ba", "a*"), 0); ASSERT_INT_EQ(match_pattern("ab", "?a"), 0); ASSERT_INT_EQ(match_pattern("ab", "*a"), 0); ASSERT_INT_EQ(match_pattern("aa", "**"), 1); ASSERT_INT_EQ(match_pattern("ab", "a***b"), 1); ASSERT_INT_EQ(match_pattern("axb", "a***b"), 1); ASSERT_INT_EQ(match_pattern("axxb", "a***b"), 1); ASSERT_INT_EQ(match_pattern("ax", "a***b"), 0); ASSERT_INT_EQ(match_pattern("abbb", "a*b*b"), 1); ASSERT_INT_EQ(match_pattern("abbb", "a*b*c"), 0); ASSERT_INT_EQ(match_pattern("aaaaaaaaac", "a*a*a*a*b"), 0); ASSERT_INT_EQ(match_pattern("aaaaaaaaab", "a*a*a*a*b"), 1); ASSERT_INT_EQ(match_pattern("ab", "*b"), 1); ASSERT_INT_EQ(match_pattern("ab", "*a*"), 1); ASSERT_INT_EQ(match_pattern("ab", "*a*b"), 1); ASSERT_INT_EQ(match_pattern("ab", "*a*c"), 0); ASSERT_INT_EQ(match_pattern("abc", "a?c"), 1); ASSERT_INT_EQ(match_pattern("abc", "??c"), 1); ASSERT_INT_EQ(match_pattern("abc", "???"), 1); ASSERT_INT_EQ(match_pattern("abc", "a?d"), 0); ASSERT_INT_EQ(match_pattern("ab", "???"), 0); ASSERT_INT_EQ(match_pattern("abc", "ab*"), 1); ASSERT_INT_EQ(match_pattern("ab", "ab*"), 1); ASSERT_INT_EQ(match_pattern("a", "ab*"), 0); ASSERT_INT_EQ(match_pattern("abc", "ab?"), 1); ASSERT_INT_EQ(match_pattern("ab", "ab?"), 0); ASSERT_INT_EQ(match_pattern("abcd", "ab?"), 0); ASSERT_INT_EQ(match_pattern("abc", "?bc"), 1); ASSERT_INT_EQ(match_pattern("abc", "?b*"), 1); ASSERT_INT_EQ(match_pattern("abc", "?c"), 0); ASSERT_INT_EQ(match_pattern("abc", "a*?c"), 1); ASSERT_INT_EQ(match_pattern("ac", "a*?c"), 0); ASSERT_INT_EQ(match_pattern("abbc", "a*?c"), 1); ASSERT_INT_EQ(match_pattern("abc", "a?*c"), 1); ASSERT_INT_EQ(match_pattern("ac", "a?*c"), 0); ASSERT_INT_EQ(match_pattern("abbc", "a?*c"), 1); ASSERT_INT_EQ(match_pattern("abc", "a*?*c"), 1); ASSERT_INT_EQ(match_pattern("ac", "a*?*c"), 0); ASSERT_INT_EQ(match_pattern("abc", "?*c"), 1); ASSERT_INT_EQ(match_pattern("ac", "?*c"), 1); ASSERT_INT_EQ(match_pattern("c", "?*c"), 0); ASSERT_INT_EQ(match_pattern("abc", "*?c"), 1); ASSERT_INT_EQ(match_pattern("ac", "*?c"), 1); ASSERT_INT_EQ(match_pattern("c", "*?c"), 0); ASSERT_INT_EQ(match_pattern("abc", "a?*"), 1); ASSERT_INT_EQ(match_pattern("ab", "a?*"), 1); ASSERT_INT_EQ(match_pattern("a", "a?*"), 0); ASSERT_INT_EQ(match_pattern("abc", "a*?"), 1); ASSERT_INT_EQ(match_pattern("ab", "a*?"), 1); ASSERT_INT_EQ(match_pattern("a", "a*?"), 0); ASSERT_INT_EQ(match_pattern("abb", "a*b"), 1); ASSERT_INT_EQ(match_pattern("abbc", "a*b"), 0); TEST_DONE(); TEST_START("match_pattern exhaustive original"); match_pattern_exhaustive_original(); TEST_DONE(); TEST_START("match_pattern_list"); ASSERT_INT_EQ(match_pattern_list("", "", 0), 0); /* no patterns */ ASSERT_INT_EQ(match_pattern_list("", "*", 0), 1); ASSERT_INT_EQ(match_pattern_list("", "!*", 0), -1); ASSERT_INT_EQ(match_pattern_list("", "!a,*", 0), 1); ASSERT_INT_EQ(match_pattern_list("", "*,!a", 0), 1); ASSERT_INT_EQ(match_pattern_list("", "a,!*", 0), -1); ASSERT_INT_EQ(match_pattern_list("", "!*,a", 0), -1); ASSERT_INT_EQ(match_pattern_list("a", "", 0), 0); ASSERT_INT_EQ(match_pattern_list("a", "*", 0), 1); ASSERT_INT_EQ(match_pattern_list("a", "!*", 0), -1); ASSERT_INT_EQ(match_pattern_list("a", "!a", 0), -1); /* XXX negated ASSERT_INT_EQ(match_pattern_list("a", "!b", 0), 1); */ ASSERT_INT_EQ(match_pattern_list("a", "!a,*", 0), -1); ASSERT_INT_EQ(match_pattern_list("b", "!a,*", 0), 1); ASSERT_INT_EQ(match_pattern_list("a", "*,!a", 0), -1); ASSERT_INT_EQ(match_pattern_list("b", "*,!a", 0), 1); ASSERT_INT_EQ(match_pattern_list("a", "a,!*", 0), -1); ASSERT_INT_EQ(match_pattern_list("b", "a,!*", 0), -1); ASSERT_INT_EQ(match_pattern_list("a", "a,!a", 0), -1); /* XXX negated ASSERT_INT_EQ(match_pattern_list("b", "a,!a", 0), 1); */ ASSERT_INT_EQ(match_pattern_list("a", "!*,a", 0), -1); ASSERT_INT_EQ(match_pattern_list("b", "!*,a", 0), -1); TEST_DONE(); TEST_START("match_pattern_list lowercase"); ASSERT_INT_EQ(match_pattern_list("abc", "ABC", 0), 0); ASSERT_INT_EQ(match_pattern_list("ABC", "abc", 0), 0); ASSERT_INT_EQ(match_pattern_list("abc", "ABC", 1), 1); ASSERT_INT_EQ(match_pattern_list("ABC", "abc", 1), 0); TEST_DONE(); TEST_START("addr_match_list"); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.0.1/44"), -2); ASSERT_INT_EQ(addr_match_list(NULL, "127.0.0.1/44"), -2); ASSERT_INT_EQ(addr_match_list("a", "*"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "*"), 1); ASSERT_INT_EQ(addr_match_list(NULL, "*"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.0.1"), 1); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.0.2"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.0.1"), -1); /* XXX negated ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.0.2"), 1); */ ASSERT_INT_EQ(addr_match_list("127.0.0.255", "127.0.0.0/24"), 1); ASSERT_INT_EQ(addr_match_list("127.0.1.1", "127.0.0.0/24"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.0.0/24"), 1); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.1.0/24"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.0.0/24"), -1); /* XXX negated ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.1.0/24"), 1); */ ASSERT_INT_EQ(addr_match_list("127.0.0.1", "10.0.0.1,!127.0.0.1"), -1); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.0.1,10.0.0.1"), -1); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "10.0.0.1,127.0.0.2"), 0); ASSERT_INT_EQ(addr_match_list("127.0.0.1", "127.0.0.2,10.0.0.1"), 0); /* XXX negated ASSERT_INT_EQ(addr_match_list("127.0.0.1", "10.0.0.1,!127.0.0.2"), 1); */ /* XXX negated ASSERT_INT_EQ(addr_match_list("127.0.0.1", "!127.0.0.2,10.0.0.1"), 1); */ TEST_DONE(); #define CHECK_FILTER(string,filter,expected) \ do { \ char *result = match_filter_denylist((string), (filter)); \ ASSERT_STRING_EQ(result, expected); \ free(result); \ } while (0) TEST_START("match_filter_list"); CHECK_FILTER("a,b,c", "", "a,b,c"); CHECK_FILTER("a,b,c", "a", "b,c"); CHECK_FILTER("a,b,c", "b", "a,c"); CHECK_FILTER("a,b,c", "c", "a,b"); CHECK_FILTER("a,b,c", "a,b", "c"); CHECK_FILTER("a,b,c", "a,c", "b"); CHECK_FILTER("a,b,c", "b,c", "a"); CHECK_FILTER("a,b,c", "a,b,c", ""); CHECK_FILTER("a,b,c", "b,c", "a"); CHECK_FILTER("", "a,b,c", ""); TEST_DONE(); /* * XXX TODO * int match_host_and_ip(const char *, const char *, const char *); * int match_user(const char *, const char *, const char *, const char *); * char *match_list(const char *, const char *, u_int *); * int addr_match_cidr_list(const char *, const char *); */ } void benchmarks(void) { printf("no benchmarks\n"); }