match.c revision 181111
1214571Sdim/* $OpenBSD: match.c,v 1.27 2008/06/10 23:06:19 djm Exp $ */ 2214571Sdim/* 3214571Sdim * Author: Tatu Ylonen <ylo@cs.hut.fi> 4214571Sdim * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland 5214571Sdim * All rights reserved 6214571Sdim * Simple pattern matching, with '*' and '?' as wildcards. 7214571Sdim * 8214571Sdim * As far as I am concerned, the code I have written for this software 9214571Sdim * can be used freely for any purpose. Any derived versions of this 10214571Sdim * software must be clearly marked as such, and if the derived work is 11214571Sdim * incompatible with the protocol description in the RFC file, it must be 12214571Sdim * called by a name other than "ssh" or "Secure Shell". 13214571Sdim */ 14214571Sdim/* 15214571Sdim * Copyright (c) 2000 Markus Friedl. All rights reserved. 16214571Sdim * 17214571Sdim * Redistribution and use in source and binary forms, with or without 18214571Sdim * modification, are permitted provided that the following conditions 19214571Sdim * are met: 20214571Sdim * 1. Redistributions of source code must retain the above copyright 21214571Sdim * notice, this list of conditions and the following disclaimer. 22214571Sdim * 2. Redistributions in binary form must reproduce the above copyright 23214571Sdim * notice, this list of conditions and the following disclaimer in the 24214571Sdim * documentation and/or other materials provided with the distribution. 25214571Sdim * 26214571Sdim * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 27214571Sdim * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 28214571Sdim * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 29214571Sdim * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 30214571Sdim * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 31214571Sdim * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32214571Sdim * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33214571Sdim * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34214571Sdim * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 35214571Sdim * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36214571Sdim */ 37214571Sdim 38214571Sdim#include "includes.h" 39214571Sdim 40214571Sdim#include <sys/types.h> 41214571Sdim 42214571Sdim#include <ctype.h> 43214571Sdim#include <string.h> 44214571Sdim 45214571Sdim#include "xmalloc.h" 46214571Sdim#include "match.h" 47214571Sdim 48214571Sdim/* 49214571Sdim * Returns true if the given string matches the pattern (which may contain ? 50214571Sdim * and * as wildcards), and zero if it does not match. 51214571Sdim */ 52214571Sdim 53214571Sdimint 54214571Sdimmatch_pattern(const char *s, const char *pattern) 55214571Sdim{ 56214571Sdim for (;;) { 57214571Sdim /* If at end of pattern, accept if also at end of string. */ 58214571Sdim if (!*pattern) 59214571Sdim return !*s; 60214571Sdim 61214571Sdim if (*pattern == '*') { 62214571Sdim /* Skip the asterisk. */ 63214571Sdim pattern++; 64214571Sdim 65214571Sdim /* If at end of pattern, accept immediately. */ 66214571Sdim if (!*pattern) 67214571Sdim return 1; 68214571Sdim 69214571Sdim /* If next character in pattern is known, optimize. */ 70214571Sdim if (*pattern != '?' && *pattern != '*') { 71214571Sdim /* 72214571Sdim * Look instances of the next character in 73214571Sdim * pattern, and try to match starting from 74214571Sdim * those. 75214571Sdim */ 76214571Sdim for (; *s; s++) 77214571Sdim if (*s == *pattern && 78214571Sdim match_pattern(s + 1, pattern + 1)) 79214571Sdim return 1; 80214571Sdim /* Failed. */ 81214571Sdim return 0; 82214571Sdim } 83214571Sdim /* 84214571Sdim * Move ahead one character at a time and try to 85214571Sdim * match at each position. 86214571Sdim */ 87214571Sdim for (; *s; s++) 88214571Sdim if (match_pattern(s, pattern)) 89214571Sdim return 1; 90214571Sdim /* Failed. */ 91214571Sdim return 0; 92214571Sdim } 93214571Sdim /* 94214571Sdim * There must be at least one more character in the string. 95214571Sdim * If we are at the end, fail. 96214571Sdim */ 97214571Sdim if (!*s) 98214571Sdim return 0; 99214571Sdim 100214571Sdim /* Check if the next character of the string is acceptable. */ 101214571Sdim if (*pattern != '?' && *pattern != *s) 102214571Sdim return 0; 103214571Sdim 104214571Sdim /* Move to the next character, both in string and in pattern. */ 105214571Sdim s++; 106214571Sdim pattern++; 107214571Sdim } 108214571Sdim /* NOTREACHED */ 109214571Sdim} 110214571Sdim 111214571Sdim/* 112214571Sdim * Tries to match the string against the 113214571Sdim * comma-separated sequence of subpatterns (each possibly preceded by ! to 114214571Sdim * indicate negation). Returns -1 if negation matches, 1 if there is 115214571Sdim * a positive match, 0 if there is no match at all. 116214571Sdim */ 117214571Sdim 118214571Sdimint 119214571Sdimmatch_pattern_list(const char *string, const char *pattern, u_int len, 120214571Sdim int dolower) 121214571Sdim{ 122214571Sdim char sub[1024]; 123214571Sdim int negated; 124214571Sdim int got_positive; 125214571Sdim u_int i, subi; 126214571Sdim 127214571Sdim got_positive = 0; 128214571Sdim for (i = 0; i < len;) { 129214571Sdim /* Check if the subpattern is negated. */ 130214571Sdim if (pattern[i] == '!') { 131214571Sdim negated = 1; 132214571Sdim i++; 133214571Sdim } else 134214571Sdim negated = 0; 135214571Sdim 136214571Sdim /* 137214571Sdim * Extract the subpattern up to a comma or end. Convert the 138214571Sdim * subpattern to lowercase. 139214571Sdim */ 140214571Sdim for (subi = 0; 141214571Sdim i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 142214571Sdim subi++, i++) 143214571Sdim sub[subi] = dolower && isupper(pattern[i]) ? 144214571Sdim (char)tolower(pattern[i]) : pattern[i]; 145214571Sdim /* If subpattern too long, return failure (no match). */ 146214571Sdim if (subi >= sizeof(sub) - 1) 147214571Sdim return 0; 148214571Sdim 149214571Sdim /* If the subpattern was terminated by a comma, skip the comma. */ 150214571Sdim if (i < len && pattern[i] == ',') 151214571Sdim i++; 152214571Sdim 153214571Sdim /* Null-terminate the subpattern. */ 154214571Sdim sub[subi] = '\0'; 155214571Sdim 156214571Sdim /* Try to match the subpattern against the string. */ 157214571Sdim if (match_pattern(string, sub)) { 158214571Sdim if (negated) 159214571Sdim return -1; /* Negative */ 160214571Sdim else 161214571Sdim got_positive = 1; /* Positive */ 162214571Sdim } 163214571Sdim } 164214571Sdim 165214571Sdim /* 166214571Sdim * Return success if got a positive match. If there was a negative 167214571Sdim * match, we have already returned -1 and never get here. 168214571Sdim */ 169214571Sdim return got_positive; 170214571Sdim} 171214571Sdim 172214571Sdim/* 173214571Sdim * Tries to match the host name (which must be in all lowercase) against the 174214571Sdim * comma-separated sequence of subpatterns (each possibly preceded by ! to 175214571Sdim * indicate negation). Returns -1 if negation matches, 1 if there is 176214571Sdim * a positive match, 0 if there is no match at all. 177214571Sdim */ 178214571Sdimint 179214571Sdimmatch_hostname(const char *host, const char *pattern, u_int len) 180214571Sdim{ 181214571Sdim return match_pattern_list(host, pattern, len, 1); 182214571Sdim} 183214571Sdim 184214571Sdim/* 185214571Sdim * returns 0 if we get a negative match for the hostname or the ip 186214571Sdim * or if we get no match at all. returns -1 on error, or 1 on 187214571Sdim * successful match. 188214571Sdim */ 189214571Sdimint 190214571Sdimmatch_host_and_ip(const char *host, const char *ipaddr, 191214571Sdim const char *patterns) 192214571Sdim{ 193214571Sdim int mhost, mip; 194214571Sdim 195214571Sdim /* error in ipaddr match */ 196214571Sdim if ((mip = addr_match_list(ipaddr, patterns)) == -2) 197214571Sdim return -1; 198214571Sdim else if (mip == -1) /* negative ip address match */ 199214571Sdim return 0; 200214571Sdim 201214571Sdim /* negative hostname match */ 202214571Sdim if ((mhost = match_hostname(host, patterns, strlen(patterns))) == -1) 203214571Sdim return 0; 204214571Sdim /* no match at all */ 205214571Sdim if (mhost == 0 && mip == 0) 206214571Sdim return 0; 207214571Sdim return 1; 208214571Sdim} 209214571Sdim 210214571Sdim/* 211214571Sdim * match user, user@host_or_ip, user@host_or_ip_list against pattern 212214571Sdim */ 213214571Sdimint 214214571Sdimmatch_user(const char *user, const char *host, const char *ipaddr, 215214571Sdim const char *pattern) 216214571Sdim{ 217214571Sdim char *p, *pat; 218214571Sdim int ret; 219214571Sdim 220214571Sdim if ((p = strchr(pattern,'@')) == NULL) 221214571Sdim return match_pattern(user, pattern); 222214571Sdim 223214571Sdim pat = xstrdup(pattern); 224214571Sdim p = strchr(pat, '@'); 225214571Sdim *p++ = '\0'; 226214571Sdim 227214571Sdim if ((ret = match_pattern(user, pat)) == 1) 228214571Sdim ret = match_host_and_ip(host, ipaddr, p); 229214571Sdim xfree(pat); 230214571Sdim 231214571Sdim return ret; 232214571Sdim} 233214571Sdim 234214571Sdim/* 235214571Sdim * Returns first item from client-list that is also supported by server-list, 236214571Sdim * caller must xfree() returned string. 237214571Sdim */ 238214571Sdim#define MAX_PROP 40 239214571Sdim#define SEP "," 240214571Sdimchar * 241214571Sdimmatch_list(const char *client, const char *server, u_int *next) 242214571Sdim{ 243214571Sdim char *sproposals[MAX_PROP]; 244214571Sdim char *c, *s, *p, *ret, *cp, *sp; 245214571Sdim int i, j, nproposals; 246214571Sdim 247214571Sdim c = cp = xstrdup(client); 248214571Sdim s = sp = xstrdup(server); 249214571Sdim 250214571Sdim for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 251214571Sdim (p = strsep(&sp, SEP)), i++) { 252214571Sdim if (i < MAX_PROP) 253214571Sdim sproposals[i] = p; 254214571Sdim else 255214571Sdim break; 256214571Sdim } 257214571Sdim nproposals = i; 258214571Sdim 259214571Sdim for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 260214571Sdim (p = strsep(&cp, SEP)), i++) { 261214571Sdim for (j = 0; j < nproposals; j++) { 262214571Sdim if (strcmp(p, sproposals[j]) == 0) { 263214571Sdim ret = xstrdup(p); 264214571Sdim if (next != NULL) 265214571Sdim *next = (cp == NULL) ? 266214571Sdim strlen(c) : (u_int)(cp - c); 267214571Sdim xfree(c); 268214571Sdim xfree(s); 269214571Sdim return ret; 270214571Sdim } 271214571Sdim } 272214571Sdim } 273214571Sdim if (next != NULL) 274214571Sdim *next = strlen(c); 275214571Sdim xfree(c); 276214571Sdim xfree(s); 277214571Sdim return NULL; 278214571Sdim} 279214571Sdim