4 ms·
SAT solvers applied. You can now solve unsolvable problems, like practical formal verification in big C/C++ codebases. There's no need anymore to write test ca
by rurban 5y ago
SAT solvers applied.
You can now solve unsolvable problems, like practical formal verification in big C/C++ codebases. There's no need anymore to write test cases, as formal verification tries all possible input values, not just a few selected. It also checks all possible error cases, not just the ones you thought about.
- AnimalMuppet 5y agoCould you expand on what you mean by this? Because it sounds like a level of hype bordering on nonsense. 1. How is a SAT solver going to do formal verification? How do you turn a formal verification into a SAT problem? 2. You can only formally verify what your formal verifier can handle, which is usually somewhat less than "everything". Can your SAT-driven formal verifier verify that the worst case response time of the system is less than X? 3. Formal verification tends to be slow. If I can write and run unit tests orders of magnitude faster than the formal verifier, then the formal verifier is going to not be used much.
- rurban 5y agoLookup what CBMC does. SAT solvers will also be also be applied in traditional compilers soon. The remaining problem with formal verification and compilation is proof of termination, which is not a SAT problem. Running all test cases via cbcm is magnitudes faster than writing 100% coverage (only line cov, not covered values) tests. It's like one day vs one month. And I've never seen code with full value test coverage. For guaranteed timing you need special tests, not a SAT solvers. The solver just helps with the proofs.
- AnimalMuppet 5y agoEven if everything you say is true, it's true the first time. Then I make a change to the code. Now if I have unit tests, I have to fix a test (maybe minutes, maybe an hour) and re-run the tests (minutes). Or I have to re-run the formal verification (a day).
- rurban 5y agomake verify needs less than a few seconds on my targets. Everything over 30min needs to be fixed, or split up.