2007 | OriginalPaper | Chapter
Algorithms for Interface Synthesis
(Invited Tutorial)
Authors : Dirk Beyer, Thomas A. Henzinger, Vasu Singh
Published in: Computer Aided Verification
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A temporal interface for a software component is a finite automaton that specifies the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfaces from program code: (1) a
game
algorithm that computes the interface as a representation of the most general environment strategy to avoid a safety violation; (2) a
learning
algorithm that repeatedly queries the program to construct the minimal interface automaton; and (3) a
CEGAR
algorithm that iteratively refines an abstract interface hypothesis by adding relevant program variables. For comparison purposes, we present and implement the three algorithms in a unifying formal setting. While the three algorithms compute the same output and have similar worst-case complexities, their actual running times may differ considerably for a given input program. On the theoretical side, we provide for each of the three algorithms a family of input programs on which that algorithm outperforms the two alternatives. On the practical side, we evaluate the three algorithms experimentally on a variety of Java libraries.