Static generation of UML sequence diagrams

To define a framework for static generation of sequence diagrams not tied to a particular object-oriented language, we introduce a typed control-flow graph (TCFG), an abstract model that will serve as the basis for our analysis. The model maintains both data flow (i.e., program points with state information attributed to collecting semantics, alias analysis, etc.) and control flow information (i.e., intra-procedural instructions and inter-procedural method calls). A program is abstracted by a typed control-flow graph (Definition 1) containing two types of edges: intra-procedural transfer edges and inter-procedural call edges.

For a program \(P\), we use a directed hypergraph [7] data structure where hypernodes (sets of nodes) capture the context of interactions and directed hyperedges capture the interactions of objects constituting \(P\). The order of hyperedges in a hypergraph captures the notion of causal ordering [1]; for events (invocations or returns of methods) U and V, we write \(U \rightarrow V\) if event U is causally ordered before event V. In our model, hyperedges consist of a set of origin nodes and a single target node: a many-to-one relationship.

Hyperedge annotations correspond to events in the program. Given two hyperedges, \(E_A = (S_1, t_1, A)\) and \(E_B = (S_2, t_2, B)\) with origin hypernodes \(S_1\) and \(S_2\), respectively, \(t_1\) and \(t_2\) target nodes, respectively, and annotations A and B, respectively, we say \(A \twoheadrightarrow B\) if \(t_1 \in S_2\). We define \(\rightarrow \) to be the transitive closure of \(\twoheadrightarrow \). An important component of our technique is the hyperpath construction; we define hyperpath in the context of an annotated hypergraph.

The annotated hypergraph in Definition 2 is an abstract structure that we instantiate to encode interactions, context, and causal ordering through nodes and hyperedges. We call the resulting hypergraph a code hypergraph. Before we formally define a code hypergraph, we define the set of nodes and hyperedges that will constitute it.

Nodes The nodes of a code hypergraph are of two types: code object and (method) trace. A code object captures the notion of an object in an object-oriented program. For example, the middleButtonOnClick method takes a parameter of object v of type View and is represented as a code object in the corresponding code hypergraph in Fig. 4 (indicated by rounded edges). A trace is more than just a basic block in a TCFG, it is a sequential set of instructions corresponding to an execution path for an entire method. For example, in Fig. 4, a trace node corresponding to one path of the middleButtonOnClick method is composed of instructions that would span many basic blocks in a TCFG. That is, a complete code hypergraph for the source code in Fig. 2 would contain 8 distinct trace nodes for the middleButtonOnClick method consistent with the 8 unique execution paths.

The applications of our theory rely upon the capabilities of a front-end tool. In this paper, we deferred to Soot [39] to provide datatype information from polymorphic code and dynamic bindings; Soot provides a query mechanism to identify the datatype of a particular object. The definition of code object in Definition 4 captures the fact that our technique relies on using a tool that provides a query mechanism for static object type information. Thus, the quality of the proposed procedures would suffer if the underlying analyzer is lacking.

With each node in a code hypergraph  we associate one of two categories \( Cats = {\{ \mathsf {object}, \mathsf {trace} \}}\); we define a corresponding function \(\mathsf {cat}\) that maps a node to its category. We may then define a function \(\mathsf {trace}\) to extract the trace nodes from a set of nodes \(N\), \( \mathsf {trace} \left( N \right) = {\{ n \mid n \in N\wedge \mathsf {cat}\left( n \right) = \mathsf {trace} \}}\).

Hyperedges There are two varieties of hyperedges we consider: call hyperedges based on method invocations and return hyperedges that represent objects being returned from non-void methods; our data-driven approach does not require return edges for void methods as edges enforce the dependence between control and information (objects).

Each call hyperedge is a many-to-one, annotated relationship among nodes in the hypergraph and is constructed for each method invocation. For a method invocation m in a method trace t, a hyperedge is constructed with the set of source nodes consisting of the node corresponding to t and the set of nodes corresponding to the formal parameter types of method m. The target of the hyperedge is a node corresponding to a method trace for method m. We annotate this node with the program state information for context as well as the method name. For a set of annotated hyperedges \(E_\mathcal {A}\), \( \mathsf {CallEdges} \left( E_\mathcal {A} \right) \) defines the set of call hyperedges.

As an example, Fig. 4 depicts a call hyperedge with source nodes consisting of two code objects (b and c) and a trace node representing the execution path of SetUpperRight Button. The target node of this call hyperedge is a trace node for SetBtnColor. In general, a hyperedge consists of \(n + 1\) source nodes where n is the number of formal parameters as well as one target node. Finally, the edge is annotated with the name of the method being invoked (SetBtnColor) as well as state information (\(\sigma _6\)). For a program P, we say a program state \(\sigma \) of a program \(P\) is data store for all variables at a given execution point in \(P\).

Each return hyperedge is a one-to-one relationship between an origin trace node and a target code object with an annotation comprised of the method name for the origin node and program state information for context. There are two return hyperedges in Fig. 4 representing code objects being returned. Specifically, getBlue returns a value which will be assigned to variable c (in middleButtonOnClick) indicated with a dotted line and annotated with getBlueReturn and state information (\(\sigma _3\)).

It is clear from Definition 6 that we can encode method invocations and returns as events and thus as annotations of hyperedges in a code hypergraph.

