Fuzzing isn't exhaustive testing, it's dynamic coverage testing. You provide random input until you discover your (compiler-instrumented) binary doing somethin

Fuzzing isn't exhaustive testing, it's dynamic coverage testing. You provide random input until you discover your (compiler-instrumented) binary doing something you haven't seen yet, then permute the input until you get it to do something else, etc... For almost all non-pathological algorithms, it's capable of reaching full coverage in linear time; though some algorithms are always going to have pathological edge and require some whiteboxing.