From dde34150e8efe5251eb6efbc6a72da7daf262d97 Mon Sep 17 00:00:00 2001 From: charlieablett Date: Fri, 23 Aug 2019 02:17:38 +1200 Subject: 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 --- app/graphql/gitlab_schema.rb | 10 ++-- ...d-graphql-query-can-cause-denial-of-service.yml | 5 ++ .../graphql/query_analyzers/recursion_analyzer.rb | 58 ++++++++++++++++++++++ .../api/graphql/recursive-introspection.graphql | 57 +++++++++++++++++++++ spec/fixtures/api/graphql/recursive-query.graphql | 47 ++++++++++++++++++ .../graphql/small-recursive-introspection.graphql | 15 ++++++ spec/requests/api/graphql/gitlab_schema_spec.rb | 47 +++++++++++++++--- spec/support/helpers/graphql_helpers.rb | 17 +++++++ 8 files changed, 244 insertions(+), 12 deletions(-) create mode 100644 changelogs/unreleased/security-64519-nested-graphql-query-can-cause-denial-of-service.yml create mode 100644 lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb create mode 100644 spec/fixtures/api/graphql/recursive-introspection.graphql create mode 100644 spec/fixtures/api/graphql/recursive-query.graphql create mode 100644 spec/fixtures/api/graphql/small-recursive-introspection.graphql diff --git a/app/graphql/gitlab_schema.rb b/app/graphql/gitlab_schema.rb index 7edd14e48f7..c49c4d937c6 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 28676bb02f4..4560e7fec00 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 d86371d70b9..6f8cbd9f516 100644 --- a/spec/support/helpers/graphql_helpers.rb +++ b/spec/support/helpers/graphql_helpers.rb @@ -176,6 +176,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)) -- cgit v1.2.1 From 46ebc4db31f958e790ed56e7081b852d81048d48 Mon Sep 17 00:00:00 2001 From: charlieablett Date: Wed, 28 Aug 2019 15:47:29 +1200 Subject: Allow tests to ignore recursion --- lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb | 6 +++++- spec/support/helpers/graphql_helpers.rb | 5 +++++ 2 files changed, 10 insertions(+), 1 deletion(-) diff --git a/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb b/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb index 70d4672d079..ccf9e597307 100644 --- a/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb +++ b/lib/gitlab/graphql/query_analyzers/recursion_analyzer.rb @@ -45,13 +45,17 @@ module Gitlab def recursion_too_deep?(node_name, times_encountered) return if IGNORED_FIELDS.include?(node_name) - times_encountered > RECURSION_THRESHOLD + 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 + + def recursion_threshold + RECURSION_THRESHOLD + end end end end diff --git a/spec/support/helpers/graphql_helpers.rb b/spec/support/helpers/graphql_helpers.rb index 6f8cbd9f516..e62bce3f321 100644 --- a/spec/support/helpers/graphql_helpers.rb +++ b/spec/support/helpers/graphql_helpers.rb @@ -117,6 +117,7 @@ module GraphqlHelpers def all_graphql_fields_for(class_name, parent_types = Set.new) allow_unlimited_graphql_complexity allow_unlimited_graphql_depth + allow_high_graphql_recursion type = GitlabSchema.types[class_name.to_s] return "" unless type @@ -240,6 +241,10 @@ module GraphqlHelpers allow_any_instance_of(GitlabSchema).to receive(:max_depth).and_return nil allow(GitlabSchema).to receive(:max_query_depth).with(any_args).and_return nil end + + def allow_high_graphql_recursion + allow_any_instance_of(Gitlab::Graphql::QueryAnalyzers::RecursionAnalyzer).to receive(:recursion_threshold).and_return 1000 + end end # This warms our schema, doing this as part of loading the helpers to avoid -- cgit v1.2.1 From 6a836620037c9392dfe4c20306f6522d3e043dfd Mon Sep 17 00:00:00 2001 From: charlieablett Date: Wed, 23 Oct 2019 15:32:08 +1300 Subject: Tweak test to insulate against magic number changes --- spec/requests/api/graphql/gitlab_schema_spec.rb | 1 + 1 file changed, 1 insertion(+) diff --git a/spec/requests/api/graphql/gitlab_schema_spec.rb b/spec/requests/api/graphql/gitlab_schema_spec.rb index 4560e7fec00..c6ff459e3a5 100644 --- a/spec/requests/api/graphql/gitlab_schema_spec.rb +++ b/spec/requests/api/graphql/gitlab_schema_spec.rb @@ -65,6 +65,7 @@ describe 'GitlabSchema configurations' do context 'a deep recursive non-introspective query' do it 'fails due to recursion, complexity and depth' do + allow(GitlabSchema).to receive(:max_query_complexity).and_return 1 query = File.read(Rails.root.join('spec/fixtures/api/graphql/recursive-query.graphql')) post_graphql(query, current_user: nil) -- cgit v1.2.1