angr原理与实践(二)—— 各类图的生成(CFG CG ACFG DDG等)

2023-05-16

本文系原创,转载请说明出处

Please Subscribe Wechat Official Account:信安科研人,获取更多的原创安全资讯

上一篇文章介绍了angr的原理,自此篇文章开始,将从一个个小实验的角度,讲述队angr的一些用法。

第二篇从(静态)程序分析必备的基础元素的角度出发,介绍一些图的生成与应用。

一 CFG(控制流图)与CG(调用图)


1.1 CFG控制流图:

概念:控制流图(control-flow graph)简称CFG,是计算机科学中的表示法,利用数学中图的表示方式,标示计算机程序执行过程中所经过的所有路径。控制流图是由法兰·艾伦所建立,他提出Reese T. Prosser(英语:Reese Prosser)曾利用邻接矩阵用在流分析上。

性质:

  • 节点基本块,内含程序语句;基本块概念基本块 - 维基百科,自由的百科全书 (wikipedia.org)
  • 边代表控制流,即如何执行

​特征:

  • 面向过程
  • 显示程序执行期间可以遍历的所有路径
  • 有向图

优点:

        可以轻松封装每个基本块的信息

        可以轻松找到程序中无法访问的代码,并且在控制流图中很容易找到循环等语法结构

缺点:

        只能表示控制依赖关系,数据依赖关系表示能力较弱

使用angr生成CFG的示例代码:

在第一篇文章中提到angr实现生成CFG的几种算法,方法按结果可以分为:CFGFast(), CFGEmulated。

使用流程一般为:

  1. 加载文件
  2. 调用图方法               

angr调用方法:

import angr
from angrutils import *

p = angr.Project(程序路径)

#使用快速生成方法生成CFG
cfg = p.analyses.CFGFast()

#使用完整生成方法生成CFG
cfg1 = p.analyses.CFGEmulated()

#调用angr-utils库可视化
plot_cfg(cfg1, "生成的cfg文件名", asminst=True, remove_imports=True, remove_path_terminator=True)  


示例:

 1.2 CG 调用图

概念:一种有向图,表示计算机程序中调用和调用子例程之间的关系,用于代码分析。每个节点表示一个过程,每个边 (f, g) 表示过程 f 调用过程 g

特点:

两种CG,一种是动态,一种是静态

静态:静态调用图是用于表示程序的每个可能运行的调用图。确切的静态调用图是一个不可判定的问题,因此静态调用图算法通常是过度的。也就是说,发生的每个调用关系都表示在图中,并且可能还有一些在程序的实际运行中永远不会发生的调用关系。

动态:动态调用图只描述程序的一次运行

代码示例:

angr里比较常见的是函数的CG,需要注意区分概念

p = angr.Project(文件路径)
cfg = p.analyses.CFGFast()
cg = cfg.functions.callgraph
#cg即是函数调用图

二 CDG和DDG (依赖图类,后续更新PDG、CPG)


依赖图一般是在CFG的基础上,按照特定的分析需求,构建特定的依赖图。常见的依赖图类包含CDG、DDG、CPG、PDG。angr按照自带的后向切片方法,在CFG上构建了生成CDG和DDG的方法,另外两种需要重构。

CDG(控制流依赖图)

概念:

人话定义:对于CFG中的两个节点X和Y,如果Y受X控制,即如果在程序执行过程中,X能直接影响Y是否执行

规范定义:

  • 对于一个有向图 G = < N , E >,节点n控制依赖于节点m,当且仅当:
  • 存在一条m到n的控制路径,n是该路径上除m之外每个节点的后支配节点,并且n不是m的后支配节点。

本文参考这边博文,即CDG由CFG和FDT(前向支配树构成),d支配(dominate)n,记为d dom n:每一条从流图的入口结点结点n的路径都经过结点d 。在这个定义下每个结点都支配它自己
如下图所示,左侧为流图,右侧为其对应的支配树

