Elastic Program Transformations

Performance and reliability are important yet conflicting properties of systems software. Software today often crashes, has security vulnerabilities and data loss, while many techniques that could address such issues remain unused due to performance concerns. This thesis presents elastic program transformations, a set of techniques to manage the trade-off between reliability and performance in an optimal way given the software's use case. Our work is based on the following insights: - Program transformations can be used to tailor many software properties: they can make software easier to verify, safer against security attacks, and faster to test. Developers can write software once and use transformations to subsequently specialize it for different use cases and environments. - Many classes of transformations are elastic: they can be applied selectively to parts of the software, and both their cost and effect scale accordingly. - The trade-off is governed by the Pareto Principle: the right choice of program transformations yields 80% of the benefit for 20% of the cost. This thesis makes four contributions that use these insights: 1. We developed Overify, a strategy and technique for choosing compiler optimizations to make programs easier to verify, rather than faster to run. Overify demonstrates that program transformations have the power to reduce verification time by up to 95x. 2. We show that known program transformations to detect memory errors and undefined behavior can be elastic. We developed ASAP, a technique and tool to apply these transformations selectively to make a program as secure as possible, while staying within a maximum overhead budget specified by the developer. For a maximum overhead of 5%, ASAP can protect 87% of the critical locations in CPU-intensive programs. 3. We improve the performance of fuzz testing tools that rely on program transformations to observe the software under test. We present FUSS, a technique and tool for focusing these transformations where they are needed, improving the time to find bugs by up to 3.2x. 4. We show that elasticity is a useful design principle for program transformations. In the BinKungfu project, we develop a novel elastic transformation to enforce control-flow integrity. Exploiting elasticity reduces the number of programs that violate performance constraints by 59%. The essence of our work is identifying elasticity as a first-class property of program transformations. This thesis explains how elasticity manifests and how Overify, ASAP, FUSS and BinKungfu exploit it automatically. We implemented each technique in a prototype, released it as open-source software, and evaluated it to show that it obtains more favorable trade-offs between reliability and performance than what was previously possible.