Check for recursion and fail if too recursive

- List all overly-recursive fields
- Reduce recursion threshold to 2
- Add test for not-recursive-enough query
- Use reusable methods in tests
- Add changelog
- Set changeable acceptable recursion level
- Add error check test helpers

8 files changed, 244 insertions, 12 deletions

diff --git a/app/graphql/gitlab_schema.rb b/app/graphql/gitlab_schema.rb
index 4c8612c8f2e..1899278ff3c 100644
--- a/app/graphql/gitlab_schema.rb
+++ b/app/graphql/gitlab_schema.rb
@@ -18,15 +18,15 @@ class GitlabSchema < GraphQL::Schema
   use Gitlab::Graphql::GenericTracing
 
   query_analyzer Gitlab::Graphql::QueryAnalyzers::LoggerAnalyzer.new
-
-  query(Types::QueryType)
-
-  default_max_page_size 100
+  query_analyzer Gitlab::Graphql::QueryAnalyzers::RecursionAnalyzer.new
 
   max_complexity DEFAULT_MAX_COMPLEXITY
   max_depth DEFAULT_MAX_DEPTH
 
-  mutation(Types::MutationType)
+  query Types::QueryType
+  mutation Types::MutationType
+
+  default_max_page_size 100
 
   class << self
     def multiplex(queries, **kwargs)
