Average Case vs. Worst Case-Margins of Safety in System Design

We predict that we will soon witness attacks on all kinds of systems that will be based on the attacked systems’ worstcase 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.