基于软件执行图的行为特性的算法研究

发布时间：2018-05-30 00:13

本文选题：软件执行图 + 高效用模式　；参考：《燕山大学》2016年硕士论文

【摘要】：大数据时代,软件系统规模与应用领域的日益复杂,使得软件动态执行轨迹需要新的处理模式才能成为具有更强决策力与洞察力的信息资产。因此,如何有效地挖掘软件的内在特征,基于软件动态执行轨迹实现其行为特性的建模与算法的研究,成为软件开发质量的基本保障,有助于软件在适用领域的合理应用及发展。本课题利用数据挖掘技术,从海量的软件执行轨迹中挖掘用户感兴趣的行为模式,以适用于广泛的软件安全分析、软件质量评估、软件漏洞挖掘等领域。首先,提出一种基于软件动态执行轨迹的软件执行图的构建方法。基于软件的不同粒度,使用分布函数生成不同粒度下的单元项权重、序列效用值等参数,采用深度优先遍历的方法构建软件执行序列,将每一条序列作为软件的一次函数执行序列,并最终形成软件动态执行序列集合。其次,提出一种基于有希望扩展的高效用序列模式挖掘算法。该算法将软件执行轨迹序列化,设计了表结构Pre-Utility-List用于存储模式的效用信息和索引。为存储长度为2的序列效用值,提出了PEUS结构,并基于此提出一种潜在高效用模式的剪枝策略,有助于模式效用上界值的降低。再次,提出一种基于软件执行图的Top-k高效用路径模式挖掘算法。基于软件执行序列中函数的调用顺序及依赖关系,提出了预插入策略Pre-insertion,以提高初始效用阈值。排序策略Sorting和过滤策略Filtering的使用有助于较早地扩展潜在高效用模式,以提高算法效率。最后,对本文提出的算法用Java语言在Windows平台下进行实现。通过实验分析算法在运行时间、候选集数量、内存使用空间等方面的性能。
[Abstract]:In the era of big data, the scale and application of software system are becoming more and more complex, which makes the dynamic execution path of software need a new processing mode to become an information asset with stronger decision power and insight. Therefore, how to effectively mine the inherent characteristics of software, and how to model and study the algorithm based on the dynamic execution trajectory of software become the basic guarantee of software development quality. It is helpful for the rational application and development of software in the field of application. In this paper, we use data mining technology to mine the behavior patterns of users' interest from the massive software execution path, which can be used in a wide range of software security analysis, software quality assessment, software vulnerability mining and other fields. Firstly, a method of constructing software execution diagram based on software dynamic execution trajectory is proposed. Based on the different granularity of the software, the distribution function is used to generate the cell item weight and the sequence utility value under different granularity, and the depth first traversal method is used to construct the software execution sequence. Each sequence is regarded as the first function sequence of the software, and finally the dynamic execution sequence set of the software is formed. Secondly, a high utility sequential pattern mining algorithm based on promising extension is proposed. The algorithm serializes the software execution trajectory and designs a table structure Pre-Utility-List to store the utility information and index of the schema. In order to store the sequence utility value of length 2, the PEUS structure is proposed, and a pruning strategy of potential high utility pattern is proposed, which is helpful to reduce the upper bound value of pattern utility. Thirdly, a Top-k high utility path pattern mining algorithm based on software execution graph is proposed. Based on the call order and dependency of functions in the software execution sequence, a pre-insertion strategy is proposed to improve the initial utility threshold. The use of sorting strategy Sorting and filtering strategy Filtering helps to extend the potential high utility pattern earlier to improve the efficiency of the algorithm. Finally, the algorithm proposed in this paper is implemented on Windows platform with Java language. The performance of the algorithm in terms of running time, number of candidate sets, memory usage space and so on is analyzed experimentally.
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13;TP311.5

【相似文献】