Average case vs. worst case: margins of safety in system design

ABSTRACT

We predict that we will soon witness attacks on all kinds of systems that will be based on the attacked systems' worst-case behavior. For example, the worst-case performance of Java Bytecode Verification rises quadratically with program length. By sending a legal, but difficult-to-verify program to a server virtual machine, we can keep that server occupied for an inordinate amount of time, effectively making it unavailable for useful work. The problem, however, is not restricted to mobile-code verification: for example, an attacker could exploit knowledge about a just-in-time compiler's register allocator by sending it a particularly difficult to solve graph-coloring puzzle. The same vulnerability can be exploited if the attacker has intimate knowledge of the data structures used in the attacked system. Similar problems occur in hardware, e.g. with respect to power variability or the heat dissipation of processors. Malicious programs can exploit which parts of computer chips dissipate power, thereby overheating regions of the chip that are known to contain no temperature sensors. This attack could be used to affect battery life or cause early chip aging. Unfortunately, worst case-based attacks are hard to counter without also limiting the system's behavior in the average case.

REFERENCES

• 1: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 2: A. W. Appel , K. J. Supowit, Generalization of the Sethi-Ullman algorithm for register allocation, Software—Practice & Experience, v.17 n.6, p.417-421, June 1987 [doi>10.1002/spe.4380170607]
• 3: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 4: CERT Coordination Center, Carnegie Mellon University, http://www.cert.org.
• 5: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 6: G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, Martin, E. Hopkins, and P. W. Markstein. Register allocation via graph coloring. Computer Languages, 6(1):47--57, 1981.
• 7: R. M. Cohen. The defensive Java Virtual Machine specification version 0.5. Technical report, Computational Logic, Inc., May 1997.
• 8: S. A. Crosby and D. S. Wallach. Denial of Service via Algorithmic Complexity Attacks. In Proceedings of the 2003 USENIX Symposium on Virtual Machines. USENIX Association, 2003.
• 9: P. Dadvar and K. Skadron. Potential Thermal Security Risks. In 21st IEEE SEMI-THERM Symposium. IEEE, 2005.
• 10: D. Dean and A. Stubblefield. Using Client Puzzles to Protect TLS. In Proceedings of the 2001 USENIX Security Symposium. USENIX Association, 2001.
• 11: A. Gal, C. W. Probst, and M. Franz. An Applet performing a complexty-based Denial-of-Service attack on the verifier. Available at http://nil.ics.uci.edu/exploit.
• 12: A. Gal, C. W. Probst, and M. Franz. A Denial of Service Attack on the Java Bytecode Verifier. Technical Report 03--23, University of California, Irvine, School of Information and Computer Science, 2003.
• 13: A. Gal, C. W. Probst, and M. Franz. Proofing: An Efficient and Safe Alternative to Mobile-Code Verification. Technical Report 03--24, University of California, Irvine, School of Information and Computer Science, November 2003.
• 14: A. Gal, C. W. Probst, and M. Franz. Integrated Java Bytecode Verification. In Proceedings of the First International Workshop on Abstract Interpretation of Object Oriented Languages, January 2005.
• 15: S. Garfinkel. Script for a king. HotWired Packet, http://hotwired.lycos.com/packet/garfinkel/96/45/geek.html and see http://simson.vineyard.net/table.html for the table attack., November 1996.
• 16: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 17: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 18: Russ Joseph , David Brooks , Margaret Martonosi, Control Techniques to Eliminate Voltage Emergencies in High Performance Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.79, February 08-12, 2003
• 19: Sylvain Lelait , Guang R. Gao , Christine Eisenbeis, A New Fast Algorithm for Optimal Register Allocation in Modulo Scheduled Loops, Proceedings of the 7th International Conference on Compiler Construction, p.204-218, March 28-April 04, 1998
• 20: Xavier Leroy, Java Bytecode Verification: Algorithms and Formalizations, Journal of Automated Reasoning, v.30 n.3-4, p.235-269, 2003 [doi>10.1023/A:1025055424017]
• 21: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 22: V. Paxson. Bro: A System for Detecting Network Intruders in Real Time. Proceedings of the 7th Security Symposium. (USENIX Association: Berkeley, CA), 1998.
• 23: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 24: Redhat. Vulnerability in zlib library, Advisory ID: RHSA-2002:026-35, 2002.
• 25: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 26: Sun Microsystems. The Java Hotspot Virtual Machine, 2002.
• 27: Sun Microsystems. CDC: An Application Framework for Personal Mobile Devices, http://java.sun.com/products/cdc/, 2003.
• 28: F. Yellin. Low level security in Java. In O'Reilly and Associates and Web Consortium (W3C), editors, World Wide Web Journal: The Fourth International WWW Conference Proceedings, pages 369--380. O'Reilly & Associates, Inc., 1995.