Test Dependence : Theory and Manifestation University of Washington Technical Report UW-CSE-1307-02

Test dependence arises when executing a test in different environments causes it to return different results. In this paper, we show through a set of substantive real-world examples that test dependence arises in practice. We also show that test dependence can have potentially costly repercussions such as masking program faults, and can be hard to identify unless explicitly searched for: We found a dependence that only manifests when a sequence of three tests are run in a specified, non-default order. We formally define test dependence in terms of test suites as ordered sequences of tests along with explicit environments in which these tests are executed. We use this formalization to formulate the concrete problem of detecting dependence in test suites, prove that a useful special case is NP-complete, and propose an initial algorithm that approximates solutions to this problem.