Testing tests if it responds with the correct output for a known input. Fuzzing can't replace testing because a. you still want to test that it works correctly given known inputs b. not all functions need to accept badly formatted input
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.Defining custom mutators (e.g libprotobuf-mutator) is sort of like implementing the Arbitrary typeclass if you squint.
I admit, this might be where the similarities end :)