From 92663b1e32722d89c3255920625329f58b3cdb78 Mon Sep 17 00:00:00 2001 From: Stefan Fritsch Date: Sat, 19 Nov 2011 21:58:48 +0000 Subject: [PATCH] Limit recursion in ap_expr evaluation to avoid unbounded stack usage * evaluate chains of ||, &&, and string concatenation non-recursively * limit other types of recursion to 20 levels * avoid some string copies if concatenating more than 2 strings git-svn-id: https://svn.apache.org/repos/asf/httpd/httpd/trunk@1204087 13f79535-47bb-0310-9956-ffa450edef68 --- include/ap_expr.h | 2 + include/ap_mmn.h | 3 +- server/util_expr_eval.c | 163 +++++++++++++++++++++++++++++++-------- server/util_expr_parse.c | 4 +- server/util_expr_parse.y | 8 +- 5 files changed, 140 insertions(+), 40 deletions(-) diff --git a/include/ap_expr.h b/include/ap_expr.h index 409c7acd4c..6d6506035a 100644 --- a/include/ap_expr.h +++ b/include/ap_expr.h @@ -130,6 +130,8 @@ typedef struct { const char **result_string; /** Arbitrary context data provided by the caller for custom functions */ void *data; + /** The current recursion level */ + int reclvl; } ap_expr_eval_ctx_t; /** diff --git a/include/ap_mmn.h b/include/ap_mmn.h index 2438a88d3d..6c09f0a2cd 100644 --- a/include/ap_mmn.h +++ b/include/ap_mmn.h @@ -366,6 +366,7 @@ * and ap_unescape_urlencoded(). * 20111025.2 (2.3.15-dev) Add ap_lua_ssl_val to mod_lua * 20111118.0 (2.5.0-dev) Add conn_rec to error_log hook + * 20111118.1 (2.5.0-dev) Add reclvl to ap_expr_eval_ctx_t */ #define MODULE_MAGIC_COOKIE 0x41503234UL /* "AP24" */ @@ -373,7 +374,7 @@ #ifndef MODULE_MAGIC_NUMBER_MAJOR #define MODULE_MAGIC_NUMBER_MAJOR 20111118 #endif -#define MODULE_MAGIC_NUMBER_MINOR 0 /* 0...n */ +#define MODULE_MAGIC_NUMBER_MINOR 1 /* 0...n */ /** * Determine if the server's current MODULE_MAGIC_NUMBER is at least a diff --git a/server/util_expr_eval.c b/server/util_expr_eval.c index 3dd5863ae8..6547d7b9d3 100644 --- a/server/util_expr_eval.c +++ b/server/util_expr_eval.c @@ -56,10 +56,30 @@ static void expr_dump_tree(const ap_expr_t *e, const server_rec *s, int loglevel, int indent); #endif +/* + * To reduce counting overhead, we only count calls to + * ap_expr_eval_word() and ap_expr_eval(). This means the actual + * recursion may be twice as deep. + */ +#define AP_EXPR_MAX_RECURSION 20 +static int inc_rec(ap_expr_eval_ctx_t *ctx) +{ + if (ctx->reclvl < AP_EXPR_MAX_RECURSION) { + ctx->reclvl++; + return 0; + } + *ctx->err = "Recursion limit reached"; + /* short circuit further evaluation */ + ctx->reclvl = INT_MAX; + return 1; +} + static const char *ap_expr_eval_word(ap_expr_eval_ctx_t *ctx, const ap_expr_t *node) { const char *result = ""; + if (inc_rec(ctx)) + return result; switch (node->node_op) { case op_Digit: case op_String: @@ -68,17 +88,41 @@ static const char *ap_expr_eval_word(ap_expr_eval_ctx_t *ctx, case op_Var: result = ap_expr_eval_var(ctx, node->node_arg1, node->node_arg2); break; - case op_Concat: { - const char *s1 = ap_expr_eval_word(ctx, node->node_arg1); - const char *s2 = ap_expr_eval_word(ctx, node->node_arg2); - if (!*s1) - result = s2; - else if (!*s2) - result = s1; - else - result = apr_pstrcat(ctx->p, s1, s2, NULL); + case op_Concat: + if (((ap_expr_t *)node->node_arg2)->node_op != op_Concat) { + const char *s1 = ap_expr_eval_word(ctx, node->node_arg1); + const char *s2 = ap_expr_eval_word(ctx, node->node_arg2); + if (!*s1) + result = s2; + else if (!*s2) + result = s1; + else + result = apr_pstrcat(ctx->p, s1, s2, NULL); + } + else { + const ap_expr_t *nodep = node; + int i = 1; + struct iovec *vec; + do { + nodep = nodep->node_arg2; + i++; + } while (nodep->node_op == op_Concat); + vec = apr_palloc(ctx->p, i * sizeof(struct iovec)); + nodep = node; + i = 0; + do { + vec[i].iov_base = (void *)ap_expr_eval_word(ctx, + nodep->node_arg1); + vec[i].iov_len = strlen(vec[i].iov_base); + i++; + nodep = nodep->node_arg2; + } while (nodep->node_op == op_Concat); + vec[i].iov_base = (void *)ap_expr_eval_word(ctx, nodep); + vec[i].iov_len = strlen(vec[i].iov_base); + i++; + result = apr_pstrcatv(ctx->p, vec, i, NULL); + } break; - } case op_StringFuncCall: { const ap_expr_t *info = node->node_arg1; const ap_expr_t *args = node->node_arg2; @@ -96,6 +140,7 @@ static const char *ap_expr_eval_word(ap_expr_eval_ctx_t *ctx, } if (!result) result = ""; + ctx->reclvl--; return result; } @@ -657,30 +702,81 @@ static int ap_expr_eval(ap_expr_eval_ctx_t *ctx, const ap_expr_t *node) { const ap_expr_t *e1 = node->node_arg1; const ap_expr_t *e2 = node->node_arg2; - switch (node->node_op) { - case op_True: - return 1; - case op_False: - return 0; - case op_Not: - return (!ap_expr_eval(ctx, e1)); - case op_Or: - return (ap_expr_eval(ctx, e1) || ap_expr_eval(ctx, e2)); - case op_And: - return (ap_expr_eval(ctx, e1) && ap_expr_eval(ctx, e2)); - case op_UnaryOpCall: - return ap_expr_eval_unary_op(ctx, e1, e2); - case op_BinaryOpCall: - return ap_expr_eval_binary_op(ctx, e1, e2); - case op_Comp: - if (ctx->info->flags & AP_EXPR_FLAG_SSL_EXPR_COMPAT) - return ssl_expr_eval_comp(ctx, e1); - else - return ap_expr_eval_comp(ctx, e1); - default: - *ctx->err = "Internal evaluation error: Unknown expression node"; - return FALSE; + int result = FALSE; + if (inc_rec(ctx)) + return result; + while (1) { + switch (node->node_op) { + case op_True: + result ^= TRUE; + goto out; + case op_False: + ctx->reclvl--; + result ^= FALSE; + goto out; + case op_Not: + result = !result; + node = e1; + break; + case op_Or: + do { + if (e1->node_op == op_Not) { + if (!ap_expr_eval(ctx, e1->node_arg1)) { + result ^= TRUE; + goto out; + } + } + else { + if (ap_expr_eval(ctx, e1)) { + ctx->reclvl--; + result ^= TRUE; + goto out; + } + } + node = node->node_arg2; + e1 = node->node_arg1; + } while (node->node_op == op_Or); + break; + case op_And: + do { + if (e1->node_op == op_Not) { + if (ap_expr_eval(ctx, e1->node_arg1)) { + result ^= FALSE; + goto out; + } + } + else { + if (!ap_expr_eval(ctx, e1)) { + result ^= FALSE; + goto out; + } + } + node = node->node_arg2; + e1 = node->node_arg1; + } while (node->node_op == op_And); + break; + case op_UnaryOpCall: + result ^= ap_expr_eval_unary_op(ctx, e1, e2); + goto out; + case op_BinaryOpCall: + result ^= ap_expr_eval_binary_op(ctx, e1, e2); + goto out; + case op_Comp: + if (ctx->info->flags & AP_EXPR_FLAG_SSL_EXPR_COMPAT) + result ^= ssl_expr_eval_comp(ctx, e1); + else + result ^= ap_expr_eval_comp(ctx, e1); + goto out; + default: + *ctx->err = "Internal evaluation error: Unknown expression node"; + goto out; + } + e1 = node->node_arg1; + e2 = node->node_arg2; } +out: + ctx->reclvl--; + return result; } AP_DECLARE(int) ap_expr_exec(request_rec *r, const ap_expr_info_t *info, @@ -704,6 +800,7 @@ AP_DECLARE(int) ap_expr_exec_ctx(ap_expr_eval_ctx_t *ctx) AP_DEBUG_ASSERT(ctx->re_source != NULL); AP_DEBUG_ASSERT(ctx->re_nmatch > 0); } + ctx->reclvl = 0; *ctx->err = NULL; if (ctx->info->flags & AP_EXPR_FLAG_STRING_RESULT) { diff --git a/server/util_expr_parse.c b/server/util_expr_parse.c index 80f47374e4..bcf0173b73 100644 --- a/server/util_expr_parse.c +++ b/server/util_expr_parse.c @@ -591,9 +591,9 @@ static const yytype_int8 yypact[] = 25, -35, 79, -17, -35, -8, 60, 60, 43, 43, 43, 43, 43, 43, 43, 5, 5, 0, 43, 43, 43, 43, 43, 43, 43, -35, -27, -35, -35, 73, - -35, 3, -35, 25, 25, 25, 25, 25, 25, 25, + -35, 86, 3, 25, 25, 25, 25, 25, 25, 25, -35, -35, -35, -35, 23, 43, -35, -35, 25, 25, - 25, 25, 25, 25, -35, -35, 106, 43, 85, 25, + 25, 25, 25, 25, 25, -35, 106, 43, 85, 25, -35, -21, -35, 43, -35, 25 }; diff --git a/server/util_expr_parse.y b/server/util_expr_parse.y index ffa1ec5a9c..85ed123104 100644 --- a/server/util_expr_parse.y +++ b/server/util_expr_parse.y @@ -81,10 +81,10 @@ %token T_OP_AND %token T_OP_NOT -%left T_OP_OR -%left T_OP_AND -%left T_OP_NOT -%left T_OP_CONCAT +%right T_OP_OR +%right T_OP_AND +%right T_OP_NOT +%right T_OP_CONCAT %type expr %type comparison -- 2.40.0