Fundamentals of Software Testing

Fall 2005

Course Number: CMSC838M. In the future, this course will be listed as CMSC737.

Meeting Times: Tue. Thu. - 9:30AM - 10:45AM (CSIC 2120)

Office Hours: Tue. Thu. - 10:45AM - 12:00PM (4115 A. V. Williams Building)

Catalog Course Description: This course will examine fundamental software testing and related program analysis techniques. In particular, the important phases of testing will be reviewed, emphasizing the significance of each phase when testing different types of software. The course will also include concepts such as test generation, test oracles, test coverage, regression testing, mutation testing, program analysis (e.g., program-flow and data-flow analysis), and test prioritization.

Course Summary: This course will examine fundamental software testing and program analysis techniques. In particular, the important phases of testing will be reviewed, emphasizing the significance of each phase when testing different types of software. Students will learn the state of the art in testing technology for object-oriented, component-based, concurrent, distributed, graphical-user interface, and web software. In addition, closely related concepts such as mutation testing and program analysis (e.g., program-flow and data-flow analysis) will also be studied. Emerging concepts such as test-case prioritization and their impact on testing will be examined. Students will gain hands-on testing/analysis experience via a multi-phase course project. By the end of this course, students should be familiar with the state-of-the-art in software testing. Students should also be aware of the major open research problems in testing.

The grade of the course will be determined as follows: 25% mid-term, 25% final exam, 50% project.

Credits: 3

Prerequisites: Software engineering CMSC435 or equivalent.

Status with respect to graduate program: MS qualifying course (Midterm+Final exam), PhD core (Software Engineering).

