SpeQTr Language Syntax

This document provides detailed information about the syntax and capabilities of the SpeQTr language.

# Table of Contents

Event Patterns
Specifications
Queries
Advanced Features
Aggregation
- Aggregate Functions

# Event Patterns

Event patterns are the building blocks for the SpeQTr language. Each of the blocks in a specification contains an event pattern. Queries are just event event patterns, with the additional ability to compute aggregates.

This section covers the basics of event patterns. For further functionality covering more complex scenarios see the advanced features.

# Basic Structure

An event pattern describes the events it should match, and how those events are connected.

event@timeline AS a FOLLOWED BY event@timeline AS b FOLLOWED BY event@timeline AS c

Each event is described using the event name and the timeline where it should occur. Event and timeline name are patterns which can include * or ? as wildcards in the style of glob-matching. Additionally, the event and timeline ids may be directly used, in case you don't have the name or the id is more convenient.

The event may be optionally labeled using AS, for use elsewhere. It may also specify additional constraints beyond the event and timeline; see below for details.

Events are joined using relationship connectives, such as -> or FOLLOWED BY (which are synonyms). These may also be further modified, for example to require the two events to occur within a given time window. See below for details.

# Example Pattern

Here's an example event pattern:

12@* AS ev1 FOLLOWED BY my_event@*(_.payload > 12) AS ev2

In this example, 12@* is used to identify all nodes in the causal graph where an event with id 12 was logged. Similarly, my_event@* is used to identify nodes where the logged event has the specified name. It has an additional predicate which restricts it to only events with a payload greater than 12. These matched nodes are associated with their respective labels, ev1 and ev2.

# Event Relationships (Paths)

A pattern can specify multiple events, constraining the matches using structural constraints between them. All relationship constraints are based on these basic causal relationships:

FOLLOWED BY (or ->)
PRECEDED BY (or <-)

These operate on labeled events to constrain the query results to those where the events occur in the given causal order. For example:

event1@timeline FOLLOWED BY event2@timeline

# Time-Limited Relationships

If you have added wall-clock time information to your events using the timestamp attribute, you can use that in a relationship constraint. Constraints can be specified as WITHIN <time> or AFTER <time>, immediately following the causal relationship (i.e. ->). The time-based relationship constraints are:

FOLLOWED BY WITHIN <time> (or -> WITHIN <time>)
FOLLOWED BY AFTER <time> (or -> AFTER <time>)
PRECEDED BY WITHIN <time> (or <- WITHIN <time>)
PRECEDED BY AFTER <time> (or <- AFTER <time>)

Here is a simple example of a time-based relationship constraint:

ev1@timeline FOLLOWED BY WITHIN 1 ms ev2@timeline

The supported time units are:

MINUTES or m
SECONDS or s
MILLISECONDS or ms
MICROSECONDS or us
NANOSECONDS or ns

Note

Time-limited relationships only consider events with the timestamp attribute. In addition, they only work for events which share a common time domain, which is determined by the value of the time_domain timeline attribute. Events on the same timeline always share a common time domain. Time-limited relationships can work across timelines if you have made special accommodations for time synchronization between them (in a way that meets your system requirements) and have appropriately initialized the relevant timelines with the same time domain id.

Alternatively, you can use the --with-lax-causality option to override this limitation and trust all timestamps in specification or query evaluation. Use caution—using this option without synchronizing your system clocks can lead to unstable results due to clock drift.

# Step Limits

You can limit the distance between matches in the causal graph using WITHIN <n> STEPS and AFTER <n> STEPS. These combine with the basic relationship constraint in the same way as time-based constraints. The full list is:

FOLLOWED BY WITHIN <n> STEPS (or -> WITHIN <n> STEPS)
FOLLOWED BY AFTER <n> STEPS (or -> AFTER <n> STEPS)
PRECEDED BY WITHIN <n> STEPS (or <- WITHIN <n> STEPS)
PRECEDED BY AFTER <n> STEPS (or <- AFTER <n> STEPS)

For example, this will match any two causally connected events within three steps of each other:

ev1@timeline FOLLOWED BY WITHIN 3 STEPS ev2@timeline

Note

While step limits are useful for narrowing down a query during debugging, they are inherently somewhat fragile. When you add additional instrumentation you could easily invalidate the structural assumptions made by some query using step limits. As such, you should avoid using step limits for specifications or systems whose instrumentation is likely to change.

