基于变异的时序测试用例生成：实时系统测试方法研究

理论计算机科学电子笔记164（2006）97-114www.elsevier.com/locate/entcs基于变异的时序测试用例生成Robert Nilssona，1，2，Je Jo Jo Jouuttb，3乔纳斯·梅林（Jonas Mellin），1，4a分布式实时系统研究组莫斯科大学Skéovde，Sweden乔治梅森大学美国弗吉尼亚州费尔法克斯摘要时间正确性对于实时系统是至关重要的。很少有方法可以测试时间正确性，实际中使用的大多数方法都是临时的。 测试实时应用程序的一个问题是响应时间依赖于并发任务的执行顺序。执行顺序又取决于执行环境属性，例如调度协议、互斥资源的使用以及注入激励的时间点。基于模型的突变测试以前曾被提出来确定需要验证的执行顺序，以增加及时性的信心。因此，仍然需要一种有效的方法来自动生成动态实时系统的测试用例。本文提出了一种基于仿真驱动的测试用例生成方法。保留字：实时系统，突变测试，基于1介绍当前的实时系统必须既灵活又及时。期望增加实时系统在使用很少的标准化硬件组件的同时所提供的服务的数量。这可能会增加系统的复杂性，并引入时间不确定性的来源（例如，缓存和管道），这使得很难预测任务的执行行为[26]。这种预测中的错误可能导致软件时效性违规和代价高昂的事故。因此，我们需要方法来检测违反计算机体系结构的时序约束，1这项工作由瑞典战略研究基金会通过FLEX- CON方案提供资金。2电子邮件：robert. his.se3电子邮件：offutt@ise.gmu.edu4 电子邮件：jonas. his.se1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.10.01098R. Nilsson等理论计算机科学电子笔记164（2006）97我们不能依赖于精确的直线假设。 时间性是软件满足时间约束的能力。例如，对飞行器监视系统的时间限制可以是，一旦请求着陆许可，必须在30秒内提供响应[28]。在设计实时系统时，软件行为由竞争系统资源（例如，处理器时间，内存和信号量）的周期性和偶发性任务这些任务的响应时间取决于它们的调度执行顺序周期性任务以固定的到达间隔时间被激活，因此这些任务被激活的所有时间点都是已知的。零星的任务是动态激活的，但假设他们的激活模式，如最小的到达时间间隔，在分析中使用。每个实时任务通常都有一个截止日期。Tasks也可以有一个o_set，它表示该类型的任务被激活之前的时间。测试方法必须适应解决的及时性，因为它是难以表征的关键序列的输入，而不考虑的活动任务和实时协议的集合上的效果。然而，现有的测试技术很少在测试用例生成中使用有关实时设计的信息，也没有预测什么执行顺序可能会揭示O-线假设中的错误（参见第5节相关工作的概述）。在实时社区中，传统上使用调度分析技术来分析和维护及时性，或者通过准入控制和应急计划在线调节。然而，这些技术使用关于任务和激活模式的假设，这些假设必须是正确的以保持及时性。此外，对非平凡系统模型进行完全可扩展性分析是复杂的，并且需要运行时系统遵循特定的规则。相比之下，及时性测试是通用的，因为它适用于所有系统架构，并且可以作为补充，通过系统地对可能导致错过最后期限的执行订单进行抽样，来获得对假设的信心。然而，在存在定时故障的情况下，只有一些可能的执行顺序通常揭示了时间性违规。基于突变的时间性测试受到Ammann，Black和Majurski [2]提出的基于模型的自动测试用例生成方法的启发。该方法背后的主要思想是系统地“猜测”系统包含哪些故障，然后评估这些故障在系统模型中的影响。一旦识别出具有不良后果的故障，就会构建测试用例，试图揭示系统实现中的这些故障。模型检查以前曾用于分析实时系统的模型，以生成用于测试及时性的测试用例[22]。在这种情况下的一个问题是，动态实时系统模型的分析往往变得如此计算复杂，以前提出的模型检查方法不工作。特别是，这发生在事件触发系统的模型中，其中不同的零星中断的定时可以影响任务的执行顺序[31]。本文研究了特定于应用程序的算法和仿真是否R. Nilsson等理论计算机科学电子笔记164（2006）9799可以用作分析此类模型的替代方案。因此，本文提出了一种方法，其中捕获可能的执行行为的变异规范模型被映射到模拟器。然后，使用遗传算法迭代地执行模拟器，以找到揭示突变模型中潜在故障的输入序列。该方法在两个实验中证明。第一个实验将该方法与基于模型检测的方法进行了比较，以获得其可靠性的基本信心。该方法还使用更大，更动态的系统规范进行评估，基于模型检查的方法失败。实验结果表明，基于仿真的方法对动态规格化模型仍然有效，提出的启发式函数提高了性能.基于突变的及时性测试的输入是实时系统和测试标准的规范。测试标准指定了使用什么样的变异算子，从而决定了测试的彻底性水平以及将产生什么样的测试用例。突变生成器将突变操作符应用于规范，并将突变的规范发送到执行顺序分析器，该分析器确定突变是否以及如何导致及时性失败。我们称一个包含错误的变异的规范模型，到一个时间性的失败一个恶性突变体。 如果分析显示违反了时效性在突变模型中，突变体被标记为被杀死。来自被杀死的突变体的痕迹被输入到测试用例生成过滤器中，该过滤器提取激活模式，该激活模式具有检测与实际测试系统中的恶性突变体类似的故障的能力。还可以自动提取在注入输入激励时可能导致最后期限违反的任务的执行顺序。 在测试用例执行过程中，根据激活模式将测试输入注入实时系统。在测试可伸缩实时系统时，与可控性和可观性相关的问题不在本文讨论范围之内基于前缀和非确定性测试执行技术[15，33，21]是对我们方法的补充2系统模型和测试标准本文使用带有任务的时间自动机（TAT）[24，11]的一个子集来定义关于被测系统的假设，并作为基于模型的测试用例生成的来源。时间自动机（TA）[1]已经被用来对实时系统的许多不同方面进行建模。TA是一个有限状态机，扩展了一组实值时钟。 每个转换可以有一个保护，一个动作和一些时钟重置。守卫是时钟和变量的条件，例如时间约束。动作可以进行计算并为变量赋值。时钟从零开始均匀地增加，直到它们在转换中单独重置。当时钟被重置时，它会立即被设置为零，然后开始以与其他时钟相同的速率增加（我们假设同步时钟）。在TAT模型中，TA用于指定任务的激活模式，即请求不同任务执行的顺序和时间点。此外，TAT100R. Nilsson等理论计算机科学电子笔记164（2006）97用一组实时任务P扩展了TA表示法，需要调度实时任务P以响应于激活来执行计算。P中的元素将任务的信息表示为四元组（c，d，SEM，PREC），其中c是任务的假定执行时间，d是相对截止日期，SEM和PREC在以下段落中定义。共享资源由一组的系统范围的信号量，R，其中每个信号量s∈R可以被锁定和解除锁定。在任务执行的固定时间点被任务锁定。 集合SEM包含元组形式为（s，t1，t2），其中t1和t2是信号量s∈R的锁定和解锁时间。这些时间是相对于任务的开始时间来表示的。优先约束是任务A和B对之间的关系，说明a的实例任务A必须在任务B的两个连续实例的执行之间完成执行（否则，任务B的第二个实例被阻塞）。因此，PREC是P的一个子集，它指定了在此任务之前必须执行的其他任务我们称任务在TAT中，任务执行模式是固定的。这可能看起来不切实际，特别是如果任务的输入数据可能会有所不同。在这一步中，我们假设任务的执行模式与输入数据的特定（典型或最坏情况）等价类相关联。在发现关键激活模式后，可以使用该序列中的不同任务输入对目标系统进行多次测试，并对其施加压力以揭示错误行为。2.1变异算子测试标准定义了测试软件时必须满足的测试要求。测试标准的一个示例是“执行所有语句一次”。测试覆盖率度量表示测试满足测试标准的程度，通常是指满足了多少测试需求。基于突变的测试准则由一组变异算子定义。因此，测试的进展可以用测试用例生成过程中杀死的突变体来表示。例如，如果在目标系统上运行了一组通过杀死所有恶性“（Δ = 3）执行时间突变体”而得到的测试用例，则该测试标准已达到100%的覆盖率。变异操作符模拟可能导致时效性失败的故障。我们之前的工作识别并提出了七种类型的错误或偏离假设的正式定义，这些错误或偏离可能导致时间性故障[22]，而本文非正式地描述了算子，并根据创建的突变体的最大数量对其进行了分类。2.1.1时间复杂度O（n）下面的运算符创建2n个突变体，其中n是任务的数量。执行时间运算符通过以下方式增加任务的建模最坏情况执行时间： 恒定时间Δ或以相同的量减少最佳情况的执行时间这种变化代表了一种情况，其中用于分析的任务执行时间的假设R. Nilsson等理论计算机科学电子笔记164（2006）97101在执行中可以。最小到达间隔时间操作符将任务执行请求之间的假定到达间隔时间减少或增加一个常数时间Δ。这反映了系统环境的变化，导致请求比预期的更频繁或更不频繁。还可以假设这种重复的环境请求已经彼此固定。模式操作符在两个激活模式之间改变操作符集，改变的是一个恒定的Δ时间单位。2.1.2时间复杂度O（nrl）这些变异操作符通过Δ时间单位增加或减少特定资源被锁定的时间锁定时间操作符更改资源锁定的时间点，解锁时间操作符更改相对于任务开始时间的资源解锁时间。保持时间移位操作符更改锁定和解锁时间。由于为每对任务和资源受保护的临界区创建突变体，因此突变体的最大数量为2nrl，其中r是资源的数量，l是需要资源的最大次数在整个执行过程中的特定任务。2.1.3时间复杂度O（n）对于每对任务，如果这对任务之间存在优先约束，则被移除。如果没有优先约束，则添加新约束。 一个任务不能被限制在自身之前，所以可以被执行的突变体的数量是有限的生成的是n2-n。3 基于遗传算法的测试自动生成先前提出的基于模型检查的方法[22]对于分析突变的TAT模型是安全的，因为如果存在漏洞，则可以保证将其揭示出来。然而，对于某些系统的状态空间变得太大，模型检查是有效的。特别地，当允许触发事件在许多不同的时间点发生时，计算复杂度（时间和存储器两者）增加。在动态实时系统中，有许多零星的任务，使模型检测不切实际。对于这些系统，我们提出了一种方法，其中每个突变模型的模拟迭代运行，并使用具有应用特定性的遗传算法进行评估。通过使用基于模拟的方法代替模型检测来分析执行顺序，避免了全状态探测的组合爆炸。此外，我们推测，它是更容易修改系统模拟比模型检查器，对应于测试中的系统的架构。当仿真用于突变分析时，模型任务集必须映射到实时仿真器中的任务实体。周期性任务的激活模式是已知的，并且可以包含在模拟器的静态配置中。在每次模拟迭代中，零星任务的激活模式应该有所不同102R. Nilsson等理论计算机科学电子笔记164（2006）97找出可能导致时效性失效的执行顺序。因此，一个必要的输入到一个特定的TAT模型的模拟是一个激活模式的零星任务。模拟的相关输出是一个执行顺序跟踪，其中根据激活模式注入了零星请求。从测试的角度来看，一个理想的输出是执行顺序跟踪，它会导致突变体中的及时性失败通过将TAT模型的测试用例生成视为一个优化问题，可以应用不同的启发式方法来找到导致错过截止线的轨迹。本文重点介绍遗传算法，因为它们具有高度可配置性，并且可以很好地处理包含局部最优值的优化问题[18]。遗传算法通过随机变化和组合现有解决方案的特征来迭代地细化优化问题在这种情况下，解决方案被称为个体和个体的集合人口被称为人口。每个个体都有一个基因组，以标准化的格式提供独特的功能。基因组的常见格式是位串和实数数组.因此，遗传算法的用户必须提供从任何标准格式的基因组到问题的特定候选解决方案的问题特定映射函数。有人认为，映射是遗传算法的成功的重要。例如，希望所有可能的基因组都代表有效的解决方案[18]。在遗传算法中，适应度函数的作用是评估特定个体的最优性或适应度。 最适合的人在一个群体中，有更高的概率被选择作为交叉功能的输入，并被复制到下一代。交叉功能应用于选定的个体，以在下一代中创造具有更高适应性的新个体。这意味着组合来自多个个体的属性，或者根据遗传学修改单个个体。传统上，应用于单个个体的功能被称为“但利用个体的信息为下一代创造基因组。有通用的交叉功能，对任意基因组进行操作，按下标准格式。 例如，交叉功能可以交换二进制字符串基因组中的两个子字符串或增加数组中的某个随机实值。然而，取决于基因组的编码，标准的交叉功能在增强个体方面可能或多或少成功使用问题域和映射函数的知识，可以以增加创建具有高拟合度的个体的概率的方式定制交叉函数。另一方面，一些交叉函数必须保持随机性，以防止搜索陷入局部最优。遗传算法的搜索通常会持续预定的世代数，或者直到找到一个适合度值超过某个集合界限的总而言之，需要定义三种类型的函数以应用遗传算法。用于突变测试的突变直接作用于模型的结构，而不是驱动模型遍历的输入的时间序列R. Nilsson等理论计算机科学电子笔记164（2006）97103y == OFS（i） +T（i，1） y：= 0y == MIAT（i）+T（i，j） y：= 0释放任务iy = MIAT（i） +T（i，j）Fig. 1.带注释的TAT模板具体搜索问题的算法：（i）基因组映射函数，（ii）启发式交叉函数，以及（iii）适合度函数。下面的小节建议这样的函数，用于从动态实时系统模型生成基于变异的测试用例。3.1基因组作图功能对于测试用例生成问题，在相同突变TAT模型的模拟之间唯一不同的是非周期性任务的激活模式，因此，基因组可以映射到这样的激活模式是足够的。每个激活模式确定性地导致模拟中的特定执行顺序跟踪。执行顺序跟踪是这个搜索问题的个体。图1包含一个带注释的TAT自动机，用于描述零星任务的激活在一般情况下，激活模式可以由任何时间自动机表示，但本文侧重于零星的任务模板，因为这样的任务是常见的实时系统模型。模板具有对于每个突变体恒定的两个参数。参数OFS提供假定的操作集，即假定请求此任务的任何实例之前的最小延迟。MIAT提供偶发任务实例之间的假定最小到达间隔时间。一个实值数组T（i，1. m）定义可变延迟间隔的持续时间在零星任务的连续请求之间i.这里m是模拟过程中可能发生的最大激活次数。通过组合突变任务集合P中的n个零星任务的阵列，我们得到矩阵T（1. n，1..m），其中每行对应于偶发任务的激活模式。矩阵T可以用作突变体的所有有效激活模式的基因组表示3.2启发式交叉函数对于时间性的测试，有什么样的激活模式可能会对突变体造成压力的直观分析。例如，以类似突发的方式释放许多不同类型的零星请求似乎比均匀分布的激活更有可能揭示时效性违规。需要引入几个概念来简化启发式交叉函数的定义。我们使用关键任务实例来表示执行顺序跟踪中具有最小松弛的任务实例。关键间隔（[cibeg，ciend]）是关键任务实例的激活时间和响应时间之间偏移y = OFS（i） +T（i，1）104R. Nilsson等理论计算机科学电子笔记164（2006）97空闲点是没有实时任务执行或在处理器上排队等待立即执行的时间点。加载间隔（[libeg，liend]）是关键任务实例的最新空闲点和激活时间之间的间隔。变量M是一个TAT模型，包含n个由自动机模板控制的零星任务，如图1所示。大小为nm的基因组矩阵由变量T表示。整数变量i用于对基因组矩阵T中的行进行索引。这样的矩阵中的行对应于零星任务，因此它由1和n限定。整数变量j用于索引基因组矩阵中的列，并且以1和m为界。变量用于表示一个小的正实数。表达式[abeg，aend]±[bbeg，bend]表示左手区间[abeg，aend]是右手区间[bbeg，bend]的子区间。形式上，这可以表示为（[abeg，aend]±[bbeg，bend]）<$$>（abeg≥bbeg<$aend≤bend）。 此外，从T和M导出的延迟间隔矩阵D（见定义3.1）用于定义以下小节中的交叉函数。定义3.1：延迟间隔矩阵D一个大小为nm的矩阵，它包含T中每个偶发任务激活的可变延迟间隔，使得：D（i，j）=[epat（i，j），epat（i，j）+T（i，j）]，其中epat（i，j）是偶发任务i的第j个实例的最早可能到达时间TAT模型M和基因组矩阵T。3.2.1聚焦临界间隔该交叉功能分析来自模拟的日志，以找到关键间隔。随机选择一个偶发任务，并对其进行更改，以增加其在临界时间间隔内执行的概率。定义3.2：聚焦关键间隔左侧对于任意的索引i，设j是最大的索引，使得D（i，j）±[0，cibeg]然后以1/4时间单位增加T（i，j），以1/4时间单位减少T定义3.3：聚焦关键区间对于任意索引i，设j是使得D（i，j）±[cibeg，ciend]的每个索引，并且修改T使得T（i，j）= 0。3.2.2临界区间移动所有零星的任务激活模式移动一个小的随机周期，使序列的零星请求导致一个关键的时间间隔发生在其他一些点相对于静态到达模式的周期性任务。定义3.4：关键区间移动对于每一个指数i，使得D（i，1）±[0，cibeg]，增加或减少T（i，1），时间单位为π3.2.3新的区间焦点该交叉函数生成新的候选临界区间，以防止优化陷入局部最优。通过以下方式选择新的时间点R. Nilsson等理论计算机科学电子笔记164（2006）97105随机的，并且所有最近的偶发激活被移向所选择的时间点定义3.5新的区间焦点设tnew为模拟区间内的任意时刻。 对于每个索引i，设j是使得D（i，j）±[0，tnew]的最大索引，并以1/4时间单位增加T（i，j）同样，以1/4时间为单位减小T（i，j+1）3.2.4加载区间摄动从理论上讲，当关键任务实例发生激活时，加载间隔中的所有任务激活都可能通过系统中的状态影响及时性加载间隔结束时的变化对关键任务实例的及时性有直接影响。该交叉功能在加载间隔结束时改变激活模式。定义3.6：加载间隔扰动对于任何索引i，设j是最大索引，使得D（i，j）±[libeg，liend]且j>1，修改T，使得T（i，j−1）= 1/2时间单位。3.3适应度函数由于我们的有效激活模式的基因组表示在没有特定的TAT突变模型的情况下是没有意义的一旦我们运行了模拟，我们就可以使用执行顺序跟踪来确定特定个体的最佳程度。一个合适的时效性函数应该衡量一个系统离最后期限有多近。松弛时间是任务实例的响应时间与其截止日期之间的时间。因此，在模拟期间观察到的最小松弛用于确定适合性。将最高拟合度赋予导致具有最小松弛的模拟执行顺序的激活模式更精细的拟合函数（例如，使用基于多样性或平均响应时间的加权）将在未来的工作中进行评估，以提高遗传算法的性能。4测试用例生成实验为了评估所提出的方法，我们进行了两个单独的实验。第一个尝试通过将其应用于一个小型系统模型来建立该方法的基本置信度，我们也可以使用模型检查器来生成测试。这使得该方法可以在基线实验中进行比较，并检测遗传算法方法在发现任何特定类型的突变体时是否存在问题。第二个实验使用了一个更大的系统模型，以评估如何基于模拟的测试用例生成处理任务集与大部分的零星任务下的动态实时系统协议。为了进行实验，我们扩展了实时和控制协同仿真工具TrueTime来模拟TAT模型的执行。TrueTime开发106R. Nilsson等理论计算机科学电子笔记164（2006）97表1基线实时系统任务集IDTAT四重我O一（3，7，{（S1，0，2）}，{D}）≥2810B（5，13，{（S1，0，4），（S2，0，5）}，{}）≥3018C（7，17，{（S1，2，6），（S2，0，4）}，{}）406D（7，29，{}，{}）200E（3，48，{（S1，0，3），（S2，0，3）}，{}）404在隆德大学自动控制系，支持控制器和实时控制器的集成设计[12]。我们还确认并扩展了遗传算法工具箱[14]，以与我们的模拟模型进行交互。对于模型检查实验，我们使用了乌普萨拉大学开发的Times工具[3]。4.1基线实时系统实验这个实验使用了一个小的任务集，只有很少的零星任务，但有很多可能的互动。静态优先级分配给任务使用的截止日期单调计划，即最高的优先级被赋予最早的相对截止日期的任务该系统使用立即上限优先级协议来避免优先级反转[32]。也就是说，如果一个任务锁定了一个信号量，那么它的优先级就变成了等于可能使用该信号量的最高优先级任务的优先级，并且总是在较低优先级任务之前调度。表1总结了任务集的假设。第一列（对于零星任务，对于周期性任务，“I”列包含固定的到达间隔时间。列表2包含测试用例生成的结果 列“μ“包含针对每个突变算子生成的突变体的数量。恶性突变体的数量列在“M”列中，通过模型检验杀死的突变体的数量列在“C”列中。使用1个时间单位的Δ值来产生突变体。 对于遗传算法设置，我们使用每代20个个体的群体，并在终止前运行每个突变体100代（遗传算法的更多参数可在扩展版本中获得[23]）。我们使用了3.2节中描述的启发式交叉函数以及三个通用的交叉功能（i）改变基因组表示中的随机值（ii）在群体中创建新的随机个体，以及（iii）用0替换基因组中的随机值。每个实验使用不同的随机种子和随机初始种群重新运行八次。 突变体数量R. Nilsson等理论计算机科学电子笔记164（2006）97107表2基线实时系统实验突变类型μMCK一G执行时间106665.8（0.1）7.6（207.8）锁定时间81111.0（0）1.3（0.2）解锁时间112222.0（0）2.2（3.1）保持时间偏移14010--优先2014151414.0（0）1.2（0.8）到达间隔时间103433.0（0）5.7（53.7）图案或图案集103533.0（0）2.5（8.7）总8329332928.8-在任何试验中使用遗传算法杀死的动物都列在“K”栏中。列杀死这种类型的恶性突变体所需的平均代数在“G”列中如表2所示，模型检查（“C”）和基于模拟（“K”）的方法都模型检测的方法不仅杀死了所有的恶性突变体，也杀死了一些良性突变体。通过比较被杀死的良性突变体的执行顺序，我们观察到任务有时会在模型检查器产生的跟踪中开始执行之前继承天花板优先级。我们推测模型检查工具实现了与最初定义的立即优先级上限协议不同的版本[32]。由于我们不知道协议的模型检查器实现的确切语义和属性，我们使用原始定义。一个有趣的发现是，所有恶性突变体平均在10代内被杀死此外，在8个试验中的7个中，所有恶性突变体都被杀死。4.2动态实时系统实验在此设置中，我们使用最早期限优先（EDF）动态调度算法以及堆栈资源协议（SRP）。EDF协议动态地重新分配任务的优先级，使得具有当前最早截止期限的任务获得最高优先级。SRP协议是一种并发控制协议，在动态优先级调度下，防止阻塞链和死锁。这是通过不允许任务开始执行，直到它们可以完成而不会被阻塞[4]。该系统由12个硬实时任务组成，其中7个是零星的，只有5个是周期性的。系统有三个共享资源，但没有优先级108R. Nilsson等理论计算机科学电子笔记164（2006）97表3动态实时系统IDTAT四重我O一（3，20，{（S1，0，2），（S2，0，2）}，{}）≥28 10B（4，24，{（S1，0，3）}，{}）≥304C（5，35，{（S2，2，5）}，{}）≥386D（6，57，{（S2，0，6），（S3，2，5）}，{}）≥480E（5，51，{}，{}）≥527F（6，39，{（S3，3，6）}，{}）≥440G（3，52，{}，{}）≥522H（3，38，{（S3，0，2）}，{}）405我（3，35，{（S1，1，2）}，{}）482J（4，52，{}，{}）602K（2，70，{（S2，0，2）}，{}）8010L（3，59，{}，{}）6012约束表3列出了完整的任务特征，使用与表1相同的符号。对于这个系统来说，人工推导恶性突变体太耗时了。此外，第一个实验中使用的模型检查工具无法用于比较，因为可达状态空间变得太大。可以采用其他更先进的模型检查工具进行分析TAT模型的可验证性。然而，从TAT模型到其他模型检查器表示的映射并不是微不足道的。此外，由于Times工具中的验证器是更常用的Uppaal工具中的验证器的扩展[5]，因此我们假设其性能代表这种分析。由于我们无法找到一种替代方法来有效和可靠地分析突变体，我们不能保证该方法杀死了所有恶性突变体。为了增加对原始规范模型的及时性的信心，每个生成的测试用例也在未突变的TAT规范上运行。这个测试实际上揭示了一个模型中的一个错误，这个模型在另一个实验中被认为是及时的我们对每个突变体运行遗传算法200代，或者直到遇到失败。每个实验进行五次。对于在启发式搜索期间执行的每R. Nilsson等理论计算机科学电子笔记164（2006）97109个模拟，还执行具有随机到达模式的模拟。这给出了模型的随机搜索（和目标系统的随机测试）的相对效率的指示。此外，我们运行了一个ESTTimes模型检查器目前不支持SRP协议，但即使是这种大小的没有共享资源的零星任务集也会被拒绝。110R. Nilsson等理论计算机科学电子笔记164（2006）97表4动态实时系统实验突变类型ΔμREK一G执行时间22400129.2（2.2）六十二（二三七二）解锁时间216000--到达间隔时间6240083.8（1.2）90（4150）O型凝固时间622000--总-86002013.0-遗传算法实验只使用一般的交叉功能，在第4.1节中描述，以获得我们的启发式交叉算子的附加性能的指示。由于每个算子都为这个系统模型生成了更多的突变体，我们决定使用一个突变算子类型的子集（基于杀死一个突变模型所需的平均表3使用与表2相同的列表示法，但是添加了列以包括来自随机测试（The“Δ” column containthe delta如表4所示，对于该特定系统，未发现恶性解锁时间或解锁时间突变体。在这个系统特定化模型中，杀死一个突变体所需的平均代数更高，这可能是因为搜索问题比4.1节中提出的更静态的系统更困难。在每次试验中，平均杀死的突变体数量很少，这表明存在较少的执行命令，可以揭示恶性突变体的缺陷。 对此的一个可能的解释是，遗传算法在没有来自启发式算子的迭代细化的情况下难以找到可比较的候选者因此，它会陷入局部最优，并过早地丢弃部分细化的候选项。解决这个问题的一个可能的方法是使用一个新的初始种群重复搜索多次。这可能是可接受的，因为用于搜索突变体模型的方法是完全自动化的。与随机测试和非启发式遗传算法的比较表明，启发式交叉函数是至关重要的方法的性能。5相关工作本节描述测试实时系统的现有方法。表5列出了相关工作的作者，并将贡献分为三类。当同一作者有多篇相关出版物阐述同一试验方法的不同方面时，仅包括一篇第一类（标记为“T”的列）列出了这些方法是否使用包括时间限制或地址测试系统级及时性的模型。标记为“I”的列在R. Nilsson等理论计算机科学电子笔记164（2006）97111表5.有关工作#作者不我C1Braberman等人[6]美国yyy2Cheung等人[八]《中国日报》n3克拉克和李[9]ny4[25]第二十五话5Mandrioli等人[17个]6[16]第十六话7卡德尔-奥利弗和格洛弗[7]8En-Nouaary等人[10个国家]n9尼尔森和斯科[20]10Raymond等[29日]11Watkins等人[35]第三十五届12[19]第十九话nyy13彼得森和塞恩[27]n14Wegener等人[36个]nn与我们的方法相比，很少有其他基于正式符号的方法在它们的模型中包括这一点，可能是为了避免状态空间爆炸。然而，如果内部行为未被建模，则通常不可能预测使用常规实时操作系统和任务模型实现的系统的最坏情况激活模式。例如，完全相同的激活模式可能会根据任务的执行时间给出完全不同的行为。表示为“C”的列列出了相关工作是否提出了可与其方法一起使用的测试标准。我们提出的测试标准与变异算子类型相关（见第3节）。其他方法提出了基于模型结构覆盖率的测试标准，例如自动机中的转换序列或位置。Braberman等人的方法。[6]是最接近的相关工作;他们从定时Petri网设计模型生成测试用例。类似于我们的方法，一个高层次的符号，SA/SD-RT，用于指定的并发实时系统的行为。与我们的方法相反，没有生成突变模型，而是将它们的设计规范转换为定时Petri网符号，从中可以导出和覆盖可达性树。由于该模型与我们的模型具有相似的详细程度，我们怀疑覆盖可达性树所需的测试数量随着系统的大小而快速增加。Cheung et al. [8]介绍了112R. Nilsson等理论计算机科学电子笔记164（2006）97一个测试多媒体软件的框架，包括任务之间的时间关系与我们的方法相反，生成的测试用例旨在测试多媒体应用程序及其特定属性。有几种基于不同形式模型的时间性测试方法。如上所述，这些方法通常不对被测系统的实时任务和协议进行建模。此外，这些方法都没有使用基于突变的测试技术（参见表5，第3 - 11行）。例如，Clarke和Lee [9]提出了一个测试实时系统激活模式时间约束的框架。时间约束在约束图中指定，被测系统使用进程代数指定。 与我们的方法相反，只考虑了对被测系统输入的约束，作者提到，测试对输出的约束是非常困难的，因为它取决于不确定的内部因素。Petitjean和Fochal [25]提出了一种方法，其中使用时钟区域图表示时间约束。 然后，系统的定时自动化规范被“附加”到传统的输入输出自动化，该输入输出自动化用于在每个时钟区域中导出实现的一致性测试。提出了一种在进行基于模型的一致性测试时如何处理目标系统时钟的方法。Krichen和Tripakis [16]解决了以前黑盒方法适用性的局限性，并提出了一种使用非确定性和部分可观察模型进行一致性测试的方法。所提出的测试标准受到Hes-sel等人[13]的启发，但扩展了测试用例规范，允许与实现进行几种可能的交互。Mandrioli等人[17]提出了一种基于时序逻辑中的系统行为规范来测试实时系统的方法。测试用例的元素是定时输入输出对。这些对可以被组合并及时转移以创建大量的部分测试用例，这样的对的数量随着软件的大小和约束而快速增长。在最近的一篇论文[30]中，作者扩展了他们以前的结果，将高层次的结构化规范用于处理更大规模的模块化软件。Cardell-Oliver和Glover [7]提出了一种从时间自动机模型生成测试的方法，以验证时间动作转换的序列。这种方法使用可达性分析来确定要测试的转换，因此，我们假设它将支持大型动态模型的状态空间爆炸。En-Nouaary等人提出了另一种基于自动机的方法。[10]。他们的方法利用了一种使用网格自动机和非确定性有限状态机作为中间表示的采样算法来减少测试误差。类似地，Nielsen和Skou [20]使用时间自动机的子类来指定实时应用程序。他们的方法的主要贡献是在规范中的时间约束上对时间行为进行粗略的等价划分。Raymond等人[29]提出了一种生成反应系统事件序列的方法。他们的方法将环境约束和测试要求作为外部观察者进行建模。与我们的方法和这一类别中的其他方法相比，Watkins等人。[35]不使用正式模型作为测试用例生成的基础相反，遗传R. Nilsson等理论计算机科学电子笔记164（2006）97113算法用于驱动包含时间约束的复杂系统的执行。数据在实际系统的执行过程中收集，并可视化以进行后期分析。测试用例的适合度是根据其唯一性以及在测试执行期间系统和测试工具生成的异常来计算的。类似地，使用这种方法，我们的遗传算法扩展可以直接用于目标系统，而不是模型。然而，缺点是，没有测试标准可以用来衡量进展，搜索问题进一步加剧了系统的内部不确定性。有一些相关的工作并没有解决系统级的时间性测试，但仍然与测试实时系统相关，或者作为我们方法的补充（见表5，第12 - 14行）。Morasca和Pezze [19]提出了一种测试并发和实时系统的方法，该方法使用高级Petri网进行规范和实现。这种方法没有显式地处理时间性，也没有提供测试标准，但据作者所知，它是第一个对被测实时系统的内部并发性建模的方法之一。Thane [33]提出了一种在实时系统投入运行之前获取其执行顺序的方法。有人建议，每个执行顺序可以被视为一个连续的程序，可以应用传统的测试方法测试执行后在最近的一篇论文中，Pettersson和Thane [27]通过支持共享资源扩展了该方法。与我们的方法相反，这种方法是为实时系统开发的Wegener等人已经探索了遗传算法用于测试实时任务的时间属性的能力[36]。然而，他们工作的主要重点是确定合适的输入，以产生最坏和最好的情况下执行时间。这种方法是一个有价值的补充，我们的方法，因为我们假设相关类的输入数据存在于每个实时任务的系统级测试的及时性开始之前。6结论提出了一种基于模型的启发式仿真生成测试用例的方法。一个基线的案例研究表明，该方法是有效的和可靠的生成测试用例的小型实时系统，包含共享资源，优先约束和零星的任务。该方法还评估了一个动态系统，更先进的实时协议和一个大部分的零星任务。对于这样的系统，没有当前的方法自动生成基于变异的测试用例是适用的。正如预期的那样，搜索问题对于更动态的系统越来越困难。然而，使用我们的启发式交叉函数的遗传算法显示出比随机搜索和仅使用通用交叉函数的遗传算法更好的性能。这种方法增加了基于突变的实时性测试的有用性，从而可以测试更真实大小和类型在实时目标上执行时生成的测试用例的有效性114R. Nilsson等理论计算机科学电子笔记164（2006）97系统目前正在调查中。我们的基因组映射功能应推广到支持一个更大的类TAT自动机模板在未来的工作。引用[1] 巴 尔 河 和 D.Dill ， A theory of timed automata ， Theoretical Computer Science126 （ 1994 ） ，pp.183- 235[2] Ammann，P.，P. Black和W.马约斯基使用模型检查从规范生成测试，在：第二届IEEE正式工程方法国际会议论文集，IEEE计算机协会，1998年，第110页。46比54[3] Amnell ， T. ， E. 费 斯 曼 湖 Mokrushin ， P. Pettersson 和 W. Yi ， Times - A tool for modeling andimplementation of embedded systems，in：Proceedings of TACAS460-464[4] Baker，T. P.，基于堆栈的实时进程，实时系统杂志（1991年），pp。67比99[5] Bengtsson，J.，K. G. Larsen，F. Larsson，P. Pettersson和W. Yi，UPPAAL-实时系统自动验证232-243。[6] Br aberm an，V.，M. FelderandM. M arr′e，测试测试，由一个实时软件组成，在：在软件质量周，1997年。[7] 卡德尔-奥利弗河和T. Glover，A practical and complete algorithm for testing real time systems，Lecture Notes in Computer Science1486（1998），pp. 251-261。[8] 张， S. C.的方 法， S. T. Chanson 和Z. Xu ， Toward generic timing tests for distributed multimediasoftware systems，in：ISSRE210.[9] Clarke，D.和I.李，从需求自动产生时间限制测试，在：第三届面向对象实时依赖系统国际研讨会论文集，纽波特比奇，加利福尼亚州，1997年。[10] En-Nouaary 河 ， K. F. Dssouli 和 A. Elqori ， 基 于 状 态 表