8000 Add limits for AQL query complexity (#14480) · arangodb/arangodb@ea62066 · GitHub
[go: up one dir, main page]
Skip to content

Commit ea62066

Browse files
jsteemannjsteemann
authored
Add limits for AQL query complexity (#14480)
1 parent ab53aa4 commit ea62066

File tree

13 files changed

+259
-9
lines changed

13 files changed

+259
-9
lines changed

‎CHANGELOG

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,19 @@
11
devel
22
-----
33

4+
* Add hard-coded complexity limits for AQL queries, in order to prevent
5+
programmatically generated large queries from causing trouble (too deep
6+
recursion, enormous memory usage, long query optimization and distribution
7+
passes etc.).
8+
This change introduces 2 limits:
9+
- a recursion limit for AQL query expressions. An expression can now be
10+
up to 500 levels deep. An example expression is `1 + 2 + 3 + 4`, which
11+
is 3 levels deep `1 + (2 + (3 + 4))`.
12+
The expression recursion is limited to 500 levels.
13+
- a limit for the number of execution nodes in the initial query
14+
execution plan.
15+
The number of execution nodes is limited to 4,000.
16+
417
* Always remove blocker object for revision trees in case of replication
518
failures.
619

‎arangod/Aql/Ast.cpp

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2055,8 +2055,9 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
20552055
AqlFunctionsInternalCache aqlFunctionsInternalCache;
20562056
transaction::Methods& trx;
20572057
int64_t stopOptimizationRequests = 0;
2058-
int64_t nestingLevel = 0;
2058+
int64_t nestingLevel = 0; // only used for subqueries
20592059
int64_t filterDepth = -1; // -1 = not in filter
2060+
uint64_t recursionDepth = 0; // current depth of the tree we walk
20602061
bool hasSeenAnyWriteNode = false;
20612062
bool hasSeenWriteNodeInCurrentScope = false;
20622063
};
@@ -2065,6 +2066,7 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
20652066

20662067
auto preVisitor = [&](AstNode const* node) -> bool {
20672068
auto ctx = &context;
2069+
20682070
if (ctx->filterDepth >= 0) {
20692071
++ctx->filterDepth;
20702072
}
@@ -2120,12 +2122,22 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
21202122
// nothing to be done in constant arrays
21212123
return false;
21222124
}
2125+
2126+
if (++ctx->recursionDepth > maxExpressionNesting) {
2127+
// maximum nesting level for expressions/other constructs reached.
2128+
// we abort to prevent a potential stack overflow
2129+
THROW_ARANGO_EXCEPTION(TRI_ERROR_QUERY_TOO_MUCH_NESTING);
2130+
}
21232131

21242132
return true;
21252133
};
21262134

21272135
auto postVisitor = [&](AstNode const* node) -> void {
21282136
auto ctx = &context;
2137+
2138+
TRI_ASSERT(ctx->recursionDepth > 0);
2139+
--ctx->recursionDepth;
2140+
21292141
if (ctx->filterDepth >= 0) {
21302142
--ctx->filterDepth;
21312143
}
@@ -2345,6 +2357,9 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
23452357

23462358
// run the optimizations
23472359
_root = traverseAndModify(_root, preVisitor, visitor, postVisitor);
2360+
2361+
// must be back to 0 after the traversal
2362+
TRI_ASSERT(context.recursionDepth == 0);
23482363
}
23492364

23502365
/// @brief determines the variables referenced in an expression

‎arangod/Aql/Ast.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,9 @@ class Ast {
8787
/// @brief destroy the AST
8888
~Ast();
8989

90+
/// @brief maximum nesting level for expressions
91+
static constexpr uint64_t maxExpressionNesting = 500;
92+
9093
/// @brief return the query
9194
QueryContext& query() const { return _query; }
9295

‎arangod/Aql/ExecutionPlan.cpp

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2179,6 +2179,13 @@ ExecutionNode* ExecutionPlan::fromNode(AstNode const* node) {
21792179
if (en == nullptr) {
21802180
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_INTERNAL, "type not handled");
21812181
}
2182+
2183+
if (_ids.size() > maxPlanNodes) {
2184+
// maximum number of execution nodes reached
2185+
// we have to limit this to prevent super-long runtimes for query
2186+
// optimization and execution
2187+
THROW_ARANGO_EXCEPTION(TRI_ERROR_QUERY_TOO_MUCH_NESTING);
2188+
}
21822189
}
21832190

