Metrinome: Path Complexity Predicts Symbolic Execution Path Explosion
Metrinome: Path Complexity Predicts Symbolic Execution Path Explosion
复制标题
DOI：
10.1109/icse-companion52605.2021.00028
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Gabriele Beßler;Joshimar Cordova;Shaheen Cullen-Baratloo;Sofiane Dissem;Emily Lu;Sofia Devin;Ibrahim Abughararh;Lucas Bang
中科院分区：
文献类型：
--
作者：
Gabriele Beßler;Joshimar Cordova;Shaheen Cullen-Baratloo;Sofiane Dissem;Emily Lu;Sofia Devin;Ibrahim Abughararh;Lucas Bang
本文介绍了一种用于C函数自动路径复杂度分析的工具Metrinome。函数的路径复杂度是一个表达式，它描述了在给定执行深度之前通过函数的路径数。Metrinome利用LLVM实用程序构建了C函数的控制流图CFG，利用代数图论和解析组合学对CFG进行了分析，并给出了函数的路径复杂度和渐近路径复杂度的封闭表达式。我们的实验表明，路径复杂性预测了Klee（一种流行的符号执行工具）能够在给定的探索深度内覆盖的执行路径数量的增长率。Metrinome是开源的，可以作为Docker镜像立即使用，我们所有的实验和数据都可以在我们的存储库中使用，并包含在我们的Docker镜像中。
This paper presents Metrinome, a tool for performing automatic path complexity analysis of C functions. The path complexity of a function is an expression that describes the number of paths through the function up to a given execution depth. Metrinome constructs the control flow graph CFG of a C function using LLVM utilities, analyzes that CFG using algebraic graph theory and analytic combinatorics, and produces a closed-form expression for the path complexity as well as the asymptotic path complexity of the function. Our experiments show that path complexity predicts the growth rate of the number of execution paths that Klee, a popular symbolic execution tool, is able to cover within a given exploration depth. Metrinome is open-source, available as a Docker image for immediate use, and all of our experiments and data are available in our repository and included in our Docker image.