一、Programming Languages体系

静态程序分析是编程语言中应用层面下的一个细分领域，它是一个非常重要的核心内容。

  • 在理论部分，考虑的是如何设计一个语言的语法和语义，如何设计语言的类型系统等等问题。在过去十年中，语言核心几乎没有变化
  • 有了语言的语法、语义和类型系统之后，我们需要支撑语言的运行。因此，在环境部分，需要考虑如何为运行中的程序提供运行时环境——如何设计编译器，在运行时需要怎样的支持（如内存的分配管理）等等。语言承载环境处于一个缓慢提升的阶段，主要集中在硬件设备以及高性能编程优化方面
  • 变化最大的是程序分析，因为随着IT、云计算、软件SaaS的快速发展，软件的规模变得更大、结构更复杂、数量更多。如何确保系统的可靠性、安全性和其他承诺，如何自动合成一个程度，成为了一个日趋热门的研究和工程化领域

二、Static Analysis定义

Static analysis analyzes a program P to reason about its behaviors and determines whether it satisfies some properties before running P.

  • Does P contain any private information leaks?
  • Does P dereference any null pointers?
  • Are all the cast operations in P safe?
  • Can v1 and v2 in P point to the same memory location?
  • Will certain assert statements in P fail?
  • Is this piece of code in P dead (so that it could be eliminated)?
  • …

上图中的两种答案在静态分析语义中都是对的，他们分别代表了两种求解方式：

  • 分支穷举：耗时，但是精确
  • 符号执行：快速，但是不那么精确

Static Analysis: ensure (or get close to) soundness, while making good trade-offs between analysis precision and analysis speed.

Two Words to Conclude Static Analysis：

Static Analysis = Abstraction + Over-approximation

举一个具体的例子：通过静态分析，判断一段PHP代码是否能存在外部任意参数执行风险，即是否是Webshell。要完成这个静态分析过程，需要进行如下处理：

  • Abstraction
  • Over-approximation
    • Transfer functions
    • Control flows

原始代码如下：

<?php

    v1 = 1;

    v2 = 2;

    v3 = $_POST[1];

    v4 = $_POST[2];

    v5 = v3 == 1 ? v3 : 5;

    $$_POST[3] = $_POST[4];  // $_POST[4] = v6

    if(v3 == 1){

        eval(v5);

    }

    echo "hello world";

?>

我们先来看Abstraction抽象，

通俗地理解Abstraction抽象，就是将程序从原始的、高维的源代码空间，映射到一个抽象的、低维的符号空间。符号化后，后续的优化、分析、处理都会更加方便。

接下来看Over-approximation: Transfer Functions转化函数，

  • In static analysis, transfer functions define how to evaluate different program statements on abstract values.
  • Transfer functions are defined according to “analysis problem” and the “semantics” of different program statements.

转化函数定义了抽象符号的运算结果，需要注意的是，转换函数和具体的语义和待分析问题有关.

需要注意的是，因为在Abstraction抽象过程中进行了值域空间的降维抽象，所以在转换函数映射中，静态符号执行和动态实际实行的结果之间，是存在差异的，这是不可避免的。

接下来看Over-approximation: Control Flows控制流，

As it’s impossible to enumerate all paths in practice, flow merging (as a way of over-approximation) is taken for granted in most static analyses.

在静态分析中，分支流合并是常用的分支推断技术，提升了Soundness的同时，也导致Completeness的下降，从而导致了不可避免的误报问题。

三、Why we need Static Analysis

  • 近年来，程序复杂度越来越高，可靠性和安全性越来越难保证

    • Null pointer dereference, memory leak, etc.
    • 空指针引用与内存泄漏等：几乎每个程序编写者都被这两个问题所困扰过
  • 对程序可靠性、安全性进行分析
    • Private information leak, injection attack, etc.
    • 隐私信息泄漏：这一问题在移动应用中较为普遍
    • 注入攻击：这是网络安全中非常常见的议题
  • 为编译优化提供基础技术
    • Dead code elimination, code motion, etc.
    • 死代码消除：在编译器的机器无关优化环节，将不会对程序执行结果产生影响的代码（即死代码）删除。
    • 循环不变量的代码移动：在编译器的机器无关优化环节，在保证不影响程序执行结果的情况下，将循环中的特定语句移动到循环外，使得程序运行时执行的语句数减少。更为详细的解释可以参考StackOverFlow上的回答。
  • 程序理解（调用栈、自动补全等）
    • IDE call hierarchy, type indication, etc.
    • 为集成开发环境的功能提供帮助：当你使用VS/Idea/Clion/Eclipse/Android Studio等等IDE时，将鼠标悬停在代码上，IDE能够动态地分析并提示你所悬停对象的相关信息，背后使用的技术就是静态程序分析。
  • 更深入地理解编程语言的语法语义
  • 自然地写出更可靠、安全、高效的程序

