/src/igraph/fuzzing/spatial.cpp

Source (jump to first uncovered line)
/*
   IGraph library.
   Copyright (C) 2025  The igraph development team

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA
*/

#include <igraph.h>

#include <limits>
#include <random>

/* Custom mutator and crossover functions are based on
 * https://rigtorp.se/fuzzing-floating-point-code/
 * A more advanced solution will take into account that we
 * are working with n-dimensional coordinates. */

extern "C" size_t LLVMFuzzerCustomMutator(uint8_t *Data, size_t Size,
                                          size_t MaxSize, unsigned int Seed) {
    double *begin = (double *) Data;
    double *end = (double *) Data + Size / sizeof(double);

    std::minstd_rand gen(Seed);

    auto rfp = [&]() {
        if (gen() < std::bernoulli_distribution(0.8)(gen)) {
            std::normal_distribution<> dist(0.0, 10);
            return dist(gen);
        } else {
            switch (std::uniform_int_distribution<>(0, 9)(gen)) {
            case 0:
                return std::numeric_limits<double>::quiet_NaN();
            case 1:
                return std::numeric_limits<double>::min();
            case 2:
                return std::numeric_limits<double>::max();
            case 3:
                return -std::numeric_limits<double>::min();
            case 4:
                return -std::numeric_limits<double>::max();
            case 5:
                return std::numeric_limits<double>::epsilon();
            case 6:
                return -std::numeric_limits<double>::epsilon();
            case 7:
                return std::numeric_limits<double>::infinity();
            case 8:
                return -std::numeric_limits<double>::infinity();
            case 9:
                return 0.0;
            }
        }
        return 0.0; // never reached, prevents compiler warning
    };

    switch (std::uniform_int_distribution<>(0, 3)(gen)) {
    case 0: { // Change element
        if (begin != end) {
            std::uniform_int_distribution<> d(0, end - begin - 1);
            begin[d(gen)] = rfp();
        }
        break;
    }
    case 1: // Add element
        if (Size + sizeof(double) <= MaxSize) {
            *end = rfp();
            ++end;
        }
        break;
    case 2: // Delete element
        if (begin != end) {
            --end;
        }
        break;
    case 3: // Shuffle elements
        std::shuffle(begin, end, gen);
        break;
    }

    return (end - begin) * sizeof(double);
}


extern "C" size_t LLVMFuzzerCustomCrossOver(const uint8_t *Data1, size_t Size1,
                                            const uint8_t *Data2, size_t Size2,
                                            uint8_t *Out, size_t MaxOutSize,
                                            unsigned int Seed) {
    std::minstd_rand gen(Seed);
    std::bernoulli_distribution bd(0.5);
    size_t n = std::min({Size1, Size2, MaxOutSize}) / sizeof(double);
    for (size_t i = 0; i < n; ++i) {
        ((double *)Out)[i] = bd(gen) ? ((double *)Data1)[i] : ((double *)Data2)[i];
    }
    return n * sizeof(double);
}


extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
    igraph_matrix_t points1d, points2d, points3d, points4d;
    igraph_t graph;

    igraph_set_error_handler(igraph_error_handler_ignore);
    igraph_set_warning_handler(igraph_warning_handler_ignore);

    if (Size % sizeof(igraph_real_t) != 0 || Size > 120 * sizeof(igraph_real_t)) {
        return 0;
    }

    size_t coord_count = Size / sizeof(double);
    igraph_real_t *coords = (igraph_real_t *) Data;

    igraph_matrix_view(&points1d, coords, coord_count / 1, 1);
    igraph_matrix_view(&points2d, coords, coord_count / 2, 2);
    igraph_matrix_view(&points3d, coords, coord_count / 3, 3);
    igraph_matrix_view(&points4d, coords, coord_count / 4, 4);

    {
        igraph_vector_int_t iv;
        igraph_vector_int_init(&iv, 0);
        igraph_convex_hull_2d(&points2d, &iv, NULL);
        igraph_vector_int_destroy(&iv);
    }

    if (igraph_nearest_neighbor_graph(&graph, &points1d, IGRAPH_METRIC_EUCLIDEAN, 2, IGRAPH_INFINITY, IGRAPH_UNDIRECTED) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_nearest_neighbor_graph(&graph, &points2d, IGRAPH_METRIC_EUCLIDEAN, 1, IGRAPH_INFINITY, IGRAPH_DIRECTED) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_nearest_neighbor_graph(&graph, &points3d, IGRAPH_METRIC_EUCLIDEAN, 3, IGRAPH_INFINITY, IGRAPH_UNDIRECTED) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_nearest_neighbor_graph(&graph, &points4d, IGRAPH_METRIC_EUCLIDEAN, 2, IGRAPH_INFINITY, IGRAPH_DIRECTED) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }

    /* Re-enable after https://github.com/qhull/qhull/issues/166 is fixed. */
    /*
    if (igraph_delaunay_graph(&graph, &points1d) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_delaunay_graph(&graph, &points2d) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_delaunay_graph(&graph, &points3d) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    if (igraph_delaunay_graph(&graph, &points4d) == IGRAPH_SUCCESS) {
        igraph_destroy(&graph);
    }
    */

    IGRAPH_ASSERT(IGRAPH_FINALLY_STACK_EMPTY);

    return 0;  // Non-zero return values are reserved for future use.
}

