Efficient and Correct Test Scheduling for Ensembles of Network Policies

Authors: 

Yifei Yuan, Sanjay Chandrasekaran, Limin Jia, and Vyas Sekar, Carnegie Mellon University

Abstract: 

Testing whether network policies are correctly implemented is critical to ensure a network’s safety, performance and availability. Network operators need to test ensembles of network policies using a combination of native and third-party tools in practice, as indicated by our survey. Unfortunately, existing approaches for running tests for ensembles of network policies on stateful networks face fundamental challenges with respect to correctness and efficiency. Running all tests sequentially is inefficient, while naïvely running tests in parallel may lead to incorrect testing results. In this paper, we propose Mikado, a principled scheduling framework for scheduling tests generated by various (blackbox) tools for ensembles of policies. We make two key contributions: (1) we develop a formal correctness criteria for running tests for ensembles of policies; and (2) we design a provably correct and efficient test scheduling algorithm, based on detecting read-write test conflicts. Mikado is open source and can support a range of policies and testing tools. We show that Mikado can generate correct schedules in real-world scenarios, achieve orders of magnitude reduction on the test running time, and schedule tests for thousands of network policies in large networks with 1000+ nodes within minutes.

NSDI '18 Open Access Videos 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.

BibTeX
@inproceedings {211295,
author = {Yifei Yuan and Sanjay Chandrasekaran and Limin Jia and Vyas Sekar},
title = {Efficient and Correct Test Scheduling for Ensembles of Network Policies},
booktitle = {15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18)},
year = {2018},
isbn = {978-1-931971-43-0},
address = {Renton, WA},
pages = {437--452},
url = {https://www.usenix.org/conference/nsdi18/presentation/yuan},
publisher = {{USENIX} Association},
}