New Experiments With A Constraint-Based Approach To Program Plan Matching

In earlier work, we presented some preliminary empirical scalability results for a constraint-based program plan matching algorithm. Those initial experiments had several important shortcomings: they worked with a collection of artifically generated programs, and they applied a particular constraint satisfaction approach. This paper reports the results of a collection of new experiments that begin to address these deficiencies. In particular, we have begun experimenting with real-world C code, and we have begun exploring alternative approaches to solving constraint satisfaction problems. While not definitive, these new experiments provide further support for our earlier results, and they have led to a new approach that provides significant improvements in the scalability of our plan matching algorithm. 1 Introduction A key part of any program understanding algorithm is the task of plan matching: locating all instances of a hypothesized program plan (such as a schema augmented with dat..