arangodb · jsteemann · Jul 14, 2021 · Jul 7, 2021 · Jul 8, 2021 · Jul 8, 2021
diff --git a/CHANGELOG b/CHANGELOG
@@ -1,6 +1,19 @@
 devel
 -----
 
+* Add hard-coded complexity limits for AQL queries, in order to prevent
+  programmatically generated large queries from causing trouble (too deep
+  recursion, enormous memory usage, long query optimization and distribution
+  passes etc.).
+  This change introduces 2 limits:
+  - a recursion limit for AQL query expressions. An expression can now be
+    up to 500 levels deep. An example expression is `1 + 2 + 3 + 4`, which
+    is 3 levels deep `1 + (2 + (3 + 4))`.
+    The expression recursion is limited to 500 levels.
+  - a limit for the number of execution nodes in the initial query 
+    execution plan. 
+    The number of execution nodes is limited to 4,000.
+
 * Always remove blocker object for revision trees in case of replication 
   failures.
 

diff --git a/arangod/Aql/Ast.cpp b/arangod/Aql/Ast.cpp
@@ -2055,8 +2055,9 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
     AqlFunctionsInternalCache aqlFunctionsInternalCache;
     transaction::Methods& trx;
     int64_t stopOptimizationRequests = 0;
-    int64_t nestingLevel = 0;
+    int64_t nestingLevel = 0;  // only used for subqueries
     int64_t filterDepth = -1;  // -1 = not in filter
+    uint64_t recursionDepth = 0;  // current depth of the tree we walk
     bool hasSeenAnyWriteNode = false;
     bool hasSeenWriteNodeInCurrentScope = false;
   };
@@ -2065,6 +2066,7 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
 
   auto preVisitor = [&](AstNode const* node) -> bool {
     auto ctx = &context;
+
     if (ctx->filterDepth >= 0) {
       ++ctx->filterDepth;
     }
@@ -2120,12 +2122,22 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
       // nothing to be done in constant arrays
       return false;
     }
