Alembic: Automated Model Inference for Stateful Network Functions

Authors: 

Soo-Jin Moon, Carnegie Mellon University; Jeffrey Helt, Princeton University; Yifei Yuan, Intentionet; Yves Bieri, ETH Zurich; Sujata Banerjee, VMware Research; Vyas Sekar, Carnegie Mellon University; Wenfei Wu, Tsinghua University; Mihalis Yannakakis, Columbia University; Ying Zhang, Facebook, Inc.

Abstract: 

Network operators today deploy a wide range of complex stateful network functions (NFs). They typically only have access to the NFs’ binary executables, configuration interfaces, and manuals from vendors. To ensure correct behavior of NFs, operators use network testing and verification tools, which typically rely on models of the deployed NFs. The effectiveness of these tools depends upon the fidelity of such models. Today, models are handwritten, which can be error prone, tedious, and does not account for implementation-specific artifacts. To address this gap, our goal is to automatically infer behavioral models of stateful NFs for a given configuration. The problem is challenging because NF configurations can contain diverse rule types and the space of dynamic and stateful NF behaviors is large. In this work, we present Alembic, which synthesizes NF models viewed as an ensemble of finite-state machines (FSMs). Alembic consists of an offline stage that learns symbolic FSM representations for each NF rule type and a fast online stage that generates a concrete behavioral model for a given configuration using these symbolic FSMs. We demonstrate that Alembic is accurate, scalable and sheds light on subtle differences across NF implementations.

NSDI '19 Open Access Sponsored by NetApp

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 {227647,
author = {Soo-Jin Moon and Jeffrey Helt and Yifei Yuan and Yves Bieri and Sujata Banerjee and Vyas Sekar and Wenfei Wu and Mihalis Yannakakis and Ying Zhang},
title = {Alembic: Automated Model Inference for Stateful Network Functions},
booktitle = {16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19)},
year = {2019},
isbn = {978-1-931971-49-2},
address = {Boston, MA},
pages = {699--718},
url = {https://www.usenix.org/conference/nsdi19/presentation/moon},
publisher = {{USENIX} Association},
month = feb,
}

Presentation Video