论文标题
路径同源性作为循环复杂性的更强类似物
Path homology as a stronger analogue of cyclomatic complexity
论文作者
论文摘要
循环复杂性是一种未完全指定但数学原则性的软件指标，可以有效地应用于源代码和二进制代码。我们将路径同源性的应用视为循环复杂性的更强类似物。我们已经实现了一种算法来计算任意维度的路径同源性，并将其应用于几类相关的流程图，包括代表结构化和非结构化控制流的随机生成的流程图。我们还比较了从GREP实用程序获得的一组拆卸的二进制文件中的路径同源性和环形复杂性。在组装级别上存在控制流程图，而在任意维度中具有非平凡路径同源性。我们在这种静脉中展示了几类示例，同时还在实验上证明了路径同源性为至少一个结构化对照流的详细概念提供了与环境复杂性相同的结果。我们还在实验上证明了这两个概念在分解的二进制文件上有所不同，我们重点介绍了极端分歧的一个例子。路径同源性从经验上概括了结构化代码的基本概念的循环复杂性，并且似乎可以确定控制流的结构相关特征。因此，路径同源性具有基本上改善环境复杂性的潜力。
Cyclomatic complexity is an incompletely specified but mathematically principled software metric that can be usefully applied to both source and binary code. We consider the application of path homology as a stronger analogue of cyclomatic complexity. We have implemented an algorithm to compute path homology in arbitrary dimension and applied it to several classes of relevant flow graphs, including randomly generated flow graphs representing structured and unstructured control flow. We also compared path homology and cyclomatic complexity on a set of disassembled binaries obtained from the grep utility. There exist control flow graphs realizable at the assembly level with nontrivial path homology in arbitrary dimension. We exhibit several classes of examples in this vein while also experimentally demonstrating that path homology gives identicial results to cyclomatic complexity for at least one detailed notion of structured control flow. We also experimentally demonstrate that the two notions differ on disassembled binaries, and we highlight an example of extreme disagreement. Path homology empirically generalizes cyclomatic complexity for an elementary notion of structured code and appears to identify more structurally relevant features of control flow in general. Path homology therefore has the potential to substantially improve upon cyclomatic complexity.
