USENIX Association

Proceedings of the Third Virtual Machine

Research and Technology Symposium
San Jose, CA, USA
May 6–7, 2004

© 2004 by The USENIX Association All Rights Reserved For more information about the USENIX Association:
Phone: 1 510 528 8649 FAX: 1 510 548 5738 Email: [email protected] WWW: http://www.usenix.org
Rights to individual papers remain with the author or the author's employer.
Permission is granted for noncommercial reproduction of the work for educational or research purposes.
This copyright notice must be included in the reproduced paper. USENIX acknowledges all trademarks herein.
 Semantic Remote Attestation —
A Virtual Machine directed approach to Trusted Computing

Vivek Haldar, Deepak Chandra and Michael Franz

Department of Computer Science
University of California
Irvine, CA 92697-3425
{vhaldar,dchandra,franz}@uci.edu

Abstract Both of these have significantly increased the im-

portance of having a so-called “common platform”.
This common platform is increasingly the language
Remote attestation is one of the core functionali- runtime, that executes some form of platform-
ties provided by trusted computing platforms. It independent mobile code.
holds the promise of enabling a variety of novel ap-
plications. However, current techniques for remote As we become dependent on this computing infras-
attestation are static, inexpressive and fundamen- tructure, its weaknesses also become painfully ap-
tally incompatible with today’s heterogeneous dis- parent. On the one hand, we have periodic waves
tributed computing environments and commodity of network outages caused by worms such as Nimda
open systems. Using language-based virtual ma- and SQL Slammer. On the other, content produc-
chines enables the remote attestation of complex, ers want control over the proliferation of their cre-
dynamic, and high-level program properties — in ations. The network is a hostile place — the default
a platform-independent way. We call this seman- assumption is to assume an adversarial remote ma-
tic remote attestation. This enables a number of chine.
novel applications that distribute trust dynamically.
We have implemented a prototype framework for se- One way to get security assurances is to use closed
mantic remote attestation, and present two example systems. They enforce compliance with a certain
applications built on it — a peer-to-peer network security policy by being tightly controlled. They
protocol, and a distributed computing application. are usually manufactured by a single vendor to rigid
specifications. Designers have complete control over
the whole system and build it specifically to con-
form to a given security policy. When one closed
1 Introduction system communicates with another, it knows within
very tight bounds the expected behavior of the re-
mote party. Common examples of closed systems
Two major trends have been immensely influen- are automated teller machines (ATMs) and propri-
tial in today’s computing environment. The first is etary game consoles
heterogeneity. We compute using everything from
small cellphones, to handhelds, to desktop worksta- Open systems, on the other hand, have no central
tions, to rack-mounted servers — and these must arbiter. Commodity personal computers and hand-
all inter-operate. This has led to the widespread ac- helds are examples of open systems. An open sys-
ceptance of open protocols for communication and tem can be easily changed to behave maliciously
portable language runtimes (such as the Java and towards other systems that communicate with it.
.NET virtual machines) for execution of programs. Two communicating open systems cannot assume
anything about each others’ behavior, and must be
The second major trend is mobility. Not only must conservative in their assumptions.
all these varied computing devices inter-operate
seamlessly, we must also be able to use most of Trusted computing is an effort to bring some of the
our familiar programs and data across all of them. properties of closed, proprietary systems to open,
commodity systems. Trusted computing introduces idea behind semantic remote attestation is to use a
mechanisms and components in both hardware and trusted virtual machine (TrustedVM) to explicitly
software that check and enforce the integrity of a derive or enforce, on behalf of a remote party, vari-
system, and allow it to authenticate itself to remote ous properties of applications running within it.
systems. For example, a trusted booting procedure
makes sure that the operating system has not been Intuitively, “authentication” of an entity should
tampered with. Using a chain of reasoning that have a broader meaning than it does currently. It
starts from a trusted hardware module, we can ar- should encompass not just verifying the source from
rive at a conclusion about the state of a system af- which it originated, but also include verifying or
ter boot-up. Similarly, we can deduce for sure what proving that its behavior conforms to a required se-
particular program is running on a system. Remote curity policy.
attestation is the process by which software authen-
ticates itself to remote parties. This allows the re- To gain experience with semantic remote attesta-
mote party to make certain assumptions about the tion, we have implemented a prototype TrustedVM,
behavior of the software. and two example applications on it. The first
application is a simplified peer-to-peer networking
Before trusted computing can reach its full poten- protocol, and the second is a distributed comput-
tial, questions such as the following need to be ad- ing client-server application. Implementing these
dressed: within our framework achieved two benefits:

