Lightweight Mining of Object Usage - Mining Software Specifications: Methodologies and Applications - page 421

n is the number of different sequential constraints). The matrix is binary 2 ; if a
particular sequential constraint c j occurs in the sequential constraint abstrac-
tion of a particular function fi, i , the entry a ij in A is 1; otherwise it is 0. Thus,
the input matrix contains information saying which sequential constraints can
be found in which functions. Figure 12.6 shows a sample matrix, with filled
circles denoting 1's in the matrix, and empty cells denoting 0's.
Before proceeding further, let us define a useful metric called support of a
set of sequential constraints.
Definition 12.5.1. Let A = (a ij ) be a binary matrix (assumed to be an
input matrix to formal concept analysis) and C = fc j 1 ;:::;c j m g be a non-
empty set of sequential constraints. Support of C is dened as jFj, where
F = ff i : 8c j 2 C :a ij = 1g.
Intuitively, support of a set of sequential constraints C is the number of
functions that \support" it (i.e., whose sequential constraints abstractions
contain all of the elements in C). For example, in Figure 12.6 support of
fc 1 ;c 2 g is 3, and support of fc 2 g is 7.
Colibri/Java finds sequential constraints that are common to many func-
tions; intuitively, these are rectangles (not necessarily contiguous) in the ma-
trix. Figure 12.6 shows two such rectangles, each representing a frequent set of
sequential constraints: fc 2 ;c 4 g and fc 2 ;c 4 ;c 5 g. To determine what is frequent
and what is not, Colibri/Java needs a parameter called minimum support. This
parameter states the minimum support (as defined above) that a particular
set of sequential constraints must have for this set to be treated as frequent
(for example, if we use 4 as the minimum support value, the second of the
sets above would not be reported as frequent, because its support is 3). We
treat each such frequent set of sequential constraints as a specification.3 3 Here
is a sample specification mined from AspectJ 1.5.3, with minimum support
set to 20:
retval of CompilerAdapter() target of compile()
retval of getAbsolutePath() 1st arg of compile()
retval of openFile() target of getAbsolutePath()
This specification corresponds to the following code snippet 4 :
CompilerAdapterca=newCompilerAdapter();
ca.compile(getAbsolutePath(openFile(...)),...,...)
Code similar to the one above must thus occur in AspectJ in at least 20
different functions, and it does in fact occur in exactly 20 functions.
2 That is, each element of the matrix is either 0 or 1.
3 These are not necessarily specifications; it can always happen that there are sets of
sequential constraints that just occur frequently, but do not form a specification. This is a
problem that is common to all automatic specification mining techniques and is in general
undecidable [1].
4 We know the number of arguments of each function, because it is in practice part of an
event, and thus a sequential constraint; we omit it from events for clarity.