Finding Adversarial Inputs for Heuristics using Multi-level Optimization


Pooria Namyar, Microsoft and University of Southern California; Behnaz Arzani and Ryan Beckett, Microsoft; Santiago Segarra, Microsoft and Rice University; Himanshu Raj and Umesh Krishnaswamy, Microsoft; Ramesh Govindan, University of Southern California; Srikanth Kandula, Microsoft


Production systems use heuristics because they are faster or scale better than their optimal counterparts. Yet, practitioners are often unaware of the performance gap between a heuristic and the optimum or between two heuristics in realistic scenarios. MetaOpt is a system that helps analyze these heuristics. Users specify the heuristic and the optimal (or another heuristic) as input, and MetaOpt encodes these efficiently for a solver to find performance gaps and their corresponding adversarial inputs. Its suite of built-in optimizations helps it scale to practical problem sizes. We used MetaOpt to analyze heuristics from three domains (traffic engineering, vector bin packing, and packet scheduling). We found a production traffic engineering heuristic can require 30\% more capacity than the optimal in realistic cases. We modified the heuristic based on the patterns in the adversarial inputs MetaOpt discovered and reduced the performance gap by 12.5×. We examined adversarial inputs to a vector bin packing heuristic and proved a new lower bound on its performance.

NSDI '24 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {295571,
author = {Pooria Namyar and Behnaz Arzani and Ryan Beckett and Santiago Segarra and Himanshu Raj and Umesh Krishnaswamy and Ramesh Govindan and Srikanth Kandula},
title = {Finding Adversarial Inputs for Heuristics using Multi-level Optimization},
booktitle = {21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24)},
year = {2024},
isbn = {978-1-939133-39-7},
address = {Santa Clara, CA},
pages = {927--949},
url = {},
publisher = {USENIX Association},
month = apr

Presentation Video