Syllabus: The following topics will be discussed. The reading lists are expected to evolve as new papers in these areas emerge.

  1. Introduction to software testing (1 week)
    • Contents: The need for testing; testing as an integral part of software engineering; software engineering processes and testing.
    • Slides: 1.pdf, 2.pdf
    • Reading List
      1. Testing: a roadmap, Mary Jean Harrold, Proceedings of the conference on the future of Software engineering May 2000.
      2. Introduction to special section on software testing, R. Hamlet, Communications of the ACM June 1988, Volume 31 Issue 6.
      3. Testing: principles and practice, Stephen R. Schach, ACM Computing Surveys, (CSUR) March 1996, Volume 28 Issue 1.
      4. Software safety: why, what, and how, Nancy G. Leveson, ACM Computing Surveys (CSUR) June 1986, Volume 18 Issue 2.
      5. Validation, Verification, and Testing of Computer Software, W. Richards Adrion, Martha A. Branstad, John C. Cherniavsky, ACM Computing Surveys (CSUR) June 1982, Volume 14 Issue 2.
  2. The overall testing process (2 weeks)
    • Contents: Test case generation; test oracles; test coverage.
    • Slides: 3.pdf.
    • Reading List
      1. The category-partition method for specifying and generating functional tests, T. J. Ostrand, M. J. Balcer, Communications of the ACM June 1988, Volume 31 Issue 6.
    • Tools
      1. Contents: JUnit; Bugzilla.
      2. Reading List
        1. Various documents at http://www.junit.org.
  1. Test case generation (3 weeks)
    • General test-case generation concepts
      1. Slides: 5.pdf, 7.pdf.
      2. Contents: Sampling the program's input space; path-testing; branch and predicate testing.
      3. Reading List
        1. A test generation strategy for pair-wise testing, Kuo-Chung Tai; Yu Lei, Software Engineering, IEEE Transactions on, Volume: 28 Issue: 1, Jan. 2002, Page(s): 109 -111.
        2. Predicate-based test generation for computer programs, Kuo-Chung Tai, Software Engineering, 1993. Proceedings of the 15th International Conference on, 1993, Page(s): 267 -276.
    • Testing object-oriented programs
      1. Contents: Challenges of testing object-oriented programs; inheritance; polymorphism.
      2. Slides: DISCUSSION.
      3. Reading List
        1. TACCLE: A Methodology for Object-Oriented Software Testing at the Class and Cluster Levels, Huo Yan Chen, T. H. Tse, T. Y. Chen, ACM Transactions on Software Engineering and Methodology, Vol. 10, No. 4, January 2001, Pages 56-109.
    • GUI testing
      1. Contents: event-flow model; event-space.
      2. Slides: 6.pdf.
      3. Reading List
        1. Hierarchical GUI test case generation using automated planning, Memon, A.M.; Pollack, M.E.; Soffa, M.L., Software Engineering, IEEE Transactions on, Volume: 27 Issue: 2, Feb. 2001, Page(s): 144 -155.
        2. Using a goal-driven approach to generate test cases for GUIs, Atif M. Memon, Martha E. Pollack, Mary Lou Soffa, Proceedings of the 21st international conference on Software engineering May 1999.
    • Data-flow testing
      1. Contents: Data definitions; data-use; def-use chains
      2. Slides: 12.pdf.
      3. Reading List
        1. Interprocedural data flow testing, M. Harrold, M. Soffa, ACM SIGSOFT Software Engineering Notes, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification November 1989, Volume 14 Issue 8.
        2. An applicable family of data flow testing criteria, Frankl, P.G.; Weyuker, E.J., Software Engineering, IEEE Transactions on, Volume: 14 Issue: 10, Oct. 1988, Page(s): 1483 -1498.
    • Web testing
      1. Contents: Challenges of testing web applications; load testing.
      2. Slides: DISCUSSION.
      3. Reading List
        1. Going Faster: Testing The Web Application Edward Hieatt and Robert Mee, IEEE SOFTWARE March/April 2002, pages 60-65.
  2. Test oracles (1 week)
    • Contents: The need for name spaces; specifications name space; implementation name space.
    • Slides: 13.pdf.
    • Reading List
      1. Automated test oracles for GUIs, Atif M. Memon, Martha E. Pollack, Mary Lou Soffa, ACM SIGSOFT Software Engineering Notes, Proceedings of the eighth international symposium on Foundations of software engineering for twenty-first century applications, November 2000, Volume 25 Issue 6.
      2. Specification-based test oracles for reactive systems, Debra J. Richardson, Stephanie Leif Aha, T. Owen O'Malley, Proceedings of the 14th international conference on Software engineering June 1992.
  1. Test coverage (2 weeks)
    • Contents: Code instrumentation; test prioritization.
    • Slides: 9.pdf, 10.pdf, 11.pdf, 14.pdf.
    • Reading List
      1. Software unit test coverage and adequacy, Hong Zhu, Patrick A. V. Hall, John H. R. May, ACM Computing Surveys (CSUR) December 1997, Volume 29 Issue 4.
      2. The evaluation of program-based software test data adequacy criteria, E. J. Weyuker, Communications of the ACM June 1988 Volume 31 Issue 6.
      3. Coverage criteria for GUI testing, Atif M. Memon, Mary Lou Soffa, Martha E. Pollack, ACM SIGSOFT Software Engineering Notes, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT symposium on Foundations of software engineering September 2001, Volume 26 Issue 5.
      4. Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria, Hutchins, M.; Foster, H.; Goradia, T.; Ostrand, T., Software Engineering, 1994. Proceedings. ICSE-16., 16th International Conference on, 1994, Page(s): 191-200.
  2. Regression testing (2 weeks)
    • Contents: Repairing test cases; obsolete test cases.
    • Slides: 15.pdf, 17.pdf.
    • Reading List
      1. An empirical study of regression test selection techniques, Todd L. Graves, Mary Jean Harrold, Jung-Min Kim, Adam Porter, Gregg Rothermel, ACM Transactions on Software Engineering and Methodology (TOSEM) April 2001, Volume 10 Issue 2.
      2. Regression testing of GUIs, Atif M. Memon, Mary Lou Soffa, September 2003, Proceedings of the 9th European software engineering conference held jointly with 10th ACM SIGSOFT international symposium on Foundations of software engineering.
  3. Mutation testing (2 weeks)
    • Contents: Mutants; fault seeding; defect estimation.
    • Slides: DISCUSSION.
    • Reading List
      1. Investigations of the Software Testing Coupling Effect, Jeff Offutt. ACM Transactions on Software Engineering Methodology, 1(1):3-18, January 1992.
      2. Practical Mutation Testing, Jeff Offutt. Twelfth International Conference on Testing Computer Software, pages 99-109, Washington, DC, June 1995.
      3. An Experimental Determination of Sufficient Mutant Operators, Jeff Offutt, Ammei Lee, Gregg Rothermel, Roland H. Untch, and Christian Zapf. ACM Transactions on Software Engineering Methodology, 5(2):99-118, April 1996.
  4. Experimentation in software testing (1 week)
    • Contents: How to conduct experiments; statistical analyses - ANOVA, Bonferroni test; threats to validity.
    • Slides: DISCUSSION.
    • Reading List
      1. On test suite composition and cost-effective regression testing, Gregg Rothermel, Sebastian Elbaum, Alexey G. Malishevsky, Praveen Kallakuri, Xuemei Qiu, July 2004, ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 13 Issue 3.

Sample project:

  • Phase 1: Black-box test-case generation - during week 2; take subject application with requirements document; create black-box test cases; create JUnit test cases; report bugs in a bug tracking tool.
  • Phase 2: White-box test-case generation and coverage - during week 4; use instrumenter; evaluate coverage; create additional white-box test cases to satisfy some coverage criteria.
  • Phase 3: Regression testing - during week 7; modify software with enhancements; regression test the new software; report new bugs.
  • Phase 4: Mutation testing - during week 10; create mutants; run test cases to kill mutants; generate additional test cases to kill all mutants.