Topology generation for protocol testing: Methodology and case studies

One of the key steps in the design or refinement of an application or network protocol is, testing of the protocol for correctness and performance. Simulation and state space exploration are the most popular ways of testing protocols. Simulation tools like NS, OPNET etc., allow the designer to test/evaluate a protocol's performance on fully specified instances of topologies. The scope of this study is limited to the correctness of control or house keeping functions of protocols.To thoroughly test IP based protocols and applications, for each protocol behavior or protocol property, the testing procedure must iterate implicitly or explicitly over the set of all topology configurations (potentially large in case of IP) on which the protocol is expected to execute. Formally, for a given behavior B a testing procedure is given by Loop 1: All valid topologies Loop 2: All inputs, initial states and sequences of injection Loop 3: check of behavior B occurs.In the above procedure, the outer most loop enumerating individual instances of topologies in the topology configuration space, will incur impractical runtime complexity due to combinatorial explosion in the number of topology instances when the number of components that make up the topology and/or their configurations are very large. Further, to ensure thorough testing, the set of topologies on which the protocol can misbehave must be used during testing. Thus, an approach that can differentiate between the set of topologies on which the behavior occurs, and, the set on which the behavior does not occur, can be very useful to reduce the complexity arising out of the necessity to consider all topology configurations to ensure thorough testing. Though several studies have attempted to study the influence of topology on protocol behavior, a methodology to systematize selection or generation of topologies that can used for effective protocol testing has received little attention. This has often resulted in errors in protocols triggered by specific topology configuration going unnoticed at design time only to show up after deployment. The focus of this work is to generate necessary topology conditions that any topology on which the target behavior occurs must satisfy. This can be used to systematize topology coverage while protocol testing, by eliminating the large class of topologies that do not satisfy the necessary conditions and focusing the simulation and state space enumeration efforts on the topology space on which the problematic behavior occurs.To generate necessary topology conditions that a topology must satisfy for the target behavior to occur, a methodology called "Compressed Representation of State Space for topology configuration generation" (COMPRESS) is developed. This is based on the novel combination of two basic ideas (a) represent complex topologies as a composition of simple end to end topology component abstractions derived from packet destination types (e.g., IP unicast, IP broadcast, etc) (b) use the information already embedded in the protocol FSMs (folded state space) to drive the composition of the end to end topology abstractions to obtain more complex, but relevant topologies. For a given behavior, COMPRESS, indirectly, i.e., without explicit topology enumeration, identifies necessary conditions satisfied by the set of all topologies on which that behavior may occur, without solving the reachability problem. To our knowledge, this is the first work that addresses the problem of generation of necessary topology conditions for a target behavior to occur.The usefulness of the COMPRESS methodology is evaluated using case studies of several different class of protocols including client server protocol, resource discovery protocol, emergency location information server protocol and multicast based micro-mobility protocol. For each protocol, behaviors that include errors that either appear as 100% performance degradation or unexpected behavior to the end user are studied. The necessary topology conditions generated by COMPRESS were highly non-intuitive and revealed unexpected or severe errors triggered often by small topology configurations. It is also shown how necessary topology conditions generated by COMPRESS can, not only be used to effectively and efficiently characterize the problematic topology space causing that behavior by eliminating a very large set of uninteresting topologies (up to 99.4%), but also be a powerful tool to characterize the severity of the problematic behavior itself. Through these case studies, it is shown that the topology conditions generated are highly non-intuitive, close to sufficient conditions and practically useful, but also the practical runtime complexity is quite manageable. (Abstract shortened by UMI.)...