Fuzz testing

[e-n-f]

@flippmoke As we briefly discussed yesterday, I wrote a quick fuzz-testing program to generate random terrible polygons and see how long it takes Clipper to handle them.

Many of the random polygons take 20 or more seconds to complete and some look like they never will. A typical stack trace (from this polygon) when interrupted looks like this:

* thread #1: tid = 0x5c6888, 0x00000001000015cb a.out`ClipperLib::PointInPolygon(pt=0x000000010010b508, op=0x00000001005dc360) + 43 at clipper.cpp:492, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
  * frame #0: 0x00000001000015cb a.out`ClipperLib::PointInPolygon(pt=0x000000010010b508, op=0x00000001005dc360) + 43 at clipper.cpp:492
    frame #1: 0x000000010000dd7c a.out`ClipperLib::Clipper::FixupFirstLefts2(ClipperLib::OutRec*, ClipperLib::OutRec*) [inlined] ClipperLib::Poly2ContainsPoly1(OutPt1=<unavailable>, OutPt2=0x00000001028792a0) + 12 at clipper.cpp:533
    frame #2: 0x000000010000dd70 a.out`ClipperLib::Clipper::FixupFirstLefts2(this=0x00007fff5fbff5e0, InnerOutRec=0x00000001002d1c30, OuterOutRec=0x00000001002d1e10) + 128 at clipper.cpp:3906
    frame #3: 0x0000000100008e5a a.out`ClipperLib::Clipper::DoSimplePolygons(this=0x00007fff5fbff5e0) + 3274 at clipper.cpp:4995
    frame #4: 0x0000000100005ed9 a.out`ClipperLib::Clipper::ExecuteInternal(this=0x00007fff5fbff5e0) + 1033 at clipper.cpp:1706
    frame #5: 0x0000000100005017 a.out`ClipperLib::Clipper::Execute(this=0x00007fff5fbff5e0, clipType=<unavailable>, polytree=0x00007fff5fbff548, subjFillType=<unavailable>, clipFillType=<unavailable>) + 71 at clipper.cpp:1626
    frame #6: 0x000000010001d429 a.out`main + 921 at abuse.cc:50
    frame #7: 0x00007fff8f3fe5c9 libdyld.dylib`start + 1

It's not checking whether the output seems reasonable, only if it completes at all.

[springmeyer]

@ericfischer with the latest fixes are you still seeing any polygons that don't finish/hang? With the fuzzer port to mapnik-vt (https://github.com/mapbox/mapnik-vector-tile/blob/master/bin/vtile-fuzz.cpp) I'm not. Also I originally only saw crashes and no hangs.

[e-n-f]

Thanks @springmeyer. I did just get it to crash on this fuzz polygon but haven't looked into what exactly went wrong yet.

In general it seems to take O(n^4) time with the number of sides, so it can get slow, but I haven't seen it fail to complete.

[springmeyer]

@ericfischer - interesting. Would it be possible to capture the rand() values that were the way that polygon was generated as well? I want to try plugging those same values into the mapnik-vt fuzzer port and make sure it also crashes/produces the same polygons.

[e-n-f]

I got it to crash again, this time in the debugger, and it was here:

* thread #1: tid = 0x1e4bef, 0x00000001000132b0 a.out`ClipperLib::Clipper::FixIntersects(this=0x00007fff5fbffa10, dupeRec=0x00007fff5fbff820, op_j=<unavailable>, op_k=<unavailable>, outRec_j=<unavailable>, outRec_k=<unavailable>) + 1392 at clipper.cpp:4746, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x20)
    frame #0: 0x00000001000132b0 a.out`ClipperLib::Clipper::FixIntersects(this=0x00007fff5fbffa10, dupeRec=0x00007fff5fbff820, op_j=<unavailable>, op_k=<unavailable>, outRec_j=<unavailable>, outRec_k=<unavailable>) + 1392 at clipper.cpp:4746
   4743         // Check for connection through chain of other intersections
   4744         for (auto it = range.first; it != range.second; ++it)
   4745         {
-> 4746             OutRec * itRec = GetOutRec(it->second.op2->Idx);
   4747             if (itRec->Idx != outRec_search->Idx &&
   4748                 op_origin_2->Pt != it->second.op2->Pt &&
   4749                 (outRec_parent == itRec || outRec_parent == ParseFirstLeft(itRec->FirstLeft)) &&

I'll start logging the random seed for easier reproducibility.

[e-n-f]

Here's a reliable crasher, with srand(1461434208).

► c++ -g -std=c++11 -Wall -O3 abuse.cc cpp/clipper.cpp

► ./a.out
620 sides
Segmentation fault: 11

[springmeyer]

Here's a reliable crasher, with srand(1461434208).

@ericfischer - your fuzzer uses 3 rand() calls right? Can you provide all three?

[springmeyer]

@ericfischer when you've got the rand() necessary pass them off to @flippmoke as he's planning on looking into this today.

[e-n-f]

I'm not sure quite what you are asking, @springmeyer. The code linked above that crashes calls rand() in four places:

• to determine the number of points to produce
• the x coordinate of each point
• the y coordinate of each point
• a 1-in-50 chance of closing the ring and starting another one.

Here is a list of the values that rand produces with a seed of 1461434208. Here are the coordinates of the points around each ring.

[e-n-f]

And the difference between this and your fuzzer, in addition to all the looping over various options that you do, is that it looks like you have an extra check to close the ring when it gets to have 100 points in it, which reduces the level of complexity that Clipper is asked to handle.

[flippmoke]

@ericfischer I found the bug in the code -- it should be fixed in 9edc2924e39266d70774b0ed0e07329a95e76f10

[e-n-f]

Thanks @flippmoke! It's looking good to me.