Korat is an existing technique for test input generation using imperative constraints that describe properties of desired inputs written as Java predicates, termed RepOk methods, which are executable checks for those properties. Korat efficiently prunes the space of candidate inputs for the RepOk method by executing it on candidate inputs and monitoring the object fields that RepOk accesses in deciding if the properties are satisfied. While Korat generates inputs effectively, its correctness and efficiency rely on two assumptions about the RepOk methods. For correctness, Korat assumes the RepOk methods do not use the Java reflection API for field accesses; the use of reflection renders Korat unable to enumerate all desired inputs. For efficiency, Korat assumes the RepOk methods do not make unnecessary field accesses, which can reduce the effectiveness of Korat’s pruning. Our thesis addresses both these limitations. To support reflection, we build on the core Korat to enhance it such that it can monitor field accesses based on reflection. To assist the users with writing RepOk’s, we introduce a static analysis tool that detects potential places where the input RepOk may be edited to enhance performance of Korat. We also present experimental results using a suite of standard data structure subjects. / text

Automating the generation of test cases for software is an active area of research. Specification based test generation is an approach in which a formal representation of a method is analyzed to generate valid test cases. Constraint solving and state space exploration are important aspects of the specification based test generation. One problem with specification based testing is that the size of the state space explodes when we apply this approach to a code of practical size. Hence finding ways to reduce the number of candidates to explore within the state space is important to make this approach practical in industry. Korat is a tool which generates test cases for Java programs based on predicates that validate the inputs to the method. Various ongoing researches intend to increase the tools effectiveness in handling large state space. Parallelizing Korat and minimizing the exploration of invalid candidates are the active research directions. This report surveys the basic algorithms of Korat, PKorat, and Fast Korat. PKorat is a parallel version of Korat and aims to take advantage of multi-processor and multicore systems available. Fast Korat implements four optimizations which reduce the number of candidate explored to generate validate candidates and reduce the amount of time required to explore each candidate. This report also presents the execution time results for generating test candidates for binary tree, doubly linked list, and sorted singly linked list, from their respective predicates. / text