并发Java测试生成与搜索问题

理论计算机科学电子笔记144（2006）57-72www.elsevier.com/locate/entcs作为搜索问题的并发Java测试生成Yaniv Eytani计算机科学系，海法大学摘要随机测试生成器生成可执行的测试及其预期结果。以噪声制造器的形式，它用可能导致上下文切换的条件调度原语（如yield（））为程序播种因此，在程序的不同执行中可能会产生不同的交织先验地确定一个bug出现所需的一组种子位置是不可能的。这项工作提出了重新制定随机测试生成的并发Java程序作为一个搜索问题。因此，它允许将一组众所周知的搜索技术从AI域应用到测试生成器的输入空间。通过迭代地细化馈送到测试生成器的输入参数，搜索过程创建测试场景（即，交织），最大化预定义的目标函数。我们开发了geneticrobot，一种使用遗传算法作为搜索方法的噪声制造器。我们证明了我们的方法，最大限度地提高两个目标函数：并发错误的高表现率和出口的高度调试信息给用户。实验结果表明，该方法是有效的。保留字： 随机测试生成器，并发JAVA，遗传学，1介绍随着并发编程在Internet和服务器端的日益普及，并发缺陷分析的问题也被提到了最前沿。Java集合1作者感谢海法大学凯撒利亚·埃德蒙·本·罗斯柴尔德基金会计算机科学跨学科应用研究所的支持。电子邮件：ieytani@cs.haifa.ac.il网址：http：//cs.haifa.ac.il/1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.02.00458Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57可能的交错是巨大的，尝试它们是不实际的。 只有少数这些交错实际上产生并发故障。因此，产生并发故障的概率非常低。因此，诸如无意的竞争条件和死锁之类的缺陷很难发现和分析，而且往往会逃逸到现场。一个相关的问题是JVM调度程序通常是确定性的;多次执行相同的测试不会有帮助，因为将创建相同的交织集。这对于在类似环境中重新执行的简单和平均复杂度测试是正确的，而不管环境如何测试多线程程序的问题是复杂的，因为在现场或压力测试中发现并发故障的测试通常很长，并且在不同的环境条件下运行因此，这样的测试不一定是可重复的，并且当检测到故障时，必须投入大量的精力来重建故障发生时的条件。在以前的工作中，我们开发了一个用于Java的启发式噪声制造器，它在发现并发错误方面是有效的[2]。RaceRace使用条件同步原语对程序进行播种，这些原语可能会更改JVM调度程序产生的运行时交织，并增加并发错误出现的可能性。然而，这种能力在很大程度上取决于竞争者的输入集（称为“配置”）。配置是程序位置和相关参数的子集，用于确定要应用的调度噪声（种子上下文切换和延迟）的量。可能的配置数量可能非常大，只有一小部分可能会发现bug。有些配置甚至无法进行测试。不同的程序通常有不同的配置集，这些配置集对于发现bug是有效的，并且先验地确定它们是很少可能的。这项工作建议重新制定并发Java程序的随机测试生成（以噪声的形式[5]）作为一个搜索问题。随机测试生成器生成可执行的测试及其预期结果.它接收测试指令或规范作为输入，这些指令或规范告诉它需要什么样的测试。将测试生成视为搜索问题，允许将一组众所周知的搜索技术从AI域应用到生成器的输入空间。改变生成器的输入改变其输出，即插入到程序的执行中的条件调度噪声，并且潜在地改变生成的交织。因此，搜索过程迭代地调整输入，以创建测试场景（即测试），该测试场景在单个执行（或可能是一组执行）上最大化预定义的目标函数为了证明我们的方法，我们开发了一种新的种族歧视的变种Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）5759工具（称为遗传算法），基于使用遗传算法作为搜索方法。遗传算法[13]（以下简称GA）通过随机采样搜索空间并创建一组称为“种群”的可能解决方案（染色体）来搜索最优或接近最优的解决方案。每个染色体都有一个指定的适合度。这些染色体经历重组、突变或存活，并以取决于其适应性水平的概率被选择以进化成新一代解决方案。遗传学目前的目标是最大化两个预定义的目标函数：（1）在程序的每个执行中实现错误显现的高概率，以及（2）向用户输出大量调试信息。后者是通过在最小的变量和程序位置集上应用高度的调度噪声来实现的。两个目标函数都有很好的相关性（这个经验来自[2][6]），我们将最大化两个函数的配置称为有效配置。以前的工作是专门针对显化错误[2]或实现覆盖目标，以创建有效的回归套件[10]。这项工作通过提供定义各种新目标函数（或这些函数的加权组合）的灵活性来推广这一概念。此外，我们的框架可以很容易地与来自不同范例的其他测试工具进行交互，例如静态分析[4]，竞争检测[1][16]和模型检查[18]。可以使用来自静态分析或动态分析（例如竞争检测）的信息作为搜索过程的起点。另一种可能性是使用噪声制造器来引发作为错误的竞争条件的潜在不正确行为（与良性竞争相对）。通过定义适当的目标函数，生成器然后，模型检查器分析的结果可以反馈给噪声制造者，并启动搜索过程的另一次迭代。我们打算在今后的工作中探讨这种可能性我们试验了一组取自公开基准的程序[7]。每个程序本文的组织如下：第2节讨论了并发测试生成与raceplayer工具。第3节将噪声生成作为搜索问题。第4节提供了种族歧视的遗传变体的实施细节。第5节给出了实验结果和分析。第六部分列出了我们的结论和未来的工作。60Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）572用racetron进行当并发bug出现在少量的交错中，或者出现在JVM的调度策略下没有产生的交错中时，它可能会以非常低的概率发生，或者根本不会发生。为了增加这些错误出现的可能性，我们以前开发了一个随机测试工具[2]，一个并发Java程序的随机测试生成器在典型的竞争性用户场景中，当执行程序P时，针对程序P重复执行给定的功能测试t。在每次执行过程中，程序在不同的程序位置都被植入了条件同步原语（如yield（））被播种的基元可以导致上下文切换，并且作为结果，产生潜在的不同交织。这个过程创建了不规则的测试场景，并增加了发现并发错误的可能性（在[2][5][17]中详细说明）。RaceMap基于两级方案执行启发式搜索。第一级决定，对于每个并发事件（访问共享变量的程序位置，称为事件[2]），是否使用种子原语强制上下文切换。在第二层，不同的种子原语被应用于所选择的并发事件。概率参数控制在运行时引入的上下文切换和延迟（称为噪声或调度噪声）的数量。2.1噪声产生的概率模型以前的工作[2]表明，与随机执行所有程序事件的上下文切换（称为白噪声）相比，将噪声应用于与并发错误相关的单个变量的策略显着增加了错误出现为了证明播种程序事件子集的合理性其他类型的条件播种也是可能的，并将在以下部分中讨论我们将在下文中简要介绍建议的分类并发bug的分类[8] [15]以及数据竞争[16]和原子性[12][19]的研究表明，并发bug在一系列事件以特定顺序发生时表现出来。这个序列通常涉及来自不同线程的事件。因此，在序列中的某些事件执行之后（或之前），需要上下文切换，以使错误得以显现。我们把这样的事件称为好事件。实验研究表明，有太多的上下文切换往往掩盖并发错误[2]。因此，对于暴露并发bug的序列，最好不要进行上下文切换Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）5761发生在序列中的大多数其他事件之前或之后。我们把后者称为坏事件。因此，对于给定的并发bug，我们区分三种类型的事件：• 好事件• 坏事件• 中性事件在下面的示例中T hread1T hread2(1)如果（x！= 0）{(3)intx= 1;(2)y= 1/x;(4)return0;}(5)z= 8事件（1）和（3）是好的，因为在这些事件之后执行的上下文切换增加了除以零发生的概率。然而，如果通过用if（x == 0）替换（1）来改变程序，则事件（1）变成坏的。事件可以自然地分组为访问共享变量的事件集，或者在给定程序位置发生的事件集。我们将根据上下文交替使用术语事件、程序位置和变量来表示这些集合对于每个共享变量或程序位置，我们松散地分配它是好的、坏的还是中性的概率。这个赋值是基于与它相关联的好、坏或中性并发事件被执行的概率来概率问题自然会出现，因为调度程序选择的特定交织取决于外部和不可预测的事件，例如在底层机器上运行的其他程序的当前负载。此外，不同程序位置处的条件播种之间的交互可以以不可预测的方式影响调度，从而证明上述概率分配是合理的。2.2调度算法如前所述，Racebooks使用两级方案将噪声应用于程序。第一级只播种程序事件的一个子集，以增加bug清单的可能性。通过使用调度，RaceRank进一步增加了bug在第二层出现的概率62Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57在所选集合的每个事件处执行单个上下文切换的优先级（即，多个上下文切换和延迟）。我们使用以下示例来激励这一点：T hread1T hread2T hread3(1)如果（x！= 0）{(3)i= 1;(5)i= 1;”(4)return0;(6)intx= 1;(2)y= 1/x;}在该示例中，在执行事件（1）之后应用调度启发式假设调度程序总是首先将控制权转移到线程3，一旦完成，将控制权返回给线程1（由于预定义的JVM调度策略）。事件（1）之后的单个上下文切换不会导致该错误出现。然而，具有长延迟的播种（1）（例如，使用wait（））可能会强制调度程序执行线程2，并增加出现错误的可能性。这个例子直观地说明了不同的调度启发式可以潜在地增加或减少错误出现的概率。我们简要描述了三种可能的竞争力：• Yield（）-在选定的事件中，yield（）启发式算法随机确定是否执行yield（）原语。这被重复随机的次数。yield（）调度启发式算法的优点是不使用超时。 如果使用了超时，CPU可能有时会空闲，导致不可接受的性能影响（参见[5]中讨论的sleep（）算法）。• Wait（）-wait（）启发式算法是通过在程序执行期间的选定事件处添加wait（）语句来实现的。为了防止死锁，线程的等待是定时的。在wait（）原语之前和之后获取和释放锁，以便从线程本地区域和堆中清除值。因此，其他线程可以看到共享变量发生的更改。• 暂停一个线程-一个不太可能的定时场景（在[8]中详细说明）发生在一个线程长时间暂停，而其他线程继续前进并更改共享变量值时。这种试探法阻止到达所选程序位置的线程前进。只有当程序的其余部分无法继续并等待该线程时，该线程才会继续前进。显然，其他调度算法也是可能的（详见[5][17]）。然而，我们相信这些算法捕捉到了导致实际程序中并发错误Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57633作为搜索问题的搜索问题可以描述为找到一组参数，目标函数具有最大值或最小值。当在大的多模态搜索空间内搜索问题的最优或接近最优的解决方案时，解析求解可能是不可行的元算法[20]是通常应用于这种搜索空间的一组技术。噪声制造很好地符合这个定义，因为一组竞争约束（选择好的位置，而不是选择坏的位置）必须平衡。此外，有时使用多目标函数（例如组合配置的错误表现率和配置的大小）来达到解决方案。先前关于噪声的工作表明，通过缩小搜索空间，仅将噪声应用于频繁访问的共享变量，噪声度量有时可以有效[2]。将其模拟为搜索问题允许使用搜索技术（例如，遗传算法），而无需考虑此类限制性假设。解决搜索问题涉及以下三个步骤：表示问题（模型），定义适应性函数（目标函数）和定义一组操作算子（搜索算子）。在接下来的小节中，我们将描述将元启发式搜索应用于噪声产生所需的符号和目标函数。3.1符号为了将噪声问题表述为一个搜索问题，我们在Java中定义了一个搜索空间，它覆盖了一组所有可能的多线程程序。我们将P表示为所有Java程序的集合。对于每个程序p∈P，我们表示以下集合：• V是程序变量的•SV是程序变量的集合，其中程序的每个变量• L是程序的程序位置的集合，其中每个程序的位置由两个元素表示，在它执行之前和之后。直观地说，这将程序的事件划分我们将访问区分为“之前“和“之后“访问本身，这是由于在这些位置之前或之后应用调度噪声获得的我们表示以下集合：64Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57(i) H是可用调度算法的有限集合，例如，H={yield（），wait（），halt one thread}。(ii) N是噪声强度的有限集合（种子原语的执行概率和种子延迟长度）：N ={0，.，100}。(iii) SL、SV和SS是三个预定义集合的笛卡尔乘积：• SL=L× H × N• SV=V× H × N• SS=SV×H×N集合SL（或SV和SS）的每个种子元素Si直观地表示应用于局部化L i∈ L（或Vi∈ V和SVi）的类型H i的一个可执行的最优性∈ SV）。我们使用术语变量来表示变量和分割访问变量（SV的元素）。为了简单起见，我们假设每个启发式算法只有一个相关的噪声强度参数Ni∈ N。定义3.1构形集C是一个格，它被构造为集的不交并的幂集：SL，SV，SS每个配置Ci都是SL、SV或SV类型的种子对象的子集。我们滥用符号，写Ci（t）来表示t个程序执行后配置Ci被执行的次数，而fb（Ci）表示表示在程序执行期间出现错误的次数3.2目标函数搜索问题可以被描述为找到一组参数，使预定义的目标函数（或函数）最大化。一个目标函数通过在它所应用的单个解上施加一个顺序标度来表征被认为是一个好的解。在搜索过程的每一步，目标函数允许从一组两个或多个解（配置，对于手头的问题在这项工作中，我们将定义两个这样的函数：一个函数将每个配置映射到并发错误出现的概率，另一个函数将每个配置映射到代表其提供的调试信息量的大小。定义3.2对于每个程序Pi，存在函数fp：C →[0，1]，函数fp将每个配置映射到并发错误出现的概率，其中应用配置Ci在程序执行期间。Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）5765定义3.3对于每个程序Pi，存在函数fs：C→ N（其中N在自然数的有限前缀上延伸），函数fs将每个配置映射到基于调度噪声量的大小由配置Ci插入，以及它在位置之间划分的方式。函数fs旨在将高度噪声集中在最小数量的位置中。显然，其他目标函数也是可能的。例如，最大化单次运行中发生的数据竞争数量的函数或最大化覆盖标准的函数（如[5]中所用）。在这项工作中提出的目标函数的自然扩展可以是接收一组配置作为其输入的函数。这些函数旨在最大化一组配置的目标（可能是多个执行次数）。这些功能可以测量总体并发覆盖率标准[10]或收集有关程序的总体统计数据[11]。例如，考虑一个函数，它最大化给定数量的测试所发生的不同数据竞争的总数。函数fs的计算由公式明确给出。然而，函数fp在每一点上都是未知的。因此，fp必须通过应用贝叶斯规则来推导，以使用关于每个配置中出现错误的次数的观察来产生后验概率（详细信息请参见[9]）。我们将在下一节4遗传学我们实现了一个使用遗传算法的racebooks变体，一种搜索方法（称为遗传算法）。下面是该实现的表示、搜索运算符和适合性评估4.1表示和运算符遗传算法对代表可能的解决方案（染色体）的个体群体进行操作。这些候选者最初是随机创建的，经过组合和变异，演变成新一代的解决方案，这些解决方案可能更适合。繁殖提供了一种在种群内混合遗传物质的机制。突变引入新的遗传物质，从而防止搜索停滞。下一个种群的解决方案是根据有利于适合个体的生存策略从父代和子代中选择的。在遗传学中，每个染色体使用三个-66Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57hash table hash table哈希表中的第一层包含启发式名称，用作访问第二层的关键字，第二层包含每个启发式的变量和程序位置。每个试探法通过随机选择一对“父“配置来完成简化每一个父代都将其算法的一个随机子集（然后是变量和程序位置的一个子集）贡献给新的“o-spring“配置。当两个父代都将相同的启发式算法和位置（或变量）添加到O型弹簧时，其噪声参数是随机选择的，并受父代值的约束。突变之前选择启发式变量或位置的子集，并将它们从“O-弹簧”配置中删除。这样做是为了创建更小的配置，仍然表现出并发错误。突变算子的“传统“角色，即，引入新的遗传物质是通过每一代随机产生许多新的构型来实现的。4.2适应度评估遗传算法在寻找最优解方面的成功在很大程度上取决于选择一个合适的函数，该函数将沿着有希望的路径进行搜索。拟合函数是目标函数的加权组合，并表征被认为是好的解决方案。给定两个可能的解决方案，它确定其中哪一个提供了更好的所需属性集。 这里，拟合函数是3.2节中定义的函数的混合。在接下来的段落中，我们将描述如何评估这些函数首先，我们讨论了fs函数的求值。一个好的解决方案的一个理想属性应该是它能够在源代码中提供有关错误原因的信息。直观地说，搜索过程可以描述为过滤掉与bug无关的位置（和变量），直到只剩下一小组相关位置。在剩余组中的位置或变量上具有高度的噪声通常与与bug相关的源代码位置高度相关。我们通过结合两个不同的函数来计算fs：大小和熵。函数大小的目的是偏好具有少量“噪声“位置或变量的解决方案程序位置的粒度更小因为每个变量将一组程序的位置组合在一起因此，我们更喜欢的解决方案包含- ING程序位置的解决方案包含类似数量的变量。噪声以不同的概率应用于每个变量或程序位置-Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）5767抽搐强度因此，函数大小计算应用于程序位置和变量的噪声强度的加权和。它的计算如下：设Ni ， j是配置C i的第j个种子对象中N让函数elementSize将每个类型播种对象映射到预定义的大小（例如1，2或8，取决于项目j的类型：位置，拆分访问变量或变量）。函数大小（Ci）的计算如下：Σ|Ci|（一）size=j=1Ni，j·elementSize（Ci，j）该函数将具有总高度噪声的配置映射到更高的值。当然，这种偏好确实准确地表示了配置包含的调试信息量（考虑没有噪声应用或噪声应用于许多变量的情况）。因此，需要评估噪声在噪声位置和变量之间划分的方式。优先考虑具有分布在少数位置之间的高度噪声的配置（与熵测度[3]大致相似）。因此，我们将该函数表示为熵，并如下计算：（二）熵=−Σ|Ci|Ni，j日志.ΣNi，jj=1size（Ci）尺寸（Ci）函数fs被构造为大小和熵的组合1（三）fs=size（Ci）+熵（Ci）将这两个函数集成到拟合函数中，倾向于选择具有较少的种子程序位置的配置，这些种子程序位置具有施加在它们上的高程度的噪声。此外，我们的目标是更喜欢一个配置（或多个配置），以高概率人为bug。由于调度器被假设为确定性的，我们可以假设一个给定的配置（执行足够的次数）以某种未知的概率出现错误。我们无法估计这种可能性之前，错误实际表现出来。然而，我们可以在测试期间估计该概率的上限，并据此评估适合性（这是通过使用贝叶斯规则导出的）。例如，如果在第100次运行中没有发现错误，我们假设概率低于0.01。准确性取决于配置执行的次数，我们认为基于更多执行的结果更重要。我们68Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57p我计算fp如下：（四）f = fb（Ci）+ log（C（t））。Ci（t）4.3遗传搜索过程在搜索的初始化阶段，创建了一个随机的配置池。搜索进程是按代来衡量的。在池中找到的每一代配置都执行预定次数。在配置完成执行后，将为该配置计算适应性函数。当给定生成的所有配置都完成了它们的执行时，它们将按照它们的适合性级别进行排序。一组排名最高的配置在池中保持不变，以便在下一代中再次执行。另一个集合，排名最低的配置，被随机创建的一组新配置所取代。其余的配置形成第三组。如前一节所述，从后一组和待配对和突变的高等级配置组中随机选择配置。这个过程会在搜索开始前确定的预定代数内继续进行5实验结果我们试验了从公开的多线程基准测试[7]中获取的程序，其中包含有并发错误的程序。每个程序都有不同的变量和与错误相关的程序位置，只有在这些位置应用噪声才能让错误显现出来。这些位置的先验知识仅用于评估搜索过程的成功。基准程序在每次执行后报告是否出现了bug，这些信息作为测试结果。在搜索过程开始之前，通过执行程序预定次数来收集有关程序变量、拆分访问变量和程序位置的信息为了演示我们的方法，我们专注于一个示例程序。本文对该方案进行了分析，并对相关的实验结果进行了详细的讨论.从我们实验的其他程序中获得的结果是相似的。5.1详细示例我们简要地描述了一个例子程序称为分配最大值。这个程序输出作为输入的整数数组的最大值（称为integersArray）。最大值是在分配Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）5769使用一组线程的方式。每个线程与数组中的一个单元格相关联，并将其关联单元格的值与全局共享变量进行比较，该变量包含在程序执行中的该点之前发现的更新的全局最大值（称为globalMaximum）。这将导致globalMaximum的值单调增加，直到它达到数组的最大当一个线程开始运行时，一个局部线程变量被初始化为它的关联单元（称为index）的数组中的对象集。在执行过程中，每个线程都会到达以下代码块：(1) If（integersArray[index] > globalMaximum）(2) globalMaximum = integersArray[index]上面的代码包含两个与变量globalMax-imum相关的数据竞争。因此，有两种可能的不规则调度场景导致bug显现（即最大值的错误计算）：（a）在globalMaximum被读入（1）之前发生上下文切换。在这种情况下，globalMaximum的值被另一个线程更改然而，第一个线程看不到这种变化，一旦它重新获得控制权，if语句的条件可能不正确。由于没有再次评估条件，因此可能会将错误的较低值写入globalMaximum（b）在globalMaximum写入（2）之前发生上下文切换。类似地，一旦第一个线程重新获得控制权，可能已经有更高的值写入了globalMaximum。在这种情况下，globalMaximum可能会再次写入错误的较低值。请注意，无论（a）或（b）发生，bug都会表现出来。5.2结果和分析为了测试我们的方法，我们使用来自基准测试的不同程序应用遗传搜索过程。我们提出了详细的结果分配的最大值计划。我们用一组小群体（10-20条染色体）进行了实验。在我们的实验中，最好的配置通常是在程序位置（1）或（2）（来自上面的代码示例）和其他与bug无关的位置和变量上应用噪声。排名非常高的配置（按总体适合度）通常包含的种子对象数量明显较低。如果有足够的运行时间（通常20-30分钟），搜索过程会收敛到只包含70Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57在实验中，我们测量了随着搜索的进行，配置大小的值（使用大小函数）和获得的解决方案的总质量（使用适应度函数）的变化。进展是通过从搜索开始以来经过的代数来衡量的。我们测量了两个函数的以下值：• 每一代最佳配置的价值• 配置池中所有配置的平均值• 在上一代配置池中保持不变的所有配置的平均值池中的配置按每一代的适合度水平排序。我们发现，所有三组的结果表现相似。我们注意到，遗传搜索过程通常朝着缩小不必要的种子变量和程序位置的数量的方向发展较小的配置每隔少量的世代就成为高级别的配置。解决方案的整体适合性不断提高，直到收敛。进一步的改进只有通过GA一遍又一遍地运行相同的配置才能实现，从而增加了他们预测的错误表现概率的置信度。在运行过程中，由于发现的bug数量只是发现bug的配置概率的近似值，因此它有时是不正确的（低估了正确的概率），因此适应性水平有时会降低一小部分。在早期的实验中，搜索过程有时会收敛到单个拆分访问变量仅包含分割访问变量的配置具有支配拟合度计算的错误的高显现率。为了确保搜索过程收敛到程序位置（1）或（2），并提供更多的调试信息，我们增加了elementSize函数中变量和拆分访问变量的权重（对于程序位置，拆分访问变量和变量分别从1，2，4到1，4，8）。为了验证新的构型是在遗传过程中产生的，我们测量了每个构型的年龄（即自其产生以来的世代数）。我们注意到不同的配置参与了搜索过程（我们测量了排名最高的配置的年龄和池中所有配置的平均年龄）。在搜索过程开始收敛到一个解决方案之后，配置的年龄稳步上升。该行为与拟合度和尺寸测量结果相关。Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57716结论和今后的工作这项工作提出了重新制定随机测试生成的并发Java程序（以噪音的形式）作为一个搜索问题。将测试生成视为搜索问题允许将一组众所周知的AI搜索技术应用于生成器的输入空间。搜索过程迭代地调整调度噪声以创建测试场景，该测试场景在单个执行或可能的一组执行中最大化预定义的目标函数。为了证明我们的方法，我们开发了遗传算法，一个新的变种的racebooking工具，基于使用遗传算法作为搜索方法。遗传算法的目标是最大化两个预定义的目标函数，第一，实现高概率的错误表现在每一个experiments的程序，第二，出口高度的调试信息给用户。实验结果表明该方法是有效的。此外，我们开发的框架通过提供灵活性来定义各种目标函数或这些函数的加权组合，从而概括了以前旨在实现特定目标的工作此外，它可以允许在未来与来自不同测试范例的其他测试工具进行轻松的交互。Raceplane是一个正在进行的研究项目。需要进一步的研究来制定搜索的停止标准，并改进拟合函数以包含更多的特征。众所周知，遗传算法的并行执行改善了其结果。我们计划在今后试验这种实施办法。我们还计划将GA与其他自然启发的方法，如粒子群优化和蚁群优化进行比较和结合。确认我感谢Sadek Jbara在遗传学中实现了许多功能，感谢Shlomo Berkovsky，Edward Furman，Larry Manevitz和Shmuel Ur在本文准备期间提供的帮助引用[1] C. Artho，K. Havelund，A.比尔“高水平的数据竞赛”。软件测试，验证可靠性13（4）：207-227（2003）[2] Y. Ben-Asher，Y. Eytani和E. Farchi，[3] C. E. 香农 贝尔系统技术公司J. 27（1948），379-423，623-659.72Y. Eytani/Electronic Notes in Theoretical Computer Science 144（2006）57[4] J.D.崔，M。古普塔，M。Serrano、V. Sreedhar和S. Midki Java的Escape分析面向对象编程系统、语言和应用会议（OOPSLA），1999年。[5] O. Edelstein，E. Farchi，E. Goldin，Y. Nir，G. Ratsaby，S. Ur.“Framework for TestingMulti- Concurrency and Computation ： Practice and Experience 15 （ 3-5 ） ： 485-499（2003）.[6] Y.艾塔尼在Java中查找并发bug的有效框架。硕士论文。海法大学计算机科学系，已提交。[7] Y. Eytani，K. Havelund，S. D. Stoller和S. Ur. Toward a Framework and Benchmark forTesting Tools for Multi-Threaded Programs. Concurrency and Computation ： PracticeExperience，即将出版。[8] E. Farchi，Y.Nir和S.Ur. 并行和分布式系统研讨会：测试和调试，2003年。[9] S. 好吧AZiv. 发援会议事录，2003年[10] S.好吧S Ur，A. Ziv.“Probably Regression Suites for Functional Verification.”发援会议事录，2004年[11] B. Finkbeiner，S. Sankaranarayanan和H.西普玛”《明史》：“以刑求刑。在第二次研讨会上验证（RV），第70卷（4），理论计算机科学中的电子Elsevier 2002.[12] C. Flanagan和S. N.弗罗因德“Atomizer: A Dynamic Atomicity Checker for Multithreaded第31届ACM SIGPLAN Symposium on Principles of Programming Languages（POPL），2004年1月。[13] D. E. Goldberg，R. Burch.“遗传算法在搜索、优化和机器学习中的应用”。AW Publ.，一九八九年[14] K.哈夫隆使用XML分析来指导Java程序的模型检查。SPIN，2000年。[15] B.朗和帕。斯楚珀Java组件中的并发故障分类 并行和分布式系统研讨会：测试和调试，2003年。[16] S. 萨维奇，M。Burrows，G.Nelson，P.Sobalvarro，T.安德森 ACM Transactions onComputer Systems，1997年。[17] S. D.斯托勒“使用随机调度测试并发Java程序”。在第二次研讨会上验证（RV），第70卷（4），理论计算机科学中的电子笔记。Elsevier，2002年。[18] W. Visser，K. Havelund，G. Brat，S. Park和F.勒达模型检查程序。International Journalon Robust Software Engineering 10（2），2003年4月。[19] L. Wang和S. D.斯托勒“原子性的运行时分析。”在第三次研讨会上验证（RV），第89卷（2），理论计算机科学中的电子笔记Elsevier，2003年。[20] J. Clark，J. J. Dolado，M.哈曼河希龙湾琼斯，M。卢姆金湾米切尔，S。曼科利，K.里斯，M。Roper和M.谢泼德“将软件工程重新定义为搜索问题。IEE Proceedings - Software150（3）：161-175，2003.