Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network

Published

October 16, 2009

Author(s)

David R. Kuhn, Raghu N. Kacker, Yu Lei

Abstract

This study compared random and t-way combinatorial inputs of a network simulator, to determine if these two approaches produce significantly different deadlock detection for varying network configurations. Modeling deadlock detection is important for analyzing configuration changes that could inadvertently degrade network operations, or to determine modifications that could be made by attackers to deliberately induce deadlock. Discrete event simulation of a network may be conducted using random generation of inputs. In this study, we compare random with combinatorial generation of inputs. Combinatorial (or t-way) testing requires every combination of any t parameter values to be covered by at least one test. Combinatorial methods can be highly effective because empirical data suggest that nearly all failures involve the interaction of a small number of parameters (1 to 6). Thus, for example, if all deadlocks involve at most 5-way interactions between n parameters, then exhaustive testing of all n-way interactions adds no additional information that would not be obtained by testing all 5-way interactions. While the maximum degree of interaction between parameters involved in the deadlocks clearly cannot be known in advance, covering all t-way interactions may be more efficient than using random generation of inputs. In this study we tested this hypothesis for t = 2, 3, and 4 for deadlock detection in a network simulation. Achieving the same degree of coverage provided by 4-way tests would have required approximately 3.2 times as many random tests; thus combinatorial methods were more efficient for detecting deadlocks involving a higher degree of interactions. The paper reviews explanations for these results and implications for modeling and simulation.

Conference Dates

October 14-16, 2009

Conference Location

Virginia Beach, VA

Conference Title

ModSim World 2009

Pub Type

Conferences

Download Paper

Local Download

Keywords

combinatorial testing, modeling and simulation, network security

Citation

Kuhn, D. , Kacker, R. and Lei, Y. (2009), Random vs. Combinatorial Methods for Discrete Event Simulation of a Grid Computer Network, ModSim World 2009, Virginia Beach, VA, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=904044 (Accessed December 14, 2024)