  Interconnected embedded devices are increasingly used invarious scenarios,
including industrial control, building automation, or emergency communication.
As these systems commonly process sensitive information or perform safety
critical tasks, they become appealing targets for cyber attacks. A promising
technique to remotely verify the safe and secure operation of networked
embedded devices is remote attestation. However, existing attestation protocols
only protect against software attacks or show very limited scalability. In this
paper, we present the first scalable attestation protocol for interconnected
embedded devices that is resilient to physical attacks. Based on the assumption
that physical attacks require an adversary to capture and disable devices for
some time, our protocol identifies devices with compromised hardware and
software. Compared to existing solutions, our protocol reduces ommunication
complexity and runtimes by orders of magnitude, precisely identifies
compromised devices, supports highly dynamic and partitioned network
topologies, and is robust against failures. We show the security of our
protocol and evaluate it in static as well as dynamic network topologies. Our
results demonstrate that our protocol is highly efficient in well-connected
networks and robust to network disruptions.
