Safety of a smart classes-used regression test selection algorithm

Susannah Mansky, Elsa L. Gunter

Research output: Contribution to journalConference articlepeer-review


Regression Test Selection (RTS) algorithms select which tests to rerun on revised code, reducing the time required to check for newly introduced errors. An RTS algorithm is considered safe if and only if all deselected tests would have unchanged results. In this paper, we present a formal proof of safety of an RTS algorithm based on that used by Ekstazi [3], a Java library for regression testing. Ekstazi's algorithm adds print statements to JVM code in order to collect the names of classes used by a test during its execution on a program. When the program is changed, tests are only rerun if a class they used changed. The main insight in their algorithm is that not all uses of classes must be noted, as many necessarily require previous uses, such as when using an object previously created. The algorithm we formally define and prove safe here uses an instrumented semantics to collect touched classes in an even smaller set of locations. We identify problems with Ekstazi's current collection location set that make it not safe, then present a modified set that will make it equivalent to our safe set. The theorems given in this paper have been formalized in the theorem prover Isabelle over JinjaDCI [7], a semantics for a subset of Java and JVM including dynamic class initialization and static field and methods. We instrumented JinjaDCI's JVM semantics by giving a general definition for Collection Semantics, small-step semantics instrumented to collect information during execution. We also give a formal general definition of RTS algorithms, including a definition of safety.

Original languageEnglish (US)
Pages (from-to)51-73
Number of pages23
JournalElectronic Notes in Theoretical Computer Science
StatePublished - 2020
Event15th International Workshop on Logical and Semantic Frameworks, with Applications, LSFA 2020 - Virtual, Online, Brazil
Duration: Aug 27 2020Aug 28 2020


  • Interactive theorem proving
  • Java
  • Regression test selection
  • Small-step semantics

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Safety of a smart classes-used regression test selection algorithm'. Together they form a unique fingerprint.

Cite this