/* $NetBSD: match.c,v 1.15 2021/03/05 17:47:16 christos Exp $ */
/* $OpenBSD: match.c,v 1.43 2020/11/03 22:53:12 djm Exp $ */
/*
* Author: Tatu Ylonen <ylo@cs.hut.fi>
* Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
* All rights reserved
* Simple pattern matching, with '*' and '?' as wildcards.
*
* As far as I am concerned, the code I have written for this software
* can be used freely for any purpose. Any derived versions of this
* software must be clearly marked as such, and if the derived work is
* incompatible with the protocol description in the RFC file, it must be
* called by a name other than "ssh" or "Secure Shell".
*/
/*
* Copyright (c) 2000 Markus Friedl. 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 ``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 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 "includes.h"
__RCSID("$NetBSD: match.c,v 1.15 2021/03/05 17:47:16 christos Exp $");
#include <sys/types.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>
#include "xmalloc.h"
#include "match.h"
#include "misc.h"
/*
* Returns true if the given string matches the pattern (which may contain ?
* and * as wildcards), and zero if it does not match.
*/
int
match_pattern(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(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(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 */
}
/*
* Tries to match the string against the
* comma-separated sequence of subpatterns (each possibly preceded by ! to
* indicate negation). Returns -1 if negation matches, 1 if there is
* a positive match, 0 if there is no match at all.
*/
int
match_pattern_list(const char *string, const char *pattern, int dolower)
{
char sub[1024];
int negated;
int got_positive;
u_int i, subi, len = strlen(pattern);
got_positive = 0;
for (i = 0; i < len;) {
/* Check if the subpattern is negated. */
if (pattern[i] == '!') {
negated = 1;
i++;
} else
negated = 0;
/*
* Extract the subpattern up to a comma or end. Convert the
* subpattern to lowercase.
*/
for (subi = 0;
i < len && subi < sizeof(sub) - 1 && pattern[i] != ',';
subi++, i++)
sub[subi] = dolower && isupper((u_char)pattern[i]) ?
tolower((u_char)pattern[i]) : pattern[i];
/* If subpattern too long, return failure (no match). */
if (subi >= sizeof(sub) - 1)
return 0;
/* If the subpattern was terminated by a comma, then skip it. */
if (i < len && pattern[i] == ',')
i++;
/* Null-terminate the subpattern. */
sub[subi] = '\0';
/* Try to match the subpattern against the string. */
if (match_pattern(string, sub)) {
if (negated)
return -1; /* Negative */
else
got_positive = 1; /* Positive */
}
}
/*
* Return success if got a positive match. If there was a negative
* match, we have already returned -1 and never get here.
*/
return got_positive;
}
/* Match a list representing users or groups. */
int
match_usergroup_pattern_list(const char *string, const char *pattern)
{
/* Case sensitive match */
return match_pattern_list(string, pattern, 0);
}
/*
* Tries to match the host name (which must be in all lowercase) against the
* comma-separated sequence of subpatterns (each possibly preceded by ! to
* indicate negation). Returns -1 if negation matches, 1 if there is
* a positive match, 0 if there is no match at all.
*/
int
match_hostname(const char *host, const char *pattern)
{
char *hostcopy = xstrdup(host);
int r;
lowercase(hostcopy);
r = match_pattern_list(hostcopy, pattern, 1);
free(hostcopy);
return r;
}
/*
* returns 0 if we get a negative match for the hostname or the ip
* or if we get no match at all. returns -1 on error, or 1 on
* successful match.
*/
int
match_host_and_ip(const char *host, const char *ipaddr,
const char *patterns)
{
int mhost, mip;
if ((mip = addr_match_list(ipaddr, patterns)) == -2)
return -1; /* error in ipaddr match */
else if (host == NULL || ipaddr == NULL || mip == -1)
return 0; /* negative ip address match, or testing pattern */
/* negative hostname match */
if ((mhost = match_hostname(host, patterns)) == -1)
return 0;
/* no match at all */
if (mhost == 0 && mip == 0)
return 0;
return 1;
}
/*
* Match user, user@host_or_ip, user@host_or_ip_list against pattern.
* If user, host and ipaddr are all NULL then validate pattern/
* Returns -1 on invalid pattern, 0 on no match, 1 on match.
*/
int
match_user(const char *user, const char *host, const char *ipaddr,
const char *pattern)
{
char *p, *pat;
int ret;
/* test mode */
if (user == NULL && host == NULL && ipaddr == NULL) {
if ((p = strchr(pattern, '@')) != NULL &&
match_host_and_ip(NULL, NULL, p + 1) < 0)
return -1;
return 0;
}
if ((p = strchr(pattern, '@')) == NULL)
return match_pattern(user, pattern);
pat = xstrdup(pattern);
p = strchr(pat, '@');
*p++ = '\0';
if ((ret = match_pattern(user, pat)) == 1)
ret = match_host_and_ip(host, ipaddr, p);
free(pat);
return ret;
}
/*
* Returns first item from client-list that is also supported by server-list,
* caller must free the returned string.
*/
#define MAX_PROP 40
#define SEP ","
char *
match_list(const char *client, const char *server, u_int *next)
{
char *sproposals[MAX_PROP];
char *c, *s, *p, *ret, *cp, *sp;
int i, j, nproposals;
c = cp = xstrdup(client);
s = sp = xstrdup(server);
for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
(p = strsep(&sp, SEP)), i++) {
if (i < MAX_PROP)
sproposals[i] = p;
else
break;
}
nproposals = i;
for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
(p = strsep(&cp, SEP)), i++) {
for (j = 0; j < nproposals; j++) {
if (strcmp(p, sproposals[j]) == 0) {
ret = xstrdup(p);
if (next != NULL)
*next = (cp == NULL) ?
strlen(c) : (u_int)(cp - c);
free(c);
free(s);
return ret;
}
}
}
if (next != NULL)
*next = strlen(c);
free(c);
free(s);
return NULL;
}
/*
* Filter proposal using pattern-list filter.
* "denylist" determines sense of filter:
* non-zero indicates that items matching filter should be excluded.
* zero indicates that only items matching filter should be included.
* returns NULL on allocation error, otherwise caller must free result.
*/
static char *
filter_list(const char *proposal, const char *filter, int denylist)
{
size_t len = strlen(proposal) + 1;
char *fix_prop = malloc(len);
char *orig_prop = strdup(proposal);
char *cp, *tmp;
int r;
if (fix_prop == NULL || orig_prop == NULL) {
free(orig_prop);
free(fix_prop);
return NULL;
}
tmp = orig_prop;
*fix_prop = '\0';
while ((cp = strsep(&tmp, ",")) != NULL) {
r = match_pattern_list(cp, filter, 0);
if ((denylist && r != 1) || (!denylist && r == 1)) {
if (*fix_prop != '\0')
strlcat(fix_prop, ",", len);
strlcat(fix_prop, cp, len);
}
}
free(orig_prop);
return fix_prop;
}
/*
* Filters a comma-separated list of strings, excluding any entry matching
* the 'filter' pattern list. Caller must free returned string.
*/
char *
match_filter_denylist(const char *proposal, const char *filter)
{
return filter_list(proposal, filter, 1);
}
/*
* Filters a comma-separated list of strings, including only entries matching
* the 'filter' pattern list. Caller must free returned string.
*/
char *
match_filter_allowlist(const char *proposal, const char *filter)
{
return filter_list(proposal, filter, 0);
}