A sequence diagram is an instance of the more general message sequence chart. The literature (e.g., [1, 14, 25]) defines a message sequence chart over a set of processes and an alphabet as a tuple consisting of:Succinctly, a message sequence chart [1, 14, 25] can be described as a set of partially ordered, labeled events over a set of “processes.” We will define a sequence diagram as a code hyperpath in a code hypergraph. A code hyperpath in a code hypergraph \(H\left( N, E_\mathcal {A} \right) \), constructed from a TCFG \(\mathcal{T}\), is a hyperpath in \(H\).

We prove the equivalence of a message sequence chart with our notion of a sequence diagram as a hyperpath.

To generate sequence diagrams, the code hypergraph is extracted according to the discussion in Sect. 3 where method m is a parameter specified by the user.

In this subsection, we formalize some properties of sequence diagrams that will be used by the query-based refinement interface for narrowing down the generated set of sequence diagrams to those sequence diagrams that would be most “informative” to the user.

Since it may be beneficial to structurally compare two sequence diagrams, we define analogy of sequence diagrams through causal ordering of method calls.

We use the term analogous to define a sequence diagram S that is equivalent to a sequence diagram T in terms of causal ordering. We formalize the notion of coarse and strictly analogous sequence diagrams by viewing sequence diagram hyperpaths as graphs.

In Definition 8, we define coarse homomorphic sequence diagrams by requiring (1) corresponding nodes be equivalent for each diagram, (2) for each corresponding hyperedge the number of origin nodes of each category are equivalent and the target nodes of the hyperedge is of the same category, and (3) each hyperedge has a corresponding hyperedge in both sequence diagrams.

Definition 9 defines strict homomorphism among sequence diagrams by insisting the type of an object and its image under \(\uppsi \) be the same type. We may now define a coarse and strict sequence diagram isomorphism based on the structural requirements of the coarse sequence diagram homomorphism.

Depth of a Sequence Diagram As a metric for code complexity, we define depth which relates the longest sequence of causally ordered messages without returning. We call \(\mathcal {O}_1, \ldots , \mathcal {O}_n = {\{ \mathcal {O} \}}_i\) an object sequence where for all \(1 \le i \le n\), \(\mathcal {O}_i\) are code objects. The length of the object sequence \(\mathcal {O}_1, \ldots , \mathcal {O}_n\) is n. We define depth for a sequence diagram independent of the hypergraph definitions.

As an example, the depth of the sequence diagram in Fig. 5 is depth 2; we observe a depth of 3 in the sequence diagram in Fig. 21 when excluding the user.

Interesting Sequence Diagrams Not all sequence diagrams are of particular interest to a user. Requiring user interaction for refinement from the set of all sequence diagrams corresponding to a program is not ideal in terms of time and effort; therefore, we suggest a first step in formalizing the notion of an interesting sequence diagram to make interactions with StaticGen more efficient.

Formally defining an interesting sequence diagram requires quantification of some characteristic(s) of a sequence diagram. For a code hypergraph \(H\left( N, E_\mathcal {A} \right) \), we define \(\mathsf {Msg}\left( H \right) = \left| \mathsf {CallEdges} \left( E_\mathcal {A} \right) \right| \) where \(\mathsf {Msg}: H\rightarrow \mathbb {N}\). For a hypergraph sequence diagram D in \(H\left( N, E_\mathcal {A} \right) \), we define \(\mathsf {Msg}(D)= \mathsf {Msg}(H)_D\) where the subscript denotes restriction to D and note that \(\mathsf {Msg}\) is a measure that specifies the number of messages (method invocations) in the sequence diagram.

We define a binary relation \(\sqsubseteq \) over the set of sequence diagrams \(\mathcal {D} \) where for \(\mathcal{D}_1, \mathcal{D}_2 \in \mathcal {D} \), \(\mathcal{D}_1 \sqsubseteq \mathcal{D}_2\) if and only if \(\mathsf {Msg}\left( \mathcal{D}_1 \right) \le \mathsf {Msg}\left( \mathcal{D}_2 \right) \). \(\sqsubseteq \) defines a partial order over the set of all sequence diagrams \(\mathcal {D} \).

Before defining interesting for sequence diagrams, we define a function \(\mathsf {top} (S, k)\) that selects the maximal k elements from a partially ordered set S (ties broken arbitrarily).

Let \(\mathcal {D} _P\) be the set of all sequence diagrams for a program \(P\). For \(\mathcal{D}\subseteq \mathcal {D} _P\), let \( Msgs\left( \mathcal{D} \right) = \{ u \mid \exists D \in \mathcal{D}\text { s.t. } \mathsf {Msg}\left( D \right) = u \in \mathbb {N}\}\) and let \( Msgs\left( \mathcal{D} \right) _k\) denote the multiset of the k greatest elements of \( Msgs\left( \mathcal{D} \right) \) where \(1 \le k \le \left| \mathcal{D} \right| \). We define a function \( \mathsf {select} : \mathbb {N}\rightarrow \mathcal {D} _P\) that, for a \(u \in \mathbb {N}\), returns a sequence diagram \(D \in \mathcal {D} _P\) such that \(\mathsf {Msg}\left( D \right) = u\). If there exists multiple \(D \in \mathcal {D} _P\) with \(\mathsf {Msg}\left( D \right) = u\), ties are broken arbitrarily; \( \mathsf {select} \left( u \right) \) is undefined if there does not exist any sequence diagram \(D \in \mathcal {D} _P\) such that \(\mathsf {Msg}\left( D \right) = u\). We define a function \(\mathsf {top} \) that, for a set of sequence diagrams \(\mathcal {D} \subseteq \mathcal {D} _P\) and a fixed number \(0 \le k \le \left| \mathcal {D} \right| \), returns k sequence diagrams in \(\mathcal {D} \) having the greatest number of messages. Formally, \(\mathsf {top} \left( \mathcal {D} , k \right) = {\{ \mathsf {select} \left( u \right) \mid u \in Msgs\left( \mathcal {D} \right) _k \}}\) where \(\mathcal {D} \subseteq \mathcal {D} _P\) and \(1 \le k \le \left| \mathcal {D} \right| \).

