diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2016-04-19 09:34:08 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2016-04-19 09:34:08 -0300 |
commit | 89c09c8e400806a2059fe8460c7c9db517d16ed7 (patch) | |
tree | 78abde0f26d7c9a4d1bd9dce15bb51ea768cd7fc | |
parent | 48baa5e89cfd7e7fbfe03966b50bfcf4f57cc6cd (diff) | |
download | lua-89c09c8e400806a2059fe8460c7c9db517d16ed7.tar.gz lua-89c09c8e400806a2059fe8460c7c9db517d16ed7.tar.bz2 lua-89c09c8e400806a2059fe8460c7c9db517d16ed7.zip |
match time limit defined by variable 'string.pattlimit'
-rw-r--r-- | lstrlib.c | 52 |
1 files changed, 36 insertions, 16 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lstrlib.c,v 1.244 2016/04/07 15:40:07 roberto Exp roberto $ | 2 | ** $Id: lstrlib.c,v 1.245 2016/04/08 21:15:02 roberto Exp roberto $ |
3 | ** Standard library for string operations and pattern-matching | 3 | ** Standard library for string operations and pattern-matching |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -26,7 +26,8 @@ | |||
26 | 26 | ||
27 | /* | 27 | /* |
28 | ** maximum number of captures that a pattern can do during | 28 | ** maximum number of captures that a pattern can do during |
29 | ** pattern-matching. This limit is arbitrary. | 29 | ** pattern-matching. This limit is arbitrary, but must fit in |
30 | ** an unsigned char. | ||
30 | */ | 31 | */ |
31 | #if !defined(LUA_MAXCAPTURES) | 32 | #if !defined(LUA_MAXCAPTURES) |
32 | #define LUA_MAXCAPTURES 32 | 33 | #define LUA_MAXCAPTURES 32 |
@@ -214,9 +215,10 @@ typedef struct MatchState { | |||
214 | const char *src_end; /* end ('\0') of source string */ | 215 | const char *src_end; /* end ('\0') of source string */ |
215 | const char *p_end; /* end ('\0') of pattern */ | 216 | const char *p_end; /* end ('\0') of pattern */ |
216 | lua_State *L; | 217 | lua_State *L; |
217 | size_t nrep; /* limit to avoid non-linear complexity */ | 218 | lua_Unsigned nrep; /* limit to avoid non-linear complexity */ |
218 | int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ | 219 | int matchdepth; /* control for recursive depth (to avoid C stack overflow) */ |
219 | int level; /* total number of captures (finished or unfinished) */ | 220 | unsigned char level; /* total number of captures (finished or unfinished) */ |
221 | unsigned char usedlimit; /* true if real limit for 'nrep' was used */ | ||
220 | struct { | 222 | struct { |
221 | const char *init; | 223 | const char *init; |
222 | ptrdiff_t len; | 224 | ptrdiff_t len; |
@@ -235,13 +237,12 @@ static const char *match (MatchState *ms, const char *s, const char *p); | |||
235 | 237 | ||
236 | 238 | ||
237 | /* | 239 | /* |
238 | ** parameters to control the maximum number of operators handled in | 240 | ** Maximum number of operators handled in a match before consulting |
239 | ** a match (to avoid non-linear complexity). The maximum will be: | 241 | ** 'string.pattlimit'. (This lower limit is only to avoid wasting time |
240 | ** (subject length) * A_REPS + B_REPS | 242 | ** consulting 'string.pattlimit' in simple matches.) |
241 | */ | 243 | */ |
242 | #if !defined(A_REPS) | 244 | #if !defined(PREPATTLIMIT) |
243 | #define A_REPS 4 | 245 | #define PREPATTLIMIT 200 |
244 | #define B_REPS 100000 | ||
245 | #endif | 246 | #endif |
246 | 247 | ||
247 | 248 | ||
@@ -421,6 +422,27 @@ static const char *end_capture (MatchState *ms, const char *s, | |||
421 | } | 422 | } |
422 | 423 | ||
423 | 424 | ||
425 | static void checklimit (MatchState *ms) { | ||
426 | lua_State *L = ms->L; | ||
427 | lua_assert(ms->nrep == 0); | ||
428 | if (!ms->usedlimit) { /* have not used 'string.pattlimit' yet? */ | ||
429 | int top = lua_gettop(L); | ||
430 | if (lua_getglobal(L, "string") == LUA_TTABLE && | ||
431 | lua_getfield(L, -1, "pattlimit") != LUA_TNIL) { /* is it defined? */ | ||
432 | lua_Unsigned limit = (lua_Unsigned)lua_tointeger(L, -1); /* get it */ | ||
433 | if (limit > PREPATTLIMIT) /* discount cycles already used */ | ||
434 | ms->nrep = limit - PREPATTLIMIT; | ||
435 | ms->usedlimit = 1; /* do not use 'pattlimit' again */ | ||
436 | } | ||
437 | else /* no limit defined; set no limit */ | ||
438 | ms->nrep = ~(lua_Unsigned)0; | ||
439 | lua_settop(L, top); /* pop 'string' table and (maybe) 'pattlimit' */ | ||
440 | } | ||
441 | if (ms->nrep == 0) | ||
442 | luaL_error(L, "pattern too complex"); | ||
443 | } | ||
444 | |||
445 | |||
424 | static const char *match_capture (MatchState *ms, const char *s, int l) { | 446 | static const char *match_capture (MatchState *ms, const char *s, int l) { |
425 | size_t len; | 447 | size_t len; |
426 | l = check_capture(ms, l); | 448 | l = check_capture(ms, l); |
@@ -502,8 +524,8 @@ static const char *match (MatchState *ms, const char *s, const char *p) { | |||
502 | s = NULL; /* fail */ | 524 | s = NULL; /* fail */ |
503 | } | 525 | } |
504 | else { /* matched once */ | 526 | else { /* matched once */ |
505 | if (ms->nrep-- == 0) | 527 | if (--ms->nrep == 0) |
506 | luaL_error(ms->L, "pattern too complex"); | 528 | checklimit(ms); |
507 | switch (*ep) { /* handle optional suffix */ | 529 | switch (*ep) { /* handle optional suffix */ |
508 | case '?': { /* optional */ | 530 | case '?': { /* optional */ |
509 | const char *res; | 531 | const char *res; |
@@ -607,10 +629,8 @@ static void prepstate (MatchState *ms, lua_State *L, | |||
607 | ms->src_init = s; | 629 | ms->src_init = s; |
608 | ms->src_end = s + ls; | 630 | ms->src_end = s + ls; |
609 | ms->p_end = p + lp; | 631 | ms->p_end = p + lp; |
610 | if (ls < (MAX_SIZET - B_REPS) / A_REPS) | 632 | ms->nrep = PREPATTLIMIT; |
611 | ms->nrep = A_REPS * ls + B_REPS; | 633 | ms->usedlimit = 0; |
612 | else /* overflow (very long subject) */ | ||
613 | ms->nrep = MAX_SIZET; /* no limit */ | ||
614 | } | 634 | } |
615 | 635 | ||
616 | 636 | ||