Evaluate filters according to the three-valued logic of X.511, as required

by RFC 4511. A filter term can now be evaluated as undefined if the
attribute description is not recognized, the attribute type doesn't define
the appropriate matching rule, or the filtering is not implemented.

This also implements the NOT filter in the query planner.

3 files changed, 162 insertions, 101 deletions

diff --git a/usr.sbin/ldapd/filter.c b/usr.sbin/ldapd/filter.c
index 7725ca9cdf1..49d942c4a8d 100644
--- a/usr.sbin/ldapd/filter.c
+++ b/usr.sbin/ldapd/filter.c
@@ -1,7 +1,7 @@
-/*	$OpenBSD: filter.c,v 1.1 2010/05/31 17:36:31 martinh Exp $ */
+/*	$OpenBSD: filter.c,v 1.2 2010/11/03 10:33:17 martinh Exp $ */
 
 /*
- * Copyright (c) 2009 Martin Hedenfalk <martin@bzero.se>
+ * Copyright (c) 2009, 2010 Martin Hedenfalk <martinh@openbsd.org>
  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
@@ -24,29 +24,24 @@
 
 #include "ldapd.h"
 
-static int		 ldap_filt_eq(struct ber_element *root,
-				struct ber_element *filter);
-static int		 ldap_filt_subs(struct ber_element *root,
-				struct ber_element *filter);
-static int		 ldap_filt_and(struct ber_element *root,
-				struct ber_element *filter);
-static int		 ldap_filt_or(struct ber_element *root,
-				struct ber_element *filter);
-static int		 ldap_filt_not(struct ber_element *root,
-				struct ber_element *filter);
+static int	 ldap_filt_eq(struct ber_element *root, struct plan *plan);
+static int	 ldap_filt_subs(struct ber_element *root, struct plan *plan);
+static int	 ldap_filt_and(struct ber_element *root, struct plan *plan);
+static int	 ldap_filt_or(struct ber_element *root, struct plan *plan);
+static int	 ldap_filt_not(struct ber_element *root, struct plan *plan);
 
 static int
-ldap_filt_eq(struct ber_element *root, struct ber_element *filter)
+ldap_filt_eq(struct ber_element *root, struct plan *plan)
 {
-	const char		*key, *cmp;
+	char			*vs;
 	struct ber_element	*a, *vals, *v;
 
-	if (ber_scanf_elements(filter, "{ss", &key, &cmp) != 0)
-		return -1;
-
-	a = ldap_get_attribute(root, key);
+	if (plan->adesc != NULL)
+		a = ldap_get_attribute(root, plan->adesc);
+	else
+		a = ldap_find_attribute(root, plan->at);
 	if (a == NULL) {
-		log_debug("no attribute [%s] found", key);
+		log_debug("no attribute [%s] found", plan->adesc ?: ATTR_NAME(plan->at));
 		return -1;
 	}
 
@@ -55,10 +50,9 @@ ldap_filt_eq(struct ber_element *root, struct ber_element *filter)
 		return -1;
 
 	for (v = vals->be_sub; v; v = v->be_next) {
-		char *vs;
 		if (ber_get_string(v, &vs) != 0)
 			continue;
-		if (strcasecmp(cmp, vs) == 0)
+		if (strcasecmp(plan->assert.value, vs) == 0)
 			return 0;
 	}
 
@@ -115,17 +109,19 @@ ldap_filt_subs_value(struct ber_element *v, struct ber_element *sub)
 }
 
 static int
-ldap_filt_subs(struct ber_element *root, struct ber_element *filter)
+ldap_filt_subs(struct ber_element *root, struct plan *plan)
 {
-	const char		*key, *attr;
-	struct ber_element	*sub, *a, *v;
+	const char		*attr;
+	struct ber_element	*a, *v;
 
-	if (ber_scanf_elements(filter, "{s{e", &key, &sub) != 0)
+	if (plan->adesc != NULL)
+		a = ldap_get_attribute(root, plan->adesc);
+	else
+		a = ldap_find_attribute(root, plan->at);
+	if (a == NULL) {
+		log_debug("no attribute [%s] found", plan->adesc ?: ATTR_NAME(plan->at));
 		return -1;
-
-	a = ldap_get_attribute(root, key);
-	if (a == NULL)
-		return -1; /* attribute not found, false or undefined? */
+	}
 
 	if (ber_scanf_elements(a, "s(e", &attr, &v) != 0)
 		return -1; /* internal failure, false or undefined? */
@@ -134,7 +130,7 @@ ldap_filt_subs(struct ber_element *root, struct ber_element *filter)
 	 */
 	for (; v; v = v->be_next) {
 		/* All substrings must match. */
-		switch (ldap_filt_subs_value(v, sub)) {
+		switch (ldap_filt_subs_value(v, plan->assert.substring)) {
 		case 0:
 			return 0;
 		case -1:
@@ -149,104 +145,80 @@ ldap_filt_subs(struct ber_element *root, struct ber_element *filter)
 }
 
 static int
-ldap_filt_and(struct ber_element *root, struct ber_element *filter)
+ldap_filt_and(struct ber_element *root, struct plan *plan)
 {
-	struct ber_element	*elm;
-
-	if (ber_scanf_elements(filter, "{e", &elm) != 0)
-		return -1;
+	struct plan	*arg;
 
-	for (; elm; elm = elm->be_next) {
-		if (ldap_matches_filter(root, elm) != 0)
+	TAILQ_FOREACH(arg, &plan->args, next)
+		if (ldap_matches_filter(root, arg) != 0)
 			return -1;
-	}
 
 	return 0;
 }
 
 static int
-ldap_filt_or(struct ber_element *root, struct ber_element *filter)
+ldap_filt_or(struct ber_element *root, struct plan *plan)
 {
-	struct ber_element	*elm;
-
-	if (ber_scanf_elements(filter, "{e", &elm) != 0) {
-		log_warnx("failed to parse search filter");
-		return -1;
-	}
+	struct plan	*arg;
 
-	for (; elm; elm = elm->be_next) {
-		if (ldap_matches_filter(root, elm) == 0)
+	TAILQ_FOREACH(arg, &plan->args, next)
+		if (ldap_matches_filter(root, arg) == 0)
 			return 0;
-	}
 
 	return -1;
 }
 
 static int
-ldap_filt_not(struct ber_element *root, struct ber_element *filter)
+ldap_filt_not(struct ber_element *root, struct plan *plan)
 {
-	struct ber_element	*elm;
+	struct plan	*arg;
 
-	if (ber_scanf_elements(filter, "{e", &elm) != 0) {
-		log_warnx("failed to parse search filter");
-		return -1;
-	}
-
-	for (; elm; elm = elm->be_next) {
-		if (ldap_matches_filter(root, elm) != 0)
+	TAILQ_FOREACH(arg, &plan->args, next)
+		if (ldap_matches_filter(root, arg) != 0)
 			return 0;
-	}
 
 	return -1;
 }
 
 static int
-ldap_filt_presence(struct ber_element *root, struct ber_element *filter)
+ldap_filt_presence(struct ber_element *root, struct plan *plan)
 {
-	const char		*key;
 	struct ber_element	*a;
 
-	if (ber_scanf_elements(filter, "s", &key) != 0) {
-		log_warnx("failed to parse presence filter");
-		return -1;
-	}
-
-	a = ldap_get_attribute(root, key);
+	if (plan->adesc != NULL)
+		a = ldap_get_attribute(root, plan->adesc);
+	else
+		a = ldap_find_attribute(root, plan->at);
 	if (a == NULL) {
-		log_debug("attribute %s not found", key);
-		return -1; /* attribute not found */
+		log_debug("no attribute [%s] found", plan->adesc ?: ATTR_NAME(plan->at));
+		return -1;
 	}
 
 	return 0;
 }
 
 int
-ldap_matches_filter(struct ber_element *root, struct ber_element *filter)
+ldap_matches_filter(struct ber_element *root, struct plan *plan)
 {
-	if (filter == NULL)
+	if (plan == NULL)
 		return 0;
 
-	if (filter->be_class != BER_CLASS_CONTEXT) {
-		log_warnx("invalid class %d in filter", filter->be_class);
-		return -1;
-	}
-
-	switch (filter->be_type) {
+	switch (plan->op) {
 	case LDAP_FILT_EQ:
 	case LDAP_FILT_APPR:
-		return ldap_filt_eq(root, filter);
+		return ldap_filt_eq(root, plan);
 	case LDAP_FILT_SUBS:
-		return ldap_filt_subs(root, filter);
+		return ldap_filt_subs(root, plan);
 	case LDAP_FILT_AND:
-		return ldap_filt_and(root, filter);
+		return ldap_filt_and(root, plan);
 	case LDAP_FILT_OR:
-		return ldap_filt_or(root, filter);
+		return ldap_filt_or(root, plan);
 	case LDAP_FILT_NOT:
-		return ldap_filt_not(root, filter);
+		return ldap_filt_not(root, plan);
 	case LDAP_FILT_PRES:
-		return ldap_filt_presence(root, filter);
+		return ldap_filt_presence(root, plan);
 	default:
-		log_warnx("filter type %d not implemented", filter->be_type);
+		log_warnx("filter type %d not implemented", plan->op);
 		return -1;
 	}
 }
diff --git a/usr.sbin/ldapd/ldapd.h b/usr.sbin/ldapd/ldapd.h
index a2dfeca08c9..4a5d30fcdb7 100644
--- a/usr.sbin/ldapd/ldapd.h
+++ b/usr.sbin/ldapd/ldapd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ldapd.h,v 1.19 2010/10/19 09:10:12 martinh Exp $ */
+/*	$OpenBSD: ldapd.h,v 1.20 2010/11/03 10:33:17 martinh Exp $ */
 
 /*
  * Copyright (c) 2009, 2010 Martin Hedenfalk <martin@bzero.se>
@@ -93,8 +93,8 @@ enum index_type {
 	INDEX_NONE,
 	INDEX_EQUAL	= 1,
 	INDEX_APPROX	= 1,
-	INDEX_SUBSTR,
-	INDEX_PRESENCE
+	INDEX_PRESENCE	= 1,
+	INDEX_SUBSTR
 };
 
 struct attr_index {
@@ -149,7 +149,15 @@ struct plan
 	TAILQ_ENTRY(plan)	 next;
 	TAILQ_HEAD(, plan)	 args;
 	TAILQ_HEAD(, index)	 indices;
+	struct attr_type	*at;
+	char			*adesc;
+	union {
+		char			*value;
+		struct ber_element	*substring;
+	} assert;
+	int			 op;
 	int			 indexed;
+	int			 undefined;
 };
 
 /* For OR filters using multiple indices, matches are not unique. Remember
@@ -427,7 +435,7 @@ void			 control_cleanup(struct control_sock *);
 
 /* filter.c */
 int			 ldap_matches_filter(struct ber_element *root,
-				struct ber_element *filter);
+				struct plan *plan);
 
 /* search.c */
 int			 ldap_search(struct request *req);
diff --git a/usr.sbin/ldapd/search.c b/usr.sbin/ldapd/search.c
index a6dcd63808d..dc94444962d 100644
--- a/usr.sbin/ldapd/search.c
+++ b/usr.sbin/ldapd/search.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: search.c,v 1.10 2010/07/02 05:23:40 martinh Exp $ */
+/*	$OpenBSD: search.c,v 1.11 2010/11/03 10:33:17 martinh Exp $ */
 
 /*
  * Copyright (c) 2009, 2010 Martin Hedenfalk <martin@bzero.se>
@@ -70,7 +70,8 @@ should_include_attribute(char *adesc, struct search *search, int explicit)
 	char			*fdesc;
 	struct ber_element	*elm;
 
-	if (search->attrlist->be_sub->be_encoding == BER_TYPE_EOC) {
+	if (search->attrlist->be_sub == NULL ||
+	    search->attrlist->be_sub->be_encoding == BER_TYPE_EOC) {
 		/* An empty list with no attributes requests the return of
 		 * all user attributes. */
 		return !is_operational(adesc);
@@ -231,7 +232,7 @@ check_search_entry(struct btval *key, struct btval *val, struct search *search)
 		return 0;
 	}
 
-	if (ldap_matches_filter(elm, search->filter) != 0) {
+	if (ldap_matches_filter(elm, search->plan) != 0) {
 		ber_free_elements(elm);
 		return 0;
 	}
@@ -616,6 +617,28 @@ add_index(struct plan *plan, const char *fmt, ...)
 	return 0;
 }
 
+static int
+plan_get_attr(struct plan *plan, struct namespace *ns, char *attr)
+{
+	if (ns->relax) {
+		/*
+		 * Under relaxed schema checking, all attributes
+		 * are considered directory strings with case-insensitive
+		 * matching.
+		 */
+		plan->at = lookup_attribute(conf->schema, "name");
+		plan->adesc = attr;
+	} else
+		plan->at = lookup_attribute(conf->schema, attr);
+
+	if (plan->at == NULL) {
+		log_debug("%s: no such attribute, undefined term", attr);
+		return -1;
+	}
+
+	return 0;
+}
+
 static struct plan *
 search_planner(struct namespace *ns, struct ber_element *filter)
 {
@@ -635,6 +658,7 @@ search_planner(struct namespace *ns, struct ber_element *filter)
 		log_warn("search_planner: calloc");
 		return NULL;
 	}
+	plan->op = filter->be_type;
 	TAILQ_INIT(&plan->args);
 	TAILQ_INIT(&plan->indices);
 
@@ -643,15 +667,31 @@ search_planner(struct namespace *ns, struct ber_element *filter)
 	case LDAP_FILT_APPR:
 		if (ber_scanf_elements(filter, "{ss", &attr, &s) != 0)
 			goto fail;
-		if (namespace_has_index(ns, attr, INDEX_EQUAL))
-			add_index(plan, "%s=%s,", attr, s);
+		if (plan_get_attr(plan, ns, attr) == -1)
+			plan->undefined = 1;
+		else if (plan->at->equality == NULL) {
+			log_debug("'%s' doesn't define equality matching",
+			    attr);
+			plan->undefined = 1;
+		} else {
+			plan->assert.value = s;
+			if (namespace_has_index(ns, attr, INDEX_EQUAL))
+				add_index(plan, "%s=%s,", attr, s);
+		}
 		break;
 	case LDAP_FILT_SUBS:
-		if (ber_scanf_elements(filter, "{s{ts",
-		    &attr, &class, &type, &s) != 0)
+		if (ber_scanf_elements(filter, "{s{ets",
+		    &attr, &plan->assert.substring, &class, &type, &s) != 0)
 			goto fail;
-		if (class == BER_CLASS_CONTEXT && type == LDAP_FILT_SUBS_INIT) {
-			/* only prefix substrings usable for index */
+		if (plan_get_attr(plan, ns, attr) == -1)
+			plan->undefined = 1;
+		else if (plan->at->substr == NULL) {
+			log_debug("'%s' doesn't define substring matching",
+			    attr);
+			plan->undefined = 1;
+		} else if (class == BER_CLASS_CONTEXT &&
+		    type == LDAP_FILT_SUBS_INIT) {
+			/* Only prefix substrings are usable as index. */
 			if (namespace_has_index(ns, attr, INDEX_EQUAL))
 				add_index(plan, "%s=%s", attr, s);
 		}
@@ -659,20 +699,31 @@ search_planner(struct namespace *ns, struct ber_element *filter)
 	case LDAP_FILT_PRES:
 		if (ber_scanf_elements(filter, "s", &attr) != 0)
 			goto fail;
-		if (strcasecmp(attr, "objectClass") != 0) {
+		if (plan_get_attr(plan, ns, attr) == -1)
+			plan->undefined = 1;
+		else if (strcasecmp(attr, "objectClass") != 0) {
 			if (namespace_has_index(ns, attr, INDEX_PRESENCE))
-				add_index(plan, "!%s,", attr);
+				add_index(plan, "%s=", attr);
 		}
 		break;
 	case LDAP_FILT_AND:
-		if (ber_scanf_elements(filter, "{e", &elm) != 0)
+		if (ber_scanf_elements(filter, "(e", &elm) != 0)
 			goto fail;
 		for (; elm; elm = elm->be_next) {
 			if ((arg = search_planner(ns, elm)) == NULL)
 				goto fail;
+			if (arg->undefined) {
+				plan->undefined = 1;
+				break;
+			}
 			TAILQ_INSERT_TAIL(&plan->args, arg, next);
 		}
-		/* select an index to use */
+
+		/* The term is undefined if any arg is undefined. */
+		if (plan->undefined)
+			break;
+
+		/* Select an index to use. */
 		TAILQ_FOREACH(arg, &plan->args, next) {
 			if (arg->indexed) {
 				while ((indx = TAILQ_FIRST(&arg->indices))) {
@@ -686,13 +737,22 @@ search_planner(struct namespace *ns, struct ber_element *filter)
 		}
 		break;
 	case LDAP_FILT_OR:
-		if (ber_scanf_elements(filter, "{e", &elm) != 0)
+		if (ber_scanf_elements(filter, "(e", &elm) != 0)
 			goto fail;
 		for (; elm; elm = elm->be_next) {
 			if ((arg = search_planner(ns, elm)) == NULL)
 				goto fail;
 			TAILQ_INSERT_TAIL(&plan->args, arg, next);
 		}
+
+		/* The term is undefined iff all args are undefined. */
+		plan->undefined = 1;
+		TAILQ_FOREACH(arg, &plan->args, next)
+			if (!arg->undefined) {
+				plan->undefined = 0;
+				break;
+			}
+
 		TAILQ_FOREACH(arg, &plan->args, next) {
 			if (!arg->indexed) {
 				plan->indexed = 0;
@@ -705,8 +765,23 @@ search_planner(struct namespace *ns, struct ber_element *filter)
 			}
 		}
 		break;
+	case LDAP_FILT_NOT:
+		if (ber_scanf_elements(filter, "{e", &elm) != 0)
+			goto fail;
+		if ((arg = search_planner(ns, elm)) == NULL)
+			goto fail;
+		TAILQ_INSERT_TAIL(&plan->args, arg, next);
+
+		plan->undefined = arg->undefined;
+		if (plan->indexed) {
+			log_debug("NOT filter forced unindexed search");
+			plan->indexed = 0;
+		}
+		break;
+
 	default:
 		log_warnx("filter type %d not implemented", filter->be_type);
+		plan->undefined = 1;
 		break;
 	}
 
@@ -873,6 +948,12 @@ ldap_search(struct request *req)
 		goto done;
 	}
 
+	if (search->plan->undefined) {
+		log_debug("whole search filter is undefined");
+		reason = LDAP_SUCCESS;
+		goto done;
+	}
+
 	if (!search->plan->indexed && search->scope == LDAP_SCOPE_ONELEVEL) {
 		int	 sz;
 		sz = strlen(search->basedn) - strlen(search->ns->suffix);