| dc.description.abstract | Software development process consists of various stages like design, implementation, and
testing. Since programmers are considerably involved in these stages, their intuition and
expertise play a vital role in the success of software deployment. Therefore, various tools
have been developed that assist programmers in creating, debugging and managing their
programs. Program analysis, the process of analyzing program behavior by examining its
source code or execution, forms the basis of such software tools. In this thesis, we identify
and address following three research gaps in the area of program analysis.
Type-awareness in concolic testing
Software testing is a widely used dynamic program analysis technique. It helps to determine
the program correctness by executing it to identify undesired behaviors. Since manually writing
effective test suite is challenging, various automated test generation approaches have
been proposed. Concolic testing is one such approach that outputs a test suite for a given
program with the intent of maximizing code coverage. This technique is shown to be very
effective for statically typed languages. With the modernization of web programming, dynamically
typed JavaScript has become a popular language. We study the extension of concolic
testing for JavaScript programs. We show that, for JavaScript programs, such approach generates
a large number of test cases that explore paths and types of the variables repeatedly.
Due to the resultant sizable test suite, adaption of such technique becomes impractical.
In our first work, we propose an effective approach that scales concolic testing by incorporating
type-awareness in conventional concolic testing. Our experiments demonstrate that,
for a significant percentage of the functions, type-aware concolic testing generates a small
percentage (less than 5%) of the test cases as compared to conventional concolic testing. On
average, this approach achieves over 97% of line coverage and over 94% of branch coverage
for all the functions across all benchmarks. Our experimental results show that adapting
type-aware concolic testing is as effective as conventional concolic testing in detecting bugs
and achieving coverage, even with a small percentage of test cases.
Test synthesis to detect redundant traversal bugs
Test generation techniques like concolic testing focus on verifying the functional correctness
of the program. Producing correct results is not the only requirement of the program.
These results should also be achieved within budgeted time. Efficiency, another important
aspect of the program, can be validated with performance testing. Our second work focuses
on automated performance testing in the context of redundant traversal bugs. Such
bugs occur when program fragment performs repetitive and same computations across
loop iterations. Various static and dynamic analysis techniques have been proposed to detect
such bugs automatically. However, the effectiveness of dynamic analyses is dependent
on input test cases, and static analyses are less useful in validating the presence of this
problem.
We propose an approach to generate tests for exposing redundant traversal of loops automatically.
Our experiments reveal the effectiveness of the proposed approach in generating
224 tests that reveal 46 bugs across seven libraries, including 34 previously unknown
bugs. The tests generated using our approach significantly outperform the randomly generated
tests in their ability to expose the inefficiencies, demonstrating the usefulness of
our design.
Performance hints for stable multithreaded systems
Assuring correctness and efficiency of the sequential programs is easier as compared to
multithreaded programs. This is mainly because the execution of multithreaded programs
depends not only on the input but also on thread interleavings. Stable multithreaded
systems restrict the set of possible schedules such that schedule remains unaffected for the
given input, even with minor changes. This eases the process of bug reproduction and
thereby guaranteeing correctness. However, the determinism imposed in these systems
can potentially serialize the schedule resulting in performance degradation. Our third
work focuses on automatically deriving performance hints so that such serialization can
be avoided. Our experimental results demonstrate that we are able to reduce the overall
execution time of programs by up to 34% when compared to the execution time where
barriers are inserted manually. Moreover, we observe a performance improvement ranging
from 38% to 88% as compared to programs without barriers. Our experimental results
show that adapting PEGASUS to infer barriers for multiple versions of a source program is
seamless.
In this thesis, we motivate the problems mentioned above and discuss proposed solutions
in detail. We implement above ideas, develop research prototypes, and study them
on well known real-world programs. The ease in using these prototypes makes our proposed
approach a viable contribution in designing techniques to develop software tools.
All the tools that are developed as part of this thesis have been released publicly | en_US |
