Structurally Defined Conditional Data-Flow Static Analysis

Elena Sherman, Matthew B. Dwyer

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Scopus citations

Abstract

<p> <p id="x-x-x-Par1"> Data flow analysis (DFA) is an important verification technique that computes the effect of data values propagating over program paths. While more precise than flow-insensitive analyses, such an analysis is time-consuming. <p id="x-x-x-Par2"> This paper investigates the acceleration of DFA by structural decomposition of the underlying control flow graph. Specifically, we explore the cost and effectiveness of dividing program paths into subsets by partitioning path suffixes at conditional statements, applying a DFA on each subset, and then combining the resulting invariants. This yields a family of independent DFA problems that are solved in parallel and where the partial results of each problem represent safe program invariants. <p id="x-x-x-Par3"> Empirical evaluations reveal that depending on the DFA type and its conditional implementation the invariants for a large fraction of program points can be computed in less time than traditional DFA. This work suggests a strategy for an &ldquo;anytime DFA&rdquo; algorithm: computing safe program invariants as the analysis proceeds. </p> </p> </p></p>
Original languageAmerican English
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems: 24th International Conference, TACAS 2018 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018 Thessaloniki, Greece, April 14-20, 2018
EditorsDirk Beyer, Marieke Huisman
PublisherSpringer Verlag
Pages249-265
Number of pages17
ISBN (Print)9783319899626
DOIs
StatePublished - 1 Jan 2018
Event24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2018 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018 - Thessaloniki, Greece
Duration: 14 Apr 201820 Apr 2018

Publication series

Name0302-9743

Conference

Conference24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2018 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018
Country/TerritoryGreece
CityThessaloniki
Period14/04/1820/04/18

EGS Disciplines

  • Computer Sciences

Fingerprint

Dive into the research topics of 'Structurally Defined Conditional Data-Flow Static Analysis'. Together they form a unique fingerprint.

Cite this