Tark: Mining Linear Temporal Patterns

Tark is an extensible toolkit to mine temporal patterns that describe various ordering patterns prevalent in (alternatively, that characterize) a set of sequences of events and that are capable of capturing data-flow constraints between participating events.

Tark can be used to mine patterns from sequential data (e.g. execution call traces, network traces, system logs) that contains temporal ordering between its elements and in which the elements/events can be expressed as a conjunction of equality constraints between (unique) names and values (or alternatively as a map from names to value).

The form of patterns mined by Tark form a subclass of linear-temporal logic (LTL).  Tark contains custom algorithms to mine patterns of the following basic forms.

    • A =>* B: Event A must be followed by event B.
    • A !=> B: Event A must be followed by event B with no intervening occurrence of event A.
    • B *<= A: Event A must be preceded by event B.
    • B <=! A: Event A must be preceded by event B with no intervening occurrence of event A.

Patterns of complex forms with higher arity (e.g. A =>* B =>* C) and/or involving disjunction of events (e.g. A =>* (B|C)) are mined by a combining a compositional rule generation procedure and a general pattern checking procedure.

The data-flow constraints between events in a pattern are intrinsically captured in the rule by admitting quantified representation of events, i.e. admitting free variables (along with a map from variables to value) in place of values in equality constraints.

Currently, a .NET-based implementation of the above algorithms/techniques along with various application scenario specific extensions (e.g. a PDML trace parser, ternary rule checking extension) is available.  This implementation is being used internally in various internal experiments, e.g. mining common API usage rules from execution traces.

Publications

Past Members

  • Jithin Thomas: Intern 2011 (BITS Pilani), Research Developer 2012/13, @Stanford University
  • Pradip Vallathol: Intern 2010 (BITS Pilani), Junior Developer 2010/12, @University of Wisconsin
  • Manukranth Kolluju: Intern 2012 (BITS Pilani), @Facebook
  • Piyush Goyal: Intern 2010 (IIT Delhi), @Goldman Sachs
  • David Lo: Intern 2008 (National University of Singapore), @Singapore Management University
  • Ganesan Ramalingam
  • Kapil Vaswani