# Event Predicates

When matching an event, an additional predicate may be provided to further restrict the matches beyond just the event name/id and timeline.

event@timeline(<predicate>)

An event predicate is an expression that is evaluated against a candidate event in the causal graph to determine if it should be included as a match to the relevant event pattern. It should evaluate to a boolean value; true means the event is included, while false means it is not. In the event predicate, the symbol _ is bound to each candidate event; the various attributes are available using object-style . notation, such as _.payload. Predicates can use any attribute defined on an event or its timeline. Timeline attributes are accessed with the prefix _.timeline., e.g. _.timeline.run_id.

# Operators

Event predicates use typical operators:

Boolean operators: AND, OR, NOT
Comparison: =, !=, <, >, <=, >=
Arithmetic: +, -, *, /, ABS
Existence: exists(_.some_attr) to check the existence of an attribute

The equality operator = supports glob-matching: all strings can be compared with a glob pattern that uses the * and ? characters as wildcards, such as "prefix*suffix". * matches any number of wildcard characters, while ? matches a single wildcard character.

# Specifications

Specifications in Conform use a syntax which naturally lends itself to describing system behavior and requirements. Each specification is made up of one or more behaviors, and each behavior contains one or more cases, as well as a single optional when block.

Here is an example of a complete specification. Each part is explained further below:

behavior "Example behavior"
    when "A message is sent"
        sent_message@worker AS sent
    end

    nominal case "The message is received"
        sent FOLLOWED BY received_message@monitor
    end

    recovery case "Message retry"
        sent FOLLOWED BY retry_message@worker FOLLOWED BY received_message@monitor
    end

    prohibited case "Connection lost"
        connection_lost@monitor
    end
end

Note

The examples below are extremely simple for demonstration purposes. The constituent parts of specifications are event patterns and can be arbitrarily complex, including the advanced features below. For more examples of common specifications see the cookbook.

# `behavior`

Behaviors are the outermost unit of a specification. A specification must have at least one behavior. There is no maximum number of behaviors for a specification. Like all blocks, a behavior must have a name after the opening keyword and is terminated with the keyword end.

# `nominal case`

Each behavior can have any number of nominal case blocks inside it. As the name suggests, a nominal case is used to describe the expected behavior of the system when everything runs smoothly. If any nominal case is matched (and no prohibited cases match), the behavior passes.

The content inside a nominal case block is simply an event pattern. This event pattern has access to variables assigned with AS from other blocks. Like all blocks, a nominal case must have a name after the opening keyword and is terminated with the keyword end.

behavior "Nominal behavior"
    nominal case "Observe success"
        success@controller
    end
end

# `recovery case`

Each behavior can have any number of recovery case blocks inside it. A recovery case is used to describe the expected behavior of the system for successful remediation of some condition. Since it represents correct handling of an adverse situation, if any recovery case is matched (and no prohibited cases match), the behavior passes.

The content inside a recovery case block is simply an event pattern. This event pattern has access to variables assigned with AS from other blocks. Like all blocks, a recovery case must have a name after the opening keyword and is terminated with the keyword end.

behavior "Recovery behavior"
    recovery case "Handle error"
        error_corrected@controller
    end
end

The ability to access variables assigned from other blocks is particularly useful in recovery cases. For nominal cases which contain a sequence of events, it allows you to essentially describe "escape hatch" behavior at various points of the sequence. Note that, since the variable name refers to the specific matched instance of the event where the name is assigned, whatever preconditions were specified for the variable still apply when it is used later.

behavior "Escape hatch recovery cases"
    when "Sequence begins"
        begin@controller AS Begin
    end

    nominal case "Sequence proceeds normally"
        Begin FOLLOWED BY
        second@controller AS Second FOLLOWED BY
        third@subsystem AS Third FOLLOWED BY
        fourth@controller AS Fourth
    end

    recovery case "Begin escape hatch"
        Begin FOLLOWED BY begin_remediation@controller
    end

    recovery case "Second event escape hatch"
        Second FOLLOWED BY second_remediation@controller
    end

    recovery case "Third event escape hatch"
        Third FOLLOWED BY remediation@subsystem FOLLOWED BY fourth@controller
    end
end

