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