Type: Evaluation Essays
Sample donated: Renee Gutierrez
Last updated: April 23, 2019
The purpose of this study is about overcoming theproblems which are faced by the concept called Substitutability. For instance, theproblem is substituting the incompatible subclass instance to the superclass reference,which is called unsafe substitute and if a subclass instance is substitutedwhen a super class instance is expected and everything has worked fine thenit’s a safe substitute. Substitutability is generally used in sequential programsbut it also important in parallel programs, hence this concept is used inparallel programs with help of subclass instance shared by multiple threads. Tofind the unsafe substitutes, an automatic testing technique is presented inwhich two class are considered Super and Sub, then Super is considered as anoracle for Sub and if Sub behaves differently from Super then it reports awarning. Then two variants called Output oracle and Crash oracle are createdunder this oracle, if the sub’s output is differed from super then outputoracle is triggered and if any crash occur in sub which does not occur in superthen crash oracle is triggered.
This analysis is simple, precise and incompleteand it can be used for both sequential and concurrent programs. For finding the unsafe substitutesgeneric tests was used where calls are combine into tests and method name,input variables and optional output variables are used in the test. The callsin a test are focused on a single object called as object under test(OUT).
To compareSuper and Sub, tests are requiring which check both Super and Sub’s OUTsbehaviour. This test is called generic test, in this static type variable isSuper and dynamic variable can be either Super or Sub. If static type Superinvolves 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 OUTand the other one decides OUTs runtime type i.e. Super or Sub. It is also importantthat the constructors which are for comparing the Super and Sub should beequivalent. For the finding the equivalent constructors therefore the conceptcalled constructor mapping is used. Then the test generator can be designed forindividual or both the sequential and concurrent tests depending on therequirement. In a generic test, the superclassoracle shows that generic tests determine an unsafe substitute for Super ornot. The superclass oracle uses the visible behaviour of the both the classesSuper and Sub, then produces two variants called output oracle and crash oracle.
These two focuses on the revealing the unsafe substitutes i.e. output-divergingsubstitutes and crash substitutes and generic test t is given as input for boththe oracles. The output oracle is used to check that a generic test reveals aSub as an output-diverging substitute for Super. The oracle executes generictests both Super and Sub and their return values are stored as results. Insequential tests it has only one output sequence when it is assumed to be deterministicexecution whereas in concurrent test it has multiple output sequence due to itsnon-deterministic scheduling. The oracle reports a warning when a sequence ofreturn values exists only with Sub because Sub is an output-divergingsubstitute of Super.
The crash oracle is used to check that a generic testreveals Subclass is a crashing substitute. The crash oracle shows warning whena subclass may lead to a deadlock or an uncaught exception while superclassexecutes successfully. In crash oracle there may be one or more failures whileexecuting Sub, but it does not mean that it is because Sub implementedincorrectly. To find the failures which are corresponding to sub, the oracleexecutes test on Super’s constructor.
To implement the above approach the source code orbyte code is given as an input and reported unsafe subclasses given as anoutput. A helper tool is also implemented to find all superclass-subclass pairsand to perform constructor mapping. To implement superclass oracle, a Java PathFinder(JPF) is used which is also used for analysing concurrent execution. Butthere are some limitations for JPF i.e. it takes more time even for executingtwo concurrent threads in which each having single method call. Therefore, afterthe evaluation of the approach it has been found that output-divergingsubstitutes are more compared to crash substitutes and developers are bother aboutcrash substitutes.
The warnings which are reported in crash oracle are due tobugs which is expected, whereas in output oracle most of the warnings are falsepositive. Most of the bugs encountered in output oracle are also found in crashoracle therefore, crash oracle is recommended as default as it finds maximumnumber of detected bugs and does not report any false positives whereas, outputoracle finds some additional bugs and reports false positives.The feedback from the developers confirmed that the unsafesubstitutes should be fixed because the developers care about substitutabilityproblems.
When it comes to performance, it takes 41 seconds on average to findcrashing substitute and 19 seconds for output-diverging substitute in sequentiallyused classes whereas in concurrently used classes it takes 21 minutes onaverage to find crashing substitute and 108 minutes for output-divergingsubstitute. There are some limitations for this approach firstly, the effectivenessdepends on the performance of test generator which should exercise analysed classes.Secondly, the approach depends upon the heuristic constructor mappings which resultin false positives and are encountered in output oracle. Thirdly this approachworks well with the library classes not with the closed programs. This approach is related to behavioural subtyping andthe substitution property. There are few models which are proposed upon the inheritanceand polymorphism in which it describes about subclass that modifies by thesuperclass which is incompatible whereas, this type of problems isautomatically detected in the given approach.
Mc Keeman proposed a model calleddifferential testing in which equivalent programs are tested, like in samelanguage comparing multiple compilers with each other and this model also testssystem program and refactoring engines. The given approach analyses software atclass-level rather than program level which is a finer level of granularity.In conclusion, Unsafe substitutes are considered as aserious issue in a software development industry therefore in this approach unsafesubstitutes are identified from their superclasses. This approach automaticallyreports the superclass abnormal behaviour for instance, crashes or whenreference points to subclass instance. This approach also ensures correctnessin both sequential and concurrent programs.