Stack overflow when parsing SQL consisting of many imbalanced open parenthesis

This code segfaults with a stack overflow on both 0.9.0 from crates.io as well as loading from git (Version 35ef0ee)

use sqlparser::dialect::GenericDialect;
use sqlparser::parser::Parser;

fn main() {
 let sql = "(".repeat(1024);

 let dialect = GenericDialect {};

 let _ = Parser::parse_sql(&dialect, &sql);
}

[46bit]

Still an issue as of 0.15.0

[46bit]

@alamb Hi, pinging you as a maintainer. I want to use this crate, but I'd need to fix this issue to prevent users from triggering stack overflows. Hoping to get some feedback on whether you'd accept a fix.

Right now the Parser struct doesn't do any tracking of stack size. What I'm thinking is adding an extra depth: usize parameter to the various parse methods. Each method would return a ParserError if the recursion got deeper than a max_depth: Option<usize> field on Parser, preventing a stack overflow. The existing parse methods would then call out to the depth-limited variants supplying depth: 0.

Default behaviour would stay the same, but you could also prevent stack overflows by setting Parser.max_depth to a reasonable number.

Does that sound like a PR you'd be open to?

[alamb]

Hi @46bit -- Thank you for offering.

The idea of adding a max_depth parameter to the existing (non pub) methods seems reasonable to me. Hopefully the interface that most external users see would remain the same

Also, for what it is worth, I have seen rust stack sizes significantly larger in debug code than release code -- so the actual stack limit may be much higher in practice in release builds (though certainly would still exist)

[46bit]

@alamb Thanks for such a quick response, I appreciate it. I'll get working on the PR soonish and let you know how it goes :)

Might be worth looking at what serde_json does, since I know they definitely have a depth limit by default. Their limit is 128.

[alamb]

I think a default depth limit (that can be overridden) seems very reasonable to me and very much in the rust "safe by default" spirit

[46bit]

serde-json is using a check_recursion { ... } macro each time it recurses deeper: https://github.com/serde-rs/json/blob/master/src/de.rs#L1273-L1304. That works OK for them, they only use it 8 times. But sqlparser branches a lot more and I think we'd use it hundreds of times:

pub fn parse_statement(&mut self) -> Result<Statement, ParserError> {
 match self.next_token() {
 Token::Word(w) => match w.keyword {
 Keyword::DESCRIBE => Ok(check_recursion! { self.parse_explain(true)? }),
 Keyword::EXPLAIN => Ok(check_recursion! { self.parse_explain(false)? }),
 Keyword::ANALYZE => Ok(check_recursion! { self.parse_analyze()? }),
 [...]

Using it inside each function is pretty bad too, the diff would be huge:

pub fn parse_statement(&mut self) -> Result<Statement, ParserError> {
 check_recursion! {
 match self.next_token() {
 Token::Word(w) => match w.keyword {
 Keyword::DESCRIBE => Ok(self.parse_explain(true)?),
 Keyword::EXPLAIN => Ok(self.parse_explain(false)?),
 Keyword::ANALYZE => Ok(self.parse_analyze()?),

The ideal from my point of view would probably be a macro annotation on each function, like this:

#[check_recursion]
pub fn parse_statement(&mut self) -> Result<Statement, ParserError> {
 [...]
}

Those macros have to be defined in a separate crate, and I can't find anything like it that already exists. It'd be by far the cleanest approach but I don't know if you'd be OK with introducing a tiny new dependency (sqlparser-rs/proc-macros?) @alamb?

[alamb]

Those macros have to be defined in a separate crate

I don't understand why they need to be in a separate crate

Adding a macro to check recursion seems like a good idea to me.

[46bit]

I don't understand why they need to be in a separate crate

Specifically the function annotation. As I understand it those have to be proc macros, and proc macros have to be in a separate crate (fourth paragraph of https://doc.rust-lang.org/reference/procedural-macros.html.)

[alamb]

🤔 I am not sure how much time I have to devote to figuring out how to release multiple dependent crates in parallel for this crate

[nickolay]

I think we'd use it hundreds of times:

Why? I'd expect only a few productions of the SQL grammar to support recursion (e.g. subqueries, subexpressions, EXPLAIN-like commands that operate on other statements).

If we track the recursion depth only when recursing, maintaining the recursion counter manually shouldn't be much of a problem.

Also: were you really going to add an extra depth: usize parameter to the various parse methods or to the Parser struct itself?

[46bit]

Why? I'd expect only a few productions of the SQL grammar to support recursion

I'd intended to track the parser's call stack. Good point though.

[46bit]

I've opened an PR for this: #501. Feedback welcome.

[alamb]

Thank you -- I am a little behind on sqlparser reviews at the moment. I'll try and take a look over the weekend. Hopefully we can get some other community feedback as well

…

On Wed, May 18, 2022 at 1:18 PM Miki Mokrysz ***@***.***> wrote: I've opened an PR for this: #501 <#501>. Feedback welcome. — Reply to this email directly, view it on GitHub <#305 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADXZMPNPV2QLAZIBDW3CZTVKUQ4VANCNFSM42G57WBA> . You are receiving this because you were mentioned.Message ID: ***@***.***>