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的功能。