---
_id: '4571'
abstract:
- lang: eng
  text: The success of software verification depends on the ability to find a suitable
    abstraction of a program automatically. We propose a method for automated abstraction
    refinement which overcomes some limitations of current predicate discovery schemes.
    In current schemes, the cause of a false alarm is identified as an infeasible
    error path, and the abstraction is refined in order to remove that path. By contrast,
    we view the cause of a false alarm -the spurious counterexample- as a full-fledged
    program, namely, a fragment of the original program whose control-flow graph may
    contain loops and represent unbounded computations. There are two advantages to
    using such path programs as counterexamples for abstraction refinement. First,
    we can bring the whole machinery of program analysis to bear on path programs,
    which are typically small compared to the original program. Specifically, we use
    constraint-based invariant generation to automatically infer invariants of path
    programs-so-called path invariants. Second, we use path invariants for abstraction
    refinement in order to remove not one infeasibility at a time, but at once all
    (possibly infinitely many) infeasible error computations that are represented
    by a path program. Unlike previous predicate discovery schemes, our method handles
    loops without unrolling them; it infers abstractions that involve universal quantification
    and naturally incorporates disjunctive reasoning.
author:
- first_name: Dirk
  full_name: Beyer, Dirk
  last_name: Beyer
- first_name: Thomas A
  full_name: Thomas Henzinger
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Ritankar
  full_name: Majumdar, Ritankar S
  last_name: Majumdar
- first_name: Andrey
  full_name: Rybalchenko, Andrey
  last_name: Rybalchenko
citation:
  ama: 'Beyer D, Henzinger TA, Majumdar R, Rybalchenko A. Path invariants. In: ACM;
    2007:300-309. doi:<a href="https://doi.org/10.1145/1250734.1250769">10.1145/1250734.1250769</a>'
  apa: 'Beyer, D., Henzinger, T. A., Majumdar, R., &#38; Rybalchenko, A. (2007). Path
    invariants (pp. 300–309). Presented at the PLDI: Programming Languages Design
    and Implementation, ACM. <a href="https://doi.org/10.1145/1250734.1250769">https://doi.org/10.1145/1250734.1250769</a>'
  chicago: Beyer, Dirk, Thomas A Henzinger, Ritankar Majumdar, and Andrey Rybalchenko.
    “Path Invariants,” 300–309. ACM, 2007. <a href="https://doi.org/10.1145/1250734.1250769">https://doi.org/10.1145/1250734.1250769</a>.
  ieee: 'D. Beyer, T. A. Henzinger, R. Majumdar, and A. Rybalchenko, “Path invariants,”
    presented at the PLDI: Programming Languages Design and Implementation, 2007,
    pp. 300–309.'
  ista: 'Beyer D, Henzinger TA, Majumdar R, Rybalchenko A. 2007. Path invariants.
    PLDI: Programming Languages Design and Implementation, 300–309.'
  mla: Beyer, Dirk, et al. <i>Path Invariants</i>. ACM, 2007, pp. 300–09, doi:<a href="https://doi.org/10.1145/1250734.1250769">10.1145/1250734.1250769</a>.
  short: D. Beyer, T.A. Henzinger, R. Majumdar, A. Rybalchenko, in:, ACM, 2007, pp.
    300–309.
conference:
  name: 'PLDI: Programming Languages Design and Implementation'
date_created: 2018-12-11T12:09:32Z
date_published: 2007-06-01T00:00:00Z
date_updated: 2021-01-12T07:59:48Z
day: '01'
doi: 10.1145/1250734.1250769
extern: 1
month: '06'
page: 300 - 309
publication_status: published
publisher: ACM
publist_id: '137'
quality_controlled: 0
status: public
title: Path invariants
type: conference
year: '2007'
...