A fundamental problem in security is to guarantee correct program behavior on an un-trusted computer regardless of a user?s actions. The problem appears in Digital Rights Management, Secure Boot, e-appliances, etc. All existing approaches are either partial or undependable. Today, dependable security is necessary not only for e-commerce, but also to ensure that, under critical conditions of information warfare, remote clients behave predictably and securely, and cannot compromise the infrastructure.

We prove that the problem of correct program execution is unsolvable without adoption of a trusted hardware platform. Since it is impractical to consider as trusted a complex computer system, we identify the minimal hardwaresupport that enables a complete solution. We propose two simple hardware mechanisms, which require minimal change to the currently popular PC architecture: (i) the use of a trusted "sealed" computing device, the "spy", and (ii) a hardware interrupt, called "two minute warning", which has the highest priority and has a pre-defined time difference from any subsequent interrupt. Finally, we incrementally build upon this minimal hardware support larger and more complex applications with guaranteed security. We call this construction the inverse security pyramid.