Regression Testing Notes

Regression Testing

CS453 Automated Software Testing. Shin Yoo | COINSE@KAIST

Overview

  • What is “regression testing”?
  • Why do we need one?
  • Test Suite Minimisation
  • Regression Test-case Selection
  • Test Case Prioritisation
  • Regression Testing and Continuous Integration

Regression Fault Examples

  • iPhone 3GS reboots itself after 4-5 minutes in a phone call after iOS4 update.
  • Cannot arrow back to the next message after reading a text message on iPhone 6 after iOS11 install.

Regression Fault Definition

  • Regression fault occurs when new features or recent modifications to the software cause existing functionalities to break.
  • These faults are called “regressions,” indicating a return to an earlier bad state.

Regression Testing Scenario

  • Releasing a new version of software.
  • New features are thoroughly tested.
  • Need to check for regression faults.

Retest-All Approach

  • Simplest approach: retest-all.
  • Run all tests for old features, not just new ones.
  • Problem: Too many tests, leading to time constraints.

Inhibitive Cost of Retest-All

  • Industrial collaborators report that for a product of about 20,000 lines of code, the entire test suite requires seven weeks to run.
  • Factors contributing to the high cost:
    • Long Product History
    • Different Configurations
    • Types of Test Cases
    • Rothermel, R.H. Untch & M.J. Harrold (2001)

Regression Testing Techniques

  • Techniques to cope with the high cost of retest-all:
    • Test Suite Minimisation
    • Regression Test-case Selection
    • Test Case Prioritisation

Test Suite Minimisation

  • Problem: Regression test suite is too large.
  • Idea: There must be some redundant test cases.
  • Solution: Minimise (or reduce) the regression test suite by removing all the redundant tests.

Redundancy

  • Redundant: “…could be omitted without loss of meaning or function…” (New Oxford American Dictionary)
  • A test case can be labeled “redundant” only according to a specific criteria (e.g., DU-path, statement coverage).

Test Suite Minimisation as a Matrix Problem

  • Information can be expressed as a matrix.
  • Rows represent tests.
  • Columns represent things to tick off (branches, statements, DU-paths, etc.).
  • The problem becomes: find the subset of rows (tests) that, when combined, will cover the most columns.

Test Suite Minimisation and the Set-Cover Problem

  • The problem definition maps to the “set-cover” problem.
  • The problem is NP-complete, meaning there is no known efficient AND exact algorithm.
  • We rely on approximated heuristics.

Greedy Minimisation

  • Algorithm:
   greedy_minimisation(TestSuite T)
   S = {}
   while(True)
   find t in T s.t. S ∪ {t} covers max. cols.;
   if t exists:
   S = S ∪ {t}
   continue
   else:
   break
  • Example:
   I0: S = {}
   I1: S = {t0}
   I2: S = {t0, t2}

Cost Considerations in Minimisation

  • Different test cases have different costs (e.g., execution time).
  • Example: t2 takes 7 minutes to run, while t1 and t3 take 3 minutes each.
  • Is it still sensible to minimise to {t0, t2}?

Greedy Minimisation with Cost

  • Algorithm:
   greedy_minimisation(TestSuite T)
   S = {}
   while(True)
   find t in T w/ max. Δcov./cost of t;
   if t exists:
   S = S ∪ {t}
   continue
   else:
   break
  • Example:
   I0: S = {}
   I1: S = {t0}
   I2: S = {t0, t1}
   I3: S = {t0, t1, t3}

Multi-Objectiveness : Problems

  • “After performing minimisation, the test suite is still too big. What can I actually do in the next 6 hours?”
  • “I care not just code coverage, but something else too. Can I also achieve X with the minimised suite?”

Single Objective vs. Multi Objective

  • Single Objective: Choose test case with the highest block per time ratio.
    • Example: T1 (ratio = 2.0), T2 (ratio = 2 / 5 = 0.4) ∴ {T1, T2} (takes 9 hours).
  • Multi Objective: Considers multiple objectives such as execution time and coverage.
    • Uses techniques like Pareto Frontier to find optimal solutions.

Code Coverage Optimization

Two objectives

Fault Coverage Optimization

Two objectives

Regression Test-case Selection

  • Problem: Regression test suite is too large.
  • Idea: Not all of your tests are related to the recent changes in software.
  • Solution: Precisely select only those tests that will actually execute the changed part of your software.

Determining Relevant Tests

  • You have changed program P into P’.
  • You have a test suite T; you should also have “execution trace” of all the tests in T (i.e. a mapping from tests to statements/branches/etc that they execute) w.r.t. original P.
  • Now pick your favourite methods, ‘cause there are tons :)

Textual Difference

  • Just use stock Unix tool, diff
  • Line 20 was modified into 2 lines; execute all tests that includes line 20 in their trace.

Graph Walking

  • Uses Control Flow Graph (CFG) that you already learned.
  • Determine which test would be best to test P->P’.

Graph Walking (Rothermel & Harrold, 1993)

  • Example:
  • P and P’ start to differ from ➁. Therefore, any test that executes ➁ should be selected to test the change. We select {t0}.

Other Techniques

  • Design artefacts (UML), data-flow analysis, path analysis, symbolic execution and many other techniques have been applied to aid precise selection of tests.

Safe Selection

  • Selection techniques do not consider the cost of tests.
  • They try to be “safe”, i.e., try to execute ALL tests that have the remotest possibility of revealing a fault related to the recent modification.
  • Realistically, by “the remotest possibility” we mean that the test executes the modified parts of the program; we do not know any more than that!

Difficulties in Test Case Selection

  • Data collection: collecting execution traces can be a hard task - especially if your system is big and consists of several different languages.
  • Non-executable modifications: things like configuration changes can be tricky to analyse.
  • Safety can be expensive: what if your safe selection is still too expensive to run?

