Thread: BUG #18214: poly_contain (@>) hangs forever for input data with zeros and infinities

The following bug has been logged on the website:

Bug reference:      18214
Logged by:          Nikolay Shaplov
Email address:      dhyan@nataraj.su
PostgreSQL version: 16.1
Operating system:   Debian 12
Description:

In postgreses 14-16, you execute following query it will work "forever" 

select '((-inf, 0), (0, inf), (-inf, 0), (0, inf), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))'::polygon @> '((0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
(-inf, 0))'::polygon;

(Colleges says it is o(n!), it worked for me for 24h and then I stopped
it)

This bug have been found while fuzzing @> operation using AFL++ as Fuzzer
Engine and LibBlobStamper for Structure Aware Fuzzing

Removing items from the query makes it work "faster" (e.g. several hours).

My colleagues have poked this bug a bit, and suggested that the cause of the
problem is probably the lseg_contain_point(LSEG *lseg, Point *pt) function,
that gives wrong result for the infinity case. Like  lseg = {(0, 0), ( -inf,
0)} and pt = (0, inf) does not contain one another, but lseg_contain_point
gives true for that data.

Also they gave another example:

select '((inf, 0), (0, -inf), (0, 0))'::polygon @> '((0, 0), (inf,
0))'::polygon a;
a    |
-----+
false|

select '((-inf, 0), (0, inf),(0, 0))'::polygon @> '((0, 0), (-inf,
0))'::polygon a;
a   |
----+
true|

If you just mirror sign of infinity, you get different result (and it should
be the same since geometry have not been changed, just have been mirrored)

PS I will provide raw data that came from Fuzzier attached to the next
message, since I can not attach it in the

PG Bug reporting form <noreply@postgresql.org> writes:
> In postgreses 14-16, you execute following query it will work "forever" 

> select '((-inf, 0), (0, inf), (-inf, 0), (0, inf), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))'::polygon @> '((0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (-inf, 0))'::polygon;

I poked at this a bit.  v13 and earlier return quickly, although their
answer is "false" which I'm not too sure is correct.  git bisect shows
the behavior changed at

commit 8597a48d01b6cc0b09ff626253ac93c67e5516d5
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Sat Nov 21 16:46:43 2020 -0500

    Fix FPeq() and friends to get the right answers for infinities.

I'm inclined to think that poly_contain_poly, or more specifically
lseg_inside_poly, is just a broken algorithm.  I don't have much faith
that it gets the right answer (especially for non-simple polygons,
which we do try to handle correctly in e.g. point_inside), and it's
pretty obviously horrid from a time-complexity standpoint.  I think
we need to throw it away and start fresh rather than try to band-aid
it further.

I googled "polygon containment" and read about sweep-line algorithms,
which might be the way to go here, but it's not something I care to
put time into personally.

> My colleagues have poked this bug a bit, and suggested that the cause of the
> problem is probably the lseg_contain_point(LSEG *lseg, Point *pt) function,
> that gives wrong result for the infinity case.

Hmm, yeah, that pretty obviously fails for infinities, or any values
large enough to cause overflow.  I doubt that fixing it is sufficient
to rescue poly_contain_poly, but it seems worth improving anyway
because it has other callers.  Not quite sure how we should define
its behavior for infinity inputs though.  If the point has any Inf
coordinate, it seems clear that it's on the segment only if it is
equal() to one of the endpoints.  But what about a finite point
versus a segment with Inf coordinate(s)?

            regards, tom lane

В письме от пятница, 24 ноября 2023 г. 21:01:02 MSK пользователь Tom Lane
написал:

>   Not quite sure how we should define its behavior for infinity inputs though.
I am not sure, if there is any practical need in comparing polygons with nodes
located in the infinity. May be the best solution would be just to refuse the
operation if there is at least one point with infinite coordinate. But I am no
expert here...

--
Nikolay Shaplov aka Nataraj
Fuzzing Engineer at Postgres Professional
Matrix IM: @dhyan:nataraj.su