# `prohibited case`

Each behavior can have any number of prohibited case blocks inside it. A prohibited case is used to describe system behavior that should never happen. If any prohibited case is matched, even if a nominal case or recovery case is also matched, the behavior fails.

The content inside a prohibited case block is simply an event pattern. This event pattern has access to variables assigned with AS from other blocks. Like all blocks, a prohibited case must have a name after the opening keyword and is terminated with the keyword end.

behavior "Failure behavior"
    prohibited case "Failure"
        failure@controller
    end
end

# `when`

Each behavior can optionally have a single when block. The when block changes the semantics of a behavior so that its cases are evaluated each time the pattern in the when block occurs. If a behavior does not have a when block, it only needs to find a match to a single nominal or recovery case in the entire set of data under consideration to pass. Thus, having a when block in a behavior is like changing it from checking whether a matching case exists anywhere to checking for a matching case for each occurrence of the when pattern.

A when block can contain any event pattern, and the named events from that pattern (using as) will be available in all blocks. If a behavior has a when block, then all the cases must connect back to it in some way. If you don't mention the such an event by name, Conform will try will using a simple followed by relationship if the event patterns are simple. For complex event patterns, you will need to specify the connections explicitly.

Like all blocks, a when must have a name after the opening keyword and is terminated with the keyword end.

behavior "When behavior"
    when "Landing command is sent"
        initiate_landing@commander AS init_land
    end

    nominal case "Landing succeeds"
        init_land FOLLOWED BY landing@flight_control FOLLOWED BY landing_succeeded@commander
    end

    recovery case "Emergency landing"
        init_land FOLLOWED BY emergency_landing@flight_control FOLLOWED BY landing_succeeded@commander
    end
end

'when' blocks and bounded relationships

When writing behaviors using when blocks, it can be easy to specify following events using a relationship that is too general, accepting events that you may not think of as directly 'following' the trigger. For example, in the above behavior, the "Landing succeeds" case will still match even if the landing@flight_control event happens a day later. You should think carefully about the extent of these relationships. They can be easily bound using within, if you have timestamps available, or using until (see below) if you can deliniate a border using an event pattern.

# `until`

The until block is used in conjunction with when to provide a pattern-based mechanism for more directly specifying the extent of a trigger region. This is best understood through the lens of a motivating example.

# `until` Example

Suppose you are specifying the behavior of a robot arm. Its basic job is to listen to commands from the rest of the system and execute those commands as best as it is able. It should respond to those commands very quickly, inside the context of one iteration of its listen-for-commands loop. If the reaction happens later, after another command is received, that's too late.

We can specify this using when and until:

behavior "Simple robot arm control loop"
    when "Command is received"
        recv_command@robot_arm as cmd
    end

    until "Next command is received"
        recv_command@robot_arm
    end

    nominal case "Actuation commands are processed"
        cmd.kind = "actuate" and actuate@robot_arm
    end

    nominal case "E-stop commands are processed"
        cmd.kind = "Emergency Stop" and emergency_stop@robot_arm
    end
end

Here, we use until to specify that the behaviors must match /before/ the next command is received. This is a very common pattern for control-loop-based systems.

# `until` semantics

Like when, until can contain any event pattern. It must be connected back to when, just like the case blocks; for simple patterns, this is done with an automatic followed by relationship. More complex event patterns require a manual connection by using a label bound in when from the until block.

If you are using an until block, it is required to occur; if the event pattern from when is found the corresponding until pattern does not match, then the behavior will not be evaluated; the when match is skipped.

We can intuitvely think of the until block as specifying the end-of-the-line, beyond which behaviors may not match. More precisely: the events matched by 'until', plus the earliest event on every timeline which causally follows those events, form the end of the line. When evaluating the case patterns, the search will never go beyond this line.

# Comments

You can use the # character to write single line comments.

# Metadata

Specifications can optionally include doxygen-like key-value metadata to help you organize and manage them. The key space is free-form. You can put metadata at the very top of a specification document to apply to the entire specification. You can also put metadata on individual behaviors or cases.

# @author = "phil"
# @project = "documentation"

