隐式规则自动提取与反例检测方法研究

摘要

在大规模程序中存在许多隐式编程规则，它们表达了程序的内在特性和特定需求；如果程序员忘记或者未意识到这些规则，那么就很容易将缺陷引入程序。隐式编程规则形态多样，可能包含多种类型的程序元素，位置分散，各个成分可能跨函数、跨文件分布，人工审查的方法很难查找到这些规则。因此很有必要研究如何从程序中自动提取隐式规则并形成文档说明。然而，现有的研究成果只能提取简单的基于函数对的程序规则，而不能挖掘出包含函数、变量和数据类型等多种程序元素的隐式规则；而且为实现规则提取，它们还需要程序员提供规则模板，对人工参与的程度要求较高。
　　为从程序中提取更多不同种类的规则，同时减少人工参与的程度，本文提出一种通用且高效的程序隐式规则自动提取与反例检测方法。该方法使用频繁闭合项集挖掘技术从大型软件源码中挖掘包含多种程序元素的编程模式，然后由编程模式产生编程规则；引入正序规则(PSDRule)概念，以避免从同一个编程模式中产生多个冗余规则。在此基础上，还提出一种高效的反例检测算法以检测违反规则的程序片段，它们很有可能包含程序缺陷。整个规则提取和反例检测过程是自动化的，不需要程序员提供任何预设信息，也不需要对目标程序有任何先验知识。
　　在多个大型开源项目源码上的实验结果表明，本文提出的规则提取和反例检测模型能够自动提取程序中存在的隐式编程规则，并且基于提取的规则快速有效地检测程序中违反这些规则的代码片段。通过对实验结果经人工分析和确认，发现本文方法提取出多条有意义的规则，并检测到了一些真实的缺陷。

目录

隐式规则自动提取与反例检测方法研究

Research on Automatically Extracting Implicit Programming Rules and Detecting Violations

摘 要

Abstract

目 录

第1章 绪 论

1.1 课题研究的目的与意义

1.2 国内外研究现状及分析

1.3 课题研究的主要内容及创新点

1.4 论文章节安排

第2章 数据挖掘在规则提取和反例检测的研究与应用

2.1 数据挖掘概述

2.2 引入数据挖掘技术的原因

2.3 基于数据挖掘的规则提取和反例检测方法的基本流程

2.4 基于数据挖掘方法的研究分类

2.5 基于数据挖掘方法的规则提取的应用

2.6 本章小结

第3章 频繁项集挖掘算法研究

3.1 频繁项集挖掘算法概述

3.2 频繁项集挖掘问题描述

3.3 FP-growth算法

3.4 CLOSET算法

3.5 本章小结

第4章 基于频繁闭合项集挖掘的隐式规则自动提取与反例检测模型

4.1 模型总体设计框架

4.2 隐式规则举例

4.3 选取感兴趣的语法成分

4.4 数据库生成

4.5 改进的频繁项集挖掘算法

4.6 规则生成与反例检测

4.7 本章小结

第5章 实验结果与分析

5.1 开源代码上的实验

5.2 两种方法的对比

5.3 误检分析

5.4 规则提取和反例检测仿真实验及分析

5.5 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