Mining API Usage Protocols from Large Method Traces - Mining Software Specifications: Methodologies and Applications - page 87

Iterator.next()
89

Iterable.iterator()
37

Iterator.hasNext()
37

85

Iterator.hasNext()

FIGURE 4.1: An inferred API usage protocol that shows correct iterator
usage in Java. The weights describe how often each transition was observed.

84 million runtime events and can be analyzed in 26 minutes. Analyzing the
inferred protocols for an API used by almost all Java programs, java.util,
shows that 28% of the protocols found in one program are independently
found in another program as well, and hence, can be considered typical. For
example, Figure 4.1 shows an inferred protocol that describes typical iterator
usage in Java.
The API usage protocols that our analysis infers can be used for different
applications. At first, they help in program understanding and provide docu-
mentation on common ways to use an API. Usage protocols can enrich existing
documentation by showing temporal constraints between methods in the con-
text of a particular usage scenario. Furthermore, static program analysis can
use specifications to formally prove the absence of certain errors [12] or to iden-
tify uncommon programming patterns that may be due to bugs [13, 39, 40].
Moreover, the inferred specifications can serve as input to runtime monitoring
tools that check whether a program violates certain usage rules [9, 26].
Our analysis infers typical API usage protocols from large method traces
of real-world applications. In particular, we make the following contributions:

Reduced complexity. The analysis focuses on small sets of related objects
and method calls, which can be analyzed separately. As a result, the
analysis scales to large traces of runtime events.

Mining techniques. We extract relevant parts of a program execution
and identify recurring patterns using a set of novel mining techniques,
such as comparing the roles that objects play within a certain context.

Specifications of interacting objects. The analysis produces API usage
protocols that describe common method call sequences on multiple ob-
jects.

Experimental validation. We apply an implementation of the analysis to
10 Java programs. The results show that the analysis infers typical API
usage patterns.