并发程序回归测试研究
发布时间：2022-01-02 11:54
给定某并发程序执行轨迹,基于约束求解的并发测试方法将并发错误模式和执行轨迹的可行性要求转化为一组约束条件,通过约束求解生成暴露并发错误的并发执行交织。该方法具有无误报、低漏报率等诸多优势。并发程序在开发过程中会经历多次修改,产生多个程序版本。在并发程序的演化过程中,直接对各个版本的基于约束求解的并发程序测试,由于未有效利用版本变化信息,而造成重复测试,致使并发程序回归测试面临效率较低等问题。为了提高并发程序的回归测试效率,本文提出了一种基于约束求解的并发程序回归测试方法。该方法首先分析收集的两个并发程序版本的执行轨迹,计算两个轨迹中每个内存访问事件的并发上下文;然后使用修改影响分析得到所有受修改语句影响的内存访问事件,组成影响集;最后采用考虑控制流的最大因果模型,将并发错误探测问题转换为约束求解问题,对至少包含一个影响集事件的交织空间进行并发错误探测。该方法基于约束求解,可保证得到的并发错误一定是真实的,不会产生误报。同时该方法基于修改影响分析,能够保证得到的并发错误一定是由修改代码生成的,不会重复报告以前版本已探测到的并发错误。该方法可有效减小并发程序错误探测的交织空间,提高回归测试...
【文章来源】：东南大学江苏省 211工程院校 985工程院校 教育部直属院校
【文章页数】：70 页
【学位级别】：硕士
【部分图文】：
事件类型
东南大学硕士学位论文8图2-2(a)是一个实例程序，该程序包含两个线程(t1,t2)、三个共享变量(a,b,c)、两个局部变量(r1,r2)和一个锁对象l。图2-2(b)是该程序的一条可行执行轨迹。该执行轨迹满足顺序一致性：（1）对于读写一致性要求：读事件e10读取共享变量b的值为-1，而该执行轨迹中，发生在e10之前、距离e10最近、访问共享变量b、且是写操作的是写事件e6，写入的值为-1，满足读写一致性要求。同样地，读事件e12以及e17均满足读写一致性要求。（2）对于独占锁互斥要求：锁释放事件e7之前存在相同线程t1和相同锁对象l的锁获取事件e2与之匹配，同样锁释放事件e11和锁获取事件e9也可相互匹配，而且两组acquire-release事件对未发生交织，因此满足独占锁互斥要求。（3）对于Happen-Before关系要求：begin事件e8发生在fork事件e1之后，并且是线程t2的第一个事件；end事件e15发生在join事件e16之前，并且是线程t2的最后一个事件；两者均满足Happen-Before关系要求。2.2松弛的可行性公理顺序一致性是执行轨迹可行的必要条件，即如果某条执行轨迹可以由并发程序实际运行得到，那么这条执行轨迹一定符合顺序一致性，但是反之则不一定。可行性公理可以分析某条可行执行轨迹，推导得出其他可行的执行轨迹，而且推导过程中无需其他信息。对于某并发程序P，将所有可以由P实际运行生成的所有执行轨迹(无论是完整或者不完整的轨迹)组成的集合称为Feasible(P)，即Feasible(P)中的执行轨迹都是可行的。可行性公理的目的就是推导获得一个Feasible(P)。最为常见的可行性公理是由Mazurkiewicz的轨迹理论和Lamport的Happen-Before关系整合而成的[14,28]。该公理要求Feasible(P)是一个交织闭包，针
东南大学硕士学位论文8图2-2(a)是一个实例程序，该程序包含两个线程(t1,t2)、三个共享变量(a,b,c)、两个局部变量(r1,r2)和一个锁对象l。图2-2(b)是该程序的一条可行执行轨迹。该执行轨迹满足顺序一致性：（1）对于读写一致性要求：读事件e10读取共享变量b的值为-1，而该执行轨迹中，发生在e10之前、距离e10最近、访问共享变量b、且是写操作的是写事件e6，写入的值为-1，满足读写一致性要求。同样地，读事件e12以及e17均满足读写一致性要求。（2）对于独占锁互斥要求：锁释放事件e7之前存在相同线程t1和相同锁对象l的锁获取事件e2与之匹配，同样锁释放事件e11和锁获取事件e9也可相互匹配，而且两组acquire-release事件对未发生交织，因此满足独占锁互斥要求。（3）对于Happen-Before关系要求：begin事件e8发生在fork事件e1之后，并且是线程t2的第一个事件；end事件e15发生在join事件e16之前，并且是线程t2的最后一个事件；两者均满足Happen-Before关系要求。2.2松弛的可行性公理顺序一致性是执行轨迹可行的必要条件，即如果某条执行轨迹可以由并发程序实际运行得到，那么这条执行轨迹一定符合顺序一致性，但是反之则不一定。可行性公理可以分析某条可行执行轨迹，推导得出其他可行的执行轨迹，而且推导过程中无需其他信息。对于某并发程序P，将所有可以由P实际运行生成的所有执行轨迹(无论是完整或者不完整的轨迹)组成的集合称为Feasible(P)，即Feasible(P)中的执行轨迹都是可行的。可行性公理的目的就是推导获得一个Feasible(P)。最为常见的可行性公理是由Mazurkiewicz的轨迹理论和Lamport的Happen-Before关系整合而成的[14,28]。该公理要求Feasible(P)是一个交织闭包，针
【参考文献】：
期刊论文
[1]并发缺陷暴露、检测与规避研究综述[J]. 苏小红,禹振,王甜甜,马培军. 计算机学报. 2015(11)
[2]一种Java字节码优化框架[J]. 张昱,刘玉宇. 计算机工程. 2008(02)
硕士论文
[1]基于并发程序切片的修改影响分析[D]. 张欢.东南大学 2017
[2]基于约束求解的并发程序错误探测[D]. 周敏敏.东南大学 2016
本文编号：3564130
【文章来源】：东南大学江苏省 211工程院校 985工程院校 教育部直属院校
【文章页数】：70 页
【学位级别】：硕士
【部分图文】：
事件类型
东南大学硕士学位论文8图2-2(a)是一个实例程序，该程序包含两个线程(t1,t2)、三个共享变量(a,b,c)、两个局部变量(r1,r2)和一个锁对象l。图2-2(b)是该程序的一条可行执行轨迹。该执行轨迹满足顺序一致性：（1）对于读写一致性要求：读事件e10读取共享变量b的值为-1，而该执行轨迹中，发生在e10之前、距离e10最近、访问共享变量b、且是写操作的是写事件e6，写入的值为-1，满足读写一致性要求。同样地，读事件e12以及e17均满足读写一致性要求。（2）对于独占锁互斥要求：锁释放事件e7之前存在相同线程t1和相同锁对象l的锁获取事件e2与之匹配，同样锁释放事件e11和锁获取事件e9也可相互匹配，而且两组acquire-release事件对未发生交织，因此满足独占锁互斥要求。（3）对于Happen-Before关系要求：begin事件e8发生在fork事件e1之后，并且是线程t2的第一个事件；end事件e15发生在join事件e16之前，并且是线程t2的最后一个事件；两者均满足Happen-Before关系要求。2.2松弛的可行性公理顺序一致性是执行轨迹可行的必要条件，即如果某条执行轨迹可以由并发程序实际运行得到，那么这条执行轨迹一定符合顺序一致性，但是反之则不一定。可行性公理可以分析某条可行执行轨迹，推导得出其他可行的执行轨迹，而且推导过程中无需其他信息。对于某并发程序P，将所有可以由P实际运行生成的所有执行轨迹(无论是完整或者不完整的轨迹)组成的集合称为Feasible(P)，即Feasible(P)中的执行轨迹都是可行的。可行性公理的目的就是推导获得一个Feasible(P)。最为常见的可行性公理是由Mazurkiewicz的轨迹理论和Lamport的Happen-Before关系整合而成的[14,28]。该公理要求Feasible(P)是一个交织闭包，针
东南大学硕士学位论文8图2-2(a)是一个实例程序，该程序包含两个线程(t1,t2)、三个共享变量(a,b,c)、两个局部变量(r1,r2)和一个锁对象l。图2-2(b)是该程序的一条可行执行轨迹。该执行轨迹满足顺序一致性：（1）对于读写一致性要求：读事件e10读取共享变量b的值为-1，而该执行轨迹中，发生在e10之前、距离e10最近、访问共享变量b、且是写操作的是写事件e6，写入的值为-1，满足读写一致性要求。同样地，读事件e12以及e17均满足读写一致性要求。（2）对于独占锁互斥要求：锁释放事件e7之前存在相同线程t1和相同锁对象l的锁获取事件e2与之匹配，同样锁释放事件e11和锁获取事件e9也可相互匹配，而且两组acquire-release事件对未发生交织，因此满足独占锁互斥要求。（3）对于Happen-Before关系要求：begin事件e8发生在fork事件e1之后，并且是线程t2的第一个事件；end事件e15发生在join事件e16之前，并且是线程t2的最后一个事件；两者均满足Happen-Before关系要求。2.2松弛的可行性公理顺序一致性是执行轨迹可行的必要条件，即如果某条执行轨迹可以由并发程序实际运行得到，那么这条执行轨迹一定符合顺序一致性，但是反之则不一定。可行性公理可以分析某条可行执行轨迹，推导得出其他可行的执行轨迹，而且推导过程中无需其他信息。对于某并发程序P，将所有可以由P实际运行生成的所有执行轨迹(无论是完整或者不完整的轨迹)组成的集合称为Feasible(P)，即Feasible(P)中的执行轨迹都是可行的。可行性公理的目的就是推导获得一个Feasible(P)。最为常见的可行性公理是由Mazurkiewicz的轨迹理论和Lamport的Happen-Before关系整合而成的[14,28]。该公理要求Feasible(P)是一个交织闭包，针
【参考文献】：
期刊论文
[1]并发缺陷暴露、检测与规避研究综述[J]. 苏小红,禹振,王甜甜,马培军. 计算机学报. 2015(11)
[2]一种Java字节码优化框架[J]. 张昱,刘玉宇. 计算机工程. 2008(02)
硕士论文
[1]基于并发程序切片的修改影响分析[D]. 张欢.东南大学 2017
[2]基于约束求解的并发程序错误探测[D]. 周敏敏.东南大学 2016
本文编号：3564130
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3564130.html
