Using declarative specification to improve the understanding, extensibility, and comparison of model-inference algorithms
by Ivan Beschastnikh, Yuriy Brun, Jenny Abrahamson, Michael D. Ernst, Arvind Krishnamurthy
Abstract:

It is a staple development practice to log system behavior. Numerous powerful model-inference algorithms have been proposed to aid developers in log analysis and system understanding. Unfortunately, existing algorithms are typically declared procedurally, making them difficult to understand, extend, and compare. This paper presents InvariMint, an approach to specify model-inference algorithms declaratively.

We applied the InvariMint declarative approach to two model-inference algorithms. The evaluation results illustrate that InvariMint (1) leads to new fundamental insights and better understanding of existing algorithms, (2) simplifies creation of new algorithms, including hybrids that combine or extend existing algorithms, and (3) makes it easy to compare and contrast previously published algorithms.

InvariMint's declarative approach can outperform procedural implementations. For example, on a log of 50,000 events, InvariMint's declarative implementation of the kTails algorithm completes in 12 seconds, while a procedural implementation completes in 18 minutes. We also found that InvariMint's declarative version of the Synoptic algorithm can be over 170 times faster than the procedural implementation.

Citation:
Ivan Beschastnikh, Yuriy Brun, Jenny Abrahamson, Michael D. Ernst, and Arvind Krishnamurthy, Using declarative specification to improve the understanding, extensibility, and comparison of model-inference algorithms, IEEE Transactions on Software Engineering (TSE), vol. 41, no. 4, April 2015, pp. 408–428.
Related:
Extended and revised version of "Unifying FSM-inference algorithms through declarative specification" in ICSE 2013.
Bibtex:
@article{Beschastnikh15tse,
  author = {Ivan Beschastnikh and Yuriy Brun and Jenny Abrahamson and Michael
  D. Ernst and Arvind Krishnamurthy},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Beschastnikh15tse.pdf}{Using 
	declarative specification to improve the understanding, extensibility, and 
	comparison of model-inference algorithms}},
  journal = {IEEE Transactions on Software Engineering (TSE)},
  venue = {TSE},
  year = {2015},
  volume = {41},
  number = {4},
  month = {April},
  pages = {408--428},
  issn = {0098-5589},
  note = {Extended and revised version of~\cite{}{Beschastnikh13icse}.
  \href{http://dx.doi.org/10.1109/TSE.2014.2369047}{DOI:
  10.1109/TSE.2014.2369047}},
  doi = {10.1109/TSE.2014.2369047},
	
  previous = {Extended and revised version of "Unifying FSM-inference
  algorithms through declarative specification" in ICSE 2013.},

  abstract = {<p>It is a staple development practice to log system behavior.
  Numerous powerful model-inference algorithms have been proposed to aid
  developers in log analysis and system understanding. Unfortunately,
  existing algorithms are typically declared procedurally, making them
  difficult to understand, extend, and compare. This paper presents
  InvariMint, an approach to specify model-inference algorithms declaratively.</p>

  <p>We applied the InvariMint declarative approach to two model-inference
  algorithms. The evaluation results illustrate that InvariMint (1) leads to
  new fundamental insights and better understanding of existing algorithms,
  (2) simplifies creation of new algorithms, including hybrids that combine
  or extend existing algorithms, and (3) makes it easy to compare and
  contrast previously published algorithms.</p>

  <p>InvariMint's declarative approach can outperform procedural
  implementations. For example, on a log of 50,000 events, InvariMint's
  declarative implementation of the kTails algorithm completes in 12 seconds,
  while a procedural implementation completes in 18 minutes. We also found
  that InvariMint's declarative version of the Synoptic algorithm can be over
  170 times faster than the procedural implementation.</p>},

  fundedBy = {NSERC, Google Inc. via the Faculty Research Award, 
	Microsoft Research via a SEIF award, DARPA FA8750-12-2-0107, 
  NSF CNS-0963754, NSF CCF-1016701},
}