Test Case Prioritisation

  • The Problem: Your regression test suite is too large.
  • The Idea: Let’s execute tests following the order of importance.
  • The Solution: Prioritise your test suite so that you get the most out of your regression testing whenever it gets stopped.

Simple Prioritisation Tips

  • You built your test suite by adding new test case whenever you added new feature: they are ordered from t1 to t100.
  • Without using any complicated technique at all, which order will you execute your test cases in?
    • Backwards: newer faults are more likely to be detected by newer test.
    • Random: choose the next test randomly.
    • Both have good chance of being better than the given order (0 to 100).

Ideal Test Case Prioritisation

  • Suppose we knew about all the faults in advance (impossible, yes, but let’s pretend).
  • Which test would you run first if you knew this? What next?
  • Obviously, it is t2 followed by t4.

Surrogate for Faults

  • Again, we do not know about all the faults in advance; therefore, the ideal ordering (one that finds all known faults as soon as possible) is not feasible.
  • Instead, we maximise the early realisation of some surrogate.
  • Most common one is coverage; the assumption is that, if we cover the program as much/as early as possible, we will also maximise the chance of early fault detection.

Surrogate Approach

  • It does not change things much; instead of trying to detect each fault, we try to cover each statement(branch/block/etc).
  • The ideal ordering still begins with t2-t4.
  • After t4, we reset the coverage counter and start again, which gives t1; similarly, t0 and t3.

Average Percentage of Fault Detection (APFD)

  • Measures how quickly your prioritisation detected the faults.
  • Intuitively, the metric measures the area beneath.

Cost Considerations in Prioritisation

  • Suppose test t0 achieves 100% code coverage in 5 hours. Tests t1 to t3 collectively achieve 80% coverage in 2 hours. Which one would you prioritise?

APFDc (Elbaum et al., 2001)

  • APFD with cost.
  • C achieves 70% coverage in 7 minutes.
  • E achieves 30% coverage in 30 seconds.
  • As a result, executing E first gives higher APFDc.

Clustering for Testing

  • One versatile tool: clustering.
  • A technique that groups objects such that objects in the same group are the most similar to each other (there are many approaches to this).
  • Benefits for testing:
    • Reduces the conceptual size of test suites (i.e. tester can think about clusters, not test cases)
    • Provides insights into what is the most common behaviour

Diversity Based Prioritization

  • Leon & Podgurski, ISSRE 2003
  • Given a distance metric that can quantify distances between test executions, you can both cluster and visualise the diversity within a test suite

Clustering Tests

  • Yoo et al., ISSTA 2009
  • Fault-detecting test can be executed earlier.
  • Human engineer can compare buckets, not tests.
  • Fault detected by a test with small coverage contribution

Similarity Measure

  • Clustering only makes sense if we can measure true similarity between test cases
  • Semantic measure
  • State of the art is largely based on syntactic measures (meaning coverage, yet again)
  • Can we do better?

Summary of Techniques

  • Minimisation: keyword is redundancy - it saves effort but you are putting yourself at the mercy of the criterion you are minimising with.
  • Selection: keyword is safety - can be expensive; you want to be conservative and execute any test that has the potential to reveal a fault regarding recent changes.
  • Prioritisation: keyword is asap/surrogate - you want to maximise the number of faults you detect early on; since you do not know faults in advance, you need to come up with a smart surrogate.

Continuous Integration (CI)

  • CI means to merge all developer working copies into a single mainline daily, or even more frequently.
  • Developers usually ensure that their commits are correct by executing test cases that are directly relevant at their local machines. This is sometimes called pre-commit testing.
  • Once changes are merged, the CI system automatically executes all relevant test cases, to ensure that individual changes correctly work with each other. This is sometimes called post-commit testing.

Regression Testing and Cloud Computing

  • All regression testing techniques we looked at assume limited resource for testing, hence the need for optimisation.
  • The elasticity of cloud computing has a significant implication on the way these techniques are used.
  • What happens if you can use unrestricted amount of computing resources?

Impact of Cloud Resources

  • If all test cases have to be executed sequentially, we have to optimise the regression testing process as much as possible, to get the most out of the limited testing resources.
  • If all test cases can be executed in parallel, the time needed for testing is only as long as the longest test execution.

Continued Relevance of Techniques

  • Many techniques are still meaningful even when test cases are executed in parallel.
  • Test suite minimisation can still save redundant cloud computing cost.
  • Impact analysis used by safe test case selection is useful for many other applications, such as automated debugging.
  • There are cases when test cases have to be executed sequentially: for example, pre-commit testing done at individual developer machines.

Redefining Prioritisation in Large Environments

  • In very large development environments, the CI (Continuous Integration) pipeline is easily flooded with commits.
  • Prioritising test cases within test suites makes little impact at this scale.
  • Instead, prioritising commits to test has been proposed.

History Based Prioritisation

  • The proposed technique is essentially history based prioritisation: commits relevant to test cases that have recently failed are given higher priority. If tests really fail, this ensures quicker feedback to the responsible developers.

Assumptions of History Based Prioritisation

  • Commits are independent from each other. In high volume environment, this is not unrealistic.
  • Relationships between code and test cases are known in advance (i.e., which test covers which parts of the code).

Regression Testing and CI

  • Modern software development requires increasingly shorter release cycles: time-to-market is extremely critical.
  • Consequently, test executions are more frequently needed.
  • While the CI environment requires adaptations, regression testing techniques are definitely relevant when test cases are repeatedly executed. In some sense, all testing is like regression testing.

Reference

  • S. Yoo and M. Harman. Regression testing minimisation, selection and prioritisation: A survey. Software Testing, Verification, and Reliability, 22(2):67–120, March 2012.