4． efg_edges_added =
{(Edit,Edit),(Edit,Cut),(Edit,Copy),(Edit,Paste),(Cut,Edit),(Copy,Edit),(Paste,Eidt)}
表1 原始GUI的4个事件序列
表1 显示4个事件序列用来测试原始GUI。列1是测试用例号，列2是测试用例的事件序列，列3是在G-CFG图中用于测试用例的事件，列4是G-CFG图中的边。通过测试以下测试用例可以得到以下结果：
1． 由于Print在GUI的结构中被删除了，因此事件1对于修改后的GUI是非法的。
2． 因为（Cut，Paste）和（Copy，Cut）在GUI的结构被删除了，事件序列3和4 对于修改后的GUI是非法的。
3． 事件序列2仍然是合法的，因为Cut在修改后的GUI中仍然是可用的。（只要初始的状态下Edit已经被执行了）
查看原始和修改后的GUI结构，我们知道，事件3和4是可以被修复的以获得合法的事件序列。对于事件3的修改可以是<Cut; Edit; Paste>；对于事件序列4的修改是<Copy; Edit; Cut; Edit; Paste>。这两个修改后的序列就是合法的了，并且可以用于修改后的GUI。而对于事件1的修改就不明显了，因为它包含了在修改后的GUI中不存在的事件Print。在这个例子中，这个事件序列将作为不可修复的测试用例被丢弃。本例说明了一些不可用测试用例是不可以被修复的。在修复工作之后，测试设计人员还要从剩下的3个事件序列中进行选择，然后使用它们进行回归测试。需要注意的是，时间2原本就是可以在修改后的GUI上使用的，因此当在事件序列中没有任何改变时，测试设计人员可以选择不重新运行该事件序列（除非在暗藏的代码中进行了改动）。在本例中，剩下的事件序列3和4加上其他新的测试用例，将被用于回归测试。
对于GUI来说，因为某些改变会造成测试用例不可用，因此在测试用例被修复前，可能要经过很多次的修改工作。我们的技术就是通过多种方式修复测试用例。
也许你会注意到，仅仅在G-CFG中添加新的事件或是关系而不删除任何的事件或关系，将不会导致事件序列非法。从原始测试集合中得到的事件序列或是没有使用任何新的事件，或是没有覆盖任何新的关系。如果关系和事件都没有被删除，则原有的测试用例仍然可以在修改后的GUI上使用。
5 回归测试
我们的回归测试技术包含2个方面：测试机将测试用例进行分类，是可用的还是不可用的；如果是不可用的，还要判断该测试用例是否可被修复。第二部分是修复机，修复可以被修复的测试用例。为了说明清楚，我们将这两部分分开进行了介绍，但在实际的应用中可以将这两部分合二为一的。
回归测试员要将原始GUI和修改后的GUI的G-CFG图和G-call图作为输入，以及修改后的GUI的测试状态SI，还有原始GUI的测试用例。测试机将原始测试用例分割为可用测试用例和不可用测试用例。关键的在于，它还将判断不可用的测试用例是否可以被修复。很显然的是，如果一个测试用例的初始状态在修改后的GUI中仍然是可用的，并且它的事件序列可以被修改为合法序列，则该测试用例就是可修复的。为了使GUI事件序列合法，我们从编译技术中借用了错误发现技术；忽略事件或是将一个新事件插入其中直到生成一个合法的事件序列。这个序列只能通过忽略事件或是包含修改后的GUI事件得到。最终，我们将一个可修复的测试用例定义为：
定义：如果一个不可用测试用例的初始状态是存在的，并且它的事件序列可以被修复为合法的，例如(ei,ek>i∈E)或者{(ei,ex),(ex,ek>i)∈E}其中1<=i<=n，则该测试用例是可以被修复的。
图4 新的回归测试方法
对于不可用测试用例，一部分将被修复并用于回归测试，而那些不可修复的测试用例将被丢弃。图4表示了这个新的回归测试方法。需要注意的是，用于测试GUI新增加部分的测试用例是不可能通过修复原有的测试用例得到的，但这部分测试用例也是回归测试集合必不可少的一部分。
回归测试包含以下几个组成部分：
- 测试机：将原始的测试用例分为（1）可用测试用例，（2）可修复的不可用测试用例，和（3）不可修复的不可用测试用例。
- 修复机：通过增加和删除测试用例中的事件来修复不可用测试用例，使这些测试用例符合修改后的GUI的事件序列。
图5 回归测试的组成部分和它们之间的关系
图5显示了回归测试中的测试机和修复机以及它们之间的联系。该图还说明了这些组成部分之间的关系。Test Case Generator和Coverage Evaluator生成新的测试用例用于测试GUI新的部分。这样，修复的、新的和原本可用的测试用例共同组成了回归测试用例集合。下面我们将介绍测试机和修复机设计的具体细节。
5.1 测试机
测试机的首要功能是标识不可用测试用例以及其中哪些是可以被修复的。测试机首先通过遍历G-CFG图决定了在测试用例中的事件序列是否可重用。
为了使我们的分析有效，我们通过一系列合理的假设简化分析。我们假设这些事件和成员：（1）有独一无二的名字（重新命名可以用于完成这个建设）和（2）除非被修改，否则在不同的GUI版本间名字是不改变的。例如，如果事件File没有被修改，则它在修改后的GUI中的名字仍然为File。如果一些事件和成员被重新命名了，则GUI设计者必须要把这些改变记录到日志中，这样测试设计者就会了解到这些改变。
通过这些假设，我们可以简单地添加或删除G-CFG图和G-call树来自动对GUI的改变标识并进行分类。简单地通过在控制流图上查找增加或删除已经用于自增数据流和代码最优化以及增加测试。
G-CFG图中所代表的成员事件，可以通过增加或删除一个点或边而改变。假设GCFG0和GCFGm分别代表了出现在原始GUI和改变后的GUI的一个成员，则通过集合相减就可以判断出是否有改变。在这里，函数Vertices和Edges分别返回的是集合V（点集）和集合E（边集）。
1．G-CFG图中所有增加的点的集合：
vertices_added?Vertices(GCFGm)-Vertices(GCFG0);
2. 从原始G-CFG中删除的所有点的集合：
vertices_deleted?Vertices(GCFG0)-Vertices(GCFGm);
3. 所有新添加的边的集合：
efg_edges_added?Edges(GCFGm)-Edges(GCFG0);
4. 从原始G-CFG中删除的边的集合：
efg_edges_deleted?Edges(GCFG0)-Edges(GCFGm);
像第4部分描述的那样，以上的集合用于标识不可用的测试用例。
类似地，一棵调用树也可以通过增加或删除一个成员或边而改变。假设G0和Gm分别代表原始GUI和修改后的GUI的调用树。两者之间的改变可以通过以下集合的改变得到。在这里，Nodes和CompEdges函数分别返回的是调用树的N和B集合。
1．添加到G-call图的成员集合：
components_added?Nodes(Gm)-Nodes(G0);
2. 从G-call图中删除成员的集合：
components_deleted?Nodes(G0)-Nodes(Gm);
3. 添加到G-call图中的边：
comp_edges_added?CompEdges(Gm)-CompEdges(G0);
4. 从G-call图中删除的边的集合：
comp_edges_deleted?CompEdges(G0)-CompEdges(Gm);
需要注意的是G-CFG图的边和G-call图的边之间的区别。一个G-CFG图的边都是有序对如(ex,ey),其中ex和ey是事件，而G-call图的边是有序对如(Cx，Cy)，其中Cx和Cy是成员。G-call图中的一条边(Cx，Cy)代表了所有边(ey, ex)的集合，ey是成员Cx中激活Cy的事件。
修改集包括以上用于标识不可用测试集合。特别以下2个集合：
1. vertices_deleted
2. edges_deleted?efg_edges_deleted∪EventEdges(comp_edges_deleted)，其中EventEdges是函数，输入是G-call边的集合，返回的是相应边的事件形式。
为了标识不可用测试用例，我们一共使用了至少2种不同的技术。首先，称作图匹配技术，输入一个事件序列< e1;e2;…;en>，判断(ei, ei+1)对于修改后的G-CFG图在1<i<n-1是否是有效的边。这项技术对于小型的测试运行简单，表现出很好的运行效率。另一个可选的技术，是在第6章中说明的，对于大型的测试要比图匹配更加有效率。该技术是在2个字节向量EDGES-MODIFIED和EVENTS-MODIFIED中记录GUI的改变。每个测试用例都与2个字节向量EVENTS-USED和EDGES-USED相关联。因此测试用例是可用/不可用可以通过非常方便的AND（与）运算得到。通过运用这个信息，检测机标识那些因为改变而变得不可用的测试用例。例如，如果一个事件e从GUI中删除，则所有使用事件e的测试用例都是不可用的。一个GUI的改变可能会造成多个集合的改变，因为同一个改变，一个测试用例可能被多次标识为不可用测试用例。以后章节中我们还将说明，多次标识对于测试用例的修复并没有影响。
一旦不可用测试用例被标识了，他们将被修复机修复，这将在下面描述。
5.2 修复机
修复机修复（算法将在图6中描述）非法的事件序列，使它们可以在修改后的GUI上执行。一个非法事件序列或是使用一个删除的事件或是一个删除的边。如果在事件序列的第i位置的事件ei被删除，则事件序列修复机会ei从事件序列中删除。然后，为了得到一个合法的事件序列，事件序列修复机将从左向右浏览事件序列，从第i+1位置开始，直到找到一个事件ej符合以下任何一个情况：(1)< ei-1;ej>对于修改后的GUI是合法的事件序列，(2)从修改后的GUI的所有事件中的任何一个事件ex，使得< ei-1; ex;ej>对于修改后的GUI是合法事件序列。
修复一个事件序列可能存在着很多种方式。当找到多种途径时，所有的这些修复都将用于生成更多的测试用例。
一旦事件ej找到了，则子串< ei;…;ej-1>将从事件序列中被删除，在第二种情况下，插入事件ex。图7(a)说明了这两种情况。在第一种情况下，修复机从ei+1到en中查找ej；在第二种情况下，从修改后的GUI的所有事件中查找事件ex, ex在e j-1执行之后而ej在ex执行之后。
通常情况下，这个方法被扩展到寻找一系列事件串< ep;…;eq>使得< ei-1; ep;…;eq;ej>在修改后的GUI上是合法的事件序列。然而，计算这样一个字符串的过程是很费时的，并且通过这样的方式生成的测试用例会与原始的测试用例非常不同。我们的目标是要生成与原始的测试用例相近的，在必要的情况下需要重新测试GUI的功能。
文章来源于领测软件测试网 https://www.ltesting.net/
