符号执行的路径爆炸及约束求解问题研究
发布时间：2021-01-09 20:53
软件测试是确保软件质量的重要方法,基本的技术手段是利用不同的测试案例去执行被测程序,测试案例的选取密切地关系着软件测试的质量和软件的质量。符号执行是一种经典程序分析技术,它将程序中的变量符号化来模拟程序的运行,收集程序路径,使用约束求解器对路径约束条件求解后得到测试案例。现实中,符号执行的应用受到路径爆炸和约束求解等问题的制约,被测程序中的循环结构是重要的影响因素,可能会导致程序路径规模成倍增长,为测试案例的生成增加困难,降低测试案例生成效率。针对软件测试案例生成过程中循环结构造成的路径爆炸问题及约束求解问题进行研究,主要研究内容:（1）对符号执行技术以及相关技术理论进行充分调查和研究。介绍选择性符号执行和启发式路径搜索策略的理论与思想,详细给出策略的概念、原理和执行流程,并使用实例具体演示执行步骤。提出基于控制流图优化循环结构的路径搜索策略。定义三种循环结构和相关算法;结合选择性符号执行思想指导测试案例生成;在路径选择过程中引入启发式搜索策略,对路径进行优先级排序与选择,引导路径的生成。（2）对主流约束求解工具进行充分研究和整理。为提高约束求解时间效率,提出综合约束求解方法。对搜集到...
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：58 页
【学位级别】：硕士
【图文】：
图２．１示例代码的符号执行树??Ｆｉｇ．?２．１?Ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ?ｆｏｒ?ｅｘａｍｐｌｅ?ｃｏｄｅ??２．?２动态符号执行??
?符号执行的路径爆炸及约束求解问题研究???ｘ＜０??ｒ＾＼??乂?＞?，?Ｘ??＜，ｙ＋ｚ＞５?＇?ａ＝２，ｂ＝２，ｃ＝３?＾ｙ＋ｚ＞５?ａ＝ｌ，ｂ＝２，ｃ＝３???！?Ｘ?＼??１???Ｚ?Ｆｘ???Ｚ?＼?ｊ??ａ＝２，ｂ＝３，ｃ＝－３?ａ＝２，ｂ＝２，ｃ—３?ａ＝ｌ，ｂ＝３，ｃ＝－３?ａ＝ｌ，ｂ＝２，ｃ＝－３??图２．１示例代码的符号执行树??Ｆｉｇ．?２．１?Ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ?ｆｏｒ?ｅｘａｍｐｌｅ?ｃｏｄｅ??２．?２动态符号执行??动态符号执行在软件测试案例生成研究领域受到非常广泛的关注。第二节主要讨论??动态符号执行技术的核心思想和执行过程，并使用示例代码来辅助说明执行过程；介绍??动态符号执行技术中的程序插桩技术。??２．２．１动态符号执行相关概念??随着现代计算水平和存储能力的优化与增强，作为路径敏感分析技术的符号执行通??过对内存模型的优化、搜索策略以及约束求解技术等方面的改进，根据发展状况，出现??动态符号执行技术和选择性符号执行技术。??程序插桩??符、‘播?＂否?，＜?结束、）???＾约束收集??初始输入）￣１符号化￣＾丨??路径搜索??Ｌ卜－十」—测试案例??约束求解??图２．２动态符号执行的通用框架模型??Ｆｉｇ．?２．２?Ｇｅｎｅｒａｌ?ｆｒａｍｅｗｏｒｋ?ｍｏｄｅｌ?ｆｏｒ?ｄｙｎａｍｉｃ?ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ??－８?－??
?大连海事大学专业学位硕士学位论文???ＡＰＰ］??ＫＥＲＮＥＬ?Ｚ??图?３．２?ＡＰＰ，?ＬＩＢ，ＫＥＲＮＥＬ?三个模块??Ｆｉｇ．?３．２?ＡＰＰ，?ＬＩＢ，?ＫＥＲＮＥＬ?ｍｏｄｕｌｅｓ??）?ａｐｐ?ｃｏｎｃｒｅｔｅ??ｌｉｂ?ｓｙｍｂｏｌｉｃ??…ｔＴ?（．……１??＞?＞?＼?ｋｅｒｎｅｌ?ｃｏｎｃｒｅｔｅ??＼＼?＼?／?〉＼ａｐｐ?ｃｏｎｃｒｅｔｅ??图３．３结果执行树??Ｆｉｇ．?３．３?Ｒｅｓｕｌｔｉｎｇ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ??选择性符号执行需要把执行状态在符号域和具体域之间互相转换。当从符号域切换??到具体域时，在调用约束求解器对当前部分路径的约束条件进行求解得到的值域中，选??择一个解作为具体执行的输入；当从具体域切换到符号域时，则把具体值用符号值代替，??同时利用具体执行的路径信息得到具体执行过程中的约束。选择性符号执行在符号执行??与具体执行交替处理时，须关注分析的准确性，两个区域转换过程中需要设置界限，并??保证程序状态的一致性，文献［２０］中由维持转换过程中约束一致性的策略。??使用２．１节中Ｊａｖａ语言的示例代码来阐述选择性符号执行的原理，此时指定代码中??风ｙ＋２＞５）０＝３；｝的代码段为特殊区域，在此区域进行符号分析，对其余代码部分进行具??体执行。对指定的特殊区域进行符号分析，仅有符号变量７和符号变量ｘ作具体值??处理。假设随机生成的初始输入为ｘ＝０，；；＝０，ｚ＝０。当到指定的特殊区域进行符号执行时，??－１５?－??
【参考文献】：
期刊论文
[1]形状分析符号执行引擎中的状态合并[J]. 邓维,李兆鹏. 计算机科学. 2017(02)
[2]基于混合搜索的含逻辑“与”“或”的RM优化算法[J]. 吕荫润,陈力,王翀,吴敬征,王永吉. 软件学报. 2017(10)
[3]改进动态符号执行中的非线性约束求解过程[J]. 董齐兴,曾凡平,严俊,张辉,彭凌. 小型微型计算机系统. 2014(11)
博士论文
[1]符号执行可扩展性及可行性关键技术研究[D]. 张羽丰.国防科学技术大学 2013
本文编号：2967380
【文章来源】：大连海事大学辽宁省 211工程院校
【文章页数】：58 页
【学位级别】：硕士
【图文】：
图２．１示例代码的符号执行树??Ｆｉｇ．?２．１?Ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ?ｆｏｒ?ｅｘａｍｐｌｅ?ｃｏｄｅ??２．?２动态符号执行??
?符号执行的路径爆炸及约束求解问题研究???ｘ＜０??ｒ＾＼??乂?＞?，?Ｘ??＜，ｙ＋ｚ＞５?＇?ａ＝２，ｂ＝２，ｃ＝３?＾ｙ＋ｚ＞５?ａ＝ｌ，ｂ＝２，ｃ＝３???！?Ｘ?＼??１???Ｚ?Ｆｘ???Ｚ?＼?ｊ??ａ＝２，ｂ＝３，ｃ＝－３?ａ＝２，ｂ＝２，ｃ—３?ａ＝ｌ，ｂ＝３，ｃ＝－３?ａ＝ｌ，ｂ＝２，ｃ＝－３??图２．１示例代码的符号执行树??Ｆｉｇ．?２．１?Ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ?ｆｏｒ?ｅｘａｍｐｌｅ?ｃｏｄｅ??２．?２动态符号执行??动态符号执行在软件测试案例生成研究领域受到非常广泛的关注。第二节主要讨论??动态符号执行技术的核心思想和执行过程，并使用示例代码来辅助说明执行过程；介绍??动态符号执行技术中的程序插桩技术。??２．２．１动态符号执行相关概念??随着现代计算水平和存储能力的优化与增强，作为路径敏感分析技术的符号执行通??过对内存模型的优化、搜索策略以及约束求解技术等方面的改进，根据发展状况，出现??动态符号执行技术和选择性符号执行技术。??程序插桩??符、‘播?＂否?，＜?结束、）???＾约束收集??初始输入）￣１符号化￣＾丨??路径搜索??Ｌ卜－十」—测试案例??约束求解??图２．２动态符号执行的通用框架模型??Ｆｉｇ．?２．２?Ｇｅｎｅｒａｌ?ｆｒａｍｅｗｏｒｋ?ｍｏｄｅｌ?ｆｏｒ?ｄｙｎａｍｉｃ?ｓｙｍｂｏｌ?ｅｘｅｃｕｔｉｏｎ??－８?－??
?大连海事大学专业学位硕士学位论文???ＡＰＰ］??ＫＥＲＮＥＬ?Ｚ??图?３．２?ＡＰＰ，?ＬＩＢ，ＫＥＲＮＥＬ?三个模块??Ｆｉｇ．?３．２?ＡＰＰ，?ＬＩＢ，?ＫＥＲＮＥＬ?ｍｏｄｕｌｅｓ??）?ａｐｐ?ｃｏｎｃｒｅｔｅ??ｌｉｂ?ｓｙｍｂｏｌｉｃ??…ｔＴ?（．……１??＞?＞?＼?ｋｅｒｎｅｌ?ｃｏｎｃｒｅｔｅ??＼＼?＼?／?〉＼ａｐｐ?ｃｏｎｃｒｅｔｅ??图３．３结果执行树??Ｆｉｇ．?３．３?Ｒｅｓｕｌｔｉｎｇ?ｅｘｅｃｕｔｉｏｎ?ｔｒｅｅ??选择性符号执行需要把执行状态在符号域和具体域之间互相转换。当从符号域切换??到具体域时，在调用约束求解器对当前部分路径的约束条件进行求解得到的值域中，选??择一个解作为具体执行的输入；当从具体域切换到符号域时，则把具体值用符号值代替，??同时利用具体执行的路径信息得到具体执行过程中的约束。选择性符号执行在符号执行??与具体执行交替处理时，须关注分析的准确性，两个区域转换过程中需要设置界限，并??保证程序状态的一致性，文献［２０］中由维持转换过程中约束一致性的策略。??使用２．１节中Ｊａｖａ语言的示例代码来阐述选择性符号执行的原理，此时指定代码中??风ｙ＋２＞５）０＝３；｝的代码段为特殊区域，在此区域进行符号分析，对其余代码部分进行具??体执行。对指定的特殊区域进行符号分析，仅有符号变量７和符号变量ｘ作具体值??处理。假设随机生成的初始输入为ｘ＝０，；；＝０，ｚ＝０。当到指定的特殊区域进行符号执行时，??－１５?－??
【参考文献】：
期刊论文
[1]形状分析符号执行引擎中的状态合并[J]. 邓维,李兆鹏. 计算机科学. 2017(02)
[2]基于混合搜索的含逻辑“与”“或”的RM优化算法[J]. 吕荫润,陈力,王翀,吴敬征,王永吉. 软件学报. 2017(10)
[3]改进动态符号执行中的非线性约束求解过程[J]. 董齐兴,曾凡平,严俊,张辉,彭凌. 小型微型计算机系统. 2014(11)
博士论文
[1]符号执行可扩展性及可行性关键技术研究[D]. 张羽丰.国防科学技术大学 2013
本文编号：2967380
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2967380.html
