KIT: Testing OS-Level Virtualization for Functional Interference Bugs

Containers share one kernel, and the isolation between them is enforced by scattered checks that a developer has to remember to write on every path that touches a protected resource; when one is missing the kernel does not crash — it quietly answers a question about the neighbours, which is exactly the kind of bug a fuzzer cannot see because there is nothing to catch. This paper (Purdue) runs the victim container twice, once with and once without an attacker container beside it, and treats any difference in the victim's system call results as evidence, finding 9 real isolation bugs in a stable Linux kernel.

The argument in one glance

Problem

One kernel is supposed to keep the tenants apart

Containers get their isolation from the kernel rather than from a hypervisor, which is what makes them cheap and also what makes them fragile. The kernel must give each container an independent view of processes, network stacks, mount points, hostnames and more, and it does that by adding checks deep inside the code on every path that can reach a protected resource. The system call interface is enormous and the codebase is larger still, so a single forgotten check is enough to leak a neighbour secrets or let one tenant degrade another. Cloud providers are visibly nervous about running containers from different customers together for exactly this reason.
What people did

Fuzz the kernel, as everyone does

Kernel testing is a mature field with excellent tools. A fuzzer generates enormous numbers of random system call sequences, runs them, and watches for something to go wrong — a crash, a hang, a sanitizer complaining about an out-of-bounds access or a data race. This works extremely well and has found a great many real bugs. It is the default answer to the question of how you test something as large and as complicated as a kernel.
Why it fell short

There is nothing for the fuzzer to catch

A missing isolation check does not corrupt memory or crash anything. The system call succeeds, returns a well-formed result, and the result happens to describe the wrong container. From the fuzzer point of view nothing occurred at all. Worse, the shape of the problem does not fit either: a fuzzer tests one sequence of calls, whereas interference by definition requires two — something one container does and something another container observes. The search space is not large, it is quadratic in an already unmanageable space.
This paper's idea

Run the victim twice and see if the attacker was visible

This paper (Purdue University — Congyu Liu, Sishuai Gong and Pedro Fonseca) builds KIT, which supplies the missing oracle by construction. Run one container program, the receiver, and record its system call results. Then run it again from an identical starting state, except that another container, the sender, ran first. If the kernel is isolating properly, the two traces must be identical. Any difference is evidence that something crossed a boundary. The hard part is not the idea but making it usable: cutting a quadratic search space down, and stopping the flood of differences that are not bugs.

Why this problem is worth solving

The mechanism being tested is unusual in that it is not a component you can point at, which is most of why it is hard to get right.

A NAMESPACE gives a group of processes their own view of one class of kernel resource. There are eight types, covering process IDs, mount points, hostnames, inter-process communication, the network stack, user and group identity, control group roots and system time, and a container is just a process that has joined a chosen combination of them. What makes this hard is that isolation is CROSS-CUTTING rather than modular: there is no single place where it lives. Every system call that might directly or indirectly reach a protected resource needs its own logical check, buried wherever that access happens, and a developer implementing an apparently unrelated subsystem has to remember. The paper cites a bug where process IDs from one namespace leaked through a statistics call in the inter-process communication subsystem, because nobody thought that code had anything to do with process isolation

The testing problem is really a problem about what counts as evidence.

Traditional kernel testing looks for evidence of an INTERNAL error — a corrupted pointer, an unbalanced lock, a crash. The bugs here produce none of that; the kernel executes happily and returns a well-formed answer that is simply wrong. So the paper switches to a property about OUTPUT instead. Functional non-interference says that what one container does must have no observable effect on another, and it is checkable without knowing anything about the kernel internals: run the observing container twice from an identical machine state, once alone and once after the other container has acted, and compare what its system calls returned. Identical traces mean nothing crossed. A difference means something did. The oracle needs no model of correct behaviour, only the assumption that isolation means what it says — which is why it can catch logic errors that leave no other trace

What people did before, and where it broke

