Cited by 40Software-Defined Networks and 5GFormal Methods in VerificationAdvanced Database Systems and Queries

The DOI matches its Crossref record.

Lessons from the evolution of the Batfish configuration analysis tool

Open access
Brown, Matt, Fogel, Ari, Halperin, Daniel, Heorhiadi, Victor, Mahajan, Ratul, Millstein, Todd·2023·Proceedings of the ACM SIGCOMM 2023 Conference

Abstract

Batfish is a tool to analyze network configurations and forwarding. It has evolved from a research prototype to an industrial-strength product, guided by scalability, fidelity, and usability challenges encountered when analyzing complex, real-world networks. We share key lessons from this evolution, including how Datalog had significant limitations when generating and analyzing forwarding state and how binary decision diagrams (BDDs) proved highly versatile. We also describe our new techniques for addressing real-world challenges, which increase Batfish performance by three orders of magnitude and enable high-fidelity analysis of networks with thousands of nodes within minutes.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3603269.3604866

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Operators need methods that remain useful under drift, produce evidence-linked outputs, and degrade safely when signals are missing.

    “Operators need methods that remain useful under drift, produce evidence-linked outputs, and degrade safely when signals are missing [128].”

    From Large language models for agentic NetOps and AIOps: Architectures, evaluation, and safety (2027) · cites this paper as [128]

    Section 5.2, “Continuous validation,” describes checking successive configuration snapshots to detect new errors, supporting usefulness as networks change. Section 4.4.3 describes annotating examples with the routing and ACL entries they encounter, supporting evidence-linked outputs. The cited passages do not establish that methods degrade safely when signals are missing; the paper’s observation that Batfish can remain useful despite modeling bugs (Lesson 3) is not the same claim. (LLM, conf=0.86)

    Experimental — accuracy not yet measured
  • Practitioner studies suggest benchmarks should reward robustness along with actionable outcomes, not accuracy alone.

    “Practitioner studies suggest benchmarks should reward robustness along with actionable outcomes, not accuracy alone [128].”

    From Large language models for agentic NetOps and AIOps: Architectures, evaluation, and safety (2027) · cites this paper as [128]

    Section 4.3.1 describes testing Batfish’s robustness across configuration patterns, while Section 5.2 reports that engineers prioritize consequential errors over making configurations completely error-free. Those practitioner observations support the emphasis on robustness and useful outcomes, but Section 6 benchmarks performance; the paper does not recommend that benchmarks reward robustness and actionable outcomes rather than accuracy alone. (LLM, conf=0.82)

    Experimental — accuracy not yet measured
  • If the agent is trained or evaluated on cleanly parsed logs, but deployed on noisy and drifting templates, autonomy will be miscalibrated.

    “For agentic AIOps, the implication is direct: if the agent is trained or evaluated on cleanly parsed logs, but deployed on noisy and drifting templates, autonomy will be miscalibrated [127], [128].”

    From Large language models for agentic NetOps and AIOps: Architectures, evaluation, and safety (2027) · cites this paper as [128]

    The paper’s “Lesson 3: Analysis fidelity is hard but not why you think” discusses inaccurate analysis of real-world router configurations that deviate from common idioms. A search for log parsing, template drift, and agent training or deployment found no passage addressing whether those conditions miscalibrate an AIOps agent’s autonomy. (LLM, conf=0.74)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 52

  1. Anubhavnidhi Abhashkumar, Aaron Gember-Jacobson, and Aditya Akella. 2020. Tiramisu: Fast Multilayer Network Verification. In NSDI.
  2. Akers. 1978. Binary Decision Diagrams. IEEE Trans. Comput. (1978).
  3. John Backes S. Bayless Byron Cook C. Dodge Andrew Gacek A.J. Hu T. Kahsai B. Kocik E. Kotelnikov J. Kukovec Sean McLaughlin J. Reed Neha Rungta J. Sizemore M. Stalzer P. Srinivasan P. Suboti Carsten Varming and B. Whaley. 2019. Reachability Analysis for AWS-based networks. In CAV. · DOI
  4. Sam Bayless, Noah Bayless, Holger H. Hoos, and Alan J. Hu. 2015. SAT Modulo Monotonic Theories. In AAAI.
  5. Ryan Beckett Aarti Gupta Ratul Mahajan and David Walker. 2017. A General Approach to Network Configuration Verification. In SIGCOMM. · DOI · Paper page
  6. Ryan Beckett Aarti Gupta Ratul Mahajan and David Walker. 2018. Control Plane Compression. In SIGCOMM. · DOI
  7. Ryan Beckett and Ratul Mahajan. 2020. A General Framework for Compositional Network Modeling. In HotNets. · DOI
  8. Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler. 2010. A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World. Commun. ACM (2010).
  9. 10.1007/978-3-319-49052-6_4 · DOI
  10. Cristiano Calcagno Dino Distefano Jeremy Dubreil Dominik Gabi Pieter Hooimeijer Martino Luca Peter O'Hearn Irene Papakonstantinou Jim Purbrick and Dulma Rodriguez. 2015. Moving Fast with Software Verification. In NASA Formal Methods. · DOI
  11. Antonio Ceseracciu. 2020. Safe ACL Change through Model-based Analysis. https://tech.ebayinc.com/engineering/safe-acl-change-through-model-based-analysis/.
  12. Seyed K. Fayaz Tushar Sharma Ari Fogel Ratul Mahajan Todd Millstein Vyas Sekar and George Varghese. 2016. Efficient Network Reachability Analysis Using a Succinct Control Plane Representation. In OSDI.
  13. Nick Feamster and Hari Balakrishnan. 2005. Detecting BGP Configuration Faults with Static Analysis. In NSDI.
  14. Sally Floyd and Van Jacobson. 1993. The Synchronization of Periodic Routing Messages. SIGCOMM Computer Communication Review (CCR) (1993).
  15. Ari Fogel Stanley Fung Luis Pedrosa Meg Walraed-Sullivan Ramesh Govindan Ratul Mahajan and Todd Millstein. 2015. A General Approach to Network Configuration Analysis. In NSDI.
  16. 10.1109/32.87281 · DOI
  17. Aaron Gember-Jacobson Raajay Viswanathan Aditya Akella and Ratul Mahajan. 2016. Fast Control Plane Analysis Using an Abstract Representation. In SIGCOMM. · DOI
  18. Aaron Gember-Jacobson Raajay Viswanathan Aditya Akella and Ratul Mahajan. 2016. Fast Control Plane Analysis Using an Abstract Representation. In SIGCOMM. · DOI
  19. 10.5555/AAI28094993 · DOI
  20. gns3 [n. d.]. GNS3 | The Software that Empowers Network Professionals. https://www.gns3.com/. Retrieved February 2023.
  21. Dong Guo, Shenshen Chen, Kai Gao, Qiao Xiang, Ying Zhang, and Y. Richard Yang. 2022. Flash: Fast, Consistent Data Plane Verification for Large-Scale Network Settings. In SIGCOMM.
  22. Alex Horn, Ali Kheradmand, and Mukul R. Prasad. 2017. Delta-Net: Real-Time Network Verification Using Atoms. In NSDI.
  23. Marieke Huisman and Raúl E. Monti. 2020. On the Industrial Application of Critical Software Verification with VerCors. In Leveraging Applications of Formal Methods, Verification and Validation: Applications.
  24. Karthick Jayaraman, Nikolaj Bjørner, Jitu Padhye, Amar Agrawal, Ashish Bhargava, Paul-Andre C Bissonnette, Shane Foster, Andrew Helwer, Mark Kasten, Ivan Lee, Anup Namdhari, Haseeb Niaz, Aniruddha Parkhi, Hanukumar Pinnamraju, Adrian Power, Neha Milind Raje, and Parag Sharma. 2019. Validating Datacenters at Scale. In SIGCOMM.
  25. Tommy R. Jensen and Bjarne Toft. 1994. Graph Coloring Problems.
  26. Theo Jepsen Ali Fattaholmanan Masoud Moshref Nate Foster Antonio Carzaniga and Robert Soulé. 2020. Forwarding and Routing with Packet Subscriptions. In CoNEXT. · DOI
  27. Siva Kesava Reddy Kakarla Alan Tang Ryan Beckett Karthick Jayaraman Todd Millstein Yuval Tamir and George Varghese. 2020. Finding Network Misconfigurations by Automatic Template Inference. In NSDI.
  28. Peyman Kazemian Michael Chang Hongyi Zeng George Varghese Nick McKeown and Scott Whyte. 2013. Real Time Network Policy Checking Using Header Space Analysis. In NSDI.
  29. Peyman Kazemian George Varghese and Nick McKeown. 2012. Header Space Analysis: Static Checking for Networks. In NSDI.
  30. Ahmed Khurshid Xuan Zou Wenxuan Zhou Matthew Caesar and P. Brighten Godfrey. 2013. VeriFlow: Verifying Network-wide Invariants in Real Time. In NSDI. · DOI
  31. Gary A. Kildall. 1973. A Unified Approach to Global Program Optimization. In POPL. · DOI
  32. Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM (1978).
  33. Guyue Liu Ao Li Christopher Canel and Vyas Sekar. 2021. Watching the Watchmen: Least Privilege for Managed Network Services. In HotNets. · DOI
  34. Hongqiang Harry Liu Yibo Zhu Jitu Padhye Jiaxin Cao Sri Tallapragada Nuno P. Lopes Andrey Rybalchenko Guohan Lu and Lihua Yuan. 2017. CrystalNet: Faithfully Emulating Large Production Networks. In SOSP.
  35. Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica. 2006. Declarative Networking: Language, Execution and Optimization. In SIGMOD.
  36. 10.1145/1080091.1080126 · DOI
  37. Nuno P. Lopes Nikolaj Bjorner Patrice Godefroid Karthick Jayaraman and George Varghese. 2015. Checking Beliefs in Dynamic Networks. In NSDI.
  38. Nuno P. Lopes and Andrey Rybalchenko. 2019. Fast BGP Simulation of Large Datacenters. In Verification, Model Checking, and Abstract Interpretation (VMCAI).
  39. Timothy Nelson, Christopher Barratt, Daniel J. Dougherty, Kathi Fisler, and Shriram Krishnamurthi. 2010. The Margrave Tool for Firewall Analysis. In Large Installation System Administration Conference (LISA).
  40. Aurojit Panda Ori Lahav Katerina Argyraki Mooly Sagiv and Scott Shenker. 2017. Verifying Reachability in Networks with Mutable Datapaths. In NSDI.
  41. Terence J. Parr and Russell W. Quong. 1995. ANTLR: A Predicated-LL (k) Parser Generator. Software: Practice and Experience (1995).
  42. Pieter Philippaerts, Jan Tobias Mühlberg, Willem Penninckx, Jan Smans, Bart Jacobs, and Frank Piessens. 2014. Software verification with VeriFast: Industrial case studies. Science of Computer Programming (2014).
  43. 10.1109/MNET.2005.1541716 · DOI
  44. Serena Spinoso Matteo Virgilio Wolfgang John Antonio Manzalini Guido Marchetto and Riccardo Sisto. 2015. Formal Verification of Virtual Network Function Graphs in an SP-DevOps Context. In Service Oriented and Cloud Computing. · DOI
  45. Radu Stoenescu Matei Popovici Lorina Negreanu and Costin Raiciu. 2016. Sym-Net: Scalable Symbolic Execution for Modern Networks. In SIGCOMM. · DOI
  46. Alan Tang, Siva Kesava Reddy Kakarla, Ryan Beckett, Ennan Zhai, Matt Brown, Todd Millstein, Yuval Tamir, and George Varghese. 2021. Campion: Debugging Router Configuration Differences. In SIGCOMM.
  47. Xieyang Xu Weixin Deng Ryan Beckett Ratul Mahajan and David Walker. 2023. Test Coverage for Network Configurations. In NSDI.
  48. Hongkun Yang and Simon S. Lam. 2013. Real-time verification of network properties using Atomic Predicates. In International Conference on Network Protocols (ICNP).
  49. Hongkun Yang and Simon S. Lam. 2017. Scalable Verification of Networks With Packet Transformers Using Atomic Predicates. IEEE/ACM Transactions on Networking (2017).
  50. Fangdan Ye, Da Yu, Ennan Zhai, Hongqiang Harry Liu, Bingchuan Tian, Qiaobo Ye, Chunsheng Wang, Xin Wu, Tianchen Guo, Cheng Jin, Duncheng She, Qing Ma, Biao Cheng, Hui Xu, Ming Zhang, Zhiliang Wang, and Rodrigo Fonseca. 2020. Accuracy, Scalability, Coverage: A Practical Configuration Verifier on a Global WAN. In SIGCOMM.
  51. Lihua Yuan, Hao Chen, Jianning Mai, Chen-Nee Chuah, Zhendong Su, and P. Mohapatra. 2006. FIREMAN: A Toolkit for Firewall Modeling and Analysis. In IEEE Symposium on Security and Privacy.
  52. Hongyi Zeng, Shidong Zhang, Fei Ye, Vimalkumar Jeyakumar, Mickey Ju, Junda Liu, Nick McKeown, and Amin Vahdat. 2014. Libra: Divide and Conquer to Verify Forwarding Tables in Huge Networks. In NSDI.

Cited by

Sorted by citations

Metadata

Authors
Brown, M., Fogel, A., Halperin, D., Heorhiadi, V., Mahajan, R., & Millstein, T.
Affiliations
  • Intentionet, Los Angeles, USA
  • Intentionet, Seattle, USA
  • University of Washington (US)
  • University of California, Los Angeles (US)
Venue
Proceedings of the ACM SIGCOMM 2023 Conference
Publisher
ACM
Published
2023-09
Pages
122-135
OpenAlex
W4386385177
Cited by
40
References
0
Citations by year
2026: 15 · 2025: 15 · 2024: 10
FWCI
12.09
Type
conference paper
Language
en
Open access
Locations
ACM SIGCOMM Conference (SIGCOMM) (publishedVersion, cc-by)
Funders
National Science Foundation (2007073, 2219863, 1901510)
Topics
  • Physical Sciences › Computer Science › Computer Networks and Communications › Software-Defined Networks and 5G
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
  • Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
Keywords
batfish, binary decision diagrams, scalability, network analysis software, tool evolution

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review