Software Testing
Software testing is the process of testing the functionality and correctness
of software by running it. It can be approached in two different ways
-- black-box and clear/white-box testing. In the black-box approach, the
tests are generated based on the expected functionality and without knowledge
of the program's internals. On the other hand, in the white-box approach
(what we are doing) the tests are based on the program's structure. White-box
testing strategies include designing tests such that every line of source
code is executed at least once, or requiring every function to be individually
tested. One of the tests that we concentrate on, in this project, is branch
coverage. It tests if every branch has been hit, which means that every
instruction has been executed to make sure that it does not produce an
unexpected/faulty error.
The Big Picture
Regularly branch testing is done through static analysis of the program,
which consists of inserting static breakpoints into the code before its
execution to monitor the branch coverage/frequency, thus modifying the
layout of the original program. For a really large program such method
will take a tremendously long time to evaluate due to the increased number
of cache misses and the instrumentation code that is executed every time
a breakpoint is hit.
Let’s consider branch coverage. We would like to know if a certain
branch has been taken, but do not care how many times it was executed.
However, under the above method the breakpoint code will be executed every
time, therefore uselessly increasing the evaluation time of the program.
Even if we would like to stop executing the instrumentation code once
a certain branch frequency is reached, it would not be possible under
the above method. However, if we can remove the breakpoint when it is
no longer needed, it should substantially decrease the amount of time
it takes to do branch testing. In addition, if we do not change the layout
of the code we should decrease the number of cache misses, therefore decrease
the execution time.
Our Technique
We propose to dynamically insert and delete fast breakpoints as required
by the testing scheme, which should decrease the amount of time it takes
to switch between the executing program and the instrumentation code,
decrease the amount of time for the overall execution of the test, and
not increase cache misses. This can be achieved by an initial fast breakpoint,
which in turn will insert the needed fast breakpoints, or inserting all
the required breakpoints after compilation into native code.
Initial Development of the Project
Madhuri Vemulapalli, a master's student, implemented a basic tool
using fast breakpoints for branch and frequency testing that is suitable for unoptimized bytecodes. However, this initial project only served as a proof of
concept design. INT3 group improved
on the initial design to eliminate known bugs and make it more suitable
for
branch and node coverage. However, the technique can be extended to
other software testing techniques.
Goals for the Project:
- To continue developing and debugging an extensible framework (tool) for various forms of instrumentation on the x86 architecture with strong emphasis on branch coverage.
- To add various functionality to the tool.
- To develop and implement various techniques to minimize the testing overhead in terms of both space and memory.
- To develop a library, which will allow for easy creation of an arbitrary test.
- To design and create an interface between the tool and the graphical user interface, which allows to specify software tests and parameters.
| Background Information: |
|
JikesRVM - Jikes Research Virtual Machine is a Just-In-Time Compiler that takes bytecodes from a Java program, compiles them into target instructions, and executes them. As any virtual machine (VM) it does garbage collection and can optimize your code for faster execution. However unlike other VMs, JikesRVM is written primarily in Java, with approximately 5% C/C++ code to communicate with the underlying system. Basic Block - a sequence of instructions with exactly one entry and exit point. Fast Breakpoints - a transition between executing code and another program/auxiliary code that does not require an OS intervention. Such transition is achieved by replacing the instruction(s) at the specific breakpoint address with a branch to the auxiliary code. |
| Reading Material: |
|
James A. Whittaker, What Is Software Testing? And Why Is It So Hard? Peter Kessler, Fast Breakpoints: Design and Implementation Matthew Arnold and Barbara G. Ryder, A Framework for Reducing the Cost of Instrumented Code B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P.Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar, H. Srinivasan, and J. Whaley, The Jalapeño Virtual Machine Bowen Alpern, Dick Attanasio, John J. Barton, Anthony Cocchi, Susan Flynn Hummel, Derek Lieber, Mark Mergen, Ton Ngo, Janice Shepherd, Stephen Smith, Implementing Jalapeño in Java Bowen Alpern, Anthony Cocchi, Derek Lieber, Mark Mergen, and Vivek Sarkar , Jalapeño - a Compiler-supported Java Virtual Machine for Servers Bowen Alpern, Anthony Cocchi, and David Grove, Dynamic Type Checking in Jalapeño Thomas Lengauer and Robert E. Tarjan, A Fast Algorithm for Finding Dominators in a Flowgraph
|