基于llvm的跳转基本块的划分之C语言【100012496】

# 基于llvm的跳转基本块的划分 ## 1.概述   本项目是我们与李子昂同学(2018302180162) 等人在信安大赛参加的作品《神经网络分析二进制控制流图的间接跳转》的一个子项目。本项目的主要内容是利用LLVM这一工具，去寻找C语言源代码中的跳转基本块，并找到跳转基本块之间的对应关系。 ## 2.LLVM相关技术的背景及现状   LLVM是伊利诺伊州大学的ChrisLattner在博士期间开发的一个编译器框架。其旨在优化以多种源程序语言编写的程序的编译时间、链接时间、运行时间以及空闲时间。其特点是支持多种源程序语言编译成为统一的LLVM IR从而进行统一的优化，在编译速度，中间代码占用空间和错误提示等方面比传统的GCC编译器做的更好。目前LLVM编译器已经成为美国苹果公司主流编译器，作为一个新生的编译器正在向GCC发起挑战，目前无论从科研角度还是实际用户，LLVM越来越被更多的开发者和用户所接受。   Clang编译器可以将多种编程语言的源代码进行编译，并生成LLVM特有的中间表示。这是LLVM开发的一款语言，应用于LLVM的中端处理，类似于汇编的虚拟指令集，旨在于帮助开发者分析程序和优化代码等。虽然LLVM中间表示属于低级表示的语言，但是通过指令组合可以支持高级语言的表示，再通过LLVM优化器Opt提供的Pass或者自行实现对应的程序分析的方法实现对程序的分析和转换。   Clang编译器可以将多种编程语言的源代码进行编译，并生成LLVM特有的中间表示。这是LLVM开发的一款语言，应用于LLVM的中端处理，类似于汇编的虚拟指令集，旨在于帮助开发者分析程序和优化代码等。虽然LLVM中间表示属于低级表示的语言，但是通过指令组合可以支持高级语言的表示，再通过LLVM优化器Opt提供的pass或者自行实现对应的程序分析的方法实现对程序的分析和转换。   LLVM中间表示是基于精简指令集计算机（RISC）和静态单赋值形式（SSAForm），并借鉴内存表示、二进制表示以及汇编指令。一个程序编译后，生成中间表示对应的模块（module）；一个程序包含多个函数，每个函数将生成中间表示对应的函数（function）；一个函数根据控制流可以划分成多个语句块，每个语句块将生成中间表示对应的基本块（basicblock）；一个语句块包含多条语句，每条语句将生成中间表示对应的一条或者多条指令。   LLVM常见的指令有二元指令、函数调用指令、比较指令、获取元素指针指令、phi指令以及终止指令等等。其中二元指令主要包含整数、浮点数四则运算以及逻辑运算的移位操作等运算操作；比较指令用于实现程序内的判断条件；获取元素指针指令用于读取数组或者结构体的地址操作；phi指令用于解决同一变量多分支情况下汇集于同一基本块时变量具体赋值，通过引入phi指令，保障中间表示的静态单赋值形式；终止指令为基本块的最后一条指令，通常用于表示基本块的跳转或者结束。   LLVM Pass是编译器中的一部分，能够对代码进行转化和优化。Pass就是“遍历一遍IR，可以同时对它做一些操作”的意思。翻译成中文应该叫“趟”。在实现上，LLVM的核心库中会给你一些Pass类去继承。你需要实现它的一些方法。最后使用LLVM的编译器会把它翻译得到的IR传入Pass里，给你遍历和修改。   LLVM Pass的用处： > 1. 插桩，在Pass遍历LLVM IR的同时，往里面插入新的代码。 > > 2. 机器无关的代码优化：IR在被翻译成机器码前会做一些机器无关的优化。但是不同的优化方法之间需要解耦，所以自然要各自遍历一遍IR，实现成了一个个LLVM Pass。最终，基于LLVM的编译器会在前端生成LLVMIR后调用一些LLVM Pass做机器无关优化，然后再调用LLVM后端生成目标平台代码。 > > 3. 静态分析：像VSCode的C/C++插件就会用LLVM Pass来分析代码，提示可能的错误(无用的变量、无法到达的代码等等)。 ## 3.跳转基本块相关应用分析   程序分析是对软件缺陷采用自动化工具进行分析，相对于程序测试的手动测试，采用这种方式可以提高查找软件缺陷的效率。根据分析方法不同可以分为程序静态分析和程序动态分析，它们各有优缺点。   程序动态分析目前使用较广，被广泛地用于程序漏洞挖掘方面。程序动态分析使用可执行文件作为输入，具体执行程序，通过有效的策略遍历执行程序的执行路径，发掘程序的缺陷。目前采用的方式有指令插桩、虚拟机模拟运行等方式。因为知道程序的变量值所以具有较低的误报率，但是不清楚程序内部具体结构，有一定的漏报。程序动态分析更加偏向于黑盒fuzz测试。   程序静态分析近些年在学术界和工业界研究较多，也有部分成熟的产品，包括Coverity Prevent， Klockwork k7等。程序静态分析不执行程序，而是通过对程序源代码或者经过源代码编译产生的中间代码进行分析，常用的分析方法包括：数据流分析、污点分析、符号执行和模型检测等方式。程序静态分析能够得到程序内部的数据流信息和控制流信息，分析结果具有较高的程序路径覆盖率和较低的漏报，但是某些变景的值只有在运行时冰确定，所以误报率比较高。程序静态分析更加偏向于白盒测试。   程序静态分析经过多年的发展，逐渐形成一个体系，根据采用的技术不同分为不同的发展方向，其中包括，控制流分析、数据流分析、符号执行、污点分析、模型检测、定理证明等方向。这里主要介绍控制流图分析：   计算机程序的本质是指令对数据进行操作，控制流分析是根据程序的指令对程序的执行路径进行分析。一般情况下，程序都不是按照指令顺序从开始执行到结束，程序之中而是存在一些控制结构包括：顺序结构、分支结构和循环结构。顺序结构中除了最后一条指令，不存在跳转和返回的指令，几条顺序结构的指令构成一个基本块；分支结构根据顺序结构最后一条指令将程序流转向另外一个基本块，分支结构连接一个前趋基本块和后继基本块，并有前趋指向后继；循环结构则是分支结构的一种特殊情况，在某些情况之下分支结构的会构成环结构，这样就产生循环结构。   由上述三种结构构成程序流图，顺序结构就是程序流图中的基本块，分支结构则构成程序流图中的有向边，循环结构则是程序流图中的环。控制流分支则是按照程序流图的结构对程序中的数据进行分析。   控制流分析一般采用深度优先遍历算法和广度优先遍历算法。因为程序分析是在前趋基本块分析完成之后，再对后继基本块进行分析，所以一般采用先序遍历的思想。在程序静态分析中，先序深度优先遍历算法采用栈的思想，在该基本块分析完成之后，对第一个后继基本块及其所有的后继基本块进行分析，在分析第二个以此类推。先序广度优先遍历算法采用队列的思想，首先分析第一个基本块，然后分析其所有后继基本块，然后分析这些基本块的后继基本块。无论是采用深度优先遍历算法，还是采用广度优先的遍历算法，都需要对控制流图中的循环有一定的处理方式，否