四、Rice’s Theorem -- 静态分析的局限

Any non-trivial property of the behavior of programs in a r.e.(recursively enumerable) language is undecidable.”

non-trivial properties：

  • ~= interesting properties
  • ~= the properties related with run-time behaviors of programs

按照莱斯定律，「完美静态分析」有两个核心特征：

  • Sound（完全覆盖）
  • Complete（精确推断）

如果一段程序是“non-trivial”的，则不存在一个完美的静态分析程序，可以同时满足Sound和Complete特征。换到工业界的术语就是，误报和漏报无法同时达到100%。

在实际使用中，我们并不是追求「完美静态分析」，而是追求「有用的静态分析」，即满足如下两个核心特征：

  • Compromise soundness (false negatives，折中地漏报控制)
  • Compromise completeness (false positives，折中地误报控制)

在实际工业场景中，Soundness往往是优先追求的目标，我们以Webshell静态代码分析为例说明。

如果追求Sound的目标，在进行静态代码分析的时候，完整性/覆盖度/高检出往往是优先追求的目标。在另一方面，相对的误报就不可避免了。

五、静态程序分析与类似技术的对比

静态程序分析

  • 优点：

    • 在选定的精度下能够保证没有bug
  • 缺点：
    • 学术门槛相对高。目前已知国内高校公开的课程资料只有北京大学，南京大学，国防科大，吉林大学的，且通俗易懂的教材稀少。作为一门计算机专业的高年级选修课，入门和提高都较困难。

动态软件测试

  • 优点：

    • 在工程中被广泛应用，并且有效。实现简单，便于自动化。
  • 缺点：
    • 无法保证没有bug。 这是无法遍历所有可能的程序输入的必然结果。
    • 在当今的由多核与网络应用带来的并发环境下作用有限。 某个bug可能只在特定情况下发生，因而难以稳定地复现。

形式化语义验证

  • 优点：

    • 由于用数学的方法对程序做了抽象，能够保证没有bug。
  • 缺点：
    • 学术门槛较高，学习者必须有良好的数学基础才能入门。
    • 验证代价较高，一般来说非常重要的项目会使用这一方式保证程序质量。甚至在操作系统这样重要的软件中，也并不一定会使用。

