Automatic Testing of Sequential and Concurrent Substitutability


Languages with inheritance and polymorphism assume that a subclass instance can substitute a superclass instance without causing behavioral differences for clients of the superclass. However, programmers may accidentally create subclasses that are semantically incompatible with their superclasses. Such subclasses lead to bugs, because a programmer may assign a subclass instance to a superclass reference. This paper presents an automatic testing technique to reveal subclasses that cannot safely substitute their superclasses. The key idea is to generate generic tests that analyze the behavior of both the subclass and its superclass. If using the subclass leads to behavior that cannot occur with the superclass, the analysis reports a warning. We find a high percentage of widely used Java classes, including classes from JBoss, Eclipse, and Apache Commons Collections, to be unsafe substitutes for their superclasses: 30% of these classes lead to crashes, and even more have other behavioral differences.


A paper describing our approach has been accepted for presentation at ICSE 2013:

Michael Pradel and Thomas R. Gross
Automatic Testing of Sequential and Concurrent Substitutability
International Conference on Software Engineering (ICSE), 2013

Source Code and Experimental Data

The implementation is available in this Git repository.

To allow others to reproduce our results, details on all substitutability problems detected by the analysis are available for download. The package contains a text file per detected substitutability problem, containing the generated test that triggers the problem, details on the behavioral difference between superclass and subclass, and our classification of whether the problem is a bug or not.