The Ariadne Debugger: An Overview

Ariadne is a post mortem, event-based debugger [16][13]. It matches user-specified models of intended program behavior against actual program behavior as captured in event traces [2]. The traces record low-level interprocess communication, pre-defined language specific-events, and user-defined events. They are stored internally as execution history graphs with nodes representing events and edges representing orderings imposed by Lamport's happened before relation [17]. Ariadne matches user-models against the execution history graph, extracting matched or partially matched subgraphs for further investigation. The extracted subgraphs can be explored through additional modeling, functional queries, and manipulations of logical, temporal orderings.

Ariadne's modeling language for describing intended behavior is quite simple. It was designed to allow efficient matching and precise feedback on errors. Communication patterns are described in terms of a three-level hierarchy of chains, p-chains, and pt-chains with a notation based on regular expressions.

• Chains are patterns that represent ``local views'' of communication. They are described by extensions of regular expressions. When matched against an execution history graph, all events in the chain must occur exactly in the specified order (with the exception of communication events that are not physically realized because of ``edge effects'' on process array boundaries).

• p-Chains are patterns that represent the concurrent execution of a chain by one or more processes. They are described by binding a chain to a process set. When a p-chain is matched, the chain is matched on each element of the associated process set.

• pt-Chains are patterns that represent the logical, temporal composition of a set of p-chains and they are matched in two steps: first the individual p-chains are matched and then the asserted temporal relations between those events are verified. (Since the temporal relations are not used in the examples in this paper, we do not discuss them further here but refer the reader to existing literature [8].)

When a pt-chain is matched or partially matched, its events are returned as a match tree in which internal nodes represent user-defined abstractions and leaves represent primitive events. The levels of a match tree correspond to the hierarchical levels of its model.

Ariadne's matching language is quite simple and, as a result, it is not always expressive enough; often its patterns are too coarse, matching program behavior in unexpected ways. To compensate, Ariadne provides a scalable, spread-sheet like interface for exploring match trees, called AVE (Ariadne Visualization Engine) [14]. AVE features the automatic compression of hierarchical visualizations, dynamic attribute calculation, and the partitioning of matched behaviors and attributes. Together these features allow a user to answer questions about a match such as: Did the number of events decrease on each iteration of a loop? Which processes were active during the third iteration? Which processes executed successful comparisons? and Why did the match fail on process 12?

Ariadne was designed for explicitly parallel programming languages in which all interprocess communication occurs through read and write operations. In the next section, we discuss the modifications we made so its modeling language would be appropriate for pC++.