Program analysis is harder than verification: A computability perspective

We study from a computability perspective static program analysis, namely detecting sound program assertions, and verification, namely sound checking of program assertions. We first design a general computability model for domains of program assertions and correspond- ing program analysers and verifiers. Next, we formalize and prove an instantiation of Rice’s theorem for static program analysis and verifica- tion. Then, within this general model, we provide and show a precise statement of the popular belief that program analysis is a harder prob- lem than program verification: we prove that for finite domains of pro- gram assertions, program analysis and verification are equivalent prob- lems, while for infinite domains, program analysis is strictly harder than verification.