Moderator: Automated Software Engineering
Runtime monitoring allows programmers to check that their programs obey important safety and security properties when executed. A runtime monitoring tool will typically instrument the program under test with additional error-checking code, a so-called runtime monitor. But having just one runtime monitor is usually not enough. Imagine that we want to check that no connection object c is used after it was closed. In this case, we need to associate one monitor instance with every collection used by the program. Current runtime monitoring tools solve this problem by so-called indexing: they use hash maps or similar data structures to associate monitors with objects.
Unfortunately, most current indexing implementations are not thread safe. When monitoring concurrent programs, one can therefore obtain incorrect results. Other implementations are thread safe but use a global lock, which makes monitoring concurrent programs highly inefficient.
The goal of this thesis research is to design, implement and evaluate an indexing scheme that is lock-free (and thus highly efficient) but nevertheless correct for concurrent programs, similar to the ConcurrentHashMap in the Java runtime library. The implementation should be based on our MOPBox library for runtime monitoring.
The thesis should describe the data structure, its implementation, argue why the implementation is thread safe, and present a performance comparison with existing indexing implementations in MOPBox. Those implementations are thread-safe but use a single lock and are hence quite inefficient.
In case you are interested, please email me at firstname.lastname@example.org.