KERAT: Static Detection of Kernel TOCTOU Bugs Caused by Races

Executive Summary

A kernel spends its life checking values before it uses them: is this pointer non-null, is this length in range, is this protocol still attached. A TOCTOU bug (CWE-367) is what happens when something changes the value after the check and before the use. Gui-Dong Han, Jia-Ju Bai, Qiu-Ji Chen and Jiqiang Lu (Beihang University) show that in Linux, the most common source of that gap is not a double-fetch from user space and not a DMA device rewriting memory. It is another kernel thread. They call those bugs KRT bugs. In a five-year patch study, 68% of TOCTOU fixes were KRT.

KERAT is the first systematic static detector aimed at that class. It mines atomicity rules — which lock must cover the check and the use of which structure field together — then walks two finite state machines over LLVM IR looking for four dangerous patterns. On Linux-6.8 and FreeBSD-14.1 it found 351 real bugs; 287 judged harmful; 65 confirmed; 10 CVE IDs; 21 patches merged covering 36 bugs. False-positive rate 18.7%. This draft keeps every figure, table and listing from the USENIX paper, then adds the kitchen-table picture of the cookie jar, the difference between a locking rule and an atomicity rule, and what a defender or an exploit developer actually does with a KRT window.

The Cookie Jar, Then Three Ways to Spoil the Check

CWE-367 is older than Linux. The kernel flavor is worse because the check is often the only thing standing between a syscall and a write into a slab object. An attacker who can arrange a safe value at check time and a hostile value at use time turns a bounds check into a buffer overflow, a null check into a crash, a protocol check into a call through a null function pointer. The paper cites three public CVEs as existence proofs: CVE-2020-25212 (NFS client), CVE-2021-29657 (KVM), CVE-2024-43882 (perm check versus set-uid/gid).

Three TOCTOU families

Figure 2 in the paper is three real Linux bugs, one of each family.

• URT (user-space race). ctl_ioctl in Linux 6.2 copies version from user space, checks it at line 1815, then copies the same user buffer again at line 1988 without a recheck. A process that mutates the buffer in between feeds the kernel an ioctl with a version the check never saw. Double-fetch literature (Wang et al., DEADLINE, LRSan) already hunts this.
• HRT (hardware / DMA). nvme_alloc_queue maps a coherent DMA buffer into nvmeq->cqes. Later nvme_handle_cqe checks command_id at line 978 and uses it as an index at 984. The device can rewrite that slot. SADA and mapped-I/O papers hunt this.
• KRT (kernel threads). ufshcd_compl_one_cqe checks hba->dev_cmd.complete for null at 5402 and calls through it at 5407. Concurrently ufshcd_wait_for_dev_cmd sets the pointer to null at 3082. Null-pointer dereference, crash. This is the family with almost no dedicated static detector — until KERAT.

Kernel race is the most common root cause of kernel TOCTOU bugs.

Han, Bai, Chen, Lu — USENIX Security 2026

What Five Years of Linux Patches Actually Fixed

The authors keyword-searched Linux patches from August 2020 to July 2025 (TOCTOU / time-of-check, double-fetch / second fetch, recheck / invalid check), then manually triaged 860 hits down to 203 real TOCTOU fixes. Table 1 is the scoreboard.

KRT bugs also live a long time: over five years on average between introduction and patch. That is the empirical case for a dedicated detector. Existing static tools miss them for structural reasons, summarized in Table 2.

The race-detector row is the subtle one. A data race is “this access is unlocked.” A KRT bug can happen with every access locked, if the check and the use sit in two different critical sections. Sequence: lock, check, unlock, lock, use, unlock. Lockset analysis is happy. The window is still there.

Challenge 1 and 2

C1: which lock should protect the check-use pair of which shared field? LR-Miner mines locking rules (which lock covers which field). That is the wrong target. C2: KRT bugs have several shapes, not one, and Linux-6.8 is 17 million lines with pointers and nested structs. Accuracy versus time is the whole game.

Figure 1 is the two-stage pipeline.

Why you cannot just retune LR-Miner

L1 — a locking rule does not imply atomicity. Figure 3 is the textbook counter-example, reproduced as published:

void atomicity_violation(struct device *dev) {
    spin_lock(&dev->lock);
    if (dev->state == STATE_A) { // Check with the lock
        spin_unlock(&dev->lock);
        ... // TOCTOU window
        spin_lock(&dev->lock);
        dev->state = STATE_C; // Use with the lock
    }
    spin_unlock(&dev->lock);
}

