public inbox for [email protected]
help / color / mirror / Atom feedStack overflow issue
15+ messages / 6 participants
[nested] [flat]
* Stack overflow issue
@ 2022-08-24 09:51 Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 13:58 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-24 16:23 ` Re: Stack overflow issue Tom Lane <[email protected]>
0 siblings, 3 replies; 15+ messages in thread
From: Егор Чиндяскин @ 2022-08-24 09:51 UTC (permalink / raw)
To: [email protected]
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%40mai...
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
@ 2022-08-24 10:07 ` mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2 siblings, 1 reply; 15+ messages in thread
From: mahendrakar s @ 2022-08-24 10:07 UTC (permalink / raw)
To: Егор Чиндяскин <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
Hi,
Can we have a parameter to control the recursion depth in these cases to
avoid crashes?
Just a thought.
Thanks,
Mahendrakar.
On Wed, 24 Aug, 2022, 3:21 pm Егор Чиндяскин, <[email protected]> wrote:
> 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%40mai...
>
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
@ 2022-08-24 10:49 ` Alvaro Herrera <[email protected]>
2022-08-24 10:59 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
0 siblings, 2 replies; 15+ messages in thread
From: Alvaro Herrera @ 2022-08-24 10:49 UTC (permalink / raw)
To: mahendrakar s <[email protected]>; +Cc: Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
On 2022-Aug-24, mahendrakar s wrote:
> Hi,
> Can we have a parameter to control the recursion depth in these cases to
> avoid crashes?
We already have one (max_stack_depth). The problem is lack of calling
the control function in a few places.
--
Álvaro Herrera 48°01'N 7°57'E — https://www.EnterpriseDB.com/
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
@ 2022-08-24 10:59 ` mahendrakar s <[email protected]>
1 sibling, 0 replies; 15+ messages in thread
From: mahendrakar s @ 2022-08-24 10:59 UTC (permalink / raw)
To: Alvaro Herrera <[email protected]>; +Cc: Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
Thanks.
On Wed, 24 Aug, 2022, 4:19 pm Alvaro Herrera, <[email protected]>
wrote:
> On 2022-Aug-24, mahendrakar s wrote:
>
> > Hi,
> > Can we have a parameter to control the recursion depth in these cases to
> > avoid crashes?
>
> We already have one (max_stack_depth). The problem is lack of calling
> the control function in a few places.
>
> --
> Álvaro Herrera 48°01'N 7°57'E —
> https://www.EnterpriseDB.com/
>
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
@ 2022-08-24 11:12 ` Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
1 sibling, 1 reply; 15+ messages in thread
From: Richard Guo @ 2022-08-24 11:12 UTC (permalink / raw)
To: Alvaro Herrera <[email protected]>; +Cc: mahendrakar s <[email protected]>; Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
On Wed, Aug 24, 2022 at 6:49 PM Alvaro Herrera <[email protected]>
wrote:
> On 2022-Aug-24, mahendrakar s wrote:
>
> > Hi,
> > Can we have a parameter to control the recursion depth in these cases to
> > avoid crashes?
>
> We already have one (max_stack_depth). The problem is lack of calling
> the control function in a few places.
Thanks Egor and Alexander for the work! I think we can just add
check_stack_depth checks in these cases.
Thanks
Richard
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
@ 2022-08-24 11:54 ` Richard Guo <[email protected]>
2022-08-24 12:59 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 14:03 ` Re: Stack overflow issue Tom Lane <[email protected]>
0 siblings, 2 replies; 15+ messages in thread
From: Richard Guo @ 2022-08-24 11:54 UTC (permalink / raw)
To: Alvaro Herrera <[email protected]>; +Cc: mahendrakar s <[email protected]>; Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
On Wed, Aug 24, 2022 at 7:12 PM Richard Guo <[email protected]> wrote:
>
> On Wed, Aug 24, 2022 at 6:49 PM Alvaro Herrera <[email protected]>
> wrote:
>
>> On 2022-Aug-24, mahendrakar s wrote:
>>
>> > Hi,
>> > Can we have a parameter to control the recursion depth in these cases to
>> > avoid crashes?
>>
>> We already have one (max_stack_depth). The problem is lack of calling
>> the control function in a few places.
>
>
> Thanks Egor and Alexander for the work! I think we can just add
> check_stack_depth checks in these cases.
>
Attached adds the checks in these places. But I'm not sure about the
snowball case. Can we edit src/backend/snowball/libstemmer/*.c directly?
Thanks
Richard
Attachments:
[application/octet-stream] v1-0001-add-check_stack_depth-in-more-places.patch (3.7K, ../../CAMbWs48iswb9cXXnq1Ocy0WLdov__1eR=qenRP+a3x1PJiphJg@mail.gmail.com/3-v1-0001-add-check_stack_depth-in-more-places.patch)
download | inline diff:
From 5c23f9cd9c16c605acdc36393e1a31e8c9b97a93 Mon Sep 17 00:00:00 2001
From: pgsql-guo <[email protected]>
Date: Wed, 24 Aug 2022 11:45:35 +0000
Subject: [PATCH v1] add check_stack_depth in more places
---
src/backend/regex/regc_lex.c | 3 +++
src/backend/snowball/libstemmer/stem_UTF_8_turkish.c | 3 +++
src/backend/tsearch/spell.c | 4 ++++
src/backend/utils/adt/geo_ops.c | 3 +++
src/backend/utils/adt/like_support.c | 4 ++++
5 files changed, 17 insertions(+)
diff --git a/src/backend/regex/regc_lex.c b/src/backend/regex/regc_lex.c
index 45727ffa01..1169e731a1 100644
--- a/src/backend/regex/regc_lex.c
+++ b/src/backend/regex/regc_lex.c
@@ -201,6 +201,9 @@ next(struct vars *v)
{
chr c;
+ /* since this function recurses, it could be driven to stack overflow */
+ check_stack_depth();
+
/* errors yield an infinite sequence of failures */
if (ISERR())
return 0; /* the error has set nexttype to EOS */
diff --git a/src/backend/snowball/libstemmer/stem_UTF_8_turkish.c b/src/backend/snowball/libstemmer/stem_UTF_8_turkish.c
index 3d04032787..9254574525 100644
--- a/src/backend/snowball/libstemmer/stem_UTF_8_turkish.c
+++ b/src/backend/snowball/libstemmer/stem_UTF_8_turkish.c
@@ -1,6 +1,7 @@
/* Generated by Snowball 2.2.0 - https://snowballstem.org/ */
#include "header.h"
+#include "miscadmin.h"
#ifdef __cplusplus
extern "C" {
@@ -1156,6 +1157,8 @@ lab0:
}
static int r_stem_suffix_chain_before_ki(struct SN_env * z) {
+ /* since this function recurses, it could be driven to stack overflow */
+ check_stack_depth();
z->ket = z->c;
{ int ret = r_mark_ki(z);
if (ret <= 0) return ret;
diff --git a/src/backend/tsearch/spell.c b/src/backend/tsearch/spell.c
index f07321b61d..edd2fbbd3a 100644
--- a/src/backend/tsearch/spell.c
+++ b/src/backend/tsearch/spell.c
@@ -63,6 +63,7 @@
#include "postgres.h"
#include "catalog/pg_collation.h"
+#include "miscadmin.h"
#include "tsearch/dicts/spell.h"
#include "tsearch/ts_locale.h"
#include "utils/memutils.h"
@@ -2400,6 +2401,9 @@ SplitToVariants(IspellDict *Conf, SPNode *snode, SplitVar *orig, char *word, int
char *notprobed;
int compoundflag = 0;
+ /* since this function recurses, it could be driven to stack overflow */
+ check_stack_depth();
+
notprobed = (char *) palloc(wordlen);
memset(notprobed, 1, wordlen);
var = CopyVar(orig, 1);
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index b79705f8b3..535301a218 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -3833,6 +3833,9 @@ lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
bool res = true,
intersection = false;
+ /* since this function recurses, it could be driven to stack overflow */
+ check_stack_depth();
+
t.p[0] = *a;
t.p[1] = *b;
s.p[0] = poly->p[(start == 0) ? (poly->npts - 1) : (start - 1)];
diff --git a/src/backend/utils/adt/like_support.c b/src/backend/utils/adt/like_support.c
index 65a57fc3c4..2d3aaaaf6b 100644
--- a/src/backend/utils/adt/like_support.c
+++ b/src/backend/utils/adt/like_support.c
@@ -44,6 +44,7 @@
#include "catalog/pg_statistic.h"
#include "catalog/pg_type.h"
#include "mb/pg_wchar.h"
+#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/supportnodes.h"
@@ -1364,6 +1365,9 @@ regex_selectivity_sub(const char *patt, int pattlen, bool case_insensitive)
int paren_pos = 0; /* dummy init to keep compiler quiet */
int pos;
+ /* since this function recurses, it could be driven to stack overflow */
+ check_stack_depth();
+
for (pos = 0; pos < pattlen; pos++)
{
if (patt[pos] == '(')
--
2.25.1
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
@ 2022-08-24 12:59 ` mahendrakar s <[email protected]>
1 sibling, 0 replies; 15+ messages in thread
From: mahendrakar s @ 2022-08-24 12:59 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Alvaro Herrera <[email protected]>; Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
Hi Richard,
Patch is looking good to me. Would request others to take a look at it as
well.
Thanks,
Mahendrakar.
On Wed, 24 Aug 2022 at 17:24, Richard Guo <[email protected]> wrote:
>
> On Wed, Aug 24, 2022 at 7:12 PM Richard Guo <[email protected]>
> wrote:
>
>>
>> On Wed, Aug 24, 2022 at 6:49 PM Alvaro Herrera <[email protected]>
>> wrote:
>>
>>> On 2022-Aug-24, mahendrakar s wrote:
>>>
>>> > Hi,
>>> > Can we have a parameter to control the recursion depth in these cases
>>> to
>>> > avoid crashes?
>>>
>>> We already have one (max_stack_depth). The problem is lack of calling
>>> the control function in a few places.
>>
>>
>> Thanks Egor and Alexander for the work! I think we can just add
>> check_stack_depth checks in these cases.
>>
>
> Attached adds the checks in these places. But I'm not sure about the
> snowball case. Can we edit src/backend/snowball/libstemmer/*.c directly?
>
> Thanks
> Richard
>
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
@ 2022-08-24 14:03 ` Tom Lane <[email protected]>
2022-08-24 17:30 ` Re: Stack overflow issue Tom Lane <[email protected]>
1 sibling, 1 reply; 15+ messages in thread
From: Tom Lane @ 2022-08-24 14:03 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Alvaro Herrera <[email protected]>; mahendrakar s <[email protected]>; Егор Чиндяскин <[email protected]>; PostgreSQL Hackers <[email protected]>
Richard Guo <[email protected]> writes:
> Attached adds the checks in these places. But I'm not sure about the
> snowball case. Can we edit src/backend/snowball/libstemmer/*.c directly?
No, that file is generated code, as it says right at the top.
I think most likely we should report this to Snowball upstream
and see what they think is an appropriate fix.
regards, tom lane
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 14:03 ` Re: Stack overflow issue Tom Lane <[email protected]>
@ 2022-08-24 17:30 ` Tom Lane <[email protected]>
2022-08-30 15:02 ` Re: Stack overflow issue Tom Lane <[email protected]>
0 siblings, 1 reply; 15+ messages in thread
From: Tom Lane @ 2022-08-24 17:30 UTC (permalink / raw)
To: Егор Чиндяскин <[email protected]>; +Cc: Richard Guo <[email protected]>; Alvaro Herrera <[email protected]>; mahendrakar s <[email protected]>; PostgreSQL Hackers <[email protected]>
I wrote:
> I think most likely we should report this to Snowball upstream
> and see what they think is an appropriate fix.
Done at [1], and I pushed the other fixes. Thanks again for the report!
regards, tom lane
[1] https://lists.tartarus.org/pipermail/snowball-discuss/2022-August/001734.html
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 14:03 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-24 17:30 ` Re: Stack overflow issue Tom Lane <[email protected]>
@ 2022-08-30 15:02 ` Tom Lane <[email protected]>
2022-08-30 22:57 ` Re: Stack overflow issue Tom Lane <[email protected]>
0 siblings, 1 reply; 15+ messages in thread
From: Tom Lane @ 2022-08-30 15:02 UTC (permalink / raw)
To: PostgreSQL Hackers <[email protected]>; +Cc: Егор Чиндяскин <[email protected]>; Richard Guo <[email protected]>; Alvaro Herrera <[email protected]>; mahendrakar s <[email protected]>
I wrote:
>> I think most likely we should report this to Snowball upstream
>> and see what they think is an appropriate fix.
> Done at [1], and I pushed the other fixes. Thanks again for the report!
The upstream recommendation, which seems pretty sane to me, is to
simply reject any string exceeding some threshold length as not
possibly being a word. Apparently it's common to use thresholds
as small as 64 bytes, but in the attached I used 1000 bytes.
regards, tom lane
Attachments:
[text/x-diff] limit-length-of-strings-passed-to-snowball.patch (1.2K, ../../[email protected]/2-limit-length-of-strings-passed-to-snowball.patch)
download | inline diff:
diff --git a/src/backend/snowball/dict_snowball.c b/src/backend/snowball/dict_snowball.c
index 68c9213f69..aaf4ff72b6 100644
--- a/src/backend/snowball/dict_snowball.c
+++ b/src/backend/snowball/dict_snowball.c
@@ -272,11 +272,25 @@ dsnowball_lexize(PG_FUNCTION_ARGS)
DictSnowball *d = (DictSnowball *) PG_GETARG_POINTER(0);
char *in = (char *) PG_GETARG_POINTER(1);
int32 len = PG_GETARG_INT32(2);
- char *txt = lowerstr_with_len(in, len);
TSLexeme *res = palloc0(sizeof(TSLexeme) * 2);
+ char *txt;
+ /*
+ * Reject strings exceeding 1000 bytes, as they're surely not words in any
+ * human language. This restriction avoids wasting cycles on stuff like
+ * base64-encoded data, and it protects us against possible inefficiency
+ * or misbehavior in the stemmers (for example, the Turkish stemmer has an
+ * indefinite recursion so it can crash on long-enough strings).
+ */
+ if (len <= 0 || len > 1000)
+ PG_RETURN_POINTER(res);
+
+ txt = lowerstr_with_len(in, len);
+
+ /* txt is probably not zero-length now, but we'll check anyway */
if (*txt == '\0' || searchstoplist(&(d->stoplist), txt))
{
+ /* empty or stopword, so reject */
pfree(txt);
}
else
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 14:03 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-24 17:30 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-30 15:02 ` Re: Stack overflow issue Tom Lane <[email protected]>
@ 2022-08-30 22:57 ` Tom Lane <[email protected]>
2022-08-31 02:38 ` Re: Stack overflow issue Richard Guo <[email protected]>
0 siblings, 1 reply; 15+ messages in thread
From: Tom Lane @ 2022-08-30 22:57 UTC (permalink / raw)
To: PostgreSQL Hackers <[email protected]>; +Cc: Егор Чиндяскин <[email protected]>; Richard Guo <[email protected]>; Alvaro Herrera <[email protected]>; mahendrakar s <[email protected]>
I wrote:
> The upstream recommendation, which seems pretty sane to me, is to
> simply reject any string exceeding some threshold length as not
> possibly being a word. Apparently it's common to use thresholds
> as small as 64 bytes, but in the attached I used 1000 bytes.
On further thought: that coding treats anything longer than 1000
bytes as a stopword, but maybe we should just accept it unmodified.
The manual says "A Snowball dictionary recognizes everything, whether
or not it is able to simplify the word". While "recognizes" formally
includes the case of "recognizes as a stopword", people might find
this behavior surprising. We could alternatively do it as attached,
which accepts overlength words but does nothing to them except
case-fold. This is closer to the pre-patch behavior, but gives up
the opportunity to avoid useless downstream processing of long words.
regards, tom lane
Attachments:
[text/x-diff] limit-length-of-strings-passed-to-snowball-2.patch (1.2K, ../../[email protected]/2-limit-length-of-strings-passed-to-snowball-2.patch)
download | inline diff:
diff --git a/src/backend/snowball/dict_snowball.c b/src/backend/snowball/dict_snowball.c
index 68c9213f69..1d5dfff5a0 100644
--- a/src/backend/snowball/dict_snowball.c
+++ b/src/backend/snowball/dict_snowball.c
@@ -275,8 +275,24 @@ dsnowball_lexize(PG_FUNCTION_ARGS)
char *txt = lowerstr_with_len(in, len);
TSLexeme *res = palloc0(sizeof(TSLexeme) * 2);
- if (*txt == '\0' || searchstoplist(&(d->stoplist), txt))
+ /*
+ * Do not pass strings exceeding 1000 bytes to the stemmer, as they're
+ * surely not words in any human language. This restriction avoids
+ * wasting cycles on stuff like base64-encoded data, and it protects us
+ * against possible inefficiency or misbehavior in the stemmer. (For
+ * example, the Turkish stemmer has an indefinite recursion, so it can
+ * crash on long-enough strings.) However, Snowball dictionaries are
+ * defined to recognize all strings, so we can't reject the string as an
+ * unknown word.
+ */
+ if (len > 1000)
+ {
+ /* return the lexeme lowercased, but otherwise unmodified */
+ res->lexeme = txt;
+ }
+ else if (*txt == '\0' || searchstoplist(&(d->stoplist), txt))
{
+ /* empty or stopword, so report as stopword */
pfree(txt);
}
else
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` Re: Stack overflow issue mahendrakar s <[email protected]>
2022-08-24 10:49 ` Re: Stack overflow issue Alvaro Herrera <[email protected]>
2022-08-24 11:12 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 11:54 ` Re: Stack overflow issue Richard Guo <[email protected]>
2022-08-24 14:03 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-24 17:30 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-30 15:02 ` Re: Stack overflow issue Tom Lane <[email protected]>
2022-08-30 22:57 ` Re: Stack overflow issue Tom Lane <[email protected]>
@ 2022-08-31 02:38 ` Richard Guo <[email protected]>
0 siblings, 0 replies; 15+ messages in thread
From: Richard Guo @ 2022-08-31 02:38 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>; Егор Чиндяскин <[email protected]>; Alvaro Herrera <[email protected]>; mahendrakar s <[email protected]>
On Wed, Aug 31, 2022 at 6:57 AM Tom Lane <[email protected]> wrote:
> I wrote:
> > The upstream recommendation, which seems pretty sane to me, is to
> > simply reject any string exceeding some threshold length as not
> > possibly being a word. Apparently it's common to use thresholds
> > as small as 64 bytes, but in the attached I used 1000 bytes.
>
> On further thought: that coding treats anything longer than 1000
> bytes as a stopword, but maybe we should just accept it unmodified.
> The manual says "A Snowball dictionary recognizes everything, whether
> or not it is able to simplify the word". While "recognizes" formally
> includes the case of "recognizes as a stopword", people might find
> this behavior surprising. We could alternatively do it as attached,
> which accepts overlength words but does nothing to them except
> case-fold. This is closer to the pre-patch behavior, but gives up
> the opportunity to avoid useless downstream processing of long words.
This patch looks good to me. It avoids overly-long words (> 1000 bytes)
going through the stemmer so the stack overflow issue in Turkish stemmer
should not exist any more.
Thanks
Richard
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
@ 2022-08-24 13:58 ` Tom Lane <[email protected]>
2022-10-26 14:47 ` Re: Stack overflow issue Egor Chindyaskin <[email protected]>
2 siblings, 1 reply; 15+ messages in thread
From: Tom Lane @ 2022-08-24 13:58 UTC (permalink / raw)
To: Егор Чиндяскин <[email protected]>; +Cc: [email protected]
=?UTF-8?B?0JXQs9C+0YAg0KfQuNC90LTRj9GB0LrQuNC9?= <[email protected]> writes:
> 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.
Nice work! I wonder if you can make the regex crashes reachable by
reducing the value of max_stack_depth enough that it's hit before
reaching the "regular expression is too complex" limit.
regards, tom lane
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 13:58 ` Re: Stack overflow issue Tom Lane <[email protected]>
@ 2022-10-26 14:47 ` Egor Chindyaskin <[email protected]>
0 siblings, 0 replies; 15+ messages in thread
From: Egor Chindyaskin @ 2022-10-26 14:47 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: [email protected]
24.08.2022 20:58, Tom Lane writes:
> Nice work! I wonder if you can make the regex crashes reachable by
> reducing the value of max_stack_depth enough that it's hit before
> reaching the "regular expression is too complex" limit.
>
> regards, tom lane
Hello everyone! It's been a while since me and Alexander Lakhin have
published a list of functions that have a stack overflow illness. We are
back to tell you more about such places.
During our analyze we made a conclusion that some functions can be
crashed without changing any of the parameters and some can be crashed
only if we change some stuff.
The first function crashes without any changes:
# CheckAttributeType
(n=60000; printf "create domain dint as int; create domain dinta0 as
dint[];"; for ((i=1;i<=$n;i++)); do printf "create domain dinta$i as
dinta$(( $i - 1 ))[]; "; done; ) | psql
psql -c "create table t(f1 dinta60000[]);"
Some of the others crash if we change "max_locks_per_transaction"
parameter:
# findDependentObjects
max_locks_per_transaction = 200
(n=10000; printf "create table t (i int); create view v0 as select *
from t;"; for ((i=1;i<$n;i++)); do printf "create view v$i as select *
from v$(( $i - 1 )); "; done; ) | psql
psql -c "drop table t"
# ATExecDropColumn
max_locks_per_transaction = 300
(n=50000; printf "create table t0 (a int, b int); "; for
((i=1;i<=$n;i++)); do printf "create table t$i() inherits(t$(( $i - 1
))); "; done; printf "alter table t0 drop b;" ) | psql
# ATExecDropConstraint
max_locks_per_transaction = 300
(n=50000; printf "create table t0 (a int, b int, constraint bc check (b
> 0));"; for ((i=1;i<=$n;i++)); do printf "create table t$i()
inherits(t$(( $i - 1 ))); "; done; printf "alter table t0 drop
constraint bc;" ) | psql
# ATExecAddColumn
max_locks_per_transaction = 200
(n=50000; printf "create table t0 (a int, b int);"; for
((i=1;i<=$n;i++)); do printf "create table t$i() inherits(t$(( $i - 1
))); "; done; printf "alter table t0 add column c int;" ) | psql
# ATExecAlterConstrRecurse
max_locks_per_transaction = 300
(n=50000;
printf "create table t(a int primary key); create table pt (a int
primary key, foreign key(a) references t) partition by range (a);";
printf "create table pt0 partition of pt for values from (0) to (100000)
partition by range (a);";
for ((i=1;i<=$n;i++)); do printf "create table pt$i partition of pt$((
$i - 1 )) for values from ($i) to (100000) partition by range (a); "; done;
printf "alter table pt alter constraint pt_a_fkey deferrable initially
deferred;"
) | psql
This is where the fun begins. According to Tom Lane, a decrease in
max_stack_depth could lead to new crashes, but it turned out that
Alexander was able to find new crashes precisely due to the increase in
this parameter. Also, we had ulimit -s set to 8MB as the default value.
# eval_const_expressions_mutator
max_stack_depth = '7000kB'
(n=10000; printf "select 'a' "; for ((i=1;i<$n;i++)); do printf "
collate \"C\" "; done; ) | psql
If you didn’t have a crash, like me, when Alexander shared his find,
then probably you configured your cluster with an optimization flag -Og.
In the process of trying to break this function, we came to the
conclusion that the maximum stack depth depends on the optimization flag
(-O0/-Og). As it turned out, when optimizing, the function frame on the
stack becomes smaller and because of this, the limit is reached more
slowly, therefore, the system can withstand more torment. Therefore,
this query will fail if you have a cluster configured with the -O0
optimization flag.
The crash of the next function not only depends on the optimization
flag, but also on a number of other things. While researching, we
noticed that postgres enforces a distance ~400kB from max_stack_depth to
ulimit -s. We thought we could hit the max_stack_depth limit and then
hit the OS limit as well. Therefore, Alexander wrote a recursive SQL
function, that eats up a stack within max_stack_depth, including a query
that eats up the remaining ~400kB. And this causes a crash.
# executeBoolItem
max_stack_depth = '7600kB'
create function infinite_recurse(i int) returns int as $$
begin
raise notice 'Level %', i;
begin
perform jsonb_path_query('{"a":[1]}'::jsonb, ('$.a[*] ? (' ||
repeat('!(', 4800) || '@ == @' || repeat(')', 4800) || ')')::jsonpath);
exception
when others then raise notice 'jsonb_path_query error at level %,
%', i, sqlerrm;
end;
begin
select infinite_recurse(i + 1) into i;
exception
when others then raise notice 'Max stack depth reached at level %,
%', i, sqlerrm;
end;
return i;
end;
$$ language plpgsql;
select infinite_recurse(1);
To sum it all up, we have not yet decided on a general approach to such
functions. Some functions are definitely subject to stack overflow. Some
are definitely not. This can be seen from the code where the recurse
flag is passed, or a function that checks the stack is called before a
recursive call. Some require special conditions - for example, you need
to parse the query and build a plan, and at that stage the stack is
eaten faster (and checked) than by the function that we are interested in.
We keep researching and hope to come up with a good solution sooner or
later.
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Stack overflow issue
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
@ 2022-08-24 16:23 ` Tom Lane <[email protected]>
2 siblings, 0 replies; 15+ messages in thread
From: Tom Lane @ 2022-08-24 16:23 UTC (permalink / raw)
To: Егор Чиндяскин <[email protected]>; +Cc: [email protected]
=?UTF-8?B?0JXQs9C+0YAg0KfQuNC90LTRj9GB0LrQuNC9?= <[email protected]> writes:
> 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
I took a closer look at these. I think the markst, numst, and nfatree
cases are non-issues. They are recursing on a subre tree that was just
built by parse(), so parse() must have successfully recursed the same
number of levels. parse() surely has a larger stack frame, and it
does have a stack overflow guard (in subre()), so it would have failed
cleanly before making a data structure that could be hazardous here.
Also, having markst error out would be problematic for the reasons
discussed in its comment, so I'm disinclined to try to add checks
that have no use.
BTW, I wonder why your test didn't notice freesubre()? But the
same analysis applies there, as does the concern that we can't
just error out.
Likewise, zaptreesubs() can't recurse more levels than cdissect() did,
and that has a stack check, so I'm not very excited about adding
another one there.
I believe that repeat() is a non-issue because (a) the number of
recursion levels in it is limited by DUPMAX, which is generally going
to be 255, or at least not enormous, and (b) it will recurse at most
once before calling dupnfa(), which contains stack checks.
I think next() is a legit issue, although your example doesn't crash
for me. I suppose that's because my compiler turned the tail recursion
into a loop, and I suggest that we fix it by doing that manually.
(Richard's proposed fix is wrong anyway: we can't just throw elog(ERROR)
in the regex code without creating memory leaks.)
regards, tom lane
^ permalink raw reply [nested|flat] 15+ messages in thread
end of thread, other threads:[~2022-10-26 14:47 UTC | newest]
Thread overview: 15+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2022-08-24 09:51 Stack overflow issue Егор Чиндяскин <[email protected]>
2022-08-24 10:07 ` mahendrakar s <[email protected]>
2022-08-24 10:49 ` Alvaro Herrera <[email protected]>
2022-08-24 10:59 ` mahendrakar s <[email protected]>
2022-08-24 11:12 ` Richard Guo <[email protected]>
2022-08-24 11:54 ` Richard Guo <[email protected]>
2022-08-24 12:59 ` mahendrakar s <[email protected]>
2022-08-24 14:03 ` Tom Lane <[email protected]>
2022-08-24 17:30 ` Tom Lane <[email protected]>
2022-08-30 15:02 ` Tom Lane <[email protected]>
2022-08-30 22:57 ` Tom Lane <[email protected]>
2022-08-31 02:38 ` Richard Guo <[email protected]>
2022-08-24 13:58 ` Tom Lane <[email protected]>
2022-10-26 14:47 ` Egor Chindyaskin <[email protected]>
2022-08-24 16:23 ` Tom Lane <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox