Fine-Grained Assertion-Based Test Selection

Similar to state-of-the-art RTS tools, HyRTS [12] and Ekstazi [9], we detect code changes by comparing checksums. However, instead of tracing bytecode files, we compute checksums for source code files directly. We perform source code analysis because our fine-grained technique requires computation at statement level for test code to collect dependencies, and statement level analysis for bytecode will be indirect and may increase analysis complexity.

The procedure to compute code changes is summarized in Algorithm 1. We trace code changes at multiple levels (i.e., method and class level). Given two versions of the code, we first compare the file-level checksums to detect the list of deleted, added, and changed files which are denoted by AF, DF, CF respectively at Line 1. Then for each file, we create class models to handle circumstances that one single file contains multiple classes (e.g., nested classes), although in most cases, there is one class per file (Line 2). We also handle enum types. Since enums can be treated as a special type of classes, we use class to represent both types in Algorithm 1. Intuitively, newly added classes (AC) and deleted classes (DC) are class-level changes, which are collected in the set $\delta^{c}$ at Line 3. Changed classes (CC) may include irrelevant changes that are not impacting the code, such as changes in comments, Javadoc, or indents. Such changes are excluded at the next step of the Algorithm (Line 4-12). For each changed class model, we separate the class body components into the following categories: class head (CH), methods (M) and other (OT). CH includes the class’s name, superclass or interfaces information. Methods (M) include all method declarations, including instance methods and constructors. Other (OT) includes other body declarations such as fields, except methods and classes. We store the smart checksums for each M, CH and OT separately.

The reason to maintain a separate category OT is that, unlike bytecode computation in which field changes are reflected in method-level changes [12], we need to consider changed fields explicitly in source code analysis. To reduce the analysis overhead, we handle field changes all together and transfer them into a class-level change, because a field may be used by multiple methods. Therefore, for each changed class, if the OT or CH checksum varies, the corresponding class will be marked as changed (Line 5-6). If there are only method checksum changes without OT or CH change, the added (AM), deleted (DM) and changed methods (CM) will be stored as method-level changes in the set $\delta^{m}$ (Line 7-10). We also compute look up changes [10, 12] for added and deleted methods based on the inheritance information at Line 9 for the sake of safety in our analysis. In the initial run, because no previous checksums are available, every class is treated as a new class with class-level changes and the whole test suite is executed once.

To perform fine-grained selection at the assertion level, we can not merely select the test assertion statement because there could be other test statements associated with the assertion that make it executable. For instance, in Figure 1, the test statement at Line 7 is associated with the assertion at Line 8, because the variable iPi is defined at Line 7 and used by Line 8. In this work, we call a code fragment that includes the targeted test assertion and the dependent statements as an assertion slice.

Using Figure 2 as an example, the test method ($m$) testExp’s assertion slices $\mathcal{A}_{m}$ are shown in the first three blocks. For the test statement $st$ at Line 3, $\mathcal{A}_{m}[st]$ contains one assertion slice shown in the first block. To obtain the assertion slices, we perform static intra-procedural backward slicing [15] for each test method based on the program dependence graph (PDG) using each assertion and its used variables as slicing criterion [16, 17, 18]. A PDG represents a procedure (i.e., the body of a test method) as a graph where nodes are statements or predicate expressions, and edges are control or data dependence. Generally speaking, test code has simpler structures than production code. Most test cases do not include conditionals such as if-else, for-loop, etc. To reduce the analysis overhead, we opted for only slicing test cases with explicit assertions and without conditional statements. Therefore, we apply data dependency analysis to create the PDG by capturing the variables used and defined for each test statement including the assertions. The global variables and methods annotated with @Before or @BeforeClass in test classes serve a purpose in points-to/alias analysis [17]; should always be included when executing the selected test entities, however, they do not need to be part of the data dependency analysis for individual test cases.

Since we target an object-oriented language (Java), we pay more attention to object variable aliases in our analysis. For instance, when an object variable objA in the assertion statement is selected as the slicing criterion and its reference is passed to a method or constructor of another object variable objB, objA’s state may be changed by objB’s methods [17, 18]. If objA is passed to any field of objB, when objA is changed, objB’s state can also change. To make sure the slices do not miss any statements as data dependencies, we make a conservative assumption that method calls will change the states of the caller object and objects passed as arguments, which means a method invocation statement $st$ is associated with the targeted assertion $asrt$ if a variable in $asrt$ is used by $st$ as a caller object or passed to $st$ as an argument. Because assertions are a particular type of statement, if an assertion $asrt_{1}$ prior to the targeted assertion $asrt_{2}$ has a data dependency on $asrt_{2}$, $asrt_{1}$ will also be included in the slice for $asrt_{2}$.

After obtaining the assertion slices, we collect test dependencies by capturing the method calls for each test statement. We instrument the production code to log the method signature for each production method invocation, and produce a separate set to keep track of method calls for each test statement inside test cases during test execution. For helper methods that are in test classes but are not test methods (i.e., without @Test annotation), we treat them the same way as production methods.

Performing code instrumentation to collect dependencies at run-time for each new program revision will be inefficient. To reduce the overhead, we instrument each production and test class at initial run $V_{0}$, and store the instrumented subject as a separate copy (shown as the gray box in Figure 3). When a new revision $V_{i}$ is ready, we only need to re-instrument the changed files computed by Algorithm 1 and synchronize them to the instrumented copy of the subject, and execute the affected tests on the instrumented subject after test selection. Therefore, the dependency collection process is separately executed on the instrumented subject, which does not interfere with the execution of the original subject.

We use $\mathcal{D}$ to denote all the test dependencies. For each test statement $st$, $\mathcal{D}(st)$ stands for a list of method invocations of $st$. Each method call is represented by its fully qualified method signature. Thus, it is easy to retrieve the class-level dependencies when needed.

In practice, some test features might pose safety or efficiency challenges in tracing dependencies for each test statement. For parameterized test classes (annotated with @RunWith(Parameterized.class)), the method calls invoked by each test statement may vary for different inputs. It will increase analysis complexity to trace dependencies for each test statement with consideration of different inputs. We opted for collecting dependencies for each parameterized test class by logging all the method calls for different parameters together into one dependency file. When the dependency file contains any changed methods, all the test cases under different parameters in the parameterized test class are selected for execution. For the test classes that use inheritance, since each subclass may inherit test methods from the super class that are not explicitly available in the subclass, the approach to collect dependencies at test statement level is unsafe because the method-calls invoked by the inherited test methods will be missing for the subclass. Therefore, for the test classes that use inheritance (including both subclasses and superclasses), we trace dependencies at the test class level by logging method calls for the whole test class execution. Moreover, when a test class contains test methods calling other tests, it is hard to isolate each test method. For this case, we collect dependencies at the test class level as well. We identify those test classes that are parameterized, use inheritance or contain test methods calling other tests during static source code analysis for code instrumentation. Then, to trace dependencies at the test class level, instead of inserting code to log method calls for each test statement, we insert code only at the beginning and the end of each test class to keep track of the method calls.

In addition to these specific test features, some test classes contain test methods that expect an exception to be thrown (e.g., annotated with @Test(expected=SomeException.class)). For those test methods, it is meaningless to trace method calls for each test statement, as the execution will be interrupted at a certain point and statements after that point will not be executed at all. Therefore, we collect dependencies for each test method instead. Moreover, in Section III-B, we choose to only slice the tests with explicit assertions and without conditional statements. For the test cases that contain conditional statements such as if-else or for-loop that are not sliced by the assertion slicing module, because they are not selected at fine-grained assertion level, it is sufficient to collect dependencies for each test method instead of each test statement to reduce overhead.

At this point, we have a comprehensive analysis of the test code through assertion slicing and code instrumentation. Based on the levels of dependency data collection and the availability of assertion slices, the test entities will be safely selected at different levels.

Algorithm 2 summarizes the procedure for our test selection. With the test dependencies $\mathcal{D}$ obtained by running the instrumented subject, the assertion slices $\mathcal{A}$ and the changes $\delta$ computed by Algorithm 1, the selected test entities $\Gamma$ for the current code revision can be computed by Algorithm 2. $\Gamma_{A}$, $\Gamma_{M}$, $\Gamma_{C}$ denote selected assertion slices, test methods and test classes, respectively. We categorize the code changes obtained from Algorithm 1 into two distinct sets: test code changes, denoted as $\delta_{T}$, and production code changes, denoted as $\delta_{P}$. For each changed test entity $t\in\delta_{T}$ which could be a modified or newly added test method or test class, its assertion slices need to be updated to align with the current code reversion (Line 2-3). Additionally, $\delta_{T}$ should also be selected for execution (Line 25). For each production code change $p\in\delta_{P}$, Line 6 computes the test entities $\mathcal{T}_{p}$ that depend on the production code change $p$ based on the dependency files in $\mathcal{D}$. Because there are some special cases that test dependencies are not collected at the test statement level (see Section III-C), the returned test entities $\mathcal{T}_{p}$ might contain test methods and test classes. For each affected test entity $t\in\mathcal{T}_{p}$, if $t$ is a test statement (Line 9), we retrieve the test method $m$ that contains $t$ (Line 10) and check if there are assertion slices available for the test method $m$ (Line 11). If assertion slices exist for $m$, all the assertion slices that contain $t$ are selected (Line 11-14). If there are no assertion slices for $m$, our selection is performed at the test method level (Line 16-17) to guarantee a safe selection. If test entity $t$ is not a test statement, $t$ is selected as the test method or test class instead (Line 20). Last but not least, all the selected test entities $\Gamma_{A}$, $\Gamma_{M}$, $\Gamma_{C}$, $\delta_{T}$ are used to rewrite their corresponding test classes to make sure only the selected assertions, methods or classes will be executed (Line 25). After the execution is finished, the test classes are restored to the original status, while the rewritten version is saved as a reference.

We implemented our approach as a tool called Selertion, which is written in Java. For our source code analysis, we build on top of Eclipse Java Development Tools (JDT) [19] to analyze and instrument source code. Our current implementation supports Java programs that use Maven and JUnit 4. In addition to the standard test assertions in JUnit, Selertion supports assertions written in popular frameworks such as AssertJ [20] and Google Truth [21]. At the initial run, Selertion takes the source code of the program, obtains assertion slices, instruments production and test code, and runs the instrumented program to obtain test dependencies. For any subsequent revision of the program, Selertion takes the new revision of the program as input and computes the changes by comparing checksums with the old revision. It instruments only the changed files and updates the changed assertion slices. It then selects tests at assertion level as the finest granularity where possible by analyzing the dependencies, assertion slices and change information. It then executes the selected tests. The code for our implementation is publicly available at [22].

Our search criteria for existing test selection techniques to compare with included tools that are available, runnable, and target Java/JUnit. We selected two state-of-the-art tools, namely HyRTS [12] and Ekstazi [9]. To the best of our knowledge, these are the exclusive options that currently meet our criteria. Significantly, they outperform older RTS techniques like FaultTracer [11], which exhibit slower performance and offer test method selection, as documented in prior research [9].

HyRTS conducts the analysis of test dependencies at either the method or class level and selects test entities at the test class level. Ekstazi analyzes production code to identify changes at the class level. Although the original paper [9] mentions the provision of both method and class-level selection, the Ekstazi tool [23] is currently available with default settings that primarily select tests at the test class level. Our technique collects test dependencies also at a mix of method and class level similar to HyRTS, however, it has the ability to select test entities at multiple levels from the coarse-grained class to the fine-grained assertion level based on its analysis of the test suite. Therefore, theoretically speaking, Selertion should be able to select tests more precisely than both HyRTS and Ekstazi. We empirically assess this in our evaluation.

We include a total of 11 subject systems. These subjects are selected based on their relevance to prior research on test assertion analysis [34, 14] and regression test selection [12] and their popularity on GitHub. To ensure fair comparison among Selertion, HyRTS and Ekstazi, our selection criteria include subjects that use Maven with executable and passing JUnit4 test cases. We focus on subjects with a test runtime of at least 30 seconds. As reported by others [12, 9], for lower test runtimes it can take more time to analyze the code than to execute the entire test suite.

The selected subjects and their characteristics are shown in Table I with the ascending order of their testing time. All the subjects are single-module projects, except Tika [30] and Accumulo [31]. Because some modules of these multi-module projects only have a few test cases, for simplicity, we choose the module with most test cases to analyze (i.e., tika-parsers module for Tika, core module for Accumulo). We examine the test suites for each subject and blacklist test classes that do not meet the selection criteria (e.g., test classes that mix JUnit3 and JUnit4 APIs in OpenTripPlanner). As some of the subjects are migrated to JUnit5 [35] recently, for consistency, we start from a revision that uses JUnit4 as the Head to collect 100 revisions before it, and remove revisions that fail to build or have no code changes. For the three subjects commons-exec, commons-net and commons-pool, which lack a sufficient number of revisions with substantial source code changes, we introduce changes artificially. To achieve this, we use a source code mutation generator called Major [36] to create random mutants in various production methods, thus introducing more prevalent source code changes. The selected subjects span different application domains and exhibit diverse code and test suite sizes. Table I presents the short hash under the Head column, and lines of code for both production and test code for the Head revision. We measure lines of code using Cloc [37]. The column Time details the average time required to execute all the tests using the build command (i.e., mvn test) for the revisions we analyzed, along with the average execution time for each test case. This table also presents information pertaining to test cases and test assertions that are further elaborated in the following subsection.

All our experiments are conducted on a macOS server with 2.4 GHz Quad-Core Intel Xeon processor and 64 GB of memory running OpenJDK 64-Bit version 1.8.0_212 and 11.