• how do programs running on trusted platforms • trust relationships between peers, or between
authenticate each other in a manner that en- clients and servers, were made explicit, and
sures that each party satisfies some security cri- then checked or enforced by the TrustedVM.
teria, while leaving room for various differing Typically, they are implicit and taken on trust.
implementations? • making the trust relationships explicit results
• the current client-server network computing in having some knowledge of degree of trust-
model assumes a trusted server, and untrusted worthiness of clients and peers. (for example,
(even malicious) clients. Thus, even though knowing which properties were satisfied, and
a significant fraction of work is done at the which were not). This allows the applications
clients, all the trust resides at the server. How to make informed decisions about the “good-
can we design new network protocols (or adapt ness” of a result, and dynamically adjust its
existing ones) to work in an environment that trust relationships.
allows a more flexible partitioning of trust?
The rest of the paper is organized as follows: Section
• Moving away from the model of having a fully
2 briefly covers basic concepts in trusted computing
trusted server, and a fully untrusted client, how
and remote attestation, and explains the shortcom-
do we design models and applications that use
ings of remote attestation as it is today; Section 3
them, that can broker trust in more flexible and
explains how virtual machines can be used for flexi-
dynamic ways than is possible today?
ble, expressive remote attestation — this forms the
core of the paper; Section 4 discusses the implemen-
As we explain in this paper, current methods of tation issues involved in this and presents two ex-
remote attestation suffer from many critical draw- ample applications; Section 5 surveys related work;
backs. It is a technique well-suited to rigidly con- Section 6 discusses avenues for future work; and Sec-
trolled closed systems, but completely inadequate tion 7 concludes.
for the open systems of today, which embody a great
variety of hardware and software platforms.

We propose a way out of the problems of standard 2 Background: Trusted Computing

remote attestation by using a trusted virtual ma- and Remote Attestation
chine as a basis for doing remote attestation. We
call this semantic remote attestation, since it can
certify high-level, fine-grained, and dynamic proper- The broad goal of trusted computing is to add com-
ties of platform-independent mobile code. The core ponents and mechanisms to open, commodity sys-
tems to bestow on them some of the properties of ately succeeding it. Thus, the BIOS must be un-
high-assurance closed systems. This is done using a able to read the TM’s private key, the boot-loader
combination of hardware and software support. It must be unable to read the BIOS’s private key and
requires three core mechanisms: so on. At the successful completion of this chain
of checks, the system is guaranteed to have booted
into a trusted, untampered operating system.
• Secure boot: to make sure that the system
is booted into a trusted operating system that Thus, a combination of hardware (the trusted mod-
adheres to some given security policy. If such a ule) and software (used for secure booting and iso-
mechanism is not provided, an adversary could lation) is needed to guarantee both integrity and
boot the system into a modified operating sys- authenticity of a trusted system. The trusted com-
tem that bypasses the security policy. puting base of this setup consists of the hardware
• Strong isolation: to prevent the system from trusted module, and a trusted operating system that
being compromised after it has been booted, handles booting, and enforces strict isolation be-
and to prevent applications from tampering tween applications.
with each other.
• Remote attestation: to certify the authen- 2.1 Remote Attestation — and its prob-
ticity of software being run by a remote party. lems

The first two guarantee integrity — that the system

Remote attestation is the process by which an appli-
was not tampered with since it was last turned off
cation authenticates itself to a remote party. When
(secure boot), and that execution of programs will
asked to authenticate itself, an application asks the
not be tampered with (strong isolation). The third
operating system for an endorsement. The oper-
has to do with authenticity — to be sure of the
ating system signs a hash of the executable of the
identity of a remote party or program. The focus of
application. The entire certificate chain, starting
this paper is remote attestation.
from the trusted module all the way up to the ap-
plication, is sent to the remote party. The remote
At the root of the attestation process is a hardware
party verifies each certificate of this chain, and also
device called a trusted module (TM). This has em-
checks that the corresponding hashes are of software
bedded in it the private key of a public-private key-
it approves.
pair. This key-pair is certified by a certification au-
thority (CA). The TM also has a small amount of
The attestation process must result in the client and
non-volatile storage. A hash of the BIOS is signed
server sharing a secret, or else the session can be
using the TM’s private key and stored here. At
easily hijacked (e.g. by doing the attestation us-
boot-up, control is first passed to the TM. It re-
ing one program, and further communication using
computes the hash of the BIOS, and compares it
another).
with its stored hash. If they are the same, then we
know that the BIOS has not been tampered with,
This method of remote attestation suffers from sev-
and control is passed to the BIOS. The BIOS does
eral critical drawbacks. Briefly, they are:
a similar check before passing control to the boot-
loader. And the boot-loader does a similar check
before passing control to the operating system. All • It says nothing about program behavior
layers along this chain have their own public-private
key-pair, which is certified (signed using the private • It is static, inflexible and inexpressive
key) by the layer immediately preceding it in the • Upgrades and patches to programs are hard to
chain. This in turn is used to certify the layer im- deal with
mediately above it. Precisely, each layer signs two
things of the layer above it: a hash of its executable • It is fundamentally incompatible with a widely
image, and its public key. This binds the public key varying, heterogeneous computing environment
to the software. • Revocation is a problem
Note that the private key of every layer along this
chain must be kept secret from the layer immedi- We discuss each of these in more detail below.
The most critical shortcoming of remote attestation lutions such as Java are so popular. Remote attes-
is that it is not based on program behavior. Even tation, however, with its stress on certifying par-
though what is fundamentally sought is some as- ticular platform-specific binaries, is fundamentally
surance of program behavior (with respect to some incompatible with this reality. Just as with man-
security policy), remote attestation certifies some- aging upgraded and patched versions of software,
thing completely different. It simply certifies what certifying programs that run on a variety of plat-
exact executable is running. Any assurances about forms and that must inter-operate with each other,
the behavior of the program are taken on trust. It quickly becomes intractable.
is possible for an attested program to have bugs, or
otherwise behave maliciously. Remote attestation inherits a problem from public-
key cryptography — revocation. Once a certifica-
Remote attestation defined in this way is completely tion authority issues a certificate, it is very hard to
static and inflexible. It can convey no dynamic in- revoke. One method is to have publicly available
formation about the program, such as its runtime certificate revocation lists (CRLs) which are looked
state, or the properties of the input it is acting upon. up at regular intervals. Thus, there may be some
It is a one-time operation done at the beginning of time lapse between a certificate being revoked, and
a network protocol. access being denied to it. Checking with some re-
vocation infrastructure (such as a CRL) at every
Another problem is that upgrades and patches are attestation would be very inefficient.
hard to deal with. Linear upgrades from one version
to the next can be dealt with by simply updating
the list of “approved” software that a remote party
uses. In closed and tightly controlled systems such
as ATMs, this is tractable. 3 Semantic Remote Attestation

