From Verification to Herding: Exploiting Software's Sparsity of Influence
New 'herding' approach achieves 90% of peak testing results with just 32 samples, replacing heavy solvers.
A new research paper from Tim Menzies and Kishan Kumar Ganguly challenges the costly status quo of software verification, which can consume over half of a project's effort. They propose moving from exhaustive verification and modeling to a concept called 'herding'—treating testing as a model-free search task that steers complex systems toward desired goals. This approach is built on the 'Sparsity of Influence' principle, the observation that vast software state spaces are often governed by just a handful of critical variables.
To operationalize this, the researchers introduce EZR (Efficient Zero-knowledge Ranker), a stochastic learning algorithm designed to identify these controlling variables directly. In experiments across dozens of tasks, EZR demonstrated remarkable efficiency, achieving 90% of peak verification results using a mere 32 samples. This performance allows it to replace computationally heavy formal solvers with lightweight, intelligent sampling, potentially slashing verification time and resource requirements for modern, complex software systems where traditional methods fail.
- Proposes 'herding' as a model-free alternative to costly verification, which currently takes >50% of project effort.
- Introduces the EZR (Efficient Zero-knowledge Ranker) tool, a stochastic learner that finds system-controlling variables.
- Achieved 90% of peak testing results with only 32 samples, replacing heavy solvers with efficient sampling.
Why It Matters
Could drastically reduce the time and cost of validating complex software, accelerating development cycles for critical systems.