BIND: A Fine-grained Attestation Service forSecure Distributed Systems∗Elaine ShiCarnegie Mellon [email protected] PerrigCarnegie Mellon [email protected] Van DoornIBM T.J. Watson Research [email protected] this paper, we propose BIND (Binding InstructionsaNd Data),1a fine-grained attestation service for secur-ing distributed systems. Code attestation has recently re-ceived considerable attention in trusted computing. How-ever, current code attestation technology is relatively im-mature. First, due to the great variability in software ver-sions and configurations, verification of the hash is difficult.Second, the time-of-use and time-of-attestation discrepancyremains to be addressed, since the code may be correct atthe time of the attestation, but it may be compromised bythe time of use. The goal of BIND is to address these is-sues and make code attestation more usable in securing dis-tributed systems. BIND offers the following properties: 1)BIND performs fine-grained attestation. Instead of attest-ing to the entire memory content, BIND attests only to thepiece of code we are concerned about. This greatly simpli-fies verification. 2) BIND narrows the gap between time-of-attestation and time-of-use. BIND measures a piece of codeimmediately before it is executed and uses a sand-boxingmechanism to protect the execution of the attested code. 3)BIND ties the code attestation with the data that the cod eproduces, such that we can pinpoint what code has beenrun to generate that data. In addition, by incorporating theverification of input data integrity into the attestation, BINDoffers transitive integrity verification, i.e., through one sig-nature, we can vouch for the entire chain of processes thathave performed transformations over a piece of data. BINDoffers a general solution toward establishing a trusted envi-ronment for distributed system d esigners.∗This research was supported in part by CyLab at Carnegie Mellon un-der grant DAAD19-02-1-0389 from the Army Research Office, and grantCAREER CNS-0347807 from NSF, and by gifts from IBM and Cisco. Thevie ws and conclusions contained here are those of the authors and shouldnot be interpreted as necessarily representing the official policies or en-dorsements, either express or implied, of ARO, Carnegie Mellon Univer -sity, IBM, Cisco, NSF, or the U.S. Government or any of its agencies.1The term BIND is also used in Domain Name Service (DNS) termi-nology to stand for the Berkeley Internet Name Daemon. Here we use it ina different context.1 IntroductionSecuring distributed systems continues to be an impor-tant research challenge. One hard problem in securing adistributed system arises from the fact that a remote soft-ware platform may be compromised and running maliciouscode. In particular, a compromised platform may exhibit ar-bitrarily malicious behavior. Such attacks are referred to asByzantine attacks [12] in the literature. The task of remotecode attestation then is to identify what software is runningon a remote platform and to detect a corrupted participant.The Trusted Computing Group (TCG, formerly knownas TCPA) [40] and the Next Generation Secure Comput-ing Base (NGSCB, formerly known as Palladium) [30] pro-pose to use a secure coprocessor (Trusted Platform Mod-ule) to bootstrap trust during system initialization. Theseapproaches compute a hash value of a loaded program be-fore execution starts, the hash value can later be used by aremote party to identify the system’s loaded code and con-figuration. Meanwhile, operating system architectures havebeen built to incorporate this approach [35, 36].Prev iously proposed TCG-style attestation mechanismshave a coarse granularity, they verify the entire opera tingsystem and loaded applications. However, operating sys-tems often contain numerous modules that depend on theinstalled hardware, as well as different versions of the samesoftware, or the same version compiled with different com-piler settings, or patched with different patches. Even tinydifferences in the execution code result in a different hashvalue. Thus, such coarse-grained attestation makes remoteverification very d ifficult. The Terra Virtual Mach ine Mon-itor [16] alleviates this problem by decompo sing attestableentities into fixed-sized bloc ks, and computing a separatehash over each block. Apart from being coarse-grained,TCG-style attestation only provides load-time guarantees,as the attestation in TCG only reflects the memory stateright after the program is loaded. However, it may well bethat the software gets compromised at run time (e.g., bufferoverflows, format string vulnerabilities), which load-timeattestation cannot possibly detect.In another line of work, researchers have proposed Copi-lot [32], a run-time memory attestation mechanism. Here,extra hardware periodically computes a hash of the mem-ory to detect deviations from the expected contents, whichwould indicate malicious code. However, Copilot checksmemory periodically, which may miss a short-lived intru-sion. Meanwhile, Copilot also verifies memor y at a coarsegranularity much the same way as TCG-style attestation.In this paper, our motivation is two-fold. First, we seekto answer the question: how can code attestation aid us indesigning a distributed system? Second, we make an effortat addressing the above mentioned issues regarding currentcode attestation technology. We present the following con-tributions: (1) We propose fine-grained attestation,wherewe attest only to the critical piece of code involved in pro-ducing a certain output, instead of computing the checksumacross the entire software system. We achieve this throughan attestation annotation mechanism. We allow the pro-grammer to identify and annotate the beginning and the endof this critical piece of code; and every time this piece ofcode is executed, our attestation service will be invoked. (2)We narrow the gap between time-of-attestation and time-of-use. We attest to the critical piece of code immediately be-fore it is executed, and we use a sand-boxing mechanismto protect the execution of the critical code. So even thoughthe rest of the software system may be compromised, it can-not tamper with the execution of the critical code. (3) Wepropose to tightly bind code integrity with data integrity.InBIND (Binding Instructions aNd Data), an integrity prooffor a piece of code is cryptographically attached to the datait has produced. This allows