Consider generating a set of sequence diagrams \(\mathcal {D} \) for the code in Fig. 2. \(\mathcal {D} \) would include eight sequence diagrams from middleButtonOnClick (similar to Fig. 5); each of these diagrams has 6 messages. However, our generation routine may also construct Fig. 6 as an element in \(\mathcal {D} \) corresponding to method onOptionsItemSelected in Fig. 2. Thus, \(\left| \mathcal {D} \right| = 9\) with one diagram having 2 messages and eight diagrams having 6 messages. The only way for the sequence diagram in Fig. 6 to be considered interesting is if \(k = 9\); that is, the entire set of sequence diagrams \(\mathcal {D} \) would be considered interesting. The sequence diagram in Fig. 6 is uninteresting for \(1 \le k \le 8\) since it has the lowest message count compared to the other eight sequence diagrams. Hence, the sequence diagram in Fig. 5 will be considered interesting when \(k = 8\) and, since ties are broken arbitrarily, may be considered interesting when \(1 \le k < 8\).

While it is arguable that Definition 13 may not be ideal for every user, we believe that code complexity is often rooted in the number of method invocations [9] and thus the probability is greater that a single trace can provide more information and thus is more likely to expose bugs and vulnerabilities.

Sequence diagrams can be used for debugging purposes, but can also provide a metric for code coverage in testing. We propose a definition that encompasses the notion of code coverage [6] using sequence diagrams.

As stated in Definition 2, each hyperedge is annotated with a parameterized set of values \(A\in \mathcal {A}\) defined in the generation space. The code hypergraph of Definition 6 annotates each hyperedge with method name and program state information. The code hypergraph constructed in Sect. 3 is a detailed structure representing a set of input code. A naive generation of sequence diagrams would produce an exorbitant number of diagrams, possibly of great depth, length, and detail. For this reason, we must have a method to either include or exclude a set of nodes or a set of hyperedges; this inclusion process we call pebbling. We more formally define this notion as a pebbled hypergraph in Definition 15 as computed using the pebbling process specified in Algorithm 4.

Algorithm 4 is a modification of the classic marking algorithm as first defined by Dowling and Gallier [13] for satisfiability of propositional horn clauses. Pebbling is a linear-time traversal over an annotated hypergraph that identifies the sub-hypergraph [7] consistent with user specified information. For example, if the user disallows library methods, those hyperedges with annotations containing System. or toString in Java, would not be allowed in the resulting pebbled code hypergraph. As described in Algorithm 4, pebbling is a breadth-first traversal over an annotated hypergraph where we mark each node with a pebble once it is visited (Line 7). Then, on Line 9 through Line 19, we use the following rule for pebbling and propagation: if all origin nodes of a hyperedge are pebbled, we place the target node of the hyperedge in the work list. As pebbling continues, we add all “unexpanded,” pebbled nodes (Line 8) and hyperedges (Line 15) to the sub-hypergraph in preparation for the return of the pebbled version of the hypergraph (Line 21).

For example, in Fig. 4, if we pebble the trace node for middleButtonOnClick, we immediately pebble the trace node for getBlue. In turn, we pebble the code object node for c. Then, since both source nodes are pebbled, we pebble the target trace node for Set UpperRightButton.

Our generation framework for sequence diagrams is based on the concept of “objects as messages.” That is, a method call (message) will only be invoked when all of the constituent actual parameters (objects) are in one-to-one correspondence with the formal parameters are available to initiate the message; that is, all origin nodes of a hyperedge have been pebbled. The pebbling procedure described in Sect. 4.1 is a general formalization of this notion, but with respect to sequence diagrams, pebbling is a selection process where only messages that are ready and able to be communicated appear in the resultant sequence diagrams. Branches in the original code may result in an object not being initialized, or in general, an object is not ready for communication and thus will not be pebbled.

Recursion and Pebbling We have mentioned a limitation in our approach how intra-method loops are treated as conditional expressions. However, we must also consider loop via method calls: recursion. It is easy to conceive of an example with three objects \(O_1\), \(O_2\), and \(O_3\) engage in the following method calls:While the code hypergraph constructed from the TCFG would encode this recursive instruction sequence as a cycle, the resulting pebbled code hypergraph will be acyclic. We refer to Algorithm 4 and argue informally that each node in a code hypergraph will only be expanded once. Pebbling is a worklist-based procedure that will add a node n to the list for processing when it is “discovered” on Line 3 or Line 16. When n is taken from the list on Line 5, it is first marked (pebbled) on Line 7 and then “expanded.” If n is ever added to the worklist again as being reachable via some hyperedge on Line 16, the conditional on Line 6 will prohibit expansion of n and inclusion of the hyperedge in the resulting pebbled code hypergraph. The result of this breadth-first procedure is an acyclic code hypergraph.

