基于扩展马尔可夫模型的程序约束挖掘方法研究

《基于扩展马尔可夫模型的程序约束挖掘方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinComputerScienceandTechnologyResearchonMiningProgramSpecificationsBasedonExtendedMarkovModelPh.D.Candidate：DengChenMajor：ComputerSoftwareandTheorySupervisor：Prof.YanshengLuHua

2、zhongUniversityofScienceandTechnologyWuhan，Hubei430074，P.R.ChinaSeptember，2014独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学

3、位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。学位论文作者签名：指导教师签名：日期：年月日日期：年月日华中科技大学博士学位论文摘要程序中的时序约束是一类广泛存在的约束，其规定了组件的接口函数之间调用的先后顺序关系。例如：调用java.util.Stack类的peek()函数之前，如果没

4、有调用push()函数，程序会因为空栈而抛出EmptyStackException异常；又比如调用java.util.Iteration类的next()函数之前，如果没有调用hasNext()函数查看是否有元素存在，就会导致NoSuchElementException异常。根据时序约束，可以对程序进行有效的验证，检测出多种类型的错误。然而，时序约束经常被软件开发人员忽视，在软件说明文档中也鲜有相关说明。自动化程序约束挖掘是获得时序约束的重要方法。这类方法大都采用静态分析或者动态分析的技术从程序中提取函数调用信息，然后利用数据挖掘

5、、机器学习和数理统计等方法归纳出采用各种形式描述的时序约束。然而，这类方法通常都受训练数据中的噪声和多样性等因素的制约。为了更好的提取程序中的时序约束，围绕着噪声和多样性等问题展开研究，采用一种具有终止概率的扩展马尔可夫模型进行时序约束挖掘。首先，基于类之间具有继承关系这一性质，从程序中收集大量的对象使用场景作为训练数据，然后采用一种联机算法对扩展马尔可夫模型进行训练，最后给出了一种基于客户端/服务器架构的动态时序约束挖掘框架。训练数据规模对于数据挖掘、机器学习等方法具有十分重要的意义。一方面，大规模的训练数据能缓解噪声带来的干

6、扰；另一方面，大规模的训练数据具有更好的多样性。因此，收集大量的对象使用场景作为时序约束挖掘器的输入，是缓解数据噪声和多样性问题并且获得准确而完备的时序约束的重要基础。大量对象使用场景提取方法根据类之间具有继承关系这一性质，能够从面向对象程序中提取出n倍于传统方法的对象使用场景，其中n为程序中的平均继承深度，为本文工作提供了可靠的数据来源。为了进一步抵抗训练数据中的噪声，采用一种扩展的马尔可夫模型进行时序约束建模。由于其是一种概率模型，与广泛采用的有限自动机相比，具有更好的噪声处理能力。以该模型为基础，采用一种联机方法进行时序约

7、束挖掘。该方法无须存储大量的对象使用场景，其接收对象使用场景中的一个函数调用，然后对已经存在I华中科技大学博士学位论文的时序约束进行更新或者创建一个新的时序约束。由于该方法不存储对象使用场景，因此具有极小的空间开销。另一方面，由于该方法能够对已有的时序约束进行持续更新，因此能够挖掘出更具普遍性的模型。为了使用时序约束，需要将采用概率模型表示的时序约束转换为一种确定性模型。转换过程中的阈值选择是获取正确模型的基础。采用的阈值计算方法不仅对噪声具有良好的处理能力，而且能够确保获得连通的确定性模型。为了减少时序约束挖掘的成本，推进其在

8、工业界的应用，给出了一种基于客户端/服务器架构的动态时序约束挖掘框架NSpecMiner。NSpecMiner采用基于扩展马尔可夫模型的时序约束挖掘方法。其客户端为一个动态程序追踪器，负责对目标程序进行插桩并将收集的程序执行轨迹发送到服务器端。服务器端从广泛分布