* [tarantool-patches] [PATCH] sql: decrease max depth of expression AST
@ 2018-12-11 23:03 Nikita Pettik
2018-12-12 13:34 ` [tarantool-patches] " Vladislav Shpilevoy
0 siblings, 1 reply; 2+ messages in thread
From: Nikita Pettik @ 2018-12-11 23:03 UTC (permalink / raw)
To: tarantool-patches; +Cc: v.shpilevoy, Nikita Pettik
Currently, all routines connected with expression AST processing rely on
recursive approaches. On the other hand, SQL is executed in a standard
fiber, which features only 64kb of stack memory. Hence, deep recursion
can result in stack overflow. To avoid obvious overflows lets
significantly restrict allowed depth of expression AST. Note that it is
not radical solution to this problem but rather temporary fix.
Workaround for #3861
---
Branch: https://github.com/tarantool/tarantool/tree/np/gh-3861-reduce-expr-AST-depth
Issue: https://github.com/tarantool/tarantool/issues/3861
src/box/sql/sqliteLimit.h | 2 +-
test/sql-tap/where7.test.lua | 32 ++++++++++++++++++++++----------
2 files changed, 23 insertions(+), 11 deletions(-)
diff --git a/src/box/sql/sqliteLimit.h b/src/box/sql/sqliteLimit.h
index 3b474ed9f..e7d1b63c2 100644
--- a/src/box/sql/sqliteLimit.h
+++ b/src/box/sql/sqliteLimit.h
@@ -106,7 +106,7 @@ enum {
* at all times.
*/
#ifndef SQLITE_MAX_EXPR_DEPTH
-#define SQLITE_MAX_EXPR_DEPTH 1000
+#define SQLITE_MAX_EXPR_DEPTH 200
#endif
/*
diff --git a/test/sql-tap/where7.test.lua b/test/sql-tap/where7.test.lua
index 09cbe53d1..d5f389347 100755
--- a/test/sql-tap/where7.test.lua
+++ b/test/sql-tap/where7.test.lua
@@ -1,6 +1,6 @@
#!/usr/bin/env tarantool
test = require("sqltester")
-test:plan(2022)
+test:plan(2023)
--!./tcltestrunner.lua
-- 2008 December 23
@@ -230,14 +230,14 @@ test:do_test(
"where7-1.20",
function()
sql = "SELECT a FROM t1 WHERE a=11 OR b=11"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR a=%s OR b=%s", i, i)
end
sql = sql .. " ORDER BY a"
return count_steps(sql)
end, {
-- <where7-1.20>
-
+
-- </where7-1.20>
})
@@ -245,7 +245,7 @@ test:do_test(
"where7-1.21",
function()
sql = "SELECT a FROM t1 WHERE b=11 OR c=11"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR b=%s OR c=%s", i, i)
end
sql = sql .. " ORDER BY a"
@@ -260,7 +260,7 @@ test:do_test(
"where7-1.22",
function()
sql = "SELECT a FROM t1 WHERE (b=11 OR c=11"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR b=%s OR c=%s", i, i)
end
sql = sql .. ") AND d>=0 AND d<9999 ORDER BY a"
@@ -275,7 +275,7 @@ test:do_test(
"where7-1.23",
function()
sql = "SELECT a FROM t1 WHERE (b=11 OR c=11"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR (b=%s AND d!=0) OR (c=%s AND d IS NOT NULL)", i, i)
end
sql = sql .. ") AND d>=0 AND d<9999 ORDER BY a"
@@ -290,14 +290,14 @@ test:do_test(
"where7-1.31",
function()
sql = "SELECT a FROM t1 WHERE (a=11 AND b=11)"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR (a=%s AND b=%s)", i, i)
end
sql = sql .. " ORDER BY a"
return count_steps(sql)
end, {
-- <where7-1.31>
-
+
-- </where7-1.31>
})
@@ -305,17 +305,29 @@ test:do_test(
"where7-1.32",
function()
sql = "SELECT a FROM t1 WHERE (b=11 AND c=11)"
- for i = 12, 400 - 1, 1 do
+ for i = 12, 100 do
sql = sql .. string.format(" OR (b=%s AND c=%s)", i, i)
end
sql = sql .. " ORDER BY a"
return count_steps(sql)
end, {
-- <where7-1.32>
-
+
-- </where7-1.32>
})
+test:do_test(
+ "where7-AST-depth-limit",
+ function()
+ sql = "SELECT a FROM t1 WHERE a = 0"
+ for i = 1, 199 do
+ sql = sql .. string.format(" OR a = %s", i)
+ end
+ return test:catchsql(sql)
+ end, {
+ 1, "Expression tree is too large (maximum depth 200)"
+ })
+
test:do_test(
"where7-2.1",
function()
--
2.15.1
^ permalink raw reply [flat|nested] 2+ messages in thread
* [tarantool-patches] Re: [PATCH] sql: decrease max depth of expression AST
2018-12-11 23:03 [tarantool-patches] [PATCH] sql: decrease max depth of expression AST Nikita Pettik
@ 2018-12-12 13:34 ` Vladislav Shpilevoy
0 siblings, 0 replies; 2+ messages in thread
From: Vladislav Shpilevoy @ 2018-12-12 13:34 UTC (permalink / raw)
To: Nikita Pettik, tarantool-patches
LGTM.
On 12/12/2018 02:03, Nikita Pettik wrote:
> Currently, all routines connected with expression AST processing rely on
> recursive approaches. On the other hand, SQL is executed in a standard
> fiber, which features only 64kb of stack memory. Hence, deep recursion
> can result in stack overflow. To avoid obvious overflows lets
> significantly restrict allowed depth of expression AST. Note that it is
> not radical solution to this problem but rather temporary fix.
>
> Workaround for #3861
> ---
> Branch: https://github.com/tarantool/tarantool/tree/np/gh-3861-reduce-expr-AST-depth
> Issue: https://github.com/tarantool/tarantool/issues/3861
>
> src/box/sql/sqliteLimit.h | 2 +-
> test/sql-tap/where7.test.lua | 32 ++++++++++++++++++++++----------
> 2 files changed, 23 insertions(+), 11 deletions(-)
>
> diff --git a/src/box/sql/sqliteLimit.h b/src/box/sql/sqliteLimit.h
> index 3b474ed9f..e7d1b63c2 100644
> --- a/src/box/sql/sqliteLimit.h
> +++ b/src/box/sql/sqliteLimit.h
> @@ -106,7 +106,7 @@ enum {
> * at all times.
> */
> #ifndef SQLITE_MAX_EXPR_DEPTH
> -#define SQLITE_MAX_EXPR_DEPTH 1000
> +#define SQLITE_MAX_EXPR_DEPTH 200
> #endif
>
> /*
> diff --git a/test/sql-tap/where7.test.lua b/test/sql-tap/where7.test.lua
> index 09cbe53d1..d5f389347 100755
> --- a/test/sql-tap/where7.test.lua
> +++ b/test/sql-tap/where7.test.lua
> @@ -1,6 +1,6 @@
> #!/usr/bin/env tarantool
> test = require("sqltester")
> -test:plan(2022)
> +test:plan(2023)
>
> --!./tcltestrunner.lua
> -- 2008 December 23
> @@ -230,14 +230,14 @@ test:do_test(
> "where7-1.20",
> function()
> sql = "SELECT a FROM t1 WHERE a=11 OR b=11"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR a=%s OR b=%s", i, i)
> end
> sql = sql .. " ORDER BY a"
> return count_steps(sql)
> end, {
> -- <where7-1.20>
> -
> +
> -- </where7-1.20>
> })
>
> @@ -245,7 +245,7 @@ test:do_test(
> "where7-1.21",
> function()
> sql = "SELECT a FROM t1 WHERE b=11 OR c=11"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR b=%s OR c=%s", i, i)
> end
> sql = sql .. " ORDER BY a"
> @@ -260,7 +260,7 @@ test:do_test(
> "where7-1.22",
> function()
> sql = "SELECT a FROM t1 WHERE (b=11 OR c=11"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR b=%s OR c=%s", i, i)
> end
> sql = sql .. ") AND d>=0 AND d<9999 ORDER BY a"
> @@ -275,7 +275,7 @@ test:do_test(
> "where7-1.23",
> function()
> sql = "SELECT a FROM t1 WHERE (b=11 OR c=11"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR (b=%s AND d!=0) OR (c=%s AND d IS NOT NULL)", i, i)
> end
> sql = sql .. ") AND d>=0 AND d<9999 ORDER BY a"
> @@ -290,14 +290,14 @@ test:do_test(
> "where7-1.31",
> function()
> sql = "SELECT a FROM t1 WHERE (a=11 AND b=11)"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR (a=%s AND b=%s)", i, i)
> end
> sql = sql .. " ORDER BY a"
> return count_steps(sql)
> end, {
> -- <where7-1.31>
> -
> +
> -- </where7-1.31>
> })
>
> @@ -305,17 +305,29 @@ test:do_test(
> "where7-1.32",
> function()
> sql = "SELECT a FROM t1 WHERE (b=11 AND c=11)"
> - for i = 12, 400 - 1, 1 do
> + for i = 12, 100 do
> sql = sql .. string.format(" OR (b=%s AND c=%s)", i, i)
> end
> sql = sql .. " ORDER BY a"
> return count_steps(sql)
> end, {
> -- <where7-1.32>
> -
> +
> -- </where7-1.32>
> })
>
> +test:do_test(
> + "where7-AST-depth-limit",
> + function()
> + sql = "SELECT a FROM t1 WHERE a = 0"
> + for i = 1, 199 do
> + sql = sql .. string.format(" OR a = %s", i)
> + end
> + return test:catchsql(sql)
> + end, {
> + 1, "Expression tree is too large (maximum depth 200)"
> + })
> +
> test:do_test(
> "where7-2.1",
> function()
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2018-12-12 13:34 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-11 23:03 [tarantool-patches] [PATCH] sql: decrease max depth of expression AST Nikita Pettik
2018-12-12 13:34 ` [tarantool-patches] " Vladislav Shpilevoy
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox