1From 9e4e95f87cdddc9082e33db204c2534b59acde58 Mon Sep 17 00:00:00 2001
2From: Szabolcs Nagy <nsz@port70.net>
3Date: Thu, 23 Apr 2026 21:22:18 +0000
4Subject: [PATCH] regex: avoid int overflow in regcomp
5
6regcomp has many int arith ops that may overflow. before tre_expand_ast
7int values are limited by 2x the input length n, e.g.:
8
9 input ERE int field max value
10 aaaaaaaaaaaa... position n
11 ()()()()()()... submatch_id n/2+1
12 ()||||||||||... num_tags 2n-3
13
14so overflow before expand requires large n (and a lot of memory). later
15some values can become big due to repetitions:
16
17 input ERE int field that overflows
18 (((a{255}){255}){255}){255} position
19 ((a|b*){255,}){255,} num_transitions
20
21num_transitions and memory use can be big without {k,} repetitions too:
22
23 input ERE what max value
24 (a|a|a|a...|a)* num_transitions n^2/4
25 (()|a|a|...|a)* sum tnfa tags > n^3/16 - n^2
26
27so memory can run out quickly as n grows (with 31bit va space 1700 long
28input is enough even without {k,}) about half is tnfa and half is ast
29firstpos/lastpos data. but overflow can happen before allocations fail.
30
31fix early overflow by limiting n. the stack usage is in [n,11n] without
32repetitions, usually 7n, so the stack limit got adjusted too. the limit
33is such that almost all inputs that worked before still work.
34
35overflows during and after expand are fixed by explicit checks via a
36check_add helper and xcalloc instead of xmalloc.
37---
38 src/regex/regcomp.c | 41 +++++++++++++++++++++++++++++++++++------
39 1 file changed, 35 insertions(+), 6 deletions(-)
40
41diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
42index b4b81968..a7115b12 100644
43--- a/src/regex/regcomp.c
44+++ b/src/regex/regcomp.c
45@@ -1680,6 +1680,12 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
46 AST to TNFA compilation routines.
47 */
48
49+/* check if a+b overflows for a,b in [0,INT_MAX] */
50+static int check_add(unsigned a, unsigned b)
51+{
52+ return a + b > INT_MAX;
53+}
54+
55 typedef enum {
56 COPY_RECURSE,
57 COPY_SET_RESULT_PTR
58@@ -1731,6 +1737,8 @@ tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
59 /* XXX - e.g. [ab] has only one position but two
60 nodes, so we are creating holes in the state space
61 here. Not fatal, just wastes memory. */
62+ if (check_add(pos, *pos_add))
63+ return REG_ESPACE;
64 pos += *pos_add;
65 num_copied++;
66 }
67@@ -1826,6 +1834,8 @@ tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
68 break;
69 }
70 }
71+ if (check_add(*pos_add, num_copied))
72+ return REG_ESPACE;
73 *pos_add += num_copied;
74 return status;
75 }
76@@ -1870,6 +1880,8 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
77 tre_literal_t *lit= node->obj;
78 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
79 {
80+ if (check_add(lit->position, pos_add))
81+ return REG_ESPACE;
82 lit->position += pos_add;
83 if (lit->position > max_pos)
84 max_pos = lit->position;
85@@ -1998,6 +2010,8 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
86 }
87
88 iter_depth--;
89+ if (check_add(pos_add_total, pos_add - pos_add_last))
90+ return REG_ESPACE;
91 pos_add_total += pos_add - pos_add_last;
92 if (iter_depth == 0)
93 pos_add = pos_add_total;
94@@ -2010,6 +2024,8 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
95 }
96 }
97
98+ if (check_add(*position, pos_add_total))
99+ return REG_ESPACE;
100 *position += pos_add_total;
101
102 /* `max_pos' should never be larger than `*position' if the above
103@@ -2711,9 +2727,19 @@ regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
104 /* Parse context. */
105 tre_parse_ctx_t parse_ctx;
106
107+ /* Limits: before tre_expand_ast, int values like position, subid or
108+ * num_tags are bounded by 2x input length, used stack entries are
109+ * bounded by 16x input length. input length is checked upfront to
110+ * avoid overflows before expand. later, values that can grow big are
111+ * bounds checked via check_add and xcalloc. */
112+ const int input_limit = 1024000;
113+ const int stack_limit = 8*input_limit;
114+ if (strnlen(regex, input_limit) >= input_limit)
115+ return REG_ESPACE;
116+
117 /* Allocate a stack used throughout the compilation process for various
118 purposes. */
119- stack = tre_stack_new(512, 1024000, 128);
120+ stack = tre_stack_new(512, stack_limit, 128);
121 if (!stack)
122 return REG_ESPACE;
123 /* Allocate a fast memory allocator. */
124@@ -2801,9 +2827,12 @@ regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
125 for example "a*" or "ab*". Figure out a simple way to detect
126 this possibility. */
127 tmp_ast_l = tree;
128- tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
129+ tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position);
130 if (tmp_ast_r == NULL)
131 ERROR_EXIT(REG_ESPACE);
132+ if (check_add(parse_ctx.position, 1))
133+ ERROR_EXIT(REG_ESPACE);
134+ parse_ctx.position++;
135
136 tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
137 if (tree == NULL)
138@@ -2813,22 +2842,22 @@ regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
139 if (errcode != REG_OK)
140 ERROR_EXIT(errcode);
141
142- counts = xmalloc(sizeof(int) * parse_ctx.position);
143+ counts = xcalloc(sizeof(int), parse_ctx.position);
144 if (counts == NULL)
145 ERROR_EXIT(REG_ESPACE);
146
147- offs = xmalloc(sizeof(int) * parse_ctx.position);
148+ offs = xcalloc(sizeof(int), parse_ctx.position);
149 if (offs == NULL)
150 ERROR_EXIT(REG_ESPACE);
151
152- for (i = 0; i < parse_ctx.position; i++)
153- counts[i] = 0;
154 tre_ast_to_tnfa(tree, NULL, counts, NULL);
155
156 add = 0;
157 for (i = 0; i < parse_ctx.position; i++)
158 {
159 offs[i] = add;
160+ if (check_add(add, counts[i] + 1))
161+ ERROR_EXIT(REG_ESPACE);
162 add += counts[i] + 1;
163 counts[i] = 0;
164 }
165--
1662.54.0
167
