针对结构化数据的安全搜索和模糊测试研究

摘要

随着大数据时代的到来，数据规模呈现爆炸式增长，结构化数据由于其易于存储，查询和分析的特性，成为大规模数据管理的主要数据形式。然而，结构化数据在安全协议设计和模糊测试等安全研究领域面临着新的问题和挑战。例如在安全协议设计时，不仅需要满足数据的安全性，同时要保持数据的结构特性以保证其高效处理的优势；在模糊测试中，传统的测试用例生成手段无法适应只接受结构化输入（具有特定语法结构）的程序，导致代码覆盖率过低，无法有效检测出安全漏洞。针对这些问题，我们展开了对结构化数据的安全研究工作，并取得了以下成果：
　　（1）提出一种能够支持结果排序和文件更新的安全多关键字搜索方案。在云计算场景中，用户出于隐私保护的考虑通常会在上传敏感数据前对其加密，这使得常用的数据搜索功能不再有效，引发了对安全搜索技术的研究。但是现有的安全搜索方案很少可以同时支持多关键字，结果排序和文件更新这三种功能。针对这一问题，我们提出一种支持结果排序和文件更新的安全多关键字搜索方案。方案中我们将向量空间模型与B+树结合构造了新型索引结构Keyword B+树，并采用函数隐藏加密方案对其加密，可以在保证数据安全和查询隐私的前提下对密文进行高效的搜索和更新，并可以将搜索结果按相关度进行排序。由于树状结构索引多分支的特性，使I/O效率得到提高，这一点非常适用于大规模云数据场景。我们对方案进行了全面的安全分析，可以证明我们的方案在允许有限信息泄露的条件下是自适应语义安全的，并能够更好地保护搜索模式。真实数据的实验结果表明本方案比现有方案的性能更好；
　　（2）提出一种对加密图数据的最短距离查询方案。由于很多大规模的网络数据可以建模为图，图数据库得到了广泛的应用；在云计算中，图数据库在外包之前也需要先被加密以保护用户隐私，这使得图中的查询问题变得富有挑战性。针对这一问题，我们提出了一种对加密图中的最短距离查询方案。在方案中，我们首先利用对称加密方法和矩阵索引相结合，实现了对最短距离高效准确查询的简单构造，但是存在预处理时间长以及索引空间过大的问题；针对这些问题，我们提出第二种方案，将部分同态加密方法和Distance Oracle索引相结合，可以实现近似最短距离的查询过程，缩短了预处理时间并减小了索引空间。最后证明了方案在允许有限信息泄露的条件下是自适应语义安全的，并通过实验展示了方案在索引构造时间和查询时间上的高效性；
　　（3）提出一种针对高结构化输入的模糊测试方法。传统的模糊测试方法无法处理具有高结构化输入的程序，测试用例会在程序验证阶段被丢弃。针对这一问题，我们提出一种新的基于语法的模糊测试方案。在方案中，我们通过把现有的测试用例分解为多个语法片段，并推导其语法结构，构造一系列新的测试用例，这些测试用例可以通过程序验证，到达在目标程序中未曾到过的位置。我们在通用的模糊测试框架中实现了这一方法。传统的基于语法的测试器只针对特定语言生成测试用例，与之相比，我们的设计不依赖于特定语言的语法，各种具体语言的模糊测试器都可以构建于我们的框架基础之上。实验表明，我们的测试框架与其它黑盒模糊测试工具相比，代码覆盖率更高。

目录

声明

插图索引

表格索引

缩略语对照表

第1章 绪论

1.2 研究现状

1.3 课题背景

1.4 本文的主要工作及结构安排

1.5 本章小结

第2章 基础知识

2.1 密码学工具

2.2 数据检索相关算法和数据结构

2.3 模糊测试的基本原理

2.4 本章小结

第3章 支持动态更新和排序的安全多关键字搜索方案

3.2 相关工作

3.3 问题描述

3.4 MKDRS的构造

3.5 正确性和安全性分析

3.6 性能分析

3.7 本章小结

第4章 具有隐私保护的图加密数据最短距离查询方案

4.2 相关工作

4.3 问题描述

4.4 SGSDQ的构造

4.5 性能分析与实验

4.6 本章小结

第5章 针对高度结构化输入的模糊测试

5.1 引言

5.2 相关工作

5.3 框架概述

5.4 测试用例的生成算法

5.5 测试框架的设计与实现

5.6 方案评估

5.7 类似工具比较

5.8 本章小结

第6章 总结与展望

6.2 下一步工作

参考文献

致谢

作者简介