The basis for all network communication is the Address Resolution Protocol, which maps IP addresses to a device's MAC identifier. ARP resolutionn has long been vulnerable to spoofing and other attacks, and past proposals to secure the protocol have focused on key owner- ship rather than the identity of the machine itself. This paper introduces arpsec, a secure ARP protocol that is based on host attestations of their integrity state. In combination with bottom-up host measurement, we define a formal ARP binding logic that bases additions of new ARP responses into a host's ARP cache on a set of operational rules and properties, implemented as a Prolog engine within the arpsec daemon. Our proof of concept implementation is designed within the Linux 3.2 kernel environment and we show that using commodity TPMs as our attestation base, arpsec incurs an overhead ranging from 7% to 15.4% over the standard Linux ARP implementation. This formally-defined protocol based on bottom-up trust provides a first step towards a formally secure and trustworthy networking stack.