CVE-2022-37734: READY - Stop DOS attacks by making the lexer stop early on evil input. by bbakerman · Pull Request #2892 · graphql-java/graphql-java

The questions to be answered here is whether to track the whitespace and line comment channels or not. They are fast BUT they still take some time BUT not like the grammar channel does.

when we run the ParserBadSituations program with unlimited tokens the numbers for whitespace and comments are something like

Whitespace Bad Payloads(run #2)(1 of 15) - | query length 50020 | bad payloads 5000 | duration 4ms 
Whitespace Bad Payloads(run #2)(2 of 15) - | query length 100020 | bad payloads 10000 | duration 9ms 
Whitespace Bad Payloads(run #2)(3 of 15) - | query length 150020 | bad payloads 15000 | duration 16ms 
Whitespace Bad Payloads(run #2)(4 of 15) - | query length 200020 | bad payloads 20000 | duration 19ms 
Whitespace Bad Payloads(run #2)(5 of 15) - | query length 250020 | bad payloads 25000 | duration 28ms 
Whitespace Bad Payloads(run #2)(6 of 15) - | query length 300020 | bad payloads 30000 | duration 28ms 
Whitespace Bad Payloads(run #2)(7 of 15) - | query length 350020 | bad payloads 35000 | duration 50ms 
Whitespace Bad Payloads(run #2)(8 of 15) - | query length 400020 | bad payloads 40000 | duration 41ms 
Whitespace Bad Payloads(run #2)(9 of 15) - | query length 450020 | bad payloads 45000 | duration 46ms 
Whitespace Bad Payloads(run #2)(10 of 15) - | query length 500020 | bad payloads 50000 | duration 48ms 
Whitespace Bad Payloads(run #2)(11 of 15) - | query length 550020 | bad payloads 55000 | duration 55ms 
Whitespace Bad Payloads(run #2)(12 of 15) - | query length 600020 | bad payloads 60000 | duration 52ms 
Whitespace Bad Payloads(run #2)(13 of 15) - | query length 650020 | bad payloads 65000 | duration 87ms 
Whitespace Bad Payloads(run #2)(14 of 15) - | query length 700020 | bad payloads 70000 | duration 84ms 
Whitespace Bad Payloads(run #2) - finished | max time was 87 ms 
=======================

Comment Bad Payloads(run #2)(1 of 15) - | query length 75022 | bad payloads 5000 | duration 14ms 
Comment Bad Payloads(run #2)(2 of 15) - | query length 150022 | bad payloads 10000 | duration 25ms 
Comment Bad Payloads(run #2)(3 of 15) - | query length 225022 | bad payloads 15000 | duration 31ms 
Comment Bad Payloads(run #2)(4 of 15) - | query length 300022 | bad payloads 20000 | duration 34ms 
Comment Bad Payloads(run #2)(5 of 15) - | query length 375022 | bad payloads 25000 | duration 26ms 
Comment Bad Payloads(run #2)(6 of 15) - | query length 450022 | bad payloads 30000 | duration 25ms 
Comment Bad Payloads(run #2)(7 of 15) - | query length 525022 | bad payloads 35000 | duration 32ms 
Comment Bad Payloads(run #2)(8 of 15) - | query length 600022 | bad payloads 40000 | duration 37ms 
Comment Bad Payloads(run #2)(9 of 15) - | query length 675022 | bad payloads 45000 | duration 48ms 
Comment Bad Payloads(run #2)(10 of 15) - | query length 750022 | bad payloads 50000 | duration 51ms 
Comment Bad Payloads(run #2)(11 of 15) - | query length 825022 | bad payloads 55000 | duration 48ms 
Comment Bad Payloads(run #2)(12 of 15) - | query length 900022 | bad payloads 60000 | duration 48ms 
Comment Bad Payloads(run #2)(13 of 15) - | query length 975022 | bad payloads 65000 | duration 52ms 
Comment Bad Payloads(run #2)(14 of 15) - | query length 1050022 | bad payloads 70000 | duration 70ms 
Comment Bad Payloads(run #2) - finished | max time was 70 ms 
=======================

So it starts to creep up BUT nothing like the grammar file which is 2 orders of magnitude slower!

This is what is discovered debugging. Channel 0 (grammar tokens) get put into the parse tree and this is quite costly when you have 10s of 1000s of them. The cost is in the lexing AND in the parse tree building so it makes total sense for them to be strongly limited.

However there is 2 other channels - whitespace and line comments (# comments). Now it turns out that they are NOT anywhere near as costly. The whitespace (while lexed as single tokens per whitespace character) are accumulated (burns some CPU and memory since each becomes a Token) but they are not placed into the parse tree - but rather accumulated. As you can see above it happens relatively fast.

And then when the parser is called back - this line means we throw them away.

    private void addIgnoredChars(ParserRuleContext ctx, NodeBuilder nodeBuilder) {
        if (!parserOptions.isCaptureIgnoredChars()) {
            return;
        }

So they accumulate fast enough and then are never used.

The line comments are also accumulated, not as fast because they are actually used in the parser tree.

    protected List<Comment> getComments(ParserRuleContext ctx) {
        if (!parserOptions.isCaptureLineComments()) {
            return NO_COMMENTS;
        }

By default (even for queries) we keep the line comments. So an attack vector is to send in

# lots of comments
# lots of comments
# lots of comments
# lots of comments
query x { f }

However as the numbers above show even this is fast-ish.

My fear is around whitespace. That 15,000 whitespace characters will catch some queries out. I mean some queries might be say 512KB in size - they will likely be below 15,000 grammar tokens BUT could they be 1/3 whitespace - (170,000 whitespace chars say) - yeah why not.

So this PR as it is (counting whitespace the same as grammar tokens or line comments) will stop them sending in such a query.

I think this leads us towards having 2 max values in ParserOptions - the max tokens and a max whitespace number.