一种并发程序的缺陷模式发现方法
一种并发程序的缺陷模式发现方法
【技术领域】
[0001] 本发明属于软件故障诊断领域，是一种自主发现并发程序缺陷模式的方法，尤其 是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法。
【背景技术】
[0002] 发现并发程序缺陷是一件困难的事情，一般都只能根据日志信息判断故障原因， 而普通的监控系统只对软件行为进行检测而无法进一步判断软件的执行是否处于正确的 轨迹(正确的行为）之上。
[0003] 基于面向方面编程的监控程序可将监测逻辑和业务逻辑相互分离，能方便获取到 一个并行程序系统的执行轨迹。针对这些获取到的并发程序系统的执行轨迹，可利用序列 模式挖掘技术对这些轨迹进行挖掘，这样能有效解决并发程序故障诊断困难的问题，并能 从并发程序执行轨迹这一海量数据中提取有用信息，以获取到隐含在历史并发程序轨迹 序列集上的故障特征关键点。这种技术将可有效地保障并发软件系统的安全性。
[0004] 现有技术的典型实现方案如下： 第一，基于专家系统的故障/缺陷诊断程序。其主要原理是将领域专家的知识与经验 被表示成产生式规则，并在知识库和数据库的支持下，综合运用各种规则进行一系列的推 理。该诊断程序在运行中要求用户输入必要的信息后，就可快速地直接找到最终故障/缺 陷或是最有可能的故障/缺陷，并由用户对结果进行进一步判断。但这种方法需要建立规 则库，并利用规则库对程序轨迹状态进行判断和预测，这种方法的主要缺点是自动化程度 不高，方法的复用性较差。
[0005] 第二，方便和有效的获取程序执行轨迹是进行软件故障/缺陷诊断的前提。在程 序执行轨迹获取方面，美国加利福尼亚大学伯克利分校和贝儿实验室共同提出了动态偏序 化简算法（DynamicPartialOrderReduction，DP0R)，探索线程的交互执行情况，并提出 了Persistent集合的概念，以保证线程执行情况搜索的完备性。该算法从程序的初始状态 执行的迀移序列开始采用深度优先搜索程序状态栈，动态探索线程间交互信息，然后利用 这些信息去鉴定回溯点，从而探索状态空间的可选路径，获取程序执行轨迹。
[0006] 在程序状态的搜索过程中计算各个状态的Persistent集合，使得程序里所有迀 移序列都不是空序列，在某一状态下可行的迀移集合里所有迀移和其他迀移序列中的迀移 都是独立的，保证搜索的完备性。
[0007] 但该算法的主要缺点是没有将完整地程序轨迹序列获取并存储；没有为程序轨迹 序列的进一步分析提供基础；没有针对含有循环的并发程序进行优化，会出现对已经搜索 过的迀移反复搜索的情况，这会造成了DP0R算法效率的低下，这反映在采用该算法的总探 索时间和单次平均探索时间都较长。
[0008] 第三，在对缺陷模式的发现方法上，美国康奈尔大学提出序列模式挖掘算法 (SequentialPAtternMining,SPAM)进行序列模式挖掘，对序列集进行挖掘得到频繁模 式。SPAM算法首先将序列信息存储于数据库位图中，然后可在项集层面实行项集拓展，和可 在序列层面实行序列拓展，并使用格理论对数据库进行深度优先遍历从而找出序列模式。SPAM算法的主要缺点是需要用户自己来设定最小支持度阈值，不当的支持度阈值可能带来 挖掘出的模式质量差的问题；只能对单一类型的序列集进行处理，误报情况严重。
【发明内容】
[0009] 本发明的目的在于针对以上不足，在传统基于动态偏序化简算法获取并发程序执 行轨迹和SPAM算法进行序列模式挖掘的基础上，针对算法的核心步骤，即获取并发程序轨 迹和对轨迹进行挖掘以发现缺陷模式，提出涉及这两步的改进的做法，能自主发现程序缺 陷模式。
[0010] 本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执 行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘得到缺陷模 式。
[0011] 本发明提供一种并发程序的缺陷模式发现方法，包括以下步骤： (1) 监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获 取状态信息； (2) 使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度，获取目标 程序的监控点的状态信息； (3) 把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹 序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集； (4) 在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘， 得到目标程序缺陷模式。
[0012] 在上述技术方案中，步骤（1)中所述的获取状态信息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序 中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点； 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切 点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行， 通知内的transformO方法将用于存放包含源程序中被监控方法的参数表数组args中的 行号、序列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现场 信息，并存入在事件类EventPO中。
[0013] 在上述技术方案中，步骤（2)中所述的动态标记迀移算法DLT(S，T，t，SeS)的算 法输入参数有：全局状态栈S，全局迀移序列集T，局部迀移t和初始的全局序列集SeS;算 法输出参数有：全局序列集SeS;其步骤如下： 步骤一，将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量〇中； 步骤二，更新s的回溯信息； 步骤三，如果存在线程P和s状态下可行迀移集合s.enabled中线程p的一个迀移元 素t，执行以下步骤： (3. 1)将线程p赋值给状态s的回溯集s.backtrack; (3. 2)创建状态s下已经执行过的迀移集合s.done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s.backtrack与状态s下已经执行过的 迀移集合S.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s.done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设p'是执行迀移tm的线程，若线程p'属于s.done，且tm属于s.enabled，则 将tjj[]入集合s.retrieved中； (3. 3. 4)将s状态下可行迀移集合s.enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' ? enabled 与 s' ? retrieved 集合的差集存入 s' ? enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3. 3. 7. 6)递归调用DLT(S，T，t，SeS)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； 步骤四，返回全局序列集SeS。
[0014] 在上述技术方案中，步骤（4)中序列模式挖掘算法ISPAM的步骤如下： 步骤一，将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup为 0 ; 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V(GS) 和V(BS)，生成V(BS)中项集列表Sinit; 步骤三，对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. 1. 1)调用SAVE0方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，Sinit>f在items之后的项的集合组成的三元组； 步骤四，如果存在元组>属于R集合并且r的支持度大于等于minsup，则 重复做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组< ：> ; (4. 2)通过调用SEARCH0方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVE()方法存储到L中； (4. 3)将元组< 7%S1; >从R中移除； (4. 4)将R中的所有满足>e5+sup(i') <mksup>条件的元组从R中移除； 步骤五，返回含有 前k个缺陷模式的集合L。
[0015] 本发明方法与现有技术相比具有以下优点： 1.对目标源程序进行插装并监控，对目标程序的监控进行设置，针对DPOR算法对循环 较多的程序，执行效率较低的缺点，排除了对相互独立迀移的选取，并将已经检索过的迀移 加入一个专门的集合，避免反复搜索已经执行过的迀移，从而实现了对包含循环较多程序 的化简，提高了执行效率，在选择性搜索过程中，记录轨迹序列，将轨迹序列存入序列集合 中，得到全部的程序轨迹序列。
[0016] 2.针对SPAM算法中用户设置最小支持度带来的模式质量过差和数量过多的问 题，引入项数k来规定对最佳模式数量的挖掘，转化为前k项序列模式挖掘，得到前k项效 果最佳的缺陷解释模式。基于此，为了达到减少搜索空间，提高算法的效率，同时能够解决 缺陷误报问题的目的，定义了成功执行序列集、失效执行序列集、相对支持度概念，所谓成 功执行序列集指的是并发程序的执行结果符合程序的预期行为的执行序列集；所谓失效执 行序列集指的是并发程序的执行结果不符合程序的预期行为的执行序列集；所谓相对支持 度指的频繁出现在失效执行序列集而较少出现在成功执行序列集的一种相对度。在此基础 上，本发明提出了在挖掘过程中通过对成功执行序列集和失效执行序列集中同一模式的比 较来计算其相对支持度，减少对频繁出现在成功执行序列集中的模式选取，从而降低缺陷 误报率的方法。
【附图说明】
[0017] 图1为本发明方法的流程图。
【具体实施方式】
[0018] 本实施使用装有Windows7操作系统的PC机作为平台，通过MyEclipse开发并发 程序缺陷检测程序。本发明实施时，用户必须安装1. 7版本以上的JDK，以获取Java提供的 新特性。
[0019] 此外，需定义如下术语： (1)监控现场：指监控的目标程序运行时的状态信息。
[0020] (2)通知：指程序执行中明确定义的点（接入点）被程序运行所触发时应该执行的 代码。
[0021] (3)并发程序的状态：指由所有共享变量的全局状态和每个线程的局部状态所组 成的状态。
[0022] (4)并发程序的迀移：指为将程序从一个状态转移到下一个状态，某个线程执行的 一个可见操作。
[0023] (5)垂直成功执行序列集：指用位图表示的垂直格式的成功执行序列集。
[0024] (6)垂直失效执行序列集：指用位图表示的垂直格式的失效执行序列集。
[0025] 本发明实施例涉及如下文献：
[1]FlanaganC,GodefroidP.DynamicPartial-OrderReductionforModel CheckingSoftwareP0PL; 2005[M].NewYork:ACMpress, 2005〇
[0026] [2]Ayres,J. ,Flannick,J. ,Gehrke,J. ,Yiu,T. .SequentialPAttern miningusingabitmaprepresentation,Proc. 8thACMSIGKDDInt.Conf.on KnowledgeDiscoveryandDataMining(KDD2002),July23-26, 2002,Edmonton, Alberta,pp. 429-435 (2002)〇
[0027] 以下以在PC机上采用Java语言在JDK开发环境下开发并发程序缺陷检测程序为 例说明本发明技术方案。
[0028](一）设置监控目标程序。
[0029] 为了获取并发程序执行的状态信息，首先需要对被监控的目标程序进行设置。具 体做法是：基于面向方面编程思想，在需监控的目标程序中定义监控点、切点（pointcut)、 通知（advice)，使用探针注入方式对监控点进行监控以获取状态信息。
[0030] 获取状态信息过程中涉及到的相关变量定义，具体如表1所示。
[0031] 表1获取状态信息过程中的符号
获取状态彳目息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序 中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点； 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切 点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行， 通知内的transform()方法将临时变量meg中的内容以及执行环境中的线程标识符转换成 监控现场信息，并存入在事件类EventPO中。
[0032](二）使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度。
[0033] 使用本发明提出的动态标记迀移算法DLT，对待监控的并发程序中的线程执行进 行调度。
[0034] 本算法要用到的相关符号定义如表2所示。
[0035] 表2.动态标记迀移算法DLT中的符号
所述动态标记迀移算法DLT(S，T，t，SeS)的步骤如下： 算法输入参数有：全局状态栈S，全局迀移序列集T，局部迀移t和初始的全局序列集SeS。算法输出参数有：全局序列集SeS。
[0036] (1)将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量〇中； (2) 更新s的回溯信息； (3) 如果存在线程p和s状态下可行迀移集合s.enabled中线程p的一个迀移元素t， 执行以下步骤： (3. 1)将线程p赋值给状态s的回溯集s. backtrack ; (3. 2)创建状态s下已经执行过的迀移集合s.done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s. backtrack与状态s下已经执行过的 迀移集合s.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s.done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设p'是执行迀移tm的线程，若线程p'属于s.done，且tm属于s.enabled，则 将乜加入集合s.retrieved中； (3. 3. 4)将s状态下可行迀移集合s.enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' ? enabled 与 s' ? retrieved 集合的差集存入 s' ? enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3. 3. 7. 6)递归调用DLT(S，T，t，SeS)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； (4) 返回全局序列集SeS。
[0037] 其具体算法如下。
[0038](三）把监控到的状态信息，以轨迹序列的形式存储在数据库中。
[0039] 把监控获取到的状态信息，存储在事件类EventPO中，通过Dao方法将事件类 EventPO中的信息以轨迹序列的形式存储在数据库SDB中。类EventPO记录每个监控点事 件；类SequencePO记录每次执行的序列信息，其中包括序列id、序列结果状态（status)。
[0040]使用Hibernate进行对象关系映射 0RM(0bjectRelationshipMapping，0RM) 操作，和数据访问对象DAO(DataAccessObject，DAO)操作Java中的持久化对象P0 (persistantobject，P0)，完成将EventPO和SequencePO中数据存储到数据库SDB〇
[0041] 事件类EventPO的定义如下： publicclassEventPO{ privateintprimaryKey; // 表示项的序号privateintthreadID; //表示线程的序号 privateStringthreadName;//表不线程名 privateintmethodLine;//表示被监控方法所在行 privateStringmethodName;//表示被监控方法名 privateintshareMemorylndex;//表不共享内存的序号 privateStringshareMemoryValue;//表不共享内存的值 privateDatedate;//表 示操作日期 privateintmillisecond;//表不操作时间 privateSequencePOsequence;//表不所属的序列号 } 上述定义中： primaryKey表示项的序号；threadID表示线程的序号； threadName表示线程名； methodLine表示被监控方法所在行； methodName表示被监控方法名； shareMemorylndex表示共享内存的序号； shareMemoryValue表示共享内存的值； date表示操作日期； millisecond表示操作时间； sequence表示所属的序列号。
[0042](四）获取数据库中每条轨迹序列的执行结果，对轨迹序列进行分类，得到成功执 行序列集和失效执行序列集。
[0043] 获取轨迹序列中的执行结果状态（status)，依据预先定义的失效结果，判定并发 程序中序列执行结果的状态是否丢失修改，或是否存在不可重复读、或是否读"脏"数据等 情况中的一种，如是则执行结果是失效的，对轨迹序列进行分类，得到成功执行序列集和失 效执行序列集。
[0044](五）基于轨迹序列的并发程序缺陷模式挖掘。
[0045] 在成功执行序列集和失效执行序列集中，利用以下改进的序列模式挖掘算法 ISPAM对存储在数据库的数据集进行挖掘，得到并发程序缺陷模式。
[0046] 序列模式挖掘算法ISPAM的相关变量含义如表3所示。
[0047] 表3序列模式挖掘算法ISPAM中的符号
所述序列模式挖掘算法ISPAM的步骤如下： (1) 将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup 为〇 ; (2) 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集 V(GS)和V(BS)，生成V(BS)中项集列表Sinit; (3) 对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. 1. 1)调用SAVEO方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，Sinit>f在items之后的项的集合组成的三元组； (4) 如果存在元组< >属于R集合并且r的支持度大于等于minsup，则重复 做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组> ; (4. 2)通过调用SEARCHO方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVE()方法存储到L中； (4. 3)将元组< >从1?中移除； (4. 4)将R中的所有满足
条件的元组从R中移除； (5)返回含有前k个缺陷模式的集合L。 [0048] 其具体算法如下。
【主权项】
1. 一种并发程序的缺陷模式发现方法，其特征在于该方法包括以下步骤： (1) 监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获 取状态信息； (2) 使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度，获取目标 程序的监控点的状态信息； (3) 把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹 序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集； (4) 在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘， 得到目标程序缺陷模式。2. 根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（1)中所述 的获取状态信息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，在待监控的并发程序中针对共享 变量的读写操作定义监控点，接着在监控点处添加若干个切点； 步骤二，定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切点匹配 时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行，通知内 的transformO方法将用于存放包含源程序中被监控方法的参数表数组args中的行号、序 列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现场信息，并 存入在事件类EventPO中。3. 根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（2)中所 述的动态标记迀移算法DLT (S，T，t，SeS)的算法输入参数有：全局状态栈S，全局迀移序 列集T，局部迀移t和初始的全局序列集SeS ;算法输出参数有：全局序列集SeS ;其步骤如 下： 步骤一，将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量σ中； 步骤二，更新s的回溯信息； 步骤三，如果存在线程P和s状态下可行迀移集合s. enabled中线程ρ的一个迀移元 素 t，执行以下步骤： (3. 1)将线程ρ赋值给状态s的回溯集s. backtrack ; (3. 2)创建状态s下已经执行过的迀移集合s. done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s. backtrack与状态s下已经执行过的 迀移集合s. done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s. done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设ρ'是执行迀移tm的线程，若线程ρ'属于s. done，且t m属于s. enabled，则 将乜加入集合s. retrieved中； (3. 3. 4)将s状态下可行迀移集合s. enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' · enabled 与 s' · retrieved 集合的差集存入 s' · enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3.3.7.6)递归调用01^(5，1'，七，565)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； 步骤四，返回全局序列集SeS。4.根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（4)中序列 模式挖掘算法ISPAM的步骤如下： 步骤一，将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量 minsup 为 O ; 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V (GS) 和V (BS)，生成V (BS)中项集列表Sinit; 步骤三，对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. I. 1)调用SAVEO方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，SinitIf在items之后的项的集合组成的三元组； 步骤四，如果存在元组<:R>属于R集合并且r的支持度大于等于minsup，则重 复做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组<r.S:;S: > ; (4. 2)通过调用SEARCH0方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVEO方法存储到L中； (4. 3)将元组< >从R中移除； (4. 4)将R中的所有满足< r: -S1r S.i >e i? sup⑴< minsup >条件的元组从R中移除； 步骤五，返回含有前k个缺陷模式的集合L。
【专利摘要】本发明属于软件故障诊断领域，提供一种自主发现并发程序缺陷模式的方法，尤其是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法，本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘，自主发现程序缺陷模式。
【IPC分类】G06F11/36
【公开号】CN104899137
【申请号】CN201510264963
【发明人】叶俊民, 李超, 曹洋洋, 叶竹君, 李蓉, 杨艳
【申请人】华中师范大学
【公开日】2015年9月9日
【申请日】2015年5月22日
【技术领域】
[0001] 本发明属于软件故障诊断领域，是一种自主发现并发程序缺陷模式的方法，尤其 是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法。
【背景技术】
[0002] 发现并发程序缺陷是一件困难的事情，一般都只能根据日志信息判断故障原因， 而普通的监控系统只对软件行为进行检测而无法进一步判断软件的执行是否处于正确的 轨迹(正确的行为）之上。
[0003] 基于面向方面编程的监控程序可将监测逻辑和业务逻辑相互分离，能方便获取到 一个并行程序系统的执行轨迹。针对这些获取到的并发程序系统的执行轨迹，可利用序列 模式挖掘技术对这些轨迹进行挖掘，这样能有效解决并发程序故障诊断困难的问题，并能 从并发程序执行轨迹这一海量数据中提取有用信息，以获取到隐含在历史并发程序轨迹 序列集上的故障特征关键点。这种技术将可有效地保障并发软件系统的安全性。
[0004] 现有技术的典型实现方案如下： 第一，基于专家系统的故障/缺陷诊断程序。其主要原理是将领域专家的知识与经验 被表示成产生式规则，并在知识库和数据库的支持下，综合运用各种规则进行一系列的推 理。该诊断程序在运行中要求用户输入必要的信息后，就可快速地直接找到最终故障/缺 陷或是最有可能的故障/缺陷，并由用户对结果进行进一步判断。但这种方法需要建立规 则库，并利用规则库对程序轨迹状态进行判断和预测，这种方法的主要缺点是自动化程度 不高，方法的复用性较差。
[0005] 第二，方便和有效的获取程序执行轨迹是进行软件故障/缺陷诊断的前提。在程 序执行轨迹获取方面，美国加利福尼亚大学伯克利分校和贝儿实验室共同提出了动态偏序 化简算法（DynamicPartialOrderReduction，DP0R)，探索线程的交互执行情况，并提出 了Persistent集合的概念，以保证线程执行情况搜索的完备性。该算法从程序的初始状态 执行的迀移序列开始采用深度优先搜索程序状态栈，动态探索线程间交互信息，然后利用 这些信息去鉴定回溯点，从而探索状态空间的可选路径，获取程序执行轨迹。
[0006] 在程序状态的搜索过程中计算各个状态的Persistent集合，使得程序里所有迀 移序列都不是空序列，在某一状态下可行的迀移集合里所有迀移和其他迀移序列中的迀移 都是独立的，保证搜索的完备性。
[0007] 但该算法的主要缺点是没有将完整地程序轨迹序列获取并存储；没有为程序轨迹 序列的进一步分析提供基础；没有针对含有循环的并发程序进行优化，会出现对已经搜索 过的迀移反复搜索的情况，这会造成了DP0R算法效率的低下，这反映在采用该算法的总探 索时间和单次平均探索时间都较长。
[0008] 第三，在对缺陷模式的发现方法上，美国康奈尔大学提出序列模式挖掘算法 (SequentialPAtternMining,SPAM)进行序列模式挖掘，对序列集进行挖掘得到频繁模 式。SPAM算法首先将序列信息存储于数据库位图中，然后可在项集层面实行项集拓展，和可 在序列层面实行序列拓展，并使用格理论对数据库进行深度优先遍历从而找出序列模式。SPAM算法的主要缺点是需要用户自己来设定最小支持度阈值，不当的支持度阈值可能带来 挖掘出的模式质量差的问题；只能对单一类型的序列集进行处理，误报情况严重。
【发明内容】
[0009] 本发明的目的在于针对以上不足，在传统基于动态偏序化简算法获取并发程序执 行轨迹和SPAM算法进行序列模式挖掘的基础上，针对算法的核心步骤，即获取并发程序轨 迹和对轨迹进行挖掘以发现缺陷模式，提出涉及这两步的改进的做法，能自主发现程序缺 陷模式。
[0010] 本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执 行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘得到缺陷模 式。
[0011] 本发明提供一种并发程序的缺陷模式发现方法，包括以下步骤： (1) 监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获 取状态信息； (2) 使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度，获取目标 程序的监控点的状态信息； (3) 把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹 序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集； (4) 在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘， 得到目标程序缺陷模式。
[0012] 在上述技术方案中，步骤（1)中所述的获取状态信息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序 中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点； 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切 点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行， 通知内的transformO方法将用于存放包含源程序中被监控方法的参数表数组args中的 行号、序列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现场 信息，并存入在事件类EventPO中。
[0013] 在上述技术方案中，步骤（2)中所述的动态标记迀移算法DLT(S，T，t，SeS)的算 法输入参数有：全局状态栈S，全局迀移序列集T，局部迀移t和初始的全局序列集SeS;算 法输出参数有：全局序列集SeS;其步骤如下： 步骤一，将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量〇中； 步骤二，更新s的回溯信息； 步骤三，如果存在线程P和s状态下可行迀移集合s.enabled中线程p的一个迀移元 素t，执行以下步骤： (3. 1)将线程p赋值给状态s的回溯集s.backtrack; (3. 2)创建状态s下已经执行过的迀移集合s.done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s.backtrack与状态s下已经执行过的 迀移集合S.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s.done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设p'是执行迀移tm的线程，若线程p'属于s.done，且tm属于s.enabled，则 将tjj[]入集合s.retrieved中； (3. 3. 4)将s状态下可行迀移集合s.enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' ? enabled 与 s' ? retrieved 集合的差集存入 s' ? enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3. 3. 7. 6)递归调用DLT(S，T，t，SeS)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； 步骤四，返回全局序列集SeS。
[0014] 在上述技术方案中，步骤（4)中序列模式挖掘算法ISPAM的步骤如下： 步骤一，将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup为 0 ; 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V(GS) 和V(BS)，生成V(BS)中项集列表Sinit; 步骤三，对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. 1. 1)调用SAVE0方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，Sinit>f在items之后的项的集合组成的三元组； 步骤四，如果存在元组>属于R集合并且r的支持度大于等于minsup，则 重复做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组< ：> ; (4. 2)通过调用SEARCH0方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVE()方法存储到L中； (4. 3)将元组< 7%S1; >从R中移除； (4. 4)将R中的所有满足>e5+sup(i') <mksup>条件的元组从R中移除； 步骤五，返回含有 前k个缺陷模式的集合L。
[0015] 本发明方法与现有技术相比具有以下优点： 1.对目标源程序进行插装并监控，对目标程序的监控进行设置，针对DPOR算法对循环 较多的程序，执行效率较低的缺点，排除了对相互独立迀移的选取，并将已经检索过的迀移 加入一个专门的集合，避免反复搜索已经执行过的迀移，从而实现了对包含循环较多程序 的化简，提高了执行效率，在选择性搜索过程中，记录轨迹序列，将轨迹序列存入序列集合 中，得到全部的程序轨迹序列。
[0016] 2.针对SPAM算法中用户设置最小支持度带来的模式质量过差和数量过多的问 题，引入项数k来规定对最佳模式数量的挖掘，转化为前k项序列模式挖掘，得到前k项效 果最佳的缺陷解释模式。基于此，为了达到减少搜索空间，提高算法的效率，同时能够解决 缺陷误报问题的目的，定义了成功执行序列集、失效执行序列集、相对支持度概念，所谓成 功执行序列集指的是并发程序的执行结果符合程序的预期行为的执行序列集；所谓失效执 行序列集指的是并发程序的执行结果不符合程序的预期行为的执行序列集；所谓相对支持 度指的频繁出现在失效执行序列集而较少出现在成功执行序列集的一种相对度。在此基础 上，本发明提出了在挖掘过程中通过对成功执行序列集和失效执行序列集中同一模式的比 较来计算其相对支持度，减少对频繁出现在成功执行序列集中的模式选取，从而降低缺陷 误报率的方法。
【附图说明】
[0017] 图1为本发明方法的流程图。
【具体实施方式】
[0018] 本实施使用装有Windows7操作系统的PC机作为平台，通过MyEclipse开发并发 程序缺陷检测程序。本发明实施时，用户必须安装1. 7版本以上的JDK，以获取Java提供的 新特性。
[0019] 此外，需定义如下术语： (1)监控现场：指监控的目标程序运行时的状态信息。
[0020] (2)通知：指程序执行中明确定义的点（接入点）被程序运行所触发时应该执行的 代码。
[0021] (3)并发程序的状态：指由所有共享变量的全局状态和每个线程的局部状态所组 成的状态。
[0022] (4)并发程序的迀移：指为将程序从一个状态转移到下一个状态，某个线程执行的 一个可见操作。
[0023] (5)垂直成功执行序列集：指用位图表示的垂直格式的成功执行序列集。
[0024] (6)垂直失效执行序列集：指用位图表示的垂直格式的失效执行序列集。
[0025] 本发明实施例涉及如下文献：
[1]FlanaganC,GodefroidP.DynamicPartial-OrderReductionforModel CheckingSoftwareP0PL; 2005[M].NewYork:ACMpress, 2005〇
[0026] [2]Ayres,J. ,Flannick,J. ,Gehrke,J. ,Yiu,T. .SequentialPAttern miningusingabitmaprepresentation,Proc. 8thACMSIGKDDInt.Conf.on KnowledgeDiscoveryandDataMining(KDD2002),July23-26, 2002,Edmonton, Alberta,pp. 429-435 (2002)〇
[0027] 以下以在PC机上采用Java语言在JDK开发环境下开发并发程序缺陷检测程序为 例说明本发明技术方案。
[0028](一）设置监控目标程序。
[0029] 为了获取并发程序执行的状态信息，首先需要对被监控的目标程序进行设置。具 体做法是：基于面向方面编程思想，在需监控的目标程序中定义监控点、切点（pointcut)、 通知（advice)，使用探针注入方式对监控点进行监控以获取状态信息。
[0030] 获取状态信息过程中涉及到的相关变量定义，具体如表1所示。
[0031] 表1获取状态信息过程中的符号
获取状态彳目息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，首先由用户在待监控的并发程序 中针对共享变量的读写操作定义监控点，接着用户在监控点处添加若干个切点； 步骤二，由用户定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切 点匹配时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行， 通知内的transform()方法将临时变量meg中的内容以及执行环境中的线程标识符转换成 监控现场信息，并存入在事件类EventPO中。
[0032](二）使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度。
[0033] 使用本发明提出的动态标记迀移算法DLT，对待监控的并发程序中的线程执行进 行调度。
[0034] 本算法要用到的相关符号定义如表2所示。
[0035] 表2.动态标记迀移算法DLT中的符号
所述动态标记迀移算法DLT(S，T，t，SeS)的步骤如下： 算法输入参数有：全局状态栈S，全局迀移序列集T，局部迀移t和初始的全局序列集SeS。算法输出参数有：全局序列集SeS。
[0036] (1)将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量〇中； (2) 更新s的回溯信息； (3) 如果存在线程p和s状态下可行迀移集合s.enabled中线程p的一个迀移元素t， 执行以下步骤： (3. 1)将线程p赋值给状态s的回溯集s. backtrack ; (3. 2)创建状态s下已经执行过的迀移集合s.done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s. backtrack与状态s下已经执行过的 迀移集合s.done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s.done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设p'是执行迀移tm的线程，若线程p'属于s.done，且tm属于s.enabled，则 将乜加入集合s.retrieved中； (3. 3. 4)将s状态下可行迀移集合s.enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' ? enabled 与 s' ? retrieved 集合的差集存入 s' ? enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3. 3. 7. 6)递归调用DLT(S，T，t，SeS)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； (4) 返回全局序列集SeS。
[0037] 其具体算法如下。
[0038](三）把监控到的状态信息，以轨迹序列的形式存储在数据库中。
[0039] 把监控获取到的状态信息，存储在事件类EventPO中，通过Dao方法将事件类 EventPO中的信息以轨迹序列的形式存储在数据库SDB中。类EventPO记录每个监控点事 件；类SequencePO记录每次执行的序列信息，其中包括序列id、序列结果状态（status)。
[0040]使用Hibernate进行对象关系映射 0RM(0bjectRelationshipMapping，0RM) 操作，和数据访问对象DAO(DataAccessObject，DAO)操作Java中的持久化对象P0 (persistantobject，P0)，完成将EventPO和SequencePO中数据存储到数据库SDB〇
[0041] 事件类EventPO的定义如下： publicclassEventPO{ privateintprimaryKey; // 表示项的序号privateintthreadID; //表示线程的序号 privateStringthreadName;//表不线程名 privateintmethodLine;//表示被监控方法所在行 privateStringmethodName;//表示被监控方法名 privateintshareMemorylndex;//表不共享内存的序号 privateStringshareMemoryValue;//表不共享内存的值 privateDatedate;//表 示操作日期 privateintmillisecond;//表不操作时间 privateSequencePOsequence;//表不所属的序列号 } 上述定义中： primaryKey表示项的序号；threadID表示线程的序号； threadName表示线程名； methodLine表示被监控方法所在行； methodName表示被监控方法名； shareMemorylndex表示共享内存的序号； shareMemoryValue表示共享内存的值； date表示操作日期； millisecond表示操作时间； sequence表示所属的序列号。
[0042](四）获取数据库中每条轨迹序列的执行结果，对轨迹序列进行分类，得到成功执 行序列集和失效执行序列集。
[0043] 获取轨迹序列中的执行结果状态（status)，依据预先定义的失效结果，判定并发 程序中序列执行结果的状态是否丢失修改，或是否存在不可重复读、或是否读"脏"数据等 情况中的一种，如是则执行结果是失效的，对轨迹序列进行分类，得到成功执行序列集和失 效执行序列集。
[0044](五）基于轨迹序列的并发程序缺陷模式挖掘。
[0045] 在成功执行序列集和失效执行序列集中，利用以下改进的序列模式挖掘算法 ISPAM对存储在数据库的数据集进行挖掘，得到并发程序缺陷模式。
[0046] 序列模式挖掘算法ISPAM的相关变量含义如表3所示。
[0047] 表3序列模式挖掘算法ISPAM中的符号
所述序列模式挖掘算法ISPAM的步骤如下： (1) 将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量minsup 为〇 ; (2) 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集 V(GS)和V(BS)，生成V(BS)中项集列表Sinit; (3) 对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. 1. 1)调用SAVEO方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，Sinit>f在items之后的项的集合组成的三元组； (4) 如果存在元组< >属于R集合并且r的支持度大于等于minsup，则重复 做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组> ; (4. 2)通过调用SEARCHO方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVE()方法存储到L中； (4. 3)将元组< >从1?中移除； (4. 4)将R中的所有满足
条件的元组从R中移除； (5)返回含有前k个缺陷模式的集合L。 [0048] 其具体算法如下。
【主权项】
1. 一种并发程序的缺陷模式发现方法，其特征在于该方法包括以下步骤： (1) 监控目标程序，使用面向方面编程探针代码的注入方法对监控点进行监控以便获 取状态信息； (2) 使用动态标记迀移算法DLT对设置监控点的目标程序的执行进行调度，获取目标 程序的监控点的状态信息； (3) 把监控到的状态信息，以轨迹序列的形式存储在数据库中，获取数据库中每条轨迹 序列的执行结果，对轨迹序列进行分类，得到成功执行序列集和失效执行序列集； (4) 在成功执行序列集和失效执行序列集中，利用序列模式挖掘算法ISPAM进行挖掘， 得到目标程序缺陷模式。2. 根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（1)中所述 的获取状态信息的步骤如下： 步骤一，基于面向方面编程思想和待监控的源程序，在待监控的并发程序中针对共享 变量的读写操作定义监控点，接着在监控点处添加若干个切点； 步骤二，定义每一个切点对应的通知，同时定义该通知需执行的处理代码，当切点匹配 时，通知内定义的处理代码在切点之前，或在切点之后，或在切点附近这3处执行，通知内 的transformO方法将用于存放包含源程序中被监控方法的参数表数组args中的行号、序 列号信息的临时变量meg中的内容以及执行环境中的线程标识符转换成监控现场信息，并 存入在事件类EventPO中。3. 根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（2)中所 述的动态标记迀移算法DLT (S，T，t，SeS)的算法输入参数有：全局状态栈S，全局迀移序 列集T，局部迀移t和初始的全局序列集SeS ;算法输出参数有：全局序列集SeS ;其步骤如 下： 步骤一，将S中的栈顶元素出栈存入状态s，将SeS中的当前序列存入序列变量σ中； 步骤二，更新s的回溯信息； 步骤三，如果存在线程P和s状态下可行迀移集合s. enabled中线程ρ的一个迀移元 素 t，执行以下步骤： (3. 1)将线程ρ赋值给状态s的回溯集s. backtrack ; (3. 2)创建状态s下已经执行过的迀移集合s. done，并将其置为空； (3. 3)如果存在某一线程q是状态s的回溯集s. backtrack与状态s下已经执行过的 迀移集合s. done的差集中的元素，重复执行以下步骤，直到不存在这样的线程q为止： (3. 3. 1)将q加入状态s下已经执行过的迀移集合s. done中； (3. 3. 2)从状态s的回溯集s. backtrack中删除线程q ; (3. 3. 3)设ρ'是执行迀移tm的线程，若线程ρ'属于s. done，且t m属于s. enabled，则 将乜加入集合s. retrieved中； (3. 3. 4)将s状态下可行迀移集合s. enabled中线程q执行的迀移设置为tn; (3. 3. 5)创建项集is并初始化为空，并将tn添加到is中； (3. 3. 6)将项集is添加到序列变量〇中； (3. 3. 7)判断从状态s出发且执行tnS移后到达的状态是否为空值，若不是，则执行以 下步骤，否则不执行： (3. 3. 7. 1)将从状态s出发且执行tnS移后得到的状态设为s' ； (3. 3. 7. 2)将独立于迀移t且属于s. enabled中的迀移t'存入s', retrieved集合中； (3. 3. 7. 3)将 s' · enabled 与 s' · retrieved 集合的差集存入 s' · enabled 中； (3. 3. 7. 4)将迀移、添加入迀移序列T中； (3. 3. 7. 5)将状态s'压入状态栈S中； (3.3.7.6)递归调用01^(5，1'，七，565)算法； (3. 3. 7. 7)将T中的最后一项序列移出； (3. 3. 8)将S中的一项状态出栈； 步骤四，返回全局序列集SeS。4.根据权利要求1所述的并发程序的缺陷模式发现方法，其特征在于步骤（4)中序列 模式挖掘算法ISPAM的步骤如下： 步骤一，将候选模式集合R和前k个缺陷模式的集合L设置为空集，并设置全局变量 minsup 为 O ; 步骤二，将成功执行序列集GS和失效执行序列集BS分别转化为垂直序列数据集V (GS) 和V (BS)，生成V (BS)中项集列表Sinit; 步骤三，对于项集列表Sinit中的每一个项items，完成以下步骤： (3. 1)计算其是否是频繁项，如果是： (3. I. 1)调用SAVEO方法对由单个项组成的模式存储到L中； (3. 1. 2)在R集合添加项items，Sinit，SinitIf在items之后的项的集合组成的三元组； 步骤四，如果存在元组<:R>属于R集合并且r的支持度大于等于minsup，则重 复做以下步骤，直到不满足这一条件为止： (4. 1)选择R集合中拥有最高支持度的模式r的元组<r.S:;S: > ; (4. 2)通过调用SEARCH0方法对候选模式集合R进行拓展，更新候选模式集合R，并将 拓展得到的模式调用SAVEO方法存储到L中； (4. 3)将元组< >从R中移除； (4. 4)将R中的所有满足< r: -S1r S.i >e i? sup⑴< minsup >条件的元组从R中移除； 步骤五，返回含有前k个缺陷模式的集合L。
【专利摘要】本发明属于软件故障诊断领域，提供一种自主发现并发程序缺陷模式的方法，尤其是一种针对系统执行轨迹使用序列模式挖掘的缺陷模式发现方法，本发明的技术方案是基于已插装的并发程序，在其运行过程中动态调度线程的执行，实时收集程序执行信息，根据需要存储程序轨迹序列，对执行序列进行挖掘，自主发现程序缺陷模式。
【IPC分类】G06F11/36
【公开号】CN104899137
【申请号】CN201510264963
【发明人】叶俊民, 李超, 曹洋洋, 叶竹君, 李蓉, 杨艳
【申请人】华中师范大学
【公开日】2015年9月9日
【申请日】2015年5月22日
最新回复(0)