# @type = "example"
behavior "Example behavior"
    when "A message is sent"
        sent_message@worker AS sent
    end

    # @requirement_id = 3
    nominal case "The message is received"
        sent FOLLOWED BY received_message@monitor
    end

    # @requirement_id = 7
    # @category = "remediation"
    recovery case "Message retry"
        sent FOLLOWED BY retry_message@worker FOLLOWED BY received_message@monitor
    end

    # @requirement_id = 9
    # @category = "failure"
    prohibited case "Connection lost"
        connection_lost@monitor
    end
end

# Evaluating Specifications

Evaluating specifications generates a pass or fail result, either for the entire set of data under consideration or for each region delimited by the when block. For a specification to pass the region under consideration must contain at least one match to either a nominal case or a recovery case, and there must be no matches to any prohibited case. If there are no matches to a case of any kind, the specification fails, since this represents unspecified behavior.

# Queries

For the most part, queries are nothing more than event patterns describing the events of interest. Patterns can be given directly to the modality query (opens new window) command, which will find events which match the pattern. For example:

*@timeline1 AS a FOLLOWED BY *@timeline2 AS b AND a.payload = b.payload

This query will find all instances of an event on timeline1 followed by an event on timeline2 with the same payload. The advanced features discussed below supplement the basic event patterns section above.

When writing a query, you also have access to the aggregation facilities using the AGGREGATE keyword:

*@* AS a
AGGREGATE std_dev(a.payload) AS payload_stddev

See the aggregation section for details.

# Advanced Features

The discussion of event patterns above covers the most commonly used features. This section covers further considerations in building event patterns.

# Negative Lookahead

A negative relationship with nothing else after it behaves like a lookahead operator. For example, suppose you want to identify errors which are not followed by a remediation event inside a suitable time window:

*@*(_.tag='error') NOT FOLLOWED BY WITHIN 5 ms *@*(_.tag='remediation')

The negative relationship operators are:

NOT FOLLOWED BY (or !->)
NOT PRECEDED BY (or <-!)

Note that the event matched by the right-hand side of the relationship may not be labeled; there's actually nothing there to find, since this is specifying what should not be present.

# Negative Path Constraints

You can similarly specify a negative constraint to be applied on the path between two events. For example, you might want to look for pairs of startup and shutdown events that don't have an error signaled on the path between them:

startup@p AS a NOT FOLLOWED BY *@*(_.tag='error') FOLLOWED BY shutdown@p AS b

The syntax is similar to negative lookahead, but the subsequent FOLLOWED BY means that it will apply to any nodes found between the events a and b. There don't have to be any events there: this query will match even if a is directly followed by b, with nothing in between.

# CROSSING ANY

By default, each relationship matches only the nearest events in either direction. More precisely, it will not match a pair of events if any of the events on the path between them could have been a match. This is the most intuitive behavior most of the time; we refer to it as local reasoning.

There may be times when you want to indicate all possible pairs of matching events regardless of the events on the path between them. This is done using CROSSING ANY.

For example, if you want to match ALL the possible bs for every a , you could write:

a@timeline AS a FOLLOWED BY CROSSING ANY b@timeline AS b

# Adding Multi-Event Predicates

Additional predicate expressions may be added to an event pattern to further constrain matches, especially based on some predicate involving multiple matched events. These expressions use the label assigned to the event using AS, instead of the _ character.

This gives the filter expression access to multiple events at the same time. For example, you might want to find causal pairs of events with the same payload as each other:

*@* AS a FOLLOWED BY *@* AS b
AND a.payload = b.payload

# External Predicates With Local Reasoning

When using AND to add additional predicates to an event pattern, you should be aware of the local reasoning that is used for all relationships by default (see the crossing any section). You can use this with external predicates to express some unique queries.

This is best explained by example. Suppose you wanted to find ground_contact events where the most recent accelerometer reading is above a certain threshold:

ground_contact@control AS a <- acceleration@control AS b
AND b.payload > 12.0

This will first match pairs of ground_contact and acceleration events as described, and then limit those matches to only the pairs where the acceleration event has the correct payload.

If the payload constraint was inside the event predicate for acceleration this would have an entirely different meaning:

ground_contact@control AS a <- acceleration@control(_.payload > 12.0) AS b

This would match the most recent acceleration event with the desired payload, with respect to the ground contact event, but there could be other more recent acceleration events (with payload <= 12) on the path between them.

# CONCURRENT Paths

