FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Program Analysis is Harder than Verification: A Computability Perspective

Authors: Patrick Cousot, Roberto Giacobazzi and Francesco Ranzato

Paper Information

Title:Program Analysis is Harder than Verification: A Computability Perspective
Authors:Patrick Cousot, Roberto Giacobazzi and Francesco Ranzato
Proceedings:CAV All Papers
Editors: Georg Weissenbacher, Hana Chockler and Igor Konnov
Keywords:Static program analysis, Program verification, Computability, Rice's theorem
Abstract:

ABSTRACT. We study from a computability perspective static program analysis, namely detecting sound program assertions, and verification, namely sound checking of program assertions. We first provide a general computability model for domains of program assertions and corresponding program analysers and verifiers. Next, we formalize and prove an instantiation of Rice's Theorem for static program analysis and verification. Then, within this general model, we provide and show a precise statement of the popular belief that program analysis is a harder problem than program verification: we prove that for finite domains of program assertions, program analysis and verification are equivalent problems, while for infinite domains, program analysis is strictly harder than verification.

Pages:18
Talk:Jul 16 12:15 (Session 113: Static Analysis)
Paper: