基于Delta-Debugging算法的多线程程序缺陷定位方法研究

发布时间：2020-11-17 21:56

　　 当今世界多核硬件的高速发展使得多线程程序逐渐被广泛使用,但是往往由于线程之间交错模式的不确定性,多线程程序易于遭遇多线程缺陷,因而保证多线程程序的正确性及其重要而又及其富有挑战性。定位到多线程程序中导致缺陷发生的代码位置,并且理清导致缺陷发生的根本原因,通常需要程序开发人员话花费较多的时间和精力。在这篇文章中,我们在Delta-Debugging算法的基础上,基于内存读写模式的抽象表达,提出了一种对多线程程序缺陷的自动化检测和缺陷原因分析方法DDM。我们的核心思想是找到导致缺陷发生的最小的内存读写模式集合,从而达到精准定位和准确分析的目标。首先,当给出一个被测的有缺陷的程序,我们记录程序运行过程中每一步的线程调度执行,然后从所有的执行步骤中抽离出所有可能的内存读写模式,首先找出内存读写模式集最接近的一对失败和成功执行序列,这两个集合之间的差异我们叫做差异集。接下来,进一步我们扩展Delta-Debugging算法,并将其应用到多线程程序的内存读写模式中,进行缺陷检测。我们利用Java Pathfinder对差异集中的内存读写模式进行打断再执行,从而验证它们是否会导致缺陷发生。由于多线程程序的内存读写模式彼此互相关联,有黏性,因而将Delta-Debugging算法应用到多线程程序有一定的难度。因此针对多线程程序的线程调度方案,我们提出了一个新的函数test(U,f)进行实现。最后,我们将这个想法用真实的程序进行实验验证和多维度研究。实验验证过程以SIR中的程序为例,将我们的方法应用于26个多线程缺陷上,通过与其他经典的方法进行对比,实验结果表明我们的方法可以有效地给出导致多线程缺陷的最小内存读写模式集合。此外,通过与经典方法的结合,我们的方法还可对已有方法的定位结果进行改进。
【学位单位】：天津大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP311.53
【部分图文】：

因为它是并发缺陷的检测、规避和修复操作的前提准备。对于大多数的并发缺陷来说，如果在并发程序执行过程中不对线程的交错进行任何人为干扰的话，是很难暴露出并发缺陷的。压力测试是一个常用而且传统的暴露并发缺陷的方法，但是压力测试是不充分的，因为压力测试趋向于基于一个相同的输入，重复测试相似的线程。因此，通过压力测试来暴露出一个不易发生的并发缺陷是几乎不可能的。并发缺陷通常被暴露的概率很低，总共有以下几个原因：（1）线程交错空间巨大，并且随着代码行数的增加，线程交错空间呈指数倍增加。（2）并发缺陷通常都隐藏在某些不常见或者特殊的内存读写线程交错模式中。（3）如果没有额外的线程交错干扰，多线程程序通常都会按照相同的线程交错模式执行。为了克服这些难题，研究学者们做了大量的工作并且提出了不同的解决方法。一个好的并发缺陷暴露方法必须是有效的，高效的而且是可重复使用的，这样才可以被大多数的程序开发人员所接受。图 1-1 展示了多线程缺陷暴露方法的流程。多线程程序首先被经过分析来确定可疑的线程交错。然后被测程序会被应用一个可控的测试方法，并且施加不同的策略，从而可以暴露并发缺陷。

第 1 章 绪论了减少误报率和漏报率，并且提出有效的缺陷自动检测方法，已经有许多方法被提出。图 1-2 展示了并发缺陷检测过程的完整步骤。给出一个多线程程序 P 和测试用例集 T，可以应用不同的方法来检测并发缺陷。基于检测过程中被测程序是否被执行过，我们把所有的检测方法分成三类：静态方法，动态方法和混合方法。

