xref: /openssh-portable/match.c (revision 72687c8e)
1 /* $OpenBSD: match.c,v 1.41 2019/11/13 04:47:52 deraadt Exp $ */
2 /*
3  * Author: Tatu Ylonen <ylo@cs.hut.fi>
4  * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland
5  *                    All rights reserved
6  * Simple pattern matching, with '*' and '?' as wildcards.
7  *
8  * As far as I am concerned, the code I have written for this software
9  * can be used freely for any purpose.  Any derived versions of this
10  * software must be clearly marked as such, and if the derived work is
11  * incompatible with the protocol description in the RFC file, it must be
12  * called by a name other than "ssh" or "Secure Shell".
13  */
14 /*
15  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions
19  * are met:
20  * 1. Redistributions of source code must retain the above copyright
21  *    notice, this list of conditions and the following disclaimer.
22  * 2. Redistributions in binary form must reproduce the above copyright
23  *    notice, this list of conditions and the following disclaimer in the
24  *    documentation and/or other materials provided with the distribution.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 #include "includes.h"
39 
40 #include <sys/types.h>
41 
42 #include <ctype.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <stdarg.h>
46 #include <stdio.h>
47 
48 #include "xmalloc.h"
49 #include "match.h"
50 #include "misc.h"
51 
52 /*
53  * Returns true if the given string matches the pattern (which may contain ?
54  * and * as wildcards), and zero if it does not match.
55  */
56 
57 int
match_pattern(const char * s,const char * pattern)58 match_pattern(const char *s, const char *pattern)
59 {
60 	for (;;) {
61 		/* If at end of pattern, accept if also at end of string. */
62 		if (!*pattern)
63 			return !*s;
64 
65 		if (*pattern == '*') {
66 			/* Skip the asterisk. */
67 			pattern++;
68 
69 			/* If at end of pattern, accept immediately. */
70 			if (!*pattern)
71 				return 1;
72 
73 			/* If next character in pattern is known, optimize. */
74 			if (*pattern != '?' && *pattern != '*') {
75 				/*
76 				 * Look instances of the next character in
77 				 * pattern, and try to match starting from
78 				 * those.
79 				 */
80 				for (; *s; s++)
81 					if (*s == *pattern &&
82 					    match_pattern(s + 1, pattern + 1))
83 						return 1;
84 				/* Failed. */
85 				return 0;
86 			}
87 			/*
88 			 * Move ahead one character at a time and try to
89 			 * match at each position.
90 			 */
91 			for (; *s; s++)
92 				if (match_pattern(s, pattern))
93 					return 1;
94 			/* Failed. */
95 			return 0;
96 		}
97 		/*
98 		 * There must be at least one more character in the string.
99 		 * If we are at the end, fail.
100 		 */
101 		if (!*s)
102 			return 0;
103 
104 		/* Check if the next character of the string is acceptable. */
105 		if (*pattern != '?' && *pattern != *s)
106 			return 0;
107 
108 		/* Move to the next character, both in string and in pattern. */
109 		s++;
110 		pattern++;
111 	}
112 	/* NOTREACHED */
113 }
114 
115 /*
116  * Tries to match the string against the
117  * comma-separated sequence of subpatterns (each possibly preceded by ! to
118  * indicate negation).  Returns -1 if negation matches, 1 if there is
119  * a positive match, 0 if there is no match at all.
120  */
121 int
match_pattern_list(const char * string,const char * pattern,int dolower)122 match_pattern_list(const char *string, const char *pattern, int dolower)
123 {
124 	char sub[1024];
125 	int negated;
126 	int got_positive;
127 	u_int i, subi, len = strlen(pattern);
128 
129 	got_positive = 0;
130 	for (i = 0; i < len;) {
131 		/* Check if the subpattern is negated. */
132 		if (pattern[i] == '!') {
133 			negated = 1;
134 			i++;
135 		} else
136 			negated = 0;
137 
138 		/*
139 		 * Extract the subpattern up to a comma or end.  Convert the
140 		 * subpattern to lowercase.
141 		 */
142 		for (subi = 0;
143 		    i < len && subi < sizeof(sub) - 1 && pattern[i] != ',';
144 		    subi++, i++)
145 			sub[subi] = dolower && isupper((u_char)pattern[i]) ?
146 			    tolower((u_char)pattern[i]) : pattern[i];
147 		/* If subpattern too long, return failure (no match). */
148 		if (subi >= sizeof(sub) - 1)
149 			return 0;
150 
151 		/* If the subpattern was terminated by a comma, then skip it. */
152 		if (i < len && pattern[i] == ',')
153 			i++;
154 
155 		/* Null-terminate the subpattern. */
156 		sub[subi] = '\0';
157 
158 		/* Try to match the subpattern against the string. */
159 		if (match_pattern(string, sub)) {
160 			if (negated)
161 				return -1;		/* Negative */
162 			else
163 				got_positive = 1;	/* Positive */
164 		}
165 	}
166 
167 	/*
168 	 * Return success if got a positive match.  If there was a negative
169 	 * match, we have already returned -1 and never get here.
170 	 */
171 	return got_positive;
172 }
173 
174 /* Match a list representing users or groups. */
175 int
match_usergroup_pattern_list(const char * string,const char * pattern)176 match_usergroup_pattern_list(const char *string, const char *pattern)
177 {
178 #ifdef HAVE_CYGWIN
179 	/* Windows usernames may be Unicode and are not case sensitive */
180 	return cygwin_ug_match_pattern_list(string, pattern);
181 #else
182 	/* Case sensitive match */
183 	return match_pattern_list(string, pattern, 0);
184 #endif
185 }
186 
187 /*
188  * Tries to match the host name (which must be in all lowercase) against the
189  * comma-separated sequence of subpatterns (each possibly preceded by ! to
190  * indicate negation).  Returns -1 if negation matches, 1 if there is
191  * a positive match, 0 if there is no match at all.
192  */
193 int
match_hostname(const char * host,const char * pattern)194 match_hostname(const char *host, const char *pattern)
195 {
196 	char *hostcopy = xstrdup(host);
197 	int r;
198 
199 	lowercase(hostcopy);
200 	r = match_pattern_list(hostcopy, pattern, 1);
201 	free(hostcopy);
202 	return r;
203 }
204 
205 /*
206  * returns 0 if we get a negative match for the hostname or the ip
207  * or if we get no match at all.  returns -1 on error, or 1 on
208  * successful match.
209  */
210 int
match_host_and_ip(const char * host,const char * ipaddr,const char * patterns)211 match_host_and_ip(const char *host, const char *ipaddr,
212     const char *patterns)
213 {
214 	int mhost, mip;
215 
216 	if ((mip = addr_match_list(ipaddr, patterns)) == -2)
217 		return -1; /* error in ipaddr match */
218 	else if (host == NULL || ipaddr == NULL || mip == -1)
219 		return 0; /* negative ip address match, or testing pattern */
220 
221 	/* negative hostname match */
222 	if ((mhost = match_hostname(host, patterns)) == -1)
223 		return 0;
224 	/* no match at all */
225 	if (mhost == 0 && mip == 0)
226 		return 0;
227 	return 1;
228 }
229 
230 /*
231  * Match user, user@host_or_ip, user@host_or_ip_list against pattern.
232  * If user, host and ipaddr are all NULL then validate pattern/
233  * Returns -1 on invalid pattern, 0 on no match, 1 on match.
234  */
235 int
match_user(const char * user,const char * host,const char * ipaddr,const char * pattern)236 match_user(const char *user, const char *host, const char *ipaddr,
237     const char *pattern)
238 {
239 	char *p, *pat;
240 	int ret;
241 
242 	/* test mode */
243 	if (user == NULL && host == NULL && ipaddr == NULL) {
244 		if ((p = strchr(pattern, '@')) != NULL &&
245 		    match_host_and_ip(NULL, NULL, p + 1) < 0)
246 			return -1;
247 		return 0;
248 	}
249 
250 	if ((p = strchr(pattern, '@')) == NULL)
251 		return match_pattern(user, pattern);
252 
253 	pat = xstrdup(pattern);
254 	p = strchr(pat, '@');
255 	*p++ = '\0';
256 
257 	if ((ret = match_pattern(user, pat)) == 1)
258 		ret = match_host_and_ip(host, ipaddr, p);
259 	free(pat);
260 
261 	return ret;
262 }
263 
264 /*
265  * Returns first item from client-list that is also supported by server-list,
266  * caller must free the returned string.
267  */
268 #define	MAX_PROP	40
269 #define	SEP	","
270 char *
match_list(const char * client,const char * server,u_int * next)271 match_list(const char *client, const char *server, u_int *next)
272 {
273 	char *sproposals[MAX_PROP];
274 	char *c, *s, *p, *ret, *cp, *sp;
275 	int i, j, nproposals;
276 
277 	c = cp = xstrdup(client);
278 	s = sp = xstrdup(server);
279 
280 	for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
281 	    (p = strsep(&sp, SEP)), i++) {
282 		if (i < MAX_PROP)
283 			sproposals[i] = p;
284 		else
285 			break;
286 	}
287 	nproposals = i;
288 
289 	for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
290 	    (p = strsep(&cp, SEP)), i++) {
291 		for (j = 0; j < nproposals; j++) {
292 			if (strcmp(p, sproposals[j]) == 0) {
293 				ret = xstrdup(p);
294 				if (next != NULL)
295 					*next = (cp == NULL) ?
296 					    strlen(c) : (u_int)(cp - c);
297 				free(c);
298 				free(s);
299 				return ret;
300 			}
301 		}
302 	}
303 	if (next != NULL)
304 		*next = strlen(c);
305 	free(c);
306 	free(s);
307 	return NULL;
308 }
309 
310 /*
311  * Filter proposal using pattern-list filter.
312  * "blacklist" determines sense of filter:
313  * non-zero indicates that items matching filter should be excluded.
314  * zero indicates that only items matching filter should be included.
315  * returns NULL on allocation error, otherwise caller must free result.
316  */
317 static char *
filter_list(const char * proposal,const char * filter,int blacklist)318 filter_list(const char *proposal, const char *filter, int blacklist)
319 {
320 	size_t len = strlen(proposal) + 1;
321 	char *fix_prop = malloc(len);
322 	char *orig_prop = strdup(proposal);
323 	char *cp, *tmp;
324 	int r;
325 
326 	if (fix_prop == NULL || orig_prop == NULL) {
327 		free(orig_prop);
328 		free(fix_prop);
329 		return NULL;
330 	}
331 
332 	tmp = orig_prop;
333 	*fix_prop = '\0';
334 	while ((cp = strsep(&tmp, ",")) != NULL) {
335 		r = match_pattern_list(cp, filter, 0);
336 		if ((blacklist && r != 1) || (!blacklist && r == 1)) {
337 			if (*fix_prop != '\0')
338 				strlcat(fix_prop, ",", len);
339 			strlcat(fix_prop, cp, len);
340 		}
341 	}
342 	free(orig_prop);
343 	return fix_prop;
344 }
345 
346 /*
347  * Filters a comma-separated list of strings, excluding any entry matching
348  * the 'filter' pattern list. Caller must free returned string.
349  */
350 char *
match_filter_blacklist(const char * proposal,const char * filter)351 match_filter_blacklist(const char *proposal, const char *filter)
352 {
353 	return filter_list(proposal, filter, 1);
354 }
355 
356 /*
357  * Filters a comma-separated list of strings, including only entries matching
358  * the 'filter' pattern list. Caller must free returned string.
359  */
360 char *
match_filter_whitelist(const char * proposal,const char * filter)361 match_filter_whitelist(const char *proposal, const char *filter)
362 {
363 	return filter_list(proposal, filter, 0);
364 }
365