1/* $OpenBSD: match.c,v 1.27 2008/06/10 23:06:19 djm 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 <string.h>
44
45#include "xmalloc.h"
46#include "match.h"
47
48/*
49 * Returns true if the given string matches the pattern (which may contain ?
50 * and * as wildcards), and zero if it does not match.
51 */
52
53int
54match_pattern(const char *s, const char *pattern)
55{
56	for (;;) {
57		/* If at end of pattern, accept if also at end of string. */
58		if (!*pattern)
59			return !*s;
60
61		if (*pattern == '*') {
62			/* Skip the asterisk. */
63			pattern++;
64
65			/* If at end of pattern, accept immediately. */
66			if (!*pattern)
67				return 1;
68
69			/* If next character in pattern is known, optimize. */
70			if (*pattern != '?' && *pattern != '*') {
71				/*
72				 * Look instances of the next character in
73				 * pattern, and try to match starting from
74				 * those.
75				 */
76				for (; *s; s++)
77					if (*s == *pattern &&
78					    match_pattern(s + 1, pattern + 1))
79						return 1;
80				/* Failed. */
81				return 0;
82			}
83			/*
84			 * Move ahead one character at a time and try to
85			 * match at each position.
86			 */
87			for (; *s; s++)
88				if (match_pattern(s, pattern))
89					return 1;
90			/* Failed. */
91			return 0;
92		}
93		/*
94		 * There must be at least one more character in the string.
95		 * If we are at the end, fail.
96		 */
97		if (!*s)
98			return 0;
99
100		/* Check if the next character of the string is acceptable. */
101		if (*pattern != '?' && *pattern != *s)
102			return 0;
103
104		/* Move to the next character, both in string and in pattern. */
105		s++;
106		pattern++;
107	}
108	/* NOTREACHED */
109}
110
111/*
112 * Tries to match the string against the
113 * comma-separated sequence of subpatterns (each possibly preceded by ! to
114 * indicate negation).  Returns -1 if negation matches, 1 if there is
115 * a positive match, 0 if there is no match at all.
116 */
117
118int
119match_pattern_list(const char *string, const char *pattern, u_int len,
120    int dolower)
121{
122	char sub[1024];
123	int negated;
124	int got_positive;
125	u_int i, subi;
126
127	got_positive = 0;
128	for (i = 0; i < len;) {
129		/* Check if the subpattern is negated. */
130		if (pattern[i] == '!') {
131			negated = 1;
132			i++;
133		} else
134			negated = 0;
135
136		/*
137		 * Extract the subpattern up to a comma or end.  Convert the
138		 * subpattern to lowercase.
139		 */
140		for (subi = 0;
141		    i < len && subi < sizeof(sub) - 1 && pattern[i] != ',';
142		    subi++, i++)
143			sub[subi] = dolower && isupper(pattern[i]) ?
144			    (char)tolower(pattern[i]) : pattern[i];
145		/* If subpattern too long, return failure (no match). */
146		if (subi >= sizeof(sub) - 1)
147			return 0;
148
149		/* If the subpattern was terminated by a comma, skip the comma. */
150		if (i < len && pattern[i] == ',')
151			i++;
152
153		/* Null-terminate the subpattern. */
154		sub[subi] = '\0';
155
156		/* Try to match the subpattern against the string. */
157		if (match_pattern(string, sub)) {
158			if (negated)
159				return -1;		/* Negative */
160			else
161				got_positive = 1;	/* Positive */
162		}
163	}
164
165	/*
166	 * Return success if got a positive match.  If there was a negative
167	 * match, we have already returned -1 and never get here.
168	 */
169	return got_positive;
170}
171
172/*
173 * Tries to match the host name (which must be in all lowercase) against the
174 * comma-separated sequence of subpatterns (each possibly preceded by ! to
175 * indicate negation).  Returns -1 if negation matches, 1 if there is
176 * a positive match, 0 if there is no match at all.
177 */
178int
179match_hostname(const char *host, const char *pattern, u_int len)
180{
181	return match_pattern_list(host, pattern, len, 1);
182}
183
184/*
185 * returns 0 if we get a negative match for the hostname or the ip
186 * or if we get no match at all.  returns -1 on error, or 1 on
187 * successful match.
188 */
189int
190match_host_and_ip(const char *host, const char *ipaddr,
191    const char *patterns)
192{
193	int mhost, mip;
194
195	/* error in ipaddr match */
196	if ((mip = addr_match_list(ipaddr, patterns)) == -2)
197		return -1;
198	else if (mip == -1) /* negative ip address match */
199		return 0;
200
201	/* negative hostname match */
202	if ((mhost = match_hostname(host, patterns, strlen(patterns))) == -1)
203		return 0;
204	/* no match at all */
205	if (mhost == 0 && mip == 0)
206		return 0;
207	return 1;
208}
209
210/*
211 * match user, user@host_or_ip, user@host_or_ip_list against pattern
212 */
213int
214match_user(const char *user, const char *host, const char *ipaddr,
215    const char *pattern)
216{
217	char *p, *pat;
218	int ret;
219
220	if ((p = strchr(pattern,'@')) == NULL)
221		return match_pattern(user, pattern);
222
223	pat = xstrdup(pattern);
224	p = strchr(pat, '@');
225	*p++ = '\0';
226
227	if ((ret = match_pattern(user, pat)) == 1)
228		ret = match_host_and_ip(host, ipaddr, p);
229	xfree(pat);
230
231	return ret;
232}
233
234/*
235 * Returns first item from client-list that is also supported by server-list,
236 * caller must xfree() returned string.
237 */
238#define	MAX_PROP	40
239#define	SEP	","
240char *
241match_list(const char *client, const char *server, u_int *next)
242{
243	char *sproposals[MAX_PROP];
244	char *c, *s, *p, *ret, *cp, *sp;
245	int i, j, nproposals;
246
247	c = cp = xstrdup(client);
248	s = sp = xstrdup(server);
249
250	for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
251	    (p = strsep(&sp, SEP)), i++) {
252		if (i < MAX_PROP)
253			sproposals[i] = p;
254		else
255			break;
256	}
257	nproposals = i;
258
259	for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
260	    (p = strsep(&cp, SEP)), i++) {
261		for (j = 0; j < nproposals; j++) {
262			if (strcmp(p, sproposals[j]) == 0) {
263				ret = xstrdup(p);
264				if (next != NULL)
265					*next = (cp == NULL) ?
266					    strlen(c) : (u_int)(cp - c);
267				xfree(c);
268				xfree(s);
269				return ret;
270			}
271		}
272	}
273	if (next != NULL)
274		*next = strlen(c);
275	xfree(c);
276	xfree(s);
277	return NULL;
278}
279