Stress testing real-time systems with genetic algorithms

ABSTRACT

Reactive real-time systems have to react to external events within time constraints: Triggered tasks must execute within deadlines. The goal of this article is to automate, based on the system task architecture, the derivation of test cases that maximize the chances of critical deadline misses within the system. We refer to that testing activity as stress testing. We have developed a method based on genetic algorithms and implemented it in a tool. Case studies were run and results show that the tool may actually help testers identify test cases that will likely stress the system to such an extent that some tasks may miss deadlines.

REFERENCES

• 1: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 2: Robert V. Binder, Testing object-oriented systems: models, patterns, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: L. C. Briand, Y. Labiche and M. Shousha, "Stress Testing for Real-Time Systems Using Genetic Algorithms," Carleton University, Technical Report SCE-03-23, http://www.sce.carleton.ca/Squall/, September, 2003.
• 4: Hassan Gomaa, Designing Concurrent, Distributed, and Real-Time Applications with Uml, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 5: Randy L. Haupt , Sue Ellen Haupt, Practical genetic algorithms, John Wiley & Sons, Inc., New York, NY, 1998
• 6: Michael A. Iverson , Füsun Özgüner , Lee Potter, Statistical Prediction of Task Execution Times through Analytic Benchmarking for Scheduling in a Heterogeneous Environment, IEEE Transactions on Computers, v.48 n.12, p.1374-1379, December 1999 [doi>10.1109/12.817403]
• 7: Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 8: C. D. Locke, D. R. Vogel and T. J. Mesler, "Building a predictable avionics platform in ada: A case study," Proc. IEEE Real Time Systems Symposium, pp. 181--189, 1991.
• 9: Samir W. Mahfoud , David E. Goldberg, Parallel recombinative simulated annealing: a genetic algorithm, Parallel Computing, v.21 n.1, p.1-28, Jan. 1995 [doi>10.1016/0167-8191(94)00071-H]
• 10: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 11: F. Mueller , J. Wegener, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Proceedings of the Fourth IEEE Real-Time Technology and Applications Symposium, p.144, June 03-05, 1998
• 12: M. A. Pawlowsky, "Crossover Operators," in L. Chambers, Ed., Practical Handbook of Genetic Algorithms Applications, vol. 1, CRC Press, pp. 101--114, 1995.
• 13: J. David Schaffer , Richard A. Caruana , Larry J. Eshelman , Rajarshi Das, A study of control parameters affecting online performance of genetic algorithms for function optimization, Proceedings of the third international conference on Genetic algorithms, p.51-60, December 1989, George Mason University, United States
• 14: L. Sha and J. B. Goodenough, "Real-time Scheduling Theory and Ada," Software Engineering Institute, Technical Report CMU/SEI-89-TR-014, 1989.
• 15: Jim Smith , Terence C. Fogarty, Adaptively Parameterised Evolutionary Systems: Self-Adaptive Recombination and Mutation in a Genetic Algorithm, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.441-450, September 22-26, 1996
• 16: B. Sprunt, L. Sha and J. Lehoczky, "Aperiodic Task Scheduling for Hard Real-Time Systems," Real-Time Systems, vol. 1 (1), pp. 27--60, 1989.
• 17: N. Tracey , J. Clark , K. Mander , J. McDermid, An Automated Framework for Structural Test-Data Generation, Proceedings of the 13th IEEE international conference on Automated software engineering, p.285, October 13-16, 1998
• 18: M. Wall, "GAlib: A C++ Library of Genetic Algorithm Components," Massachusetts Institute of Technology, http://lancet.mit.edu/ga/dist/galibdoc.pdf, August, 1996.
• 19: Jian Zhang , S. C. Cheung, Automated test case generation for the stress testing of multimedia systems, Software—Practice & Experience, v.32 n.15, p.1411-1435, December 2002 [doi>10.1002/spe.487]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

General Terms:
Algorithms, Design, Experimentation, Performance, Reliability, Theory, Verification

Keywords:
genetic algorithms, schedulability theory