void locked_state_update(struct device *dev) {
    spin_lock(&dev->lock);
    dev->state = STATE_B; // Modification with the lock
    spin_unlock(&dev->lock);
}

L2 — LR-Miner’s statistic (lock coverage ≥ 0.7 and at least one write) drops fields that are often read unlocked on purpose. The mxser TTY driver reads info->xmit_cnt without the spinlock in mxser_flush_chars and mxser_chars_in_buffer for performance. Coverage falls under the threshold. The real bug in mxser_put_char — check outside the lock, increment inside — is never associated with a rule. Figure 4.

FILE: linux-5.16/drivers/tty/mxser.c
971. int mxser_put_char(struct tty_struct *tty, ...) { ......
    // Invalid check!
    if (info->xmit_cnt >= SERIAL_XMIT_SIZE - 1) return 0;
    ...... spin_lock_irqsave(&info->slock, flags);
    ......
    // TOCTOU: xmit_cnt may exceed SERIAL_XMIT_SIZE
    info->xmit_cnt++;
    spin_unlock_irqrestore(&info->slock, flags);
    ......
}
992. void mxser_flush_chars(struct tty_struct *tty) { ......
    if (!info->xmit_cnt || ...) // Read without lock protection
        return;
    ......
}
1012. unsigned int mxser_chars_in_buffer(struct tty_struct *tty) {
    struct mxser_port *info = tty->driver_data;
    return info->xmit_cnt; // Read without lock protection
}

Technique 1: Mining Atomicity Rules

An atomicity rule is: the check and the later use of a shared structure field must be covered together by a lock field. Two steps. S1: find fields that appear in conditional statements (candidate security checks), field-sensitively, with a field graph so tty->driver_data->xmit_cnt is not confused with some other xmit_cnt. S2: if every modification of that field is protected by the same lock field in the same parent struct, emit the pair.

In Figure 5, info = tty->driver_data grows an edge. The condition at line 996 marks info->xmit_cnt and tty->flow.stopped. Line 1435 marks info->board->must_hwid.

Figure 6 is the mining algorithm, reproduced as published:

AtomicityRuleMining(CPset, CFset)
Input:  CPset : set of code paths; CFset : checked fields from S1
Output: AtomicityRuleSet
1:  CandPairSet <- empty
2:  foreach code path cp in CPset do
3:      FieldGraph <- empty; LockSet <- empty
4:      foreach inst in cp do
5:          update FieldGraph and LockSet based on inst
6:          if inst is a variable-modification instruction then
7:              var <- GetModifiedVar(inst)
8:              foreach lock in LockSet do
9:                  Ancestor <- FindCommonAncestor(var, lock, FieldGraph)
10:                 if Ancestor != NULL then
11:                     APvar  <- GetAccessPath(var, Ancestor, FieldGraph)
12:                     APlock <- GetAccessPath(lock, Ancestor, FieldGraph)
13:                     if IsCheckedField(APvar, CFset) then
14:                         Insert <APvar, APlock> into CandPairSet
15:                 end if
16:             end foreach
17:         end if
18:     end foreach
19: end foreach
20: AtomicityRuleSet <- CandPairSet
21: foreach code path cp in CPset do
22:     FieldGraph <- empty; LockSet <- empty
23:     foreach inst in cp do
24:         update FieldGraph and LockSet based on inst
25:         if inst is a variable-modification instruction then
26:             var <- GetModifiedVar(inst)
27:             foreach <APv, APl> in CandPairSet do
28:                 if FieldFormMatch(var, APv, FieldGraph) then
29:                     if APl not in FieldFormMatchSet(LockSet, FieldGraph) then
30:                         Remove <APv, APl> from AtomicityRuleSet
31:                     end if
32:                 end if
33:             end foreach
34:         end if
35:     end foreach
36: end foreach
37: return AtomicityRuleSet

Figure 7: tty->hw_stopped is written under info->slock on CP1 but without it on CP2, so no rule. info->xmit_cnt is decremented/incremented under info->slock on CP3, CP4, CP5. Rule: <info.xmit_cnt, info.slock>.

Technique 2: Two Finite State Machines

Once you have a rule, you look at how lock / check / use can be ordered. Five patterns. One is safe. Four are KRT.

• SafePat1: lock, check, use, unlock. One hold.
• DanPat1: neither check nor use locked. Window is the whole gap.
• DanPat2: use locked, check not. Window is before the lock.
• DanPat3: check locked, use not. Window is after the unlock.
• DanPat4: both locked, separately. Window is between unlock and the next lock. Figure 3 is this.