Line	Count	Source (jump to first uncovered line)
1		/*
2		IGraph library.
3		Copyright (C) 2025 The igraph development team
4
5		This program is free software; you can redistribute it and/or modify
6		it under the terms of the GNU General Public License as published by
7		the Free Software Foundation; either version 2 of the License, or
8		(at your option) any later version.
9
10		This program is distributed in the hope that it will be useful,
11		but WITHOUT ANY WARRANTY; without even the implied warranty of
12		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13		GNU General Public License for more details.
14
15		You should have received a copy of the GNU General Public License
16		along with this program; if not, write to the Free Software
17		Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18		02110-1301 USA
19		*/
20
21		#include <igraph.h>
22
23		#include <limits>
24		#include <random>
25
26		/* Custom mutator and crossover functions are based on
27		* https://rigtorp.se/fuzzing-floating-point-code/
28		* A more advanced solution will take into account that we
29		* are working with n-dimensional coordinates. */
30
31		extern "C" size_t LLVMFuzzerCustomMutator(uint8_t *Data, size_t Size,
32	0	size_t MaxSize, unsigned int Seed) {
33	0	double begin = (double ) Data;
34	0	double end = (double ) Data + Size / sizeof(double);
35
36	0	std::minstd_rand gen(Seed);
37
38	0	auto rfp = [&]() {
39	0	if (gen() < std::bernoulli_distribution(0.8)(gen)) {
40	0	std::normal_distribution<> dist(0.0, 10);
41	0	return dist(gen);
42	0	} else {
43	0	switch (std::uniform_int_distribution<>(0, 9)(gen)) {
44	0	case 0:
45	0	return std::numeric_limits<double>::quiet_NaN();
46	0	case 1:
47	0	return std::numeric_limits<double>::min();
48	0	case 2:
49	0	return std::numeric_limits<double>::max();
50	0	case 3:
51	0	return -std::numeric_limits<double>::min();
52	0	case 4:
53	0	return -std::numeric_limits<double>::max();
54	0	case 5:
55	0	return std::numeric_limits<double>::epsilon();
56	0	case 6:
57	0	return -std::numeric_limits<double>::epsilon();
58	0	case 7:
59	0	return std::numeric_limits<double>::infinity();
60	0	case 8:
61	0	return -std::numeric_limits<double>::infinity();
62	0	case 9:
63	0	return 0.0;
64	0	}
65	0	}
66	0	return 0.0; // never reached, prevents compiler warning
67	0	};
68
69	0	switch (std::uniform_int_distribution<>(0, 3)(gen)) {
70	0	case 0: { // Change element
71	0	if (begin != end) {
72	0	std::uniform_int_distribution<> d(0, end - begin - 1);
73	0	begin[d(gen)] = rfp();
74	0	}
75	0	break;
76	0	}
77	0	case 1: // Add element
78	0	if (Size + sizeof(double) <= MaxSize) {
79	0	*end = rfp();
80	0	++end;
81	0	}
82	0	break;
83	0	case 2: // Delete element
84	0	if (begin != end) {
85	0	--end;
86	0	}
87	0	break;
88	0	case 3: // Shuffle elements
89	0	std::shuffle(begin, end, gen);
90	0	break;
91	0	}
92
93	0	return (end - begin) * sizeof(double);
94	0	}
95
96
97		extern "C" size_t LLVMFuzzerCustomCrossOver(const uint8_t *Data1, size_t Size1,
98		const uint8_t *Data2, size_t Size2,
99		uint8_t *Out, size_t MaxOutSize,
100	0	unsigned int Seed) {
101	0	std::minstd_rand gen(Seed);
102	0	std::bernoulli_distribution bd(0.5);
103	0	size_t n = std::min({Size1, Size2, MaxOutSize}) / sizeof(double);
104	0	for (size_t i = 0; i < n; ++i) {
105	0	((double )Out)[i] = bd(gen) ? ((double )Data1)[i] : ((double *)Data2)[i];
106	0	}
107	0	return n * sizeof(double);
108	0	}
109
110
111	1.02k	extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
112	1.02k	igraph_matrix_t points1d, points2d, points3d, points4d;
113	1.02k	igraph_t graph;
114
115	1.02k	igraph_set_error_handler(igraph_error_handler_ignore);
116	1.02k	igraph_set_warning_handler(igraph_warning_handler_ignore);
117
118	1.02k	if (Size % sizeof(igraph_real_t) != 0 \|\| Size > 120 * sizeof(igraph_real_t)) {
119	12	return 0;
120	12	}
121
122	1.01k	size_t coord_count = Size / sizeof(double);
123	1.01k	igraph_real_t coords = (igraph_real_t ) Data;
124
125	1.01k	igraph_matrix_view(&points1d, coords, coord_count / 1, 1);
126	1.01k	igraph_matrix_view(&points2d, coords, coord_count / 2, 2);
127	1.01k	igraph_matrix_view(&points3d, coords, coord_count / 3, 3);
128	1.01k	igraph_matrix_view(&points4d, coords, coord_count / 4, 4);
129
130	1.01k	{
131	1.01k	igraph_vector_int_t iv;
132	1.01k	igraph_vector_int_init(&iv, 0);
133	1.01k	igraph_convex_hull_2d(&points2d, &iv, NULL);
134	1.01k	igraph_vector_int_destroy(&iv);
135	1.01k	}
136
137	1.01k	if (igraph_nearest_neighbor_graph(&graph, &points1d, IGRAPH_METRIC_EUCLIDEAN, 2, IGRAPH_INFINITY, IGRAPH_UNDIRECTED) == IGRAPH_SUCCESS) {
138	912	igraph_destroy(&graph);
139	912	}
140	1.01k	if (igraph_nearest_neighbor_graph(&graph, &points2d, IGRAPH_METRIC_EUCLIDEAN, 1, IGRAPH_INFINITY, IGRAPH_DIRECTED) == IGRAPH_SUCCESS) {
141	921	igraph_destroy(&graph);
142	921	}
143	1.01k	if (igraph_nearest_neighbor_graph(&graph, &points3d, IGRAPH_METRIC_EUCLIDEAN, 3, IGRAPH_INFINITY, IGRAPH_UNDIRECTED) == IGRAPH_SUCCESS) {
144	934	igraph_destroy(&graph);
145	934	}
146	1.01k	if (igraph_nearest_neighbor_graph(&graph, &points4d, IGRAPH_METRIC_EUCLIDEAN, 2, IGRAPH_INFINITY, IGRAPH_DIRECTED) == IGRAPH_SUCCESS) {
147	940	igraph_destroy(&graph);
148	940	}
149
150		/* Re-enable after https://github.com/qhull/qhull/issues/166 is fixed. */
151		/*
152		if (igraph_delaunay_graph(&graph, &points1d) == IGRAPH_SUCCESS) {
153		igraph_destroy(&graph);
154		}
155		if (igraph_delaunay_graph(&graph, &points2d) == IGRAPH_SUCCESS) {
156		igraph_destroy(&graph);
157		}
158		if (igraph_delaunay_graph(&graph, &points3d) == IGRAPH_SUCCESS) {
159		igraph_destroy(&graph);
160		}
161		if (igraph_delaunay_graph(&graph, &points4d) == IGRAPH_SUCCESS) {
162		igraph_destroy(&graph);
163		}
164		*/
165
166	1.01k	IGRAPH_ASSERT(IGRAPH_FINALLY_STACK_EMPTY);
167
168	1.01k	return 0; // Non-zero return values are reserved for future use.
169	1.01k	}

Coverage Report

Created: 2025-08-28 06:37