Secure Virtual Machine

Project Infrastructure LLVM Dev List Archives
1

Many VMs focus on performance, optimizations, memory consumption, etc.
but very few, if any, focus on fault isolation and security. Given
memory safety, any VM reduces to capability security, which is
sufficient to implement most security policies of interest; however,
most such VMs still ignore two main attack vectors from malicious
code: DoS attack on memory allocation, and DoS against the CPU.

I've been mulling over how LLVM could be extended to provide a degree
of isolation from these two attack vectors [3].

Preventing a DoS against memory allocation involves controlling access
to allocation in some way. Fine-grained control over every single
allocation is likely infeasible [1]. Similarly, preventing a DoS
against the CPU involves controlling the execution time of certain
code blocks, by introducing concurrency or flow control of some sort.

There is a single abstraction which has solved the above two problems
for over 40 years: the process, which provides an isolated memory
space, and an independently schedulable execution context.

A VM process would run in its own heap and manages its own memory. The
memory allocation routines are scoped to the process, which can itself
potentially call out to a "space bank" to allocate more space for its
heap. Memory faults in a process can be handled by "keepers" [4].

Concurrency is still an open question, because a kernel thread per VM
process is actually overkill. A mix of kernel threads and Erlang-style
preemptive green threads might be optimal, but this isn't the
interesting part of the proposal IMO.

There must also be some sort of interprocess communication (IPC),
either via copying between heaps, or an "exchange heap". The exchange
heap is the approach taken by the Singularity OS [2] where they add
"software isolated processes" to the .NET VM and make it an operating
system.

There are two approaches I currently foresee for adding process
constructs to LLVM:

1. Add process management instructions to the core instructions, and
modify the runtime to rebind the allocation routines depending on some
VM-level context that names which process is actually executing
(perhaps in thread-local storage).

2. Add instrinsics to launch an entirely new VM instance
(ExecutionEngine?) as if it were the process. This would involve
modifying the VM to accept allocation primitives as function pointers,
and potentially adding some scheduling awareness.

At the moment, I'm not primarily interested in making LLVM itself a
secure VM, but I think that too might be possible, and suggests
possible future work.

