Fundamentals of Software Testing

Fall 2010

 

Course Number: CMSC737.

 

Meeting Times: Tue. Thu. - 8:00AM - 9:15AM (CSIC 1121).

 

Office Hours: Tue. Thu. - 9:15AM - 11:00AM (4115 A. V. Williams Building) Other meetings may be scheduled individually and held over Skype and Phone.

 

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: 10% midterm exam 1, 10% midterm exam 2, 5% presentation, 25% final exam, 50% class project.

 

Credits: 3

 

Prerequisites: Software engineering CMSC435 or equivalent.

 

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

 

Student Presentations: All students are required to present a topic related to software testing. You must prepare slides and select a date for your presentation. Group presentations are encouraged if the selected topic is broad enough.

 

Syllabus: The following topics will be discussed (this list is tentative and subject to change).

• Introduction to software testing
• [Aug. 31] 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
• Testing: a roadmap, Mary Jean Harrold, Proceedings of the conference on the future of Software engineering May 2000.
• Testing: principles and practice, Stephen R. Schach, ACM Computing Surveys, (CSUR) March 1996, Volume 28 Issue 1.
• [Sep. 2] The relationship between sampling and testing – an Introduction
• [Sep. 7] The role of experimentation in testing – an Introduction
• [Sep. 9] Designing an experiment to compare test adequacy criteria
• Test-case Generation
• Contents: Blackbox testing; sampling the program's input space, white-box testing; path-testing; branch and predicate testing, GUI Testing.
• Reading List
• [Sep. 14] 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. Slides: 3.pdf
• [Sep. 14] 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. Slides: 4.pdf
• [Sep. 16, 21] 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. Slides: 5.pdf
• [Sep. 21] A heuristic approach for test case generation, Kai-Hsiung Chang, W. Homer Carlisle, James H. Cross, II, David B. Brown, Proceedings of the 19th annual conference on Computer Science, 1991, Page(s): 174–180. Slides: 6.pdf
• [Sep. 21, 23] Hierarchical GUI Test Case Generation Using Automated Planning, by Atif M. Memon, Martha E. Pollack, and Mary Lou Soffa., IEEE Trans. Softw. Eng., vol. 27, no. 2, 2001, pp. 144-155, IEEE Press.
• [Sep. 23, 28, 30] Using a Pilot Study to Derive a GUI Model for Automated Testing, by Qing Xie and Atif M. Memon, ACM Trans. on Softw. Eng. and Method., 2008, ACM Press.
• [Sep. 30, Oct. 5] Feedback-based test-case generation
1. Using GUI Run-Time State as Feedback to Generate Test Cases, by Xun Yuan and Atif M. Memon. In ICSE '07: Proceedings of the 29th International Conference on Software Engineering, May 23-25, 2007, pp. 396-405.
2. Generating Event Sequence-Based Test Cases Using GUI Run-Time State Feedback, IEEE Transactions on Software Engineering.
• [Oct. 7] No Lecture in class. Please view the video on Model-based testing of Web Applications at the 3rd Google Test Automation Conference (GTAC 2008). The slides are available HERE. Here is the YouTube video.
• Test Adequacy I
• Contents: Test coverage and adequacy.
• Reading List
• [Oct. 12] General discussion and overview. Slides: 7.pdf
• [Oct. 12] STUDENT PRESENTATION (NOTE: Each student is required to fill this evaluation form for each presentation. The filled forms will be used for grading the presentation.)

o    Ray Chen; On DynInst.

• Test Adequacy II
•  [Oct. 14] Coverage criteria for GUI testing, by Atif M. Memon, Mary Lou Soffa, and Martha E. Pollack, ESEC/FSE-9: Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, (New York, NY, USA), 2001, pp. 256-267.
• [Oct. 14] STUDENT PRESENTATION

o    Robert Gove; Mobile usability testing; SOURCES:

·       Henry Been-Lirn Duh, Gerald C. B. Tan, and Vivian Hsueh-hua Chen. Usability evaluation for mobile device: a comparison of laboratory and eld tests. In MobileHCI '06: Proceedings of the 8th conference on Human-computer interaction with mobile devices and services, pages 181-186, New York, NY, USA, 2006. ACM.

·         Christian Monrad Nielsen, Michael Overgaard, Michael Bach Pedersen, Jan Stage, and Sigge Stenild. It's worth the hassle!: the added value of evaluating the usability of mobile systems in the eld. In NordiCHI '06: Proceedings of the 4th Nordic conference on Human-computer interaction, pages 272-280, New York, NY, USA, 2006. ACM.

