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
53 int
match_pattern(const char * s,const char * pattern)54 match_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
118 int
match_pattern_list(const char * string,const char * pattern,u_int len,int dolower)119 match_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 */
178 int
match_hostname(const char * host,const char * pattern,u_int len)179 match_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 */
189 int
match_host_and_ip(const char * host,const char * ipaddr,const char * patterns)190 match_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 */
213 int
match_user(const char * user,const char * host,const char * ipaddr,const char * pattern)214 match_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 ","
240 char *
match_list(const char * client,const char * server,u_int * next)241 match_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