Pointer Analysis Based Lock Set Analysis Tool

As multi-core processors become popular, more concurrencyprograms implemented by multi-thread are developed. As a way to protectcritical regions in multi-thread programs, mutex lock is introduced alongwith new types of errors. Errors that caused by lock mishandling, likeforgetting to release an acquired lock, are very common and hard to detect.Classic static analysis methods can find errors without executing anyprogram. Lock analysis tools implemented based on static analysis usuallysearch the error state by traversing the source code. However, staticanalysis can be imprecise due to the lack of dynamic information. Forexample, whether two lock statements in succession triggers a deadlockdepends on whether they manipulate the same lock, i.e. locks in the samelock set. This leads to approximate results, makes a large number ofalarms.There are also two problems in identifying lock sets by usingconventional pointer analysis algorithm. On the one hand, if precisecontext-sensitive and flow-sensitive pointer analysis is applied, thescalability is not assured. On the other hand, if scalable context-insensitiveand flow-insensitive pointer analysis is used, the imprecision may affectthe lock analysis. How to tradeoff between precision and efficiency is acritical problem.In this paper, a new technology is introduced to identify lock sets toassist static analysis. A new lock set analysis tool called ELFI is alsodeveloped. This alias based method is very scalable and can be applied tolarge server programs. The experiment results show that ELFI is moreaccurate than context-insensitive and flow insensitive pointer analysis infinding lock sets in programs. The optimized ELFI is7.2times as fast as the original algorithm.This paper has following contributions:(1)Giving the insight that lock associated variables are only a smallportion of all variables, this paper proposes to slice the original program interms of lock set in order to reduce the analysis effort. A new static slicingmethod is presented for pointer analysis. The program is sliced accordingto the topological structure of coarser-grained points-to graph.(2)Divide the analysis process into two iterative analysis stages. Alightweight Andersen pointer analysis algorithm is implemented withseveral optimizations. Flow dependency graph is built for fine-grainedpointer analysis with the help of coarser-grained points-to graph.(4)For each program slice, apply a context-sensitive andflow-sensitive pointer analysis algorithm on the flow dependency graphwith several optimizations to refine the analysis results.