What is an example of a buggy function that would be hard to find to discover the bug without fuzz testing?

Question

I'd like to come up with a motivating example or code challenge for fuzz testing and/or property-based testing.

What I'm looking for is a concise situation where such testing is maximally critical/necessary.

For example, ideally it would take enough fuzz runs that a human would be unlikely to discover the bug by manually trying random unit tests or relying on intuition to come up with edge cases.

Bonus if:

• in TypeScript (but not a big deal; I can translate)
• an example from real/historical software

I tried asking ChatGPT but the bug was too obvious. I also tried a bit of Googling and found this, but it's still quite obvious and probably also reveals itself after a few unit tests. I also considered making some kind of broken lookup table (inspired by Pentium FDIV bug) but I couldn't figure out how to make it so that you can't trivially solve it by just computing the correct lookup table and comparing it.

Answer 1

One in my opinion convincing and still easy-to-understand example is prime factorization. Look at the blog article on property-driven development of such an algorithm.

Full disclosure: I'm the author of the article and main committer of the used PBT library.

Consider the implementation (sorry it's Java) as it resulted after a few steps of TDD using properties:

public static List<Integer> factorize(int number) {
    List<Integer> factors = new ArrayList<>();
    int candidate = 2;
    while (number >= candidate) {
        while (number % candidate != 0) {
            candidate++;
        }
        factors.add(candidate);
        number /= candidate;
    }
    return factors;
}

From an algorithmic standpoint factorize works alright. Some of the failings - e.g. handling large numbers, potential integer overflows - are only discovered when you set it under stress with a generic property:

@Property
void all_numbers_above_1_can_be_factorized(
        @ForAll @IntRange(min = 2, max = 10000) int number
) {
    List<Integer> factors = Primes.factorize(number);
    Integer product = factors.stream().reduce(1, (a, b) -> a * b);
    Assertions.assertThat(product).isEqualTo(number);
}

If you start increasing max beyond 1_000_000 and towards Integer.MAX_VALUE range the algorithm will run for a very long time or not finish at all. Those failing properties lead to changes of the algorithm to handle factorization for the full range of integers. An implementation running fast up to the maximum integer value is e.g.:

public static List<Integer> factorize(int number) {
    List<Integer> factors = new ArrayList<>();
    int candidate = 2;
    while (number >= candidate) {
        while (number % candidate != 0) {
            if (Math.sqrt(number) < candidate) {
                candidate = number;
            } else {
                candidate++;
            }
        }
        factors.add(candidate);
        number /= candidate;
    }
    return factors;
}

Before I learned about PBT, I tended to not test such things; now it comes naturally.