Modern society is increasingly surrounded by, and is growing accustomed to, a wide range of Cyber-Physical Systems (CPS), Internet-of-Things (IoT), and smart devices. They often perform safety-critical functions, e.g., personal medical devices, automotive CPS as well as industrial and residential automation (such as sensor-alarm combinations). On the lower end of the scale, these devices are small, cheap, and specialized sensors and/or actuators. They tend to host small CPUs, have small amounts of memory, and run simple software. If such devices are left unprotected, consequences of forged sensor readings or ignored actuation commands can be catastrophic, particularly, in safety-critical settings. This prompts the following questions: (1) How to trust data produced, or guarantee that actions will be performed, by a simple remote embedded device?, (2) How to bind actions and results to the execution of expected software? and, (3) Can (1) and (2) be attained even if all software on a device can be modified and/or compromised (e.g., by malware) at any given time?

This dissertation presents a set of hardware/software co-designs for obtaining several security services – namely remote attestation, TOCTOU-avoidance, proofs of execution, and root of trust availability – which can be used to assure the integrity and availability of software and its execution, even on some of the most resource-constrained micro-controllers. We realize these services with four formally verified and publicly available architectures (VRASED, RATA, APEX, and TAROT) and show how they have been securely implemented atop the TI MSP430 micro-controller at a relatively low cost.