Event-driven programming frameworks, such as Android, are based on components with asynchronous interfaces. The protocols for interacting with these components can often be described by finite-state machines we dub *callback typestates*. Callback typestates are akin to classical typestates, with the difference that their outputs (callbacks) are produced asynchronously. While useful, these specifications are not commonly available, because writing them is difficult and error-prone. Our goal is to make the task of producing callback typestates significantly easier. We present a callback typestate assistant tool, DroidStar, that requires only limited user interaction to produce a callback typestate. Our approach is based on an active learning algorithm, L*. We improved the scalability of equivalence queries (a key component of L*), thus making active learning tractable on the Android system. We use DroidStar to learn callback typestates for Android classes both for cases where one is already provided by the documentation, and for cases where the documentation is unclear. The results show that DroidStar learns callback typestates accurately and efficiently. Moreover, in several cases, the synthesized callback typestates uncovered surprising and undocumented behaviors.
Inferring interfaces using execution traces of client programs using the framework is another common approach @cite_15 @cite_16 @cite_4 @cite_12 @cite_24 @cite_10 @cite_27 @cite_8 . In contrast to dynamic mining, we do not rely on the availability of client applications or a set of execution traces. The algorithm drives the testing.
@cite_4 @cite_8 @cite_24 @cite_27 @cite_15 @cite_16 @cite_10 @cite_12
2166064937 2093938715 2131954495 2121059325 2074001172
A software system interacts with its environment through interfaces. Improper handling of exceptional returns from system interfaces can cause robustness problems. Robust- ness of software systems are governed by various tempo- ral properties related to interfaces. Static verification has been shown to be effective in checking these temporal prop- erties. But manually specifying these properties is cum- bersome and requires the knowledge of interface specifica- tions, which are often either unavailable or undocumented. In this paper, we propose a novel framework to automati- cally infer system-specific interface specifications from pro- gram source code. We use a model checker to generate traces related to the interfaces. From these model check- ing traces, we infer interface specification details such as return value on success or failure. Based on these inferred specifications, we translate generically specified interface robustness rules to concrete robustness properties verifi- able by static checking. Hence the generic rules can be specified at an abstract level that needs no knowledge of the source code, system, or interfaces. We implement our framework for an existing static analyzer that employs push down model checking and apply the analyzer to the well known POSIX-API system interfaces. We found 28 robust- ness violations in 10 open source packages using our frame- work. Program specifications are important for many tasks during software design, development, and maintenance. Among these, temporal specifications are particularly useful. They express formal correctness requirements of an application's ordering of specific actions and events during execution, such as the strict alternation of acquisition and release of locks. Despite their importance, temporal specifications are often missing, incomplete, or described only informally. Many techniques have been proposed that mine such specifications from execution traces or program source code. However, existing techniques mine only simple patterns, or they mine a single complex pattern that is restricted to a particular set of manually selected events. There is no practical, automatic technique that can mine general temporal properties from execution traces. In this paper, we present Javert, the first general specification mining framework that can learn, fully automatically, complex temporal properties from execution traces. The key insight behind Javert is that real, complex specifications can be formed by composing instances of small generic patterns, such as the alternating pattern ((ab)) and the resource usage pattern ((ab c)). In particular, Javert learns simple generic patterns and composes them using sound rules to construct large, complex specifications. We have implemented the algorithm in a practical tool and conducted an extensive empirical evaluation on several open source software projects. Our results are promising; they show that Javert is scalable, general, and precise. It discovered many interesting, nontrivial specifications in real-world code that are beyond the reach of existing automatic techniques. Dynamic inference techniques have been demonstrated to provide useful support for various software engineering tasks including bug finding, test suite evaluation and improvement, and specification generation. To date, however, dynamic inference has only been used effectively on small programs under controlled conditions. In this paper, we identify reasons why scaling dynamic inference techniques has proven difficult, and introduce solutions that enable a dynamic inference technique to scale to large programs and work effectively with the imperfect traces typically available in industrial scenarios. We describe our approximate inference algorithm, present and evaluate heuristics for winnowing the large number of inferred properties to a manageable set of interesting properties, and report on experiments using inferred properties. We evaluate our techniques on JBoss and the Windows kernel. Our tool is able to infer many of the properties checked by the Static Driver Verifier and leads us to discover a previously unknown bug in Windows. Component-based software design is a popular and effective approach to designing large systems. While components typically have well-defined interfaces, sequencing information---which calls must come in which order---is often not formally specified.This paper proposes using multiple finite statemachine (FSM) submodels to model the interface of a class. A submodel includes a subset of methods that, for example, implement a Java interface, or access some particular field. Each state-modifying method is represented as a state in the FSM, and transitions of the FSMs represent allow able pairs of consecutive methods. In addition, state-preserving methods are constrained to execute only under certain states.We have designed and implemented a system that includes static analyses to deduce illegal call sequences in a program, dynamic instrumentation techniques to extract models from execution runs, and a dynamic model checker that ensures that the code conforms to the model. Extracted models can serve as documentation; they can serve as constraints to be enforced by a static checker; they can be studied directly by developers to determine if the program is exhibiting unexpected behavior; or they can be used to determine the completeness of a test suite.Our system has been run on several large code bases, including the joeq virtual machine, the basic Java libraries, and the Java 2 Enterprise Edition library code. Our experience suggests that this approach yields useful information. To learn what constitutes correct program behavior, one can start with normal behavior. We observe actual program executions to construct state machines that summarize object behavior. These state machines, called object behavior models, capture the relationships between two kinds of methods: mutators that change the state (such as add()) and inspectors that keep the state unchanged (such as isEmpty()): "A Vector object initially is in isEmpty() state; after add(), it goes into ¬isEmpty() state". Our ADABU prototype for JAVA has successfully mined models of undocumented behavior from the AspectJ compiler and the Columba email client; the models tend to be small and easily understandable.