For a given method m, we can construct the corresponding set of all paths in a code hypergraph \(H\) using Algorithm 5 (which relies upon Algorithm 6). We note that this construction algorithm maintains the same information for a sequence diagram as stated in Definition 7, but instead of maintaining a sequential hyperpath the result is an equivalent path consisting of one-to-one edges and an associated set of objects. A method has many associated traces so Paths \(H, m\) in Algorithm 5 acquires all such traces and accumulates the set of all paths. For each trace (acquired using CollectTraceNodes on Line 3), we construct all paths. In this case, a path is a DAG whose nodes are code instructions and edges are attributed to the flow of control of the code. For a path \({{\mathcal {P}}}\), we use an object-oriented notation in which (1) \({{\mathcal {P}}}.Path\) refers to the path associated with a trace path and (2) \({{\mathcal {P}}}.\mathcal {O}\) is an associated set of code objects.

Recall that a trace T is a sequential set of instructions. In Algorithm 6, PathsFromTrace \(H, T\) loops starting on Line 3 through the set of instructions in T using i as our iterator representing an instruction seeking method calls. The Boolean function isInvocation on Line 4 will return true if the instruction is a method call. If the instruction in T is a method call, hyperpath construction is recursive (Line 7) by following the corresponding call hyperedge to the target trace node, otherwise, we simply view the instruction i as a singleton set (Line 9). Regardless of how instruction i is processed, we append the new sets of paths (\(\mathcal {Q}\)) to the old path sets (\(\mathcal {Y}\)) using procedure AppendPaths \(\mathcal {Y}\), \(\mathcal {Q}\); this includes the objects in a particular path (Line 20). We assume set union with \(\cup \) operator maintains sequential ordering of instructions and creates a directed edge from the last instruction of one path to the first instruction of the other path.

As described in Sect. 5.1, Algorithm 5 computes the set of all paths corresponding to sequential hyperpaths, including the associated objects with the path. Given a path, we construct the associated sequence diagram using Algorithm 7. The set of objects in the sequence diagram corresponds to the set of objects in the path (Line 3). Messages in the sequence diagram are constructed recursively; each method invocation instruction results in a sub-sequence diagram, \(q\) being constructed (Line 7) and appended to the main sequence diagram, \(D\) (Line 8), including a return message using addReturnMessage.

We consider the code hypergraph in Fig. 4 which depicts a single hyperpath corresponding to the code in Fig. 2. In this example, the consequent code objects in the hyperpath is an anonymous object of type Main as well as a code object of type Button (b); no methods act on code object c thus it does not appear in the resulting sequence diagram. To generate the set of method calls for the sequence diagram, we begin with the dashed hyperedge into the trace node for middleButtonOnClick. Considering each of the instructions of this trace node in turn, we add messages in causal order: recursively following call hyperedges to getBlue and SetUpperRightButton then subsequently following their respective return hyperedges. The result is the sequence diagram in Fig. 5.

We define a query over the language of sequence diagrams. The language of sequence diagrams \(\mathcal {L}\) is defined over the alphabet \(\varSigma \) consisting of code objects and method traces. For simplicity, we will refer to code objects as \(c_i\) with \(i \in \mathbb {Z}^+\), method traces as \(m_j\) with \(j \in \mathbb {Z}^+\) with corresponding method returns \(m_j'\). Hence, \(\varSigma = {\{ c \}}_i \cup {\{ m \}}_j \cup {\{ m \}}_j'\) for i and j finite in \(\mathbb {Z}^+\) and \(i \ge 1\) and \(j \ge 1\).

We note that distinct orders of topological sorts on a DAG corresponding to a hyperpath will result in distinct strings; however, each such string is unique in \(\mathcal {L}\) over the original program. A query is defined over a set of sequence diagrams \(\mathcal {D} \subseteq \mathcal {L}\) generated using the techniques described in Sect. 5; however, generation can be more targeted. It is often cumbersome and unnecessary to generate all sequence diagrams beginning at a main method in a program. Generation can be performed on-demand beginning at any method reducing the size of the corresponding hypergraph. In order to acquire the initial set of sequence diagrams \(\mathcal{D}_S\), we may use the predicate “start M,” where M is a method dictating where the resultant sequence diagram(s) will begin.

Query Operations. A query \(Q={\{ q \}}_i\) over \(\mathcal {L}\) consists of a finite sequence of operations \({\{ q \}}_i\) that refine the given set of sequence diagrams \(\mathcal {D} \subseteq \mathcal {L}\) into the resulting set \(Q(\mathcal {D} ) = F \subseteq \mathcal {D} \).We define a simple grammar for a query \(Q\) over \(\mathcal {L}\); the terminal symbols include \(\ell \), \(R\), \(0 \le p \le 1\), and \(k \in \mathbb {Z}^+\) as defined above.The code hypergraph is a representation of all traces of a program; it is thus a prohibitively large structure. We therefore give the user the power to define queries that will make the analysis tractable and the resulting set of sequence diagrams more likely to be meaningful. For example, a user may not want to dive into a complete analysis of a program from a main method, instead they may begin their analysis at any arbitrary method. Our solution is a set of modes of refinement. A user-defined query is a tuple of refinement modes or global query predicates. A refinement mode is of the form \({\left\langle t, m \right\rangle }\) where t is a unique identifier for an object or a method and m is a mode descriptor; we define each of the mode descriptors below.Beyond refinement modes, global query predicates prune the resulting set of sequence diagrams. Using our definition for interesting sequence diagrams, a user may use the predicate “top-interesting d” where d is an integer specifying the number of resulting diagrams. Similarly for code coverage, we may refer to “function-cover p” or “branch cover p” where p is a lower bound percentage of the coverage desired.

In this subsection, we formalize the query language semantics by describing the denotational interpretation of the query language and operations defined in Sect. 6.1.

