# Long Duration Flows detection based on Bloom Filter

**Repository Path**: lambyte/long-duration-flows-detection-based-on-bloom-filter

## Basic Information

- **Project Name**: Long Duration Flows detection based on Bloom Filter
- **Description**: 使用布隆过滤器实现长流检测（复现自论文《Detecting Long Duration Flows without False Negatives》）
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-11-17
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Simple Long Duration Flows Detection

复现论文[《Detecting Long Duration Flows without False Negatives》](https://search.ieice.org/bin/pdf_link.php?category=B&lang=E&year=2011&fname=e94-b_5_1460&abst=)。



## 环境与依赖

### 环境

Window 10

### 依赖

Python 3.8.5

- [dpkt](https://dpkt.readthedocs.io/en/latest/)
- [tqdm](https://github.com/tqdm/tqdm)
- [bloompy](https://github.com/01ly/bloompy)



## 快速开始

### 配置 

`config.py` 为项目配置文件，各字段含义如下

| 名称                      | 含义                                                         |
| ------------------------- | ------------------------------------------------------------ |
| error_rate                | 布隆过滤器发生错误的错误率上限（判断某个元素存在，实际上不存在） |
| element_num               | 可以存储元素的个数上限                                       |
| PCAP_FILE_PATH            | 离线流量文件路径                                             |
| measurement_period_length | 一个测量周期的时长（秒）                                     |
| measurement_times         | 测量次数                                                     |
| result_file_path          | 结果文件输出路径                                             |

注意：

- pcap 文件中流量应为 IP 层及 IP 层以上的数据，即默认 pcap 文件中不包含 MAC 层数据。
- 长流阈值 = `measurement_period_length` * `measurement_times`，即假设测量时长为 50 秒，测量次数为 6 次，那么检出的长流被认为是大于 50 * 6 = 300 秒的。

## 运行

```shell
python detect-LDF.py
```



## 论文解读

该文提出了一种轻量的长流（Long Duration Flow，LDF）检测算法。长流是指在网络中周期性出现、持续时间较长的流量，流的总数据量可能不大。该文作者说其方法不存在有长流没有被检出的情况。

**长流定义**：一个流是长流，当且仅当其在每次测量时都至少出现一次，且总的测量次数超过预定义的阈值 θ。

**流 ID**：通常使用 (src_IP, dst_IP, src_port, dst_port, portocol) 五元组作为 ID，该文为了方便仅使用源 IP 地址作为流 ID。

### 基础知识

#### 布隆过滤器

[布隆过滤器](https://en.wikipedia.org/wiki/Bloom_filter)是一个包含 $m$ 位的数组。此外，还有 $k$ 个不同的哈希函数，每一个哈希函数都可以将元素映射到布隆过滤器 $m$ 位中的其中一个位置，位置服从均匀随机分布。

**增加元素**，需要将元素代入 $k$ 个哈希函数作哈希运算，得到 $k$ 个对应的数组的位置，并将该位置**置 1 **。

**查询元素**是否存在于集合中时，将元素代入 $k$ 个哈希函数作哈希运算，得到 $k$ 个对应的数组的位置，如果这些位置中有 0 ，则元素必定不存在于集合中；如果这些位置全部为 1 ，则有两种可能：(1) 元素存在于集合中；(2) 元素不存在于集合中，对应位置上的 1 是插入其他元素造成的结果。

由此可见，若布隆过滤器判断一个元素不存在于集合中，那么判断一定是正确的，但若判断一个元素存在于集合中，有一定概率的误判（Flase Positive）。此外，简单布隆过滤器无法删除元素。

**近似误报率**：
$$
\epsilon = (1-e^{\frac{-kn}{m}})^{k}
$$


其中， $\epsilon$ 为误报率，$k$ 为哈希函数个数（假设各哈希函数之间无显著相关性）， $n$ 为插入元素个数， $m$ 为布隆过滤器比特数。可以看出，布隆过滤器比特数 $m$ 的增加会使误报率的降低，但插入元素的个数 $n$ 的增加会导致误报率会上升。

**最佳哈希函数个数**：
$$
k = \frac{m}{n}\ln2
$$


#### 计数布隆过滤器

[计数布隆过滤器](https://en.wikipedia.org/wiki/Counting_Bloom_filter)是布隆过滤器的一种推广，不同之处在于原来的 $m$ 个比特位变成了 $m$ 个计数器。

**增加元素**，需要将元素代入 $k$ 个哈希函数作哈希运算，得到 $k$ 个对应的数组的位置，并将该位置**加 1 **。

**查询元素**是否小于阈值 $\theta$ 时，将元素代入 $k$ 个哈希函数作哈希运算，得到 $k$ 个对应的数组的位置，如果这些位置上计数器值中有小于 $\theta$ 的，则元素被定义为小于 $\theta$ ；如果这些位置上的计数器的值全部大于等于 $\theta$ ，则元素被定义为大于等于 $\theta$ 。



**近似误报率**、**最佳哈希函数个数**：

参考：https://www.mdpi.com/2079-9292/8/7/779

###  算法描述

#### 符号表

| 符号    | 意义                                                       |
| ------- | ---------------------------------------------------------- |
| $d$     | 测量周期大小                                               |
| $θ$     | 测量次数                                                   |
| $B[i]$  | 布隆过滤器（Bloom filter）中的第 $i$ 个位                  |
| $C[i]$  | 计数布隆过滤器（counting Bloom filter）中的第 $i$ 个计数器 |
| $H_{i}$ | 布隆过滤器中的第 i 个 hash 函数                            |
| $m$     | $B$ 和 $C$ 的大小                                          |

#### 算法

1. 将时间轴分为长度为 $d$ 的多个测量周期
2. 在每个测量周期开始，将 $B[i]$ 初始化为 0 （$0 \leq i \leq m-1$）
3. 在测量周期期间，对于流 $x$，计算 $k$ 个 hash 函数对应的结果（$i=H_{j}(x), 1 \leq j \leq k$）。如果 $B[i] + C[i] \geq \theta$ ，那么这个流就是长流
4. 在测量周期结束，如果 $B[i]=1$ 那么将相应的 $C[i]$ 加 1 ，否则将 $C[i]$ 置零



## 数据集及数据文件说明 

### seu_tcp.pcap

描述：东南大学校园网某一个网段 30 分钟的流量抓包。绝大多数数据包 IP 层以上的数据包，包含 TCP 流量。

来源："/data/zdhua/20200816/seu_tcp.pcap"

### seu_tcp.txt

描述：东南大学校园网某一个网段 30 分钟的流量抓包统计方法解析结果（标签）。

来源："/data/zdhua/20200816/seu_tcp.txt"

其中的一条记录的形式为：

> 1973840340 26415 985691779 80 6 1597538322 1597538638 316

各个字段对应含义为：

src_IP, src_port, dst_IP, dst_port, protocol, start_time, end_time, duration



## 结果

### 长流的阈值：300s  测量周期：30s

| 指标                 | 值                 |
| -------------------- | ------------------ |
| 标注长流个数         | 4027               |
| 论文方法检出长流个数 | 386                |
| Precision            | 0.8782383419689119 |
| Recall               | 0.0841817730320337 |

### 长流的阈值：300s  测量周期：60s

| 指标                 | 值                 |
| -------------------- | ------------------ |
| 标注长流个数         | 4027               |
| 论文方法检出长流个数 | 4121               |
| Precision            | 0.7270080077651055 |
| Recall               | 0.7439781475043457 |

### 长流的阈值：300s  测量周期：50s

| 指标                 | 值                 |
| -------------------- | ------------------ |
| 标注长流个数         | 4027               |
| 论文方法检出长流个数 | 3712               |
| Precision            | 0.7588900862068966 |
| Recall               | 0.6995281847529178 |



# 其他

### 截取 pcap 文件

原始 pcap 文件很大（> 1 GB），不方便进行测试分析，可以使用 tcpdump 进行截取：

```
tcpdump -r /path/to/input_file -c NUM -w /path/to/output_file
```

例如，要截取`./project/data/seu_tcp.pcap`中的前 1000 个报文，可以运行下面的命令：

```
tcpdump -r ./project/data/seu_tcp.pcap -c 1000 -w ./project/data/seu_tcp_1000.pcap
```

参考：[tcpdump 手册](https://www.tcpdump.org/manpages/tcpdump.1.html)