Program Dependence Net and Its Slice for Verifying Linear Temporal Properties

01/27/2023
by   Zhijun Ding, et al.
0

The finite-state model checking of software is still limited by the notorious state-explosion problem. The dependence-based program slicing is effective to reduce the verification time and is orthogonal to other reduction techniques of model checking. However, within slicing concurrent programs for model checking, the conversions between multiple irreplaceable models and the calculation of dependencies for some variables irrelevant to the verified property produce redundant calculating costs. Thus, we propose a Program Dependence Net (PDNet) as a unified model combining the control-flow structure with dependencies to avoid the model conversions. For reduction, we propose a PDNet slicing to capture the relevant variables' dependencies on demand. The calculating costs could be significantly compressed by our unified model and on-demand slicing based on PDNet. Then, we implemented a concurrent program model checking tool based on PDNet and its slice. Finally, we validated the advantages of our methods.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset