| Popis: |
We present a novel approach to optimize incremental scope-bounded checking of programs using a relational constraint solver. Given a program and its correctness specification, scope-bounded checking encodes control-flow and data-flow of bounded code segments into declarative formulas and uses constraint solvers to search for correctness violations. For non-trivial programs, the formulas are often complex and represent a heavy workload that can choke the solvers. To scale scope-bounded checking, our previous work introduced an incremental approach that uses the program’s control-flow as a basis of partitioning the program and generating several sub-formulas, which represent simpler problem instances for the underlying solvers. This paper introduces a new approach that uses the program’s dataflow, specifically variable-definitions, as a basis for incremental checking. Experimental results show that the use of data-flow provides a significant reduction in the number of variables in the encoded formulas over the previous control-flow-based approach, thereby further improving scalability of scopebounded checking. |