The situation with widely available commodity soft-

ware is completely different. As is increasingly com- The shortcomings of traditional ways of remote at-
mon today, upgrades and patches are released very testation can be traced back to one root cause —
frequently. Also, software is patched more often what is desired is attestation of the behavior of soft-
than it is upgraded. There are usually multiple ware running on a remote machine, but what actu-
patches for multiple bugs and insecurities for a given ally gets attested is the fact that a particular binary
program. Any subset of these patches may be ap- is being run.
plied in any order. This results in an exponential
blowup in the space of possible binaries for a pro- Whether a remote party is running, say, Outlook
gram. 5.1, is not per se the information that is sought.
What is sought is whether that particular program
In such a scenario, remote attestation faces prob- abides by some security policy. However, all that
lems at both ends of the network. Servers have to traditional remote attestation is able to certify is
manage the growing intractability of maintaining a simply what exact binary code is running on a re-
very large list of “approved software”, which is likely mote platform. From this, an indirect implication
to always be behind the current state. Clients, on is drawn about the program’s behavior. It is very
the other hand, may have to hold off on applying important to realize that such an assurance gained
patches or on upgrading, simply to be able to work about a program’s behavior is based purely on trust,
within a remote attestation framework. not on verification. Given the knowledge of what
exact program is running on a remote platform, we
Today’s computing ecosystem is extremely varied trust it to behave according to a given policy be-
and accommodates a spectrum of heterogeneous cause, essentially, the vendor of the software claims
systems with widely varying capabilities. These so. The chain of cryptographic certificates binds
systems range from high-end supercomputers, to this claim to the vendor, and the program.
consumer devices such personal computers, hand-
helds, cellphones and watches, and even ubiqui- This is a direct consequence of using purely crypto-
tously embedded microprocessors. Thus, a high pre- graphic methods for remote attestation. Cryptogra-
mium is placed on portability and interoperability. phy is good at certifying entities — it is not suitable
This is one reason why cross-platform portable so- for certifying behavior.
The solution we propose leverages the techniques chine is the Java Virtual Machine. It is important
of language-based security and virtual machines. to differentiate this from virtual machine monitors
Language-based security [21, 25] has been vari- (VMM) that virtualize a hardware architecture, and
ously defined as “a set of techniques based on pro- present an interface exactly like, or very similar to,
gramming language theory and implementation, in- raw hardware. Examples of VMMs are VMWare,
cluding semantics, types, optimization and verifica- and Disco [9].
tion, brought to bear on the security question” and
“leveraging program analysis and program rewriting Requests for remote attestation are now made to
to enforce security policies”. It derives assurances the TrustedVM. These requests ask for the enforce-
about the behavior of the code by looking at the ment or checking of specific security policies on code
code itself. that is being run by the TrustedVM. Thus, what is
enforced is not the execution of a particular binary,
Recent and very promising examples of this but security policies and other constraints specified
approach include proof-carrying code[24], typed by a remote party.
assembly language (TAL), inlined execution
monitors[14], and information flow type systems[23]. There are two key observations that enable our
These techniques can be thought of as falling into TrustedVM approach:
two major categories — program rewriting and
program analysis. Program analysis covers a
variety of techniques that statically try to check a • Firstly, code expressed in a portable representa-
program’s conformance to a security policy. The tion (e.g. Java bytecode) contains high-level in-
primary example of this is type-safe programming formation about the code — such as its class hi-
and types-based approaches to security such as erarchy, method signatures, typing information
TAL. Program rewriting is a complementary set etc. The presence of this high-level informa-
of techniques which aim to enforce security by tion, as well as the fact that code is expressed
rewriting programs to conform to a security policy. in a platform independent format, makes such
Inlining security monitors is an example of this code very amenable to program analysis. A
class of techniques. The primary advantage of the trusted virtual machine can attest to high-level
language-based approach to security is that it is meta-information about a program, as well as
flexible and can easily express fine-grained security the results of some code analysis done on a pro-
policies. gram.
• Secondly, code runs completely under the con-
trol of a virtual machine, and so its execution
3.1 Using a Trusted Virtual Machine can be explicitly monitored. Thus, a trusted
for Attestation virtual machine can attest to dynamic proper-
ties regarding the execution of a program, or
its inputs.
We propose making remote attestation more flexible
and expressive by leveraging language-based tech-
niques and virtual machines. The goal is to at- Some examples of properties that a trusted virtual
test program behavior, not a particular binary. Our machine can attest are:
domain is platform-independent mobile code that
runs on a virtual machine. Instead of a trusted op- • TrustedVM attests properties of classes:
erating system, we use a trusted virtual machine, the remote party may require class A to sub-
or TrustedVM, to attest to remote parties various class a well-known class B, or some interface
properties of code running within it. Software up C. This may be because extending B or C con-
to, and including, the virtual machine, still has to straints the behavior of A in some way. For
be trusted, and attested using the standard “signed- example, C may be a restricted interface for
hash” method. input-output operations, that disallows arbi-
trary network connections.
In this paper, we use the term virtual machine (VM)
to mean a language-based virtual machine that exe- • Attesting dynamic properties: the pro-
cutes some form of platform-independent code. The gram being attested runs under complete con-
most widespread example of such a virtual ma- trol of a TrustedVM. Thus, a TrustedVM can
 attest to dynamic properties. This includes the traditional remote attestation — semantic at-
runtime state of the program and properties of testation reasons about the behavior of the
the input of the program. code, without tying that reasoning to a par-
ticular executable binary.
• Attesting arbitrary properties: A Trust-
edVM has the ability to run arbitrary analysis
• It is dynamic in nature — it can attest to var-
code(within the limits set by the security policy
ious dynamic properties of a program, such as
of the local host) on the program being attested
its runtime state at interesting program points,
on behalf of the remote party. Thus the remote
or input to the program. As opposed to tradi-
party can test for a wide variety of properties
tional remote attestation, it is not one-time.
by sending across code that does the appropri-
ate analysis.
• It is flexible — a TrustedVM can carry out ar-
• Attesting system properties: a remote bitrary code analyses and attest its results.
party can send across code that tests certain
relevant system and virtual machine properties,
and the TrustedVM can attest its results. For Semantic remote attestation done in virtual ma-
example, before running a distributed comput- chines with platform-independent code enables
ing program (such as SETI@Home, or Fold- truly new functionality that was not possible be-
ing@Home), the server may want to test the fore, because this sort of high-level attestation of
floating point behavior of the system and vir- program properties cannot be done using native
tual machine by having the TrustedVM run a code. Firstly, native code is too low-level, and does
test suite of floating point programs. not have enough high-level structure and informa-
tion to drive the sort of analysis our TrustedVM
does. Secondly, some of the functionality of a Trust-
Note that this sort of attestation is a much more
edVM (such as a server sending code to analyze or
fine-grained and semantically richer operation than
monitor the program being run) requires platform-
signing the hash of an executable image — we call
independent code.
this semantic remote attestation. What is now at-
tested is not the presence of a particular binary exe-
Semantic attestation can allow for the possibility
cutable, but relevant properties of a program. This
that some of the properties required of a program
has the effect of explicitly separating two concerns
may not be satisfied. In that case, the remote party
that were earlier merged into one — identity and be-
can lower its expectations of how trustworthy the
havior. Claims about code behavior are now made
behavior of the program is likely to be, and proceed
by the trusted virtual machine explicitly checking
accordingly, rather than terminate the whole proto-
or deriving them.
col altogether. Thus, properties that make an appli-
cation trustworthy can now be thought of as falling
A direct consequence of this is that now a variety of
within a range, rather than one all-or-nothing attes-
different implementations of some functionality will
tation. This has an important consequence for back-
be able to function within our remote attestation
ward compatibility. Most common network proto-
framework — as long as they satisfy the proper-
cols today (TCP, HTTP) assume a completely un-
ties required of them. Cryptography now plays the
trusted client. Using a flexible approach to attesta-
part of binding this claim about code behavior to
tion allows these untrusted protocols to be gradually
an entity which is qualified to make such claims —
endowed with trusted capabilities, and the ability to
a trusted virtual machine.
deal with clients of varying trustworthiness.

3.2 Advantages of Semantic Remote Semantic remote attestation also allows attestation
Attestation without locking the client into a particular plat-
form, or binary. By far the most scathing critiques
of trusted computing have focused on the idea of
Semantic remote attestation has a number of ad- remote attestation being used to lock consumers
vantages over traditional remote attestation: into a particular platform, thus extending monopoly
control[6]. Semantic remote attestation, however,
explicitly separates identity from behavior, and al-
• It overcomes the most critical shortcoming of lows flexible attestation of code properties, while
 signed hashes.

The trusted base of a virtual machine also includes

its standard libraries. Even if the virtual machine
itself is trustworthy, an adversary could modify the
standard system libraries for malicious ends — for
example, by substituting the standard security man-
ager class with a weaker one. Thus, the operat-
ing system certifies both the virtual machine binary,
and the libraries it uses.

At the time of this writing, we did not have access

to trusted hardware. Thus, the certificate chains we
emit are not rooted in a trusted hardware module,
but in the operating system. We do not foresee any
conceptual difficulties in interfacing to real trusted
Figure 1: Top-level architecture for dynamic check- hardware, since it is a matter of extending the cer-
ing in a TrustedVM tificate chain.

allowing inter-operation of a variety of implementa- We now explain the implementation of two applica-
tions that satisfy these properties. tions that we implemented on our prototype Trust-
edVM.

4 Implementation and Results 4.1 A peer-to-peer protocol