We define \(\mathsf {D}\) to be the set of string objects over the language of sequence diagram strings \(\mathcal {L}\). These sequence diagram string objects also maintain diagram information including, but not limited to the number of messages, branch coverage, and method coverage. Our query language consists of a set of predicates, \(R\), over a set of set of sequence diagrams, \(\mathsf {D}\). We use emphatic brackets \(\llbracket \ \rrbracket \) to express denotations of expressions in the query language. We first consider the set of operations related to evaluating predicates. For the set of predicates \(R\), we evaluate a sequence diagram \(\mathsf {d}\in \mathsf {D}\) to confirm if it adheres to a subset of predicates in \(R\): we define \(\mathsf {Eval}: (D \times 2^{R}) \rightarrow {\{ true, false \}}\). We then define a function E which evaluates a given operation \(\mathsf {BoolOp}\), \(\mathsf {E}: \mathsf {BoolOp} \rightarrow \mathsf {Eval}\). Since our operations result in boolean expressions, we define standard notions of logic-based commands, \(\mathsf {BoolOp}\). For \(\varepsilon , \varepsilon ' \in \mathsf {Eval}\), \(\mathsf {d}\in \mathsf {D}\), and predicates \(R' \in 2^{R}\):The last expression is the boolean evaluation of a single predicate over a single sequence diagram.