Events and relationships alone are sufficient to match trace-like patterns, which consist of a single path through the causal graph. But many systems have behaviors which cannot be described this simply.

A very common kind of complex system behavior is parallel execution with synchronization points. Events logged by such systems can be matched using CONCURRENT WITH event patterns.

This is best described by example:

start@common FOLLOWED BY (a1@a FOLLOWED BY a2@a CONCURRENT WITH b1@b FOLLOWED BY b2@b) FOLLOWED BY end@common

In this example, the two event patterns a1@a FOLLOWED BY a2@a and b1@b FOLLOWED BY b2@b are causally independent of each other. But they must both be causally preceded by a single event which matches start@common, and followed by a single event which matches end@common.

If you want to add additional restrictions to the edges going into or out of the CONCURRENT WITH block, you can do so by adding labels and using AND:

start@common as common_start FOLLOWED BY (a1@a as a_start FOLLOWED BY a2@a CONCURRENT WITH b1@b FOLLOWED BY b2@b) FOLLOWED BY end@common
AND common_start FOLLOWED BY WITHIN 10 ms a_start

# Combining Paths

If you want to match complex patterns which do not fit the CONCURRENT WITH model, you can do so by describing them as multiple paths which AND with each other, using common labels to indicate intersection points. For example:

source_1@p1 FOLLOWED BY meet@center AS meet
AND source_2@p2 FOLLOWED BY meet

Note that the meet label is used in both paths: this means that the two matches are unified. meet has to be the same event in both paths; graphically it's a "V" pattern. Modality will search for ways to choose three events such that ALL the given relationships are satisfied.

Note

One common misinterpretation of this is to view them as 'shortcuts' to match multiple events using the same condition. This is not correct. Each time you reuse an event label you're applying a new constraint to the same event. So each time you talk about event a, it's always the same a within a single match for the event pattern.

# Aggregation

The SpeQTr language has aggregation functionality to allow you to calculate aggregate functions over matched event patterns.

Aggregation works very similarly to aggregation in other query languages. You can specify aggregations over previous results, do some computations with them, and give them names.

For example:

*@* AS a
AGGREGATE std_dev(a.payload) AS payload_stddev

This will compute the standard deviation of the payload value for all events, naming it payload_stddev in the aggregation result. Any events that do not have a payload will be skipped when computing the aggregation.

The parameter to each aggregate function is an expression with access to all matched events.

*@* AS a FOLLOWED BY *@* AS b
AGGREGATE std_dev(a.payload - b.payload) AS payload_diff_stddev

You can also do computations with the results of multiple aggregations:

*@* AS a FOLLOWED BY *@* AS b
AGGREGATE (min(a.payload) - min(b.payload)) / 2 AS min_payload_avg

# Aggregate Functions

count(): Count the number of results. Unlike the other aggregates, this one doesn't have an expression argument.
min(...), max(...): Compute the minimum or maximum value of the expression.
sum(...), mean(...): Compute the sum or mean of the expression.
distinct(...): Return the set of distinct values taken on by the expression.
count_distinct(...): Return the number of distinct values taken on by the expression.
variance(...), std_dev(...): Calculate the variance or standard deviation of the expression.

# Aggregation in Specs

You can use aggregation functions inside of spec cases. The result of the aggregate must be used in a formula so that the whole thing evalutes to true or false.

behavior "Agg in a case"
    nominal case "It happened at least ten times"
      some_event@tl AGGREGATE count() >= 10
    end
end

← Overview Cookbook →

SpeQTr Language Syntax

# Table of Contents

# Event Patterns

# Basic Structure

# Example Pattern

# Event Relationships (Paths)

# Time-Limited Relationships

# Step Limits

# Event Predicates

# Operators

# Specifications

# behavior

# nominal case

# recovery case

# prohibited case

# when

# until

# until Example

# until semantics

# Comments

# Metadata

# Evaluating Specifications

# Queries

# Advanced Features

# Negative Lookahead

# Negative Path Constraints

# CROSSING ANY

# Adding Multi-Event Predicates

# External Predicates With Local Reasoning

# CONCURRENT Paths

# Combining Paths

# Aggregation

# Aggregate Functions

# Aggregation in Specs

# `behavior`

# `nominal case`

# `recovery case`

# `prohibited case`

# `when`

# `until`

# `until` Example

# `until` semantics