Learning invariants using association rules technique

摘要

Dynamic invariant detection is the identification of properties of programs by analyzing execution traces. Traditional dynamic invariant detectors, such as Daikon, use naive techniques based on verification of predefined invariant forms. Unfortunately, this may discard many useful knowledge such as relationship between variables. This kind of knowledge can be helpful to understand hidden dependencies in the program. In this paper, we propose to model invariant detection as a machine learning process. We intend to use learning algorithms to find out correlation between variables. We are particularly interested by association rules since they are suitable to detect such relationship. We propose an adaptation to existing learning techniques as well as some pruning algorithms in order to refine the obtained invariants. Compared to the traditional Daikon tool, our approach has successfully inferred many meaningful invariants about variables relationship.