软件构件与中间件 - 欢迎访问北京大学信息学院软工所 .ppt

关于代码 你有什么样的先验知识？ 如何形式化描述这些知识？ 如何使用这些知识查找缺陷？ 动态测试 离线运行程序 应用最广泛的缺陷查找技术 对功能性最有效 工作量大：微软（半数的测试人员？） 自动程度难以提高 基本分类 黑盒 白盒 静态缺陷查找 不运行程序(广义测试包含这类活动) 静态分析可以涉及更多的路径组合 测试一次只能有一个执行轨迹 可以分析多种属性 死琐？安全漏洞?性能属性? 源码？目标码？ 在线检测 当系统正在为用户提供服务时，一般不能进行测试：输入受限 但可以进行检测，获取各种状态、事件 进行分析，并可能据此调整目标系统 尽量减少对系统的应用 与静态分析结合？ 二、静态代码缺陷类别 与具体应用“无关” 词法或者语法 共性特性（死锁、空指针、内存泄露、数组越界） 公共库用法（顺序、参数、接口实现，容错，安全） 与具体应用“相关” 类型定义（操作格式，不含其它信息（信息隐藏）） 类型约束（调用的顺序、参数值，接口实现） 需求相关（正确） 如何得到这些知识？ 与具体应用无关 词法或者语法：语言设计人员 共性特性： 基础知识 公共库用法：库开发人员（形成文挡） 用户整理(分析实现代码、分析使用代码) 与具体应用相关 类型定义： 应用设计人员 类型约束： 应用设计人员、编程人员 需求相关： 用户 三、静态代码缺陷查找的主要方法 1、静态代码分析 2、编译过程中的代码缺陷查找 3、形式化分析方法 4、缺陷模式匹配 静态代码缺陷查找属于静态代码分析的范畴 静态代码分析是在不运行代码的前提下，获取关于程序信息的过程 静态代码分析还可以用于 获取设计结构 理解代码功能 演化代码 …… 给定一个程序，可以问许多问题： ? 对于某个输入，停机吗? ? 执行过程需要多少内存? ? 对于某个输入的输出是什么? ? 变量 x 被使用前是否已经初始化过了 ? 变量 x 的值将来被读取吗? ? 变量 x 的值是否一直大于0？ ? 变量 x 的值取值范围是多少？ ? 变量 x 的当前值是什么时候赋予的? ? 指针p会是空吗? Rice 定理 Rice’s 定理 (1953) 非正式地指出： 所有关于程序“行为”的问题是不可判定的(undecidable) 例如：能否判定如下变量 x 的值? x = 17; if (TM(j)) x = 18; 第 j 个图灵机的停机问题是不可判定的 x的值也就不能判定 2、编译过程中的代码缺陷查找 最基本的代码分析 词法分析 语法分析 抽象语法树 （AST） 类型检验 语义分析？ 变量赋值、调用操作、类型变换 等 程序设计语言中的类型 某些具有相同/相似特性实例的集合 值的集合？操作的集合？ 基本类型 整数、实数、枚举、字符、布尔 自定义 结构、抽象数据、面向对象 为什么要引入？便于理解？帮助人们发现错误！ 静态类型化语言 每个表达式在静态程序分析时都是确定的 强类型化语言 所有表达式的类型是一致的（可以在运行时检验） 3、形式化的软件分析方法 形式化软件分析是一种基于数学的“自动化”技术：给出一个特定行为的精确描述，该技术可以“准确地”对软件的语义进行推理 模型检测 基于“有限状态自动机”理论 从代码中抽取有限状态转换系统模型，用来表示目标系统的行为 适合检验“并发”等时序方面的特性 对于值域等类型的分析比较困难 状态爆炸 抽象解释 一种基于“格”理论的框架 许多形式化分析方法都可以被涵盖其中 主要适合 数据流分析（Data Flow Analysis） 尤其是对循环、递归等 主要思想是对代码进行“近似”，将不可判定问题进行模拟 定理证明(Theorem Proving) 演绎方法（Deductive Methods） 基于Floyd/Hoare 逻辑 用如下形式表示程序的状态{P} C {Q} C: 可执行代码 P: Pre-condition，执行前的状态属性 Q: Post-condition，执行后的状态属性 利用推理/证明机制解决 语句复合问题 符号执行 通过使用抽象的符号表示程序中变量的值来模拟程序的执行，克服了变量的值难以确定的问题 跟踪各路径上变量的可能取值，有可能发现细微的逻辑错误 程序较大时，可能的路径数目增长会很快。可以选取重要的路径进行分析 4、缺陷模式匹配 事先收集足够多的共性缺陷模式 用户仅输入待检测代码就可以 与”类型化”方法关系密切 比较实用 容易产生“误报” 四、缺陷查找工具 准确？ 漏报（False Negative, not Complete） 误报（False P