程序分析的精确性
Precision in Program analysis
根据 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;
一般来说,确定程序中的哪条路径被采用以及哪条路径不被采用的任务是不可判定的。很可能可以证明特定表达式(如您的示例)具有特定值。但是,"in general" 和 "undecidable" 这两个词表示您无法编写每次都能计算该值的算法。
此时分析算法可以是乐观的也可以是悲观的。乐观的人可以选择 8
并且没问题——它认为在 运行 时间 x
可能会得到这个值。它还可以选择 7
— "who knows, maybe, x
would be 7
"。但是如果要求分析的很好,不能确定条件的取值,就应该假设一次执行可以走第一个分支,另一次执行可以走第二个分支,所以x
可以是 7
或 8
.
换句话说,在稳健性和精确性之间存在权衡。或者,实际上,在稳健性、精确性和可判定性之间。后者 属性 告诉分析是否总是终止。现在,您必须选择需要的内容:
可判定性 — 这是编译器和代码分析器的常见选择,因为您希望在有限的时间内获得有关程序的答案。但是,证明助手可以启动一些可以 运行 达到指定时间限制的进程,如果未设置限制,则永远:由用户停止并尝试其他操作。
Soundness — 这是编译器的常见选择,因为您希望得到符合语言规范的答案。代码分析器更加灵活。其中很多都是不健全的,但正因为如此,他们可以在有限的时间内发现更多潜在的问题,将解释权留给开发人员。我相信你提到的例子是关于声音分析的。
精度 — 这是罕见的 属性。编译器和代码分析器应该是悲观的,否则一些不正确的代码可能会潜入。但这可能是可参数化的。例如,如果 compiler/analyzer 支持常量传播和折叠,并且示例中的所有变量在条件之前都设置为一些已知常量,它可以计算出它之后的 x
的确切值,并且完全准确。
根据 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;
一般来说,确定程序中的哪条路径被采用以及哪条路径不被采用的任务是不可判定的。很可能可以证明特定表达式(如您的示例)具有特定值。但是,"in general" 和 "undecidable" 这两个词表示您无法编写每次都能计算该值的算法。
此时分析算法可以是乐观的也可以是悲观的。乐观的人可以选择 8
并且没问题——它认为在 运行 时间 x
可能会得到这个值。它还可以选择 7
— "who knows, maybe, x
would be 7
"。但是如果要求分析的很好,不能确定条件的取值,就应该假设一次执行可以走第一个分支,另一次执行可以走第二个分支,所以x
可以是 7
或 8
.
换句话说,在稳健性和精确性之间存在权衡。或者,实际上,在稳健性、精确性和可判定性之间。后者 属性 告诉分析是否总是终止。现在,您必须选择需要的内容:
可判定性 — 这是编译器和代码分析器的常见选择,因为您希望在有限的时间内获得有关程序的答案。但是,证明助手可以启动一些可以 运行 达到指定时间限制的进程,如果未设置限制,则永远:由用户停止并尝试其他操作。
Soundness — 这是编译器的常见选择,因为您希望得到符合语言规范的答案。代码分析器更加灵活。其中很多都是不健全的,但正因为如此,他们可以在有限的时间内发现更多潜在的问题,将解释权留给开发人员。我相信你提到的例子是关于声音分析的。
精度 — 这是罕见的 属性。编译器和代码分析器应该是悲观的,否则一些不正确的代码可能会潜入。但这可能是可参数化的。例如,如果 compiler/analyzer 支持常量传播和折叠,并且示例中的所有变量在条件之前都设置为一些已知常量,它可以计算出它之后的
x
的确切值,并且完全准确。