Fuzz the kernel and watch for crashes. The standard approach, well tooled, and genuinely productive against memory errors and races.
But these bugs produce no failure at all. The call succeeds and returns something plausible, so there is nothing for a crash detector or a sanitizer to report.
Compare specific files between a container and the host. Prior work checks whether the same entries under the process and system filesystems look different from inside and outside a container.
But it covers a tiny slice of what namespaces protect. It cannot see leaks through any other interface, and it does not explore different kernel states, so bugs that need an unusual state stay hidden.
Statically analyse the kernel for exhaustible resources. Another line of work looks for abstract resources a container could consume to deny service to others.
But it targets one bug class and struggles with the kernel. Static analysis has a hard time being sound in a codebase this large and pointer-heavy, and extending it to leaks is not obvious.
Just look at the code. Every bug of this kind reproduced in the paper was originally found by a human reading the kernel.
But humans miss them repeatedly, even on the second pass. One bug found here is in a function that had already been patched for a very similar leak; the fix covered network device information and overlooked packet socket information in the same output.
The gap. The tools that scale could not tell a bug had happened, and the method that could tell was a person reading code.

How you catch a kernel telling one container about another

Turning an isolation property into a test with a decidable outcome

Generate random system call sequences and watch for failures

The established kernel fuzzing loop: produce enormous numbers of programs, run them, and report crashes, hangs and sanitizer violations. This is the source of the raw material here too, since the corpus of test programs comes from an existing fuzzer rather than being invented.
↓ →
Redefine the bug as a difference between two runs new

Pick two programs and call them sender and receiver. Run the receiver alone from a clean machine snapshot and record every system call result. Run it again from the same snapshot, this time after the sender has executed in another container. If isolation holds the two traces must match, so a difference is the bug report.
↓ →
Cut the quadratic space using kernel memory accesses new

Interference requires a data flow, so a sender can only affect a receiver by writing kernel memory the receiver later reads. Profile every candidate program from an identical snapshot, record which kernel addresses it touches and how, then pair programs that write and read the same location.
↓ →
Cluster the surviving pairs and run one from each new

Many pairs exercise the same kernel behaviour and would find the same bug. Group them by the instructions involved in the data flow, optionally also by the call stacks those instructions ran under, and execute a single representative per group. This is what makes the campaign finish.
↓ →
Strip out differences that are not evidence new

Two kinds of noise. Results that vary anyway, like timestamps, are found by re-running the receiver with different start times and marking which parts of the result vary. And resources the kernel never promised to isolate are excluded using a partial specification the user refines as they go.
↓ →
Blame a specific pair of system calls and group by it new

For each surviving report, remove one sender call at a time and see whether the difference disappears; the call that masks it is the culprit. Reports sharing a culprit pair almost always share a root cause, so grouping by that pair collapses hundreds of reports into a handful worth reading.

Applied to the namespace subsystem of stable Linux 5.13, using a corpus of 98,853 programs from an existing fuzzer, executing 1.13 million test cases across 110 virtual machines on four servers.

The idea

The oracle is the contribution. Everything else in the paper exists to make this one move practical. Kernel fuzzing is effective because a crash is self-announcing — you do not need to know what the program should have done, only that it should not have died. Isolation bugs give you nothing of the sort, so the paper manufactures a signal by exploiting the structure of the property itself. Non-interference is a statement about two executions rather than one, which means it can be checked by running one of them twice and diffing, with no model of correct kernel behaviour required anywhere. What makes this more than a restatement is that the resulting evidence is also unusually good for the person who has to act on it: a report is a concrete pair of programs, a specific system call, and two different answers, which lets a developer compare the implementation against the documentation directly rather than hunting for a memory error. Converting a property that cannot be observed in one run into a difference between two runs, so that a testable signal exists where none did, is the same manufacture-the-oracle move covered elsewhere on this site where a compiler property with no natural failure mode becomes checkable by compiling twice and comparing the outputs.

The search space doubled in dimension, so it had to be cut by reasoning about mechanism. A fuzzer explores sequences of system calls; this needs pairs of sequences, which squares an already hopeless space. Brute force is not an option, so the paper narrows it with a physical fact about how interference must happen: one container can only affect another by writing kernel memory that the other later reads. That converts an unbounded search over program pairs into something mechanical — profile each program once from an identical snapshot, record the kernel addresses it writes and reads, and only pair programs whose accesses overlap. A second filter drops pairs where the reading call does not touch a namespace-protected resource at all, since such a pair could not demonstrate an isolation failure even in principle. The effect is dramatic: unfiltered data-flow pairing yields 234 million test cases, and clustering brings that to 1.13 million while still finding all nine bugs, where random pairing across a comparable budget finds five. Replacing an intractable search with a necessary condition that is cheap to evaluate is the same prune-by-what-must-be-true discipline covered elsewhere on this site where a candidate space is narrowed by a structural requirement rather than by sampling.

