基于程序行为特征比较的谓词切换排序

摘要

谓词切换(Predicate Switching)通过动态改变程序中的谓词判断语句状态观察程序运行结果的变化，分析可能与错误相关的关键谓词判断语句，从而实现辅助错误定位。谓词判断语句排序算法决定了谓词切换定位关键谓词判断语句的效率。已有的排序算法如LEFS算法定位效率较低； PRIOR算法虽然提高了定位效率，但必须首先做程序动态切片找寻与错误相关的谓词判断语句集合，而后建立程序依赖图以定义谓词判断语句的优先级，这个过程需要花费大量的时间，且算法复杂度较高。在这两种算法基础上提出一种新的改进排序算法，首先通过对比成功和失败的测试用例在运行中所展现出来不同程序行为特征，以此定义谓词判断语句的优先级，然后对不同优先级别的谓词根据执行先后顺序进行反向排序。基于基准测试集Siemens Suite的程序进行了实验，结果表明本文的排序算法与LEFS算法相比定位效率更高，与PRIOR算法相比减少定义谓词优先级的耗费，且算法更易于实现。