Dynamic specification mining extracts candidate specifications from logs of execution traces. Existing algorithms differ in the kinds of traces they take as input and in the kinds of candidate specification they present as output. One challenge common to all approaches relates to the faithfulness of the mining results: how can we be confident that the extracted specifications faithfully characterize the program we investigate? Since producing and analyzing traces is costly, how would we know we have seen enough traces? And, how would we know we have not wasted resources and seen too many of them?In this paper we address these important questions by presenting a novel, black box, probabilistic framework based on a notion of log completeness, and by applying it to three different well-known specification mining algorithms from the literature: k-Tails, Synoptic, and mining of scenario-based triggers and effects. Extensive evaluation over 24 models taken from 9 different sources shows the soundness, generalizability, and usefulness of the framework and its contribution to the state-of-the-art in dynamic specification mining.

k-Tails is a popular algorithm for extracting a candidate behavioral model from a log of execution traces. The usefulness of k-Tails depends on the quality of its input log, which may include too few traces to build a representative model, or too many traces, whose analysis is a waste of resources. Given a set of traces, how can one be confident that it includes enough, but not too many, traces? While many have used the k-Tails algorithm, no previous work has yet investigated this question.