4 ms·

Not sure what machine can possibly completely test a problem with a 32-bit input space in any "practical" or "reasonable" time. Once states are added in, it qui

Not sure what machine can possibly completely test a problem with a 32-bit input space in any "practical" or "reasonable" time. Once states are added in, it quickly explodes beyond a simple 32-bit input space. I have yet to see any literature showing that "Exhaustive" testing is even marginally feasible. I know in my own work, we don't even bother. We come up with the test cases we can and leave the rest to the Software gods.

masklinn 8y ago
> Not sure what machine can possibly completely test a problem with a 32-bit input space in any "practical" or "reasonable" time. Any modern machine: https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/ https://randomascii.wordpress.com/2014/01/27/theres-only-fou... It's the same order of magnitude as your CPU frequency, and trivially partitionable (and thus parallelisable), how fast exactly depends on the complexity of the function being tested, but assuming the entire thing happens in native code it's on the order of 1~10 minutes to go through all values, call both the FUT and the oracle and compare the results. > Once states are added in, it quickly explodes beyond a simple 32-bit input space. Then you're not testing a problem with a 32b input space anymore. My comment specifically points out that it's doable for small input states and gives 32 bits as an anchor at the upper end. If the program under test is fast enough and you're fine with hours-long tests you could get up to the low 40s and still be able to test every single value but since every bit doubles the number of states (and thus the time spent testing) it grows unreasonable extremely quickly. > I know in my own work, we don't even bother. Of course not, the average program is billions of orders of magnitude beyond 32 bits of input state. The current HN homepage is 42.5KB, that's ~350000 bits of input space. If you take an input file or some such you start stacking exponentials just so the number of bits in your input space doesn't get unwieldy.

masklinn 8y ago

> Not sure what machine can possibly completely test a problem with a 32-bit input space in any "practical" or "reasonable" time. Any modern machine: https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/ https://randomascii.wordpress.com/2014/01/27/theres-only-fou... It's the same order of magnitude as your CPU frequency, and trivially partitionable (and thus parallelisable), how fast exactly depends on the complexity of the function being tested, but assuming the entire thing happens in native code it's on the order of 1~10 minutes to go through all values, call both the FUT and the oracle and compare the results. > Once states are added in, it quickly explodes beyond a simple 32-bit input space. Then you're not testing a problem with a 32b input space anymore. My comment specifically points out that it's doable for small input states and gives 32 bits as an anchor at the upper end. If the program under test is fast enough and you're fine with hours-long tests you could get up to the low 40s and still be able to test every single value but since every bit doubles the number of states (and thus the time spent testing) it grows unreasonable extremely quickly. > I know in my own work, we don't even bother. Of course not, the average program is billions of orders of magnitude beyond 32 bits of input state. The current HN homepage is 42.5KB, that's ~350000 bits of input space. If you take an input file or some such you start stacking exponentials just so the number of bits in your input space doesn't get unwieldy.