基于符号执行的软件测试效率的优化

《基于符号执行的软件测试效率的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP311论文编号：102871618-SZ026学科分类号：085212硕士学位论文基于符号执行的软件测试效率的优化研究生姓名李航专业类别工程硕士专业领域软件工程指导教师臧洌副教授南京航空航天大学研究生院计算机科学与技术学院二○一八年三月NanjingUniversityofAeronauticsandAstronauticsTheGraduateSchoolCollegeofComputerScienceandTechnologyOptimizationofsoftwaretestingef

2、ficiencybasedonsymbolicexecutionAThesisinSoftwareEngineeringbyLiHangAdvisedbyAssociateProf.ZangLieSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringMarch,2018承诺书本人声明所呈交的硕士学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其它人

3、已经发表或撰写过的研究成果，也不包含为获得南京航空航天大学或其它教育机构的学位或证书而使用过的材料。本人授权南京航空航天大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作者签名：日期：南京航空航天大学全日制专业学位硕士学位论文摘要软件质量是软件的生命，它直接影响着软件的使用和维护。软件测试是保证软件质量的重要手段，也是软件开发流程不可或缺的环节，用来检验软件是否满足规定的需求或者检验预期结果与实际结果是否相

4、符。符号执行可以用来查找程序缺陷、生成测试用例、验证程序正确性等。针对符号执行面临的路径爆炸和约束求解问题，本文研究提升符号执行效率的方法。主要工作包括：(1)提出了冗余路径的消除方法。在软件测试中，探索更多的路径不一定会揭示更多的程序行为。如果在路径中展示的程序行为已经被其它先前探索过的路径表现，则这样的路径是多余的，不需要进行探索。基于此，本文提出了一种通过符号价值概念实现路径缩减的方法，此外针对控制依赖、数据依赖和潜在依赖的不足，引入一种称为交互依赖的新型依赖关系。实验结果表明，冗余路径消除的方法与传

5、统符号执行相比，探索了6.69%-96.57%的路径，实现了1.02-49.56倍的加速。(2)提出了基于蚁群算法的路径搜索策略。猜测符号执行的核心思想是猜测，由于猜测失败时需要进行回溯，降低猜测符号执行的效率，所以猜测的成功率高低是影响整体效率的关键。基于蚁群算法的路径搜索策略，以分支路径的可行性大小为信息素，路径搜索时选择信息素量大的分支方向进行猜测，并在搜索后动态更新分支的可行性（权重）。实验结果表明，基于蚁群算法的路径搜索策略明显减少了路径搜索时间和约束求解时间。(3)改进了传统的集中式调度策略，并

6、使用负载均衡技术共同提升并行符号执行的效率。集中式调度明显的缺点是节点间频繁的通信会导致中心节点繁忙，工作节点出现空闲,影响并行效率。为了解决这个问题，本文增加了缓冲区来存储任务队列，解决任务分发和处理速度不一致的问题，减少工作节点的空闲时间。同时，使用最小任务队列算法来保证各个任务队列长度基本相等，各工作节点负载均衡。实验表明，设置了任务队列的集中式调度，对比传统的集中式调度，能再提高1倍左右的速度。关键词：路径爆炸，约束求解，猜测符号执行，蚁群算法，冗余路径，集中式调度I基于符号执行的软件测试效率的优化

7、ABSTRACTThequalityofsoftwareisthelifeofasoftware,anditdirectlyaffectstheuseandmaintenanceofasoftware.Softwaretestingisanimportantmethodtoensurethequalityofthesoftware,andtheintegralpartofthesoftwaredevelopmentprocess.Itisusedtotestwhetherthesoftwaremeetsth

8、especifiedrequirementsorverifiesthattheexpectedresultsareconsistentwiththeactualresults.Symbolicexecutioncanbeusedtofinddefectsinaprogram,togeneratetestcases,toverifythecorrectnessoftheprogram,etc.Inordertoso