Gaussian Elimination of Side-Channels: Linear Algebra for Memory Coloring

Memory coloring is a software-based technique to ensure microarchitectural isolation between trust domains sharing a CPU. Prior coloring schemes target individual microarchitectural components and thus provide only partial solutions. In this paper, we provide theoretical foundations and practical algorithms to infer comprehensive coloring schemes for modern cloud CPUs. To this end, we first formulate the requirements for effective memory coloring schemes in a set-theoretic model, including definitions for simultaneous isolation of shared components and uniform utilization of private components. We then algebraically characterize these requirements for microarchitectural components that are indexed by linear functions, which is the prevalent case in today's CPUs. Based on this, we develop efficient algorithms for computing multi-resource coloring schemes from linear indexing functions, and for reverse-engineering unknown linear indexing functions under minimal assumptions. In a case study, we use our algorithms to compute coloring schemes for recent Intel CPUs, and we show how to design indexing functions that maximize the number of supported trust domains. CCS Concepts • Security and privacy → Formal security models; Side-channel analysis and countermeasures; Hardware reverse engineering.