The class are considered Super and Sub, then


The purpose of this study is about overcoming the
problems which are faced by the concept called Substitutability. For instance, the
problem is substituting the incompatible subclass instance to the superclass reference,
which is called unsafe substitute and if a subclass instance is substituted
when a super class instance is expected and everything has worked fine then
it’s a safe substitute. Substitutability is generally used in sequential programs
but it also important in parallel programs, hence this concept is used in
parallel programs with help of subclass instance shared by multiple threads. To
find the unsafe substitutes, an automatic testing technique is presented in
which two class are considered Super and Sub, then Super is considered as an
oracle for Sub and if Sub behaves differently from Super then it reports a
warning. Then two variants called Output oracle and Crash oracle are created
under this oracle, if the sub’s output is differed from super then output
oracle is triggered and if any crash occur in sub which does not occur in super
then crash oracle is triggered. This analysis is simple, precise and incomplete
and it can be used for both sequential and concurrent programs.

            For finding the unsafe substitutes
generic tests was used where calls are combine into tests and method name,
input variables and optional output variables are used in the test. The calls
in a test are focused on a single object called as object under test(OUT). To compare
Super and Sub, tests are requiring which check both Super and Sub’s OUTs
behaviour. This test is called generic test, in this static type variable is
Super and dynamic variable can be either Super or Sub. If static type Super
involves OUT to call, then it is type-compatible for both Super and Sub.
Generally, a generic test has two parts in which the first part creates the OUT
and the other one decides OUTs runtime type i.e. Super or Sub. It is also important
that the constructors which are for comparing the Super and Sub should be
equivalent. For the finding the equivalent constructors therefore the concept
called constructor mapping is used. Then the test generator can be designed for
individual or both the sequential and concurrent tests depending on the

            In a generic test, the superclass
oracle shows that generic tests determine an unsafe substitute for Super or
not. The superclass oracle uses the visible behaviour of the both the classes
Super and Sub, then produces two variants called output oracle and crash oracle.
These two focuses on the revealing the unsafe substitutes i.e. output-diverging
substitutes and crash substitutes and generic test t is given as input for both
the oracles. The output oracle is used to check that a generic test reveals a
Sub as an output-diverging substitute for Super. The oracle executes generic
tests both Super and Sub and their return values are stored as results. In
sequential tests it has only one output sequence when it is assumed to be deterministic
execution whereas in concurrent test it has multiple output sequence due to its
non-deterministic scheduling. The oracle reports a warning when a sequence of
return values exists only with Sub because Sub is an output-diverging
substitute of Super. The crash oracle is used to check that a generic test
reveals Subclass is a crashing substitute. The crash oracle shows warning when
a subclass may lead to a deadlock or an uncaught exception while superclass
executes successfully. In crash oracle there may be one or more failures while
executing Sub, but it does not mean that it is because Sub implemented
incorrectly. To find the failures which are corresponding to sub, the oracle
executes test on Super’s constructor.

To implement the above approach the source code or
byte code is given as an input and reported unsafe subclasses given as an
output. A helper tool is also implemented to find all superclass-subclass pairs
and to perform constructor mapping. To implement superclass oracle, a Java Path
Finder(JPF) is used which is also used for analysing concurrent execution. But
there are some limitations for JPF i.e. it takes more time even for executing
two concurrent threads in which each having single method call. Therefore, after
the evaluation of the approach it has been found that output-diverging
substitutes are more compared to crash substitutes and developers are bother about
crash substitutes. The warnings which are reported in crash oracle are due to
bugs which is expected, whereas in output oracle most of the warnings are false
positive. Most of the bugs encountered in output oracle are also found in crash
oracle therefore, crash oracle is recommended as default as it finds maximum
number of detected bugs and does not report any false positives whereas, output
oracle finds some additional bugs and reports false positives.

The feedback from the developers confirmed that the unsafe
substitutes should be fixed because the developers care about substitutability
problems. When it comes to performance, it takes 41 seconds on average to find
crashing substitute and 19 seconds for output-diverging substitute in sequentially
used classes whereas in concurrently used classes it takes 21 minutes on
average to find crashing substitute and 108 minutes for output-diverging
substitute. There are some limitations for this approach firstly, the effectiveness
depends on the performance of test generator which should exercise analysed classes.
Secondly, the approach depends upon the heuristic constructor mappings which result
in false positives and are encountered in output oracle. Thirdly this approach
works well with the library classes not with the closed programs.

This approach is related to behavioural subtyping and
the substitution property. There are few models which are proposed upon the inheritance
and polymorphism in which it describes about subclass that modifies by the
superclass which is incompatible whereas, this type of problems is
automatically detected in the given approach. Mc Keeman proposed a model called
differential testing in which equivalent programs are tested, like in same
language comparing multiple compilers with each other and this model also tests
system program and refactoring engines. The given approach analyses software at
class-level rather than program level which is a finer level of granularity.

In conclusion, Unsafe substitutes are considered as a
serious issue in a software development industry therefore in this approach unsafe
substitutes are identified from their superclasses. This approach automatically
reports the superclass abnormal behaviour for instance, crashes or when
reference points to subclass instance. This approach also ensures correctness
in both sequential and concurrent programs.