·         Henry Been-Lirn Duh, Gerald C. B. Tan, and Vivian Hsueh-hua Chen. Usability evaluation for mobile device: a comparison of laboratory and eld tests. In MobileHCI '06: Proceedings of the 8th conference on Human-computer interaction with mobile devices and services, pages 181-186, New York, NY, USA, 2006. ACM.

·         Rudy Schusteritsch, Carolyn Y.Wei, and Mark LaRosa. Towards the perfect infrastructure for usability testing on mobile devices. In CHI '07: CHI '07 extended abstracts on Human factors in computing systems, pages 1839-1844, New York, NY, USA, 2007. ACM.

• [Oct. 19] STUDENT PRESENTATION

o    Christoph Schulze; Web Testing; SOURCES: From formal requirements to automated web testing and prototyping, Ernesto Cid Brasil de Matos and Thiago C. Sousa, From the issue entitled "Special Issue ICFEM'09".

• [Oct. 21] MIDTERM EXAM 1
• [Oct. 26] STUDENT PRESENTATIONS
• Jorge Faytong; Prioritization of Software Tests;
• SOURCES:
1. An empirical study of incorporating cost into test suite reduction and prioritization
2. On the economics of requirements-based test case prioritization
3. An optimized change-driven regression testing selection strategy for binary Java applications
4. Configuration-aware regression testing: an empirical study of sampling and prioritization
5. Test case prioritization using ant colony optimization
• Test Adequacy III
•  [Oct. 28] Scott McMaster, Atif Memon, Call-Stack Coverage for GUI Test Suite Reduction, IEEE Transactions on Software Engineering, vol. 34,  no. 1,  pp. 99-115,  Jan.,  2008.
• [Oct. 28] STUDENT PRESENTATION
• Arnold Robin Fernandes; Testing Database Applications;
• SOURCES.
1. M.Y. Chan and S.C. Cheung, Testing Database Applications with SQL Semantics, in the Proceedings of 2nd International Symposium on Cooperative Database Systems for Advanced Applications (CODAS'99), Wollongong, Australia, March 1999, pp. 363-374
2. "Testing Database Applications" by Carsten Binnig, Donald Kossmann and Eric Lo.
• Test Adequacy IV
•  [Nov. 2] “GUI Interaction Testing: Incorporating Event Context” by Xun Yuan, Myra B. Cohen, and Atif M. Memon, IEEE Transactions on Software Engineering.
• [Nov. 4] STUDENT PRESENTATION
• Raul David Guerra and Khoa Doan; Symbolic execution and program testing;
• SOURCES
1. J. C. King. Symbolic execution and program testing. Cmmunications of the ACM, 19(7):385~V394, July 1976.
2. M. Latendresse. Fast symbolic evaluation of C/C++ Preprocessing using conditional values.  In Proceedings of the Seventh European Conference on Software Maintenance and Reengineering (CSMR~R03), pages 170~V179, March 2003.
3. G. Muller and U. P. Schultz. Harissa: A hybrid approach to Java execution. IEEE Software, 16(2):44~V51, 1999.
• Test Oracles I
•  [Nov. 9] General discussion and overview. Slides: 9.pdf
•  [Nov. 9] Qing Xie and Atif M. Memon, Designing and comparing automated test oracles for GUI-based software applications, ACM Transactions on Software Engineering and Methodology, vol. 16, no. 1, 2007.
• [Nov. 9] STUDENT PRESENTATION
• Vasileios Lekakis; Automated Test Generation; Cadar et al. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. USENIX  (OSDI) (2008).
• Regression Testing I
•  [Nov. 11] 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. Slides: 8.pdf
• [Nov. 11] STUDENT PRESENTATION
• Christopher Neylan; Testing for Security;
• SOURCES
1. B. Arkin, S. Stender, and G. McGraw. "Software penetration testing". *Security & Privacy*, 2005.* *IEEE, vol.3, no.1, pp.84-87, Jan-Feb 2005. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.1308&rep=rep1&type=pdf
2. D. Wenliang and A.P. Mathur. "Testing for software vulnerability using environment perturbation". In *Proceedings International Conference on **Dependable Systems and Networks*, 2000 (DSN '00)*. *pp.603-612, 2000. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.4464&rep=rep1&type=pdf
3. P. Bisht, T. Hinrichs, N. Skrupsky, R. Bobrowicz, and V. N. Venkatakrishnan. "NoTamper: automatic blackbox detection of parameter tampering opportunities in web applications". In *Proceedings of the 17th ACM conference on Computer and communications security*, 2010 (CCS '10). ACM, New York, NY, USA, 607-618. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.171.97&rep=rep1&type=pdf
• [Nov. 16] STUDENT PRESENTATIONS
• Jiarong Jiang; Machine Learning and Software Testing;
• SOURCES
1. Zheng, A., Jordan,M., Liblit, B., Naik, M., Aiken, A.: Statistical debugging: simultaneous identification of multiple bugs.  In ICML 2006.
• Ethar Ibrahim; Network Measures in Testing;
• SOURCES.
1. Aye Tosun, Burak Turhan, and Aye Bener "Validation of Network Measures as Indicators of Defective Modules in Software Systems", Proceedings of the 5th International Conference on Predictor Models in Software Engineering 2009.
2. Thomas Zimmermann, Nachiappan Nagappan "Predicting defects using network analysis on dependency graphs", ICSE 2008.
3. Ethar Elsaka, Walaa Eldin Moustafa, and Bao Nguyen, and Atif Memon "A Social Network-Based Approach for GUI Testing,"TESTing Techniques & Experimentation Benchmarks for Event-Driven Software (TESTBEDS 2010).
• [Nov. 18] MIDTERM EXAM 2
• [Nov. 23] STUDENT PRESENTATIONS
• Teng Long; Component Compatibility Testing;
• SOURCES.
1. “Prioritizing Component Compatibility Tests via User Preferences” by Il-Chul Yoon, Alan Sussman and Atif Memon, and Adam Porter, in ICSM '09: Proceedings of the 23rd IEEE International Conference on Software Maintenance, (Alberta, Canada), 2009. Download: PDF.
2. “Effective and Scalable Software Compatibility Testing” by Il-Chul Yoon, Alan Sussman and Atif M. Memon, and Adam Porter, in ISSTA '08: Proceedings of the International Symposium on Software Testing and Analysis, (Washington DC, USA), 2008. Download: PDF.
3. “Direct-Dependency-based Software Compatibility Testing” by Il-Chul Yoon, Alan Sussman and Atif M. Memon, and Adam Porter, in ASE '07: Proceedings of the 22nd IEEE international conference on Automated software engineering, (Washington, DC, USA), 2007. Download: PDF.
• Leslie Milton; Testing Spreadsheets;
• SOURCES
1. Automated Test Case Generation for Spreadsheets
2. An Empirical Evaluation of a Testing and Debugging Methodology for Excel
• [Nov. 30] STUDENT PRESENTATIONS
• Jeesanth Thayavalliyil; Testing Web Applications;
• SOURCES.
1. Modelling methods for web application verification and testing: state of the art, Manar H. Alalfi, James R. Cordy and Thomas R. Dean
• Jayant Kumar; Test Adequacy Survey; 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.
• [Dec. 2] STUDENT PRESENTATIONS
• Richard B. Johnson; Load Testing;
• SOURCES.
1. Load Testing of Web Sites, Daniel A. Menasc, http://cs.gmu.edu/~menasce/papers/IEEE-IC-LoadTesting-July-2002.pdf
2. Load-Testing Web Applications, J.D. Meier, Carlos Farre, Prashant Bansode, Scott Barber, and Dennis Rea, http://msdn.microsoft.com/en-us/library/bb924372.aspx
• Naga Prathyusha Kanala; Bounded Exhaustive Testing;
• SOURCES.
1. Software Assurance by Bounded Exhaustive Testing, by D. Coppit (ISSTA 2004).
• [Dec. 7] Student Project Presentations

 

 

 

 

 

 

• [Dec. 9] Student Project Presentations

 

•  [Dec. 17] FINAL EXAM CSI 1121 Fri, Dec 17 10:30 am - 12:30 pm
• Exam will cover entire course content. It is an open book/notes exam.

 

Course Project (Studying the Role of Configurations in Testing)

[NOTE: This is the standard project for this class to be done individually. If you don’t want to do this project, you are welcome to propose your own. I have some project ideas too; feel free to stop by and discuss. We will have to agree on a project together with a grading policy.]

Summary: A major problem with software testing is that some bugs are difficult to replicate. That is, a tester finds a bug and reports it; but a developer fails to reproduce the bug. This problem of “nondeterministic” bugs is related to variation in software configurations (a combination of hardware, OS, run-time environment, memory). For example, a tester (or an end-user) who is running Java version 6, update 20 encounters a problem in a Java application; reports it; the developer, running Java version 6, update 21 attempts to reproduce the bug but fails. The reason is that the bug is masked by the Java update. In this project, we will study the issues that surround such problems.

 

Phase 1

Goal: Downloading and running all the applications.

Procedure: In this phase, you need to demonstrate that you are able to run four applications (JFCRipper, GUIStructure2GraphConvert, TestCaseGenerator, JFCReplayer) in GUITAR (use the application in http://guitar.svn.sourceforge.net/viewvc/guitar/examples/RadioButton/ as input). The source code for all these applications resides in a Subversion repository that can be viewed at http://guitar.svn.sourceforge.net/viewvc/guitar/. Please refer to https://sourceforge.net/projects/guitar/develop for additional help with Subversion. Each application (let’s call it foo for fun) resides in the folder foo.tool/ in the repository. Checkout this folder, for each application, and read its README.txt file. You will find more information about the modules that foo uses for building and execution. You will also find instructions on how to build and run foo.

Deliverables: There are no deliverables for this phase. Points will be awarded for demos.

Grading session: During the grading session, you will have access to a new machine (Windows or Linux) that is connected to the Internet. You will have to download, build, and execute all four applications and run them on all the inputs. You will also need to install Ant, Subversion, Java, and any other tools needed to run the applications. Each application is worth 10 points.

Points: 40

Due on or before Sep. 14 by 2:00pm. [Late submission policy – you lose 20% (of the maximum points) per day]

Phase 2

Goal: Replicating http://comet.unl.edu/benchmarks.php?q=group&g=umd.length1-2.efg.2010 and obtaining coverage (statement and branch) reports.

Procedure: Visit the page http://comet.unl.edu/benchmarks.php?q=group&g=umd.length1-2.efg.2010 and download the benchmark. Regenerate all the artifacts in this benchmark using the same configuration (Linux version 2.6.31-19-generic Ubuntu 9.10, Java 1.6 update 15, Gnome 2.28.0) described in the benchmark document. Store these regenerated artifacts in a folder (Original/) using the structure used in the benchmark. Add coverage (statement and branch) reports for the test cases, both at test case level and test suite level. Select four NEW unique platform configurations (ensure that they have not already been selected by another student; see table below) and regenerate all artifacts again; store them in new folders (New1/, New2/, New3/, New4/); also generate coverage (statement and branch) reports. Document any differences found between the artifacts and coverage (differences.txt), if any, and explain their causes.

 

Deliverables: Original/, New1/, New2/, New3/, New4/, and differences.txt.

Grading session: Based on a meeting and discussion. You may be asked to regenerate the artifacts for a new configuration.

Points: 200 (50 per new configuration plus discussion).

Due on or before Oct. 5 by 2:00pm. [Late submission policy – you lose 20% (of the maximum points) per day]

Phase 3

Goal: Obtaining fault matrices, one for each configuration.

Procedure: Execute all test cases from the previous phase and determine if any crash (terminate unexpectedly or throw an uncaught exception) the application. Find the causes of the crash and document them. If none cause a crash, then generate new tests that cause a crash (obtain their statement and branch coverage reports); or prove that no tests can cause a crash.

Deliverables: Four fault matrices, new test cases (if any) with coverage reports, and causes of crashes.

Grading session: Based on individual meeting and discussion. You may be asked to regenerate a part of the fault matrix for a new configuration.

Points: 200 (50 per new configuration plus document).

Due on or before Nov. 9 by 2:00pm. [Late submission policy – you lose 20% (of the maximum points) per day]

Phase 4

Goal: Improving the tests and obtaining new fault matrices.

Procedure: The test cases use “default” strings for text-fields. Improve the test cases by replacing the default strings with new values obtained using the category-partition method. Execute the test cases and determine if any crash (terminate unexpectedly or throw an uncaught exception) the application. Find the causes of the crash and document them. If none cause a crash, then revise the text strings so that they crash the application; or prove that no text strings will ever cause the application to crash. Report the test coverage.

Deliverables: New tests and their coverage, four fault matrices, and causes of crashes.

Grading session: Based on individual meeting and discussion. You may be asked to regenerate a part of the fault matrix for a new configuration.

Points: 200 (50 per new configuration plus document).

Due on or before Dec. 1 by 2:00pm. [Late submission policy – you lose 20% (of the maximum points) per day]