程序分析的精确性

问题描述 投票:0回答:1

根据David Brumley的控制流完整性&软件故障隔离(PPT幻灯片)。

在下面的语句中,由于x总是8,即使采用路径敏感分析,x=7的路径也是无法实现的。

为什么会这样呢?"是因为在分析过程中不能预先确定n、a、b、c的值吗?还是因为没有可以用计算机计算的解?


if(a^n + b^n = c^n &&n>2 &&a>0 &&b>0 &&c>0) x = 7; 无法实现的路径别的

x = 8;

precision static-analysis
1个回答
0
投票

一般情况下,确定程序中哪条路径被采取,哪条--不被采取,这个任务是无法确定的。很有可能,一个特定的表达式,就像你的例子一样,可以被证明有一个特定的值。但是,"一般情况下 "和 "不可决定 "这两个词是说,你不可能写出一个每次都能计算出这个值的算法。

这时,分析算法可以是乐观的,也可以是悲观的。乐观的可以选择 8 就可以了--它认为有可能在运行时 x 会得到这个值。它也可以选择 7 - "谁知道呢,也许。x 将是 7". 但如果要求分析合理,而又不能确定条件值,则应假设在一次执行过程中可以取第一个分支,在另一次执行过程中可以取第二个分支,所以 x 可以是 78.

换句话说,在健全性和精确性之间有一个权衡。或者,实际上,在健全性、精确性和可决断性之间。后一个属性告诉我们分析是否总是终止。现在,你必须选择需要什么。

  • 可决断性 - 这是编译器和代码分析器的常见选择, 因为你想在有限的时间内得到一个关于你的程序的答案. 然而,证明助手可以启动一些进程,这些进程可以运行到指定的时间限制,如果没有设置限制,则永远:用户可以停止它,并尝试其他东西。

  • 健全性--这是编译器的常见选择,因为你希望得到与语言规范相匹配的答案。代码分析器比较灵活。他们中的许多人都是不健全的,但正因为如此,他们可以在有限的时间内发现更多的潜在问题,将解释工作留给开发者。我相信你提到的例子谈到的是健全的分析。

  • 精确性--这是一个罕见的属性。编译器和代码分析器应该是悲观的,因为否则一些不正确的代码可能会潜入。但这可能是可以参数化的。例如,如果编译器分析器支持常量传播和折叠,并且例子中的所有变量在条件前都被设置为一些已知的常量,它就可以算出准确的值 x 后,而且要完全精确。

© www.soinside.com 2019 - 2024. All rights reserved.