Semantic remote attestation is a dynamic process, To gain experience with building and using a Trust-
and attestation of properties can be done at various edVM for semantic attestation, we chose peer-to-
points during the lifetime of a distributed applica- peer networks as one example domain. In partic-
tion. We refer to the machine running the Trust- ular, we considered the Gnutella P2P protocol[2].
edVM as the client, and the machine which is in- Peer-to-peer communication is particularly interest-
terested in attesting programs on it as the server. ing as a trial application for remote attestation. It
The TrustedVM on a client machine runs an attes- is inherently distributed in nature, and current pro-
tation service, whose job is to check or analyze the tocols vest a tremendous amount of trust in clients
behavior of applications running under the Trust- for correct operation of the network. This has led
edVM, and answer attestation requests from other to various security and policy violations, and has
machines. The server has two channels of communi- even been used to stage denial-of-service attacks
cation with the client: one with the client applica- [26, 13, 8]. In the case of the Gnutella protocol, the
tion, and another with the attestation service, with reason for these security weaknesses is that peers
which the server communicates to find out about the believe each other without verification. For exam-
behavior of the client application. This is shown in ple, when given the result of a query(a query hit in
Figure 1. The communication between the server Gnutella terminology), there is no guarantee that
and attestation service must be secure and must the given machine will actually have the content
guarantee integrity and authenticity. This can be asked for — the query result can be easily faked
done using various cryptographic protocols, such as and is not checked. This can be exploited to mount
SSL. a denial-of-service attack against a particular ma-
chine by simply flooding the network with query
Semantic attestation certifies properties of programs results all pointing to that one machine. The same
running in a virtual machine. The virtual machine holds for routing messages that announce which ma-
itself, however, runs on top of an operating system. chines are part of the P2P network. These routing
To certify the layers of software up to, and including messages (called pong messages in Gnutella, because
the virtual machine, still requires traditional remote they are sent out as replies to ping messages to find
attestation. This is done in the standard way using out network topology) can also easily be faked.
Our implementation is based on the Java Virtual time it took for 5000 subsequent ping/pong, and
Machine. We used the Java Development Kit ver- query/queryhit messages to travel between two ma-
sion 1.4.1 from Sun, running on an Intel Pentium-M chines. Both were on a 100 Mbps Ethernet network.
1.3 Ghz machine with 384 MB of RAM. This was compared with the same benchmark run
without a protocol checker. Within experimental er-
We modified the standard Java network socket class ror, the timings were the same — between 9.5 and
so that network communication over sockets could 10.2 seconds for both cases. Increasing the number
be captured and monitored. An API is exposed to of iterations to 10,000 yielded similar results — both
do this. This captured traffic is sent to a proto- cases took between 18.5 and 20.8 seconds.
col watcher which checks the protocol messages for
conformance with a security policy, and informs the This result is not a surprise since the checks are sim-
server accordingly. The Java bytecode for protocol ple, and network round-trip-time dominates compu-
watcher itself is sent by the server to the attestation tation time. Even if the checks are more complex,
service on the client, since it embodies the policy the in realistic situations they are only done periodi-
server is interested in enforcing on the client. cally, and not in a tight loop. Thus, end-to-end per-
formance of applications is still likely to show very
Here we see the utility of using a machine- little overhead.
independent code representation — the protocol
watcher can be sent to and executed on various We can distinguish between two kinds of applica-
platforms, as long as they have a Java TrustedVM. tions that run on a TrustedVM. Legacy applications
Note that the protocol watcher is independent of the are those that do not explicitly make use of trusted
application. Various implementations of a protocol functionality such as remote attestation. We just
can be checked by same protocol manager. presented an example of a legacy untrusted appli-
cation being attested by a TrustedVM, completely
We implemented a protocol very similar to Gnutella, transparently. New applications that are written
though somewhat simpler in its wire format (to sim- with trusted functionality in mind can use a much
plify debugging and parsing of network messages). broader range of a TrustedVM’s facilities.
The protocol watcher examined all outgoing mes-
sages from the client, and checked two properties: We also unsuccessfully tried writing protocol watch-
ers by using bytecode rewriting[12]. This turned
out to be unsuitable for the task because load-
• for pong messages, make sure that the IP ad- time rewriting of system classes is not allowed
dress in the message is the same as that of the in the JVM. Rewriting bytecode at load-time re-
client. quires a specialized class loader, that transforms the
bytecode before handing it off to the virtual ma-
• for query hit messages, make sure that the file
chine. However, all system classes (java.lang.*,
that is mentioned in the query actually exists
java.net.* etc) must be loaded by the “primi-
on the client.
tive” system classloader. Systems such as SASI[14]
and Naccio[15] inline reference monitors by rewrit-
These two properties were checked in particular be- ing Java bytecode. However, they transform the
cause they can exploited to mount denial-of-service classfiles off-line, and not at load-time.
attacks, and can be easily spoofed — they are com-
pletely unchecked.
4.2 A distributed computing applica-
We have not yet implemented a protocol checker tion
for multi-hop messages, but this can be done using
transitive certificate chains.
The previous application was an example of dy-
At the time of this writing, we are not aware of namic enforcement of security properties within a
any applications that use functionality provided by TrustedVM. A TrustedVM can also attest static
trusted hardware, so we do not have a meaningful properties, of both the system it is running on, as
comparison benchmark. However, we can measure well as the code that it runs. The attestation re-
the overhead that protocol checkers impose on net- quester sends across code for testing various prop-
work latency. To measure this, we measured the erties, which the TrustedVM then executes. The
results are signed, and sent back to the attestation
requester (see Figure 2). The results of these tests
can then affect further computation and communi-
cation between the two parties.