2.2 多线程程序缺陷的分类和特点Tan 等人[23]对一共 2060 个真实程序中的软件缺陷进行了一个研究，并将所有缺陷分为四大类：内存缺陷，语义缺陷，并发缺陷和性能缺陷。在所有缺陷中，本文开展的研究集中于并发缺陷，而并发缺陷又可分为四类：数据竞争（dataraces），原子性违背（atomicity violations），顺序违背（order violations）和死锁（deadlocks）。数据竞争缺陷定义为当有两个并发的内存访问操作都针对同一个内存地址，且这两个操作分别来自两个线程，其中至少有一个操作必须为写操作。图 2-1 展示了一个数据竞争缺陷的例子，我们截取自快速傅里叶变换（fast Fouriertransform，简称 FFT）这个算法[24]。在这个例子中，程序开发人员原本计划在执行线程 1 的 S1 语句之前执行线程 2 中的 S2 语句。但是由于相应的保证程序按照特定顺序执行的同步语句的缺失，这个确定的顺序不能完全被保证。结果，在某些情况中，S1可能会在S2之前执行，而这样的顺序必将导致一个错误的结果。
【相似文献】

相关期刊论文 前10条

1 ;你的脑袋有几根线[J];广东第二课堂(下半月中学生阅读);2016年10期

2 张蕊;;计算机中的多线程问题[J];科技传播;2013年22期

3 张红斌;李广丽;刘觉夫;;网络机器人多线程爬行的研究与实现[J];计算机应用与软件;2010年01期

4 潘海波;;多线程扫描局域网内的计算机[J];黑龙江科技信息;2009年19期

5 张云苑;Java多线程并发技术的实现[J];电脑开发与应用;2004年09期

6 曹军梅,张贞,杨东风;一种实现多线程的方法[J];延安大学学报(自然科学版);2002年02期

7 应荣军;;MFC多线程用事件(EVENT)同步的探讨[J];中文信息;2002年08期

8 罗宇,商临锋;操作系统多线程实现技术研究[J];小型微型计算机系统;2000年05期

9 田晓红;国产多线程浏览器“七仙女”的靓点[J];电脑爱好者;2000年24期

10 宋燕红,马礼;多线程并发服务器的设计与实现[J];华北工学院学报;1998年02期

相关博士学位论文 前10条

1 朱亮;基于NUMA架构的多线程程序性能和能耗研究[D];华中科技大学;2016年

2 吴振东;并行程序中bug检测技术研究[D];国防科学技术大学;2015年

3 赵荣彩;多线程低功耗编译优化技术研究[D];中国科学院研究生院（计算技术研究所）;2002年

4 杨华;片上多线程体系结构资源分配策略的研究[D];哈尔滨工业大学;2006年

5 郑龙;多线程锁同步运行时特征分析与调优机制研究[D];华中科技大学;2016年

6 邓鹍;前瞻多线程编译优化技术的研究与实现[D];国防科学技术大学;2001年

7 逄龙;多线程程序中关联变量原子性验证关键技术研究[D];哈尔滨工业大学;2015年

8 陈沉;面向多线程程序的确定性并行关键技术研究[D];国防科学技术大学;2015年

9 徐海峰;多线程的内存调度[D];浙江大学;2011年

10 林英;多核软件形式化建模、验证及性能评价方法研究[D];云南大学;2013年

相关硕士学位论文 前10条

1 傅浩杰;基于Delta-Debugging算法的多线程程序缺陷定位方法研究[D];天津大学;2018年

2 朱欣;基于单指令集异构多核架构的单核多线程性能建模[D];东南大学;2017年

3 缪磊;网络处理引擎性能评估技术研究[D];西安电子科技大学;2018年

4 潘有顺;嵌入式多线程程序数据竞态条件的分析与研究[D];昆明理工大学;2015年

5 简道红;多线程程序数据竞争静态检测方法研究[D];大连理工大学;2013年

6 徐超;基于动态二进制翻译的多线程程序数据竞争检测方法研究[D];上海交通大学;2010年

7 殷绍剑;嵌入式多线程远程调试器研究与实现[D];电子科技大学;2013年

8 白哥乐;基于静态源码分析的多线程死锁检测方法研究[D];北京邮电大学;2011年

9 祝帅君;多核多线程虚拟化中断系统的研究与实现[D];国防科学技术大学;2008年

10 许先超;龙芯2号多线程扩展的研究与设计[D];中国科学院研究生院（计算技术研究所）;2005年

本文编号：2887964