From Verification to Herding: Exploiting Software's Sparsity of Influence
This addresses the problem of costly software verification for developers, presenting a novel paradigm rather than an incremental improvement.
The paper tackles the high cost of software verification by shifting from verification to herding, a model-free search approach that exploits sparsity of influence in software systems. It introduces EZR, a stochastic learner that achieved 90% of peak results with only 32 samples across dozens of tasks, replacing heavy solvers with light sampling.
Software verification is now costly, taking over half the project effort while failing on modern complex systems. We hence propose a shift from verification and modeling to herding: treating testing as a model-free search task that steers systems toward target goals. This exploits the "Sparsity of Influence" -the fact that, often, large software state spaces are ruled by just a few variables, We introduce EZR (Efficient Zero-knowledge Ranker), a stochastic learner that finds these controllers directly. Across dozens of tasks, EZR achieved 90% of peak results with only 32 samples, replacing heavy solvers with light sampling.