Project Members
Faculty:   Tzi-cker Chiueh
Students: Pradipta De  and  Rupa Krishnan  and  Anindya Neogi

Overview
An increasing thrust in the area of cluster-based computing has lead to the development of a myriad of network protocols to communicate among machines in the cluster. These protocols range from distributed middleware message passing schemes to server load balancing protocols mostly implemented in the kernel. Complexity of such protocols and their possible usage in mission-critical systems mandates fool-proof verification and testing before deployment. A major component of the complexity of communication protocols is attributed to network failure and various types of error handling. Formal processes exist to verify if a protocol specification contains bugs or efficiency bottlenecks. However it is often the case that the problem lies in the incorrect implementation of a correct and verified protocol specification.

In this project we are building a system on which one may test the "actual implementation" of a network protocol and validate its operation in the presence of emulated network misbehaviors. The system consists of

• a declarative fault specification language and its parser
• a kernel module for distributed fault emulation to be installed on all nodes in the network under test
• a trace collection and analysis tool for debugging

• There is no change required in any part of the system under test. This is important because often the source code of the protocol under test may be unavailable.
• Any protocol (user or kernel) may be tested as long as its is implemented above Ethernet driver because the kernel module sits above the Ethernet driver.
• The network topology under test may be single or multi-segment Ethernet with routers or any switched network. There are only certain language features which may be restricted, like performing an action at ALL nodes or choosing a node at random to perform an action, if a network contains routers. Also faults can be emulated on only those nodes on which the kernel module can be installed. Similarly faults can be emulated on only those links which are terminated by a node on which the kernel module is installed. Thus we cannot emulate a fault on a link between two directly connected commercial switches.
• One can emulate most types of protocol stack/network misbehaviors like : packet drops, reordering, spurious packets, duplication, delay, or fatal node crashes, and disconnections.
• The testing process is automated because the user specifies the test cases in our language. The language follows a declarative style so that the user has to write only the nature of the fault(s) in the test case, not how to implement it. This requires minimum programmming effort on the part of the user.
• The system also provides debugging support in the form of trace collection tools, flagging of untriggered test case conditions, and trace analysis.

System Architecture

Publications:
VirtualWire: A Fault Injection and Analysis Tool for Network Protocols [ ps ]
 Pradipta De, Anindya Neogi and Tzi-cker Chiueh
 In Proceedings of  International Conference on Distributed Computing Systems (ICDCS), May 2003 

Related Work
Z. Segall and T. Lin, “Fiat: Fault-injection based automated testing environment,” in 18th Int’l Symposium on Fault Tolerant Computing, 1988.
J. Carreira, H. Madeira, and J. G. Silva, “Xception: Software fault injection and monitoring in processor functional units,” in 5th IFIP Int’l Working ConferenceDependable Computing of Critical Applications (DCCA), Sept. 1995.
 S. Han, H. A. Rosenberg, and K. G. Shin, “Doctor: An integrated software fault injection environment for distributed systems,” in IEEE International Computer Performance and Dependability Symposium, 1995.
D. Stott, B. Floering, Z. Kalbarczyk, and R. K. Iyer, “Nftape: A framework for assessing dependability in distributed systems with lightweight fault injectors,” in 4th IEEE International Computer Performance and Dependability Symposium (IPDS-2K), 2000.
D. Engler, B. Chelf, A. Chou, and S. Hallem, “Checking system rules using system-specific, programmer-written compiler extensions,” in OSDI, 2000.
V. Paxson, “Automated packet trace analysis of tcp implementations,” in ACM SIGCOMM, 1997.
D. E. Comer and J. C. Lin, “Probing tcp implementations,” in USENIX, June 1994.
S. Dawson, F. Jahanian, and T. Mitton, “Orchestra: A fault injection environment for distributed systems,” in 26th International Symposium on Fault-Tolerant Computing (FTCS), 1996.
J. L. Griffin, “Testing protocol implementation robustness,” in 29th International Symposium on Fault-Tolerant Computing, 1999.
T. Tsai and N. Singh, “Reliability testing of applications on windows NT,” in International Conference on Dependable Systems and Networks (DSN), 2000.
D.B.Ingham and G.D.Parrington, “Delayline: A wide-area network emulation tool,” in Computing Systems, 1994.
L. Rizzo, “Dummynet: a simple approach to the evaluation of network protocols,” in ACM computer Communications Review, 1997.

Project Status
We have completed system design and the parser for the specification language. We have implemented the fault injection and analysis engine as a kernel module that runs on Linux 2.4 kernel using Netfilter hooks. We are currently porting this tool for use in protocol debugging for multi-hop wireless ad hoc networks, as part of the MiNT project.