第一章 - 引言

约 1357 个字 预计阅读时间 5 分钟

程序设计语言

研究领域分支

• 理论
  • 语言设计
  • 类型系统
  • 程序逻辑
• 环境
  • 编译器
  • 运行系统
• 应用
  • 程序分析
  • 程序验证
  • 程序合成

语言类型

程序设计语言主要分为三类：

• 命令式语言
• 函数式语言
• 逻辑式（声明式）语言

在过去十多年中，程序设计语言的核心类型并未发生太多变化，但是语用环境出现了很大的差异。软件变得更加复杂，因此对大型复杂程序的可靠性和安全性的需求更加显著。这正是程序分析所关注和考察的领域。

静态分析的意义

1. 保证程序可靠性
   • 空指针、内存泄漏
2. 保证程序安全性
   • 私有信息泄漏、注入式攻击
3. 编译优化
   • 死代码消除、代码模式
4. 程序理解
   • IDE层次分析、类型指示
5. 提升编程能力
   • 更深入地理解编程语言的语法、语义
   • 自然地编写更加可靠、安全、高效的程序

什么是静态分析

静态分析 (static analysis) 是指在实际运行程序前对程序的行为和性质进行分析。

举例来说，静态分析可以考察的问题有：

• 是否有私有信息泄漏？
• 是否有空指针？
• 类型转换是否安全？
• 是否有共用内存的指针？
• 程序中的语句是否会失效？
• 是否有死代码？

静态分析的特性

莱斯定理

莱斯定理 (Rice's Theorem) 陈述了这样一个事实：递归可枚举语言的所有非平凡性质都是不可判定的。

进一步解释说明，递归可枚举 (recursive enumerable) 语言指的是可以被图灵机识别的语言；一个性质如果适用于所有的递归可枚举语言，或者不适用于任意一个递归可枚举语言，那么这个性质就是平凡的 (trivial)，否则为非平凡的 (nontrival) 。

可靠性与完全性

静态分析中考察的大部分性质都是非平凡的，这意味着一个完美的，即能够判断所有程序是否满足某一非平凡性质的静态分析方法是不存在的。因此我们不会试图得到一个完美的静态分析，而是希望得到一个可靠的 (sound)、完全的 (complete) 静态分析。下图很好的表明了完美的、可靠的、完全的之间的关系：

因此我们认为有用的 (useful) 的静态分析，必然是对可靠性或完全性作出了妥协，于是我们可以如下分类：

• 减少完全性：出现伪阳性 (false positives)，又称第一类错误，即误报增多
• 减少可靠性：出现伪阴性 (false negatives)，又称第二类错误，即漏报增多

在实际情况中，绝大多数静态分析都是减少完全性（即变得不那么精确）以提高可靠性。这是因为可靠性在应用中更加重要，我们可以接受对伪阳性的额外验证，但难以接受有错误未被检测出来。

有效的静态分析

在实际情况中，一个精确的静态分析往往需要花费更多的时间和空间，而不那么精确的静态分析则花费更少的时间和空间。考虑到这一点，我们可以对静态分析有更加深刻的认识：

有效的静态分析是在保证（或接近）可靠性的前提下，在分析的精度和速度间达成好的平衡。

静态分析的步骤

总的来说，静态分析分为两个步骤：

• 抽象
• 过近似

抽象

抽象 (abstraction) 是指将静态分析中对象的具体状态映射到性质的类型中。

举例来说，我们需要考察一个程序中每个整型变量的正负性。此时「对象的具体状态」即为每个变量具体的值，如 a = 1000、b = -1、c = 0、d = f ? 1 : -1、e = g / 0；而「性质的类型」有：正数 +、负数 -、零 0、未知 UK、未定义 UD。

显然，a、b、c、d、e 五个变量就可以顺次抽象到五种类型中。

过近似

转换函数

在静态分析中，转换函数 (transfer function) 是对于抽象值的函数，其是根据静态分析的目标和程序语句的语义 (semantics) 设计的。

沿用前例，根据一般的运算语义（即四则运算规则），可以定义这些转换函数：+ + + = +、- + - = -、0 + 0 = 0、+ + - = UK、+ / + = +、- / - = +、UK / 0 = UD……

因此在静态分析中，我们不会直接考察「对象的具体状态」，而是在完成抽象并定义转换函数后，考察「性质的类型」。而由于抽象这一步的不精确性，故转换函数是一种过近似的方法。

控制流

在程序中，一个对象可能会在不同控制流 (control flow) 中被修改。而在实际情况中，难以枚举所有的情况以确定对象在完整控制流下的真实状态，因此在静态分析中总是会将这些控制流在同一对象处合并。而这样的合并总是会丢失一些信息，因此也是一种过近似的方法。