Resoves: #448831

Summary: attacker can tie up CPU in regex code
Description: when substring search is requested, sets the time limit based upon
the nsslapd-timelimit value.  Pass the timelimit (time_up) to the regular
expression function.  When the time is up, it returns the "Timelimit exceeded"
error.	Note: timelimit is applied non-Directory Manager users.

12 files changed, 83 insertions, 35 deletions

diff --git a/ldap/servers/plugins/acl/acl.c b/ldap/servers/plugins/acl/acl.c
index 120e70db..5262ca3e 100644
--- a/ldap/servers/plugins/acl/acl.c
+++ b/ldap/servers/plugins/acl/acl.c
@@ -3253,7 +3253,7 @@ acl_match_substring ( Slapi_Filter *f, char *str, int exact_match)
 	** matching, it seems that step() is leaking 1036 bytes/search	
 	** I couldn't figure out why it's leaking.
 	*/
-	rc = slapd_re_exec( realval );
+	rc = slapd_re_exec( realval, -1 /* no timelimit */ );
 
 	slapd_re_unlock();
 
diff --git a/ldap/servers/plugins/syntaxes/string.c b/ldap/servers/plugins/syntaxes/string.c
index c0701978..315610d8 100644
--- a/ldap/servers/plugins/syntaxes/string.c
+++ b/ldap/servers/plugins/syntaxes/string.c
@@ -195,9 +195,20 @@ string_filter_sub( Slapi_PBlock *pb, char *initial, char **any, char *final,
 	char		pat[BUFSIZ];
 	char		buf[BUFSIZ];
 	char		ebuf[BUFSIZ];
+	time_t		curtime = 0;
+	time_t		time_up = 0;
+	time_t		optime = 0; /* time op was initiated */
+	int		timelimit = 0; /* search timelimit */
 
 	LDAPDebug( LDAP_DEBUG_FILTER, "=> string_filter_sub\n",
 	    0, 0, 0 );
+	slapi_pblock_get( pb, SLAPI_SEARCH_TIMELIMIT, &timelimit );
+	slapi_pblock_get( pb, SLAPI_OPINITIATED_TIME, &optime );
+	/*
+	 * (timelimit==-1) means no time limit
+	 */
+	time_up = ( timelimit==-1 ? -1 : optime + timelimit);
+
 	/*
 	 * construct a regular expression corresponding to the
 	 * filter and let regex do the work for each value
@@ -259,18 +270,21 @@ string_filter_sub( Slapi_PBlock *pb, char *initial, char **any, char *final,
 	p = (bigpat) ? bigpat : pat;
 	slapd_re_lock();
 	if ( (tmpbuf = slapd_re_comp( p )) != 0 ) {
-		LDAPDebug( LDAP_DEBUG_ANY, "re_comp (%s) failed (%s)\n",
-		    pat, p, 0 );
-		slapd_re_unlock();
-		if( bigpat != NULL ) {
-			slapi_ch_free((void**)&bigpat );
-		}
-		return( LDAP_OPERATIONS_ERROR );
+		LDAPDebug( LDAP_DEBUG_ANY, "re_comp (%s) failed (%s): %s\n",
+		    pat, p, tmpbuf );
+		rc = LDAP_OPERATIONS_ERROR;
+		goto bailout;
 	} else {
  		LDAPDebug( LDAP_DEBUG_TRACE, "re_comp (%s)\n",
 				   escape_string( p, ebuf ), 0, 0 );
 	}
 
+	curtime = current_time();
+	if ( time_up != -1 && curtime > time_up ) {
+		rc = LDAP_TIMELIMIT_EXCEEDED;
+		goto bailout;
+	}
+
 	/*
 	 * test the regex against each value
 	 */
@@ -296,22 +310,22 @@ string_filter_sub( Slapi_PBlock *pb, char *initial, char **any, char *final,
 		}
 		value_normalize( realval, syntax, 1 /* trim leading blanks */ );
 
-		tmprc = slapd_re_exec( realval );
+		tmprc = slapd_re_exec( realval, time_up );
 
 		LDAPDebug( LDAP_DEBUG_TRACE, "re_exec (%s) %i\n",
 				   escape_string( realval, ebuf ), tmprc, 0 );
-		if ( tmprc != 0 ) {
+		if ( tmprc == 1 ) {
 			rc = 0;
 			break;
+		} else if ( tmprc != 0 ) {
+			rc = tmprc;
+			break;
 		}
 	}
+bailout:
 	slapd_re_unlock();
-	if ( tmpbuf != NULL ) {
-		slapi_ch_free((void**)&tmpbuf );
-	}
-	if( bigpat != NULL ) {
-		slapi_ch_free((void**)&bigpat );
-	} 
+	slapi_ch_free((void**)&tmpbuf );	/* NULL is fine */
+	slapi_ch_free((void**)&bigpat );	/* NULL is fine */
 
 	LDAPDebug( LDAP_DEBUG_FILTER, "<= string_filter_sub %d\n",
 	    rc, 0, 0 );
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_search.c b/ldap/servers/slapd/back-ldbm/ldbm_search.c
index 7979b585..b9ca5cbf 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_search.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_search.c
@@ -1296,6 +1296,10 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
                                   "Failed the filter test", 0, NULL );
                   rc = SLAPI_FAIL_GENERAL;
                   goto bail;
+              } else if (LDAP_TIMELIMIT_EXCEEDED == filter_test) {
+                  slapi_send_ldap_result( pb, LDAP_TIMELIMIT_EXCEEDED, NULL, NULL, nentries, urls );
+                  rc = SLAPI_FAIL_GENERAL;
+                  goto bail;
               }
           }
         }
diff --git a/ldap/servers/slapd/entry.c b/ldap/servers/slapd/entry.c
index 57f1d47f..d01c2c41 100644
--- a/ldap/servers/slapd/entry.c
+++ b/ldap/servers/slapd/entry.c
@@ -1843,7 +1843,7 @@ slapi_entry_vattrcache_findAndTest( const Slapi_Entry *e, const char *type,
 														f->f_choice,
 														&f->f_ava );
 				} else if ( filter_type == FILTER_TYPE_SUBSTRING) {
-					*rc = plugin_call_syntax_filter_sub( tmp_attr,
+					*rc = plugin_call_syntax_filter_sub( NULL, tmp_attr,
 															&f->f_sub);
 				} else if ( filter_type == FILTER_TYPE_PRES ) {
 					/* type is there, that's all we need to know. */
diff --git a/ldap/servers/slapd/filterentry.c b/ldap/servers/slapd/filterentry.c
index 1e7ab8bb..e9df0949 100644
--- a/ldap/servers/slapd/filterentry.c
+++ b/ldap/servers/slapd/filterentry.c
@@ -693,7 +693,7 @@ int test_substring_filter(
 			rc = -1;
 			for ( a = e->e_attrs; a != NULL; a = a->a_next ) {
 				if ( slapi_attr_type_cmp( f->f_sub_type, a->a_type, SLAPI_TYPE_CMP_SUBTYPE ) == 0 ) {
-					rc = plugin_call_syntax_filter_sub( a, &f->f_sub );
+					rc = plugin_call_syntax_filter_sub( pb, a, &f->f_sub );
 					if ( rc == 0 ) {
 						break;
 					}
@@ -726,8 +726,8 @@ int test_substring_filter(
 		rc = -1;
 		for ( a = e->e_attrs; a != NULL; a = a->a_next ) {
 			if ( slapi_attr_type_cmp( f->f_sub_type, a->a_type, SLAPI_TYPE_CMP_SUBTYPE ) == 0 ) {
-				rc = plugin_call_syntax_filter_sub( a, &f->f_sub );
-				if ( rc == 0 ) {
+				rc = plugin_call_syntax_filter_sub( pb, a, &f->f_sub );
+				if ( rc == 0 || rc == LDAP_TIMELIMIT_EXCEEDED ) {
 					break;
 				}
 			}
diff --git a/ldap/servers/slapd/getfilelist.c b/ldap/servers/slapd/getfilelist.c
index b72b0453..08619056 100644
--- a/ldap/servers/slapd/getfilelist.c
+++ b/ldap/servers/slapd/getfilelist.c
@@ -130,7 +130,7 @@ matches(const char *filename, const char *pattern)
 	slapd_re_lock();
 	s = slapd_re_comp((char *)pattern);
 	if (!s)
-		match = slapd_re_exec((char *)filename);
+		match = slapd_re_exec((char *)filename, -1 /* no timelimit */);
 	slapd_re_unlock();
 
 	return match;
diff --git a/ldap/servers/slapd/plugin_syntax.c b/ldap/servers/slapd/plugin_syntax.c
index 2002ae58..2034e5c4 100644
--- a/ldap/servers/slapd/plugin_syntax.c
+++ b/ldap/servers/slapd/plugin_syntax.c
@@ -211,15 +211,17 @@ plugin_call_syntax_filter_ava_sv(
 
 int
 plugin_call_syntax_filter_sub(
+    Slapi_PBlock	*pb,
     Slapi_Attr		*a,
     struct subfilt	*fsub
 )
 {
-	return(plugin_call_syntax_filter_sub_sv(a,fsub));
+	return(plugin_call_syntax_filter_sub_sv(pb,a,fsub));
 }
 
 int
 plugin_call_syntax_filter_sub_sv(
+    Slapi_PBlock	*pb,
     Slapi_Attr		*a,
     struct subfilt	*fsub
 )
@@ -240,6 +242,13 @@ plugin_call_syntax_filter_sub_sv(
 	{
 		Slapi_Value **va= valueset_get_valuearray(&a->a_present_values);
 		pblock_init( &pipb );
+		if (pb)
+		{
+			Operation *op = NULL;
+			/* to pass SLAPI_SEARCH_TIMELIMIT & SLAPI_OPINITATED_TIME */
+			slapi_pblock_get( pb, SLAPI_OPERATION, &op );
+			slapi_pblock_set( &pipb, SLAPI_OPERATION, op );
+		}
 		slapi_pblock_set( &pipb, SLAPI_PLUGIN, (void *) a->a_plugin );
 		rc = a->a_plugin->plg_syntax_filter_sub( &pipb,
 		    fsub->sf_initial, fsub->sf_any, fsub->sf_final, va);
diff --git a/ldap/servers/slapd/proto-slap.h b/ldap/servers/slapd/proto-slap.h
index 566dff06..1ef45039 100644
--- a/ldap/servers/slapd/proto-slap.h
+++ b/ldap/servers/slapd/proto-slap.h
@@ -745,8 +745,8 @@ int plugin_mr_filter_create (mr_filter_t* f);
 struct slapdplugin *slapi_get_global_syntax_plugins();
 int plugin_call_syntax_filter_ava( const Slapi_Attr *a, int ftype, struct ava *ava );
 int plugin_call_syntax_filter_ava_sv( const Slapi_Attr *a, int ftype, struct ava *ava, Slapi_Value **retVal, int useDeletedValues );
-int plugin_call_syntax_filter_sub( Slapi_Attr *a, struct subfilt *fsub );
-int plugin_call_syntax_filter_sub_sv( Slapi_Attr *a, struct subfilt *fsub );
+int plugin_call_syntax_filter_sub( Slapi_PBlock *pb, Slapi_Attr *a, struct subfilt *fsub );
+int plugin_call_syntax_filter_sub_sv( Slapi_PBlock *pb, Slapi_Attr *a, struct subfilt *fsub );
 int plugin_call_syntax_get_compare_fn(void *vpi, value_compare_fn_type *compare_fn);
 struct slapdplugin *plugin_syntax_find( const char *nameoroid );
 void plugin_syntax_enumerate( SyntaxEnumFunc sef, void *arg );
diff --git a/ldap/servers/slapd/regex.c b/ldap/servers/slapd/regex.c
index 9fe06a76..c1d9a073 100644
--- a/ldap/servers/slapd/regex.c
+++ b/ldap/servers/slapd/regex.c
@@ -66,6 +66,14 @@
  * Modification history:
  *
  * $Log: regex.c,v $
+ * Revision 1.7  2008/06/30 17:28:16  nhosoi
+ * Resoves: #448831
+ * Summary: attacker can tie up CPU in regex code
+ * Description: when substring search is requested, sets the time limit based upon
+ * the nsslapd-timelimit value.  Pass the timelimit (time_up) to the regular
+ * expression function.  When the time is up, it returns the "Timelimit exceeded"
+ * error.	Note: timelimit is applied non-Directory Manager users.
+ *
  * Revision 1.6  2008/04/29 00:38:36  nhosoi
  * Resolves: #182621 (#443955)
  * Summary: Allow larger regex buffer to enable long substring filters
@@ -695,7 +703,7 @@ static UCHAR *bol;
 static UCHAR *bopat[MAXTAG];
 static UCHAR *eopat[MAXTAG];
 #ifdef NEEDPROTOS
-static UCHAR *pmatch( UCHAR *lp, UCHAR *ap );
+static UCHAR *pmatch( UCHAR *lp, UCHAR *ap, time_t time_up, int *err );
 #else /* NEEDPROTOS */
 static UCHAR *pmatch();
 #endif /* NEEDPROTOS */
@@ -720,14 +728,18 @@ static UCHAR *pmatch();
  *	to the beginning and the end of the matched fragment,
  *	respectively.
  *
+ *  return values: 0 -- did not match
+ *                 1 -- matched
+ *                 othersise -- ldap error (TIMELIMIT_EXCEEDED only)
  */
 
 int
-slapd_re_exec( char *lp )
+slapd_re_exec( char *lp, time_t time_up )
 {
 	register UCHAR c;
 	register UCHAR *ep = 0;
 	register UCHAR *ap = nfa;
+	int ldaperror = 0;
 
 	bol = (UCHAR*)lp;
 
@@ -745,7 +757,7 @@ slapd_re_exec( char *lp )
 	switch(*ap) {
 
 	case BOL:			/* anchored: match from BOL only */
-		ep = pmatch((UCHAR*)lp,ap);
+		ep = pmatch((UCHAR*)lp,ap,time_up,&ldaperror);
 		break;
 	case CHR:			/* ordinary char: locate it fast */
 		c = *(ap+1);
@@ -755,7 +767,7 @@ slapd_re_exec( char *lp )
 			return 0;
 	default:			/* regular matching all the way. */
 		do {
-			if ((ep = pmatch((UCHAR*)lp,ap)))
+			if ((ep = pmatch((UCHAR*)lp,ap,time_up,&ldaperror)))
 				break;
 			lp++;
 		} while (*lp);
@@ -764,6 +776,8 @@ slapd_re_exec( char *lp )
 	case END:			/* munged automaton. fail always */
 		return 0;
 	}
+	if (ldaperror)
+		return ldaperror;
 	if (!ep)
 		return 0;
 
@@ -844,13 +858,19 @@ static char chrtyp[MAXCHR] = {
 #define CCLSKIP 18	/* [CLO] CCL 16bytes END ... */
 
 static UCHAR *
-pmatch( UCHAR *lp, UCHAR *ap)
+pmatch( UCHAR *lp, UCHAR *ap, time_t time_up, int *err )
 {
 	register int op, c, n;
 	register UCHAR *e;		/* extra pointer for CLO */
 	register UCHAR *bp;		/* beginning of subpat.. */
 	register UCHAR *ep;		/* ending of subpat..	 */
 	UCHAR *are;			/* to save the line ptr. */
+	time_t curtime = current_time();
+
+	if ( time_up != -1 && curtime > time_up ) {
+		*err = LDAP_TIMELIMIT_EXCEEDED;
+		return 0;
+	}
 
 	while ((op = *ap++) != END)
 		switch(op) {
@@ -927,7 +947,7 @@ pmatch( UCHAR *lp, UCHAR *ap)
 			ap += n;
 
 			while (lp >= are) {
-				if ((e = pmatch(lp, ap)) != NULL)
+				if ((e = pmatch(lp, ap, time_up, err)) != NULL)
 					return e;
 				--lp;
 			}
diff --git a/ldap/servers/slapd/sasl_map.c b/ldap/servers/slapd/sasl_map.c
index 25923b3c..cc8adc63 100644
--- a/ldap/servers/slapd/sasl_map.c
+++ b/ldap/servers/slapd/sasl_map.c
@@ -434,9 +434,10 @@ sasl_map_check(sasl_map_data *dp, char *sasl_user_and_realm, char **ldap_search_
 	recomp_result = slapd_re_comp(dp->regular_expression);
 	if (recomp_result) {
 		LDAPDebug( LDAP_DEBUG_ANY, "sasl_map_check : re_comp failed for expression (%s)\n", dp->regular_expression, 0, 0 );
+	} else {
+		matched = slapd_re_exec(sasl_user_and_realm, -1 /* no timelimit */);
+		LDAPDebug( LDAP_DEBUG_TRACE, "regex: %s, id: %s, %s\n", dp->regular_expression, sasl_user_and_realm, matched ? "matched" : "didn't match" );
 	}
-	matched = slapd_re_exec(sasl_user_and_realm);
-	LDAPDebug( LDAP_DEBUG_TRACE, "regex: %s, id: %s, %s\n", dp->regular_expression, sasl_user_and_realm, matched ? "matched" : "didn't match" );
 	if (matched) {
 		if (matched == 1) {
 			/* Allocate buffers for the returned strings */
diff --git a/ldap/servers/slapd/slapi-private.h b/ldap/servers/slapd/slapi-private.h
index 8d16deee..49a8fbb9 100644
--- a/ldap/servers/slapd/slapi-private.h
+++ b/ldap/servers/slapd/slapi-private.h
@@ -1185,7 +1185,7 @@ typedef char*(*CFP)();
 
 void bervalarray_add_berval_fast(struct berval ***vals, const struct berval *addval, int nvals, int *maxvals);
 
-int slapd_re_exec( char *lp );
+int slapd_re_exec( char *lp, time_t time_up );
 char *slapd_re_comp( char *pat );
 int slapd_re_subs( char *src, char* dst );
 void slapd_re_lock( void );
diff --git a/ldap/servers/slapd/vattr.c b/ldap/servers/slapd/vattr.c
index 5c22cb05..270594d4 100644
--- a/ldap/servers/slapd/vattr.c
+++ b/ldap/servers/slapd/vattr.c
@@ -540,7 +540,7 @@ int vattr_test_filter( Slapi_PBlock *pb,
 									rc = plugin_call_syntax_filter_ava( a,
 															f->f_choice, &f->f_ava );
 								} else if ( filter_type == FILTER_TYPE_SUBSTRING) {
-									rc = plugin_call_syntax_filter_sub( a,
+									rc = plugin_call_syntax_filter_sub( pb, a,
 																		&f->f_sub);
 								}
 
@@ -611,7 +611,7 @@ int vattr_test_filter( Slapi_PBlock *pb,
 								    		
     	} else if ( filter_type == FILTER_TYPE_SUBSTRING ) {
 			
-			rc = test_substring_filter( NULL, e, f, 0 /* no access check */,
+			rc = test_substring_filter( pb, e, f, 0 /* no access check */,
 									0 /* do test filter */, &acl_test_done);
 				
 		} else if ( filter_type == FILTER_TYPE_PRES ) {