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: |