Automatic test packet generation

ABSTRACT

Networks are getting larger and more complex; yet administrators rely on rudimentary tools such as ping and traceroute to debug problems. We propose an automated and systematic approach for testing and debugging networks called "Automatic Test Packet Generation" (ATPG). ATPG reads router configurations and generates a device-independent model. The model is used to generate a minimum set of test packets to (minimally) exercise every link in the network or (maximally) exercise every rule in the network. Test packets are sent periodically, and detected failures trigger a separate mechanism to localize the fault. ATPG can detect both functional (e.g., incorrect firewall rule) and performance problems (e.g., congested queue). ATPG complements but goes beyond earlier work in static checking (which cannot detect liveness or performance faults) or fault localization (which only localize faults given liveness results).

We describe our prototype ATPG implementation and results on two real-world data sets: Stanford University's backbone network and Internet2. We find that a small number of test packets suffices to test all rules in these networks: For example 4000 packets can cover all rules in Stanford backbone network while 54 is enough to cover all links. Sending 4000 test packets 10 times per second consumes less than 1% of link capacity. ATPG code and the data sets are publicly available¹[1].

References

1. ATPG code repository. http://eastzone.github.com/atpg/.
2. Automatic Test Pattern Generation. http://en.wikipedia.org/wiki/Automatic_test_pattern_generation.
3. Beacon. http://www.beaconcontroller.net/.
4. C. Cadar, D. Dunbar, and D. Engler. Klee: unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of OSDI'08, pages 209--224, Berkeley, CA, USA, 2008. USENIX Association.
5. M. Canini, D. Venzano, P. Peresini, D. Kostic, and J. Rexford. A NICE way to test openflow applications. Proceedings of NSDI'12, 2012.
6. A. Dhamdhere, R. Teixeira, C. Dovrolis, and C. Diot. Netdiagnoser: troubleshooting network unreachabilities using end-to-end probes and routing data. In Proceedings of the 2007 ACM CoNEXT conference, pages 18:1--18:12, New York, NY, USA, 2007. ACM.
7. N. Duffield. Network tomography of binary network performance characteristics. IEEE Transactions on Information Theory, 52(12):5373 --5388, dec. 2006.
8. N. Duffield, F. Lo Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In Proceedings IEEE INFOCOM 2001, volume 2, pages 915--923 vol.2, 2001.
9. N. G. Duffield and M. Grossglauser. Trajectory sampling for direct traffic observation. IEEE/ACM Trans. Netw., 9(3):280--292, June 2001.
10. P. Gill, N. Jain, and N. Nagappan. Understanding network failures in data centers: measurement, analysis, and implications. In Proceedings of the ACM SIGCOMM 2011 conference, pages 350--361, New York, NY, USA, 2011. ACM.
11. Hassel, the header space library. https://bitbucket.org/peymank/hassel-public/.
12. The Internet2 Observatory Data Collections. http://www.internet2.edu/observatory/archive/data-collections.html.
13. M. Jain and C. Dovrolis. End-to-end available bandwidth: measurement methodology, dynamics, and relation with tcp throughput. IEEE/ACM Trans. Netw., 11(4):537--549, Aug. 2003.
14. P. Kazemian, G. Varghese, and N. McKeown. Header Space Analysis: static checking for networks. Proceedings of NSDI'12, 2012.
15. R. R. Kompella, J. Yates, A. Greenberg, and A. C. Snoeren. Ip fault localization via risk modeling. In Proceedings of NSDI'05 - Volume 2, pages 57--70, Berkeley, CA, USA, 2005. USENIX Association.
16. M. Kuzniar, P. Peresini, M. Canini, D. Venzano, and D. Kostic. A SOFT way for openflow switch interoperability testing. In Proceedings of the 2012 ACM CoNEXT Conference, 2012.
17. K. Lai and M. Baker. Nettimer: a tool for measuring bottleneck link, bandwidth. In Proceedings of USITS'01 - Volume 3, pages 11--11, Berkeley, CA, USA, 2001. USENIX Association.
18. B. Lantz, B. Heller, and N. McKeown. A network in a laptop: rapid prototyping for software-defined networks. In Proceedings of Hotnets '10, pages 19:1--19:6, New York, NY, USA, 2010. ACM.
19. F. Le, S. Lee, T. Wong, H. S. Kim, and D. Newcomb. Detecting network-wide and router-specific misconfigurations through data mining. IEEE/ACM Trans. Netw., 17(1):66--79, Feb. 2009.
20. H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iplane: an information plane for distributed services. In Proceedings of OSDI'06, pages 367--380, Berkeley, CA, USA, 2006. USENIX Association.
21. A. Mahimkar, Z. Ge, J. Wang, J. Yates, Y. Zhang, J. Emmons, B. Huntley, and M. Stockert. Rapid detection of maintenance induced changes in service performance. In Proceedings of the 2011 ACM CoNEXT Conference, pages 13:1--13:12, New York, NY, USA, 2011. ACM.
22. A. Mahimkar, J. Yates, Y. Zhang, A. Shaikh, J. Wang, Z. Ge, and C. T. Ee. Troubleshooting chronic conditions in large ip networks. In Proceedings of the 2008 ACM CoNEXT Conference, pages 2:1--2:12, New York, NY, USA, 2008. ACM.
23. H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P. B. Godfrey, and S. T. King. Debugging the data plane with anteater. SIGCOMM Comput. Commun. Rev., 41(4):290--301, Aug. 2011.
24. A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, Y. Ganjali, and C. Diot. Characterization of failures in an operational ip backbone network. IEEE/ACM Trans. Netw., 16(4):749--762, Aug. 2008.
25. N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner. OpenFlow: enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev., 38:69--74, March 2008.
26. OnTimeMeasure. http://ontime.oar.net/.
27. Open vSwitch. http://openvswitch.org/.
28. All-pairs ping service for PlanetLab ceased. http://lists.planet-lab.org/pipermail/users/2005-July/001518.html.
29. M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker. Abstractions for network update. In Proceedings of the ACM SIGCOMM 2012 conference. ACM, 2012.
30. S. Shenker. The future of networking, and the past of protocols. http://opennetsummit.org/talks/shenker-tue.pdf.
31. Troubleshooting the Network Survey.http://eastzone.github.com/atpg/docs/NetDebugSurvey.pdf.
32. D. Turner, K. Levchenko, A. C. Snoeren, and S. Savage. California fault lines: understanding the causes and impact of network failures. SIGCOMM Comput. Commun. Rev., 41(4):--, Aug. 2010.
33. P. Yalagandula, P. Sharma, S. Banerjee, S. Basu, and S.-J. Lee. S3: a scalable sensing service for monitoring large networked systems. In Proceedings of INM '06, pages 71--76, New York, NY, USA, 2006. ACM.

Index Terms

• Networks

  • Network services

    • Network monitoring

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging