基于符号执行和数据挖掘的路径可达性检测.pdf

《基于符号执行和数据挖掘的路径可达性检测.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于符号执行和数据挖掘的路径可达性检测Pathfeasibilitydetectionusingsymbolicexecutionanddatamining姓名：范彧学号：1100379010班级：B11003791专业：计算机科学与技术导师：赵建军教授答辩日期：2013年1月9日上海交通大学软件学院2012年12月万方数据上海交通大学工学硕士学位论文基于符号执行和数据挖掘的路径可达性检测ADissertationSubmittedtoShanghaiJiaoTongUniversityfortheDegreeofMasterinScience

2、PathfeasibilitydetectionusingsymbolicexecutionanddataminingAuthor:YuFanAdvisor:Prof.JianjunZhaoSpecialty:ComputerSoftwareandTheorySchoolofSoftwareShanghaiJiaoTongUniversityNovember1,2012万方数据万方数据万方数据上海交通大学工学硕士学位论文摘要基于符号执行和数据挖掘的路径可达性检测摘要程序静态分析是指在不运行代码的情况下，利用控制流、数据流分析等技术对源程序进行扫

3、描，检验程序是否满足某些特定的性质，可用于代码优化、软件缺陷检测等各方面。可以说，静态分析是许多软件工程方法和工具的重要基础。在静态分析中一个最常见的假设就是每一条程序路径都是可执行的，然而这种假设在很多时候都过于保守了。D.Hedley针对NAGFortranLibrary的调查显示12.5%的程序路径都是不可达的，也就是说，在所有可能的程序输入下，总有12.5%的路径是不会被执行的。不可达路的存在已经成为把静态分析技术真正应用于软件工程的实践中的一个巨大障碍。在缺乏不可达路径信息的情况下，数据流信息只能以一种非常保守的方式被利用，因而使进一

4、步的工作变得更加困难和低效。在路径导向的测试用例生成过程中，大量不必要的精力被浪费在了不可达路径上；在软件缺陷检测过程中，不可达路径的存在引起了许多误报。针对这一问题，本文提出了一种结合符号执行以及数据挖掘的混合型方法来检测程序中的不可达路径。通过修改传统的符号执行算法，提高其效率，使其更适合被使用在路径可达性判定的问题上。同时，辅助以数据挖掘中关联规则挖掘技术，弥补了特殊的符号执行算法在精度上的不足。效率和精度的权衡可以在运行前调节，以适应不同规模不同种类的程序。本文利用JavaPathFinder模型检测工具、Weka数据挖掘工具以及DiS

5、L字节码插桩工具实现了上述算法，并使用一个典型的Java程序作为例子，展示本方法的可行性。关键词：符号执行；数据挖掘；程序路径；可达性；不可达路径I万方数据上海交通大学工学硕士学位论文ABSTRACTPATHFEASIBILITYDETECTIONUSINGSYMBOLICEXECUTIONADNDATAMININGABSTRACTStaticanalysisistheanalysisthatmakesverificationofpropertiesofcomputerprogramswithoutactuallyexecutingthem.B

6、asedoncontrolflowanddataflowanalysis,itcanbeusedintheareaofcodeoptimizationandbugfinding.Staticanalysisisthebasisofmanysoftwareengineeringmethodsandtools.Acommonassumptionmadeinstaticanalysisisthateveryprogrampathisexecutable.Butitisactuallytooconservativeinmanycases.Reporto

7、nNAGFortranLibrarybyD.Hedleyshowsthatalmost12.5%ofallprogrampathsareinfreasible.Thatis,forallvalidinputs,thereare12.5%oftheprogrampathsneverbeingexecuted.Theexistenceofinfeasibleprogrampathshasbecomeanobstacleinapplyingstaticanalysistosoftwareengineeringactivities.Withoutthe

8、knowledgeoftheinfeasiblepathproblem,dataflowinformationcanonlybetreatedinar