Some inputs that trigger failure

[Som1Lse]

I did some fuzzing and found a few cases that trigger failure.

Given

CDT::Triangulation<double> Triangulation = {};

Infinite loop in ensureDelaunayByEdgeFlips:

Triangulation.insertVertices({
    {0.0, 1.0E38},
    {1.0, 1.0E38},
});

Assertion failure in edgeNeighborInd:

Triangulation.insertVertices({
    { 2.0,           -2.18933983E-5},
    {-0.0896810815,  -2.18407786E-5},
    {-2.19008489E-5, -7.64692231E-6},
    { 8.73939061E-5,  0.00568488613},
    {-0.00142463227, -0.00142461748},
    {-7.67273832E-6,  8.7602064E-5},
    { 0.00569847599, -0.00142463227},
    {-2.18156383E-5, -7.6295637E-6},
});
Triangulation.insertEdges({
    {0, 1},
});

Assertion failure in triangulatePseudopolygonIteration:

Triangulation.insertVertices({
    {-2.0,         1.47656155},
    {-6.40527344, -40.4999084},
    { 0.0,        -7.96960115},
    {-2.00152564,  1.46877956},
    {-2.70361328, -7.99999619},
    {-2.70465064, -7.99901962},
    {-7.97778273, -19.3754253},
    { 7.96885204, -5.37488127},
    {-7.97180128, -39.7499695},
});
Triangulation.insertEdges({
    {0, 8},
});

I am not familiar enough with the code to know how to fix them, or even where to begin, so I'm just going to leave this here, and hope it'll be useful.

[artem-ogre]

Thank you @Som1Lse for opening the issue. I will check it as soon as I will get some time.

Can you share any details on how you did the fuzzing? This sounds very interesting.

[Som1Lse]

Here's the source code for it:

#undef NDEBUG

#include <CDT.h>

#include <vector>
#include <limits>

#include <cmath>

struct point {
    float x, y;

    friend bool operator==(point, point)=default;
};

inline bool issafe(float x){
    float x0 = 1.0f;
    float x1 = 1.0E+4f;
    return (-x1 < x && x <= -x0) || x == 0.0f || (x0 < x && x <= x1);
}

inline bool issafe(point p){
    return issafe(p.x) && issafe(p.y);
}

extern "C" int LLVMFuzzerTestOneInput(const point* Points, std::size_t Size){
    std::vector<CDT::V2d<double>> Vertices = {};

    float x0, x1, y0, y1;
    x0 = y0 = std::numeric_limits<float>::max();
    x1 = y1 = -x0;

    for(std::size_t i = 0, End = Size/sizeof(*Points); i < End; ++i){
        auto p = Points[i];
        if(!std::isfinite(p.x)){
            goto found_point;
        }

        if(!issafe(p) || !std::isfinite(p.y)){
            break;
        }

        for(std::size_t j = 0; j < i; ++j){
            if(p == Points[j]){
                return -1;
            }
        }

        x0 = std::min(x0, p.x);
        y0 = std::min(y0, p.y);
        x1 = std::max(x1, p.x);
        y1 = std::max(y1, p.y);

        Vertices.push_back({p.x, p.y});
    }

    return -1;

    found_point:

    std::vector<CDT::Edge> Constraints = {};

    auto Edges = reinterpret_cast<const CDT::Edge*>(Points+Vertices.size()+1);
    Size -= (Vertices.size()+1)*sizeof(*Points);

    for(std::size_t i = 0, End = Size/sizeof(*Edges); i < End; i += 2){
        auto e = Edges[i];
        auto v1 = e.v1();
        auto v2 = e.v2();
        if(0 > v1 || v1 >= v2 || v2 >= Vertices.size()){
            return -1;
        }

        Constraints.push_back(e);
    }

    try {
        CDT::Triangulation<double> Triangulation = {};

        if(!Vertices.empty() && x0 != x1 && y0 != y1){
            Triangulation.insertVertices(Vertices);
            Triangulation.insertEdges(Constraints);
        }
    }catch(...){}

    return 0;
}

Compile with clang++ -fsanitize=fuzzer fuzz.cpp -O3 and run it. This version uses C++20, that should be easily fixed if you want to include this in the project. There's a goto because it was quickly hacked together. It would make sense to split the parsing code into multiple functions, which would eliminate the goto.

Basically, it interprets the buffer as a series of points and when it finds a point with a non-finite x coordinate, it interprets the rest of the buffer as a series of edges to be inserted. Then it calls the library, and catches any exception thrown by it.

It does some basic input validation:

• Checks the bounding is actually a box and not a line. (Otherwise everything would fall into the first case.)
• Checks the points are within a safe range. (This makes the input more human readable, compare the second and third case.)
• Checks edges are actually valid edges. (Since that is actually a precondition of the library.)
• Checks there are no duplicate points. (Dunno if this is allowed by the library or not.)

It would be possible to write a fuzzer that uses a text based format like the one uses for tests, but that would make it run significantly slower. Instead I'd recommend writing another program that turns the format used for fuzzing into a human readable format.

[artem-ogre]

Thank you very much again, @Som1Lse. :bow: I have added you to the list of contributors, this is the least I can do to acknowledge your effort and help.

The first problem is caused by rounding errors when calculating super-triangle vertices from very large coordinate values. I think it is should be rare and not too severe, but it is fixed now anyway.

The second an third case I believe were catching the same issue which was caused by a wrong assumption in the algorithm that 'hanging' edges in pseudo-polygons are never attached to a 'loop'. This bug was introduced some time ago when re-writing the code for better performance. It is a genuine bug in the algorithm and it should be fixed now.

I am very short on a free time, so I focused on fixing the bugs first, but I will definitely come back to you fuzzing code as soon as I get more time. It looks like a very powerful tool, and I would like to understand and use it.