A New Model of Program Dependences for Reverse Engineering

Abstract

A dependence model for reverse engineering should treat procedures in a modular fashion and should be fine-grained, distinguishing dependences that are due to different variables. The program dependence graph (PDG) satisfies neither of these criteria. We present a new form of dependence graph that satisfies both, while retaining the advantages of the PDG: it is easy to construct and allows program slicing to be implemented as a simple graph traversal. We define 'chopping', a generalization of slicing that can express most of its variants, and show that, using our dependence graph, it produces more accurate results than algorithms based directly on the PDG.