Photo credit: The SOHO-EIT Consortium. See bottom of page for more information.

A binary rewriting system transforms a binary program into a different but functionally equivalent program. A link-time optimizer is a binary rewriting system that modifies an object program to improve some aspect of its behavior, such as execution time, code size, or security. A significant benefit of a link-time optimizer is that it can perform whole program optimizations that cannot be done by compilers---e.g., those based on run-time values---or that usually are not done by compilers---e.g., because library source code is not available or is written in a different language.

The SOLAR project is developing techniques for flexible link-time and run-time code optimizations. We are exploring a variety of applications, architectures, and optimization metrics. Applications include traditional sequential programs, parallel scientific programs, operating systems, embedded systems, and distributed systems. Optimization metrics include performance (speed), code size, and security properties. To date we have developed link-time optimizers for three architectures: ALTO for the Compaq Alpha, PLTO for the Intel IA-32 (Pentium), and ILTO for the Intel/HP IA-64 (Itanium). Current work is applying and extending the PLTO optimizer.

People

Faculty: Greg Andrews, Saumya Debray

Collaborators: Gregg Townsend, Rick Schlichting, Matti Hiltunen

Graduate Students: Kevin Coogan, Haifeng He, Somu Periyanayagam, Joe Roback

Undergraduate Students: Drew Davidson, Tasneem Kaochar

Graduate Alumni: Milind Chabbi, Aniket Dubashi, Matt Legendre, Rohit Kundaji, Patrick Moseley, Mohan Rajagopalan, Sharad Santhanam, Sharath Udupa, Scott Watterson

Undergraduate Alumni: S. Chandrasekharan, Jose Gifford, Cullen Linn, Igor Popov, Michael Prestwich, Ben Schwarz, Tal Shaked, Noah Snavely, John Trimble, Jeremy Weiner

Publications

The publications below are organized by the type of optimization and application. See the ALTO page for additional information on the Alpha link-time optimizer. See the Squeeze page for related work on reducing code size.

General Topics

Robert Muth and Saumya Debray. On the Complexity of Flow-Sensitive Dataflow Analyses. Proc. 27th ACM Symposium on Principles of Programming Languages (POPL), Jan. 2000, pp. 67-80.
Abstract | PostScript

Robert Muth, Scott Watterson, and Saumya Debray. Code Specialization Based on Value Profiles. Proc. 7th. International Static Analysis Symposium (SAS 2000), June 2000. Springer LNCS vol. 1824, pp. 340-359.
Abstract | PostScript

Gregory R. Andrews. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 2000.
Web Site

Scott Watterson and Saumya Debray. Goal-Directed Value Profiling. Proc. 2001 Int. Conf. on Compiler Construction (CC 2001), April 2001.
Abstract | PostScript

Benjamin Schwarz, Saumya Debray, and Gregory Andrews. Disassembly of Executable Code Revisited. Proc. 2002 IEEE Working Conference on Reverse Engineering (WCRE 2002), Oct. 2002.
Abstract | PostScript

Patrick Moseley, Saumya Debray, and Greg Andrews. Checking Program Profiles. Proc. Third IEEE Workshop on Source Code Analysis and Manipulation (SCAM 2003), September 2003.
PostScript | PDF

Computer Security

Mila Dalla Preda, Mihai Christodorescu, Somesh Jha, and Saumya Debray. A Semantics-Based Approach to Malware Detection. Proc. 34th. ACM Symposium on Principles of Programming Languages (POPL), January 2007.
PostScript | PDF

Milind Chabbi. Efficient Taint Analysis Using Multicore Machines. Master's Thesis, June 2007.
PostScript | PDF

Code Compaction and Compression

Saumya Debray, William Evans and Robert Muth. Compiler Techniques for Code Compression. ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 22 no. 2, March 2000, pp. 378-415.
Abstract | PostScript | Technical Report(contains raw data from experiments)

Bjorn De Sutter, Bruno De Bus, Koen De Bosschere, and Saumya Debray. Combining Global Code and Data Compaction. Proc. SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), June 2001.
Abstract | PostScript

Saumya Debray and William Evans. Profile-Guided Code Compression. Proc. SIGPLAN '02 Conf. on Prog. Language Design and Implementation (PLDI 02), June 2002.
PostScript

John Trimble. Combining High Level Alias Analysis with Low Level Code Compaction of the Linux Kernel. Honors Thesis, December 2006.
PostScript | PDF

Haifeng He, John Trimble, Somu Perinayagam, Saumya Debray, and Gregory Andrews. Code Compaction of an Operating System Kernel. Proc. Fifth International Symposium on Code Generation and Optimization (CGO), March 2007.
PostScript | PDF

PLTO: Pentium Link-Time Optimizer

Gregory Andrews, Saumya Debray, Benjamin Schwarz, and Matthew Legendre. Using Link-Time Optimization to Improve the Performance of MPI Programs. Preliminary results, April 2001.
Abstract | PostScript

Benjamin Schwarz, Saumya Debray, and Gregory Andrews. PLTO: A Link-Time Optimizer for the Intel IA-32 Architecture. Proc. 2001 Workshop on Binary Translation (WBT-2001), Sept. 2001.
Abstract | PostScript

