| 进化算法与符号执行结合的程序复杂度分析方法 |
| |
| 引用本文： | 周晟伊,曾红卫. 进化算法与符号执行结合的程序复杂度分析方法[J]. 计算机科学, 2021, 48(12): 107-116. DOI: 10.11896/jsjkx.210200052 |
| |
| 作者姓名： | 周晟伊 曾红卫 |
| |
| 作者单位： | 上海大学计算机工程与科学学院 上海200444;上海市计算机软件评测重点实验室 上海201112;上海大学计算机工程与科学学院 上海200444 |
| |
| 摘 要： | 程序的最坏执行路径是计算程序复杂度的一项重要指标,有助于发现系统可能存在的复杂性漏洞.近年来将符号执行应用于程序复杂度分析的研究取得了不小的进展,但现有方法存在通用性较差、分析时间较长的问题.文中提出一种面向最坏路径探测的进化算法——EvoWca,其核心思想是利用程序在较小输入规模下的已知最坏路径特征指导较大输入规模下初始路径集合的构建,然后模拟进化算法,对路径进行组合、突变和选择迭代,使得在搜索范围内探测到的最坏路径逼近于最坏时间复杂度对应的路径.基于该算法实现了一个用于程序复杂度分析的原型工具EvoWca2j,使用该工具和已有技术对一组Java程序进行最坏路径探索和执行效率评估,实验结果表明,相比现有方法,EvoWca2j的通用性和探索效率都有明显提高.
|
| 关 键 词： | 复杂度分析 符号执行 进化算法 路径探测 最坏执行路径 |
Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution |
| |
| ZHOU Sheng-yi,ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution[J]. Computer Science, 2021, 48(12): 107-116. DOI: 10.11896/jsjkx.210200052 |
| |
| Authors: | ZHOU Sheng-yi ZENG Hong-wei |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
