match.c revision 76259
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" 3876259SgreenRCSID("$OpenBSD: match.c,v 1.12 2001/03/10 17:51:04 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/* 10758582Skris * Tries to match the host name (which must be in all lowercase) 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 11476259Sgreenmatch_hostname(const char *host, const char *pattern, u_int len) 11558582Skris{ 11658582Skris char sub[1024]; 11758582Skris int negated; 11858582Skris int got_positive; 11976259Sgreen u_int i, subi; 12058582Skris 12158582Skris got_positive = 0; 12258582Skris for (i = 0; i < len;) { 12358582Skris /* Check if the subpattern is negated. */ 12458582Skris if (pattern[i] == '!') { 12558582Skris negated = 1; 12658582Skris i++; 12758582Skris } else 12858582Skris negated = 0; 12958582Skris 13058582Skris /* 13158582Skris * Extract the subpattern up to a comma or end. Convert the 13258582Skris * subpattern to lowercase. 13358582Skris */ 13458582Skris for (subi = 0; 13558582Skris i < len && subi < sizeof(sub) - 1 && pattern[i] != ','; 13658582Skris subi++, i++) 13758582Skris sub[subi] = isupper(pattern[i]) ? tolower(pattern[i]) : pattern[i]; 13858582Skris /* If subpattern too long, return failure (no match). */ 13958582Skris if (subi >= sizeof(sub) - 1) 14058582Skris return 0; 14158582Skris 14258582Skris /* If the subpattern was terminated by a comma, skip the comma. */ 14358582Skris if (i < len && pattern[i] == ',') 14458582Skris i++; 14558582Skris 14658582Skris /* Null-terminate the subpattern. */ 14758582Skris sub[subi] = '\0'; 14858582Skris 14958582Skris /* Try to match the subpattern against the host name. */ 15058582Skris if (match_pattern(host, sub)) { 15158582Skris if (negated) 15265668Skris return -1; /* Negative */ 15358582Skris else 15465668Skris got_positive = 1; /* Positive */ 15558582Skris } 15658582Skris } 15758582Skris 15858582Skris /* 15958582Skris * Return success if got a positive match. If there was a negative 16065668Skris * match, we have already returned -1 and never get here. 16158582Skris */ 16258582Skris return got_positive; 16358582Skris} 16476259Sgreen 16576259Sgreen 16676259Sgreen#define MAX_PROP 20 16776259Sgreen#define SEP "," 16876259Sgreenchar * 16976259Sgreenmatch_list(const char *client, const char *server, u_int *next) 17076259Sgreen{ 17176259Sgreen char *sproposals[MAX_PROP]; 17276259Sgreen char *c, *s, *p, *ret, *cp, *sp; 17376259Sgreen int i, j, nproposals; 17476259Sgreen 17576259Sgreen c = cp = xstrdup(client); 17676259Sgreen s = sp = xstrdup(server); 17776259Sgreen 17876259Sgreen for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0'; 17976259Sgreen (p = strsep(&sp, SEP)), i++) { 18076259Sgreen if (i < MAX_PROP) 18176259Sgreen sproposals[i] = p; 18276259Sgreen else 18376259Sgreen break; 18476259Sgreen } 18576259Sgreen nproposals = i; 18676259Sgreen 18776259Sgreen for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0'; 18876259Sgreen (p = strsep(&cp, SEP)), i++) { 18976259Sgreen for (j = 0; j < nproposals; j++) { 19076259Sgreen if (strcmp(p, sproposals[j]) == 0) { 19176259Sgreen ret = xstrdup(p); 19276259Sgreen if (next != NULL) 19376259Sgreen *next = (cp == NULL) ? 19476259Sgreen strlen(c) : cp - c; 19576259Sgreen xfree(c); 19676259Sgreen xfree(s); 19776259Sgreen return ret; 19876259Sgreen } 19976259Sgreen } 20076259Sgreen } 20176259Sgreen if (next != NULL) 20276259Sgreen *next = strlen(c); 20376259Sgreen xfree(c); 20476259Sgreen xfree(s); 20576259Sgreen return NULL; 20676259Sgreen} 207