Inductive data flow graphs

Azadeh Farzan, Zachary Kincaid, Andreas Podelski

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The correctness of a sequential program can be shown by the annotation of its control flow graph with inductive assertions. We propose inductive data flow graphs, data flow graphs with incorporated inductive assertions, as the basis of an approach to verifying concurrent programs. An inductive data flow graph accounts for a set of dependencies between program actions in interleaved thread executions, and therefore stands as a representation for the set of concurrent program traces which give rise to these dependencies. The approach first constructs an inductive data flow graph and then checks whether all program traces are represented. The size of the inductive data flow graph is polynomial in the number of data dependencies (in a sense that can be made formal); it does not grow exponentially in the number of threads unless the data dependencies do. The approach shifts the burden of the exponential explosion towards the check whether all program traces are represented, i.e., to a combinatorial problem (over finite graphs).

Original languageEnglish (US)
Pages (from-to)129-142
Number of pages14
JournalACM SIGPLAN Notices
Volume48
Issue number1
DOIs
StatePublished - Jan 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Concurrency
  • Static analysis
  • Verification

Fingerprint Dive into the research topics of 'Inductive data flow graphs'. Together they form a unique fingerprint.

Cite this