Using Concept Lattices to Uncover Causal Dependencies in Software

Suppose that whenever event x occurs, a second event y must subsequently occur. We say that x “causes” y, or y is causally dependent on x. Deterministic causality abounds in software where execution of one routine can necessarily force execution of a subsequent sub-routine. Discovery of such causal dependencies can be an important step to understanding the structure of undocumented, legacy code. In this paper we describe a methodology based on formal concept analysis that uncovers possible causal dependencies in execution trace streams. We first walk through the process using a small synthetic, but easily comprehensible, example. Then we illustrate its potential using 57 threads involving 18,969 executed operations that were monitored in an open source middleware system.