21842191
return en;

‎arangod/Aql/ExecutionPlan.h

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -60,8 +60,13 @@ class ExecutionPlan {
6060

6161
/// @brief destroy the plan, frees all assigned nodes
6262
~ExecutionPlan();
63+
64+
/// @brief maximum number of execution nodes allowed per query
65+
/// (at the time the initial execution plan is created). we have to limit
66+
/// this to prevent super-long runtimes for query optimization and
67+
/// execution)
68+
static constexpr uint64_t maxPlanNodes = 4000;
6369

64-
public:
6570
/// @brief create an execution plan from an AST
6671
/// note: tracking memory usage requires accessing the Ast/Query objects,
6772
/// which can be inherently unsafe when running within the gtest unit tests.

‎js/common/bootstrap/errors.js

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -190,6 +190,7 @@
190190
"ERROR_QUERY_VARIABLE_NAME_UNKNOWN" : { "code" : 1512, "message" : "unknown variable '%s'" },
191191
"ERROR_QUERY_COLLECTION_LOCK_FAILED" : { "code" : 1521, "message" : "unable to read-lock collection %s" },
192192
"ERROR_QUERY_TOO_MANY_COLLECTIONS" : { "code" : 1522, "message" : "too many collections/shards" },
193+
"ERROR_QUERY_TOO_MUCH_NESTING" : { "code" : 1524, "message" : "too much nesting or too many objects" },
193194
"ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE" : { "code" : 1539, "message" : "unknown OPTIONS attribute used" },
194195
"ERROR_QUERY_FUNCTION_NAME_UNKNOWN" : { "code" : 1540, "message" : "usage of unknown function '%s()'" },
195196
"ERROR_QUERY_FUNCTION_ARGUMENT_NUMBER_MISMATCH" : { "code" : 1541, "message" : "invalid number of arguments for function '%s()', expected number of arguments: minimum: %d, maximum: %d" },

‎lib/Basics/error-registry.h

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ struct elsa<ErrorCode> {
1818
#include <cinttypes>
1919

2020
namespace arangodb::error {
21-
constexpr static frozen::unordered_map<ErrorCode, const char*, 345> ErrorMessages = {
21+
constexpr static frozen::unordered_map<ErrorCode, const char*, 346> ErrorMessages = {
2222
{TRI_ERROR_NO_ERROR, // 0
2323
"no error"},
2424
{TRI_ERROR_FAILED, // 1
@@ -383,6 +383,8 @@ constexpr static frozen::unordered_map<ErrorCode, const char*, 345> ErrorMessage
383383
"unable to read-lock collection %s"},
384384
{TRI_ERROR_QUERY_TOO_MANY_COLLECTIONS, // 1522
385385
"too many collections/shards"},
386+
{TRI_ERROR_QUERY_TOO_MUCH_NESTING, // 1524
387+
"too much nesting or too many objects"},
386388
{TRI_ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE, // 1539
387389
"unknown OPTIONS attribute used"},
388390
{TRI_ERROR_QUERY_FUNCTION_NAME_UNKNOWN, // 1540

‎lib/Basics/errors.dat

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -233,6 +233,7 @@ ERROR_QUERY_VARIABLE_REDECLARED,1511,"variable '%s' is assigned multiple times",
233233
ERROR_QUERY_VARIABLE_NAME_UNKNOWN,1512,"unknown variable '%s'","Will be raised when an unknown variable is used or the variable is undefined the context it is used."
234234
ERROR_QUERY_COLLECTION_LOCK_FAILED,1521,"unable to read-lock collection %s","Will be raised when a read lock on the collection cannot be acquired."
235235
ERROR_QUERY_TOO_MANY_COLLECTIONS,1522,"too many collections/shards","Will be raised when the number of collections or shards in a query is beyond the allowed value."
236+
ERROR_QUERY_TOO_MUCH_NESTING,1524,"too much nesting or too many objects","Will be raised when a query contains expressions or other constructs with too many objects or that are too deeply nested."
236237
ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE,1539,"unknown OPTIONS attribute used","Will be raised when an unknown attribute is used inside an OPTIONS clause."
237238
ERROR_QUERY_FUNCTION_NAME_UNKNOWN,1540,"usage of unknown function '%s()'","Will be raised when an undefined function is called."
238239
ERROR_QUERY_FUNCTION_ARGUMENT_NUMBER_MISMATCH,1541,"invalid number of arguments for function '%s()', expected number of arguments: minimum: %d, maximum: %d","Will be raised when the number of arguments used in a function call does not match the expected number of arguments for the function."

‎lib/Basics/voc-errors.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1005,6 +1005,12 @@ constexpr auto TRI_ERROR_QUERY_COLLECTION_LOCK_FAILED
10051005
/// beyond the allowed value.
10061006
constexpr auto TRI_ERROR_QUERY_TOO_MANY_COLLECTIONS = ErrorCode{1522};
10071007

1008+
/// 1524: ERROR_QUERY_TOO_MUCH_NESTING
1009+
/// "too much nesting or too many objects"
1010+
/// Will be raised when a query contains expressions or other constructs with
1011+
/// too many objects or that are too deeply nested.
1012+
constexpr auto TRI_ERROR_QUERY_TOO_MUCH_NESTING = ErrorCode{1524};
1013+
10081014
/// 1539: ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE
10091015
/// "unknown OPTIONS attribute used"
10101016
/// Will be raised when an unknown attribute is used inside an OPTIONS clause.

‎lib/Rest/GeneralResponse.cpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -314,6 +314,7 @@ rest::ResponseCode GeneralResponse::responseCode(ErrorCode code) {
314314
case static_cast<int>(TRI_ERROR_QUERY_FAIL_CALLED):
315315
case static_cast<int>(TRI_ERROR_QUERY_INVALID_DATE_VALUE):
316316
case static_cast<int>(TRI_ERROR_QUERY_MULTI_MODIFY):
317+
case static_cast<int>(TRI_ERROR_QUERY_TOO_MUCH_NESTING):
317318
case static_cast<int>(TRI_ERROR_QUERY_COMPILE_TIME_OPTIONS):
318319
case static_cast<int>(TRI_ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE):
319320
case static_cast<int>(TRI_ERROR_QUERY_DISALLOWED_DYNAMIC_CALL):

‎tests/Aql/QueryLimitsTest.cpp

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
////////////////////////////////////////////////////////////////////////////////
2+
/// DISCLAIMER
3+
///
4+
/// Copyright 2014-2020 ArangoDB GmbH, Cologne, Germany
5+
/// Copyright 2004-2014 triAGENS GmbH, Cologne, Germany
6+
///
7+
/// Licensed under the Apache License, Version 2.0 (the "License");
8+
/// you may not use this file except in compliance with the License.
9+
/// You may obtain a copy of the License at
10+
///
11+
/// http://www.apache.org/licenses/LICENSE-2.0
12+
///
13+
/// Unless required by applicable law or agreed to in writing, software
14+
/// distributed under the License is distributed on an "AS IS" BASIS,
15+
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16+
/// See the License for the specific language governing permissions and
17+
/// limitations under the License.
18+
///
19+
/// Copyright holder is ArangoDB GmbH, Cologne, Germany
20+
///
21+
/// @author Jan Steemann
22+
////////////////////////////////////////////////////////////////////////////////
23+
24+
#include "ApplicationFeatures/ApplicationServer.h"
25+
#include "Aql/Ast.h"
26+
#include "Aql/ExecutionPlan.h"
27+
#include "Aql/Query.h"
28+
#include "Aql/QueryString.h"
29+
#include "Transaction/StandaloneContext.h"
30+
#include "Utils/ExecContext.h"
31+
#include "VocBase/LogicalCollection.h"
32+
#include "VocBase/VocbaseInfo.h"
33+
#include "VocBase/vocbase.h"
34+
35+
#include <velocypack/Builder.h>
36+
#include <velocypack/Parser.h>
37+
#include <velocypack/Slice.h>
38+
39+
#include "gtest/gtest.h"
40+
#include "Mocks/Servers.h"
41+
42+
namespace {
43+
44+
class AqlQueryLimitsTest
45+
: public ::testing::Test,
46+
public arangodb::tests::LogSuppressor<arangodb::Logger::AUTHENTICATION, arangodb::LogLevel::ERR> {
47+
protected:
48+
arangodb::tests::mocks::MockAqlServer server;
49+
50+
public:
51+
AqlQueryLimitsTest() : server(false) {
52+
server.startFeatures();
53+
}
54+
55+
arangodb::aql::QueryResult executeQuery(TRI_vocbase_t& vocbase, std::string const& queryString,
56+
std::shared_ptr<arangodb::velocypack::Builder> bindVars = nullptr,
57+
std::string const& optionsString = "{}") {
58+
auto ctx = std::make_shared<arangodb::transaction::StandaloneContext>(vocbase);
59+
arangodb::aql::Query query(ctx, arangodb::aql::QueryString(queryString), bindVars,
60+
arangodb::velocypack::Parser::fromJson(optionsString)->slice());
61+
62+
arangodb::aql::QueryResult result;
63+
while (true) {
64+
auto state = query.execute(result);
65+
if (state == arangodb::aql::ExecutionState::WAITING) {
66+
query.sharedState()->waitForAsyncWakeup();
67+
} else {
68+
break;
69+
}
70+
}
71+
return result;
72+
}
73+
};
74+
75+
TEST_F(AqlQueryLimitsTest, testManyNodes) {
76+
arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
77+
testDBInfo.load("testVocbase", 2);
78+
TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
79+
80+
std::string query("LET x = NOOPT('testi')\n");
81+
size_t cnt = arangodb::aql::ExecutionPlan::maxPlanNodes - 4; // singleton + calculation + calculation + return
82+
for (size_t i = 1; i <= cnt; ++i) {
83+
query.append("FILTER x\n");
84+
}
85+
query.append("RETURN 1");
86+
87+
auto queryResult = executeQuery(vocbase, query);
88+
89+
ASSERT_TRUE(queryResult.result.ok());
90+
auto slice = queryResult.data->slice();
91+
EXPECT_TRUE(slice.isArray());
92+
EXPECT_EQ(1, slice.length());
93+
EXPECT_EQ(1, slice[0].getNumber<int64_t>());
94+
}
95+
96+
TEST_F(AqlQueryLimitsTest, testTooManyNodes) {
97+
arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
98+
testDBInfo.load("testVocbase", 2);
99+
TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
100+
101+
std::string query("LET x = NOOPT('testi')\n");
102+
size_t cnt = arangodb::aql::ExecutionPlan::maxPlanNodes;
103+
for (size_t i = 1; i <= cnt; ++i) {
104+
query.append("FILTER x\n");
105+
}
106+
query.append("RETURN 1");
107+
108+
auto queryResult = executeQuery(vocbase, query);
109+
110+
ASSERT_FALSE(queryResult.result.ok());
111+
ASSERT_EQ(TRI_ERROR_QUERY_TOO_MUCH_NESTING, queryResult.result.errorNumber());
112+
}
113+
114+
TEST_F(AqlQueryLimitsTest, testDeepRecursion) {
115+
arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
116+
testDBInfo.load("testVocbase", 2);
117+
TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
118+
119+
std::string query("RETURN 0");
120+
size_t cnt = arangodb::aql::Ast::maxExpressionNesting - 2;
121+
for (size_t i = 1; i <= cnt; ++i) {
122+
query.append(" + ");
123+
query.append(std::to_string(i));
124+
}
125+
126+
auto queryResult = executeQuery(vocbase, query);
127+
128+
ASSERT_TRUE(queryResult.result.ok());
129+
auto slice = queryResult.data->slice();
130+
EXPECT_TRUE(slice.isArray());
131+
EXPECT_EQ(1, slice.length());
132+
EXPECT_EQ(124251, slice[0].getNumber<int64_t>());
133+
}
134+
135+
TEST_F(AqlQueryLimitsTest, testTooDeepRecursion) {
136+
arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
137+
testDBInfo.load("testVocbase", 2);
138+
TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
139+
140+
std::string query("RETURN 0");
141+
size_t cnt = arangodb::aql::Ast::maxExpressionNesting;
142+
for (size_t i = 1; i <= cnt; ++i) {
143+
query.append(" + ");
144+
query.append(std::to_string(i));
145+
}
146+
147+
auto queryResult = executeQuery(vocbase, query);
148+
ASSERT_FALSE(queryResult.result.ok());
149+
ASSERT_EQ(TRI_ERROR_QUERY_TOO_MUCH_NESTING, queryResult.result.errorNumber());
150+
}
151+
152+
}

‎tests/CMakeLists.txt

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -131,8 +131,9 @@ set(ARANGODB_TESTS_SOURCES
131131
Aql/NgramPosSimila C2EE rityFunctionTest.cpp
132132
Aql/NoResultsExecutorTest.cpp
133133
Aql/ProjectionsTest.cpp
134-
Aql/QueryHelper.cpp
135134
Aql/QueryCursorTest.cpp
135+
Aql/QueryHelper.cpp
136+
Aql/QueryLimitsTest.cpp
136137
Aql/RegisterPlanTest.cpp
137138
Aql/RemoteExecutorTest.cpp
138139
Aql/RemoveExecutorTest.cpp

‎tests/js/server/aql/aql-queries-simple.js

Lines changed: 48 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1358,14 +1358,57 @@ function ahuacatlQuerySimpleTestSuite () {
13581358
const expected = _.range(cnt, cnt + 10);
13591359
assertEqual(expected, AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
13601360
},
1361+
1362+
testQueryWithManyInitializeCursors : function() {
1363+
let q = "LET x = NOOPT([1])\n";
1364+
const cnt = 999;
1365+
for (let i = 0; i < cnt; ++i) {
1366+
q += `FOR s${i} IN x\n `;
1367+
}
1368+
q += "RETURN 1";
1369+
assertEqual([1], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
1370+
},
1371+
1372+
testQueryWithManyNodes : function() {
1373+
let q = "LET x = NOOPT('testi')\n";
1374+
const cnt = 4000 - 4; // singleton + calculation + calculation + return
1375+
for (let i = 0; i < cnt; ++i) {
1376+
q += `FILTER x\n `;
1377+
}
1378+
q += "RETURN 1";
1379+
assertEqual([1], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
1380+
},
1381+
1382+
testQueryWithTooManyNodes : function() {
1383+
let q = "LET x = NOOPT('testi')\n";
1384+
const cnt = 4000; // plus singleton + calculation + calculation + return
1385+
for (let i = 0; i < cnt; ++i) {
1386+
q += `FILTER x\n `;
1387+
}
1388+
q += "RETURN 1";
1389+
assertQueryError(errors.ERROR_QUERY_TOO_MUCH_NESTING.code, q);
1390+
},
1391+
1392+
testQueryWithDeepExpression : function() {
1393+
let q = "RETURN 0";
1394+
const cnt = 500 - 2;
1395+
for (let i = 1; i <= cnt; ++i) {
1396+
q += " + " + i;
1397+
}
1398+
assertEqual([124251], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
1399+
},
1400+
1401+
testQueryWithTooDeepExpression : function() {
1402+
let q = "RETURN 0";
1403+
const cnt = 500;
1404+
for (let i = 0; i < cnt; ++i) {
1405+
q += " + " + i;
1406+
}
1407+
assertQueryError(errors.ERROR_QUERY_TOO_MUCH_NESTING.code, q);
1408+
},
13611409
};
13621410
}
13631411

1364-
////////////////////////////////////////////////////////////////////////////////
1365-
/// @brief executes the test suite
1366-
////////////////////////////////////////////////////////////////////////////////
1367-
13681412
jsunity.run(ahuacatlQuerySimpleTestSuite);
13691413

13701414
return jsunity.done();
1371-

0 commit comments

Comments
 (0)
0