SpecMiner: Heuristic-based mining of service behavioral models from interaction traces

Software behavioral models have proven useful for emulating and testing software systems. Many techniques have been proposed to infer behavioral models of software systems from their interaction traces. The quality of the inferred/mined model is critical to their successful use. While generalization is necessary to deduce concise behavioral models, existing techniques of inferring models, in general, overgeneralize what behavior is valid. Imprecise models include many spurious behaviors, and thus compromise the effectiveness of their use. In this paper, we propose a novel approach, named SpecMiner, that increases the precision of the behavioral model inferred from interaction traces. The essence of our approach is a heuristic-based generalization and truthful minimization. The set of heuristics include patterns to match input traces and generalize them towards concise model representations. Furthermore, we adopt a truthful minimization technique to merge these generalized traces. The key insight of our approach is to infer a concise behavioral model without compromising its precision. We present an empirical evaluation of how our approach improves upon the state-of-the-art specification inference techniques. The results show that our approach mines model with 100% precision and recall with a limited computation overhead.