Testing and Profiling Finite-State Machine Software
Introduction
Grail+ is constantly being evolved and refined. Every change we make,
however, introduces the possibility of error; consequently, we must
take measures to ensure that enhancements actually do improve performance,
and that they do not impair correctness. This project involves developing
an extensive library of finite-state machines and regular expressions to
be used for checking both the correctness of Grail+, and for profiling
execution to check its efficiency.
Tasks
- Study the current (small) test and profile library.
- Research and develop a more comprehensive test and profile
library, with a particular bent to uncovering potential bugs and
inefficiencies. Test cases may come from:
- examples in textbooks and the research literature
- the use of cross product
- repetitive conversion from regexp to fsm and back
- random generation
- complementation
- Construct a more general and powerful test/profiling harness
- Apply this library to other FSM packages, such as AMORE,
FANCY, and the Fire Engine. Write a report on the correctness and
efficiency of these packages.
- Develop the software necessary to promote the library's
use as a benchmark for the FSM `industry'.
Difficulty
The first two tasks can be done within a 4-month work term by a motivated
student who has a good knowledge of finite-state machines. A 4th-year
project would involve completion of the first four tasks, and we would
expect a more complete library to be developed in this time.
This project requires that the student either possess or eventually
develop a deep understanding of FSMs and their implementations.
The best student for this project is one who has a talent for finding
bugs in software, or for developing nasty test cases. The ability to
explain why one's test cases are good is almost as important as being
able to find them. The project is not programming intensive.
Value to the student
This project would be very useful experience for students who intend to
pursue a career in software quality assurance, software testing, or
software engineering.
Top of page
Grail+ home page