一句话：提出 APC-IP 算法，高效计算过程间函数的渐近路径复杂度，并预测符号执行的路径爆炸。
符号执行等软件测试技术常受路径爆炸困扰。渐近路径复杂度（APC）可量化这种爆炸，但已有 APC 方法一般无法处理过程间函数。本文提出 APC-IP 算法，能够高效计算更广泛函数的 APC，包括过程间调用，并在速度与适用范围上优于先前方法。作者将 APC-IP 实现于 Metrinome 之上，在 C 函数基准上，与现有方法和基线对比，并与符号执行引擎 KLEE 的路径爆炸进行比较。结果表明，APC-IP 不仅与既有 APC 值一致，还在性能、可扩展性和复杂源码处理上表现更优；它还能预测 KLEE 探索的路径数量，扩展了 APC 指标的应用范围并超越此前实现。
Software testing techniques like symbolic execution face significant challenges with path explosion. Asymptotic Path Complexity (APC) quantifies this path explosion complexity, but existing APC methods do not work for interprocedural functions in general. Our new algorithm, APC-IP, efficiently computes APC for a wider range of functions, including interprocedural ones, improving over previous methods in both speed and scope. We implement APC-IP atop the existing software Metrinome, and test it against a benchmark of C functions, comparing it to existing and baseline approaches as well as comparing it to the path explosion of the symbolic execution engine Klee. The results show that APC-IP not only aligns with previous APC values but also excels in performance, scalability, and handling complex source code. It also provides a complexity prediction of the number of paths explored by Klee, extending the APC metric's applicability and surpassing previous implementations.
@inproceedings{paperbot8527,
title = {Interprocedural Path Complexity Analysis},
author = {Mira Kaniyur and Ana Cavalcante-Studart and Yihan Yang and Sangeon Park and David Chen and Duy Lam and Lucas Bang},
booktitle = {ISSTA},
year = {2024},
doi = {10.1145/3650212.3652118}
}