FSM_KRT1 catches DanPat1 and DanPat2. FSM_KRT2 catches DanPat3 and DanPat4. States are named by the prefix already seen (A = acquire, C = check, R = release). SKRT is the sink. The authors considered merging the machines; the union would have more than ten states and they kept two trackers instead. These FSMs are not deadlock or double-lock detectors — those transitions are simply absent.

Aliases: if the lock is copied into a local and you ignore the alias, SafePat1 looks like DanPat1. If the field is copied into a local for the check, you miss DanPat1. KERAT tracks state on alias sets built from the field graph. Inter-procedural: each function gets a summary, an ordered list of <operation, access-path>; callees are instantiated at the call site instead of re-walked.

Figure 9 applies the mined pair to mxser_put_char. Operations: check, lock, use, unlock. FSM_KRT1 reaches SKRT (DanPat2). The other machine stays clean. One report.

FILE: linux-5.16/drivers/tty/mxser.c
971.int mxser_put_char(struct tty_struct *tty, ...) { ......
    // Invalid check!
979. if (info->xmit_cnt >= SERIAL_XMIT_SIZE - 1)
980.     return 0;
    ......
982. spin_lock_irqsave(&info->slock, flags);
    ......
    // TOCTOU: xmit_cnt may exceed SERIAL_XMIT_SIZE
985. info->xmit_cnt++;
986. spin_unlock_irqrestore(&info->slock, flags);
    ......
989.}

KERAT, Wired Together

About 12K lines of C++ on Clang, analyzing kernel LLVM bitcode. Phase 1 compiles and indexes functions. Phase 2 mines rules; a virtual root node is the common ancestor for globals that never travel as arguments. Phase 3 runs the FSMs, drops infeasible paths with Z3, skips probe/remove (no concurrency at bind/unbind), and deduplicates by check-use source locations.

What It Found

Targets: Linux-5.16 (known-bug regression), Linux-6.8 and FreeBSD-14.1 (then-current). Linux: allyesconfig x86-64. FreeBSD: GENERIC. Machine: 16-core Xeon 2.10 GHz, 128 GB RAM.

31.1 million lines, 49.3 thousand files, under 57 hours. 283K checked fields, 4.2K rules, 516 violated, 825 reports, 671 real after two master’s students spent 24 hours. 881 dropped by Z3 / non-concurrent functions. False-positive rate 18.7%.

Of 320 real bugs on 5.16, 76 were already gone in 6.8 (the detector finds known bugs). Of 315 on 6.8, 244 survived from 5.16 (at least two years old) and 71 are new code. 78% of bugs sit in drivers; the rest in sound, filesystems, networking. 15% have multiple calls between check and use. Use operations: 65% reads, 30% dereferences, 5% writes.

122 of 671 are judged non-security (logging, debug). 549 harmful, four buckets:

• C1 Memory corruption (167): UAF, OOB write, double-free. 72 / 86 / 9 across 5.16 / 6.8 / FreeBSD. Privilege escalation is in play.
• C2 System crash (187): null deref, division by zero. 93 / 84 / 10. Denial of service.
• C3 Undefined behavior (112): over-width shifts, signed overflow. 55 / 51 / 6.
• C4 Logic error (83): wrong kernel path. 42 / 37 / 4.

287 harmful bugs on 6.8 and FreeBSD-14.1 were reported. 65 confirmed. 21 patches landed for 36 bugs; 55 confirmed bugs have fixes. 10 CVE IDs. Some maintainers asked to keep running KERAT and to put mined rules into documentation.

False positives and negatives

154 false reports, three causes: 76 lock over-protection (developers wrap extra fields in the same lock); 40 redundant checks (kfree(NULL) is fine); 38 nested loops and non-constant array indices. Misses: wait-queues and refcounts (not locks), and atomic_* helpers.

Three confirmed case studies

• Linux SCSI (UAF): Thread 1 snapshots ctxp->rqb_buffer, null-checks it, then uses a member. Thread 2 takes the same pointer, nulls the shared field, and frees. Use-after-free, memory corruption.
• FreeBSD LAGG (crash): Thread 1 checks sc->sc_proto != PROTO_NONE, then calls lagg_proto_start. Thread 2 detaches and sets PROTO_NONE. The start path indexes lagg_protos[PROTO_NONE], a null function pointer.
• Linux HWMON (UB): Thread 1 checks data->fan_source[chan] != SOURCE_INVALID (0xff), then uses it as a shift amount on 1u. Thread 2 writes 0xff. Shift count 255 is undefined for a 32-bit int.

