Best way to stop the lexer from lexing too much

[bbakerman]

The graphql-java project uses ANTLR to represent its graphql grammar.

We discovered an Denial OF Service attack that involves putting pathological query text into play and this would cause the parser to spend an inordimate amount of time parsing invalid documents

query {
   f @lol@lol@lol   # <-- 1000s of these say
}

We fixed it the first time by putting ParseTreeListener into the mix and counting how many tokens we encounter - we give up after a certain number.

See ParseTreeListener

However we discovered another mechanism to DOS the process and that involves the Lexer generated by ANTLR. The Lexer is by design greedy and certain grammar syntaxes means it will look WAY ahead for all the tokens it can to satisfy a rule.

This meant that CPU was being burnt (> 30 seconds worth) reading ahead building context for the parse tree without the parser itself being invoke and hence our limiting ParseTreeListener

We solved this by creating a wrapping org.antlr.v4.runtime.TokenSource around the base lexer and stopping the parsing when a certain number of tokens has been asked for.

graphql-java/graphql-java#2892

So my question to the group is

• what is the best way to limit lexer activity
• is there a callback mechanism for the lexer to allow it to be limited
• if there isn't, should there be one
• Have others encountered this problem?

[kaby76]

There is an equivalence between a parse tree listener and an action in a parser grammar. Since lexer grammars don't have listeners, you could modify the grammar to add an action that checks for too many iterations across a '+'-operator or '*'-operator or stack depth. However, that would require a modification to the grammar.