resource bound parsing execution

[garypen]

Description

It's relatively easy to cause the parser to execute into a stack overflow. For example, something like:

query {Q1:product(id:1){url},Q2:product(id:2){url},Q3:product(id:3){url},Q4:product(id:4){url},Q5:product(id:5){url},Q6:product(id:6){url},Q7:product(id:7){url},...

Once you start getting up to the tens of thousands, you will hit a stack overflow. This particular query triggers a recursion in

selection() -> field() -> field()...

A simple remediation looks like:

apollo-rs % git diff
diff --git a/crates/apollo-parser/src/parser/grammar/field.rs b/crates/apollo-parser/src/parser/grammar/field.rs
index 291ab08..b3bad49 100644
--- a/crates/apollo-parser/src/parser/grammar/field.rs
+++ b/crates/apollo-parser/src/parser/grammar/field.rs
@@ -9,7 +9,14 @@ use crate::{
 ///
 /// *Field*:
 ///     Alias? Name Arguments? Directives? SelectionSet?
-pub(crate) fn field(p: &mut Parser) {
+pub(crate) fn field(p: &mut Parser, mut count: usize) -> bool {
+    if count > 4096 {
+        p.err("recursion limit exceeded");
+        return false;
+    }
+
+    count += 1;
+
     let guard = p.start_node(SyntaxKind::FIELD);
 
     if let Some(TokenKind::Name) = p.peek() {
@@ -36,7 +43,7 @@ pub(crate) fn field(p: &mut Parser) {
     match p.peek() {
         Some(TokenKind::Name) => {
             guard.finish_node();
-            field(p)
+            return field(p, count);
         }
 
         Some(T!['}']) => {
@@ -44,6 +51,8 @@ pub(crate) fn field(p: &mut Parser) {
         }
         _ => guard.finish_node(),
     }
+
+    true
 }
 
 /// See: https://spec.graphql.org/October2021/#FieldsDefinition
diff --git a/crates/apollo-parser/src/parser/grammar/selection.rs b/crates/apollo-parser/src/parser/grammar/selection.rs
index 6608c3a..f62b337 100644
--- a/crates/apollo-parser/src/parser/grammar/selection.rs
+++ b/crates/apollo-parser/src/parser/grammar/selection.rs
@@ -50,8 +50,8 @@ pub(crate) fn selection(p: &mut Parser) {
                 break;
             }
             TokenKind::Name => {
-                field::field(p);
-                has_selection = true;
+                has_selection = field::field(p, 0);
+                // has_selection = true;
             }
             _ => {
                 if !has_selection {

(I'm not proposing this as a solution, but more as an illustration of a simple approach to bounding the recursion. Other options include making more use of the heap, trying to see if tail recursion makes a difference, etc...)

In general, it's probably acceptable to have the default behaviour of the parser to be "unbounded" (i.e.: use whatever the environment provides). It's also often acceptable (if not ideal) to have the parser fail with a stack overflow, because it's not part of a long running service and users can handle such failure manually.

For certain resource constrained scenarios, this is unacceptable, because service failure is very serious.

My proposal would be to consider introducing a bounded execution mode for the parser (or make bounded execution the single behaviour if desired). I'm not sure what the API for this would look like, so it would certainly require some discussion and I'm happy to participate in figuring out the best way to address this.

Summary:

• Parser assumes infinite resources
• Parser should not make this assumption either in bounded execution mode or for all invocations
• Main use case is embedding the parser in long running services that cannot fail

[garypen]

Some notes from discussion with @lrlna:

1. New parser constructor with_limits.
2. Counter exposed from parser as a getter. Maintains recursion depths for
   each limit (may only need one limit)
3. Expose this counter in router via prometheus.
4. Add Environment variable(s) to the router (undocumented at first) for limit(s) tuning.
5. Eventually graduate to configuration variable(s) when better understood.

also consider: dynamic/adaptive tuning if possible to simplify things for users.