match of the custom structure; that is, only events connected in the specified order, without any interleaving events, will be shown as a search result. Developers can further filter the result set by specifying host-name constraints. A host timeline with an added constraint will only map to timelines in the execution graph that satisfy the given restriction. For example, the right side of Figure 5 shows how ShiViz visualizes two highlighted matching patterns corresponding to the custom query on the left.

The query in Figure 5 corresponds to use case 2 in Section 2; it is an example of a user-defined sub-graph with host-name constraints. In this figure, the Client* constraint on the left-most host constrains the structured search to match host names like Client-1.

Alternatively, developers can search for a predefined sub-graph pattern (middle of Figure ShiViz has three such patterns: (1) request-response: a source host sends a request and the nation host sends a response back; (2) broadcast: a host sends a message to most other hosts the system; (3) gather: a host receives a message from most other hosts. Figure 6 lists search results for these three predefined sub-graph patterns. The predefined searches are advanced than the custom structured search and can find variations of an underlying pattern. instance, a broadcast can be represented as a sequence of separate send events, as illustrated blue in Figure 6, or as multiple sends at once, as seen in green in the same figure. Both tures will be highlighted as a search result. The predefined sub-graphs are also more flexible

ACM Transactions on Software Engineering and Methodology, Vol. 29, No. 2, Article 9. Pub. date: March 2020.



Fig. 6. Example search results for three predefined sub-graph search patterns in ShiViz.

not restricted to exact matches. For instance, when querying for request-response interactions, events interleaving between the request and response events will not interfere with detection of the pattern.

Both the user-defined and predefined searches allow developers to locate communication pat- terns of interest within an execution graph. The presence or absence of queried sub-graphs at particular points in an execution can help developers detect anomalous behavior, aiding them in their debugging efforts.

4.2.2 Keyword Search. Unlike the structured search, which allows the developer to find patterns in the structure of the graph, a keyword search allows a developer to search across the events’ data fields.

Developers can query for a particular word or phrase and find all events in the graph with a field matching the search. These constraints can be generalized with JavaScript regular expressions and combined through logical connectives.

In both types of searches, the developer interacts with the search results in one of two ways. The developer can scroll through the execution graph to find the highlighted search results manually, or they can jump to the previous/next instance in the results using a pair of arrow buttons in the

Multi-execution Comparing and Clustering

A common challenge for studying a concurrent system over several executions is the nondeter- minism that makes two executions not directly comparable. That is, an interleaving difference may make two logs appear behaviorally different even though the system that produced the logs is the same. For this reason, we decided to extend ShiViz to support developers in understanding and juxtaposing multiple executions recorded in the log. Specifically, when ShiViz parses more than one execution from the log, it allows the developer to view any single execution or any pair of

The features described previously (e.g., search, hiding a host) continue to operate in the side- by-side view. For example, if the developer hides a host in the left execution, the same host will be hidden in the right execution.

4.3.1 Highlighting Differences between Executions. A feature exclusive to the pairwise view is the ability to highlight differences between two executions. To use this feature the user selects a base execution, against which other executions will be compared. Hosts or events in an execution that do not appear in the base execution are drawn as rhombuses (Figure 7). This highlighting is

ACM Transactions on Software Engineering and Methodology, Vol. 29, No. 2, Article 9. Pub. date: March





Fig. 7. ShiViz uses rhombuses to highlight differences between executions. Here, compared to a base tion (a), the execution in (b) has a different host, and the execution in (c) differs in both hosts and events.

done by walking the timeline of corresponding processes and comparing each event against events in the base execution.

This explicit highlighting of differences provides developers with fast detection of anomalous events, or points where two executions diverge, allowing them to more effectively compare exe- cutions. For example, during a debugging task, this differencing can lead the developer to quickly spot buggy behavior.

The event differencing mechanism compares the host name and event text strings. As future work, we plan to allow the developer to specify which other data fields to include in event com- parison and to highlight order or structural differences between two executions.

4.3.2 Clustering Executions. ShiViz also supports grouping multiple executions into clusters. Developers can cluster by the number of processes or by using the comparison against a base execution described above (Figure 7). Cluster results are presented as distinct groups of listed execution names.