RobustDeterminant is not robust

[rdool]

int RobustDeterminant::signOfDet2x2(double x1,double y1,double x2,double y2)

This method loops endlessly when the initial parameters x1,y1,x2,y2 all have the value -nan (0x8000000000000).

The following stacktrace is causing the method to loop endlessly.

#0  geos::algorithm::RobustDeterminant::signOfDet2x2 (x1=-nan(0x8000000000000), y1=-nan(0x8000000000000), x2=-nan(0x8000000000000), 
    y2=-nan(0x8000000000000)) at RobustDeterminant.cpp:212
#1  0x00007f170df5cf9e in geos::algorithm::CGAlgorithms::isCCW (ring=<value optimized out>) at CGAlgorithms.cpp:219
#2  0x00007f170df8a2f8 in geos::geomgraph::GeometryGraph::addPolygonRing (this=0xc42e90, lr=0xb32250, cwLeft=2, cwRight=0)
    at GeometryGraph.cpp:248
#3  0x00007f170df8a49e in geos::geomgraph::GeometryGraph::addPolygon (this=0xc42e90, p=0xb8b840) at GeometryGraph.cpp:274
#4  0x00007f170df8ade3 in geos::geomgraph::GeometryGraph::add (this=0xc42e90, g=0xb8b840) at GeometryGraph.cpp:178
#5  0x00007f170dfb9235 in GeometryGraphOperation (this=<value optimized out>, g0=0xbc76d0, g1=0xb8b840)
    at ../../source/headers/geos/geomgraph/GeometryGraph.inl:59
#6  0x00007f170dfd9826 in RelateOp (this=0xfff8000000000000, g0=0x400, g1=0xc3fe68) at RelateOp.cpp:44
#7  0x00007f170dfd988f in geos::operation::relate::RelateOp::relate (a=<value optimized out>, b=<value optimized out>) at RelateOp.cpp:38
#8  0x00007f170df6cf98 in geos::geom::Geometry::intersects (this=0xbc76d0, g=0xb8b840) at Geometry.cpp:367
#9  0x00007f170e471b4a in GEOSIntersects (g1=0xfff8000000000000, g2=0x400) at geos_c.cpp:177
#10 0x00007f170e6a67b2 in intersects () from /usr/lib/postgresql/8.3/lib/liblwgeom.so

I think methods that do calculations should verify the initial conditions with assert-like statements. To protect against NAN is only possible with negative if-statements since every logical test of a NAN value results into False. The last property is also causing the endless looping process.

[strk]

Is there any way to trigger this from the C-API ?

[rdool]

You can trigger this by assigning every argument of the method the NaN value. There seems to be no standard way in C++ to do this but maybe the following link helps:

 http://cboard.cprogramming.com/cplusplus-programming/35382-using-nan-cplusplus.html#post245195

Assigning the value 0x8000000000000 to the double using inline assembly might give another possibility, as long as the value is recognized as NaN resulting in every comparison giving false result.

The stacktrace given in the issue comes from a machine running Debian-5 and Postgresql-8.3 + PostGIS (postgresql-8.3-postgis_1.3.3-3_amd64.deb).

[strk]

Do you have the HEXWKB of the offending geometry ?

[rdool]

We have no example for the geometry that gives problems since the problem does not show up frequently and only terminating the Linux process seemed the only possibility to end the loop (so loosing the logging of the offending geometry).

Since we protected our Geos library with a NaN detecting patch we never met the infinite looping problem again (although we didn't protect against INF, so that is still a possible hole in the protection).

The same kind of endless loop could happen if some of the arguments equal INF (infinite). See:  http://postgis.org/pipermail/postgis-users/2011-February/029001.html

The given hyperlink shows a geometry (possibly containing infinities) that result in the same stacktrace.

suggestion to create a NaN using a union. Something like this (on AMD-64, Debian-5 Linux):

union NanUnion? {

// first representation unsigned long long = 0x8000000000000000;

// second representation

double nanDouble;

};

[strk]

I'm trying to reproduce with a unit test. This doesn't get into the infinite loop:

RobustDeterminant::signOfDet2x2: -nan, -nan, -nan, -nan

[rdool]

Machine (or CPU) dependent behavior ?

[rdool]

Possibly a compiler option could help ?

Something like: -OPT:IEEE_NaN_inf=ON|OFF

[strk]

maybe. geos is supposed to build with IEEE floats, or other places will fail as well.

I've committed the test as r3341, see if you can get a segfault on your system.

[jantuar]

This problem was noticed on Debian Lenny with GEOS 3.0.0, it might have been fixed since then. RobustDeterminant?.cpp is essentially the same between that version and current trunk, but I have no way to verify if in the current version something above that does sanity checks on the passed values before RobustDeterminant? is called.

To help figure this out I created a standalone C program based on your test case, but that fails to trigger the infinite loop even on a machine that is known to be bad (running unpatched libgeos-3.0.0).

In my (limited) understanding this proves that either my standalone program isn't correct or the test case itself isn't correct and will not trigger this (one possible cause is that geom1 is compared to geom1, something above RobustDeterminant? may notice this and never call the problematic function).

It could be helpful if a person who understands GEOS wrote a self contained test case that could be used for further tests.

[strk]

Locally, I've added a debugging line in RobustDeterminant::signOfDet2x2, which is where the message I posted few comments ago comes from there. This is to say there's nothing preventing the -nan from getting down the line. It'd be worth for you to add those debugging lines too, in case your system doesn't turn those 0.0/0 into nans.

I attach a patch (patch -p1)

[strk]

It's been reported that this triggers the bug (inf ordinate):

0103000020E61000000100000005000000737979F3DDCC2CC0F92154F9E7534540000000000000F
07F000000000000F07F8F806E993F7E55C0304B29FFEA8554400634E8D1DD424540B5FEE6A37FCD4
540737979F3DDCC2CC0F92154F9E7534540

See  http://postgis.refractions.net/pipermail/postgis-devel/2011-May/012819.html

[strk]

Bingo, testing the above to itself for intersection enters the loop

[strk]

I attach an XML test, which shows JTS is also affected.

[strk]

Failed on JTS too:  https://sourceforge.net/tracker/?func=detail&aid=3300893&group_id=128875&atid=713120

[strk]

Fix committed in r3360 It's a wide catch of any nan and inf, throwing IllegalArgumentException?. Better safe than sorry...

If JTS will make it any narrower we'll adapt.