Reverse Engineering Foreign Type Systems

Abstract. Building systems from existing applications and data sources is common practice. Semi-structured data sources (such as XML, HTML, and databases) and programming languages (such as C # and Java) conform to welldefined, albeit different, type systems, each with their own unique underlying representations. As a consequence, reverse engineering of programs that access, manipulate and update data in foreign type systems (FTSs), i.e., type systems that are different from the host programming language, is a notoriously difficult task. We present a practical and effective process to reverse engineer FTS-based systems. We offer a programming model that is based on the uniform abstraction of FTSs as graphs and the use of path expressions 1 for traversing and manipulating data. This model enables us to achieve multiple benefits, including coding simplicity and uniformity (where neither was present before) that facilitate further reverse engineering. By performing control and data flow analyses of FTS-based programs we infer the schemas used by all participating FTSs and the actions performed by each FTS on others. Finally, we describe a tool called FORTRESS that we implement to automate our reverse engineering process. The contribution of this paper is a process that allows programmers to reverse engineer automatically foreign type systems and their instances at the highest level of design. We know of no other approach with comparable benefits.