Division-by-zero SIGFPE crash in DiscreteFrechetDistance

[erikgrinaker]

Using a very small densifyFrac with DiscreteFrechetDistance causes a division-by-zero error. This can be reproduced via e.g. PostGIS using the following query:

test=# SELECT st_frechetdistance('LINESTRING (0 0, 3 7, 5 5)', 'LINESTRING (0 0, 9 1, 2 2)', 1e-20); ERROR: floating-point exception DETAIL: An invalid floating-point operation was signaled. This probably means an out-of-range result or an invalid operation, such as division by zero.

1e-20 causes a SIGFPE, while 1e-19 returns the error "GEOSFrechetDistance: vector", possibly due to a memory allocation failure.

The problem is isolated to GEOS, since we're seeing the same problem when implementing this function in CockroachDB using GEOS.

[mdavis]

I doubt we'll be able to handle very small densify fractions, since (a) math precision issues are hard and (b) the implemented algorithm is O(nm) and uses the stack heavily, so is liable to OOM errors for very large numbers of vertices (which the small densify fraction effectively produces).

We could hard-limit the densify fraction to something reasonable (e.g. 1E-4). Or document and raise an error if the input exceeds this limit.

Of course, you can also do this in the client code.

Is this just erroneous/fuzzed input, or is there a perceived need for this small a fraction?

[dbaston]

The SIGFPE does not appear to be raised in GEOS main. I added tests to check for this in a9d53329700e0f052ae276ec27b1220f59e4d7b3/git