Benjamin Schwarz. Post Link-Time Optimization on the Intel IA-32 Architecture. Honors Thesis, May 2002.
Abstract | PostScript | PDF

Tal Shaked. Value Profiling in PLTO. Honors Thesis, May 2002.
Abstract | PostScript | PDF

Systems Programs

Mohan Rajagopalan, Saumya Debray, Matti Hiltunen, and Richard Schlichting. Profile-Directed Optimization of Event-Based Programs. Proc. SIGPLAN '02 Conf. on Prog. Language Design and Implementation (PLDI 02), June 2002.
Abstract | PostScript

Mohan Rajagopalan, Saumya Debray, Matti Hiltunen, and Richard Schlichting. System Call Clustering: A Profile-Directed Optimization Technique. Technical Report, May 2002.
PostScript | PDF

Mohan Rajagopalan, Matti Hiltunen, Trevor Jim, and Richard Schlichting. Authenticated System Calls. Proc. IEEE Int. Conf. on Dependable Systems and Networks (DSN 05), June 2005.
PostScript | PDF

Cullen Lin, Mohan Rajagopalan, Scott Baker, Christian Collberg, Saumya Debray, and John Hartman. Protecting Against Unexpected System Calls. Proc. USENIX Security '05, August 2005.
PostScript | PDF

Mohan Rajagopalan, Somu Perinayagam, Haifeng He, Gregory Andrews, and Saumya Debray. Binary Rewriting of an Operating System Kernel. Proc. Workshop on Binary Instrumentation and Applications, October 2006.
PostScript | PDF

Somu Perinayagam, Haifeng He, Mohan Rajagopalan, Gregory Andrews, and Saumya Debray. Profile-Guided Specialization of an Operating System Kernel. Proc. Workshop on Binary Instrumentation and Applications, October 2006.
PostScript | PDF

Intellectual Property Protection

Cullen Linn and Saumya Debray. Obfuscation of Executable Code to Improve Resistance to Static Disassembly. Proc. 10th ACM Conference on Computer and Communications Security (CCS 2003), Oct. 2003.
PostScript | PDF

Cullen Linn, Saumya Debray, and John Kececioglu. Enhancing Software Tamper-Resistance via Stealthy Address Computations. Work In Progress, 19th Annual Computer Security Applications Conference (ACSAC 2003), Dec. 2003.
PostScript | PDF

Christian Collberg, Saumya Debray, Edward Carter, Andrew Huntwork, Cullen Linn, and Mike Stepp. Dynamic Path-Based Software Watermarking. Proc. SIGPLAN '04 Conf. on Prog. Language Design and Implementation (PLDI 04), June 2004.
PostScript | PDF

Matias Madou, Bertrand Anckaert, Patrick Moseley, Saumya Debray, Bjorn De Sutter, Koen De Bosschere. Software Protection through Dynamic Code Mutation. Proc. Int. Workshop on Information Security Applications, Aug. 2005.
PostScript | PDF

Sharath Udupa, Saumya Debray, and Matias Madou. Deobfuscation: Reverse Engineering Obfuscated Code. Proc. 12th IEEE Working Conf. on Reverse Engineering (WCRE 2005), November 2005.
PostScript | PDF

Igor Popov, Samuya Debray, and Gregory Andrews. Binary Obfuscation Using Signals. USENIX Security '07, August 2007.
PostScript | PDF

ILTO: Itanium Link-Time Optimizer

Noah Snavely, Saumya Debray, and Gregory Andrews. Predicate Analysis and If-Conversion in an Itanium Link-Time Optimizer. Proc. 2nd Workshop on EPIC Architectures and Compilers, Istanbul, Turkey, Nov. 2002.
PostScript

Noah Snavely. Optimizing and Reverse Engineering Itanium Executables. Honors Thesis, May 2003.
PostScript | PDF

Noah Snavely, Saumya Debray, and Gregory Andrews. Unspeculation. Proc. 18th IEEE Int. Conf. on Automated Software Engineering (ASE 2003), Oct. 2003.
PostScript | PDF

Noah Snavely, Saumya Debray, and Gregory Andrews. Unpredication, Unscheduling, Unspeculation: Reverse Engineering Itanium Executables. IEEE Trans. on Software Engineering, vol. 31, no. 2, Feb. 2005, pages 99-115.
An earlier version appeared in the 10th IEEE Working Conf. on Reverse Engineering (WCRE 2003), Nov. 2003.
PDF

Acknowledgements

This research has been supported by the National Science Foundation through grants ACR-9720738, CCR-0113633, CNS-0410918, and CNS-0615347. Computing facilities used by the project have been supported by NSF grants CDA-9500991 and EIA-0080123 and by a gift from the HP/Intel Itanium-Based Systems Grant Program.

The image of the sun was taken by the Extreme Ultraviolet Imaging Telescope (EIT) on the Solar and Heliospheric Observatory (SOHO), a spacecraft that was launched on December 2, 1995. SOHO is an ESA-NASA program of international cooperation. The larger 512 x 512 and 1024 x 1024 images are even more spectacular.

[linuxkernelnewbies] The SOLAR Project: Software Optimization,at Link-time And Run-time