In this paper, we propose the Stateless Permutation of Application Memory (SPAM), a software defense that enables fine-grained data permutation for C programs. The key benefits include resilience against attacks that directly exploit software errors (i.e., spatial and temporal memory safety violations) in addition to attacks that exploit hardware vulnerabilities such as ColdBoot, RowHammer or hardware side-channels to disclose or corrupt memory using a single cohesive technique. Unlike prior work, SPAM is stateless by design making it automatically applicable to multi-threaded applications. We implement SPAM as an LLVM compiler pass with an extension to the compiler-rt runtime. We evaluate it on the C subset of the SPEC2017 benchmark suite and three realworld applications: the Nginx web server, the Duktape Javascript interpreter, and the WolfSSL cryptographic library. We further show SPAM’s scalability by running a multi-threaded benchmark suite. SPAM has greater security coverage and comparable performance overheads to state-of-the-art software techniques for memory safety on contemporary x86_64 processors. Our security evaluation confirms SPAM’s effectiveness in preventing intra/inter spatial/temporal memory violations by making the attacker success chances as low as 1/16!.