Automated testing of stochastic systems: a statistically grounded approach

ABSTRACT

Automated tests can play a key role in ensuring system quality in software development. However, significant problems arise in automating tests of stochastic algorithms. Normally, developers write tests that simply check whether the actual result is equal to the expected result (perhaps within some tolerance). But for stochastic algorithms, restricting ourselves in this way severely limits the kinds of tests we can write: either to trivial tests, or to fragile and hard-tounderstand tests that rely on a particular seed for a random number generator. A richer and more powerful set of tests is possible if we accommodate tests of statistical properties of the results of running an algorithm many times. The work described in this paper has been done in the context of a real-world application, a large-scale simulation of urban development designed to inform major decisions about land use and transportation. We describe our earlier experience with using automated testing for this system, in which we took a conventional approach, and the resulting difficulties. We then present a statistically based approach for testing stochastic algorithms based on hypothesis testing. Three different ways of constructing such tests are given, which cover the most commonly used distributions. We evaluate these tests in terms of frequency of failing when they should and when they should not, and conclude with guidelines and practical suggestions for implementing such unit tests for other stochastic applications.

REFERENCES

• 1: Adbelmonem A. Afifi , V. Clark, Computer-Aided Multivariate Analysis, Chapman & Hall, Ltd., London, UK, 1999
• 2: Kent Beck, Extreme programming explained: embrace change, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Beck, Test Driven Development: By Example, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 4: K. Beck and E. Gamma. Test infected: Programmers love writing tests. http://junit.sourceforge.net/doc/testinfected/testing.htm. last visited 19-jan-2006.
• 5: M. Ben-Akiva and S. R. Lerman. Discrete Choice Analysis: Theory and Application to Travel Demand. The MIT Press, Cambridge, Massachusetts, 1987.
• 6: Yih-Farn Chen , David S. Rosenblum , Kiem-Phong Vo, TestTube: a system for selective regression testing, Proceedings of the 16th international conference on Software engineering, p.211-220, May 16-21, 1994, Sorrento, Italy
• 7: M. Fowler and M. Foemmel. Continuous integration. Technical report, ThoughtWorks, http://martinfowler.com/articles/continuousIntegration.html, 2006. last visited 22-jan-2006.
• 8: Bjorn Freeman-Benson , Alan Borning, YP and Urban Simulation: Applying an Agile Programming Methodology in a Politically Tempestuous Domain, Proceedings of the Conference on Agile Development, p.2, June 25-28, 2003
• 9: Andy Hunt , Dave Thomas, Pragmatic Unit Testing in C# with NUnit, The Pragmatic Programmers, 2004
• 10: Dieter Kranzlmüller, Testing nondeterministic message-passing programs with NOPE, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.152, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281054]
• 11: D. Lee and M. Yannakakis. Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE, 84(8):1090--1123, August 1996.
• 12: John D. McGregor , David A. Sykes, A practical guide to testing object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 13: A. Mood, F. A. Graybill, and D. C. Boes. Introduction to the Theory of Statistics. McGraw-Hill, third edition, 1974.
• 14: Lev Nachmanson , Margus Veanes , Wolfram Schulte , Nikolai Tillmann , Wolfgang Grieskamp, Optimal strategies for testing nondeterministic systems, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 15: Robert E. Noonan , Richard H. Prosl, Unit testing frameworks, Proceedings of the 33rd SIGCSE technical symposium on Computer science education, February 27-March 03, 2002, Cincinnati, Kentucky
• 16: M. Noth, A. Borning, and P. Waddell. An extensible, modular architecture for simulating urban development, transportation, and environmental impacts. Computers, Environment and Urban Systems, 27(2):181--203, Mar. 2003.
• 17: H. Ševčíková, A. Raftery, and P. Waddell. Assessing uncertainty in urban simulations using Bayesian melding. Submitted for publication - draft available from http://www.urbansim.org/papers/BMinUrbansim.pdf, 2006.
• 18: Deepinder P. Sidhu , Ting-kau Leung, Formal Methods for Protocol Testing: A Detailed Study, IEEE Transactions on Software Engineering, v.15 n.4, p.413-426, April 1989 [doi>10.1109/32.16602 ]
• 19: Ian Sommerville, Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 20: K. E. Train. Discrete Choice Methods with Simulation. Cambridge University Press, 2003.
• 21: P. Waddell. UrbanSim: Modeling urban development for land use, transportation, and environmental planning. Journal of the American Planning Association, 68(3):297--314, Summer 2002.
• 22: P. Waddell, A. Borning, M. Noth, N. Freier, M. Becke, and G. Ulfarsson. Microsimulation of urban development and location choices: Design and implementation of UrbanSim. Networks and Spatial Economics, 3(1):43--67, 2003.
• 23: P. Waddell, H. Ševčíková, D. Socha, E. Miller, and K. Nagel. Opus: An open platform for urban simulation. Presented at the Computers in Urban Planning and Urban Management Conference, London, June 2005. Available from www.urbansim.org/papers.
• 24: Mihalis Yannakakis , David Lee, Testing finite state machines, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.476-485, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103468]

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:
Algorithms, Verification

Keywords:
hypothesis testing, software engineering, software testing, stochastic algorithms, unit tests