Against LRSan, CPALockator, LR-Miner

Linux-5.16 only: the older tools die on 6.8 and FreeBSD. Double-fetch and DMA papers were not compared (they do not look at kernel concurrency).

KERAT subsumes the KRT bugs the others happened to trip over, and finds the rest because it is looking at check-use atomicity rather than unlocked accesses or user-copy rechecks. It is slower than LRSan and LR-Miner, faster than CPALockator (which explodes on “every function is concurrent”).

Exploitability, Ethics, Artifact

The paper is explicit: given the check and use sites, an attacker can build a workload that hits the window, then turn it into a deterministic UAF or overflow. ExpRace (IPIs to widen the window) and GhostRace (speculative races) are cited as amplifiers. KERAT itself emits no PoC and no exploit. Bugs went through Linux and FreeBSD disclosure. The ethics write-up argues the benefit of forcing attention onto a 68% patch class outweighs the risk that someone reads a public patch and writes an exploit — a risk shared with every kernel CVE.

Source, binary, and instructions: https://doi.org/10.5281/zenodo.17898451. Funding: Smart Grid National S&T Major Project 2025ZD0808500 and NSFC 62572021. Acknowledgments: anonymous reviewers, shepherd, kernel developers, Julia Lawall.

A Longer Walk Through the Field Graph

The paper’s field graph is easy to skip if you have never stared at Linux structs. It is the reason KERAT can tell tty->driver_data->xmit_cnt from a similarly named counter on another object. A node is a field. An edge is labeled with the C member used to walk from a parent to a child. As the analyzer walks a path, the graph grows. When a condition is hit, the operands are resolved against the graph as it exists at that program point, not against a global points-to dump that pretends every assignment happened.

That last clause matters. Kernel code reuses locals. info is tty->driver_data in one function and something else after a reassignment. A flow-insensitive alias analysis would merge them and either invent a fake atomicity rule or drop a real one. KERAT rebuilds the graph along each path, the same way a human reading the function rebuilds the mental map.

Globals that never appear as arguments get a virtual root. Without that hack, a file-scope mutex and a file-scope table have no common ancestor, and the miner refuses to pair them. With it, they look like siblings under a synthetic parent, which is honest enough for “these two live in the same compilation unit and are clearly meant to travel together.”

FSM Transitions, Written Out

The paper compresses the machines into Table 3. Here is the same information as state sequences, because that is how you debug a report.

FSM_KRT1 (unlocked check). Alphabet: lock, unlock, check, use. States: S0, SA (lock held, no check yet), SC (check happened without lock), SC-A (lock acquired after an unlocked check), SKRT.

• DanPat1: S0 –check–> SC –use–> SKRT. Nobody held the lock.
• DanPat2: S0 –check–> SC –lock–> SC-A –use–> SKRT. The use is locked; the check was not. mxser_put_char is this.
• SafePat1 on this machine: S0 –lock–> SA –check–> SA –use–> SA –unlock–> S0. Never SKRT.

FSM_KRT2 (locked check, then trouble). States: S0, SA, SA-C (checked while holding), SA-C-R (unlocked after that), SA-C-R-A (re-locked), SKRT.

• DanPat3: S0 –lock–> SA –check–> SA-C –unlock–> SA-C-R –use–> SKRT. Use after drop.
• DanPat4: S0 –lock–> SA –check–> SA-C –unlock–> SA-C-R –lock–> SA-C-R-A –use–> SKRT. Figure 3. Two critical sections, one pair.

The machines ignore double-lock and missing-unlock on purpose. Adding those transitions would turn KERAT into a lockdep clone and explode the state count. The authors say a unified machine would exceed ten states and dozens of edges; they kept two walkers on the same path instead.

What “Harmful” Means in a Kernel Report

The 122 bugs marked non-security are not false. They are real atomicity violations on fields used for printk, debugfs, or statistics. A racy debug counter is still a KRT bug; it is not a CVE. The 549 harmful ones are the ones where the field is an index, a pointer that is freed, a shift count, a protocol id, or a length that gates a copy.

C1 (memory corruption) is the exploit developer’s row. If the use is a kfree, a queue index, or a memcpy length, the window is a UAF or OOB. Linux SCSI in Figure 12(a) is the textbook: snapshot a buffer pointer, lose the race to a free, touch a member. That is a classic write-what-where once you control the slab reuse, which ExpRace-style interrupt storms make less random.

