ε-Indistinguishability In Moving Target Defense: Framework, Algorithms, And Cloud Case Studies
Provides a framework and diagnostic for designing effective Moving Target Defense systems by quantifying the anonymity provided by configuration pools.
The paper formalizes the pool-safety problem in Moving Target Defense as finding the largest ε-close subset of configurations, proposes four algorithms for different scales, and demonstrates through cloud case studies that latency differences among component variants determine effective anonymity, with a four-runtime serverless rotation collapsing to three-way anonymity and a 27-configuration stack achieving nine-way anonymity.
Moving Target Defense (MTD) assumes its pool of candidate configurations is safe to cycle among, i.e. latency and other observables do not trivially fingerprint the active choice, but this assumption has not been quantified at the pool level. We formalize this pool-safety problem as finding the largest $\varepsilon$-close subset of the Cartesian product of per-component implementation choices, reducing pairwise indistinguishability under an additive utility model to a densest-window query over a sum-set. We give four algorithms spanning the scalability spectrum -- full enumeration, meet-in-the-middle, FFT convolution, and Monte Carlo sampling -- covering configuration spaces from tens to $10^{38}$. We then measure the anonymity gap end-to-end on two production cloud case studies, and find that a component's latency differences do not survive deployment unchanged: a four-runtime serverless rotation, where nothing else masks the interpreter, collapses from four-way to three-way anonymity against a VPC-adjacent adversary, while a $27$-configuration three-tier stack, where the same interpreter differences are instead absorbed by a shared $8$~ms database round-trip, delivers nine-way effective anonymity. The framework and the two case studies together suggest a diagnostic for MTD design: rotating a component adds anonymity only if the latency differences among its variants are too small for the adversary to identify.