Paradigm shift: fuzzing is testing if you write fuzzers that test properties. For instance, if you have a class that can be parsed and serialized, you may write something like this in a fuzzer:

    if (serialize(parse(data, size)) != data) {
        CRASH();
    }

More directly addressing your point about not all functions accepting malformed input, you can also use a fuzzer to exercise sequences of methods on an object. If your class has any invariants, you can test them along the way.