C2 (crash) is DoS, sometimes more. A null function pointer in LAGG is a panic. On a production router that is an outage. On a shared host it is a guest-to-host noise source. C3 (undefined behavior) is the one compilers will weaponize: a shift of 255 on a 32-bit 1u is UB, so the optimizer may delete the later path or assume the source was never 0xff, which is how a “just a warning” becomes a logic bug. C4 (logic error) is the rest: wrong branch, skipped teardown, interface left in a state the rest of the driver does not expect.

How an Attacker Turns a KERAT Report into a Primitive

Section 7 is short and honest. KERAT names the check, the use, and the lock. It does not give you a syscall sequence. The remaining work, which the authors list as future work, is constructing a workload that (1) runs the check path, (2) runs the writer on another CPU, (3) hits the use. For drivers that is often: open the device, start I/O, close or reconfigure from another thread. For filesystems: two threads on the same inode. For net: a reconfiguration ioctl racing datapath.

ExpRace (Lee, Min, Lee, USENIX Security 2021) shows you can widen a kernel race window by raising interrupts on the victim CPU so the check-to-use gap lasts milliseconds instead of nanoseconds. GhostRace (Ragab et al., USENIX Security 2024) shows speculative execution can leak or act on the torn state even when the architectural window is tiny. Neither paper is KERAT; both are why a “hard to hit” KRT bug is still a security bug.

The authors refuse to ship PoCs. That is the right default. If you are in an authorized kernel hardening engagement, the report plus the two source locations plus a pair of kprobes on check and use is usually enough to see the window on a debug kernel. Do not publish that trace.

Related Work, Without the Citation Fog

Userland TOCTOU is a different animal: file-system TOCTTOU (Wei and Pu, Lhee and Chapin, Payer and Gross), SGX AsyncShock and EnclaveFuzz, compiler-introduced double-fetches (WarpAttack). Those tools assume POSIX files or enclave entry. They do not see spinlocks or DMA.

Kernel double-fetch (Wang et al. USENIX 2017, DEADLINE / Xu et al. IEEE S&P 2018) and lacking-recheck (LRSan, CCS 2018) watch copy_from_user. SafeFetch (Duta et al., USENIX 2024) is a defense: cache the kernel fetch. SADA (Bai et al., USENIX 2021) and Lu et al. JCST 2018 watch DMA and MMIO. All of that is URT/HRT. The 68% slice is elsewhere.

Dynamic kernel race finding: Razzer, KRACE, Snowcat, KCSAN, context-sensitive concurrency fuzzing (Jiang et al. NDSS 2022). High precision on paths they hit; blind on drivers that never run in the harness. Static race finding: RacerX, RELAY, CPALockator, LR-Miner. Deadlocks: DLOS, interrupt-based deadlock work (Ye, Cai, Zhang, USENIX 2024). Concurrency UAF: Bai et al. ATC 2019, Zhang et al. NDSS 2025. Multi-variable correlations: MUVI (SOSP 2007). Atomicity violations as a class: AVIO (Lu et al. 2006) in userland. None of those tools’ predicates is “check and use of the same shared field must be one critical section.”

IoT remote-attestation TOCTOU (ZKSA, AutoCert) is a protocol problem, not a kernel one. True IOMMU / DMA injection (Markuze et al.) is the hardware analog of HRT. The paper’s claim is narrower than “we invented TOCTOU analysis.” It is: we are the first systematic static tool whose bug class is KRT.

Limitations You Should Budget For

• Wait queues, completions, and refcounts are synchronization. KERAT only believes locks. A field whose writer uses wait_event will not get a rule, and the matching KRT is a false negative.
• atomic_set / atomic_inc are modifications. If the analyzer does not model those helpers, atomic fields are invisible.
• Lock over-protection (one spinlock covering a whole struct because the author was unsure) mints extra rules and extra reports. 76 of 154 FPs.
• kfree(NULL) after a racy null check is not a bug. 40 FPs. Teach the checker libc/kernel freeing semantics.
• Non-constant indices and nested loops: 38 FPs. Array elements are not fields in the graph.
• allyesconfig still leaves files out. GENERIC on FreeBSD leaves more out. More configs, more bugs, more time.
• No automatic PoC. Security impact of a given report is still a human reading the use site.
• Future work they want: fewer FPs, more primitives, auto syscall PoCs, auto patches that take the mined lock without introducing deadlocks, LLM triage of reports.

Open Science and Who Was in the Room

Artifact: source, binary, usage, DOI 10.5281/zenodo.17898451. Analysis is offline on public trees. No live systems, no testcases against production, no exploit code. Reports went through Linux and FreeBSD’s own disclosure. Companies and end users were not contacted; they get the fixes from stable. The ethics appendix argues residual harm is the same as any public kernel patch, mitigated by not shipping PoCs. The decision paragraph is unusually blunt: unfixed bugs remain, developers acknowledged them, the authors help with patches, publishing will make maintainers look at KRT harder, therefore submit.

Stakeholders listed: Linux and FreeBSD communities, vendors, end users, the research team. Julia Lawall is thanked for revision. Shepherd and reviewers too. Grants: Smart Grid National Science and Technology Major Project 2025ZD0808500; NSFC 62572021.

Operator Playbook: After You Clone the Artifact

The paper is not a user manual. The Zenodo tarball is. In spirit, the pipeline is: build the kernel with Clang to LLVM bitcode (the same way LR-Miner and many other Beihang/Tsinghua kernel static papers do), run the rule miner, run the bug detector, then triage. Practical notes the paper implies but does not spell out:

1. Start with a single driver directory, not allyesconfig, until you trust the reports. mxser is the running example; it should reproduce Figure 4/9 if the bitcode includes drivers/tty/mxser.c.
2. For each report, open the check line and the use line. If they are printk, close the tab. If they are a pointer deref or an index, keep going.
3. Ask whether a writer exists that can run concurrently. probe/remove were already filtered. Init-only stores are usually safe. Datapath versus ioctl reconfigure is the usual yes.
4. Confirm the lock on the write side is the mined lock. If writers use a different lock, you have either a false rule or a second bug.
5. Patch shape A: extend the critical section over the use. Patch shape B: re-read and re-check after re-lock. Patch shape C: copy the field to a local under the lock and only use the local. C is often the one that does not deadlock.
6. Run lockdep and the driver’s selftests after the patch. KERAT does not prove deadlock freedom.
7. If you are defending a fleet, grep for the pattern check-unlock-use on pointer fields in out-of-tree drivers. Those never saw Linux review and will not see KERAT unless you run it.

// Patch shape C, sketch only — not from the paper
spin_lock_irqsave(&info->slock, flags);
cnt = info->xmit_cnt;
if (cnt >= SERIAL_XMIT_SIZE - 1) {
    spin_unlock_irqrestore(&info->slock, flags);
    return 0;
}
info->xmit_buf[info->xmit_head++] = ch;
info->xmit_cnt = cnt + 1;
spin_unlock_irqrestore(&info->slock, flags);

That sketch is ours, not Han et al. The paper does not publish a canonical mxser patch. The point is: snapshot under the lock, or hold the lock. Do not check, drop, then mutate.

Why Drivers, Why Five Years, Why Static

78% of the real bugs are in drivers because drivers are where shared device state lives: rings, completion pointers, PHY config, fan sources, protocol attachments. Core kernel code has more review and more lockdep coverage. Out-of-tree and under-reviewed in-tree drivers are where a completion pointer is checked in the IRQ path and cleared in the timeout path.

Five-year average lifetime is the other number to remember. KCSAN and fuzzing need the device, the schedule, and the stars to align. A static miner needs the .c file. That is why 244 of the Linux-6.8 bugs were already in 5.16: the code sat there through two years of syzkaller and nobody happened to hit the window. KERAT does not happen to hit. It enumerates.

Static analysis on 17 million lines in 29 hours on a workstation is the engineering claim. Function summaries are the reason it is not 29 weeks. The cost is precision at call sites that pass function pointers or that recurse. The paper does not quantify recursion; it quantifies dropped infeasible paths (881) and remaining FPs (154). That is a usable tool, not a verified kernel.

Reading KERAT Next to Part 1 of Your Own Notes

If you arrived from userspace race hunting or from LDAP enumeration, the vocabulary shift is: the shared variable is a struct field, the lock is another field of the same object, the attacker is often just another syscall on another core, and the “filter” is an FSM over LLVM. The kitchen picture does not change. Look, gap, use. Close the gap or stop trusting the look.

How the Patch Study Was Built (and Why 68% Is Not a Vibes Number)

