-
题名进化算法与符号执行结合的程序复杂度分析方法
- 1
-
-
作者
周晟伊
曾红卫
-
机构
上海大学计算机工程与科学学院
上海市计算机软件评测重点实验室
-
出处
《计算机科学》
CSCD
北大核心
2021年第12期107-116,共10页
-
基金
国家重点研发计划(2020YFB1006003)。
-
文摘
程序的最坏执行路径是计算程序复杂度的一项重要指标,有助于发现系统可能存在的复杂性漏洞。近年来将符号执行应用于程序复杂度分析的研究取得了不小的进展,但现有方法存在通用性较差、分析时间较长的问题。文中提出一种面向最坏路径探测的进化算法——EvoWca,其核心思想是利用程序在较小输入规模下的已知最坏路径特征指导较大输入规模下初始路径集合的构建,然后模拟进化算法,对路径进行组合、突变和选择迭代,使得在搜索范围内探测到的最坏路径逼近于最坏时间复杂度对应的路径。基于该算法实现了一个用于程序复杂度分析的原型工具EvoWca2j,使用该工具和已有技术对一组Java程序进行最坏路径探索和执行效率评估,实验结果表明,相比现有方法,EvoWca2j的通用性和探索效率都有明显提高。
-
关键词
复杂度分析
符号执行
进化算法
路径探测
最坏执行路径
-
Keywords
Complexity analysis
Symbolic execution
Evolutionary algorithm
Path detection
Worst case execution path
-
分类号
TP311.5
[自动化与计算机技术—计算机软件与理论]
-