This is useful for distributed computing. There are a

number of popular distributed computing projects,
such as SETI@Home [20] and Folding@Home[27],
that distribute work units out to a large number
of clients. They face a common problem — getting
some assurances about the behavior and capabilities
of their numerous clients. There is a complex trust
relationship between the server and client, since the
server expects the client to use a particular algo-
rithm, compute answers within certain bounds, and
not return maliciously crafted or incorrect answers.
Currently, this problem is solved to some extent by Figure 2: Top-level architecture for using test suites
measures such as redundancy and keeping track of in a TrustedVM
client behavior over a period of time[22].
1. First time primality check: This is the most
Using a semantic remote attestation framework can
computationally intensive of the three problems
benefit a distributed computing application in the
and is assigned to the fastest clients. It also
following ways:
requires double precision floating point support
for doing a fast Fourier transform (FFT).
• The server can test various properties of both
the system, as well as the client, by having the 2. Double check assignment: It verifies the results
TrustedVM execute tests for it. This would of the first time primality check. The workload
give the server a better idea of the capabili- is smaller in this case and hence is assigned to
ties of the platform as well as the client. This slower clients. It also requires double precision
knowledge can be used both for giving the client floating point support.
suitable work units, and estimating how “good”
its answers are likely to be. 3. Factoring work: This tries to eliminate a few
test candidates by finding small factors using
some common factoring algorithms. This re-
• Testing for properties in this way makes the duces candidates for more expensive primality
trust relationships between the client and checks. Since this least expensive of the three
server explicit. Now, instead of being implicit this gets assigned to the slowest clients.
and being taken on trust, they are explicitly
enforced or checked by the TrustedVM.
For a full treatment of the mathematical back-
ground of this problem see [4].
To experiment with these concepts, we took
an existing distributed computing project, exam- Many different implementations of the client exist
ined its client-server trust relationships, and re- [1]. The various clients differ from each other in the
implemented it to run on our TrustedVM. We following ways
chose a distributed computing project that tries to
find large Mersenne Primes — the Great Internet
Mersenne Prime Project, or GIMPS[4]. Mersenne • The clients have subtle differences in the algo-
primes are prime numbers of the form 2n − 1. Just rithms used.
like SETI@Home[20], GIMPS distributes its compu-
tation over a large number of clients on the Internet. • Some of the clients are highly specialized for
We chose GIMPS because it divides the problem a particular architecture and hence lose porta-
into three subproblems, each with different compu- bility. Others have to be compiled for various
tational needs. They are: architecture/OS combinations.
 • The performance of different clients differ, even Thus, the server now has reliable information about
on the same platform due to implementation the clients it is communicating with. Using this in-
differences. formation, it can both vary the work units given
out to clients, as well as make estimates about the
• The accuracy of the clients also differ hence re-
accuracy of their answers. Moreover, the whole ap-
sults slightly vary. This is mainly because of
plication is now portable, and does not depend on
the different algorithms used.
specific clients.
• More surprisingly the results differ for the same
client on different platforms because of the dif-
ferences in the underlying hardware.
5 Related Work
Thus, GIMPS suffers from the same problems of dis-
tributed computing as pointed out above: its client-
server trust relationships are implicit, and the server To the best of our knowledge, there is no prior work
has very little information about the capabilities of that aims to make the mechanism of remote at-
the clients. A client is expected to behave reason- testation more fine-grained, dynamic and platform-
ably because it is specific to a particular platform, independent. However, the field of trusted comput-
and its behavior has been tested on that platform. ing has attracted a great deal of attention recently.

