Mining for Patterns in Program Dependence Graphs

Abstract

Program graphs display programs from different perspectives. Some patterns repeat themselves in program graphs. By looking at these frequent patterns, one can make informed inferences about the underlying characteristics of programs. Searching for frequent patterns can be a challenging task due to the complexity and size of these graphs. An effort has been underway to apply data mining techniques to unsupervised discovery of these frequent patterns in graphs and then analyzing the output to deduce rules that can provide useful information about programs. This thesis work concerned the discovery of patterns in program dependence graphs. Program dependence graphs of different versions of open source Java programs were extracted and mined for patterns. Analysis of the discovered patterns pointed out the existence of relationships between the discovered patterns and the changes made in the program code. It was found that the patterns can be grouped into at least six different classes based on the code changes they represent. These patterns can prove to be useful in program maintenance.