For language operation commands \(\mathsf {Oper}\), we define a function \(\mathsf {C}: \mathsf {Oper} \rightarrow ((2^\mathsf {D}\times 2^{R}) \rightarrow 2^\mathsf {D})\), ensuring each query operation takes a set of sequence diagrams and returns a refined subset of sequence diagrams. We define sequential execution of operations \( \mathsf {C} {\llbracket } \gamma _1 ; \gamma _2 {\rrbracket } \left( \mathsf {d}, R' \right) = \mathsf {C} {\llbracket } \gamma _1 {\rrbracket } \left( \mathsf {d}, R' \right) \ \circ \ \mathsf {C} {\llbracket } \gamma _2 {\rrbracket } \left( \mathsf {d}, R' \right) \) with \(\circ \) referring to function composition. We then define a basic conditional operation: with \(\varepsilon \in \mathsf {Eval}\) and \(\gamma \in 2^{\mathsf {D}}\), \(\gamma ' \ {:}{:}= \ \varvec{if}\ \varepsilon \ \varvec{then}\ \gamma \ \). This expression is a traditional if-then statement where the missing “else” evaluates to an empty set:if \( \mathsf {E} {\llbracket } \varepsilon {\rrbracket } \left( {\{ \mathsf {d} \}} , R' \right) = true\), otherwise \(\emptyset \).

Before we define the denotational semantics of the query operations, we define two support operations. In some cases, the user may wish to exclude elements of a sequence diagram such as a particular variable or method; the first support operation defines a means of such pruning mechanisms. \(\mathsf {Mutate}\) is a function that maps a mutation operation, \(\mathsf {MutOp}\) to a function that takes a sequence diagram and returns a modified version of the sequence diagram: \(\mathsf {Mutate}: \mathsf {MutOp} \rightarrow (\mathsf {D}\rightarrow \mathsf {D})\). The second support function \(\mathsf {Property}\) is a mapping from a property operation \(\mathsf {PropOp}\) that takes a sequence diagram and returns a quantity related to the diagram (e.g., method count, method coverage, etc.): \(\mathsf {Property}: \mathsf {PropOp} \rightarrow (\mathsf {D}\rightarrow \mathbb {R})\).

We may now define the denotational semantics of the query operations.

To properly define filtration, we first define two mutation operations, one for code objects and one for methods.

For a string s and two characters a, z, we assume the standard substring operation \(\mathsf {substr}(s, a, z)\) returns the string beginning at a through all characters ending with (and including) z. In the case where characters a or z is not found in s, \(\mathsf {substr}(s, a, z)\) returns an empty string. We define a complementary operation \(\mathsf {rem\_\mathsf {substr}}(s, a, z)\) which returns the original string excluding all such substrings \(\mathsf {substr}(s, a, z)\). If \(\mathsf {substr}(s, a, z)\) does not appear in s, \(\mathsf {rem\_\mathsf {substr}}(s, a, z) = s\) by returning the original string, unmodified; \(\mathsf {rem\_\mathsf {substr}}(s, a, a) = a\) deletes all occurrences of character a from string s.

For a sequence diagram string \(\mathsf {d}\), a character m.a corresponding to method m, and a character m.z corresponding to the return of method m, \(\texttt {prune}(\mathcal{D}, m) = \mathsf {rem\_\mathsf {substr}}(\mathcal{D}, m.a, m.z) \in \mathsf {MutOp}\) removes method m from \(\mathsf {d}\).

Pruning a code object c from a sequence diagram is a more involved process since it requires we prune c as well as all methods that act on c. For a sequence diagram string \(\mathsf {d}\) and a character o corresponding to code object c, we prune all methods \(m_i\) \(0 < i \le k\) that call a method defined by code object c; we define functionally with a functional-style pattern matching and list dissection.The first function removes the actual code object c from the diagram (invoked last). The second function removes all occurrences of method m from the sequence diagram. The third function iterates through all methods for which code object c interacts. The final function invokes all method removal and code object removal, respectively.

With \(\texttt {prune}\) defined, we may now filter a single diagram with a set of predicates: \(\gamma \ {:}{:} = \texttt {filter}({\{ \mathsf {d} \}}, L) = \texttt {prune}(\mathsf {d}, L)\). Filtering many diagrams over a set of predicates: \(\gamma \ {:}{:}= \texttt {filter}(\mathsf {D}, L) = \bigcup _{\mathsf {d}\in \mathsf {D}} \texttt {filter}({\{ \mathsf {d} \}}, \ell )\).

For clarity and simplicity, we define an evaluator to determine if a diagram \(\mathsf {d}\) satisfies all predicates in a set \(R\).For a set of predicates \(R\) and a sequence diagram \(\mathsf {d}\), a diagram is removed if \(\texttt {remove}(R, \mathsf {d})\) evaluates to true; that is, diagram \(\mathsf {d}\) does not satisfy all \(r\in R\):

\(\gamma \ {:}{:}= \texttt {remove}(R, \mathsf {d}) =\)

\( \mathsf {C} {\llbracket } \ \varvec{if}\ \ \varvec{not}\ \left( \texttt {satisfies}(R, \mathsf {d}) \right) \ \varvec{then}\ {\{ \mathsf {d} \}}\ {\rrbracket } \left( {\{ \mathsf {d} \}} , R' \right) .\) Similarly, for a set of diagrams \(\mathsf {D}\), \(\texttt {remove}(R, \mathsf {D}) = \bigcup _{\mathsf {d}\in \mathsf {D}} \texttt {remove}(R, {\{ \mathsf {d} \}})\).

Similarly, \(\texttt {accept}(R, \mathsf {d})\) requires \(\mathsf {d}\) satisfy all \(r\in R\):For a set of sequence diagrams \(\mathsf {D}\), \(\texttt {accept}(R, \mathsf {D}) = \bigcup _{\mathsf {d}\in \mathsf {D}} \texttt {accept}(R, \mathsf {d}).\) We note that accept and remove have similar, yet opposing goals where an accept command followed by a remove with the same set of predicates results in an empty set:This observation is also true when remove precedes accept: \(\texttt {accept} \left( R, \texttt {remove}(R, \mathsf {D}) \right) = \emptyset \).

Let \(\mathsf {D}= {\{ \mathsf {d}_i \}}\) be a set of sequence diagrams ordered by the number of messages: for all \(1 \le i < j \le \left| \mathsf {D} \right| \), \(\mathsf {Msg}\left( \mathsf {d}_i \right) \le \mathsf {Msg}\left( \mathsf {d}_j \right) \). In [11], the authors define the function \(\texttt {select}(k, S)\) which returns the k-th largest element in a set S. We modify this notion to define \(\texttt {select}(k, \mathsf {D})\) to return the sequence diagram corresponding to the k-th largest number of messages of the sequence diagrams in \(\mathsf {D}\). We select the top-k sequence diagrams:Hence, \(\gamma \ {:}{:}= \texttt {top-interesting}(k, \mathsf {D}) = \texttt {top}(\mathsf {D}, k)\) results in the set corresponding to \(\mathsf {D}\) restricted to the top-k: \({\{ \mathsf {d}\in \mathsf {D}\mid \mathsf {d}_{\left| \mathsf {D} \right| - k + 1}, \mathsf {d}_{\left| \mathsf {D} \right| - k + 2}, \ldots , \mathsf {d}_{\left| \mathsf {D} \right| } \}}.\)

Sequence diagram object representations maintain code coverage metrics. For branch and method coverage, respectively,and

We present an interface where a user of StaticGen can query over the set of sequence diagram features to obtain a subset of sequence diagrams. Our methodology requires manual input of the code as well as a query \(Q\) as previously described. Depending on the specification of \(Q\), we may omit, through the pebbling process, call hyperedges corresponding to method calls that may be removed. Given a pebbled code hypergraph, we construct the corresponding set of all sequence diagrams. We then filter the resulting set of sequence diagrams related to method removal, coverage, or \(\mathsf {top} \) into the desired set of sequence diagrams.

If the user wishes to refine \(Q\) into \(Q'\), we may re-pebble the code hypergraph and generate according to \(Q'\). Our query system provides continual refinement until the appropriate set of sequence diagrams is acquired. That is, initially, a user might simply request a set of interesting sequence diagrams. Then, as the user becomes more familiar with the code base, they may define a more restricted query. This process of query refinement can continue ad libitum.

Within the bounds of the user selected query, we prioritize what the user sees by first eliminating strictly isomorphic diagrams and diagrams which are “subsets” of other diagrams. We then determine the set of sequence diagrams S that match the user’s query. Using a method coverage metric for the code, we prioritize the diagrams into a list I using the following greedy algorithm. Using this construction, I is a minimal coverage set for the input code and provides a desired viewing order with the most unique information possible in the fewest views of diagrams, assuming a quality user query.

Assume the user specifies as input the code base containing the source code in Fig. 2. To filter elements from the set of resulting sequence diagrams, the user defines a query \(Q\) with start being middleButtonOn Click and filters object r and its corresponding methods as well as the setText method. The result is eight diagrams, seven of which are strictly isomorphically unique, and one of which is shown in Fig. 5. If we append to \(Q\) an accept predicate with SetUpperRight Button(int), the only diagram returned is shown in Fig. 5. As another example, Fig. 6 arises from a query requesting the least interesting diagram from analyzing all methods.

Queries can be used to select a more sophisticated set of diagrams. Queries can choose to accept diagrams with certain characteristics, for example the query in Fig. 7 will reduce the diagrams generated by the code in Fig. 2 to only the diagrams containing the methods SetUpperRightButton(int) or SetUpperLeft Button(int). In a larger example, the complete package name of the method to be queried would be required. Figure 8 will take the set of all possible diagrams, and remove any diagram that contains the method SetUpperRightButton (int). In the remaining diagrams, any calls to the method nextInt(int) will be omitted from the diagram. This will also necessarily remove any calls that nextInt(int) would make to any other methods. The diagrams would appear as if the call to nextInt(int) simply did not exist.

We also have the capacity to produce more sophisticated queries by combining accept or reject criteria with the or and and operations. In Fig. 9, we can see three methods that are combined with the and operator. In order for a diagram to be a member of the output set of this query, it must pass each of the components of that query. Therefore, it must contain both the methods SetUpperLeftButton(int) and getRed() and not have a call to the method getBlue(). This query language allows the user to select a very specific subset of the diagrams produced by the system. Additionally, the query framework produces an output both as diagrams and as a dataset of json files which can be used as another input to the querying system, allowing that subset to serve as a starting point for another round of querying.

The query language defined in this section is based on the intuitive constructs that a software engineer may normally be looking for while trying to understand a program. For example, a software engineer may wish to use the tool for the following use cases: (1) they may filter a set of sequence diagrams based on some criteria, (2) remove sequence diagrams that they may not be interested in, (3) request a set of sequence diagrams that satisfy certain criteria, and (4) want to see the most interesting sequence diagrams that would lead to better understanding of the code. The query language attempts to formalize the intuitive notions of what a user requires. However, we admit that, over time, the features for which we have defined our query language should evolve to meet the needs of future users.

Our initial tests have focused on open-source Android bytecode applications taken from [12, 44] with wide-ranging focus, including: ad blocking, email, and web browsing. The bytecode was input into the Soot framework [39] which can process bytecode or source code thus bringing the same capabilities to bear, independent of input format. Table 1 lists the projects and corresponding facts about each code base in the chosen corpus, including the package we analyzed, the number of constituent classes, processing time, and the operation count.

Soot analyzes bytecode by breaking down classes into groups of methods, and methods into groups of abstract statements; the number of abstract statements is referred to as the operation count. While operation count may not correspond one-to-one with source lines of code, it does correspond to essential logical statements executed by the processor, and are a useful measurement of the complexity of the program analyzed. The operation count for our corpus is shown in Table 1.

As another measure of complexity of our corpus, the target Android code, we consider the histogram in Fig. 10 depicting the mean depth of diagrams for non-library functionality for each benchmark Android package. Our event-driven benchmarks are generally shallow as is evident in Fig. 10; the mean among all packages is \(1.29\) with standard deviation \(0.92\). We view the depth metric as a guide to the number of corresponding sequence diagrams; the greater the depth, the more diagrams should result. Figure 11 is a scatterplot of the relationship between mean depth and number of diagrams generated. We see a linear model given by \(y=887.58x-496.56\), where y is the number of diagrams generated, and x is the mean depth of the set of diagrams for an Android package. The correlation is moderate with correlation coefficient \(r^2 = 0.5643{}\).

We measure tool efficiency by considering generation time. Our reported execution times include Soot’s Simplification [39] procedure, hypergraph construction, diagram generation, and refinement. In Fig. 12, several Android packages are processed quickly. However, the mean of \(96.78 s\) and the standard deviation of \(174.58 s\) indicates more complex packages result in greater time dispersion. For each Android package, Fig. 13 describes the number of diagrams that give complete method coverage. Some of the more complex packages skew the distribution (std. dev. \(1085.23\) and mean \(647.1\)) with a strongly correlated linear model (\(r^2 = 0.9082{}\)) comparing the number of diagrams with respect to generation time. This is strong evidence indicating our technique does not require a significant amount of processing time for code bases with large sets of sequence diagrams.

We test the usefulness of our interestingness metric by examining the possibility of using it in uncovering security vulnerabilities in code in concert with diagram filtering. We selected an independently studied example for assessing our definition of interestingness. Both Livshits [26] and Sampaio [40] used a web application named blueblog [8] in their corpora of applications with security vulnerabilities. In addition, [40] provided a software tool, ESVD [30], to analyze code for vulnerabilities.

We focus on a vulnerability evident in the unsafe http request in the code in Fig. 14 that was originally detected by ESVD [30]. The value returned by the getServletPath function is stored in the variable url and is not sanitized by both branches.

As described in Sect. 2, we have a methodology to allow us to select a subset of all sequence diagrams \(\mathcal {D} \) and to rank those diagrams by the number of methods present in the diagram such that \(\left| \mathcal {D} \right| = k\) where k is defined by user query. Our methodology of selecting and filtering proceeds as follows. From all diagrams generated, we select \(D\in \mathcal {D} \) (using \(k_I = 1\)) with the most messages adding \(D\) to our interesting set \(\mathcal {D} _I\). For all remaining diagrams \(\mathcal {D} \setminus {\{ D \}}\), we filter each diagram in \(\mathcal {D} \) for code objects and methods found in \(D\). We repeat this process until k diagrams are acquired. This procedure thus selects diagrams by how much new information they add.

Our experiment with blueblog defined \(k = 45\). Without any filtering, StaticGen generated 2800 diagrams from blueblog. The doGet method was the subject of the diagrams ranked 22 and 32 of the 45 interesting diagrams; a fragment of the rank-22 diagram is shown in Fig. 15. This example shows that prioritizing novel information allows us to reduce a set of diagrams while retaining information about code paths that can possibly lead to a vulnerability. This reduced set of diagrams can then be delegated to a human expert or a vulnerability analysis tool for further analysis for security vulnerabilities. It is possible that an excluded diagram may contain the vulnerability; however, our queries focusing on interestingness and filtration ensures each diagram provides novel information. The discarded diagrams, because they have fewer messages than the selected ones, and because they provide less novel information, would therefore less likely be the ones that solely contain/reveal the vulnerability. Hence, it is with low probability that a vulnerability is relegated to the set of discarded diagrams.

An important characteristic to object-oriented languages is dynamic dispatch through polymorphically defined methods. A sequence diagram, because it views the lifetimes and messages of different object instances, may not clearly explain at what level inheritance a particular method is actually handled. The UML language provides the ability to represent these situations using a “scenario box” that lists all possible alternatives. While listing all alternatives may properly convey operational semantics, it becomes cumbersome to users and obfuscates code in large class hierarchies. Soot, as an underlying component to StaticGen provides complete datatype information of each object: \( \mathsf {Datatype} \left( \texttt {obj} \right) = \texttt {Derived}\) in the code from Fig. 16. We recognize that static analysis of code does have its limitations specifically with polymorphic code, but we wish to present how StaticGen handles basic polymorphism relying on Soot.

Sequence diagrams present object instances as having a single name and a single type, while an object instance passed to different methods may possess several names, and its interactions may be guided by any of the types in its inheritance ancestry. StaticGen maintains a list of the names and types used for a single object instance throughout a hypergraph traversal, and, when presenting that information as a sequence diagram, presents what it sees as the most expressive name and the most specific type. Generalizing the type of an object has a corresponding loss in precision. Our hypergraph traversal represents method calls with their complete names, including the package name, class name, method name, and argument type signature. While an argument can be made that sequence diagrams are not ideal for expressing more complex polymorphic interactions, hypergraph traversal can precisely handle all these interactions.

As a brief example of how StaticGen handles polymorphism, we consider the code in Fig. 16 and the corresponding sequence diagram in Fig. 17. In Fig. 16, a simple inheritance is established with Derived inheriting from BaseClass. In main, object obj is created with \( \mathsf {Datatype} \left( obj \right) = \texttt {Derived}\) and two methods are subsequently called. Together these three method calls (new, overridden, and unique) are reflected clearly in the sequence diagram.

We consider these three calls in turn which correspond directly to the sequence diagram Fig. 17. Since constructors are not defined, yet exist in the bytecode, creation of object obj with new results in two subsequent self-calls to super-constructors in BaseClass and class Object. Next, overridden is called and handled in class Derived. We observe a self-call to overridden since Derived.overridden invokes a super call to BaseClass.overridden. Last, unique is handled entirely in BaseClass.

While StaticGen is effective for basic polymorphism among classes and hierarchies, StaticGen relies on Soot for pointer analysis. Consider a list of objects of type BaseClass (List<BaseClass>) which may contain both BaseClass and Derived objects. In the list structure, the contents become amorphous and the corresponding sequence diagrams present more generic information.

Sequence diagram generation is not a new idea. In this subsection, we compare StaticGen to an existing tool. Specifically, we compare a single run of our StaticGen to Diver [32], an eclipse plug-in which generates sequence diagrams from a trace of program execution. As described in related work (Sect. 8), other sequence diagram generation tools are described in the literature, but only a small subset of these tools are actually accessible. These UML Case tools [5, 31, 34, 41, 43] do not provide a query language that allows refinement in the way StaticGen provides. Dynamic tools [32] for generating sequence diagrams uncover sequence diagrams that actually occur during execution. It is therefore interesting to compare the effectiveness of a static tool like StaticGen with a dynamic tool like Diver. Our goal is to show that our static analysis tool compares well to a dynamic tool: static diagrams map to traces occur during dynamic execution. Our Diver tests were executed on version 0.5.0.201209240108, downloaded from the github repository [10] running Eclipse (Luna Service Release 1a 4.4.1) [16]. The target program was FindBugs [35]: a mature java source code base easily accessible for analysis with both tools. For full disclosure, it is important to state that the goal of our case study comparison should not be taken as a full feature comparison or a recommendation to use StaticGen over Diver. Our platform is an academic prototype while Diver is mature (undergone significant revision and bug fixing over several years). Additionally, we have extensive experience with our own tool and only basic experience with Diver. The working Diver example was found first, and then we attempted to replicate the same results using our tool (Fig. 18).

We focus on the addOption method in package edu. umd.cs.findbugs.

config.CommandLine shown in Fig. 19. The sequence diagram in Fig. 18 depicts the output from Diver and its trace. With Diver, there does not appear to be an obvious way to save or export a specific diagram from a trace without providing the entire diagram. The Diver trace allows expansion of called methods to the desired level in the resulting sequence diagram. There are several similarities between the Diver diagram in Fig. 20 and StaticGen in Fig. 18; clearly the order of the methods are equivalent. StaticGen preserves more, but not all, variable names (option and argumentDesc). StaticGen also maintains individual objects thus differentiating method calls to length on distinct objects; similarly for the two calls to put on Map. It can be argued that the default Diver display is more compact; however, it is unclear in the expansion in Fig. 20 whether Diver differentiates method calls from distinct objects thus providing less accurate information.

We detail some differences between our approach and Diver. In package edu.umd.findbugs.gui2, we consider the constructor of class GUI2CommandLine. The diagram in Fig. 21 is the complete, allowable expansion of this flow through Diver starting at the class constructor. For the code in Fig. 22, StaticGen was able to visualize greater depth into the static class constructor for the class Driver (Fig. 23) in edu.umd.cs.findbugs.gui2. Generally, in comparison, StaticGen can offer users a view of object creation from any level; StaticGen produced 55 total potential execution path diagrams which we could query and sort.