A detector nobody can act on is not a detector. The most instructive numbers in the paper are not about bugs. Over 1.13 million test cases produce 15,353 reports, and 14,545 of them are noise — differences that are real but meaningless, either because the result varies between runs anyway or because the resource was never namespace-protected. Both are handled carefully rather than bluntly. The non-determinism filter re-runs the receiver at different times and marks which parts of a result vary, at the granularity of individual fields in a parsed structure, because a call like a file stat returns a non-deterministic timestamp alongside a perfectly deterministic file size and discarding the whole call would hide real bugs. The protected-resource filter uses a partial specification the user refines incrementally rather than demanding a complete model up front. And the 808 survivors are then collapsed to 71 groups by identifying which sender call actually caused each difference, through the direct method of removing calls one at a time until the difference vanishes. The total human cost lands at about 30 person-hours. Treating false-positive suppression and report deduplication as first-class design problems rather than post-processing is the same make-the-output-actionable discipline covered elsewhere on this site where a detection technique only becomes usable once someone works out how to present what it found.

Following one leak from suspicion to patch

How a packet socket in one container became visible in another

The paper first case study, a confirmed information leak in the network namespace of Linux 5.13, patched upstream within a week.

Step 1 of 5

Pair two programs that touch the same kernel memory

Profiling finds that one program writes a kernel structure describing registered packet types when it creates a packet socket, and another reads that same structure when it opens a particular file under the process filesystem. That overlap is the necessary condition for interference, so the pair becomes a test case. Nothing yet suggests a bug.

the reading call also has to touch something namespaces claim to protect, and the network namespace documentation explicitly covers this directory
pairs failing either condition are discarded, which is what makes the campaign finish at all

Why it works

Non-interference is a property of two executions rather than one → it can be checked by running the observer twice and comparing → so a signal exists where a crash detector sees nothing at all.
Interference requires the sender to write kernel memory the receiver reads → profiling memory accesses identifies which program pairs could possibly interact → converting a quadratic search into a mechanical join over addresses.
Many candidate pairs exercise the same kernel path → clustering by the instructions and call stacks in the data flow and running one per group → cutting 234 million candidate cases to 1.13 million without losing any of the nine bugs.
Non-deterministic results are localised to particular fields rather than whole calls → comparing parsed result trees with per-field determinism flags → letting a timestamp be ignored while the file size beside it is still checked.
One functional interference is usually reachable through one pair of system calls → removing sender calls until the difference vanishes identifies it → collapsing 808 reports into 71 groups and about 30 hours of human work.

What it costs (trade-offs and scope)

It inherits the blind spots of its input corpus. Test programs come from an existing fuzzer, so a bug requiring a write nothing in the corpus performs is simply invisible, which the authors state plainly.
Every new bug found was in one namespace. All nine are in the network namespace despite the technique covering all eight types, so the demonstrated reach is narrower than the design.
Some interference is undetectable by construction. Of seven known bugs used as a benchmark, two cannot be caught — one because the resource is non-deterministic even without interference, one because it needs a runtime identifier passed between the programs.
The data-flow analysis misses what is not a memory access. One bug root cause is a kernel variable implemented by patching code rather than reading memory, so profiling could not see it; random pairing happened to find it instead.
It needs a human-written partial specification and heavy infrastructure. The user must say which resources are protected, refining as they go, and the campaign ran 110 virtual machines across four servers.

The evaluation

Two questions are asked. Does it find new bugs, answered by running against stable Linux 5.13 and reporting upstream. And does it find bugs known to matter, answered by collecting seven documented isolation bugs from the kernel history and security advisories, all of them originally found by humans, and checking how many the technique reproduces. Alongside these sit the numbers that decide whether the approach is usable at all: how many test cases each generation strategy produces, how many reports survive filtering, and how much human time the surviving reports consume.

Property	Crash-oriented kernel fuzzing	Targeted leak checking	Functional interference testing
What counts as a bug
Shape of the test
Coverage of the interface
Bugs of this class found
Cost of reading the output

Data-flow pairing generates 234 million candidate test cases, reduced to 1.13 million by clustering while still finding all nine bugs; random pairing over a larger budget of 8.66 million finds five. Filtering removes 14,545 of 15,353 reports as non-deterministic or outside what namespaces protect, and grouping by culprit system call pair collapses the remaining 808 into 71.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The technique is only as good as the programs it is given. Test material comes from an existing fuzzer, and the authors say directly that a bug requiring a write that no program in the corpus performs cannot be found — so this is a multiplier on fuzzing progress rather than a replacement for it. The demonstrated reach is also narrower than the design: all nine new bugs are in the network namespace, even though the approach covers all eight types. Two limits are structural rather than incidental. Of seven known bugs used as a benchmark, two are undetectable by construction, one because the resource returns non-deterministic results even without any interference and one because it requires the receiver to know an identifier the sender created at runtime. And the data-flow analysis only sees memory accesses, which it turns out is not the only way kernel state gets shared: the root cause of one bug is a variable implemented through code patching rather than memory reads, invisible to the profiler, and found only because random pairing was also being tried. Practical costs are real too — the user must supply and incrementally refine a specification of which resources are protected, the campaign occupied 110 virtual machines across four servers, and 61 reports survived all filtering as false positives, mostly device numbers that namespaces never claimed to isolate.

Background

When the property has no natural failure mode

This paper sits in the site’s security and correctness clusters and rhymes with several ideas covered elsewhere on this site. Its structural twin is the compiler consistency page, which faces the same difficulty — a property everyone relies on whose violation produces no crash — and solves it the same way, by running the system twice under conditions that should not matter and treating any difference as the bug. Its framing of the task as testing an implementation against a property nobody had written down as a testable statement rhymes with the speculation contract page, which does this for processors, and its manufactured oracle sits beside the undefined-behaviour page, where the same source compiled two ways exposes what a single run cannot. Its pruning of an unmanageable search space by reasoning about the mechanism through which the bug must occur — here a kernel memory write followed by a read — is the same necessary-condition filter the concurrency testing pages apply to interleavings. And its subject, that the isolation between co-located tenants is thinner than the abstraction suggests, is the same shared-substrate anxiety the cloud side-channel and co-location pages document from the attacker side.

If you remember only three things

1. Containers are isolated by the kernel rather than by a hypervisor, which means one shared kernel must give each container an independent view of processes, network stacks, mount points and five other resource classes. Isolation is cross-cutting rather than modular, so it is enforced by checks scattered wherever a protected resource is touched, and a developer implementing an unrelated subsystem has to remember to add them. When one is missing nothing crashes and no memory is corrupted — the system call succeeds and returns a well-formed answer describing the wrong container, which is exactly why crash-oriented kernel fuzzing cannot see these bugs.
2. The fix is to manufacture an oracle from the property itself. Non-interference is a statement about two executions, so it can be checked by running the observing container twice from an identical snapshot, once alone and once after another container has acted, and diffing the system call results. No model of correct kernel behaviour is needed anywhere. Making that practical takes two more ideas: interference requires the sender to write kernel memory the receiver reads, so profiling memory accesses turns a quadratic search over program pairs into a mechanical join, and clustering by the instructions involved cuts 234 million candidates to 1.13 million without losing a single bug.
3. The unglamorous half decides whether it is usable. Of 15,353 reports, 14,545 are noise — results that vary anyway, or resources namespaces never claimed to protect — filtered by re-running with different timings at per-field granularity and by an incrementally refined specification. The 808 survivors collapse to 71 groups by removing sender calls one at a time until the difference vanishes, leaving about 30 person-hours of human work. Nine real bugs in stable Linux 5.13, four leaking information and three enabling denial of service, and one of them sat in a function that had already been patched for a nearly identical leak.

Check yourself

Check your understanding

1. Kernel fuzzing is mature and effective, yet the paper argues it structurally cannot find these bugs. Predict the two separate reasons.
2. The oracle requires comparing two runs, but the space of program pairs is quadratic. Predict how the candidate pairs are narrowed without giving up bugs.
3. Over a million test cases produce 15,353 reports, of which 14,545 are not bugs. Predict where that noise comes from and how it is removed without discarding real findings.
4. The technique found nine bugs in a heavily scrutinised kernel subsystem. Predict what the paper reports as its most telling limitation.

Sources

Congyu Liu, Sishuai Gong and Pedro Fonseca. “KIT: Testing OS-Level Virtualization for Functional Interference Bugs.” ASPLOS 2023, Vancouver. Purdue University. DOI 10.1145/3575693.3575731.
Full text of the paper was used for this explainer, including the background on namespaces and prior testing approaches in Section 2, the functional interference testing method in Section 3, the four-stage design covering test generation, execution, detection and report aggregation in Section 4, and the new bugs, known bug reproduction, generation strategy comparison, report filtering statistics and performance measurements in Section 6.
The authors released their implementation and artifact publicly.