Object-Based Dynamic Protocol Recovery for Multi-Threading Programs

A protocol defines the sequencing constraints for the operations that can be applied to an object. Quante introduced a protocol recovery technique that is able to extract protocols from existing software by means of dynamic analysis. This approach represents the behavior as object process graphs (OPG). OPGs are a projection of the control flow graph reduced to the operations relevant to an individual object. The protocol is inferred from a set of OPGs. The extraction was designed to handle sequential programs only. As multi-core architectures and, hence, multi-threading becomes more and more common in nowadays programming, it is necessary to extend reverse engineering techniques for multi-threaded programs. In this paper, we extend Quante´s approach to protocol reconstruction for programs with multiple threads. We are formalizing this process using concepts from automata theory, namely, product and shuffle automata. We present a naive approach to combine these concepts and a combined approach. Our evaluation for realistic Java programs demonstrates the scalability of the combined approach and the combinatorial explosion of the naive approach.