Covert Channels That Survive Logical Isolation

A sandbox is a statement about access. It says that a program cannot read this memory, cannot call that function, cannot open that file. It says nothing about whether the program can learn the same information by other means, and Lampson’s 1973 note on the confinement problem identified the gap: a confined process may still communicate with the outside by modulating a resource that the outside can observe.

The distinction between a covert channel and a side channel is a matter of intent. A side channel leaks information as a by-product of legitimate computation. A covert channel is created deliberately by two parties who are not permitted to communicate directly. The mechanisms are the same; the policy response differs, because a covert channel is a policy violation by design while a side channel is an information leak that the computation cannot avoid.

Why timing is the universal carrier

Every channel needs a signal that one party can modulate and another can observe. Time is the signal that survives every logical isolation, because the clock is shared by construction: a process on a machine observes the same passage of time as every other process on it, regardless of which address space, container, or tenant it belongs to.

The general shape of a timing channel: a sender modulates the duration of some operation based on the bit it wants to send, and a receiver measures the duration of an operation it performs and infers the bit. The modulation can be as simple as “do a large computation for a 1, do nothing for a 0”, and the measurement can be as simple as timing a loop. This channel requires no shared memory, no shared file, and no communication primitive. It requires only that both parties run on the same machine and can read a clock.

Bandwidth is limited by the receiver’s ability to distinguish durations in the presence of noise. Clock resolution, scheduling jitter, and the interference of other work on the machine all add variance, and the sender must make the difference between the two states larger than the noise. A channel that sends one bit per second is easy to build; one that sends thousands of bits per second requires a low-noise carrier, which is why cache-based channels are used when bandwidth matters.

The policy implication is uncomfortable. A sandbox that permits a confined program to run concurrently with an unconfined one, and permits either to read a clock, has a channel. Closing it requires either eliminating concurrency, which defeats the purpose of hosting, or eliminating clock access, which the runtime can do only for its own interfaces and not for the hardware’s time source.

Cache-based channels and the granularity of sharing

A cache is shared between all code on a core, and its state is not part of any address space. Two processes with disjoint page tables share the same L1 and L2, and a memory access by one changes what the other will find there. Address-space separation of the kind discussed in fault isolation is a statement about the page table, and the cache is not addressed through the page table.

The prime-and-probe pattern: the receiver fills a cache set with its own data, waits, then measures how long it takes to reload each line. Lines that the sender evicted take longer to reload, so the pattern of evictions encodes information about the sender’s addresses. The sender need not cooperate; if it is a cryptographic routine, its address pattern is a function of its secret key, and the receiver recovers the key from the eviction pattern.

Flush-and-reload variants use an instruction that invalidates a specific cache line, so the receiver can observe whether the sender accessed that exact address. These are more precise and require the receiver to know the address, which is available when the two parties share a library or when the address is in a shared mapping.

The isolation argument that fails here is the one that says “the tenants have separate address spaces, so they cannot see each other’s memory”. They cannot read each other’s memory, which is true and insufficient. They share a cache, and the cache’s replacement policy is a function of both tenants’ access patterns.

Mitigations operate at three levels, and each has a cost.

Partition the cache. If each tenant’s data is constrained to a subset of cache sets, the tenants cannot evict each other. Intel’s Cache Allocation Technology provides this, and it requires the cache to be way-partitioned, which means a tenant gets a fraction of the ways in each set. The cost is that each tenant’s effective cache is smaller, so legitimate performance falls.

Flush on switch. If the runtime invalidates the cache when switching between tenants, no state carries across. The cost is that every switch pays the refill cost, which is substantial for a large working set, and the benefit is bounded by the switch granularity: within a single time slice, the two tenants are not concurrent, but the channel through the cache is closed only if the flush is complete.

Remove the clock. If the receiver cannot measure time precisely, the channel’s bandwidth collapses. Some environments reduce the resolution of the clock available to untrusted code, which raises the noise floor and makes fine-grained measurement unreliable. This is a mitigation rather than a closure, because coarser timing channels remain and because the receiver may find other time sources.

Contention as a channel with high bandwidth

Shared resources with quantifiable capacity produce channels that are easier to use than caches, because the modulation is coarse and the measurement is a simple rate.

Memory bandwidth: a tenant that streams through memory reduces the bandwidth available to another, and the reduction is measurable by the second tenant’s throughput. The channel’s bandwidth is low but the mechanism needs no knowledge of addresses or cache geometry.

Allocator state: if two tenants allocate from a shared allocator, one tenant’s allocation pattern changes the addresses the other receives, and the addresses are observable. A tenant that frees a block and observes that the next allocation returns the same address learns something about the other tenant’s activity. Per-tenant heaps, as described in fault isolation, remove this channel by construction, which is one of their less obvious benefits.

Lock contention: a shared lock’s acquisition time reflects how long another party held it, so the holder’s behaviour is observable to the waiter. If the runtime has any shared lock on the path of both tenants, the channel exists. The mitigation is to remove sharing, which usually means per-tenant data structures.

File system and network state: a shared directory’s metadata, a shared socket’s queue depth, and a shared rate limiter’s remaining budget are all observable. Each is a channel whose bandwidth depends on how finely the state can be read.

The formal statement and why it is unsatisfying

Information-flow security states the requirement as non-interference: the observable behaviour of the system must not depend on the high-level inputs. If a low-clearance observer’s view is identical regardless of the high-clearance value, no flow exists.

Non-interference is a strong property and it is undecidable in general for programs with loops and unbounded state. Practical systems therefore check a syntactic approximation: a type system that labels values and rejects assignments from high to low, or a dynamic monitor that taints values and blocks flows at sinks. Both catch the direct flows and miss the indirect ones, because a value can influence a branch that influences timing without ever being assigned to a low variable.

The gap is not a defect in the type systems; it is the gap between what a program computes and how long it takes. A type system reasons about values, and timing is not a value. Closing the gap requires reasoning about the program’s execution cost as a function of its inputs, which is what constant-time programming disciplines attempt for specific operations: no data-dependent branches, no data-dependent memory indices, no data-dependent loop bounds. Those disciplines are enforceable by inspection and by tooling for small routines, and not enforceable in general.

What a runtime can do about it

Three practical positions, in increasing order of cost.

Ignore it and document it. Most sandboxes take this position, because the channel requires concurrent execution on the same physical machine and the threat model excludes that. The position is defensible when the tenants are all operated by the same party, and indefensible when they are not.

Reduce the carrier’s precision. Round the clock, coarsen the scheduler’s quantum, and avoid sharing data structures between tenants. Each reduces bandwidth without eliminating the channel. The measure of success is not zero but “below the noise floor of the application’s own variance”, which is a weaker and achievable goal.

Partition the physical resources. Separate cores, separate cache ways, separate memory channels, and separate allocators. This is what strong multi-tenant isolation does, and it converts the problem from a software one to a hardware partitioning one. The cost is that partitioning wastes capacity: a core reserved for one tenant is idle when that tenant is idle, and the utilization loss is the price of the guarantee.

The honest summary is that logical isolation and information isolation are different properties, and a system can have the first completely and the second not at all. Lampson’s note is still the clearest statement of why: the confinement problem is not about access to objects, it is about the flow of information, and objects are only one of the paths that information takes.