NeTS: Small: Systematically and Scalably Testing Network Programs through Symbolic Exploration of Packet Dynamics

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

Network protocols and applications are an essential component of the Internet, and they must be implemented correctly so that Internet nodes (e.g., desktop PCs, laptops, smartphones, sensors, and routers) can correctly communicate with one another. However, the correctness of their implementations is difficult to test, especially under the large space of potential behavior introduced by packet dynamics. This is because there are a prohibitively large number of packet dynamics possibilities, and many bugs are revealed only in low probability corner cases, such as those with specific packet delay, number of packets, packet ordering, or packet loss and duplication. The goal of this project is to design and implement symbolic representations and methods for packet dynamics and the underlying network. These representations and methods will enable the use of emerging test case generation techniques based on symbolic execution for a systematic exploration of network protocol and application implementations. The approach will leverage symbolic execution capabilities of focusing on distinct input classes, in our context for packet dynamics and network states, avoiding redundantly testing equivalent behavior, and instead spending testing resources on packet dynamics leading to distinct and potentially buggy behavior. The proposed research consists of four research tasks. First, develop symbolic representations of common types of Internet packet dynamics, such as independent and dependent packet delays, and packet loss rates. Second, design distributed symbolic drivers that provide a network program under test with the illusion of communicating over a network with symbolic packet dynamics. Third, design a class of execution methods with mixed symbolic and random packet dynamics models for testing a network program with a large number of packets. Fourth, evaluate the proposed techniques and tools. The tasks will provide new insights into the correctness of vital network protocols and applications, and what type of representations and methods are more effective at detecting different types of bugs. The key potential broader impact is the detection of bugs in critical network protocols and applications, which may resonate well outside the computer science community. In addition, joined efforts by members of the networking and the software engineering communities are rare, but as shown in this proposal could be clearly beneficial in bringing the latest validation methodologies to bear in critical networking infrastructure, and in pushing to the forefront of the software testing agenda the networking timing and scale issues. From that perspective, the cross-cutting nature of this proposal and the expected byproducts for which the investigators have a strong record (students, data, tools, papers in top venues) will impact and generate synergy across both communities. The investigators will hold seminars to discuss with the systems and software engineering groups of professional and students the challenges and results of the project. They will also continue actively recruiting and training undergraduate, female, and minority students through this project.