MerkleShield: Freshness-Bound Cryptographic Authorization of Executable-Memory Transitions on Multi-Tenant Cloud Hosts

Workloads on multi-tenant cloud hosts share a kernel,a hypervisor, and an operational trust boundary with code they didnot write. Code-injection attacks against such workloads must, atsome point, cause attacker-controlled bytes to become executable,which on a W^X system requires an explicit write-to-execute(W→X) permission transition. Endpoint integrity monitors thatreact to this transition today either scan memory linearly, whichscales poorly and thrashes caches, or validate asynchronously,which leaves a time-of-check-to-time-of-use (TOCTOU) windowin which the first malicious transition succeeds. This paperpresents MerkleShield, a kernel-synchronized runtime memoryintegrity subsystem for Linux. MerkleShield models the sensitiveaddress space of a monitored process as a segmented Merklehash tree whose leaf set is derived from, and bounded by, theprocess’s mapped regions, anchors that tree to an Ed25519-signed baseline root, and re-validates only the page blocks namedby a trapped transition in O(k log n) hash evaluations. Theprincipal contribution is a race-resistant authorization protocol:the kernel admits a W → X transition only against a singleuse, short-lived verdict token whose binding tuple (task identityincluding start time, mapping identity and generation, page range,content version, and verifier epoch) still equals live kernel stateat the instant of enforcement. Every mismatch, expiry, droppedevent, alias, PID reuse, or verifier silence is denied. We give theconstruction, the verification and freshness protocols, an informalsecurity argument, an analytical complexity treatment, and microbenchmarks of the user-space engines on a 4-vCPU KVM guest:re-validating one 4 KiB block in a tree of 216 leaves takes a medianof 5.8 µs, of which path recomputation grows by about 0.13 µs pertree level, as the O(log n) analysis predicts. On a live Linux 6.8kernel with BPF-LSM, running in a software-emulated (QEMUTCG) virtual machine, the deny-by-default protocol blocked 7 of9 attack vectors against a single monitored process, with no falsepositives on 2 benign vectors, identically across three passes. Allexperiments ran in virtual machines in a cloud sandbox; none ranon bare metal or a production multi-tenant host, and kernel-pathtiming and system-wide deployment remain future work.