并发缺陷的检测与规避研究

发布时间：2018-07-05 11:31

  本文选题：并发缺陷 + 死锁检测与规避　； 参考：《哈尔滨工业大学》2017年博士论文

【摘要】：当前普遍流行的多核架构带来无处不在的并行潜能。为从硬件的并行能力获益,并发程序设计正成为主流程序开发模型。相对于顺序程序,并发程序具有并发性和不确定性的特点。这导致并发程序易于遭遇并发缺陷且并发缺陷难以暴露、检测、调试和修复。在传统测试下,许多并发缺陷没有被检测出来而继续潜伏在程序中,直至在生产性运行时被触发,造成重大事故或财产损失。为消除并发缺陷对程序正确性的威胁,可以采取2种措施:一种是设法尽快暴露和准确检测并发缺陷,识别其构成要素以辅助调试和修复;另一种是容忍并发缺陷存在,有意识地控制执行调度,避免并发缺陷发生。前者侧重于缺陷检测,后者侧重于缺陷规避。因此,研究如何准确检测和有效规避并发缺陷,对于提高并发程序质量和增强其运行可靠性,具有重要的科学理论意义和实际应用价值。本文首先将并发缺陷分为死锁、数据竞争、原子性违背和顺序违背4类,讨论这4类并发缺陷的相互关系,接着就如何暴露、检测和规避各类并发缺陷对已有研究做出分析、比较和归纳,提炼出4个尚待进一步研究的科学问题:如何增强死锁检测能力,如何降低数据竞争检测误报率和漏报率,如何增强死锁规避能力并提高死锁规避效率以及如何增强通用并发缺陷规避能力并降低其人工参与度,最后对这4个问题进行深入研究。针对现有死锁检测技术检测能力弱,只能检测互斥锁死锁的问题,研究并提出一种基于锁分配图的混合死锁动态检测方法,以检测由互斥锁和读写锁造成的所有5类死锁。首先提出混合死锁的概念,给出混合锁分配图的定义和构建方法,然后通过劫持所有互斥锁和读写锁的加锁解锁操作,动态构建和实时更新一个反映目标程序同步状态的混合锁分配图,最后通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁,当检测到死锁时,输出死锁信息以辅助调试。实验结果表明,该方法检测能力强、对目标程序性能影响小且可扩展性好。针对现有静态竞争检测技术误报率高和动态竞争检测技术漏报率高的问题,研究并提出一种动静结合的数据竞争检测方法,以同时降低误报率和漏报率。首先采用静态分析找到所有可能的竞争访问对,识别所有潜在自定义同步原语,然后采用动态分析监视程序在竞争访问点的行为,控制线程调度以尽量暴露数据竞争,并综合使用锁集算法和先发生于算法来检测式地验证被遮蔽的数据竞争,最后动态确认自定义同步原语,剔除虚假和良性数据竞争。实验结果表明,该方法的检测准确度高,误检率和漏检率低,而性能影响和扩展性不差于已有方法。针对现有死锁规避技术规避能力弱、被动盲目、开销较大和影响程序正确性等问题,研究并提出一种基于未来锁集的动静结合死锁规避方法。基本思想是,对于一个加锁操作,若其未来锁集中的所有锁都是空闲的,则执行该加锁操作不会导致死锁。一个加锁操作的未来锁集包括当前要加锁的锁和从该加锁操作到与之相对应的解锁操作过程中遇到的所有加锁操作所要加的锁。通过静态分析,计算锁效应信息并插桩到相应的加锁操作和函数调用操作前后。通过动态分析,劫持加锁操作,根据其锁效应信息为之计算未来锁集,只有当未来锁集中的所有锁都未被锁定才执行该加锁操作,否则等待。实验结果表明该方法能智能主动地规避多种类型死锁,对目标程序的性能影响较小,可扩展性好,不影响程序正确性。针对现有通用并发缺陷规避技术规避能力弱和人工参与度高的问题,研究并提出一种基于软件事务内存的并发缺陷规避方法,能够自动事务化目标程序,规避死锁、数据竞争、原子性违背和顺序违背等4类并发缺陷,支持事务I/O并合理处理条件变量。通过使用进程替代线程、利用进程间虚拟内存保护机制并定制内存分配回收逻辑,实现内存事务化。通过劫持每个线程的线程间操作并将它们之间的代码划分为事务,实现目标程序的自动事务化。通过在启动/撤销事务时保存/恢复当前线程的栈帧和CPU寄存器,实现执行流可回滚化。通过建立和维护虚拟文件系统,并将I/O操作重定向到它们上,实现I/O事务化。通过置空加锁解锁操作,定制条件变量操作和事务性地提交内存与I/O变更,实现对死锁、数据竞争、原子性违背和顺序违背的规避。实验结果表明,该方法的规避能力强,无需人工参与,但对目标程序的性能影响较大。综上所述,本文在如何增强死锁检测能力、降低数据竞争检测误报率和漏报率、增强死锁规避能力与提高死锁规避效率、增强通用并发缺陷规避能力并降低其人工参与度等科学问题上提供了新思路与新方法。
[Abstract]:Current popular multicore architectures bring ubiquitous parallel potential. In order to benefit from the parallel capabilities of hardware, concurrent programming is becoming the mainstream program development model. Relative to sequential programs, concurrent programs have the characteristics of concurrency and uncertainty. This leads to concurrent programs that are prone to concurrency defects and are difficult to expose concurrency defects. Detection, testing, debugging and repair. In traditional tests, many concurrency defects have not been detected and continue to lurk in the program until they are triggered in a productive operation, causing major accidents or property losses. In order to eliminate the threat of concurrent defects to the correctness of the program, 2 measures can be taken: one is to try to expose and detect accurately as soon as possible and Defects, identify its components to assist in debugging and repair; the other is tolerance of concurrency defects, conscious control of execution scheduling, and avoidance of concurrent defects. The former focuses on defect detection, and the latter focuses on defect avoidance. Therefore, it studies how to accurately detect and effectively circumvent concurrent defects and improve the quality of concurrent programs. In order to enhance its operational reliability, it has important scientific theoretical significance and practical application value. Firstly, this paper divides concurrency defects into 4 categories: deadlock, data competition, atomic violation and sequence violation, and discusses the relationship between the 4 kinds of concurrency defects. Then, the analysis of how to expose, detect and avoid various concurrency defects is analyzed and compared. And induction, 4 scientific problems to be further studied: how to enhance the ability of deadlock detection, how to reduce the false alarm rate and false alarm rate of data competition detection, how to enhance the ability of deadlock avoidance and to improve the efficiency of deadlock avoidance, how to enhance the ability to evade the common concurrency defects and reduce the manual participation, and finally to the 4 problems In order to detect the problem that the existing deadlock detection technology is weak and can only detect the deadlock of the mutex lock, a hybrid deadlock dynamic detection method based on the lock allocation graph is proposed to detect all 5 types of deadlocks caused by the mutex lock and the read write lock. First, the concept of mixed deadlock is proposed and the mixing lock allocation graph is given. Meaning and construction method, and then dynamically build and update a mixed lock map that reflects the synchronization state of the target program by hijacking all the mutex lock and read and write lock. Finally, the detection ring is detected on the lock allocation graph and whether the ring is dead lock, and the deadlock information is output when the deadlock is detected. The experimental results show that the method has the advantages of strong detection ability, small impact on the performance of target program and good scalability. In view of the problem of high false alarm rate and high leakage rate of dynamic competitive detection technology in the existing static competition detection technology, a method of dynamic and static combination of data competition detection is proposed in order to reduce the false alarm rate and leakage at the same time. Reporting rate. First, it uses static analysis to find all possible competitive access pairs, identify all potential custom synchronization primitives, then use dynamic analysis monitoring programs at competitive access points, control thread scheduling to expose data competition as far as possible, and use the lock set algorithm and algorithms to verify the occlusion. The experimental results show that the method has high detection accuracy, low error rate and low missed detection rate, and the performance impact and scalability are not bad for the existing methods. The basic idea is that for a lock operation, if all the locks in the future lock set are idle, the lock operation will not cause the deadlock. The future lock set of a lock operation includes the lock lock and the addition of the lock. Lock operation to all lock operations that are encountered during the unlocking operation corresponding to it. Through static analysis, the lock effect information is calculated and piled to the corresponding lock operation and function call operation. By dynamic analysis, the lock operation is hijacked, and the future lock set is calculated according to the information of its lock effect, only in the future. All locks in the lock are not locked until the lock operation is carried out, or otherwise, the experimental results show that the method can intelligently evade various types of deadlocks, have less impact on the performance of the target program, have good scalability, and do not affect the correctness of the program. High problem, research and propose a method of concurrency defect avoidance based on software transaction memory, which can automatically transactional target program, avoid 4 concurrency defects such as deadlock, data competition, atomic violation and sequential violation, support transaction I/O and handle conditional variables reasonably. Through using process instead of threads and using virtual memory between processes Protect the mechanism and customize the memory allocation recovery logic to realize memory transactional. By hijacking each thread's threads between threads and dividing the code between them into transactions, the target program is automatically transactional. The execution flow can be rolled back by saving / restoring the current thread's stack frame and CPU register when starting / revoking transactions. By setting up and maintaining the virtual file system and redirecting the I/O operations to them, I/O transactional. Through the empty and lock unlocking operation, the condition variable operation and the transactional submission of the memory and I/O changes to achieve the evasion of the deadlock, the data competition, the atomic violation and the CIS sequence violation. Experimental results show that the method is avoided. It has strong ability and no manual participation, but has great influence on the performance of the target program. In summary, this paper is how to enhance the deadlock detection ability, reduce the false alarm rate and false alarm rate of the data competition detection, enhance the deadlock avoidance ability and improve the efficiency of deadlock avoidance, enhance the general concurrency concurrence evasion ability and reduce the artificial participation degree. New ideas and new methods are provided.
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.1
，

本文编号：2100066