match.c revision 92555
157429Smarkm/* 257429Smarkm * Author: Tatu Ylonen <ylo@cs.hut.fi> 357429Smarkm * Copyright (c) 1995 Tatu Ylonen <ylo@cs.hut.fi>, Espoo, Finland 457429Smarkm * All rights reserved 557429Smarkm * Simple pattern matching, with '*' and '?' as wildcards. 660573Skris * 765668Skris * As far as I am concerned, the code I have written for this software 865668Skris * can be used freely for any purpose. Any derived versions of this 965668Skris * software must be clearly marked as such, and if the derived work is 1065668Skris * incompatible with the protocol description in the RFC file, it must be 1165668Skris * called by a name other than "ssh" or "Secure Shell". 1257429Smarkm */ 1376259Sgreen/* 1476259Sgreen * Copyright (c) 2000 Markus Friedl. All rights reserved. 1576259Sgreen * 1676259Sgreen * Redistribution and use in source and binary forms, with or without 1776259Sgreen * modification, are permitted provided that the following conditions 1876259Sgreen * are met: 1976259Sgreen * 1. Redistributions of source code must retain the above copyright 2076259Sgreen * notice, this list of conditions and the following disclaimer. 2176259Sgreen * 2. Redistributions in binary form must reproduce the above copyright 2276259Sgreen * notice, this list of conditions and the following disclaimer in the 2376259Sgreen * documentation and/or other materials provided with the distribution. 2476259Sgreen * 2576259Sgreen * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2676259Sgreen * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2776259Sgreen * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2876259Sgreen * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2976259Sgreen * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 3076259Sgreen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3176259Sgreen * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3276259Sgreen * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3376259Sgreen * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3476259Sgreen * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3576259Sgreen */ 3657429Smarkm 3757429Smarkm#include "includes.h" 3892555SdesRCSID("$OpenBSD: match.c,v 1.19 2002/03/01 13:12:10 markus Exp $"); 3957429Smarkm 4076259Sgreen#include "match.h" 4176259Sgreen#include "xmalloc.h" 4257429Smarkm 4357429Smarkm/* 4457429Smarkm * Returns true if the given string matches the pattern (which may contain ? 4557429Smarkm * and * as wildcards), and zero if it does not match. 4657429Smarkm */ 4757429Smarkm 4860573Skrisint 4957429Smarkmmatch_pattern(const char *s, const char *pattern) 5057429Smarkm{ 5157429Smarkm for (;;) { 5257429Smarkm /* If at end of pattern, accept if also at end of string. */ 5357429Smarkm if (!*pattern) 5457429Smarkm return !*s; 5557429Smarkm 5657429Smarkm if (*pattern == '*') { 5757429Smarkm /* Skip the asterisk. */ 5857429Smarkm pattern++; 5957429Smarkm 6057429Smarkm /* If at end of pattern, accept immediately. */ 6157429Smarkm if (!*pattern) 6257429Smarkm return 1; 6357429Smarkm 6457429Smarkm /* If next character in pattern is known, optimize. */ 6557429Smarkm if (*pattern != '?' && *pattern != '*') { 6657429Smarkm /* 6757429Smarkm * Look instances of the next character in 6857429Smarkm * pattern, and try to match starting from 6957429Smarkm * those. 7057429Smarkm */ 7157429Smarkm for (; *s; s++) 7257429Smarkm if (*s == *pattern && 7357429Smarkm match_pattern(s + 1, pattern + 1)) 7457429Smarkm return 1; 7557429Smarkm /* Failed. */ 7657429Smarkm return 0; 7757429Smarkm } 7857429Smarkm /* 7957429Smarkm * Move ahead one character at a time and try to 8057429Smarkm * match at each position. 8157429Smarkm */ 8257429Smarkm for (; *s; s++) 8357429Smarkm if (match_pattern(s, pattern)) 8457429Smarkm return 1; 8557429Smarkm /* Failed. */ 8657429Smarkm return 0; 8757429Smarkm } 8857429Smarkm /* 8957429Smarkm * There must be at least one more character in the string. 9057429Smarkm * If we are at the end, fail. 9157429Smarkm */ 9257429Smarkm if (!*s) 9357429Smarkm return 0; 9457429Smarkm 9557429Smarkm /* Check if the next character of the string is acceptable. */ 9657429Smarkm if (*pattern != '?' && *pattern != *s) 9757429Smarkm return 0; 9857429Smarkm 9957429Smarkm /* Move to the next character, both in string and in pattern. */ 10057429Smarkm s++; 10157429Smarkm pattern++; 10257429Smarkm } 10357429Smarkm /* NOTREACHED */ 10457429Smarkm} 10558582Skris 10658582Skris/* 10792555Sdes * Tries to match the string against the 10858582Skris * comma-separated sequence of subpatterns (each possibly preceded by ! to 10965668Skris * indicate negation). Returns -1 if negation matches, 1 if there is 11065668Skris * a positive match, 0 if there is no match at all. 11158582Skris */ 11258582Skris 11358582Skrisint 11492555Sdesmatch_pattern_list(const char *string, const char *pattern, u_int len, 11592555Sdes int dolower) 11658582Skris{ 11758582Skris char sub[1024]; 11858582Skris int negated; 11958582Skris int got_positive; 12076259Sgreen u_int i, subi; 12158582Skris 12258582Skris got_positive = 0; 12358582Skris for (i = 0; i < len;) { 12458582Skris /* Check if the subpattern is negated. */ 12558582Skris if (pattern[i] == '!') { 12658582Skris negated = 1; 12758582Skris i++; 12858582Skris } else 12958582Skris negated = 0; 13058582Skris 13158582Skris /* 13258582Skris * Extract the subpattern up to a comma or end. Convert the 13358582Skris * subpattern to lowercase. 13458582Skris */ 13558582Skris for (subi = 0; 13692555Sdes i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 13792555Sdes subi++, i++) 13892555Sdes sub[subi] = dolower && isupper(pattern[i]) ? 13992555Sdes tolower(pattern[i]) : pattern[i]; 14058582Skris /* If subpattern too long, return failure (no match). */ 14158582Skris if (subi >= sizeof(sub) - 1) 14258582Skris return 0; 14358582Skris 14458582Skris /* If the subpattern was terminated by a comma, skip the comma. */ 14558582Skris if (i < len && pattern[i] == ',') 14658582Skris i++; 14758582Skris 14858582Skris /* Null-terminate the subpattern. */ 14958582Skris sub[subi] = '\0'; 15058582Skris 15192555Sdes /* Try to match the subpattern against the string. */ 15292555Sdes if (match_pattern(string, sub)) { 15358582Skris if (negated) 15465668Skris return -1; /* Negative */ 15558582Skris else 15665668Skris got_positive = 1; /* Positive */ 15758582Skris } 15858582Skris } 15958582Skris 16058582Skris /* 16158582Skris * Return success if got a positive match. If there was a negative 16265668Skris * match, we have already returned -1 and never get here. 16358582Skris */ 16458582Skris return got_positive; 16558582Skris} 16676259Sgreen 16792555Sdes/* 16892555Sdes * Tries to match the host name (which must be in all lowercase) against the 16992555Sdes * comma-separated sequence of subpatterns (each possibly preceded by ! to 17092555Sdes * indicate negation). Returns -1 if negation matches, 1 if there is 17192555Sdes * a positive match, 0 if there is no match at all. 17292555Sdes */ 17392555Sdesint 17492555Sdesmatch_hostname(const char *host, const char *pattern, u_int len) 17592555Sdes{ 17692555Sdes return match_pattern_list(host, pattern, len, 1); 17792555Sdes} 17876259Sgreen 17992555Sdes/* 18092555Sdes * returns 0 if we get a negative match for the hostname or the ip 18192555Sdes * or if we get no match at all. returns 1 otherwise. 18292555Sdes */ 18392555Sdesint 18492555Sdesmatch_host_and_ip(const char *host, const char *ipaddr, 18592555Sdes const char *patterns) 18692555Sdes{ 18792555Sdes int mhost, mip; 18892555Sdes 18992555Sdes /* negative ipaddr match */ 19092555Sdes if ((mip = match_hostname(ipaddr, patterns, strlen(patterns))) == -1) 19192555Sdes return 0; 19292555Sdes /* negative hostname match */ 19392555Sdes if ((mhost = match_hostname(host, patterns, strlen(patterns))) == -1) 19492555Sdes return 0; 19592555Sdes /* no match at all */ 19692555Sdes if (mhost == 0 && mip == 0) 19792555Sdes return 0; 19892555Sdes return 1; 19992555Sdes} 20092555Sdes 20192555Sdes/* 20292555Sdes * match user, user@host_or_ip, user@host_or_ip_list against pattern 20392555Sdes */ 20492555Sdesint 20592555Sdesmatch_user(const char *user, const char *host, const char *ipaddr, 20692555Sdes const char *pattern) 20792555Sdes{ 20892555Sdes char *p, *pat; 20992555Sdes int ret; 21092555Sdes 21192555Sdes if ((p = strchr(pattern,'@')) == NULL) 21292555Sdes return match_pattern(user, pattern); 21392555Sdes 21492555Sdes pat = xstrdup(pattern); 21592555Sdes p = strchr(pat, '@'); 21692555Sdes *p++ = '\0'; 21792555Sdes 21892555Sdes if ((ret = match_pattern(user, pat)) == 1) 21992555Sdes ret = match_host_and_ip(host, ipaddr, p); 22092555Sdes xfree(pat); 22192555Sdes 22292555Sdes return ret; 22392555Sdes} 22492555Sdes 22592555Sdes/* 22692555Sdes * Returns first item from client-list that is also supported by server-list, 22792555Sdes * caller must xfree() returned string. 22892555Sdes */ 22992555Sdes#define MAX_PROP 40 23076259Sgreen#define SEP "," 23176259Sgreenchar * 23276259Sgreenmatch_list(const char *client, const char *server, u_int *next) 23376259Sgreen{ 23476259Sgreen char *sproposals[MAX_PROP]; 23576259Sgreen char *c, *s, *p, *ret, *cp, *sp; 23676259Sgreen int i, j, nproposals; 23776259Sgreen 23876259Sgreen c = cp = xstrdup(client); 23976259Sgreen s = sp = xstrdup(server); 24076259Sgreen 24176259Sgreen for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 24292555Sdes (p = strsep(&sp, SEP)), i++) { 24376259Sgreen if (i < MAX_PROP) 24476259Sgreen sproposals[i] = p; 24576259Sgreen else 24676259Sgreen break; 24776259Sgreen } 24876259Sgreen nproposals = i; 24976259Sgreen 25076259Sgreen for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 25192555Sdes (p = strsep(&cp, SEP)), i++) { 25276259Sgreen for (j = 0; j < nproposals; j++) { 25376259Sgreen if (strcmp(p, sproposals[j]) == 0) { 25476259Sgreen ret = xstrdup(p); 25576259Sgreen if (next != NULL) 25676259Sgreen *next = (cp == NULL) ? 25776259Sgreen strlen(c) : cp - c; 25876259Sgreen xfree(c); 25976259Sgreen xfree(s); 26076259Sgreen return ret; 26176259Sgreen } 26276259Sgreen } 26376259Sgreen } 26476259Sgreen if (next != NULL) 26576259Sgreen *next = strlen(c); 26676259Sgreen xfree(c); 26776259Sgreen xfree(s); 26876259Sgreen return NULL; 26976259Sgreen} 270