编写一个计算机程序来分析另一个计算机程序的质量？

Question

我很想知道这种可能性。我正在从事一个验证软件工程师技能的项目，目前我们根据有资质的开发人员的代码审查来验证技能。

我知道答案，如果比这个问题更完整的话，我无法想象该程序必须能够分析复杂的代码有多复杂，但我从基本的编程面试问题开始。

比如经典的FizzBuzz问题：

编写一个程序，打印从 1 到 20 的数字。但是对于三的倍数打印“Fizz”而不是数字，对于五的倍数打印“Buzz”。对于同时为三和五的倍数的数字打印“FizzBuzz”。

以下是python中的解决方案：

for num in range(1,21):
    string = ""
    if num % 3 == 0:
        string = string + "Fizz"
    if num % 5 == 0:
        string = string + "Buzz"
    if num % 5 != 0 and num % 3 != 0:
        string = string + str(num)
    print(string)

问题是，我们能否以编程方式分析此解决方案的有效性？

我想知道有没有人尝试过这个，如果有当前的实现我可以看看。另外如果有人用过z3，如果它是我可以用来解决这个问题的东西。

Answer 1

让我们这样说：数学证明您不能确定如果一个程序将永远终止。所以如果你想要一个数学上完美的答案来判断目标程序是否正确，那你就完蛋了。

也就是说，您仍然可以进行单元测试，"linting" 这会给您带来很多有趣的见解。

但对于像 FizzBuzz 这样的简单代码，我认为由经验丰富的开发人员观察可能会带来最好的结果。

Answer 2

正如 Vilx- 提到的，程序的正确性（包括它们是否终止）通常是不可判定的。然而，诸如 Z3 之类的工具表明，尽管问题通常具有不确定性，但仍然可以对相关的具体案例进行推理。

静态分析器 通常寻找 "simple" 问题（例如 null 取消引用、越界访问、数值溢出），但速度相对较快且需要很少的用户指导（本着向代码添加类型注释的精神考虑指导）。

要搜索的关键字的非详尽（且有偏见）列表："static analysers"、"abstract interpretation"； "facebook infer", "airbus absint", "juliasoft".

验证者 试图证明更丰富的属性，特别是功能正确性，例如"does this sort-implementation really sort my array (and not do anything else, e.g. deallocate some global memory or update an element reachable from the array)?" 或 "does that crypto-implementation really implement the crypto protocol it promises to implement?"。这是一项多更艰巨的任务，来自该研究领域的工具通常相当缓慢，需要具有正式验证背景和重要用户指导的专家用户。

要搜索的关键字的非详尽（且有偏见）列表："verification"、"hoare logic"、"separation logic"； "eth viper", "microsoft dafny", "kuleuven verifast", "microsoft f*".

存在其他形式化方法，例如改进（或通过构造纠正），但工具支持更少，据我所知，行业接受度。

编写一个计算机程序来分析另一个计算机程序的质量？

Writing a computer program that will analyse the quality of another computer program?

testing

automated-tests

software-quality

z3