For instance, unsafe pointer operations can be made safe if the
casting operation from integer to pointer implements a dynamic check
that it's within the bounds of the heap. This is potentially an
expensive operation, but such casts only penalize heavily unsafe
programs, which should hopefully be rare. I believe LLVM programs that
do not use these casting instructions are inherently memory safe, so
they incur no such penalties (please correct me if I'm wrong). Using
this approach, LLVM could support the safe execution of unsafe
programs by running them in an isolated VM process.

Alternately, one could actually launch the unsafe code in a completely
separate OS process with a new LLVM instance, and the VM-level IPC
instructions would transparently perform OS-level IPC to the separate
process. This maintains the isolation properties, with the full
execution speed (no need for dynamic heap bound checks), at the cost
of using slightly heavier OS processes.

Any comments on the feasibility of this approach? I'm definitely not
familiar with the LLVM internals, and I wrote the above given only my
understanding from reading the LLVM reference manual.

Sandro

[1] except perhaps using some sort of region-based approach with
region inference, etc. I'm still reading the literature on this.
[2] http://research.microsoft.com/os/singularity/
[3] I realize that LLVM is unsafe in other ways, but I believe it
currently lacks even the base constructs necessary to even build a
secure VM on top of it.
[4] I can explain space banks and keepers concepts further, but just
think of them as stateful exception handlers specific to a process.
The concepts come from the KeyKOS/EROS and Coyotos secure operating
systems.

2

We have a research project that is developing a Secure Virtual Architecture using LLVM as the instruction set, and implementing via a VM which we call a Secure Virtual Machine. The memory safety foundations of this work are based on Dinakar Dhurjati's thesis and publications:
  http://llvm.org/pubs/

SVA is at a very preliminary stage but some slides about it are attached.

2007-SVAOverview.ppt (809 KB)

3

SVA looks very promising. It would be great to be able to run
unmodified C safely!

However, it does not seem to address my original question: how can I
ensure that code cannot DoS either the memory subsystem, or the CPU?

In my proposal, I could execute said code in a concurrent process with
a memory quota. How would SVA address that problem?

Sandro

4

Sandro Magi wrote:

SVA looks very promising. It would be great to be able to run
unmodified C safely!

However, it does not seem to address my original question: how can I
ensure that code cannot DoS either the memory subsystem, or the CPU?
  

To be honest, while I understand your questions, I do not understand the
context in which you are asking them. Are you asking if LLVM provides
any facilities to provide these protections, or are you asking if we've
added any special features to LLVM (or to SVA; our research work based
on LLVM) to provide these protections beyond what is commonly provided
by systems today? Can you provide more information on how you want to
use LLVM for your project?

To answer the first question, yes, there are simple ways in which LLVM
can provide these protections. Programs compiled to LLVM bytecode are
either translated to native code ahead of time or run with a JIT. Either
way, each program is run within a separate process which has its own set
of operating system imposed memory limits and CPU time limits. Code can
execute the fork() and clone() system calls to create new threads and
processes (I'm not sure if our JIT can handle multi-threaded code, but
in theory, it could). You could, in fact, write an LLVM transformation
pass that inserts calls to fork()/clone()/pthread_create()/etc. to
create new processes/threads as needed to enforce your policies. In
short, a program compiled to LLVM bytecode gets whatever protections the
OS itself provides against such attacks, and I believe these guarantees
extend to the JIT as well as to the code running within the JIT.

To answer the second question, no, we have not done any research into
how to provide more fine grained protections against these attacks in
our Secure Virtual Architecture (which is based on LLVM). In particular,
there is nothing that ensures that there are any protections against
these sort of attacks on kernel level code compiled for SVA, and we have
not done any work to ensure that our JIT, if run below the OS, would be
immune to such attacks.

However, I suspect that adding such features would be an interesting
research question. I would think that static program analysis could be
used to determine code follows a particular memory allocation/CPU usage
policy. I think it would also be possible to use automatic program
transformation to modify code to have run-time checks to ensure that
such policies were followed. However, I'm not familiar with the work in
this area, so I don't know what has been done or what challenges one
would need to overcome.

-- John T.

5

To be honest, while I understand your questions, I do not understand the
context in which you are asking them. Are you asking if LLVM provides
any facilities to provide these protections, or are you asking if we've
added any special features to LLVM (or to SVA; our research work based
on LLVM) to provide these protections beyond what is commonly provided
by systems today? Can you provide more information on how you want to
use LLVM for your project?

The context was fully detailed in my original message:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-June/009261.html

Basically, if you want to be able to download and execute potentially
malicious code safely, no existing VM is sufficiently safe, since the
malicious code can still DoS the CPU and the memory subsystems. This
is because all VMs of which I'm aware provide insufficient resource
accounting; the only efforts to minimize these DoS opportunities are
CapROS/EROS and Coyotos secure operating systems (that I'm aware).
Secure mobile code will remain a pipe dream until such isolation is
addressed.

So I was proposing an extension to LLVM to address the problem, and
asking about the feasibility of the extension as detailed in the above
message.

Static analyses are certainly preferable to a runtime solution, but I
have yet to see a static analysis that attempts to extract these
specific properties. The sort of analysis that might be able to do so
with sufficient flexibility might be "sized types", which express
algorithmic runtime and space complexity in types. I'm doubtful that
this approach is feasible with low-level LLVM code, but I'd love to be
wrong!

Another attack specific to a JIT is self-modifying code (SMC); if a
piece of SMC can repeatedly get the VM to re-JIT code, the VM had
better make sure that the JITting is done under the SMC's schedule,
and using memory booked to the SMC. Otherwise, this is another DoS
vulnerability possible due to improper resource accounting.

I was going to ask about SMC in a separate e-mail, but since I brought
it up here: can LLVM support languages with SMC or runtime code
generation like MetaOCaml? I don't see how it could be done from what
I understand of LLVM, but perhaps others see a way. It might be
possible with additional intrinsics that invoke the JIT, but I don't
see how native LLVM can express SMC.

Thanks for your detailed response. Hope I've been able to clear
everything up. :slight_smile:

Sandro

6

>
> To be honest, while I understand your questions, I do not understand the
> context in which you are asking them. Are you asking if LLVM provides
> any facilities to provide these protections, or are you asking if we've
> added any special features to LLVM (or to SVA; our research work based
> on LLVM) to provide these protections beyond what is commonly provided
> by systems today? Can you provide more information on how you want to
> use LLVM for your project?

The context was fully detailed in my original message:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-June/009261.html

Basically, if you want to be able to download and execute potentially
malicious code safely, no existing VM is sufficiently safe, since the
malicious code can still DoS the CPU and the memory subsystems. This
is because all VMs of which I'm aware provide insufficient resource
accounting; the only efforts to minimize these DoS opportunities are
CapROS/EROS and Coyotos secure operating systems (that I'm aware).
Secure mobile code will remain a pipe dream until such isolation is
addressed.

Personally, I wonder it may be a little bit too early for LLVM to meet
these fine-grained
confinement problems before the SVA gets mature.
Real world virtual machines like Vmware or Xen already provide some
level of confinement which in most circumstances can prevents an
attacker in guest OS from overwhelming the host.
(e.g. I have a native debian installed on a core duo system. If I
configure my vmware with 1 virtual cpu, I always have the cpu power
to manage my native debian even with the Dos case in the vmware.)
SVA is a step forward which is more analyzable compared to Vmware or Xen.
And more confined policies seems to be steps further.

So I was proposing an extension to LLVM to address the problem, and
asking about the feasibility of the extension as detailed in the above
message.

Static analyses are certainly preferable to a runtime solution, but I
have yet to see a static analysis that attempts to extract these
specific properties. The sort of analysis that might be able to do so
with sufficient flexibility might be "sized types", which express
algorithmic runtime and space complexity in types. I'm doubtful that
this approach is feasible with low-level LLVM code, but I'd love to be
wrong!

I think John Criswell was referring to this kind of particular cases:

   for ( i=0; i<10; ++i) p[i]=malloc( 10* sizeof(int) );

If we statically "pattern match" the loop we can see that this line of
code trends to allocate
memory with 100*sizeof(int). This static information may be feed to
the optimizer (can we allocate 100*sizeof(int) contiguous memory at a
time? ) or the security protector ( Is this line of code allocating
more than expected? ).

Correct me if I am wrong. :slight_smile:

Best Regards,
Nai

7

I'm not proposing a secure virtual machine for unsafe code (though I
did suggest that it could possibly be extended to unsafe code), I'm
suggesting extensions to handle this security hole for *safe* code. At
the moment, if I want to design a secure language and runtime like
Singularity, I can't build it on LLVM because I don't have sufficient
control over memory management and execution.

Actually, I probably can build Singularity on LLVM, but it's not at
all *straightforward* to do so; it involves allocating byte buffers
and manually managing them as a heap, transforming all functions to
explicitly pass around process state, and not using LLVM's allocation
routines, but using custom ones instead.

I would think LLVM would want to make this mapping a little simpler,
hence my proposal.

Sandro

8

Let me cut it down to the core problem: I'm asking about the
feasibility of extending LLVM with constructs to manage separate
heaps. Given my current understanding of LLVM, I can see this done in
two ways:

1. Add heap management instructions to the core instructions, modify
allocation routines to explicitly name heaps or modify the runtime to
rebind the allocation routines depending on some VM-level context that
names a heap (thread-local storage?).

2. Add instrinsics to start a new heap (via a new ExecutionEngine?).
This would involve modifying the VM to accept allocation primitives as
function pointers.

So a program or language with real-time constraints where an
incremental GC is preferable, and where an efficient, non-incremental
GC is used for other tasks, can be expressed as partitioned heaps each
with their own GC.

Sandro

9

Sandro Magi wrote:

Let me cut it down to the core problem: I'm asking about the
feasibility of extending LLVM with constructs to manage separate
heaps. Given my current understanding of LLVM, I can see this done in
two ways:
  

If you just need to partition the heap into multiple heaps, then the
easiest thing to do would be to replace the use of malloc/free
instructions with calls to library functions that implement your
segmented heap allocation/free functions.

For example, in the Automatic Pool Allocation work
(http://llvm.org/pubs/2005-05-21-PLDI-PoolAlloc.html), we have an LLVM
pass that changes malloc instructions:

%tmp = malloc struct {i8}

... into calls to an allocation function that takes a pool identifier
and an allocation size as arguments (in this work, we segregated the
heap based upon pointer analysis results):

%tmp = call %poolalloc (sbyte * PoolID, uint 8)

The poolalloc function is then implemented as a run-time library
(written in C) that is compiled and linked into the program (either as a
native code library or an LLVM bytecode library).

You could do something similar to implement multiple heaps.

Your proposed methods below (adding intrinsics or new core instructions)
would work too, but using memory allocator functions does the same thing
with less work. Adding intrinsics or new core instructions is only
useful in a few rare cases, such as when you need special code generator
support or need to extend the type system.

1. Add heap management instructions to the core instructions, modify
allocation routines to explicitly name heaps or modify the runtime to
rebind the allocation routines depending on some VM-level context that
names a heap (thread-local storage?).

2. Add instrinsics to start a new heap (via a new ExecutionEngine?).
This would involve modifying the VM to accept allocation primitives as
function pointers.

So a program or language with real-time constraints where an
incremental GC is preferable, and where an efficient, non-incremental
GC is used for other tasks, can be expressed as partitioned heaps each
with their own GC.
  

Doing GC may require using the LLVM GC intrinsics as described in this
document (http://llvm.org/docs/GarbageCollection.html), but just
segmenting the heap into multiple heaps should not require any new
instructions or intrinsics to be added.

-- John T.

10

If you just need to partition the heap into multiple heaps, then the
easiest thing to do would be to replace the use of malloc/free
instructions with calls to library functions that implement your
segmented heap allocation/free functions.

For example, in the Automatic Pool Allocation work
(http://llvm.org/pubs/2005-05-21-PLDI-PoolAlloc.html), we have an LLVM
pass that changes malloc instructions:

%tmp = malloc struct {i8}

... into calls to an allocation function that takes a pool identifier
and an allocation size as arguments (in this work, we segregated the
heap based upon pointer analysis results):

%tmp = call %poolalloc (sbyte * PoolID, uint 8)

The poolalloc function is then implemented as a run-time library
(written in C) that is compiled and linked into the program (either as a
native code library or an LLVM bytecode library).

You could do something similar to implement multiple heaps.

Ah, I didn't realize passes could do such transformations. I'll read
up on them further then, thanks. :slight_smile:

Doing GC may require using the LLVM GC intrinsics as described in this
document (http://llvm.org/docs/GarbageCollection.html), but just
segmenting the heap into multiple heaps should not require any new
instructions or intrinsics to be added.

Hmm, I don't see how the current GC intrinsics could be used with two
different heaps, particularly if each heap is GC'd with its own
algorithm. It seems like you would need a pass like the one you
describe above to specify a heap each time you mark a root, or
allocate, which would require your own augmented intrinsics, or
equivalent calls inserted via a pass.

Sandro