Inferring Models of Concurrent Systems from Logs of their Behavior with CSight
by Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, Arvind Krishnamurthy
Abstract:

Concurrent systems are notoriously difficult to debug and understand. A common way of gaining insight into system behavior is to inspect execution logs and documentation. Unfortunately, manual inspection of logs is an arduous process, and documentation is often incomplete and out of sync with the implementation.

To provide developers with more insight into \networked systems, we developed CSight. CSight mines logs of a system's executions to infer a concise and accurate model of that system's behavior, in the form of a communicating finite state machine (CFSM).

Engineers can use the inferred CFSM model to understand complex behavior, detect anomalies, debug, and increase confidence in the correctness of their implementations. CSight's only requirement is that the logged events have vector timestamps. We provide a tool that automatically adds vector timestamps to system logs. Our tool prototypes are available at http://synoptic.googlecode.com/.

This paper presents algorithms for inferring CFSM models from traces of concurrent systems, proves them correct, provides an implementation, and evaluates the implementation in two ways: by running it on logs from three different networked systems and via a user study that focused on bug finding. Our evaluation finds that CSight infers accurate models that can help developers find bugs.

Citation:
Ivan Beschastnikh, Yuriy Brun, Michael D. Ernst, and Arvind Krishnamurthy, Inferring Models of Concurrent Systems from Logs of their Behavior with CSight, in Proceedings of the 36th International Conference on Software Engineering (ICSE), 2014, pp. 468–479.
Related:
Previous versions appeared as University of British Columbia technical report 2429/46122 and as University of Washington technical report UW-CSE-12-10-01.
Bibtex:
@inproceedings{Beschastnikh14icse,
  author = {Ivan Beschastnikh and Yuriy Brun and Michael D. Ernst and
  Arvind Krishnamurthy},
  title =
  {\href{http://people.cs.umass.edu/brun/pubs/pubs/Beschastnikh14icse.pdf}{Inferring
  Models of Concurrent Systems from Logs of their Behavior with
  CSight}},
  booktitle = {Proceedings of the 36th International Conference on Software
  Engineering (ICSE)},
  venue = {ICSE},
  address = {Hyderabad, India},
  month = {June},
  date = {4--6},
  year = {2014},
  pages = {468--479},
  accept = {$\frac{99}{495} = 20\%$},

  note = {Previous versions appeared as University of British Columbia
  technical report 2429/46122 and as University of Washington
  technical report UW-CSE-12-10-01.
  \href{http://dx.doi.org/10.1145/2568225.2568246}{DOI:
  10.1145/2568225.2568246}},
  previous = {Previous versions appeared as University of British
  Columbia technical report 2429/46122 and as University of Washington
  technical report UW-CSE-12-10-01.},
  doi = {10.1145/2568225.2568246},  

  abstract = {<p>Concurrent systems are notoriously difficult to debug
  and understand. A common way of gaining insight into system behavior
  is to inspect execution logs and documentation. Unfortunately,
  manual inspection of logs is an arduous process, and documentation
  is often incomplete and out of sync with the implementation.</p>

  <p>To provide developers with more insight into \networked systems, we
  developed CSight. CSight mines logs of a system's executions to
  infer a concise and accurate model of that system's behavior, in the
  form of a communicating finite state machine (CFSM).</p>

  <p>Engineers can use the inferred CFSM model to understand complex
  behavior, detect anomalies, debug, and increase confidence in the
  correctness of their implementations. CSight's only requirement is
  that the logged events have vector timestamps. We provide a tool
  that automatically adds vector timestamps to system logs. Our tool
  prototypes are available at http://synoptic.googlecode.com/.</p>

  <p>This paper presents algorithms for inferring CFSM models from traces
  of concurrent systems, proves them correct, provides an
  implementation, and evaluates the implementation in two ways: by
  running it on logs from three different networked systems and via a
  user study that focused on bug finding. Our evaluation finds that
  CSight infers accurate models that can help developers find bugs.</p>},

  fundedBy = {AFOSR FA8750-12-C-0174, IARPA N66001-13-1-2006},
}