Abstract: Deadlock detection of programs plays an important role in ensuring the stability of software systems.In view of the high efficiency and low false alarmrate of deadlock detection,the dynamic deadlock analysis method is widely studied.However,traditional dynamic analysis methods use lock graph or extended variants to model program trajectory,which cannot accurately describe the lock authorization/release operations and their execution scenario information,thus still leads to some deadlock false positives.To solve this problem,a new deadlock dynamic analysis method based on Petri net model mining was proposed.The operations corresponding to concurrent primitives of programs were captured,and a Petri net model of the program was constructed according to the captured operation sequence.The deadlock detection problem of programs was converted to the dead marking detection problem of adjoint Petri net model of programs.Traditional reachability trees were extended to incorporate scheduling scheme for deadlock replay.The proposed method could eliminate more false positives and provide a deterministic deadlock replay scheme,which effectively improved the accuracy of deadlock detection.

Key words: program trajectory, deadlock detection, Petri nets, deadlock replay, process mining

摘要： 程序死锁检测对于保证软件系统的稳定性具有重要作用。动态死锁分析方法由于具有高效和低误报率的特点而得到广泛研究。然而,传统的动态分析方法采用锁图及其各类扩展模型进行程序运行轨迹的建模和分析,它们难以对锁的授权/释放操作及其执行场景进行准确刻画,从而会导致误报现象。针对该问题,提出一种新型的基于程序运行轨迹Petri网模型挖掘的多线程程序动态死锁分析方法。首先,捕获程序运行轨迹中各类并发原语对应的操作,并据此构建程序的Petri网模型;然后,将程序的死锁检测问题转化为程序伴随Petri网模型的死标识检测问题;最后,在传统可达树基础上,计算并扩充了可用于死锁重演的程序调度方案。所提方法能排除更多的误报,并给出一种确定性的死锁重演方案,可有效提高死锁检测的准确性。

关键词: 程序运行轨迹, 死锁检测, Petri网, 死锁重演, 过程挖掘