These problems can be solved by running this appli- Garfinkel et. al.[17] have proposed the TerraVM[16]
cation on a TrustedVM. The server now explicitly virtual machine monitor architecture to interface
tests the relevant capabilities of the client-side by with underlying trusted hardware. Their architec-
asking the TrustedVM to execute a test suite, and ture provides two VMM abstractions to software —
return the attested results. This solution also has an open box VMM, and a closed box VMM. The
the added advantage of being portable across any open box VMM simply provides a legacy, untrusted
range of architectures that implement a TrustedVM. interface. This allows old operating systems and
software to run unmodified on it. The closed box
The two capabilities that are relevant for the VMM, however, provides an interface to underly-
GIMPS project are: floating point precision and the ing trusted hardware that new software can use. A
computational power. Our test suite has a compoe- number of such VMMs can execute on bare hard-
nent for each. ware. They are strongly isolated from each other,
and have their own encrypted storage.
The most computationally intensive routine in the
prime factorization problem is computing a fast There are many important differences between Ter-
Fourier transform and its inverse. Hence to test raVM and our TrustedVM architecture. While Ter-
for computation speed we execute a one-dimensional raVM provides an interface just like real hardware,
fast Fourier transform over small but typical data the TrustedVM exposes a much higher-level inter-
and time it. The result of this test helps the server face. It executes platform-independent code. Their
to give the client an appropriate work unit. goal is providing strong isolation between applica-
tions running in different VMMs, ours is to provide
For floating point precision we are interested in test- a better technique for remote attestation. Most
ing if the platform implements a double precision importantly, TerraVM uses the standard “signed-
floating point operations and also if it complies with hash” method of remote attestation. The authors
the IEEE 754 standard for floating point. In par- acknowledge some of the shortcomings of standard
ticular we used the Java port of the Elefunt test remote attestation, and call for “appropriate tech-
suite[3]. Elefunt[11] is a test suite to check for the nical and legal protections ... to minimize abuse”.
compliance of floating point implementation of the
various functions with the IEEE floating point stan- The goal of TerraVM is similar to Microsoft’s Palla-
dards. Since the FFT and the inverse FFT use the dium architecture. Palladium is said to have a high-
sine and the cosine functions the two tests that we assurance trusted microkernel running on hardware
are interested in are the ones that determine the ac- (called the nexus) that provides strong isolation be-
curacy of these functions. Depending on results we tween legacy untrusted and newer trusted applica-
determine whether the client is accurate enough to tions, as well as among trusted applications. Un-
run the computations. fortunately, to our knowledge there is no published
technical documentation about Palladium, which trol and other safety issues. The emphasis is differ-
makes it hard to make an in-depth comparison. ent for remote attestation. Servers want to know if
the application is obeying some high-level semantic
The Cerium system[10] aims to provide tamper- rules. One candidate for an analysis that may be of
evident execution. The goal is to know if the re- interest to servers is information flow[23]. Such an
mote execution of a program was carried out in an analysis would convince the server that a client is
untampered manner. They use a physically tamper- not leaking the results of some confidential compu-
resistant CPU block. This executes all code — it is tation, or data.
not a co-processor. Tamper-resistance is provided
both at the hardware level, by physical means, and In our current implementation, the policy a server
at the software-level, by encrypting all data (includ- wants enforced is embodied in the protocol watcher
ing cache data that is written back to main mem- or test suite. We would like to develop a systematic
ory). Semantic remote attestation is orthogonal to language for expressing remote attestation requests.
this — a TrustedVM could use Cerium as an under- With “signed-hash” attestation, this was not an is-
lying hardware architecture. sue. But a TrustedVM provides a broad range of
fine-grained attestation capabilities, and a language
The Digital Distributed System Security is probably the right tool to make full use of them.
Architecture[18] had many of the features of
today’s TCPA specification[5], including secure We would also like to gain experience with devel-
bootstrapping, and remote attestation of system oping more applications that use the functionality
software using signed hashes. The Aegis system[7] provided by a TrustedVM. Distributed firewalls[19]
provided secure bootstrapping. Every layer of implement a network traffic policy at the end-points
software from the hardware up was checked (using of a network, rather than at one single point. This
stored hashes) and control was passed to it only way of distributing trust seems like a good match
if it was untampered. Both these systems did not for implementation on a TrustedVM.
focus on improving remote attestation.
The ability to communicate to a server what par-
The Trusted Computing Group (TCG), has begun ticular property of a program could not be certified
producing specifications of a hardware trusted mod- can be very useful. Using TrustedVMs, this infor-
ule to be used in personal computers[5]. They call mation can be communicated, and the server can get
it a trusted platform module (TPM). Some models detailed information about what desired properties
of IBM ThinkPad laptops contain a similar mod- are not present in a client program. It can then
ule. A commodity trusted computer will couple this make an informed decision about either decreasing
trusted module with software that provides secure its trust in this particular instantiation of a protocol,
booting and strong isolation. or stopping altogether. Thus, the server gains some
dynamic feedback about the trustworthiness of its
clients. We believe this property can be fruitfully
exploited to ”port” a variety of untrusted network
6 Discussion and Future Work protocols (TCP, HTTP etc) to a trusted computing
framework in a gradual manner, and yet have vari-
ous implementation of them inter-operate. This is in
There are many avenues for further investigation. stark contrast to the all-or-nothing model that stan-
Protocol watchers and test suites, as presented here, dard “signed-hash” remote attestation provides —
are only two of many kinds of expressive attestation attestation either passes or fails — there is no gra-
a TrustedVM is capable of. dation. This would also provide a gentler upgrade
path for applications as trusted hardware becomes
A TrustedVM is capable of attesting the results of increasingly available in the market.
some static analysis done on code. However, there
are not many static analyses of code for properties
of interest to a remote server. Most static anal-
yses and runtime enforcement policies so far have
been geared towards protecting a host from mali-
cious mobile code. Thus, the emphasis has been
on type-safety, information-flow, and resource con-
7 Conclusion of the most well-known weaknesses in peer-to-peer
protocols.

Standard ways of doing remote attestation are based Trusted computing introduced the concept of re-
purely on cryptography, and suffer from many crit- motely supervised execution - the idea that a remote
ical shortcomings — they are static, inexpressive, server will be able to monitor as well as change the
inflexible and do not scale. Most importantly, they execution of a program on a client machine. Re-
do not speak about program behavior — they can mote attestation is the key to doing this. However,
only attest to the presence of a particular binary. current architectures for attestation are able to im-
It is possible for an attested binary to have bugs plement this idea in only a very limited way. Seman-
and not obey the security policy a server was ex- tic remote attestation takes this idea to its logical
pecting it to. Remote attestation is hard to scale conclusion — to have fine-grained, dynamic control
up to a flood of software patches and upgrades. It over the monitoring and execution of an application.
also does not accommodate a varied, homogeneous
computing environment very well.

We have introduced a novel technique for remote at- References

