Segmentation fault when: [...] USING (*)

[patricklopdrup]

Hi,

The bug

A statement like this SELECT * FROM abc INNER JOIN xyz USING (*) results in a segmentation fault. But SELECT * FROM abc JOIN xyz USING (id) parses successfully. The parser does not seem to like the * in the USING.

This was found using grammar-based fuzzing.

---

How it was found, if you think that is fun :)

I am doing some analysis of grammar-based fuzzy testing for my master's thesis. For this I used AFL++ and created a grammar for SQL, which AFL++ then uses for its tests. Part of the grammar can be seen here. The highlights are a path to an SQL statement that crashes the parser:

(1) We start from <START> and go to <STATEMENTS>.
(2) Here it can only go to <STATEMENT> (singular)
(3) Here it has multiple options. For the crash-statement, it takes the <SELECT>
(4) Now it takes the <SELECT> with the <JOIN_CLAUSE>
(5) Here it takes the one with "USING"
(6) It takes the one with the * and goes to <COLUMNS_1>
(7) Here it takes the empty one

This could result in the following statement: SELECT v AS Y6 FROM b INNER JOIN pB USING (* );, which gives a segmentation fault.

[dey4ss]

Hi @patricklopdrup,

Thank you for submitting this issue. We are always super interested when people use our projects elsewhere. Seems like a super interesting topic you have for your thesis!

After a quick look, it seems like the problem could be here in line 1280/1287, where we access the column name even though the star expression does not have one:

sql-parser/src/parser/bison_parser.y

Lines 1274 to 1296 in c247124

	| table_ref_atomic opt_join_type JOIN table_ref_atomic USING '(' column_name ')' {
	$$ = new TableRef(kTableJoin);
	$$->join = new JoinDefinition();
	$$->join->type = (JoinType)$2;
	$$->join->left = $1;
	$$->join->right = $4;
	auto left_col = Expr::makeColumnRef(strdup($7->name));
	if ($7->alias) {
	left_col->alias = strdup($7->alias);
	}
	if ($1->getName()) {
	left_col->table = strdup($1->getName());
	}
	auto right_col = Expr::makeColumnRef(strdup($7->name));
	if ($7->alias) {
	right_col->alias = strdup($7->alias);
	}
	if ($4->getName()) {
	right_col->table = strdup($4->getName());
	}
	$$->join->condition = Expr::makeOpBinary(left_col, kOpEquals, right_col);
	delete $7;
	};

Handling this should be quite easy: It seems that allowing * in USING is non-standard. The standard only allows named columns if I read that correctly [1, p. 427, 428, 398, 195]:

<named columns join> ::=
 USING <left paren> <join column list> <right paren> [ AS <join correlation name> ]

<join column list> ::=
 <column name list>

<column name list> ::=
 <column name> [ { <comma> <column name> }... ]

<column name> ::=
 <identifier>

Oracle allows to reference all columns of a table using <table name>.* [2], but that seems to be an extension. SQL Server does not seem to support USING at all [3]. Our goal with the parser is to be mostly compliant to Postgres, which defines it like the following [4]:

USING ( join column list )

This join colums list is characterized as "a comma-separated list of the shared column names." Playing with DB Fiddle (Postgres 15) yields the following:

create table foo (a int, b int, c int);
create table bar (a int, b int, d int);

select * from foo inner join bar using (a);       -- fine
select * from foo inner join bar using (a, b);    -- fine
select * from foo inner join bar using ();        -- error: syntax error at or near ")"
select * from foo inner join bar using (a, b, c); -- error: column "c" specified in USING clause does not exist in right table
select * from foo inner join bar using (a, b, d); -- error: column "d" specified in USING clause does not exist in left table
select * from foo inner join bar using (*);       -- error: syntax error at or near "*"
select * from foo inner join bar using (foo.a);   -- error: syntax error at or near "."
select * from foo inner join bar using (foo.*);   -- error: syntax error at or near "."

So this seems just to be an underspecification in our grammar. Furthermore, we only allow a single column rather than multiple ones.

@Bouncner If you agree, I'll add support for specifying a list of columns. Note that the standard explicitly requires a column name rather than a column reference. That means only the column name is allowed, not [<schema name>.]<table name>.<column name> (and also rules out aliases in the USING list). However, this is a restriction we did not have before. How do we want to deal with that regarding backwards compatibility/forks?

Also noticed that SQL requires all columns that are in the USING list to be emitted only once (different to ON or implicit join with WHERE). E.g., with the example schemata above and:

insert into foo values (1, 1, 1);
insert into bar values (1, 1, -1);

select * from foo inner join bar using (a);

a 	b 	c 	b 	d
1 	1 	1 	1 	-1

(a emitted once, then foo.b, foo.c, bar.b, bar.d)

select * from foo inner join bar using (a, b);

a 	b 	c 	d
1 	1 	1 	-1

(a and b emitted once, then foo.c, bar.d)

Thus, we must also somehow distinguish between a join with a condition (ON) and a join with named columns (USING) so we can adjust the output expressions accordingly. Currently, we do not seem to to do that.

[1] Information technology – Database languages SQL – Part 2: Foundation (SQL/Foundation). ISO/IEC 9075-2:2023(E)
[2] https://docs.oracle.com/javadb/10.8.3.0/ref/rrefsqljusing.html
[3] https://learn.microsoft.com/en-us/sql/t-sql/queries/from-transact-sql?view=sql-server-ver16#syntax
[4] https://www.postgresql.org/docs/16/queries-table-expressions.html#QUERIES-JOIN

[Bouncner]

Totally agree on keeping the syntax Postgres'ish.

And allowing references is fine from my point of view. At least I don't see a good reason not to allow it. Do you?
Saw your comment in the PR. I think I get it.