Linux produced more than 300,000 patches in the five-year window. Nobody reads that. The authors grepped three keyword buckets, then sat down with 860 patches. The TOCTOU bucket was small and clean: 55 hits, 46 real, 9 were people talking about defenses rather than shipping a fix. The double-fetch bucket was tiny and perfect: 10 hits, 10 real. The invalid-check / recheck bucket was a swamp: 795 hits, 147 real, 648 unrelated (a lot of “this check is wrong” is just a logic bug with no race). 46+10+147=203. Classification into URT/HRT/KRT was by the source of the race, not by the commit message. That is why KRT is 138 and not whatever git log –grep=race would claim.

Lifetime: they dated introduction versus patch for the KRT subset and got a mean over five years. That number is the argument against “syzkaller would have found these.” Some of them syzkaller did find, eventually. The mean says eventually is not a strategy.

Table 1’s invalid-check column is dominated by KRT (113 of 147). Maintainers describe KRT as “the check is invalid” more often than they type TOCTOU. If you only grep TOCTOU you will think the class is rare. If you grep invalid check and then read, you will think the class is most of the pile. The paper did the second thing.

Compilation, Summaries, Z3, and What Gets Thrown Away

Phase 1 is Clang emitting LLVM bitcode per .c, then a function database of names and body locations. That database is how inter-procedural analysis finds callees without re-parsing the world. Phase 2 walks paths, not the whole CFG at once: field graph and lockset are per path. A modification instruction is the event that proposes or kills a candidate pair. Phase 3 instantiates two FSMs per mined pair and walks the same style of path, consulting summaries at calls.

A summary is an ordered list of (lock|unlock|check|use, access path). Instantiation substitutes actual arguments. Function pointers and recursion are the usual static-analysis holes; the paper does not claim to close them. Z3 is applied to drop reports whose path is contradictory (the classic “this check and that use cannot happen together because of an earlier return”). probe and remove in the function name are skipped because device bind/unbind is not concurrent with itself in the way datapath is. Dedup is by source location of the check-use pair, so the same bug found on ten paths is one row.

881 reports died in that filter before a human saw them. That is why the raw FSM hits are not the 825 number. 825 is after automated dropping. 671 is after two students. 154 remaining FPs are the three buckets already named. If you rerun KERAT, budget a day of humans per kernel, not a week, because the automated drop already did the infeasible-path work.

Linux-5.16 versus 6.8, in sentences

320 real on 5.16, 315 on 6.8. 76 of the 5.16 set were gone by 6.8: KERAT can find bugs the kernel already knew about, which is the sanity check. 244 of the 6.8 set were already in 5.16: KERAT can find bugs the kernel did not know about for two years. 71 of the 6.8 set are new code: KERAT can find bugs in code that has not had years to rot. Those three sentences are the evaluation. The rest is tables.

FreeBSD-14.1 is the portability check. GENERIC, not allyesconfig, 4.2K of 19.9K files, 36 real bugs, same miner. The field-graph and lockset machinery is not Linux-spinlock-specific in the abstract; it has to recognize FreeBSD’s mtx/sx or it would have found zero rules. 0.4K rules versus 1.9K on Linux is the config and the smaller tree, not a different theory.

Comparison Experiment, Unpacked

LRSan was built from kengiter/lrsan. It wants old kernels; 6.8 fatal-errors. 3,652 lacking-recheck reports. The authors sampled 300, found 3 real, 0 KRT. That is not a dunk on LRSan. LRSan is a user-copy tool. Asking it for KRT is asking a DMA paper for filesystem races.

CPALockator lives in CPAchecker as a data-race CPA. Thread-modular analysis with projections. 773 reports, 23 real races, 5 of which happen to be KRT because the racy variable was also read in a check. 132 hours. The assumption that functions are concurrent is the state explosion. KERAT does not assume that; it only cares about pairs that have a write-side lock rule, which prunes the world.

LR-Miner is the sibling. Same group, locking rules, statistical threshold 0.7. 373 reports, 257 real races, 12 KRT. Artifact on a Google Site. It is the closest tool and still not a KRT tool, because of Figure 3 and Figure 4. KERAT finds those 12 plus 308 more on 5.16. Time 17h versus KERAT 21h: you pay four hours for the atomicity predicate and the FSMs.

Double-fetch detectors (Wang, DEADLINE) and DMA validators (SADA, mapped I/O) were excluded from the bake-off because they do not inspect kernel concurrency at all. Including them would have been a table of zeros in the KRT column.

CWE-367, CVEs the Paper Names, and CVEs It Does Not

