Structured intermediate representation modification in the LLVM compiler infrastructure

In this thesis we propose a new approach for modifying programs expressed in an intermediate representation (IR) that leverages the many-to-one relationship between source languages and IR and also supports modifying code emitted from binary-to-IR decompilers. The open source LLVM Compiler Infrastructure offers a semantically well-defined IR and supports a variety of popular source languages and target instruction set architectures (ISAs).;LLVM currently supports program modification by translating source code into LLVM IR and performing a fixed set of transformations on the IR. This functionality is part of the LLVM optimizer and improves a program's execution performance while preserving its visible behavior.;We improve LLVM's techniques for systematic program modification by introducing structured methods for behavior alteration. The targets for modification are programs written in LLVM IR. First, this work presents a call graph transformation algebra which allows for call graph manipulation while preserving structural validity of a target graph. Second, this thesis explores the implementation of a structured IR editor based on this transformation algebra that allows users to modify a target program in terms of its call graph. Finally, we demonstrate the usefulness of our IR editor through an example in which we retrofit security features into the OpenSSH codebase.