安全的布鲁姆过滤器和基于键值对的布鲁姆过滤器

摘要

布鲁姆过滤器(Bloom filter)是一种具有空间节俭、查询高效的数据结构。在无线传感网中，一种将信息加密传输的方式是，在传输的每一个节点中进行消息的加密和解密，频繁的加密和解密操作增加了传感节点的计算开销，让传感节点的寿命减少。使用布鲁姆过滤器可以降低传感节点在无线传感网中传输加密的消耗。同时随着IP地址数量的逐渐增多，基于IP地址的TCP的流量监控算法已经越来越受到关注，传统的基于键值对的流量监控算法也随着IP地址的增多而变得极具挑战性，基于布鲁姆过滤器的TCP状态查询算法也逐渐成为热点。因此，本论文围绕这两大问题，展开了深入的研究，本文的主要工作以及创新点如下:
　　针对无线传感网中信息的隐私保护问题，本文基于布鲁姆过滤器和同态加密函数设计了一种隐私保护的布鲁姆过滤器(Privacy Preservation Invertible Bloom Filter,PPIBF)，并设计该结构的插入，聚合，和展示算法。PPIBF结构的设计仅仅只在数据采集时进行加密，在中间传输节点不需要解密操作，因此节省了中间节点的计算开销，增加中间节点的寿命。最后通过安全性分析和实验分析表明PPIBF能将信息得到有效的保护，并且节省中间节点的计算开销。
　　针对TCP流量监控问题，本文设计了状态布鲁姆过滤器(stateBF)来存储所有TCP流的状态。基于状态布鲁姆过滤器的结构设计了状态布鲁姆过滤器的插入，删除，查找操作，使得该算法能够快速的进行TCP流状态的更新和查询操作。最后，使用网络上公开数的TCP流数据集以及自己采集的校园网TCP流数据集进行实验，实验显示相较于现有的两种基于布鲁姆过滤器的状态查询算法(sBF以及kBF)而言，状态布鲁姆过滤器有更小的假阳性和更小的假阴性，适合在大型网络中应用。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及研究意义

1．2 国内外研究现状

1．2．1 基于布鲁姆过滤器的矩阵索引键值存储

1．2．2 基于布鲁姆过滤器的P2P网节点交互

1．2．3 基于布鲁姆过滤器的资源路由

1．2．4 基于布鲁姆过滤器的无线网络中的数据聚合

1．2．5 基于布鲁姆过滤器的网络系统的同步

1．2．6 基于布鲁姆过滤器的多播系统的源地址路由

1．2．7 基于布鲁姆过滤器的TCP流量状态的监控

1．2．8 基于计数布鲁姆过滤器的几何布鲁姆过滤器

1．3 本文主要工作与论文组织结构

1．3．1 本文主要工作

1．3．2 论文组织结构

第2章 布鲁姆过滤器概述

2．1 查询算法简介

2．2 标准布鲁姆过滤器查询算法

2．2．1 标准布鲁姆过滤器的插入操作

2．2．2 标准布鲁姆过滤器的查询操作

2．2．3 标准布鲁姆过滤器的例子

2．2．4 标准布鲁姆过滤器查询算法的理论分析

2．2．5 标准布鲁姆过滤器的优化

2．3 布鲁姆过滤器的扩展

2．3．1 计数布鲁姆过滤器

2．3．2 可逆布鲁姆过滤器

2．4 小结

第3章 无线传感网中的隐私保护

3．1 引言

3．2 问题来源

3．3 PPIBF结构设计

3．3．1 PPIBF结构分析

3．3．2 同态加密函数

3．4 PPIBF算法设计

3．4．1 PPIBF插入操作

3．4．2 PPIBF聚合操作

3．4．3 PPIBF的展示(list)操作

3．5 安全性分析和仿真实验

3．5．1 安全性分析

3．5．2 计算开销

3．5．3 消息长度开销

3．5．4 加解密性能比较

3．6 小结

第4章 基于键值对的布鲁姆过滤器

4．1 引言

4．2 问题来源

4．3 stateBF结构设计

4．4 stateBF算法设计

4．4．1 插入操作

4．4．2 删除操作

4．4．3 stateBF查询操作

4．4．4 stateBF的更新操作

4．4．5 stateBF的例子

4．5 stateBF的分析

4．5．1 查询算法的验证

4．5．2 假阳性概率分析

4．5．3 假阴性概率分析

4．5．4 状态布鲁姆过滤器长度的最优化

4．5．5 查错能力

4．5．6 特征分析和比较

4．6 实验仿真

4．6．1 实验数据集来源

4．6．2 实验环境设置

4．6．3 实验结果和分析

4．7 小结

结论

参考文献

附录A 攻读学位期间所发表的学术论文

附录B 攻读学位期间所参与的科研活动

致谢