Mining Message Sequence Graphs

• Main Authors: KUMAR, Sandeep, KHOO, Siau-Cheng, Roychoudhury, Abhik, LO, David
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1346; http://dx.doi.org/10.1145/1985793.1985807
• Institution: Singapore Management University

Dynamic specification mining involves discovering software behavior from traces for the purpose of program comprehension and bug detection. However, in concurrent/distributed programs, the inherent partial order relationships among events occurring across processes pose a big challenge to specification mining. In this paper, we propose a framework for mining partial orders so as to understand concurrent program behavior. Our miner takes in a set of concurrent program traces, and produces a message sequence graph (MSG) to represent the concurrent program behavior. An MSG represents a graph where the nodes of the graph are partial orders, represented as Message Sequence Charts. Mining an MSG allows us to understand concurrent behaviors since the nodes of the MSG depict important ``phases" or ``interaction snippets" involving several concurrently executing processes. Experiments on mining behaviors of several fairly complex distributed systems show that our miner can produce the corresponding MSGs with both high precision and recall.