Our society increasingly depends on computing devices. Customers rely on laptops and mobile devices to access security sensitive applications such as online banking. Companies have to protect their trade secrets. And governments have to guard their country's critical infrastructure against espionage and sabotage. Security of computing devices in such use cases is paramount and various security measures have been developed that raise the bar significantly for attackers. However, vulnerabilities in such systems still exist and are frequently exploited successfully. A common pitfall is that software security takes a layered approach where privileged layers keep getting extended with new components over the system's lifetime. This results in a snowball effect on the size of these privileged levels and this in turn increases the likelihood of software vulnerabilities. As all applications running on the device rely on the integrity of these layers, increasing the size of their code base has a negative impact on security of the overall device.Many security measures have been proposed to automatically harden the most privileged software layer, but they all fail to provide strong security guarantees. In this thesis, we considered a different approach. We developed three security primitives that can be applied at most privilege levels. Unlike related approaches, this set of primitives is fixed. Software components can be added easily at any privilege level, but no additional primitives will be required. Moreover, these security primitives can provide provable security guarantees.The most important security primitive is a program-counter-based access control mechanism. By enforcing different access rights on physical memory depending in which code module the processor is executing, sensitive parts of an application can be strongly isolated. For instance, a cryptographic key can be isolated to a protected module implementing a certificate-signing service.Since the key cannot be accessed by any other code than the module's, it cannot be stolen even if malware was already present on the platform. The access control mechanism also guarantees that the module is only accessible through the interface that it exposes explicitly.Second, we enable protected modules to limit which protected modules can access their services. Unrestricted access to modules may still allow a large range of attacks. While an attacker may no longer be able to access a well-isolated cryptographic key, for example, the exposed interface may still allow her to sign forged certificates. We prevent such attacks using a capability-based access control mechanism; a module can only be accessed if the caller ever received the capability to do so.Third, we propose a fast and practical state-continuity system. Using cryptographic properties, protected modules can use many services of the<br> unprotected, legacy system while providing strong security guarantees. Unfortunately, these security guarantees only are ensured while the system is up and running. In practice systems crash, loose power or need to reboot. Integrity and confidentiality protecting the module's state before it is stored on disk is insufficient in such cases. Care must be taken that an attacker cannot present a stale state of a protected module as being fresh. Practical implementations are hindered by the substantial economical costs to add non-volatile storage to the processor. Many computing devices are already shipped with access-controlled non-volatile storage off-chip, but this memory is slow, very limited in size and wears out quickly. We propose an algorithm based on a simple hardware component to avoid all these shortcomings.During this dissertation we also focused on how these newly-added security primitives can be applied to provide strong security guarantees. A fully-abstract compilation scheme was developed that ensures that software-level abstractions provided to programmers cannot be broken; for every low-level attack, there also exists an attack at source-code level. This significantly simplifies reasoning about the security guarantees that protected modules provide and increases security of the overall system.