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.
@article{Beschastnikh15tse,
author = {Ivan Beschastnikh and Yuriy Brun and Jenny Abrahamson and Michael
D. Ernst and Arvind Krishnamurthy},
title =
{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\ref{Beschastnikh13icse}.
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 = {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.},
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},
}