Abstract

Large-scale systems rely on heuristics to tackle NP-hard problems such as traffic engineering, virtual machine placement, and packet scheduling. While these heuristics are efficient, they can exhibit severe performance gaps under certain workloads, leading to outages or costly over-provisioning. This risk has motivated tools that attempt to identify inputs causing worst-case underperformance. However, using these tools in practice often requires rewriting heuristics as formal mathematical models—a process that is time-consuming, error-prone, and excludes many real-world algorithms.

We introduce “MetaEase”, a practical general-domain analyzer that works by directly analyzing a heuristic’s source code, eliminating the need for formal modeling. MetaEase combines code-aware input generation with guided search to uncover worst-case scenarios efficiently, even for heuristics with randomness (e.g., various traffic engineering schemes) or non-convex behavior (e.g., bin packing for virtual machine placement).

Across five problem domains and eight heuristics, MetaEase matched or exceeded MetaOpt, a state-of-the-art optimization-based heuristic analyzer, in most cases; in the remainder, it achieved at least $85–98\%$ of its performance and often ran faster. Against black-box optimization baselines, it won in $88\%$ of settings and ranked in the top two otherwise. MetaEase analyzed Arrow, a widely studied networking heuristic, which cannot be analyzed by any of the state-of-the-art heuristic analyzers. We revealed previously unknown performance gaps in Arrow.

BibTeX Citation

Coming soon!