Inductive data flow graphs

Azadeh Farzan, Zachary Kincaid, Andreas Podelski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 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)
Title of host publicationPOPL 2013 - Proceedings of 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
Pages129-142
Number of pages14
DOIs
StatePublished - Feb 26 2013
Externally publishedYes
Event40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2013 - Rome, Italy
Duration: Jan 23 2013Jan 25 2013

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

Other

Other40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2013
CountryItaly
CityRome
Period1/23/131/25/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • concurrency
  • static analysis
  • verification

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

  • Cite this

    Farzan, A., Kincaid, Z., & Podelski, A. (2013). Inductive data flow graphs. In POPL 2013 - Proceedings of 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (pp. 129-142). (Conference Record of the Annual ACM Symposium on Principles of Programming Languages). https://doi.org/10.1145/2429069.2429086