Comments (3)
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.
from cdt.
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.
from cdt.
Thank you very much again, @Som1Lse. 🙇
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.
from cdt.
Related Issues (20)
- Could not find vertex triangle intersected by edge HOT 4
- Bug in resolving constraint edges intersection when there is a hanging edge
- Assert during triangulation HOT 8
- Missing inline HOT 4
- [1.3.3] Issue with edge insertion (CDT::IntersectingConstraintEdges::Resolve) HOT 6
- What is the coordinate system for this algorithm? HOT 4
- Port to C# [link in description]
- Warnings: `vertices` is shadowing a member declaration HOT 1
- Tiny compilation warning (VS2019) HOT 6
- initializeWithCustomGrid HOT 1
- Infinite Loop in Conform Mode HOT 4
- overlapping edges / flat triangles (solved) HOT 5
- Csharp support? HOT 1
- Are there better ways to find all triangles containing a certain edge? HOT 2
- Generate some degenerate triangles HOT 2
- How to update triangulations efficiently? HOT 10
- How to obtain the vertices inside the boundary composed with some edges? HOT 3
- A case that failed in triangulation HOT 20
- Question about m_vertTris HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cdt.