Abstract
Soundness and completeness are two sides of the same coin, used in program analysis to balance between catching all errors and avoiding false positives. Testing-based formal verification has been proposed to reduce testing costs and improve software reliability by automatically verifying the correctness of program execution paths with regard to the functional scenario form of a specification. In this paper, we propose the notions of functional soundness and functional completeness with regard to a functional scenario and develop the corresponding analysis techniques by integrating testing-based formal verification with program slicing. To further reduce the program scale and verification cost, we propose an FSF-guided program slicing technique, which generates a scenario-specific executable slice for each functional scenario $(T_i,D_i)$. The technique identifies the input and output variables involved in the functional scenario, preserves their relevant data and control dependencies, and removes branches that are unreachable under the testing condition $T_i$.Moreover, we implement tool support for the Java language and conduct an experiment on 250 Java programs containing 740 scenario-specific slicing tasks. The experiment investigates three research questions concerning the reduction in program scale, the reduction in verification cost, and the preservation of verification results. The experimental results show that FSF-guided slicing reduces the numbers of lines of code, executable statements, and cyclomatic complexity by 39.21\%, 46.81\%, and 45.81\% on average, respectively. It also reduces the total cost of testing-based formal verification by 22.5\%, achieves a 97.03\% conclusive preservation rate over all tasks, and preserves the functional soundness and functional completeness judgments on all definite verification tasks.

This publication has 13 references indexed in Scilit: