基于序列模式挖掘的软件行为模式分析

摘要

随着软件规模的不断增大，对复杂软件系统的行为进行分析日益成为数据挖掘领域的热点。软件的一次运行对应一条执行轨迹，表示软件的一次行为，从大量的软件执行轨迹中挖掘出人们感兴趣的行为模式对于帮助解决软件缺陷定位、软件异常检测、测试用例的选择和约减具有重要的现实意义。从数据挖掘的角度来看，软件的执行轨迹可以看成软件执行序列，因此，结合序列模式挖掘，从大量动态软件执行轨迹中进行软件行为模式分析。
　　本研究主要内容包括：⑴从软件执行轨迹中提取软件执行序列，并从动态、静态两个角度出发，结合距离匹配和统计分析方法提出一种关键函数的度量方法，既可以识别出软件中的关键函数，又可以为下文研究提供参考。⑵提出了一种基于PT-tree的频繁模式挖掘算法，该算法将软件执行序列数据库压缩成一个树结构，并通过数据结构FNodesets存储PT-tree中每个节点包含的项集，利用集合枚举树作为搜索空间，并基于超集等价特性作为剪枝策略，提升算法的效率。⑶结合前文给出的关键函数度量标准以及函数之间的调用关系，提出了一种基于函数调用路径序列的高效用路径模式挖掘算法 FHUPPM。根据关键函数的排名分配各函数项的外部效用所占的比重，设计了一种表结构PIUL用于存储模式的效用信息和位置信息，提出了UCMS矩阵结构，并基于该结构设计了一种高效用模式剪枝策略，作为相邻路径模式扩展的判断依据。⑷对提出的挖掘算法进行实现，基于Windows平台，通过java语言进行实现。并通过对比算法进行实验分析，验证提出的算法在运行时间，内存占用及可扩展性等方面的性能。

目录

声明

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 国内外研究现状

1.3 存在的问题

1.4 主要研究内容

1.5 文章的总体结构

第2章 软件执行序列的构建及关键函数的识别

2.1 引言

2.2 关键函数

2.3 构建软件执行序列

2.4 关键函数的识别

2.5 本章小结

第3章 基于频繁模式挖掘分析函数之间的关联性

3.1 引言

3.2 基本概念定义

3.3 软件执行序列中基于PT-tree的频繁模式挖掘算法设计

3.4 算法实例

3.5 本章小结

第4章 基于函数调用路径的高效用路径模式挖掘算法

4.1 引言

4.2 基本概念定义

4.3 基于函数调用路径的高效用路径模式挖掘算法设计

4.4 算法实例

4.5 本章小结

第5章 算法实验结果与分析

5.1 实验环境基本配置

5.2 实验所用数据集

5.3 实验结果及分析

5.4 基于PT-tree的频繁模式挖掘算法的性能分析

5.5 基于函数调用路径的高效用路径模式挖掘算法的性能分析

5.6 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