Eindhoven University of Technology PhD candidate Thomas Neele has developed three techniques for smarter and faster bug checking, based on the model checking method. In his work, carried out in collaboration with ASML, he addresses the infamous state space explosion problem by reducing the number of software states that need to be checked. On 16 September, he’ll defend his thesis, called “Reductions for parity games and model checking.”
Model checking is one of the most rigorous techniques to check software. It looks at all possible things a software system can do, and the states it can be in, to check if it works as required. The challenge is that software often consists of many parts that work in parallel. That can cause an explosion in the number of states that need to be investigated, making model checking costly and perhaps even unmanageable.
The three new reduction techniques Neele developed in his PhD project have one thing in common: they take the requirement of the states in mind. This extra piece of information means it’s easier to see which states don’t need checking. To be able to look at the system’s behavior and requirement at the same time, Neele first developed a new, structured way to show the behavior-requirement combination.
The first technique reduces the number of states by grouping similar states together. This even makes it possible to work with an infinite number of states. The second approach checks whether the parts that work in parallel sometimes perform a task independently. In that case, it’s unnecessary to investigate all possible states. The last technique checks whether certain data elements are relevant and removes them if they’re not.
In the future, these ideas will help to reduce the development cost and time-to-market of safety-critical software. Furthermore, Neele’s techniques can help eliminate dangerous bugs from systems such as airplanes and medical devices. Currently, the application of his ideas, and model checking in general, requires a lot of expertise. To enable widespread adoption, it’s necessary to develop a fully-automated system that decides which approach is most suitable for a particular application.