南京大学 静态软件分析（static program analyzes）-- introduction 学习笔记的更多相关文章

  1. 《Linux内核分析》第七周学习笔记

    <Linux内核分析>第七周学习笔记 可执行程序的装载 郭垚 原创作品转载请注明出处 <Linux内核分析>MOOC课程http://mooc.study.163.com/co ...

  2. 《Linux内核分析》第六周学习笔记

    <Linux内核分析>第六周学习笔记 进程的描述和创建 郭垚 原创作品转载请注明出处 <Linux内核分析>MOOC课程http://mooc.study.163.com/co ...

  3. 《Linux内核分析》第三周学习笔记

    <Linux内核分析>第三周学习笔记 构造一个简单的Linux系统MenuOS 郭垚 原创作品转载请注明出处 <Linux内核分析>MOOC课程http://mooc.stud ...

  4. 《Linux内核分析》第八周学习笔记

    <Linux内核分析>第八周学习笔记 进程的切换和系统的一般执行过程 郭垚 原创作品转载请注明出处 <Linux内核分析>MOOC课程http://mooc.study.163 ...

  5. 《Linux内核分析》第五周学习笔记

    <Linux内核分析>第五周学习笔记 扒开系统调用的三层皮(下) 郭垚 原创作品转载请注明出处 <Linux内核分析>MOOC课程http://mooc.study.163.c ...

  6. 20179223《Linux内核原理与分析》第八周学习笔记

    视频学习 可执行文件是怎么得来的? .c汇编成汇编代码.asm,然后再汇编成目标码.o.然后在连接成可执行文件,然后加载到内存可执行了. 对hello.c文件预处理(cpp),预处理负责把includ ...

  7. 第十七篇:实例分析(1)--初探WDDM驱动学习笔记(八)

    第四篇(VidPN)中提到过MIRROR驱动. 在进入本篇的实际内容前, 带着好奇心, 想请教CSDN中的显卡驱动方面的大虾, 怎样才干把这个驱动玩起来, 这个驱动的作用是什么,等等, 敬请不吝赐教. ...

  8. 20179223《Linux内核原理与分析》第十一周学习笔记

    缓冲区溢出漏洞实验 一.实验简介 缓冲区溢出是指程序试图向缓冲区写入超出预分配固定长度数据的情况.这一漏洞可以被恶意用户利用来改变程序的流控制,甚至执行代码的任意片段.这一漏洞的出现是由于数据缓冲器和 ...

  9. 20179223《Linux内核原理与分析》第五周学习笔记

    视频内容知识学习 一.用户态.内核态和中断 1.内核态:处于高的执行级别下,代码可以执行特权指令,访问任意的物理地址,这时的CPU就对应内核态 2.用户态:处于低的执行级别下,代码只能在级别允许的特定 ...

  10. 20179223《Linux内核原理与分析》第十周学习笔记

    课本第17.19和20章内容学习 关于设备驱动和设备管理,Linux主要有四种内核成分 设备类型:在所有Unix系统中为了统一普通设备的操作所采用的分类. 模块:Linux内核中用于按需加载和卸载目标 ...

随机推荐

  1. Java、JVM模型

    程序计数器:记录当前线程的执行位置(便于CPU切换线程的时候执行) 虚拟机栈:Java方法,方法从调用到执行完成对应一个栈帧从虚拟机栈入栈到出栈的过程. 本地方法区:Native方法(C++) 方法区 ...

  2. Python使用MySQLdb报Library not loaded: libmysqlclient.18.dylib错误

    Library not loaded: libmysqlclient.18.dylib就是找不到这个文件,首先要确定是否有这个文件 可以使用find命令,确认位置后可以使用如下两种方法:1.制作软连接 ...

  3. X86架构与ARM架构比较（摘录自网络）

    引言 CPU是怎样运作的? CPU的运作与人脑的运作差不多.先谈一下人这个系统的工作方式.眼镜.耳朵.舌头.皮肤等等感觉器官接收到"触觉",把信息传给大脑,大脑把信息处理后,把处理 ...

  4. 我的c程序

    想写一个不同机器通信获取状态的c程序.遇到无数困难.断断续续了3.4周了,得到的结果仍然无法面世. 我想还是把其中遇到的所有困难写下来吧! 下面是结果 #include <stdlib.h> ...

  5. 声明replicated属性之后我编译不通过的问题

  6. Snippet: align a TextView around an image

    A few weeks ago I discovered the Spans on Android,after reading the wonderful post by Flavien Lauren ...

  7. Hadoop第7周练习—MapReduce进行数据查询和实现推简单荐系统

    1.1 1.2 :计算员工相关 2.1 内容 :求各个部门的总工资 :求各个部门的人数和平均工资 :求每个部门最早进入公司的员工姓名 :求各个城市的员工的总工资 :列出工资比上司高的员工姓名及其工资 ...

  8. php小写金额转大写

    public static function amountInWords($num) {         if (!is_numeric($num) || empty($num))           ...

  9. Windows socket之最简单的socket程序

    原文:Windows socket之最简单的socket程序 最简单的服务器的socket程序流程如下(面向连接的TCP连接 ): 1. WSAStartup(); 初始化网络库的使用. 2. soc ...

  10. 初识Hibernate之环境搭建

         相信所有做后端的程序员同行们,没有不知道Hibernate大名的.这是一个经典的轻量级Java EE持久层的解决方案,它使得我们程序员能以面向对象的思维操作传统的关系型数据库,这也是其存在的 ...