Resource exhaustion exploit when parsing queries

[tadhglewis]

Re-posting here as advised in apollographql/apollo-server#7688. Without digging into source code I'm not exactly sure which part of graphql-js is causing this.

Issue Description

We've identified a potential resource exhaustion vector which has a significant impact on our CPU and response times. We're currently experiencing this on AS 3 however we're able to reproduce on AS 4.

We have a custom query complexity calc plugin which is intended to handle this scenario and others however it seems before we get to didResolveOperation event/stage, there is some processing that takes a long time.

I'm assuming this is an underlying dependancy in Apollo however I'm not 100% sure so any ideas or suggestions on how we can mitigate this would be great.

Link to Reproduction

https://github.com/tadhglewis/apollo-koa-minimal

Reproduction Steps

1. pnpm install && pnpm start
2. Run

curl \
--data "{\"query\":\"{ $(python3 -c "print('%s' % ('__typename ' * 1000))")}\"}" \
--header 'Content-Type: application/json' \
--include \
--request POST \
https://example.com/graphql

This will take ~2.5s and increase to ~21s if you change the number of __typename to 3000

Notes

• On subsequent requests there seems to be some caching and response time goes to ~10ms however if you change the number of __typename by one it will bypass this
• This isn't limited to __typename, it can also be hit when using hello and I imagine introspection as well

[trevor-scheer]

👋 Apollo Server maintainer here. Going to follow along on this issue to track updates. For @IvanGoncharov 's sake it would be nice to minimize the reproduction to exclude apollo server (and add certainty that it's a graphql-js problem).

[tadhglewis]

@trevor-scheer I'll look at just testing against graphql-js this week and post an update

[tadhglewis]

I've added a minimal graphql-js example in the same repo. You can run it using node graphql-js.mjs.

The slow parsing performance is still observed here

// 1000 __typename query = Took 1999.3179998397827 milliseconds
// 2000 __typename query = Took 8064.870334148407 milliseconds

We've also reproduced this in a real world scenario on a API and due to it's impact, I consider it a critical issue.

[AaronMoat]

It looks like (nearly) all the time is spent in OverlappingFieldsCanBeMergedRule.

[AaronMoat]

Ran a bisect, discovered the performance degradation was 5caff03 (#3457). Raised #3958

cc: @IvanGoncharov

[AaronMoat]

Raised #3967 for 16

[AaronMoat]

@IvanGoncharov or others on this thread. Can we please organise a release for v16? As per #3967.

I would argue this issue should not be marked complete until consumers can use a fixed version of this security/performance hole, on a stable (non-beta) release channel.