diff --git a/changelogs/unreleased/security-64519-nested-graphql-query-can-cause-denial-of-service.yml b/changelogs/unreleased/security-64519-nested-graphql-query-can-cause-denial-of-service.yml
new file mode 100644
index 00000000000..5ce37b0d032
--- /dev/null
+++ b/changelogs/unreleased/security-64519-nested-graphql-query-can-cause-denial-of-service.yml
@@ -0,0 +1,5 @@
+---
+title: Analyze incoming GraphQL queries and check for recursion
+merge_request:
+author:
+type: security
diff --git a/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb b/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb
new file mode 100644
index 00000000000..70d4672d079
--- /dev/null
+++ b/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb
@@ -0,0 +1,58 @@
+# frozen_string_literal: true
+
+# Recursive queries, with relatively low effort, can quickly spiral out of control exponentially
+# and may not be picked up by depth and complexity alone.
+module Gitlab
+  module Graphql
+    module QueryAnalyzers
+      class RecursionAnalyzer
+        IGNORED_FIELDS = %w(node edges ofType).freeze
+        RECURSION_THRESHOLD = 2
+
+        def initial_value(query)
+          {
+              recurring_fields: {}
+          }
+        end
+
+        def call(memo, visit_type, irep_node)
+          return memo if skip_node?(irep_node)
+
+          node_name = irep_node.ast_node.name
+          times_encountered = memo[node_name] || 0
+
+          if visit_type == :enter
+            times_encountered += 1
+            memo[:recurring_fields][node_name] = times_encountered if recursion_too_deep?(node_name, times_encountered)
+          else
+            times_encountered -= 1
+          end
+
+          memo[node_name] = times_encountered
+          memo
+        end
+
+        def final_value(memo)
+          recurring_fields = memo[:recurring_fields]
+          recurring_fields = recurring_fields.select { |k, v| recursion_too_deep?(k, v) }
+          if recurring_fields.any?
+            GraphQL::AnalysisError.new("Recursive query - too many of fields '#{recurring_fields}' detected in single branch of the query")
+          end
+        end
+
+        private
+
+        def recursion_too_deep?(node_name, times_encountered)
+          return if IGNORED_FIELDS.include?(node_name)
+
+          times_encountered > RECURSION_THRESHOLD
+        end
+
+        def skip_node?(irep_node)
+          ast_node = irep_node.ast_node
+          !ast_node.is_a?(GraphQL::Language::Nodes::Field) || ast_node.selections.empty?
+        end
+      end
+    end
+  end
+end
diff --git a/spec/fixtures/api/graphql/recursive-introspection.graphql b/spec/fixtures/api/graphql/recursive-introspection.graphql
new file mode 100644
index 00000000000..db970bb14b6
--- /dev/null
+++ b/spec/fixtures/api/graphql/recursive-introspection.graphql
@@ -0,0 +1,57 @@
+query allSchemaTypes {
+  __schema {
+    types {
+      fields {
+        type{
+          fields {
+            type {
+              fields {
+                type {
+                  fields {
+                    type {
+                      fields {
+                        type {
+                          fields {
+                            type {
+                              fields {
+                                type {
+                                  fields {
+                                    type {
+                                      fields {
+                                        type {
+                                          fields {
+                                            type {
+                                              fields {
+                                                type {
+                                                  fields {
+                                                    type {
+                                                      fields {
+                                                        name
+                                                      }
+                                                    }
+                                                  }
+                                                }
+                                              }
+                                            }
+                                          }
+                                        }
+                                      }
+                                    }
+                                  }
+                                }
+                              }
+                            }
+                          }
+                        }
+                      }
+                    }
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+}
\ No newline at end of file
diff --git a/spec/fixtures/api/graphql/recursive-query.graphql b/spec/fixtures/api/graphql/recursive-query.graphql
new file mode 100644
index 00000000000..d1616c4de6e
--- /dev/null
+++ b/spec/fixtures/api/graphql/recursive-query.graphql
@@ -0,0 +1,47 @@
+{
+  project(fullPath: "gitlab-org/gitlab-ce") {
+    group {
+      projects {
+        edges {
+          node {
+            group {
+              projects {
+                edges {
+                  node {
+                    group {
+                      projects {
+                        edges {
+                          node {
+                            group {
+                              projects {
+                                edges {
+                                  node {
+                                    group {
+                                      projects {
+                                        edges {
+                                          node {
+                                            group {
+                                              description
+                                            }
+                                          }
+                                        }
+                                      }
+                                    }
+                                  }
+                                }
+                              }
+                            }
+                          }
+                        }
+                      }
+                    }
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/spec/fixtures/api/graphql/small-recursive-introspection.graphql b/spec/fixtures/api/graphql/small-recursive-introspection.graphql
new file mode 100644
index 00000000000..1025043b474
--- /dev/null
+++ b/spec/fixtures/api/graphql/small-recursive-introspection.graphql
@@ -0,0 +1,15 @@
+query allSchemaTypes {
+  __schema {
+    types {
+      fields {
+        type {
+          fields {
+            type {
+              name
+            }
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/spec/requests/api/graphql/gitlab_schema_spec.rb b/spec/requests/api/graphql/gitlab_schema_spec.rb
index e1eb7c7f738..1f2bc67a9d2 100644
--- a/spec/requests/api/graphql/gitlab_schema_spec.rb
+++ b/spec/requests/api/graphql/gitlab_schema_spec.rb
@@ -13,7 +13,7 @@ describe 'GitlabSchema configurations' do
 
           subject
 
-          expect(graphql_errors.flatten.first['message']).to include('which exceeds max complexity of 1')
+          expect_graphql_errors_to_include /which exceeds max complexity of 1/
         end
       end
     end
@@ -21,12 +21,11 @@ describe 'GitlabSchema configurations' do
     describe '#max_depth' do
       context 'when query depth is too high' do
         it 'shows error' do
-          errors = { "message" => "Query has depth of 2, which exceeds max depth of 1" }
           allow(GitlabSchema).to receive(:max_query_depth).and_return 1
 
           subject
 
-          expect(graphql_errors.flatten).to include(errors)
+          expect_graphql_errors_to_include /exceeds max depth/
         end
       end
 
@@ -36,7 +35,41 @@ describe 'GitlabSchema configurations' do
 
           subject
 
-          expect(Array.wrap(graphql_errors).compact).to be_empty
+          expect_graphql_errors_to_be_empty
+        end
+      end
+    end
+  end
+
+  context 'depth, complexity and recursion checking' do
+    context 'unauthenticated recursive queries' do
+      context 'a not-quite-recursive-enough introspective query' do
+        it 'succeeds' do
+          query = File.read(Rails.root.join('spec/fixtures/api/graphql/small-recursive-introspection.graphql'))
+
+          post_graphql(query, current_user: nil)
+
+          expect_graphql_errors_to_be_empty
+        end
+      end
+
+      context 'a deep but simple recursive introspective query' do
+        it 'fails due to recursion' do
+          query = File.read(Rails.root.join('spec/fixtures/api/graphql/recursive-introspection.graphql'))
+
+          post_graphql(query, current_user: nil)
+
+          expect_graphql_errors_to_include [/Recursive query/]
+        end
+      end
+
+      context 'a deep recursive non-introspective query' do
+        it 'fails due to recursion, complexity and depth' do
+          query = File.read(Rails.root.join('spec/fixtures/api/graphql/recursive-query.graphql'))
+
+          post_graphql(query, current_user: nil)
+
+          expect_graphql_errors_to_include [/Recursive query/, /exceeds max complexity/, /exceeds max depth/]
         end
       end
     end
@@ -86,7 +119,7 @@ describe 'GitlabSchema configurations' do
         # Expect errors for each query
         expect(graphql_errors.size).to eq(3)
         graphql_errors.each do |single_query_errors|
-          expect(single_query_errors.first['message']).to include('which exceeds max complexity of 4')
+          expect_graphql_errors_to_include(/which exceeds max complexity of 4/)
         end
       end
     end
@@ -103,12 +136,12 @@ describe 'GitlabSchema configurations' do
   end
 
   context 'when IntrospectionQuery' do
-    it 'is not too complex' do
+    it 'is not too complex nor recursive' do
       query = File.read(Rails.root.join('spec/fixtures/api/graphql/introspection.graphql'))
 
       post_graphql(query, current_user: nil)
 
-      expect(graphql_errors).to be_nil
+      expect_graphql_errors_to_be_empty
     end
   end
 
diff --git a/spec/support/helpers/graphql_helpers.rb b/spec/support/helpers/graphql_helpers.rb
index 4d2ad165fd6..69bf1f0f3fa 100644
--- a/spec/support/helpers/graphql_helpers.rb
+++ b/spec/support/helpers/graphql_helpers.rb
@@ -213,6 +213,23 @@ module GraphqlHelpers
     end
   end
 
+  def expect_graphql_errors_to_include(regexes_to_match)
+    raise "No errors. Was expecting to match #{regexes_to_match}" if graphql_errors.nil? || graphql_errors.empty?
+
+    error_messages = flattened_errors.collect { |error_hash| error_hash["message"] }
+    Array.wrap(regexes_to_match).flatten.each do |regex|
+      expect(error_messages).to include a_string_matching regex
+    end
+  end
+
+  def expect_graphql_errors_to_be_empty
+    expect(flattened_errors).to be_empty
+  end
+
+  def flattened_errors
+    Array.wrap(graphql_errors).flatten.compact
+  end
+
   # Raises an error if no response is found
   def graphql_mutation_response(mutation_name)
     graphql_data.fetch(GraphqlHelpers.fieldnamerize(mutation_name))