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