• CWE-367 is the parent: time-of-check time-of-use. The paper’s contribution is a subclass (KRT) and a detector.
• CVE-2020-25212: NFS client TOCTOU mismatch. Named as prior art, not a KERAT find.
• CVE-2021-29657: KVM TOCTOU. Same.
• CVE-2024-43882: permission check versus set-uid/gid use. Same.
• Ten new CVE IDs for KERAT bugs: assigned, not listed in the PDF. Follow the authors’ kernel mailing-list threads and lore.kernel.org for the actual numbers as embargo lifts.
• dm-ioctl double-fetch of version (commit 249bed821b4d) is Figure 2(a).
• nvme CQE double-fetch (commit 62df80165d7f) is Figure 2(b).
• UFS device-command race (commit 20b97acc4caf) is Figure 2(c).

Those three commits are the motivating examples. They are also a lesson in how maintainers name things: “avoid possible double-fetch” on a DMA completion is HRT language; “fix a race condition related to the device commands” is KRT language. KERAT is for the second sentence.

What to Tell a Maintainer in the First Email

The authors got 65 confirmations and 21 merged patches. The email shape that works, inferred from how kernel people talk, is: here is the check line, here is the use line, here is the writer, here is the lock that already protects the write, here is why unlocking between check and use is DanPat3/4, here is a patch that snapshots or extends. Do not lead with FSM_KRT2. Do not attach 392 reports. One bug, one writer, one suggested patch, then ask if they want the rest as a series.

Static Analysis of Kernels, in One Kitchen Paragraph

Coverity, Smatch, SLAM2, UBITect, MLEE, SPATA, Pinpoint, DLOS: the kernel has been statically analyzed to death for leaks, uninit, deadlocks, UAF. Concurrency static analysis either says “this access is unlocked” (races) or “this lock is taken twice” (deadlocks). Atomicity of a pair is a third predicate. AVIO did it dynamically for user programs in 2006. KERAT does it statically for kernel structs in 2026. Twenty years and a different code base, same idea: some bugs are not about a single memory operation. They are about two operations that were supposed to be one story.

If you only remember one contrast from the paper, remember this: lockdep and KCSAN will not save you from DanPat4. Every access is locked. The pair is not. That is why a new miner existed.

Key Takeaways

• Most kernel TOCTOU is not double-fetch. It is another thread. 68% of a five-year Linux sample.
• A lock around every access can still leave a TOCTOU window. Atomicity is about the pair, not the load.
• Statistical lock coverage throws away fields that are read unlocked on purpose. Mine on writes.
• Four dangerous patterns, two small FSMs, field-graph aliases, function summaries, Z3 for path junk.
• 671 real bugs; 549 harmful; drivers dominate; 10 CVEs; artifact on Zenodo.
• ExpRace-class tricks exist to make the window wide. Finding the pair is the first half of the exploit and of the patch.

Defensive Recommendations

1. Treat check-use on shared fields as a lock-documentation problem. If KERAT (or review) says <field, lock>, put that in the comment above the struct and in the driver’s locking.rst.
2. Do not split a null-check and a dereference across an unlock. That is DanPat4, and it is how ufshcd and LAGG die.
3. DMA completion queues are HRT, not KRT — copy the CQE out of the coherent buffer before you trust command_id.
4. Double-fetch remains real for ioctl structs. One copy_from_user into a kernel-private snapshot, then check and use that.
5. KCSAN + lockdep + KERAT cover different slices. Dynamic tools miss cold driver paths; KERAT misses wait-queues and atomics. Run both.
6. Patch KRT with re-check after re-lock, or with a snapshot. Blindly extending the critical section is how you get sleeping-while-atomic and deadlocks.
7. Prioritize driver bugs that free or index from the raced field. Those are C1/C2. Log-only races can wait.
8. Disclose like the authors did: no public PoC until the stable trees have the fix. The paper already named the pattern.

Conclusion

Han, Bai, Chen and Lu measured the kernel’s TOCTOU debt and found it was mostly concurrency, then built a static miner that asks a more precise question than race detectors: not “is this load locked?” but “is this check still true when we use the value?” KERAT’s 351 real bugs on current Linux and FreeBSD, the ten CVEs, and the maintainers who asked for the rules in the docs are the argument that the question was the right one. The cookie jar is still open whenever a driver unlocks between looking and biting. The paper, and the artifact, are how you find those jars without waiting five years for a patch.

Original text: “Static Detection of TOCTOU Bugs Caused by Kernel Races” by Gui-Dong Han, Jia-Ju Bai, Qiu-Ji Chen, and Jiqiang Lu at 35th USENIX Security Symposium.