进化算法与符号执行结合的程序复杂度分析方法

程序的最坏执行路径是计算程序复杂度的一项重要指标,有助于发现系统可能存在的复杂性漏洞。近年来将符号执行应用于程序复杂度分析的研究取得了不小的进展,但现有方法存在通用性较差、分析时间较长的问题。文中提出一种面向最坏路径探测的进化算法——EvoWca,其核心思想是利用程序在较小输入规模下的已知最坏路径特征指导较大输入规模下初始路径集合的构建,然后模拟进化算法,对路径进行组合、突变和选择迭代,使得在搜索范围内探测到的最坏路径逼近于最坏时间复杂度对应的路径。基于该算法实现了一个用于程序复杂度分析的原型工具EvoWca2j,使用该工具和已有技术对一组Java程序进行最坏路径探索和执行效率评估,实验结果表明,相比现有方法,EvoWca2j的通用性和探索效率都有明显提高。

基于WCET的SPM实时性管理策略

提出一种基于最坏情况执行时间(WCET)的SPM静态分配算法,该算法采用额外的WCET分析工具获得任务最坏情况执行路径(WCEP),针对最坏情况执行路径,把程序划分为全局变量、全局堆栈、指令块等节点,用包含节点和节点间关系的CFG描述应用程序,采用考虑节点间关系的算法把选中的节点分配到SPM中。仿真实验结果表明,采用该分配策略管理SPM空间比不采用SPM时的实时性提高54%左右。