5.2.3　不可达路径的特征调研

本节所调研的不可达路径选自与不可达路径检测相关的学术论文[14-18]以及6个广泛使用的开源工程(WCET-benchmark、CoreUtil、libPNG、sqlito、nanoxml、IPEGbenchmark)。

程序中若存在返回值无法直观判定的函数调用,这样的函数被当作未指定的函数(uninterpreted function)来处理,认为其能够返回满足路径约束的任意值,这种对于外部函数的近似处理方法被很多分析工具采用[9]。

不可达路径的特征从控制流和数据流两方面特征进行分类。循环结构是一种能够导致路径爆炸的控制流结构;在CSP中,相比于不等式,等式条件更加难以满足[19]。因此本节对于循环结构和等式操作在不可达路径中的出现频次进行了统计。

统计结果如图5-9所示,结果表明,在不可达路径中,包含等式操作的路径占了总路径的76%(图5-9(a)),包含循环结构的路径占了54%(图5-9(b))。对于包含循环结构的不可达路径所做的进一步分析表明,这其中有60%(图5-9(c))的路径上矛盾约束与等式操作相关。(https://www.daowen.com)

图5-9　不可达路径中循环和等式出现的比例

基于此统计数据,我们推测循环结构和等式操作与不可达路径之间存在着相关性。一个直观的解释是,循环结构导致程序路径的长度可能变得很长,已有的研究表明,路径长度越长,路径不可达的可能性越高[20];路径中的等式操作导致路径约束难以满足。在下一节,我们定义一个代码片段模式来描述包含循环结构和等式条件的情况。