Reverse Engineering of Legacy Code is Intractable

Reverse engineering of large legacy software systems is widely recognized to be a difficult problem. How bad is it? By an argument that identifies key underlying sources of the difficulty, reverse engineering of legacy code is shown to be intractable in the usual computational complexity sense. This conclusion implies that we should not be too enthusiastic about the ultimate value of reverse engineering as the centerpiece of a cost-effective approach to constructing new generations of systems. Copyright 1994 by the authors. All rights reserved. THIS PAGE INTENTIONALLY BLANK 1 1. Introduction Many large software systems, even if apparently well-engineered on a componentby -component basis, have proved to be incoherent as a whole due to unanticipated long-range "weird interactions" among supposedly independent parts. The best anecdotal evidence for this conclusion comes from experience dealing with "legacy" code, i.e., programs 1 in which too much has been invested just to throw ...