Differences between static analysis and (dynamic) testing?

My Answer:

  • Static Analysis: Before compling the program, the analysis tool will detect whether the program is suitable to compile.
  • Dynamic Analysis: detect program whether true while compling?

Exact Answer:

  • Static Analysis: 运行程序 P 前，静态分析会 analyze P to reason about its behaviors 和判断 P 是否满足一些 properties:

    1. Does P contain any private information leaks
    2. Does P dereference any null pointers
    3. Whether cast is safe
    4. Can v1 and v2 in P point to the same memory location
    5. Will certain assert statement in P fail
    6. Is this piece of code in P dead ?

  • Dynamic analysis is the testing and evaluation of a program by executing data in real-time.

    JVM - 会在真实或虚拟处理器上执行程序来执行对软件的分析

Other notes:

  • Rice Theorem: no approach to determine whether P satisfies such non-trivial properties.

  • non-trivial: 能理解为一些 与程序运行时有关的性质(i.e. 信息泄漏)，因此莱斯定理可以理解为：不可能存在一个方法能给出 non-trivial properties 的 exact answers.

“Any non-trivial property of the behavior of programs in a r.e. language is undecidable.”

r.e.(recursive emunerable): 递归可枚举的语言 - 指能被 Turing-machine 识别的语言，现代高级语言都是 r.e. 的

Understand soundness, completeness, false negatives, and false positives

My Answer:

Posix: 程序 P 中只有 10 个分析异常的行为 - 即 Truth = 10

  • Soundness: 比 Truth 范围大，Soundness 性质会分析出 P 内可能有 12 个错误
  • completeness: 比 Truth 范围小，但分析出来的一定是对的，只是会少于 10 个错误
  • False negatives: Negatives 指 Soundness 范围缩小达到 Truth，但可能缩减太厉害，此时分析出的异常少于 10 个，漏报异常，即应该是 Truth 的却分析成了 negatives 而没报出。
  • False positives: Positives 扩大 completeness 范围，有可能分析出不在 Truth 范围的异常，即不属于 P 程序的异常，为异常误报

Exact Answer:

Why soundness is usually required by static analysis?

My Answer:

  • 因为达到 perfect 是没什么可能的，宁愿多提醒这块代码可能有异常，也不要为了 completeness 而少提醒

Exact Answer

  • Unsound: “Safe cast” -> wrong
  • Sound: “Not safe cast” - correct

如上方有两条 flows，如果只看 B->A，会认为是 Safe，这样不 Sound 会得出一个错的结论

Abstraction and over-approximation?

My Answer:

  • Abstraction: 将程序变量的 OP 作为抽象符号，静态分析时根据抽象符号来判断
  • Over-approximation: 过于 Sound，可以理解为 Compromise completeness

Exact Answer: (我的答案描述很不全啊)

  • Abstration: Determine the sign(+, -, or 0) of all the variables of a given program.

  • Over-approximation: Produces false positives, while is taken for granted in most static analyses.

    更 Sound 意味着能更安全些