一种并发程序的缺陷模式发现方法

摘要

本发明属于软件故障诊断领域，提供一种自主发现并发程序缺陷模式的方法，尤其是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法，本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘，自主发现程序缺陷模式。

权利要求

1.一种并发程序的缺陷模式发现方法，其特征在于该方法包括以下步骤：(1)监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获取状态信息；

(2)使用动态标记迁移算法DLT对设置监控点的目标程序的执行进行调度，获取目标程序的监控点的状态信息；所述的动态标记迁移算法DLT(S,T,t,SeS)的算法输入参数有：全局状态栈S，全局迁移序列集T，局部迁移t和初始的全局序列集SeS；算法输出参数有：全局序列集SeS；其步骤如下：(2-1)将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量σ中；

(2-2)更新s的回溯信息；

(2-3)如果存在线程p和s状态下可行迁移集合s.enabled中线程p的一个迁移元素t，执行以下步骤：(2-3-1)将线程p赋值给状态s的回溯集s.backtrack；

(2-3-2)创建状态s下已经执行过的迁移集合s.done，并将其置为空；

(2-3-3)如果存在某一线程q是状态s的回溯集s.backtrack与状态s下已经执行过的迁移集合s.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止：(2-3-3-1)将q加入状态s下已经执行过的迁移集合s.done中；

(2-3-3-2)从状态s的回溯集s.backtrack中删除线程q；

(2-3-3-3)设p’是执行迁移tm的线程，若线程p’属于s.done，且tm属于s.enabled，则将tm加入集合s.retrieved中；

(2-3-3-4)将s状态下可行迁移集合s.enabled中线程q执行的迁移设置为tn；

(2-3-3-5)创建项集is并初始化为空，并将tn添加到is中；

(2-3-3-6)将项集is添加到序列变量σ中；

(2-3-3-7)判断从状态s出发且执行tn迁移后到达的状态是否为空值，若不是，则执行以下步骤，否则不执行：(2-3-3-7-1)将从状态s出发且执行tn迁移后得到的状态设为s'；

(2-3-3-7-2)将独立于迁移t且属于s.enabled中的迁移t'存入s'.retrieved集合中；

(2-3-3-7-3)将s'.enabled与s'.retrieved集合的差集存入s'.enabled中；

(2-3-3-7-4)将迁移tn添加入迁移序列T中；

(2-3-3-7-5)将状态s'压入状态栈S中；

(2-3-3-7-6)递归调用DLT(S,T,t,SeS)算法；

(2-3-3-7-7)将T中的最后一项序列移出；

(2-3-3-8)将S中的一项状态出栈；

(2-4)返回全局序列集SeS；

(3)把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集；

(4)在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘，得到目标程序缺陷模式；所述的序列模式挖掘算法ISPAM的步骤如下：(4-1)将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup为0；

(4-2)将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V(GS)和V(BS)，生成V(BS)中项集列表Sinit；

(4-3)对于项集列表Sinit中的每一个项items，完成以下步骤：(4-3-1)计算其是否是频繁项，如果是：

(4-3-1-1)调用SAVE()方法对由单个项组成的模式存储到L中；

(4-3-1-2)在R集合添加项items，Sinit，Sinit中在items之后的项的集合组成的三元组；

(4-4)如果存在元组＜r，S1，S2＞属于R集合并且r的支持度大于等于minsup，则重复做以下步骤，直到不满足这一条件为止：(4-4-1)选择R集合中拥有最高支持度的模式r的元组＜r，S1，S2＞；

(4-4-2)通过调用SEARCH()方法对候选模式集合R进行拓展，更新候选模式集合R，并将拓展得到的模式调用SAVE()方法存储到L中；

(4-4-3)将元组＜r，S1，S2＞从R中移除；

(4-4-4)将R中的所有满足＜r，S1，S2＞∈R|sup(r)条件的元组从R中移除；

(4-5)返回含有前k个缺陷模式的集合L。

2.根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤(1)中所述的获取状态信息的步骤如下：步骤一，基于面向方面编程思想和待监控的源程序，在待监控的并发程序中针对共享变量的读写操作定义监控点，接着在监控点处添加若干个切点；

步骤二，定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行，通知内的transform()方法将用于存放包含源程序中被监控方法的参数表数组args中的行号、序列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现场信息，并存入在事件类EventPO中。

说明书

一种并发程序的缺陷模式发现方法

技术领域

[0001] 本发明属于软件故障诊断领域，是一种自主发现并发程序缺陷模式的方法，尤其是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法。

背景技术

[0002] 发现并发程序缺陷是一件困难的事情，一般都只能根据日志信息判断故障原因，而普通的监控系统只对软件行为进行检测而无法进一步判断软件的执行是否处于正确的
轨迹（正确的行为）之上。

[0003] 基于面向方面编程的监控程序可将监测逻辑和业务逻辑相互分离，能方便获取到一个并行程序系统的执行轨迹。针对这些获取到的并发程序系统的执行轨迹，可利用序列
模式挖掘技术对这些轨迹进行挖掘，这样能有效解决并发程序故障诊断困难的问题，并能
从并发程序执行轨迹这一海量数据中提取有用信息,以获取到隐含在历史并发程序轨迹序
列集上的故障特征关键点。这种技术将可有效地保障并发软件系统的安全性。

[0004] 现有技术的典型实现方案如下：

[0005] 第一，基于专家系统的故障/缺陷诊断程序。其主要原理是将领域专家的知识与经验被表示成产生式规则,并在知识库和数据库的支持下,综合运用各种规则进行一系列的
推理。该诊断程序在运行中要求用户输入必要的信息后,就可快速地直接找到最终故障/缺
陷或是最有可能的故障/缺陷,并由用户对结果进行进一步判断。但这种方法需要建立规则
库，并利用规则库对程序轨迹状态进行判断和预测，这种方法的主要缺点是自动化程度不
高，方法的复用性较差。

[0006] 第二，方便和有效的获取程序执行轨迹是进行软件故障/缺陷诊断的前提。在程序执行轨迹获取方面，美国加利福尼亚大学伯克利分校和贝儿实验室共同提出了动态偏序化
简算法（Dynamic Partial Order Reduction，DPOR），探索线程的交互执行情况，并提出了
Persistent集合的概念，以保证线程执行情况搜索的完备性。该算法从程序的初始状态执
行的迁移序列开始采用深度优先搜索程序状态栈，动态探索线程间交互信息，然后利用这
些信息去鉴定回溯点，从而探索状态空间的可选路径，获取程序执行轨迹。

[0007] 在程序状态的搜索过程中计算各个状态的Persistent集合，使得程序里所有迁移序列都不是空序列，在某一状态下可行的迁移集合里所有迁移和其他迁移序列中的迁移都
是独立的，保证搜索的完备性。

[0008] 但该算法的主要缺点是没有将完整地程序轨迹序列获取并存储；没有为程序轨迹序列的进一步分析提供基础；没有针对含有循环的并发程序进行优化，会出现对已经搜索
过的迁移反复搜索的情况，这会造成了DPOR算法效率的低下，这反映在采用该算法的总探
索时间和单次平均探索时间都较长。

[0009] 第三，在对缺陷模式的发现方法上，美国康奈尔大学提出序列模式挖掘算法(Sequential PAttern Mining,SPAM)进行序列模式挖掘，对序列集进行挖掘得到频繁模
式。SPAM算法首先将序列信息存储于数据库位图中，然后可在项集层面实行项集拓展，和可
在序列层面实行序列拓展，并使用格理论对数据库进行深度优先遍历从而找出序列模式。
SPAM算法的主要缺点是需要用户自己来设定最小支持度阈值，不当的支持度阈值可能带来
挖掘出的模式质量差的问题；只能对单一类型的序列集进行处理，误报情况严重。

发明内容

[0010] 本发明的目的在于针对以上不足，在传统基于动态偏序化简算法获取并发程序执行轨迹和SPAM算法进行序列模式挖掘的基础上，针对算法的核心步骤，即获取并发程序轨
迹和对轨迹进行挖掘以发现缺陷模式，提出涉及这两步的改进的做法，能自主发现程序缺
陷模式。

[0011] 本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘得到缺陷模
式。

[0012] 本发明提供一种并发程序的缺陷模式发现方法，包括以下步骤：

[0013] （1）监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获取状态信息；

[0014] （2）使用动态标记迁移算法DLT对设置监控点的目标程序的执行进行调度，获取目标程序的监控点的状态信息；

[0015] （3）把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集；

[0016] （4）在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘，得到目标程序缺陷模式。

[0017] 在上述技术方案中，步骤（1）中所述的获取状态信息的步骤如下：

[0018] 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点；

[0019] 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执
行，通知内的transform()方法将用于存放包含源程序中被监控方法的参数表数组args中
的行号、序列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现
场信息，并存入在事件类EventPO中。

[0020] 在上述技术方案中，步骤（2）中所述的动态标记迁移算法DLT(S, T, t,SeS)的算法输入参数有：全局状态栈S，全局迁移序列集T，局部迁移t和初始的全局序列集SeS；算法
输出参数有：全局序列集SeS；其步骤如下：

[0021] 步骤一，将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量σ中；

[0022] 步骤二，更新s的回溯信息；

[0023] 步骤三，如果存在线程p和s状态下可行迁移集合s.enabled中线程p的一个迁移元素t，执行以下步骤：

[0024] （3.1）将线程p赋值给状态s的回溯集s.backtrack；

[0025] （3.2）创建状态s下已经执行过的迁移集合s.done，并将其置为空；

[0026] （3.3）如果存在某一线程q是状态s的回溯集s.backtrack与状态s下已经执行过的迁移集合s.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止：

[0027] （3.3.1）将q加入状态s下已经执行过的迁移集合s.done中；

[0028] （3.3.2）从状态s的回溯集s.backtrack中删除线程q；

[0029] （3.3.3）设p’是执行迁移tm的线程，若线程p’属于s.done，且tm属于s.enabled，则将tm加入集合s.retrieved中；

[0030] （3.3.4）将s状态下可行迁移集合s.enabled中线程q执行的迁移设置为tn；

[0031] （3.3.5）创建项集is并初始化为空，并将tn添加到is中；

[0032] （3.3.6）将项集is添加到序列变量σ中；

[0033] （3.3.7）判断从状态s出发且执行tn迁移后到达的状态是否为空值，若不是，则执行以下步骤，否则不执行：

[0034] （3.3.7.1）将从状态s出发且执行tn迁移后得到的状态设为s'；

[0035] （3.3.7.2）将独立于迁移t且属于s.enabled中的迁移t'存入s'.retrieved集合中；

[0036] （3.3.7.3）将s'.enabled与s'.retrieved集合的差集存入s'.enabled中；

[0037] （3.3.7.4）将迁移tn添加入迁移序列T中；

[0038] （3.3.7.5）将状态s'压入状态栈S中；

[0039] （3.3.7.6）递归调用DLT(S, T, t,SeS)算法;

[0040] （3.3.7.7）将T中的最后一项序列移出；

[0041] （3.3.8）将S中的一项状态出栈；

[0042] 步骤四，返回全局序列集SeS。

[0043] 在上述技术方案中，步骤（4）中序列模式挖掘算法ISPAM的步骤如下：

[0044] 步骤一，将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup为0；

[0045] 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V(GS)和V(BS)，生成V(BS)中项集列表Sinit；

[0046] 步骤三，对于项集列表Sinit中的每一个项items，完成以下步骤：

[0047] （3.1）计算其是否是频繁项，如果是：

[0048] （3.1.1）调用SAVE()方法对由单个项组成的模式存储到L中；

[0049] （3.1.2）在R集合添加项items，Sinit，Sinit中在items之后的项的集合组成的三元组；

[0050] 步骤四，如果存在元组  属于R集合并且r的支持度大于等于minsup，则重复做以下步骤，直到不满足这一条件为止：

[0051] （4.1）选择R集合中拥有最高支持度的模式r的元组 ；

[0052] （4.2）通过调用SEARCH()方法对候选模式集合R进行拓展，更新候选模式集合R，并将拓展得到的模式调用SAVE()方法存储到L中；

[0053] （4.3）将元组 从R中移除；

[0054] （4.4）将R中的所有满足 条件的元组从R中移除；

[0055] 步骤五，返回含有前k个缺陷模式的集合L。

[0056] 本发明方法与现有技术相比具有以下优点：

[0057] 1.对目标源程序进行插装并监控，对目标程序的监控进行设置，针对DPOR算法对循环较多的程序，执行效率较低的缺点，排除了对相互独立迁移的选取，并将已经检索过的
迁移加入一个专门的集合，避免反复搜索已经执行过的迁移，从而实现了对包含循环较多
程序的化简，提高了执行效率，在选择性搜索过程中，记录轨迹序列，将轨迹序列存入序列
集合中，得到全部的程序轨迹序列。

[0058] 2.针对SPAM算法中用户设置最小支持度带来的模式质量过差和数量过多的问题，引入项数k来规定对最佳模式数量的挖掘，转化为前k项序列模式挖掘，得到前k项效果最佳
的缺陷解释模式。基于此，为了达到减少搜索空间，提高算法的效率，同时能够解决缺陷误
报问题的目的，定义了成功执行序列集、失效执行序列集、相对支持度概念，所谓成功执行
序列集指的是并发程序的执行结果符合程序的预期行为的执行序列集；所谓失效执行序列
集指的是并发程序的执行结果不符合程序的预期行为的执行序列集；所谓相对支持度指的
频繁出现在失效执行序列集而较少出现在成功执行序列集的一种相对度。在此基础上，本
发明提出了在挖掘过程中通过对成功执行序列集和失效执行序列集中同一模式的比较来
计算其相对支持度，减少对频繁出现在成功执行序列集中的模式选取，从而降低缺陷误报
率的方法。

附图说明

[0059] 图1为本发明方法的流程图。

具体实施方式

[0060] 本实施使用装有Windows 7操作系统的PC机作为平台，通过MyEclipse开发并发程序缺陷检测程序。本发明实施时，用户必须安装1.7版本以上的JDK，以获取Java提供的新特
性。

[0061] 此外，需定义如下术语：

[0062] （1）监控现场：指监控的目标程序运行时的状态信息。

[0063] （2）通知：指程序执行中明确定义的点（接入点）被程序运行所触发时应该执行的代码。

[0064] （3）并发程序的状态：指由所有共享变量的全局状态和每个线程的局部状态所组成的状态。

[0065] （4）并发程序的迁移：指为将程序从一个状态转移到下一个状态，某个线程执行的一个可见操作。

[0066] （5）垂直成功执行序列集：指用位图表示的垂直格式的成功执行序列集。

[0067] （6）垂直失效执行序列集：指用位图表示的垂直格式的失效执行序列集。

[0068] 本发明实施例涉及如下文献：

[0069] [1] Flanagan C, Godefroid P. Dynamic Partial-Order Reduction for Model Checking Software POPL＇2005[M]. New York: ACM press, 2005。

[0070] [2] Ayres, J., Flannick, J., Gehrke, J., Yiu, T.. Sequential PAttern mining using a bitmap representation, Proc. 8th ACM SIGKDD Int. Conf. on 
Knowledge Discovery and Data Mining (KDD 2002), July 23-26, 2002, Edmonton, 
Alberta, pp. 429-435 (2002)。

[0071] 以下以在PC机上采用Java语言在JDK开发环境下开发并发程序缺陷检测程序为例说明本发明技术方案。

[0072] （一）设置监控目标程序。

[0073] 为了获取并发程序执行的状态信息，首先需要对被监控的目标程序进行设置。具体做法是：基于面向方面编程思想，在需监控的目标程序中定义监控点、切点（pointcut）、
通知（advice），使用探针注入方式对监控点进行监控以获取状态信息。

[0074] 获取状态信息过程中涉及到的相关变量定义，具体如表1所示。

[0075] 表1获取状态信息过程中的符号 符号名 符号类型 含义
meg 字符串 存放参数表数组args中的行号、序列号信息的临时变量
transform() 方法 将执行环境中的线程标识符和meg信息转换成监控现场信息的方法
EventPO 类 存储监控现场信息的类

[0076] 获取状态信息的步骤如下：

[0077] 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点；

[0078] 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执
行，通知内的transform()方法将临时变量meg中的内容以及执行环境中的线程标识符转
换成监控现场信息，并存入在事件类EventPO中。

[0079] （二）使用动态标记迁移算法DLT对设置监控点的目标程序的执行进行调度。

[0080] 使用本发明提出的动态标记迁移算法DLT，对待监控的并发程序中的线程执行进行调度。

[0081] 本算法要用到的相关符号定义如表2所示。

[0082] 表2.动态标记迁移算法DLT中的符号 符号名 符号类型 含义
update_backtrack_info 文献[1]中定义的方法 更新回溯信息的方法
s 程序状态 共享变量的全局状态和每个线程的局部状态组成的状态
SeS 集合 由所有序列构成的集合
enabled 集合 某一状态下可行迁移集合，其集合元素是可行的迁移
p 线程 s.enabled中的某一线程
t 迁移 使得状态发生转移的一个可见操作
σ 序列 SeS中的当前序列
tm 迁移 该迁移属于s状态下可行迁移集合s.enabled中的迁移，且执行该迁移的线程是状态s下已经执行过的迁移集合s.done中的线程tn 迁移 该迁移属于s状态下可行迁移集合s.enabled中线程q执行的迁移
retrieved 集合 存放某一状态下能够执行却无执行必要的全部迁移的集合
q 线程 某一线程
backtrack 集合 某一状态下的回溯集，其集合元素是可执行但尚未执行的线程
done 集合 某一状态下已经执行过的迁移集合
next(s,t) 方法 从状态s出发且执行t迁移
s' 程序状态 从状态s出发且执行tn迁移后得到的状态
T 集合 由所有迁移构成的集合
S 栈 由所有状态构成的栈
p’ 集合 执行迁移tm的线程
is 项集 添加到序列变量σ中的项集
t' 迁移 该迁移属于s.enabled，独立于迁移t

[0083] 所述动态标记迁移算法DLT(S, T, t,SeS)的步骤如下：

[0084] 算法输入参数有：全局状态栈S，全局迁移序列集T，局部迁移t和初始的全局序列集SeS。算法输出参数有：全局序列集SeS。

[0085] （1）将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量σ中；

[0086] （2）更新s的回溯信息；

[0087] （3）如果存在线程p和s状态下可行迁移集合s.enabled中线程p的一个迁移元素t，执行以下步骤：

[0088] （3.1）将线程p赋值给状态s的回溯集s.backtrack；

[0089] （3.2）创建状态s下已经执行过的迁移集合s.done，并将其置为空；

[0090] （3.3）如果存在某一线程q是状态s的回溯集s.backtrack与状态s下已经执行过的迁移集合s.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止：

[0091] （3.3.1）将q加入状态s下已经执行过的迁移集合s.done中；

[0092] （3.3.2）从状态s的回溯集s.backtrack中删除线程q；

[0093] （3.3.3）设p’是执行迁移tm的线程，若线程p’属于s.done，且tm属于s.enabled，则将tm加入集合s.retrieved中；

[0094] （3.3.4）将s状态下可行迁移集合s.enabled中线程q执行的迁移设置为tn；

[0095] （3.3.5）创建项集is并初始化为空，并将tn添加到is中；

[0096] （3.3.6）将项集is添加到序列变量σ中；

[0097] （3.3.7）判断从状态s出发且执行tn迁移后到达的状态是否为空值，若不是，则执行以下步骤，否则不执行：

[0098] （3.3.7.1）将从状态s出发且执行tn迁移后得到的状态设为s'；

[0099] （3.3.7.2）将独立于迁移t且属于s.enabled中的迁移t'存入s'.retrieved集合中；

[0100] （3.3.7.3）将s'.enabled与s'.retrieved集合的差集存入s'.enabled中；

[0101] （3.3.7.4）将迁移tn添加入迁移序列T中；

[0102] （3.3.7.5）将状态s'压入状态栈S中；

[0103] （3.3.7.6）递归调用DLT(S, T, t,SeS)算法;

[0104] （3.3.7.7）将T中的最后一项序列移出；

[0105] （3.3.8）将S中的一项状态出栈；

[0106] （4）返回全局序列集SeS。

[0107] 其具体算法如下。

[0108]

[0109] （三）把监控到的状态信息，以轨迹序列的形式存储在数据库中。

[0110] 把监控获取到的状态信息，存储在事件类EventPO中，通过Dao方法将事件类EventPO中的信息以轨迹序列的形式存储在数据库SDB中。类EventPO记录每个监控点事件；
类SequencePO记录每次执行的序列信息，其中包括序列id、序列结果状态（status）。

[0111] 使用Hibernate进行对象关系映射ORM（Object Relationship Mapping，ORM）操作，和数据访问对象DAO（Data Access Object，DAO）操作Java中的持久化对象PO
（persistant object，PO），完成将EventPO和SequencePO中数据存储到数据库SDB。

[0112] 事件类EventPO的定义如下：

[0113] public class EventPO {

[0114]     private int primaryKey; //表示项的序号

[0115]     private int threadID; //表示线程的序号

[0116]     private String threadName;//表示线程名

[0117]     private int methodLine;//表示被监控方法所在行

[0118]     private String methodName;//表示被监控方法名

[0119]     private int shareMemoryIndex;//表示共享内存的序号

[0120]     private String shareMemoryValue;//表示共享内存的值

[0121]     private Date date;//表示操作日期

[0122]     private int millisecond;//表示操作时间

[0123]     private SequencePO sequence;//表示所属的序列号

[0124] }

[0125] 上述定义中：

[0126] primaryKey表示项的序号；

[0127] threadID表示线程的序号；

[0128] threadName表示线程名；

[0129] methodLine表示被监控方法所在行；

[0130] methodName表示被监控方法名；

[0131] shareMemoryIndex表示共享内存的序号；

[0132] shareMemoryValue表示共享内存的值；

[0133] date表示操作日期；

[0134] millisecond表示操作时间；

[0135] sequence表示所属的序列号。

[0136] （四）获取数据库中每条轨迹序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集。

[0137] 获取轨迹序列中的执行结果状态（status），依据预先定义的失效结果，判定并发程序中序列执行结果的状态是否丢失修改，或是否存在不可重复读、或是否读“脏”数据等
情况中的一种，如是则执行结果是失效的，对轨迹序列进行分类，得到成功执行序列集和失
效执行序列集。

[0138] （五）基于轨迹序列的并发程序缺陷模式挖掘。

[0139] 在成功执行序列集和失效执行序列集中，利用以下改进的序列模式挖掘算法ISPAM对存储在数据库的数据集进行挖掘，得到并发程序缺陷模式。

[0140] 序列模式挖掘算法ISPAM的相关变量含义如表3所示。

[0141] 表3 序列模式挖掘算法ISPAM中的符号 符号名 符号类型 含义
R 集合 候选模式集合
L 集合 前k个缺陷模式的集合
minsup 双精度变量 最小支持度
GS 集合 成功执行序列集
BS 集合 失效执行序列集
V(GS) 集合 垂直成功执行序列集
V(BS) 集合 垂直失效执行序列集
Sinit 列表 项集列表
SAVE() 方法 实现存储过程的方法
items 项 Sinit中的一个项
三元组 可拓展序列记录元组
SEARCH() 文献[2]中定义的方法 实现候选集生成过程的方法
r 模式 模式挖掘过程中的一个候选模式
k 整型变量 模式的个数
sup(r) 方法 计算r的支持度的方法
bv(items) 方法 计算items是否为频繁项的方法

[0142] 所述序列模式挖掘算法ISPAM的步骤如下：

[0143] （1）将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup为0；

[0144] （2） 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V(GS)和V(BS)，生成V(BS)中项集列表Sinit；

[0145] （3）对于项集列表Sinit中的每一个项items，完成以下步骤：

[0146] （3.1）计算其是否是频繁项，如果是：

[0147] （3.1.1）调用SAVE()方法对由单个项组成的模式存储到L中；

[0148] （3.1.2）在R集合添加项items，Sinit，Sinit中在items之后的项的集合组成的三元组；

[0149] （4）如果存在元组 属于R集合并且r的支持度大于等于minsup，则重复做以下步骤，直到不满足这一条件为止：

[0150] （4.1）选择R集合中拥有最高支持度的模式r的元组 ；

[0151] （4.2）通过调用SEARCH()方法对候选模式集合R进行拓展，更新候选模式集合R，并将拓展得到的模式调用SAVE()方法存储到L中；

[0152] （4.3）将元组 从R中移除；

[0153] （4.4）将R中的所有满足 条件的元组从R中移除；

[0154] （5）返回含有前k个缺陷模式的集合L。

[0155] 其具体算法如下。

[0156]