  Modern society is increasingly surrounded by, and 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 and industrial automation (smart factories). Some devices are
small, cheap and specialized sensors and/or actuators. They tend to run simple
software and operate under control of a more sophisticated central control
unit. The latter is responsible for the decision-making and orchestrating the
entire system. If 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 three questions: (1) How
to trust data produced by a simple remote embedded device? and (2) How to
ascertain that this data was produced via execution of expected software?
Furthermore, (3) Is it possible to attain (1) and (2) under the assumption that
all software on the remote device could be modified or compromised?
  In this paper we answer these questions by designing, proving security of,
and formally verifying, VAPE: Verified Architecture for Proofs of Execution. To
the best of our knowledge, this is the first of its kind result for low-end
embedded systems. Our work has a range of applications, especially, to
authenticated sensing and trustworthy actuation, which are increasingly
relevant in the context of safety-critical systems. VAPE architecture is
publicly available and our evaluation demonstrates that it incurs low overhead,
affordable even for lowest-end embedded devices, e.g., those based on MSP430 or
ARV ATMega processors.
