---
OA_type: closed access
_id: '4458'
abstract:
- lang: eng
  text: 'The success of model checking for large programs depends crucially on the
    ability to efficiently construct parsimonious abstractions. A predicate abstraction
    is parsimonious if at each control location, it specifies only relationships between
    current values of variables, and only those which are required for proving correctness.
    Previous methods for automatically refining predicate abstractions until sufficient
    precision is obtained do not systematically construct parsimonious abstractions:
    predicates usually contain symbolic variables, and are added heuristically and
    often uniformly to many or all control locations at once. We use Craig interpolation
    to efficiently construct, from a given abstract error trace which cannot be concretized,
    a parsominous abstraction that removes the trace. At each location of the trace,
    we infer the relevant predicates as an interpolant between the two formulas that
    define the past and the future segment of the trace. Each interpolant is a relationship
    between current values of program variables, and is relevant only at that particular
    program location. It can be found by a linear scan of the proof of infeasibility
    of the trace.We develop our method for programs with arithmetic and pointer expressions,
    and call-by-value function calls. For function calls, Craig interpolation offers
    a systematic way of generating relevant predicates that contain only the local
    variables of the function and the values of the formal parameters when the function
    was called. We have extended our model checker Blast with predicate discovery
    by Craig interpolation, and applied it successfully to C programs with more than
    130,000 lines of code, which was not possible with approaches that build less
    parsimonious abstractions.'
article_processing_charge: No
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Ranjit
  full_name: Jhala, Ranjit
  last_name: Jhala
- first_name: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Kenneth
  full_name: Mcmillan, Kenneth
  last_name: Mcmillan
citation:
  ama: 'Henzinger TA, Jhala R, Majumdar R, Mcmillan K. Abstractions from proofs. In:
    <i>Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming
    Languages</i>. Association for Computing Machinery; 2004:232-244. doi:<a href="https://doi.org/10.1145/964001.964021">10.1145/964001.964021</a>'
  apa: 'Henzinger, T. A., Jhala, R., Majumdar, R., &#38; Mcmillan, K. (2004). Abstractions
    from proofs. In <i>Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles
    of programming languages</i> (pp. 232–244). Venice, Italy: Association for Computing
    Machinery. <a href="https://doi.org/10.1145/964001.964021">https://doi.org/10.1145/964001.964021</a>'
  chicago: Henzinger, Thomas A, Ranjit Jhala, Ritankar Majumdar, and Kenneth Mcmillan.
    “Abstractions from Proofs.” In <i>Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium
    on Principles of Programming Languages</i>, 232–44. Association for Computing
    Machinery, 2004. <a href="https://doi.org/10.1145/964001.964021">https://doi.org/10.1145/964001.964021</a>.
  ieee: T. A. Henzinger, R. Jhala, R. Majumdar, and K. Mcmillan, “Abstractions from
    proofs,” in <i>Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles
    of programming languages</i>, Venice, Italy, 2004, pp. 232–244.
  ista: 'Henzinger TA, Jhala R, Majumdar R, Mcmillan K. 2004. Abstractions from proofs.
    Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming
    languages. POPL: Principles of Programming Languages, 232–244.'
  mla: Henzinger, Thomas A., et al. “Abstractions from Proofs.” <i>Proceedings of
    the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages</i>,
    Association for Computing Machinery, 2004, pp. 232–44, doi:<a href="https://doi.org/10.1145/964001.964021">10.1145/964001.964021</a>.
  short: T.A. Henzinger, R. Jhala, R. Majumdar, K. Mcmillan, in:, Proceedings of the
    31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Association
    for Computing Machinery, 2004, pp. 232–244.
conference:
  end_date: 2004-01-16
  location: Venice, Italy
  name: 'POPL: Principles of Programming Languages'
  start_date: 2004-01-14
date_created: 2018-12-11T12:08:57Z
date_published: 2004-04-01T00:00:00Z
date_updated: 2026-05-29T09:32:36Z
day: '01'
doi: 10.1145/964001.964021
extern: '1'
fulldoi: https://doi.org/10.1145/964001.964021
language:
- iso: eng
month: '04'
oa_version: None
page: 232 - 244
publication: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of
  programming languages
publication_identifier:
  isbn:
  - '9781581137293'
publication_status: published
publisher: Association for Computing Machinery
publist_id: '270'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Abstractions from proofs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2004'
...
