Exploiting Unix File-System Races via Algorithmic Complexity Attacks

The paper that made a filesystem race arbitrarily slow — and so defeated the best probabilistic defense of its day, plus a kernel race detector, with one technique.

Kind	Paper (attack)
Year	2009
Authors	Xiang Cai, Yuwei Gui, Rob Johnson (Stony Brook University)
Venue	30th IEEE Symposium on Security and Privacy (S&P / Oakland 2009)
Systems	Linux 2.6.24, FreeBSD 7.0, OpenSolaris 5.11, OpenBSD 3.4
Primitive	Algorithmic-complexity attack on the kernel name-cache hash table
Dimension 2	Attack: makes each of the victim's path lookups O(ℓ), so the attacker wins every race
Source read	cai09-mazes.pdf (15pp.); canonical DOI 10.1109/SP.2009.10

Overview

What it solves

Again, an attack. Its two targets are the strongest probabilistic file-race defenses of 2004–2008: atomic k-race (Tsafrir et al., best-paper FAST 2008, building on Dean & Hu's k-race — see tsafrir-2008 and dean-hu-2004-borisov-2005) and the TY-Race kernel detector (Tsyrklevich & Yee, 2003). The abstract states the conclusion up front (p.1):

We defeat two proposed Unix file-system race condition defense mechanisms. […] We conclude that programmers should use provably-secure methods for avoiding race conditions when accessing the file-system.

The classic vulnerability under all of this is the access(2)/open(2) pattern (p.1-2): a setuid-root program calls access(path, R_OK) to check its invoker's rights, then open(path) — and an attacker who swaps path (via unlink+link/symlink) between the two calls redirects the open to a file the invoker could not read.

Design philosophy

Where an earlier maze attack (Borisov et al.) beat plain k-race by forcing the victim to sleep on I/O, atomic k-race's lstat(2) calls refuse to follow symlinks and so avoid that I/O — closing the maze. Cai et al.'s insight is to slow the victim down a different way, one that needs no I/O at all: an algorithmic-complexity attack on the kernel's in-memory name cache. Make every path lookup take milliseconds, and the attacker has all the time it needs to win each race deterministically.

The strategic argument (p.13) is the paper's real payload:

Probabilistic race defenses are brittle because they make so many unspecified assumptions about the underlying OS. By leaving a non-zero chance that the attacker can win races against the victim, probabilistic schemes pull the performance characteristics of the OS and hardware into the trusted computing base.

How it works

Every Unix kernel the authors examined caches recently-resolved names in a hash table with a hard-coded hash function, and looks up a name by walking the collision chain in its bucket (p.10):

procedure name-lookup(name)
  h := hash(name)
  listnode := C[h]
  while listnode != nil
      if listnode.name = name
          return listnode.inode
      listnode := listnode.next
  return nil

If an attacker finds ℓ filenames f₁ … f_ℓ that all hash to the same bucket, creating them puts the whole set on one linked list. A lookup of f_ℓ at the tail then walks the entire chain — O(ℓ) — and if the names share a long common prefix (> 240 chars), each node comparison scans the prefix too, so the walk is slower still. The attacker makes f_ℓ a hard link to the target file; the victim runs against f_ℓ, so only that one name needs to be slow.

Colliding names are generated with a birthday attack on each OS's hash function (Appendix gives the exact hash for Linux 2.6.28, FreeBSD 7.0, OpenSolaris 5.11, OpenBSD 3.4) — tens of thousands of collisions in seconds, versus half an hour for the generic Crosby attack. Measured effect (Table 2): an lstat(2) that costs ~6 µs normally is stretched to ~3120 µs on Linux, ~11100 µs on one OpenBSD config.

Slowing the victim is only half the exploit. To wake up inside the victim's now-slow syscall, the paper adds three scheduler tools:

• Clock-syncing — call nanosleep(2) twice so the second sleep begins right after a clock tick, yielding a reliable sub-tick sleep.
• Priority laundering — launch the victim from a child that nice(2)s itself down; the main attacker sleeps and so looks I/O-bound, earning a scheduler priority boost the victim doesn't get (p.11-12).
• Sleep-walking — a shared-memory flag lets the attacker call nanosleep and wake the victim (kill) "nearly simultaneously," so it can prepare the next race while asleep (Fig. 11).
• Fast file switching — pre-create directories of hard links t₁ … t_m to each possible target, so switching f_ℓ costs a single rename(2) instead of unlink+link (p.12-13), fast enough on OpenBSD to skip SIGSTOP/SIGCONT entirely.

Results (Table 3): atomic k-race broken at the recommended k = 9 with success ≥ 0.5 on all four OSes (1.00 on OpenSolaris), and still broken at k = 20 — raising k is no defense. Against TY-Race, pausing 5 s between SIGSTOP and the swap evades the detector's ~2-3 s table flush; "TY-Race had no appreciable impact on our success rate" (p.13).

Dimension 1 — Threat model

An unprivileged local user racing a privileged (setuid-root) victim, or on OpenBSD any privileged program including servers (no SIGSTOP needed there). Attack vehicles: symlink/hard-link swap of a path component, plus the name-cache complexity attack as the timing amplifier. The paper generalizes: the technique "work[s] on any name-based Unix system call, e.g. stat(2), chdir(2), chmod(2)" and even on lookups of non-existent names, so it applies to temp-file-creation races too (p.1, p.13). Uni- and multi-processor both covered (MP via sched_setaffinity binding).

Dimension 2 — Resolution primitive (the defense/attack mechanism and its atomicity claim)

The defense being broken, atomic k-race, resolves the path in user space, one atom at a time, and re-runs the lstat/access/open/fstat sequence k times per atom (atom_race, Fig. 5), verifying each time that it sees the same file. Its atomicity claim is probabilistic: if the attacker wins each race with probability p, the nominal success bound is p^(2k+2). The paper's first observation is that this is already overstated — k+1 of the races are "already known to be easy," so the real security is p^(k+1) (p.3). The complexity attack then drives p to ~1, collapsing the exponent to irrelevance. No amount of k helps once each race is deterministically winnable — which is precisely why the survey's constructive answers move to deterministic primitives (chari-2010, linux-openat2).

Dimension 3 — Symlink and .. policy

atomic k-race's own policy is to refuse to follow symlinks during an atom's check (its is_symlink/lstat step is what closed the original maze), resolving each symlink by recursion instead. The attack does not need symlinks at all in its final form — it uses hard links (link/rename) to repoint f_ℓ, because a hard link changes the file a name resolves to without a symlink the lstat check would catch. .. is not a lever here.

Dimension 4 — Boundaries

Not addressed — no mounts, procfs, or magic links. The boundary this paper attacks is time: the scheduler quantum and clock resolution. Its one forward-looking boundary observation is that new OS features widen the attack surface: Linux inotify lets a watching process run "as soon as the open completes but before control is returned to the original process," handing the attacker fine control over scheduling of open/read/write/rename (p.13) — the concrete evidence that probabilistic defenses "interact poorly with new OS features."

Dimension 5 — Portability and fallback

The attack itself is portable across four kernels (with per-OS hash functions and small scheduling tweaks). The lesson for defenders is the inverse: the authors note the algorithmic-complexity holes could be fixed (replace hash tables with balanced binary trees), but "every OS we tested is vulnerable," fixing them "would require a huge, coordinated effort among OS vendors," and even then other complexity bugs (OpenBSD has two) or features like inotify keep the attack alive (p.1, p.13). Hence: "fix the Unix system call interface to enable race-free file-system access."

Dimension 6 — Failure and partiality

The victim never sees a failure — it opens the wrong file believing its checks held. Against the TY-Race detector, the attack's success is measured by non-detection: the detector's state table must forget entries to bound memory, and any table-eviction policy (TY-Race's 2-3 s timeout, or LRU) leaves a window the attacker's arbitrary-length pause exploits. The paper's general theorem (p.1): every kernel dynamic race detector must have side information about the programs it protects, protect only a subset, be DoS-vulnerable, have false positives, or miss some exploits — a state-management impossibility.

Dimension 7 — Enumeration and deletion

Does not apply, because the paper targets single check/use pairs, not tree enumeration or deletion. Its transferable warning for a remove_dir_all-style walker is the timing one: an attacker can make any single openat/lstat in a walk take milliseconds on demand, so a walker that assumes lookups are fast (and therefore that a race window is negligibly small) is assuming something the attacker controls.

Strengths

• Deterministic where the defense was probabilistic. Turns p ≈ 1, so the security parameter k becomes meaningless — a qualitative, not incremental, break.
• Two defenses, one technique. Same tools break atomic k-race and TY-Race, and the accompanying impossibility argument generalizes to all kernel dynamic detectors.
• Reusable primitives. Clock-syncing, priority laundering, sleep-walking and fast file switching are independently useful for exploiting Unix races.

Weaknesses

• Setup cost. init-hash-table runs in O(ℓ²) (each insertion scans the cache), taking minutes; the attack "takes several hours to execute" in some configurations (footnote, p.10).
• Randomized atomic k-race still open. The attack does not pause the victim mid-syscall, so it does not directly extend to a randomized-busy-wait variant (p.13) — though the authors decline to recommend that variant either.

Key design decisions and trade-offs

Decision	Rationale	Trade-off
Slow the victim via name-cache collisions, not I/O	Sidesteps atomic k-race's symlink-refusing lstat (which killed mazes)	Costly O(ℓ²) setup; per-OS hash reverse-engineering
Use hard links (rename) to repoint the target, not symlinks	A hard-link swap evades the defense's lstat-based symlink check	Needs the target and links on one filesystem
Argue impossibility for all kernel dynamic detectors	Elevates two concrete breaks into a class result (state management)	The proof leaves narrow escapes (per-process tables, side information)

Sources

• cai09-mazes.pdf — the paper: the access/open race and atomic k-race routines (Figs. 1-5, p.1-3), the name-cache complexity attack (§5.1, p.9-10), scheduler tools (§5.2, p.11-13), results against atomic k-race and TY-Race (Table 3, p.13), and the brittleness argument for probabilistic defenses (§7, p.13).