  The design of tiny trust anchors has received significant attention over the
past decade, to secure low-end MCU-s that cannot afford expensive security
mechanisms. In particular, hardware/software (hybrid) co-designs offer low
hardware cost, while retaining similar security guarantees as (more expensive)
hardware-based techniques. Hybrid trust anchors support security services, such
as remote attestation, proofs of software update/erasure/reset, proofs of
remote software execution, in resource-constrained MCU-s, e.g., MSP430 and AVR
AtMega32. Despite these advances, detection of control-flow attacks in low-end
MCU-s remains a challenge, since hardware requirements of the cheapest related
architectures are often more expensive than the MCU-s themselves. In this work,
we tackle this challenge by designing Tiny-CFA - a control-flow attestation
(CFA) technique with a single hardware requirement - the ability to generate
proofs of remote software execution (PoX). In turn, PoX can be implemented very
efficiently and securely in low-end MCU-s. Consequently, our design achieves
the lowest hardware overhead of any CFA architecture (i.e., two orders of
magnitude cheaper), while relying on a formally verified PoX architecture as
its sole hardware requirement. With respect to runtime overhead, Tiny-CFA also
achieves better performance than prior CFA techniques based on code
instrumentation. We implement and evaluate Tiny-CFA, analyze its security, and
demonstrate its practicality using real-world publicly available applications.
