match.c revision 181111
1181111Sdes/* $OpenBSD: match.c,v 1.27 2008/06/10 23:06:19 djm Exp $ */ 257429Smarkm/* 357429Smarkm * Author: Tatu Ylonen <ylo@cs.hut.fi> 457429Smarkm * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland 557429Smarkm * All rights reserved 657429Smarkm * Simple pattern matching, with '*' and '?' as wildcards. 760573Skris * 865668Skris * As far as I am concerned, the code I have written for this software 965668Skris * can be used freely for any purpose. Any derived versions of this 1065668Skris * software must be clearly marked as such, and if the derived work is 1165668Skris * incompatible with the protocol description in the RFC file, it must be 1265668Skris * called by a name other than "ssh" or "Secure Shell". 1357429Smarkm */ 1476259Sgreen/* 1576259Sgreen * Copyright (c) 2000 Markus Friedl. All rights reserved. 1676259Sgreen * 1776259Sgreen * Redistribution and use in source and binary forms, with or without 1876259Sgreen * modification, are permitted provided that the following conditions 1976259Sgreen * are met: 2076259Sgreen * 1. Redistributions of source code must retain the above copyright 2176259Sgreen * notice, this list of conditions and the following disclaimer. 2276259Sgreen * 2. Redistributions in binary form must reproduce the above copyright 2376259Sgreen * notice, this list of conditions and the following disclaimer in the 2476259Sgreen * documentation and/or other materials provided with the distribution. 2576259Sgreen * 2676259Sgreen * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2776259Sgreen * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2876259Sgreen * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2976259Sgreen * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 3076259Sgreen * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 3176259Sgreen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3276259Sgreen * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3376259Sgreen * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3476259Sgreen * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3576259Sgreen * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3676259Sgreen */ 3757429Smarkm 3857429Smarkm#include "includes.h" 3957429Smarkm 40162852Sdes#include <sys/types.h> 41162852Sdes 42162852Sdes#include <ctype.h> 43162852Sdes#include <string.h> 44162852Sdes 45162852Sdes#include "xmalloc.h" 4676259Sgreen#include "match.h" 4757429Smarkm 4857429Smarkm/* 4957429Smarkm * Returns true if the given string matches the pattern (which may contain ? 5057429Smarkm * and * as wildcards), and zero if it does not match. 5157429Smarkm */ 5257429Smarkm 5360573Skrisint 5457429Smarkmmatch_pattern(const char *s, const char *pattern) 5557429Smarkm{ 5657429Smarkm for (;;) { 5757429Smarkm /* If at end of pattern, accept if also at end of string. */ 5857429Smarkm if (!*pattern) 5957429Smarkm return !*s; 6057429Smarkm 6157429Smarkm if (*pattern == '*') { 6257429Smarkm /* Skip the asterisk. */ 6357429Smarkm pattern++; 6457429Smarkm 6557429Smarkm /* If at end of pattern, accept immediately. */ 6657429Smarkm if (!*pattern) 6757429Smarkm return 1; 6857429Smarkm 6957429Smarkm /* If next character in pattern is known, optimize. */ 7057429Smarkm if (*pattern != '?' && *pattern != '*') { 7157429Smarkm /* 7257429Smarkm * Look instances of the next character in 7357429Smarkm * pattern, and try to match starting from 7457429Smarkm * those. 7557429Smarkm */ 7657429Smarkm for (; *s; s++) 7757429Smarkm if (*s == *pattern && 7857429Smarkm match_pattern(s + 1, pattern + 1)) 7957429Smarkm return 1; 8057429Smarkm /* Failed. */ 8157429Smarkm return 0; 8257429Smarkm } 8357429Smarkm /* 8457429Smarkm * Move ahead one character at a time and try to 8557429Smarkm * match at each position. 8657429Smarkm */ 8757429Smarkm for (; *s; s++) 8857429Smarkm if (match_pattern(s, pattern)) 8957429Smarkm return 1; 9057429Smarkm /* Failed. */ 9157429Smarkm return 0; 9257429Smarkm } 9357429Smarkm /* 9457429Smarkm * There must be at least one more character in the string. 9557429Smarkm * If we are at the end, fail. 9657429Smarkm */ 9757429Smarkm if (!*s) 9857429Smarkm return 0; 9957429Smarkm 10057429Smarkm /* Check if the next character of the string is acceptable. */ 10157429Smarkm if (*pattern != '?' && *pattern != *s) 10257429Smarkm return 0; 10357429Smarkm 10457429Smarkm /* Move to the next character, both in string and in pattern. */ 10557429Smarkm s++; 10657429Smarkm pattern++; 10757429Smarkm } 10857429Smarkm /* NOTREACHED */ 10957429Smarkm} 11058582Skris 11158582Skris/* 11292555Sdes * Tries to match the string against the 11358582Skris * comma-separated sequence of subpatterns (each possibly preceded by ! to 11465668Skris * indicate negation). Returns -1 if negation matches, 1 if there is 11565668Skris * a positive match, 0 if there is no match at all. 11658582Skris */ 11758582Skris 11858582Skrisint 11992555Sdesmatch_pattern_list(const char *string, const char *pattern, u_int len, 12092555Sdes int dolower) 12158582Skris{ 12258582Skris char sub[1024]; 12358582Skris int negated; 12458582Skris int got_positive; 12576259Sgreen u_int i, subi; 12658582Skris 12758582Skris got_positive = 0; 12858582Skris for (i = 0; i < len;) { 12958582Skris /* Check if the subpattern is negated. */ 13058582Skris if (pattern[i] == '!') { 13158582Skris negated = 1; 13258582Skris i++; 13358582Skris } else 13458582Skris negated = 0; 13558582Skris 13658582Skris /* 13758582Skris * Extract the subpattern up to a comma or end. Convert the 13858582Skris * subpattern to lowercase. 13958582Skris */ 14058582Skris for (subi = 0; 14192555Sdes i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 14292555Sdes subi++, i++) 14392555Sdes sub[subi] = dolower && isupper(pattern[i]) ? 144162852Sdes (char)tolower(pattern[i]) : pattern[i]; 14558582Skris /* If subpattern too long, return failure (no match). */ 14658582Skris if (subi >= sizeof(sub) - 1) 14758582Skris return 0; 14858582Skris 14958582Skris /* If the subpattern was terminated by a comma, skip the comma. */ 15058582Skris if (i < len && pattern[i] == ',') 15158582Skris i++; 15258582Skris 15358582Skris /* Null-terminate the subpattern. */ 15458582Skris sub[subi] = '\0'; 15558582Skris 15692555Sdes /* Try to match the subpattern against the string. */ 15792555Sdes if (match_pattern(string, sub)) { 15858582Skris if (negated) 15965668Skris return -1; /* Negative */ 16058582Skris else 16165668Skris got_positive = 1; /* Positive */ 16258582Skris } 16358582Skris } 16458582Skris 16558582Skris /* 16658582Skris * Return success if got a positive match. If there was a negative 16765668Skris * match, we have already returned -1 and never get here. 16858582Skris */ 16958582Skris return got_positive; 17058582Skris} 17176259Sgreen 17292555Sdes/* 17392555Sdes * Tries to match the host name (which must be in all lowercase) against the 17492555Sdes * comma-separated sequence of subpatterns (each possibly preceded by ! to 17592555Sdes * indicate negation). Returns -1 if negation matches, 1 if there is 17692555Sdes * a positive match, 0 if there is no match at all. 17792555Sdes */ 17892555Sdesint 17992555Sdesmatch_hostname(const char *host, const char *pattern, u_int len) 18092555Sdes{ 18192555Sdes return match_pattern_list(host, pattern, len, 1); 18292555Sdes} 18376259Sgreen 18492555Sdes/* 18592555Sdes * returns 0 if we get a negative match for the hostname or the ip 186181111Sdes * or if we get no match at all. returns -1 on error, or 1 on 187181111Sdes * successful match. 18892555Sdes */ 18992555Sdesint 19092555Sdesmatch_host_and_ip(const char *host, const char *ipaddr, 19192555Sdes const char *patterns) 19292555Sdes{ 19392555Sdes int mhost, mip; 19492555Sdes 195181111Sdes /* error in ipaddr match */ 196181111Sdes if ((mip = addr_match_list(ipaddr, patterns)) == -2) 197181111Sdes return -1; 198181111Sdes else if (mip == -1) /* negative ip address match */ 19992555Sdes return 0; 200181111Sdes 20192555Sdes /* negative hostname match */ 20292555Sdes if ((mhost = match_hostname(host, patterns, strlen(patterns))) == -1) 20392555Sdes return 0; 20492555Sdes /* no match at all */ 20592555Sdes if (mhost == 0 && mip == 0) 20692555Sdes return 0; 20792555Sdes return 1; 20892555Sdes} 20992555Sdes 21092555Sdes/* 21192555Sdes * match user, user@host_or_ip, user@host_or_ip_list against pattern 21292555Sdes */ 21392555Sdesint 21492555Sdesmatch_user(const char *user, const char *host, const char *ipaddr, 21592555Sdes const char *pattern) 21692555Sdes{ 21792555Sdes char *p, *pat; 21892555Sdes int ret; 21992555Sdes 22092555Sdes if ((p = strchr(pattern,'@')) == NULL) 22192555Sdes return match_pattern(user, pattern); 22292555Sdes 22392555Sdes pat = xstrdup(pattern); 22492555Sdes p = strchr(pat, '@'); 22592555Sdes *p++ = '\0'; 22692555Sdes 22792555Sdes if ((ret = match_pattern(user, pat)) == 1) 22892555Sdes ret = match_host_and_ip(host, ipaddr, p); 22992555Sdes xfree(pat); 23092555Sdes 23192555Sdes return ret; 23292555Sdes} 23392555Sdes 23492555Sdes/* 23592555Sdes * Returns first item from client-list that is also supported by server-list, 23692555Sdes * caller must xfree() returned string. 23792555Sdes */ 23892555Sdes#define MAX_PROP 40 23976259Sgreen#define SEP "," 24076259Sgreenchar * 24176259Sgreenmatch_list(const char *client, const char *server, u_int *next) 24276259Sgreen{ 24376259Sgreen char *sproposals[MAX_PROP]; 24476259Sgreen char *c, *s, *p, *ret, *cp, *sp; 24576259Sgreen int i, j, nproposals; 24676259Sgreen 24776259Sgreen c = cp = xstrdup(client); 24876259Sgreen s = sp = xstrdup(server); 24976259Sgreen 25076259Sgreen for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 25192555Sdes (p = strsep(&sp, SEP)), i++) { 25276259Sgreen if (i < MAX_PROP) 25376259Sgreen sproposals[i] = p; 25476259Sgreen else 25576259Sgreen break; 25676259Sgreen } 25776259Sgreen nproposals = i; 25876259Sgreen 25976259Sgreen for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 26092555Sdes (p = strsep(&cp, SEP)), i++) { 26176259Sgreen for (j = 0; j < nproposals; j++) { 26276259Sgreen if (strcmp(p, sproposals[j]) == 0) { 26376259Sgreen ret = xstrdup(p); 26476259Sgreen if (next != NULL) 26576259Sgreen *next = (cp == NULL) ? 266149749Sdes strlen(c) : (u_int)(cp - c); 26776259Sgreen xfree(c); 26876259Sgreen xfree(s); 26976259Sgreen return ret; 27076259Sgreen } 27176259Sgreen } 27276259Sgreen } 27376259Sgreen if (next != NULL) 27476259Sgreen *next = strlen(c); 27576259Sgreen xfree(c); 27676259Sgreen xfree(s); 27776259Sgreen return NULL; 27876259Sgreen} 279