简单的来说如何划分,即如果现在这个节点只有一条入边,那么逆着入边往上看第一个节点直接控制现在这个节点,如2和3;如果现在这个节点有多条入边,逆着入边往上看,以一种合并的方式,找到这些入边往上合并的第一个节点,就是直接控制现在这个节点的节点。

又如如下例子:第一张图是程序示例和对应的CFG,第二张图是CDG和变量X的DDG

 应用:

死代码删除(DCE,Dead Code Elimination)和激进死代码删除(ADCE,Aggressive Dead Code Elimination)是编译中常见的优化pass。相较于DCE,ADCE会删除冗余的分支。

示例代码

import angr

b = angr.Project(文件路径)


cfg = b.analyses.CFGEmulated(keep_state=True, 
                           state_add_options=angr.sim_options.refs, 
                            context_sensitivity_level=2)

# 生成控制流依赖图
cdg = b.analyses.CDG(cfg)

DDG (数据依赖图)

定义:

  • 两个句子存在数据依赖:一条语句中一个变量的定义,可以到达另一条语句中对该变量的使用
  • 在编译领域有不同类型的数据依赖,如果s2依赖于s1,可以是:
    1. s1 写内存 s2 读 (RAW)
    2. s1 读内存 s2 写 (WAR)
    3. s1 写内存 s2 写 (WAW)
    4. s1 读内存 s2 读 (RAR)
  • 如果两个语句可能引用相同的内存位置和引用之一,则它们是数据相关的

代码示例:

import angr

b = angr.Project(文件路径)


cfg = b.analyses.CFGEmulated(keep_state=True, 
                           state_add_options=angr.sim_options.refs, 
                            context_sensitivity_level=2)


# 生成数据流依赖图
ddg = b.analyses.DDG(cfg)

ACFG 属性控制流图


在很多代码相似性检测的工作中,常常需要二进制程序的结构和语义信息,ACFG诞生于二进制程序漏洞检测的工作GENIUS中,其定义了ACFG属性控制流图,以获取二进制程序的基本块的内部特征,以及外部的结构特征,从而将其嵌入向量空间,使用机器学习按照代码相似性的技术,进行漏洞检测。

Scalable Graph-based Bug Search for Firmware Images | Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

定义:

一个有向图G = <V,E,α>,V为基本块集合,E是边集合,α代表基本块的特征标签集合,一般定义特征集合如下(参考此博文)

最后形成的ACFG如下:

代码示例:

首先导入库函数

import angr
import argparse
import os
import json
from angrutils import *

 接着,从基本块中获取指令的统计特征,指令的种类需要手工枚举,数量有限,问题不大:

def calc_ins(insns):
    """
    统计基本块中指令类型的数量
    参数insns为angr调用cfg中的基本块
    """
    transfer_ins = ['MOV', 'PUSH', 'POP', 'XCHG', 'IN', 'OUT', 'XLAT', 'LEA', 'LDS', 'LES', 'LAHF', 'SAHF', 'PUSHF','POPF']
    
    arithmetic_ins = ['ADD', 'SUB', 'MUL', 'DIV', 'XOR', 'INC', 'DEC', 'IMUL', 'IDIV','OR', 'NOT', 'SLL', 'SRL']
    
    calls_ins = ['CALL']

    num_transfer = 0
    num_arithmetic = 0
    num_calls = 0

    for ins in insns:
        ins_name = ins.insn_name()   #angr基本块中的block.capstone.insns.insn_name()方法

        if ins_name in transfer_ins:
            num_transfer = num_transfer + 1

        if ins_name in arithmetic_ins:
            num_arithmetic = num_arithmetic + 1

        if ins_name in calls_ins:
            num_calls = num_calls + 1

    return num_transfer, num_calls, num_arithmetic

然后,获取基本块的其他特征,如字符串常量的个数、数值常量的个数、指令总数:

