Concurrent Testing of Semaphore-based and Shared-memory Software

[[abstract]]Concurrent program is becoming commonplace in modern computing. However, the bugs in concurrent program are usually difficult to be detected because of the non-deterministic behavior of concurrent programs. Semaphore is one of the major synchronization mechanisms in computer science. It often used to control the access of shared data in a multiprogramming environment. The misuse of semaphore is a very serious problem, because this may cause the program deadlock or make some inappropriate access of shared data. In this thesis, we describe how to apply dynamic effective testing to semaphore-based concurrent programs. We propose some protocols that can perform prefix-based replay on semaphore operations and record the program status when the deadlock happened. We also define a novel format for the SYN-sequence of semaphore-based program. Then, we have an algorithm to filter out the infeasible race variants generated by race analyzer in reachability testing. Last, we develop a compression function to deal with the state space explosion problem induced by the reiterative events. Thus, we can successfully perform state-cover testing for semaphore-based and shared memory concurrent programs and find out all the states of the concurrent programs which contain shared semaphores and shared memories and all the deadlocks in the programs.