CoChat
Sign Up
PreprintCited by 0Software Testing and Debugging TechniquesSoftware-Defined Networks and 5GSoftware System Performance and Reliability

Test coverage for network configurations

Open access
Xu, Xieyang, Deng, Weixin, Beckett, Ryan, Mahajan, Ratul, Walker, David·2022·arXiv
DOI 10.48550/arxiv.2209.12870arXiv 2209.12870
Open this paper in CoChat — free accountOpen PDF

Abstract

We develop NetCov, the first tool to reveal which network configuration lines are being tested by a suite of network tests. It helps network engineers improve test suites and thus increase network reliability. A key challenge in its development is that many network tests test the data plane instead of testing the configurations (control plane) directly. We must be able to efficiently infer which configuration elements contribute to tested data plane elements, even when such contributions are non-local (on remote devices) or non-deterministic. NetCov uses an information flow graph based model that precisely captures various forms of contributions and a scalable method to lazily infer contributions. Using it, we show that an existing test suite for Internet2 (a nation-wide backbone network in the USA) covers only 26% of the configuration lines. The feedback from NetCov makes it easy to define new tests that improve coverage. For Internet2, adding just three such tests covers an additional 17% of the lines.

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

DataCite · 10.48550/arxiv.2209.12870

Cites

Statistics

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?

  • The state observed by an agent can be skewed due to a partial view.

    “The state observed by an agent can be skewed due to a partial view [57], [127], [137], [138].”

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

    Section 6.1 (p. 8) says the authors approximate unavailable Internet2 data-plane state using Route Views, producing a coarse approximation. It does not say that an agent's observed state is skewed by a partial view. Searches for “partial view,” “skewed,” and incomplete observation found no passage addressing that claim. (LLM, conf=0.72)

    Experimental — accuracy not yet measured

  • Drift is the default case in operations.

    “Drift is the default case in operations [127], [137], [138], [”

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

    The Introduction (p. 1) says network configurations receive day-to-day updates and that those updates are error-prone. It does not say that configuration drift—divergence from an intended state—is the default in operations. Searches for “drift” and operational divergence found no passage addressing that claim. (LLM, conf=0.72)

    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.

The citation lists haven’t been fetched yet

Research works printed but not linked: 32

  1. [2][2] Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A scalable, commodity data center network architecture. In Proceedings of SIGCOMM '08 , page 63-74. ACM, 2008. -
  2. [4][4] James H Andrews, Lionel C Briand, Yvan Labiche, and Akbar Siami Namin. Using mutation analysis for assessing and comparing testing coverage criteria. IEEE Transactions on Software Engineering , 32(8):608-624, 2006. -
  3. [5][5] John Backes, Sam Bayless, Byron Cook, Catherine Dodge, Andrew Gacek, Alan J Hu, Temesghen Kahsai, Bill Kocik, Evgenii Kotelnikov, Jure Kukovec, et al. Reachability analysis for aws-based networks. In International Conference on Computer Aided Verification , pages 231-241. Springer, 2019. -
  4. [7][7] Ryan Beckett, Aarti Gupta, Ratul Mahajan, and David Walker. A general approach to network configuration verification. In Proceedings of SIGCOMM '17 , pages 155-168. ACM, 2017. -
  5. [8][8] Karl S Brace, Richard L Rudell, and Randal E Bryant. Efficient implementation of a bdd package. In Proceedings of the 27th ACM/IEEE design automation conference , pages 40-45, 1991. -
  6. [12][12] Ari Fogel, Stanley Fung, Luis Pedrosa, Meg WalraedSullivan, Ramesh Govindan, Ratul Mahajan, and Todd Millstein. A general approach to network configuration analysis. In Proceedings of NSDI 15 , pages 469-483. USENIX Association, 2015. -
  7. [13][13] Lixin Gao and Jennifer Rexford. Stable internet routing without global coordination. IEEE/ACM Transactions on networking , 9(6):681-692, 2001. -
  8. [14][14] Aaron Gember-Jacobson, Raajay Viswanathan, Aditya Akella, and Ratul Mahajan. Fast control plane analysis using an abstract representation. In Proceedings of SIGCOMM '16 , pages 300-313. ACM, 2016. -
  9. [15][15] Milos Gligoric, Alex Groce, Chaoqiang Zhang, Rohan Sharma, Mohammad Amin Alipour, and Darko Marinov. Comparing non-adequate test suites using coverage criteria. In Proceedings of the 2013 International Symposium on Software Testing and Analysis , ISSTA 2013, page 302-313, 2013. -
  10. [16][16] Timothy G Griffin, F Bruce Shepherd, and Gordon Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions On Networking , 10(2):232243, 2002. -
  11. [18][18] Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray Huang, Dave Maltz, Zhaoyi Liu, Vin Wang, Bin Pang, Hua Chen, Zhi-Wei Lin, and Varugis Kurien. Pingmesh: A large-scale system for data center network latency measurement and analysis. In Proceedings of SIGCOMM '15 , page 139-152. ACM, 2015. -
  12. [19][19] Alex Horn, Ali Kheradmand, and Mukul Prasad. Deltanet: Real-time network verification using atoms. In Proceedings of NSDI 17 , pages 735-749. USENIX Association, 2017. -
  13. [20][20] Monica Hutchins, Herb Foster, Tarak Goradia, and Thomas Ostrand. Experiments on the effectiveness of dataflow-and control-flow-based test adequacy criteria. In Proceedings of 16th International conference on Software engineering , pages 191-200. IEEE, 1994. -
  14. [22][22] Marko Ivankovi´ c, Goran Petrovi´ c, René Just, and Gordon Fraser. Code coverage at google. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering , pages 955-963. ACM, 2019. -
  15. [23][23] 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. Validating datacenters at scale. In Proceedings of SIGCOMM '19 , pages 200213. ACM, 2019. -
  16. [24][24] Yue Jia and Mark Harman. An analysis and survey of the development of mutation testing. IEEE transactions on software engineering , 37(5):649-678, 2010. -
  17. [25][25] Peyman Kazemian, George Varghese, and Nick McKeown. Header space analysis: Static checking for networks. In Proceedings of NSDI 12 , pages 113-126. USENIX Association, 2012. -
  18. [26][26] Ahmed Khurshid, Xuan Zou, Wenxuan Zhou, Matthew Caesar, and P Brighten Godfrey. Veriflow: Verifying network-wide invariants in real time. In Proceedings of NSDI 13 , pages 15-27. USENIX Association, 2013. -
  19. [27][27] Nuno P Lopes and Andrey Rybalchenko. Fast bgp simulation of large datacenters. In International Conference on Verification, Model Checking, and Abstract Interpretation , pages 386-408. Springer, 2019. -
  20. [28][28] Matthew Luckie, Bradley Huffaker, Amogh Dhamdhere, Vasileios Giotsas, and KC Claffy. As relationships, customer cones, and validation. In Proceedings of IMC '13 , pages 243-256, 2013. -
  21. [29][29] Santhosh Prabhu, Kuan Yen Chou, Ali Kheradmand, Brighten Godfrey, and Matthew Caesar. Plankton: Scalable network configuration verification through model checking. In Proceedings of NSDI 20 , pages 953-967. USENIX Association, 2020. -
  22. [30][30] Bruno Quoitin and Steve Uhlig. Modeling the routing of an autonomous system with c-bgp. IEEE network , 19(6):12-19, 2005. -
  23. [34][34] Joao Luis Sobrinho. Network routing with path vector protocols: Theory and applications. In Proceedings of - the 2003 conference on Applications, technologies, architectures, and protocols for computer communications , pages 49-60, 2003. -
  24. [37][37] Bingchuan Tian, Xinyi Zhang, Ennan Zhai, Hongqiang Harry Liu, Qiaobo Ye, Chunsheng Wang, Xin Wu, Zhiming Ji, Yihong Sang, Ming Zhang, Da Yu, Chen Tian, Haitao Zheng, and Ben Y. Zhao. Safely and automatically updating in-network acl configurations with intent language. In Proceedings of SIGCOMM '19 , page 214-226. ACM, 2019. -
  25. [38][38] Omer Tripp, Marco Pistoia, Stephen J Fink, Manu Sridharan, and Omri Weisman. Taj: effective taint analysis of web applications. ACMSigplan Notices , 44(6):87-97, 2009. -
  26. [41][41] Konstantin Weitz, Doug Woos, Emina Torlak, Michael D Ernst, Arvind Krishnamurthy, and Zachary Tatlock. Scalable verification of border gateway protocol configurations with an smt solver. In Proceedings of OOPSLA 2016 , pages 765-780. ACM, 2016. -
  27. [43][43] Yang Wu, Mingchen Zhao, Andreas Haeberlen, Wenchao Zhou, and Boon Thau Loo. Diagnosing missing events in distributed systems with negative provenance. ACM SIGCOMM Computer Communication Review , 44(4):383-394, 2014. -
  28. [44][44] Xieyang Xu, Ryan Beckett, Karthick Jayaraman, Ratul Mahajan, and David Walker. Test coverage metrics for the network. In Proceedings of SIGCOMM '21 , page 775-787. ACM, 2021. -
  29. [45][45] Hongkun Yang and Simon S. Lam. Real-time verification of network properties using atomic predicates. IEEE/ACM Trans. Netw. , 24(2):887-900, April 2016. -
  30. [46][46] 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. Accuracy, scalability, coverage: A practical configuration verifier on a global wan. In Proceedings of SIGCOMM '20 , page 599-614. ACM, 2020. -
  31. [47][47] Hongyi Zeng, Shidong Zhang, Fei Ye, Vimalkumar Jeyakumar, Mickey Ju, Junda Liu, Nick McKeown, and Amin Vahdat. Libra: Divide and conquer to verify forwarding tables in huge networks. In Proceedings of NSDI 14 , pages 87-99. USENIX Association, 2014. -
  32. [48][48] Wenchao Zhou, Micah Sherr, Tao Tao, Xiaozhou Li, Boon Thau Loo, and Yun Mao. Efficient querying and maintenance of network provenance at internet-scale. In Proceedings of SIGMOD '10 , pages 615-626. ACM, 2010.

Authors
Xu, X., Deng, W., Beckett, R., Mahajan, R., & Walker, D.
Affiliations
  • University of Washington (US)
  • Microsoft (United States) (US)
  • Princeton University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2209.12870
arXiv
2209.12870
OpenAlex
W4297411755
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
  • Physical Sciences › Computer Science › Computer Networks and Communications › Software-Defined Networks and 5G
  • Physical Sciences › Computer Science › Computer Networks and Communications › Software System Performance and Reliability
Keywords
test coverage, information flow graph, data plane, control plane, Internet2, network reliability

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