testation based on language-based virtual machines.
The core idea behind our technique, called seman- [1] GIMPS source code timings page. http://
tic remote attestation, is to use a language-based hogranch.com/mayer/gimps_timings.html.
virtual machine that executes a form of platform-
[2] The gnutella protocol specification.
independent code. Software up to and including
http://www9.limewire.com/developer/
this virtual machine is trusted. However, the vir-
gnutella_protocol_0.4.pdf.
tual machine can certify various properties of code
running under it by explicitly deriving or enforc- [3] Java port of elefunt.
ing them. This can be done in many ways, such as http://www.math.utah.edu/ beebe/software/java/.
observing the execution of programs running in a
VM, or analyzing the code before execution. This [4] The Great Internet Prime Mersenne Search:
is particularly easy to do with high-level platform- GIMPS. http://www.mersenne.org/.
independent code that has a lot of information [5] T. C. P. Alliance. TCPA PC-
about the structure and properties of code. specific implementation specification
(http://www.trustedcomputing.org), May
The fact that “trusted computing”, and its core 2001.
technique, standard remote attestation, can lock
consumers into a particular program or platform [6] R. Anderson. Cryptography and competition
has been a very widely expressed fear. A key ad- policy — issues with trusted computing. In
vantage of our approach is that reasoning about the Workshop on Economics and Information Se-
behavior of a program is now not tied to a partic- curity, May 2003.
ular binary. Semantic remote attestation checks for [7] W. Arbaugh, D. Farber, and J. Smith. A secure
program properties, and works with different im- and reliable bootstrap architecture. In IEEE
plementation of the same program as long as they Symposium on Security and Privacy, 1997.
satisfy the properties required of them.
[8] S. Bellovin. Security aspects of napster and
To validate our ideas we have implemented a pro- gnutella. In USENIX Security Symposium,
totype TrustedVM by modifying a Java virtual ma- Aug. 2000.
chine to observe the behavior of network protocols.
[9] E. Bugnion, S. Devine, K. Govil, and M. Rosen-
We have used this prototype to check the untrusted
blum. Disco: Running commodity operat-
behavior of a Gnutella-like peer-to-peer protocol.
ing systems on scalable multiprocessors. ACM
Specifically, we check that messages about network
Transactions on Computer Systems, 15(4):412–
topology and query results are not spoofed. Our
447, 1997.
measurements show that the overheads of checking
are negligible, at least for the simple checking this [10] B. Chen and R. Morris. Certifying program
particular application needs. However, even the few execution with secure processors. In USENIX
simple checks we do are sufficient to overcome some HotOS Workshop, May 2003.
[11] W. Cody and W. Waite. Software manual for [23] A. C. Myers. JFlow: Practical mostly-static in-
the elementary functions. Prentice Hall, 1980. formation flow control. In Symposium on Prin-
ciples of Programming Languages, pages 228–
[12] G. Cohen, J. Chase, and D. Kaminsky. Auto- 241, 1999.
matic program transformation with JOIE. In
1998 USENIX Annual Technical Symposium, [24] G. C. Necula. A scalable architecture for proof-
pages 167–178, 1998. carrying code. Lecture Notes in Computer Sci-
ence, 2024:21+, 2001.
[13] Z.-Y. Demetris. Exploiting the security weak-
neses of the gnutella protocol, Mar. 2002. [25] F. B. Schneider, G. Morrisett, and R. Harper.
A language-based approach to security. Lecture
[14] Erlingsson and Schneider. SASI enforcement Notes in Computer Science, 2000:86–??, 2001.
of security policies: A retrospective. In
[26] D. Wallach. A survey of peer-to-peer security
NSPW: New Security Paradigms Workshop.
issues. In International Symposium on Software
ACM Press, 2000.
Security, Nov. 2002.
[15] D. Evans and A. Twyman. Flexible policy- [27] B. Zagrovic, E. Sorin, and V. Pande. Beta hair-
directed code safety. In IEEE Symposium on pin folding simulations in atomistic detail using
Security and Privacy, pages 32–45, 1999. an implicit solvent model. Journal of Molecular
Biology, 317(4), 2002.
[16] T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum,
and D. Boneh. Terra: A virtual machine-based
platform for trusted computing. In Proceed-
ings of the 19th Symposium on Operating Sys-
tem Principles(SOSP 2003), October 2003.

[17] T. Garfinkel, M. Rosenblum, and D. Boneh.

Flexible os support and applications for trusted
computing. In Proceedings of the 9th Workshop
on Hot Topics in Operating Systems (HotOS-
VIII), May 2003.

[18] M. Gasser, A. Goldstein, C. Kaufman, and

B. Lampson. The digital distributed system se-
curity architecture. In Proc. 12th NIST-NCSC
National Computer Security Conference, pages
305–319, 1989.

[19] S. Ioannidis, A. D. Keromytis, S. M. Bellovin,

and J. M. Smith. Implementing a distributed
firewall. In ACM Conference on Computer
and Communications Security, pages 190–199,
2000.

[20] E. Korpela, D. Werthimer, D. Anderson,

J. Cobb, and M. Lebofsky. Seti@home — mas-
sively distributed computing for SETI. Com-
puting Science and Engineering, 3(1), 2001.

[21] D. Kozen. Language-based security. In Math-

ematical Foundations of Computer Science,
pages 284–298, 1999.

[22] D. Molnar. The SETI@home problem.

http://www.acm.org/crossroads/columns/
onpatrol/september2000.html, Sept. 2000.