def calc_block(block, num_str):
    """
    统计每个基本的特征
    """
    # 字符串常量个数初始化,通过传入外部的angr字符串个数计数方法
    num_string = num_str

    # 数字常量的个数
    num_numeric = len(block.vex.constants)

    # 指令的总数
    num_instructions = block.instructions

    # 指令集区分并计数
    num_transfer, num_calls, num_arithmetic = handle_ins(block.capstone.insns)

    # 基本块子节点个数
    num_offspring = 0

    return [num_string, num_numeric, num_transfer, num_calls, num_instructions, num_arithmetic, num_offspring]

接着,在定义好统计基本块内部的特征后,以一个函数为单位,统计基本块的外部结构特征,如连接的节点个数,子节点个数,使用邻接矩阵记录这些节点关系:

def calc_function(function, func_addr):
    """
    提取每个函数的特征
    """

    function_feature = dict() 
    function_feature["func_addr"] = func_addr       #函数的位置
    function_feature["function_name"] = function.name  #函数名
    function_feature["features"] = []     #函数内基本块的总特征
    function_feature["adj"] = []        #函数内的基本块结构

    try:
        # 函数中字符串常量的个数
        f_num_string = len(function.string_references())
        block_cnt = 0   

        # 提取函数内每个基本块的属性并统计基本块的个数
        for blk in function.blocks:
            function_feature["features"].append(calc_block(blk, f_num_string))
            block_cnt = block_cnt + 1
        function_feature["block"] = block_cnt

        # CFG图的节点数目为0时直接返回
        if 0 == len(function.graph):
            return

        # 将函数中的基本块结构图转为邻接矩阵
        matrix = nx.adjacency_matrix(function.graph).todense().tolist()
        
        for i, line in enumerate(matrix):
            # 当前节点到自己无边
            line[i] = 0
            num_offspring = line.count(1) #计算子节点个数

            function_feature["features"][i][-1] = num_offspring
            function_feature["adj"].append(line)


        
        print("*************************************")
        print(function_feature)

        
    except Exception as e:
        print("Exception->", e)

这里比较难理解的操作是邻接矩阵这块,把它打印出来看会更容易理解:

 上左图是一个函数的具体信息和邻接矩阵(最后一行),右图是可视化CFG后该函数对应的部分,可以看到0x4005a0基本块节点到本身无边,因此为0,到第二个0x4005a0和第三个0x4005b0都有边,所以,最后为[0,1,1];第二个[0,0,0]按顺序为0x4005b2基本块,可以看到,其到其他两个都没有指向边,因此全为0;最后一个同理。

所以,对于每个line,如下图,就是一个基本块的节点连接情况,计算line.count(1)就是计算子节点的个数

 最后,对每个文件进行方法调用即可:

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

