Low-Overhead Deadlock Prediction
Low-Overhead Deadlock Prediction
复制标题
DOI：
10.1145/3377811.3380367
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yan Cai;Ruijie Meng;J. Palsberg
中科院分区：
文献类型：
--
作者：
Yan Cai;Ruijie Meng;J. Palsberg
即使在部署后，多线程程序也可以发生僵局，因此用户可能需要在部署程序上运行死锁工具。但是，当前的僵局预测因素（例如Magiclock和Undead）具有大型开销，使它们在最终用户部署中不切实际，并将其局限于开发时间。这样的开销源于在大的执行跟踪上运行指数时间算法。在本文中，我们介绍了第一个称为Airlock的低空僵局预测因子，它适合内部测试和部署的程序。 Airlock保持一个小的预测性锁定性图形，搜索图表以进行周期，并仅针对每个周期运行指数时间算法。这种方法让Airlock找到与MagicLock和Undead相同的僵局，但由于循环的数量在实践中很少，因此开销要少得多。我们使用现实世界基准测试的实验表明，气锁的平均时间开销为3.5％，这比Magiclock和Undead的三个数量级要小三个数量级。 Airlock的低开销使其适合与AFL这样的模糊测试仪和部署后直接使用。
Multithreaded programs can have deadlocks, even after deployment, so users may want to run deadlock tools on deployed programs. However, current deadlock predictors such as MagicLock and UnDead have large overheads that make them impractical for end-user deployment and confine their use to development time. Such overhead stems from running an exponential-time algorithm on a large execution trace. In this paper, we present the first low-overhead deadlock predictor, called AirLock, that is fit for both in-house testing and deployed programs. AirLock maintains a small predictive lock reachability graph, searches the graph for cycles, and runs an exponential-time algorithm only for each cycle. This approach lets AirLock find the same deadlocks as MagicLock and UnDead but with much less overhead because the number of cycles is small in practice. Our experiments with real-world benchmarks show that the average time overhead of AirLock is 3.5%, which is three orders of magnitude less than that of MagicLock and UnDead. AirLock's low overhead makes it suitable for use with fuzz testers like AFL and on-the-fly after deployment.