Fuzzing is effective in testing parsers, but what about testing other algorithms?

[szhorvat]

At the igraph project, we use OSS-fuzz to test igraph's graph format readers, following the original integration set up by @AdamKorcz. Most of the projects integrated into OSS-fuzz parse some sort of data, and fuzzing is a very effective way to test them.

What about other kinds of algorithms though, whose purpose is something different than parsing? I'd love to hear from people who have experimented with this.

More concretely, I was wondering if we could use fuzzing to test igraph's graph algorithms. This seems very difficult. We need to find a way of converting the bytes generated by the fuzzer to a graph in such a way that the fuzzer can be effective in finding "interesting" inputs. Just getting a "valid" graph is difficult though, even with the most trivial constraints, such as requiring that the graph be simple, or that it be connected. Even if we manage to get some valid graphs, it is doubtful if the fuzzer can do much better than generating random graphs would. Random graphs are known to "all look the same" in the sense that hitting on "interesting" cases (and thus triggering different code paths) has very low probability.

I've been experimenting with two such fuzz targets for a few months, but at this point I'm inclined to shut them down. I'm worried that they are not effective and therefore not a good use of OSS-fuzz's resources.

I'm curious if anyone else has run similar experiments, and what your experience was.