angr原理与实践(二)—— 各类图的生成(CFG CG ACFG DDG等) 的相关文章

  • 手把手使用 Egg+TypeScript+mongoDB快速实现增删改查

    创建一个Egg的TS项目 xff08 Egg js官方教程 xff09 安装MogoDB Egg 依赖 span class token function npm span span class token function install
  • 小白学java——做一个歌手比赛系统(一)

    xfeff xfeff 完整代码加实验报告都在https download csdn net download qq 39980334 11232331 我已经设置成0积分下载了 xff0c 有需要的自行下载 xff0c 有问题的多看看代码
  • 使用尾插法创建链表并打印输出

    include lt stdio h gt include lt stdlib h gt include lt string h gt typedef struct LNode struct LNode next int data LNod
  • RabbitMQ 发展史与安装

    RabbitMQ 天降奇兵 解决的实例1 xff1a 统计用户的行为 xff0c 利用消息队列解耦模块和认证服务器 xff0c 认证模块被设计为 xff0c 在每一次请求页面的时候 xff0c 发送一条认证请求消息到rabbitmq xff
  • 小白学java------做一个歌手比赛系统(二)

    完整代码加实验报告都在 https download csdn net download qq 39980334 11232331 我已经设置成0积分下载了 xff0c 有需要的自行下载 xff0c 如果页面打不开可能还在审核中 xff08
  • 网络爬虫入门

    1 网络爬虫 网络爬虫 xff08 Web crawler xff09 xff0c 是一种按照一定的规则 xff0c 自动地抓取万维网信息的程序或者脚本 1 1 爬虫入门程序 1 1 1 环境准备 JDK1 8IntelliJ IDEAID
  • Java API入门篇

    文章目录 1 API1 1 API概述1 2 如何使用API帮助文档 2 String类2 1 String类概述2 2 String类的特点2 3 String类的构造方法2 4 创建字符串对象两种方式的区别2 5 字符串的比较2 5 1
  • Java异常篇

    文章目录 1 异常2 JVM默认处理异常的方式3 try catch方式处理异常4 Throwable成员方法5 编译时异常和运行时异常的区别6 throws方式处理异常7 throws和throw的区别8 自定义异常 1 异常 异常的概述
  • Java集合篇

    文章目录 1 Collection集合1 1 集合体系结构1 2 Collection集合概述和基本使用1 3 Collection集合的常用方法1 4 Collection集合的遍历1 5 集合使用步骤图解1 6 集合的案例 Collec
  • macOS下安装JDK11和配置环境变量

    1 下载 官网下载地址 华为云下载JDK11地址 tar包或者dmg xff0c 二者区别在于 xff1a tar你自己解压 xff0c 放在你想要的地方 xff08 配置JAVA HOME的时候是你自己选的位置 xff01 xff09 d
  • Java文件操作、IO流

    文章目录 1 File类1 1 File类概述和构造方法1 2 File类创建功能1 3 File类判断和获取功能1 4 File类删除功能 2 递归2 1 递归2 2 递归求阶乘2 3 递归遍历目录 3 IO流3 1 IO流概述和分类3
  • Java多线程

    文章目录 1 实现多线程1 1 进程和线程1 2 实现多线程方式一 xff1a 继承Thread类1 3 设置和获取线程名称1 4 线程优先级1 5 线程控制1 6 线程的生命周期1 7 实现多线程方式二 xff1a 实现Runnable接
  • Java编程思想(第4版)习题答案

    https span class token operator span span class token operator span span class token operator span greggordon span class
  • Bootstrap给表格设置宽度不起作用

    更改名称为table的class 将table layout属性设置为fixed span class token selector table span span class token punctuation span span cla
  • C++作用域运算符“::“的作用

    1 当存在具有相同名称的局部变量时 xff0c 要访问全局变量 include lt iostream gt using namespace std int x Global x int main int x 61 10 Local x c
  • HTML实现鼠标拖动元素排序

    1 简介 拖放 xff08 Drag和 drop xff09 是 HTML5 标准的组成部分 xff0c 为了使元素可拖动 xff0c 必须把 draggable 属性设置为 true xff0c 整个拖拽事件触发的顺序如下 xff1a d
  • MacOS安装svn客户端

    一 安装Homebrew环境 打开终端 输入以下命令 bin zsh c span class token string 34 span class token variable span class token variable span
  • MySql数据库root账户无法远程登陆解决办法

    最近换了新的腾讯云服务器后 xff0c 通过宝塔面板安装了mysql 数据库 xff0c 之后使用root用户通过navicat远程连接登录不了 解决办法如下 两行代码ok MySQL5 7和MySql8 开启root 用户远程访问 mys
  • MacOS修改Hosts文件

    1 苹果Mac电脑上 xff0c hosts文件的路径为 etc hosts xff0c 打开VI编辑 span class token function sudo span span class token function vim sp
  • ERD Online 4.0.0 免费私有部署方案

    文章目录 1 快速安装2 前置条件 3 一键安装 4 兼容性列表4 1 云主机兼容性列表4 2 虚拟机兼容性列表 1 快速安装 ERD Online的服务理念 xff1a 能喂到嘴里 xff0c 绝不递到手里 2 前置条件 一台至少配置为

随机推荐