Program plan matching: experiments with a constraint-based approach

The plan matching problem is to determine whether a program plan is present in a program. This problem has been shown to be NP-hard, which makes it an open question whether plan matching algorithms can be developed that scale sufficiently well to be useful in practice. This paper discusses experiments in the scalability of a series of constraint-based program plan matching algorithms we have developed. These empirical studies have led to significant improvements in the scalability of our plan matching algorithm, and they suggest that this algorithm can be successfully applied to large, real-world programs.