+
+    if (++ctx->recursionDepth > maxExpressionNesting) {
+      // maximum nesting level for expressions/other constructs reached.
+      // we abort to prevent a potential stack overflow
+      THROW_ARANGO_EXCEPTION(TRI_ERROR_QUERY_TOO_MUCH_NESTING);
+    }
 
     return true;
   };
 
   auto postVisitor = [&](AstNode const* node) -> void {
     auto ctx = &context;
+
+    TRI_ASSERT(ctx->recursionDepth > 0);
+    --ctx->recursionDepth;
+
     if (ctx->filterDepth >= 0) {
       --ctx->filterDepth;
     }
@@ -2345,6 +2357,9 @@ void Ast::validateAndOptimize(transaction::Methods& trx) {
 
   // run the optimizations
   _root = traverseAndModify(_root, preVisitor, visitor, postVisitor);
+
+  // must be back to 0 after the traversal
+  TRI_ASSERT(context.recursionDepth == 0);
 }
 
 /// @brief determines the variables referenced in an expression

diff --git a/arangod/Aql/Ast.h b/arangod/Aql/Ast.h
@@ -87,6 +87,9 @@ class Ast {
   /// @brief destroy the AST
   ~Ast();
 
+  /// @brief maximum nesting level for expressions
+  static constexpr uint64_t maxExpressionNesting = 500;
+
   /// @brief return the query
   QueryContext& query() const { return _query; }
 

diff --git a/arangod/Aql/ExecutionPlan.cpp b/arangod/Aql/ExecutionPlan.cpp
@@ -2179,6 +2179,13 @@ ExecutionNode* ExecutionPlan::fromNode(AstNode const* node) {
     if (en == nullptr) {
       THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_INTERNAL, "type not handled");
     }
+
+    if (_ids.size() > maxPlanNodes) {
+      // maximum number of execution nodes reached
+      // we have to limit this to prevent super-long runtimes for query
+      // optimization and execution
+      THROW_ARANGO_EXCEPTION(TRI_ERROR_QUERY_TOO_MUCH_NESTING);
+    }
   }
 
   return en;

diff --git a/arangod/Aql/ExecutionPlan.h b/arangod/Aql/ExecutionPlan.h
@@ -60,8 +60,13 @@ class ExecutionPlan {
 
   /// @brief destroy the plan, frees all assigned nodes
   ~ExecutionPlan();
+
+  /// @brief maximum number of execution nodes allowed per query
+  /// (at the time the initial execution plan is created). we have to limit
+  /// this to prevent super-long runtimes for query optimization and
+  /// execution)
+  static constexpr uint64_t maxPlanNodes = 4000;
 
- public:
   /// @brief create an execution plan from an AST
   /// note: tracking memory usage requires accessing the Ast/Query objects,
   /// which can be inherently unsafe when running within the gtest unit tests.

diff --git a/js/common/bootstrap/errors.js b/js/common/bootstrap/errors.js
@@ -190,6 +190,7 @@
     "ERROR_QUERY_VARIABLE_NAME_UNKNOWN" : { "code" : 1512, "message" : "unknown variable '%s'" },
     "ERROR_QUERY_COLLECTION_LOCK_FAILED" : { "code" : 1521, "message" : "unable to read-lock collection %s" },
     "ERROR_QUERY_TOO_MANY_COLLECTIONS" : { "code" : 1522, "message" : "too many collections/shards" },
+    "ERROR_QUERY_TOO_MUCH_NESTING" : { "code" : 1524, "message" : "too much nesting or too many objects" },
     "ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE" : { "code" : 1539, "message" : "unknown OPTIONS attribute used" },
     "ERROR_QUERY_FUNCTION_NAME_UNKNOWN" : { "code" : 1540, "message" : "usage of unknown function '%s()'" },
     "ERROR_QUERY_FUNCTION_ARGUMENT_NUMBER_MISMATCH" : { "code" : 1541, "message" : "invalid number of arguments for function '%s()', expected number of arguments: minimum: %d, maximum: %d" },

diff --git a/lib/Basics/error-registry.h b/lib/Basics/error-registry.h
@@ -18,7 +18,7 @@ struct elsa<ErrorCode> {
 #include <cinttypes>
 
 namespace arangodb::error {
-constexpr static frozen::unordered_map<ErrorCode, const char*, 345> ErrorMessages = {
+constexpr static frozen::unordered_map<ErrorCode, const char*, 346> ErrorMessages = {
     {TRI_ERROR_NO_ERROR,  // 0
       "no error"},
     {TRI_ERROR_FAILED,  // 1
@@ -383,6 +383,8 @@ constexpr static frozen::unordered_map<ErrorCode, const char*, 345> ErrorMessage
       "unable to read-lock collection %s"},
     {TRI_ERROR_QUERY_TOO_MANY_COLLECTIONS,  // 1522
       "too many collections/shards"},
+    {TRI_ERROR_QUERY_TOO_MUCH_NESTING,  // 1524
+      "too much nesting or too many objects"},
     {TRI_ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE,  // 1539
       "unknown OPTIONS attribute used"},
     {TRI_ERROR_QUERY_FUNCTION_NAME_UNKNOWN,  // 1540

diff --git a/lib/Basics/errors.dat b/lib/Basics/errors.dat
@@ -233,6 +233,7 @@ ERROR_QUERY_VARIABLE_REDECLARED,1511,"variable '%s' is assigned multiple times",
 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."
 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."
 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."
+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."
 ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE,1539,"unknown OPTIONS attribute used","Will be raised when an unknown attribute is used inside an OPTIONS clause."
 ERROR_QUERY_FUNCTION_NAME_UNKNOWN,1540,"usage of unknown function '%s()'","Will be raised when an undefined function is called."
 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."

diff --git a/lib/Basics/voc-errors.h b/lib/Basics/voc-errors.h
@@ -1005,6 +1005,12 @@ constexpr auto TRI_ERROR_QUERY_COLLECTION_LOCK_FAILED
 /// beyond the allowed value.
 constexpr auto TRI_ERROR_QUERY_TOO_MANY_COLLECTIONS                              = ErrorCode{1522};
 
+/// 1524: ERROR_QUERY_TOO_MUCH_NESTING
+/// "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.
+constexpr auto TRI_ERROR_QUERY_TOO_MUCH_NESTING                                  = ErrorCode{1524};
+
 /// 1539: ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE
 /// "unknown OPTIONS attribute used"
 /// Will be raised when an unknown attribute is used inside an OPTIONS clause.

diff --git a/lib/Rest/GeneralResponse.cpp b/lib/Rest/GeneralResponse.cpp
@@ -314,6 +314,7 @@ rest::ResponseCode GeneralResponse::responseCode(ErrorCode code) {
     case static_cast<int>(TRI_ERROR_QUERY_FAIL_CALLED):
     case static_cast<int>(TRI_ERROR_QUERY_INVALID_DATE_VALUE):
     case static_cast<int>(TRI_ERROR_QUERY_MULTI_MODIFY):
+    case static_cast<int>(TRI_ERROR_QUERY_TOO_MUCH_NESTING):
     case static_cast<int>(TRI_ERROR_QUERY_COMPILE_TIME_OPTIONS):
     case static_cast<int>(TRI_ERROR_QUERY_INVALID_OPTIONS_ATTRIBUTE):
     case static_cast<int>(TRI_ERROR_QUERY_DISALLOWED_DYNAMIC_CALL):

diff --git a/tests/Aql/QueryLimitsTest.cpp b/tests/Aql/QueryLimitsTest.cpp
@@ -0,0 +1,152 @@
+////////////////////////////////////////////////////////////////////////////////
+/// DISCLAIMER
+///
+/// Copyright 2014-2020 ArangoDB GmbH, Cologne, Germany
+/// Copyright 2004-2014 triAGENS GmbH, Cologne, Germany
+///
+/// Licensed under the Apache License, Version 2.0 (the "License");
+/// you may not use this file except in compliance with the License.
+/// You may obtain a copy of the License at
+///
+///     http://www.apache.org/licenses/LICENSE-2.0
+///
+/// Unless required by applicable law or agreed to in writing, software
+/// distributed under the License is distributed on an "AS IS" BASIS,
+/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+/// See the License for the specific language governing permissions and
+/// limitations under the License.
+///
+/// Copyright holder is ArangoDB GmbH, Cologne, Germany
+///
+/// @author Jan Steemann
+////////////////////////////////////////////////////////////////////////////////
+
+#include "ApplicationFeatures/ApplicationServer.h"
+#include "Aql/Ast.h"
+#include "Aql/ExecutionPlan.h"
+#include "Aql/Query.h"
+#include "Aql/QueryString.h"
+#include "Transaction/StandaloneContext.h"
+#include "Utils/ExecContext.h"
+#include "VocBase/LogicalCollection.h"
+#include "VocBase/VocbaseInfo.h"
+#include "VocBase/vocbase.h"
+
+#include <velocypack/Builder.h>
+#include <velocypack/Parser.h>
+#include <velocypack/Slice.h>
+
+#include "gtest/gtest.h"
+#include "Mocks/Servers.h"
+
+namespace {
+
+class AqlQueryLimitsTest 
+    : public ::testing::Test,
+      public arangodb::tests::LogSuppressor<arangodb::Logger::AUTHENTICATION, arangodb::LogLevel::ERR> {
+ protected:
+  arangodb::tests::mocks::MockAqlServer server;
+
+ public:
+  AqlQueryLimitsTest() : server(false) {
+    server.startFeatures();
+  }
+
+  arangodb::aql::QueryResult executeQuery(TRI_vocbase_t& vocbase, std::string const& queryString,
+                                        std::shared_ptr<arangodb::velocypack::Builder> bindVars = nullptr,
+                                        std::string const& optionsString = "{}") {
+    auto ctx = std::make_shared<arangodb::transaction::StandaloneContext>(vocbase);
+    arangodb::aql::Query query(ctx, arangodb::aql::QueryString(queryString), bindVars,
+                               arangodb::velocypack::Parser::fromJson(optionsString)->slice());
+
+    arangodb::aql::QueryResult result;
+    while (true) {
+      auto state = query.execute(result);
+      if (state == arangodb::aql::ExecutionState::WAITING) {
+        query.sharedState()->waitForAsyncWakeup();
+      } else {
+        break;
+      }
+    }
+    return result;
+  }
+};
+
+TEST_F(AqlQueryLimitsTest, testManyNodes) {
+  arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
+  testDBInfo.load("testVocbase", 2);
+  TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
+
+  std::string query("LET x = NOOPT('testi')\n");
+  size_t cnt = arangodb::aql::ExecutionPlan::maxPlanNodes - 4; // singleton + calculation + calculation + return
+  for (size_t i = 1; i <= cnt; ++i) {
+    query.append("FILTER x\n");
+  }
+  query.append("RETURN 1");
+
+  auto queryResult = executeQuery(vocbase, query);
+
+  ASSERT_TRUE(queryResult.result.ok());
+  auto slice = queryResult.data->slice();
+  EXPECT_TRUE(slice.isArray());
+  EXPECT_EQ(1, slice.length());
+  EXPECT_EQ(1, slice[0].getNumber<int64_t>());
+}
+
+TEST_F(AqlQueryLimitsTest, testTooManyNodes) {
+  arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
+  testDBInfo.load("testVocbase", 2);
+  TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
+
+  std::string query("LET x = NOOPT('testi')\n");
+  size_t cnt = arangodb::aql::ExecutionPlan::maxPlanNodes;
+  for (size_t i = 1; i <= cnt; ++i) {
+    query.append("FILTER x\n");
+  }
+  query.append("RETURN 1");
+
+  auto queryResult = executeQuery(vocbase, query);
+
+  ASSERT_FALSE(queryResult.result.ok());
+  ASSERT_EQ(TRI_ERROR_QUERY_TOO_MUCH_NESTING, queryResult.result.errorNumber());
+}
+
+TEST_F(AqlQueryLimitsTest, testDeepRecursion) {
+  arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
+  testDBInfo.load("testVocbase", 2);
+  TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
+
+  std::string query("RETURN 0");
+  size_t cnt = arangodb::aql::Ast::maxExpressionNesting - 2; 
+  for (size_t i = 1; i <= cnt; ++i) {
+    query.append(" + ");
+    query.append(std::to_string(i));
+  }
+
+  auto queryResult = executeQuery(vocbase, query);
+
+  ASSERT_TRUE(queryResult.result.ok());
+  auto slice = queryResult.data->slice();
+  EXPECT_TRUE(slice.isArray());
+  EXPECT_EQ(1, slice.length());
+  EXPECT_EQ(124251, slice[0].getNumber<int64_t>());
+}
+
+TEST_F(AqlQueryLimitsTest, testTooDeepRecursion) {
+  arangodb::CreateDatabaseInfo testDBInfo(server.server(), arangodb::ExecContext::current());
+  testDBInfo.load("testVocbase", 2);
+  TRI_vocbase_t vocbase(TRI_vocbase_type_e::TRI_VOCBASE_TYPE_NORMAL, std::move(testDBInfo));
+
+  std::string query("RETURN 0");
+  size_t cnt = arangodb::aql::Ast::maxExpressionNesting; 
+  for (size_t i = 1; i <= cnt; ++i) {
+    query.append(" + ");
+    query.append(std::to_string(i));
+  }
+
+  auto queryResult = executeQuery(vocbase, query);
+  ASSERT_FALSE(queryResult.result.ok());
+  ASSERT_EQ(TRI_ERROR_QUERY_TOO_MUCH_NESTING, queryResult.result.errorNumber());
+}
+
+}
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
@@ -131,8 +131,9 @@ set(ARANGODB_TESTS_SOURCES
   Aql/NgramPosSimilarityFunctionTest.cpp
   Aql/NoResultsExecutorTest.cpp
   Aql/ProjectionsTest.cpp
-  Aql/QueryHelper.cpp
   Aql/QueryCursorTest.cpp
+  Aql/QueryHelper.cpp
+  Aql/QueryLimitsTest.cpp
   Aql/RegisterPlanTest.cpp
   Aql/RemoteExecutorTest.cpp
   Aql/RemoveExecutorTest.cpp

diff --git a/tests/js/server/aql/aql-queries-simple.js b/tests/js/server/aql/aql-queries-simple.js
@@ -1358,14 +1358,57 @@ function ahuacatlQuerySimpleTestSuite () {
       const expected = _.range(cnt, cnt + 10);
       assertEqual(expected, AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
     },
+
+    testQueryWithManyInitializeCursors : function() {
+      let q = "LET x = NOOPT([1])\n";
+      const cnt = 999;
+      for (let i = 0; i < cnt; ++i) {
+        q += `FOR s${i} IN x\n `;
+      }
+      q += "RETURN 1";
+      assertEqual([1], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
+    },
+
+    testQueryWithManyNodes : function() {
+      let q = "LET x = NOOPT('testi')\n";
+      const cnt = 4000 - 4; // singleton + calculation + calculation + return
+      for (let i = 0; i < cnt; ++i) {
+        q += `FILTER x\n `;
+      }
+      q += "RETURN 1";
+      assertEqual([1], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
+    },
+
+    testQueryWithTooManyNodes : function() {
+      let q = "LET x = NOOPT('testi')\n";
+      const cnt = 4000; // plus singleton + calculation + calculation + return
+      for (let i = 0; i < cnt; ++i) {
+        q += `FILTER x\n `;
+      }
+      q += "RETURN 1";
+      assertQueryError(errors.ERROR_QUERY_TOO_MUCH_NESTING.code, q);
+    },
+
+    testQueryWithDeepExpression : function() {
+      let q = "RETURN 0";
+      const cnt = 500 - 2; 
+      for (let i = 1; i <= cnt; ++i) {
+        q += " + " + i;
+      }
+      assertEqual([124251], AQL_EXECUTE(q, {}, {optimizer: {rules: ['-all']}}).json);
+    },
+
+    testQueryWithTooDeepExpression : function() {
+      let q = "RETURN 0";
+      const cnt = 500; 
+      for (let i = 0; i < cnt; ++i) {
+        q += " + " + i;
+      }
+      assertQueryError(errors.ERROR_QUERY_TOO_MUCH_NESTING.code, q);
+    },
   };
 }
 
-////////////////////////////////////////////////////////////////////////////////
-/// @brief executes the test suite
-////////////////////////////////////////////////////////////////////////////////
-
 jsunity.run(ahuacatlQuerySimpleTestSuite);
 
 return jsunity.done();
-