Covering arrays for efficient fault characterization in complex configuration spaces

ABSTRACT

Testing systems with large configurations spaces that change often is a challenging problem. The cost and complexity of QA explodes because often there isn't just one system, but a multitude of related systems. Bugs may appear in certain configurations, but not in others.The Skoll system and process has been developed to test these types of systems through distributed, continuous quality assurance, leveraging user resources around-the-world, around-the-clock. It has been shown to be effective in automatically characterizing configurations in which failures manifest. The derived information helps developers quickly narrow down the cause of failures which then improves turn around time for fixes. However, this method does not scale well. It requires one to exhaustively test each configuration in the configuration space.In this paper we examine an alternative approach. The idea is to systematically sample the configuration space, test only the selected configurations, and conduct fault characterization on the resulting data. The sampling approach we use is based on calculating a mathematical object called a covering array. We empirically assess the effect of using covering array derived test schedules on the resulting fault characterizations and provide guidelines to practitioners for their use.

REFERENCES

• 1: L. Breiman, J. Freidman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Monterey, CA, 1984.
• 2: R. Brownlie, J. Prowse, and M. S. Padke. Robust testing of AT&T PMX/StarMAIL using OATS. AT&T Technical Journal, 71(3):41--7, 1992.
• 3: K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation and code coverage. In Proc. of the Intl. Conf. on Software Testing Analysis & Review, 1998.
• 4: M. Chateauneuf and D. Kreher. On the state of strength-three covering arrays. Journal of Combinatorial Designs, 10(4):217--238, 2002.
• 5: David M. Cohen , Siddhartha R. Dalal , Michael L. Fredman , Gardner C. Patton, The AETG System: An Approach to Testing Based on Combinatorial Design, IEEE Transactions on Software Engineering, v.23 n.7, p.437-444, July 1997 [doi>10.1109/32.605761]
• 6: Myra B. Cohen , Peter B. Gibbons , Warwick B. Mugridge , Charles J. Colbourn, Constructing test suites for interaction testing, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 7: S. R. Dalal , A. Jain , N. Karunanithi , J. M. Leaton , C. M. Lott , G. C. Patton , B. M. Horowitz, Model-based testing in practice, Proceedings of the 21st international conference on Software engineering, p.285-294, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302640]
• 8: I. S. Dunietz , W. K. Ehrlich , B. D. Szablak , C. L. Mallows , A. Iannino, Applying design of experiments to software testing: experience report, Proceedings of the 19th international conference on Software engineering, p.205-215, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253271]
• 9: D. Richard Kuhn , Michael J. Reilly, An Investigation of the Applicability of Design of Experiments to Software Testing, Proceedings of the 27th Annual NASA Goddard Software Engineering Workshop (SEW-27'02), p.91, December 05-06, 2002
• 10: Robert Mandl, Orthogonal Latin squares: an application of experiment design to compiler testing, Communications of the ACM, v.28 n.10, p.1054-1058, Oct. 1985 [doi>10.1145/4372.4375]
• 11: A. Memon , A. Porter , C. Yilmaz , A. Nagarajan , D. Schmidt , B. Natarajan, Skoll: Distributed Continuous Quality Assurance, Proceedings of the 26th International Conference on Software Engineering, p.459-468, May 23-28, 2004
• 12: N. Sloane. Covering arrays and intersecting codes. Journal of Combinatorial Designs, 1(1):51--63, 1993.
• 13: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Economics, Reliability

Keywords:
covering arrays, distributed continuous quality assurance, fault characterization, software testing