基于访问模式保护的空间数据安全系统的制作方法

基于访问模式保护的空间数据安全系统的制作方法
【技术领域】
[0001] 本发明涉及的是一种信息安全领域的技术，具体是一种基于访问模式保护的空间 数据安全系统。
【背景技术】
[0002] 自从诞生以来，数据安全问题就一直是云存储服务所面临的最重大的挑战之一。 因为数据存储于云端，并且通过网络进行存取，所以难免会遭到攻击者的利用。尽管数据的 内容本身可以进行加密，但是攻击者仍然能够从用户的访问模式中得到有用的信息。如何 设计一种合理的结构，尽量减小云存储中的信息泄露，把受到攻击的风险降到最低，一直是 一个重要的课题。在这个领域，目前比较有代表性的工作如下：
[0003]Goldreich等人最早研宄了如何隐藏访问模式以避免消息泄露的问题。他们的想 法是使用一个带有密钥的物理隔离的CPU来处理指令。CPU接收加密指令，并且使用它的内 部寄存器将其解密。他们最初设计了一种"平方根"方案，来将主存划分为主存储空间和保 护空间。这种方案虽然简单，但是性能并不理想。随后他们又提出了将保护空间结构化的 思路。Pinkas等人在其基础上进行了改进，使其性能得到了进一步的提升。Boneh等人提 出了遗忘存储（ObliviousStorage)的方案，在性能上又有了进一步的提升。然而这些解决 方案都只针对一维的数据，对于二维以上的数据并没有很好的办法。
[0004] 另一方面，空间数据对象是地理位置查询中常见的对象。它通常出现在多维（例 如二维）空间中，仅仅用点是不能很好地描述的。对于空间对象，例如城市，街道等等，在二 维空间中都不能用一个孤立点来简单描述。而在数据对象的使用上，范围查询是一个很常 见的操作。例如，想要找到一个用户所在位置附近5公里内的街道。如何根据他们的空间 位置快速有效地返回相应的数据对象是非常重要的。
[0005]R-tree是由伯克利大学的AntomnGuttman等人在1984年最先提出的一种针对多 维数据的动态索引结构，是目前使用最为广泛的多维数据索引结构之一。它采用一种类似 于B+树的结构来存储多维数据，使得用户可以进行快速的查询和修改。WangPeng等人在其 基础上，结合非对称标量积保存加密（ASPE)，进一步提出了rhat-trees，用于在加密的情 况下向服务器进行查询操作。尽管如此，以上方法对于如何应对由访问模式猜测用户信息 的攻击者都没有很好的解决方案。

【发明内容】

[0006] 本发明针对现有技术存在的上述不足，提出一种基于访问模式保护的空间数据安 全系统，在保证查询效率的同时，不但实现数据的加密，同时对数据的访问模式也进行隐藏 和保护，从而大大降低信息泄漏的风险。
[0007] 本发明是通过以下技术方案实现的：
[0008] 本发明涉及一种基于访问模式保护的空间数据安全系统，包括：服务端和与之相 连的用户端，其中：用户端向服务端发出数据项查询指令，并接收服务端反馈的数据查询结 果；
[0009] 用户端包括：地址翻译单元、置乱处理单元和执行单元，其中：地址翻译单元根据 用户指令翻译得到查询请求，通过执行单元发送至向服务端进行查询；
[0010] 服务端包括：数据存储单元和查询请求响应单元，其中：数据存储单元与硬盘或 数据库相连并存储数据信息，其中包括用户的数据以及用于加密算法的隐藏存储区。查询 请求响应单元与数据存储相连，响应用户端的查询请求并传输数据信息。
[0011] 所述的地址翻译单元中包含一个动态索引结构R-tree，将其命名为R;
[0012] 所述的执行单元中包含一个层级列表L，该层级列表L中存储着服务器上隐蔽存 储区的结构信息；当收到地址翻译模块的请求后，执行端向服务器执行查询请求，并将得 到结果并返回给用户；为了数据安全考虑，当系统开始运行的时候，必须输入一个密钥SK， SK| =k，用于数据加密。
[0013] 所述的置乱处理单元包括：局部置乱处理模块、移层操作模块、全局置乱处理模块 和并发置乱模块，其中：局部置乱处理模块负责进行隐藏存储区中某个层级内部或是主存 储区内部的置乱操作，移层操作模块负责进行隐藏存储区中不同层级之间的置乱操作，全 局置乱处理模块负责进行隐藏存储区和主存储区之间的置乱操作，并发置乱模块负责保证 用户在置乱处理的过程中仍然能对数据进行正常访问。 技术效果
[0014] 与现有技术相比，本发明的技术效果包括：
[0015] 首先，在服务器端采用了简单的一维id，使得服务器上不需要存储复杂的多位数 据，从而使得服务器数据结构的复杂度大大降低。
[0016] 其次，避免将地址信息a直接存储在服务器，可以避免泄密的风险。潜在的攻击者 只能获取到一维id的信息，而无法获知用户查询的真实范围。
[0017] 此外，本方法当服务器的存储空间M固定时，用户端的存储空间m越大，算法的运 行速度越快。实验结果表明，在保证数据安全的前提下，对二维空间数据的处理速度达到了 接近一维速度的效果。
【附图说明】
[0018] 图1为本发明系统结构示意图；
[0019] 图2为实施例中动态索引结构R-tree规模测试效果示意图；
[0020] 图3为实施例执行时间效果示意图；
[0021] 图4为实施例中置乱等待时长示意图；
[0022] 图5为实施例系统结构示意图；
[0023] 图6为实施例置乱处理示意图。
【具体实施方式】
[0024] 下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下进行 实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施 例。
[0025] 以下实施例的应用环境包括：
[0026] 服务器端S，包括：局部置乱处理模块、移层操作模块、全局置乱处理模块和并发 置乱模块，其中：局部置乱处理模块负责进行隐藏存储区中某个层级内部或是主存储区内 部的置乱操作，移层操作模块负责进行隐藏存储区中不同层级之间的置乱操作，全局置乱 处理模块负责进行隐藏存储区和主存储区之间的置乱操作，并发置乱模块负责保证用户在 置乱处理的过程中仍然能对数据进行正常访问。
[0027] 该服务器端S上的数据形式为（v，b)，其中：v表示数据标识（id)，b表示数据内 容；
[0028] 所述的用户端包括：地址翻译单元和执行单元，其中：地址翻译单元根据用户指 令翻译得到查询请求，通过执行单元发送至向服务端进行查询；
[0029] 所述的服务器端S响应以下指令：
[0030] 数据项查询指令Get(v):当id为v的项存在于服务器端S，则返回（v，b)，否则返 回空值。
[0031] 数据项更新指令Put(v):服务器端S将（v，b)加入到存储空间中，且当v已经存 在时覆盖原数据。
[0032] 数据项批量查询指令GetRange(vl，v2):服务器端S返回所有满足vl<v<v2 的（v,b)值。
[0033] 数据项批量删除指令DelRange(Vl，v2):服务器端S删除所有满足vl<v彡v2 的（V，b)值。
[0034] 所述的用户端C响应以下指令：
[0035] 数据获取指令Get_o(a):获取范围a内的所有数据。
[0036] 数据更新指令Put_o(a，b):将范围a内的数据覆盖为b。
[0037] 其中：a=(屯，d2-)为查询的范围，扎七…分别代表不同维度内的范围信息。例 如，对于二维的地理坐标，屯和(1 2分别表示经度和炜度的范围。
[0038] 所述的用户U向用户端C发送Get_o(a)或是Put_o(a，b)的指令，且只有在接到 前一条指令的结果之后，U才会发送下一条指令。
[0039] 所述的地址翻译模块中包含一个动态索引结构R-tree，将其命名为R。当接到用 户的请求时，地址翻译模块负责将形如（a，b)的数据转换为形如（v，b)的数据，S卩：将a转 换为V。
[0040] 与传统数据结构不同，地址翻译模块中的R-tree的叶子节点不需要存储节点的 具体信息b，取而代之的是存储这条信息在服务器上对应的idv，即地址翻译模块中的R-tree存储的是（a，v)的信息。这样就大大减小了R-tree的体积，使得可以将存储了所有 节点信息的整个R_tree都放置在用户端C。
[0041] 当地址翻译模块收到获取范围a内的所有数据的指令Get_o(a)时，在R中寻找a 范围内的节点，令结果为v，v= (VpVf)。对于每一个vnGv，发送一个Get(v)请求到执 行端。收到结果后，将结果输出给用户。
[0042] 当地址翻译模块收到将范围a内的数据覆盖为b的指令Put_o(a,b)时，在R中寻 找a范围内的节点，令结果为v，v=(Vpv2~）。对于每一个vnGv，发送一个Put(V，b)请 求到执行端。收到结果后，将结果输出给用户。
[0043] 所述的执行端中包含一个层级列表L，该层级列表L中存储着服务器上隐蔽存储 区的结构信息。当收到地址翻译模块的请求后，执行端向服务器执行查询请求，并将得到结 果并返回给用户。为了数据安全考虑，当系统开始运行的时候，必须输入一个密钥SK，|SK| =k，用于数据加密。
[0044] 置乱函数PRPsS-个定长伪随机置换，对应服务器端S上所有包括主存储区以及 隐蔽存储区的数据的id，都用该PRPS进行加密。 实施例1
[0045] 如图4所示，本实施例中，当用户端C从服务器端S获取一个id的时候，要对其进 行解密，并在用户端返回服务器数据时进行重加密，具体为：
[0046] 步骤1、执行端判断v是否存在于层级列表L中
[0047] 步骤2、当v存在于L中时：
[0048] 2. 1)对于L中的每一层，用户端C向服务器端S发出一个数据项查询指令 Cet(P/?Ps?))?以获取一个伪装数据编号对应的数据值，并在接收到后忽略该数据 值。
[0049] 2. 2)向服务器发送数据项查询指令Get(PRPS (v))，并在接收到服务器端S返回的 结果b。
[0050] 2. 3)执行加密传输处理shelterlnsert(V，b)。
[0051] 2. 4)将decryptSK(b)作为结果返回给用户。
[0052] 步骤3、当v不存在于L中时：
[0053] 3. 1)设1为L中id为v的项目所在的层中最高的一层。
[0054] 3. 2)对于L中的每一个i辛1的层，用户端向服务器端发出一个种))的 请求，以获取一个伪装数据。接收并忽略该数据；发送，设b为服务器返回的结 果。
[0055] 3.3)向服务器端S发送一个数据项查询指令Get(PRPs(d))以获取一个伪装数据 编号对应的数据值，并在接收到后忽略该数据值。
[0056] 3. 4)执行加密传输处理shelterlnsert(V，b)。
[0057] 3. 5)将decryptSK(b)作为结果返回给用户。
[0058] 所述的加密传输处理shelterlnsert(V，b)，包括以下步骤：
[0059]i? 对数据值进行更新，具体为b=encryptSK(decryptSK(b))
[0060] ii.向服务器端S发送数据项更新指令Put(PRPsl (v)，b)
[0061] iii.当服务器端S的层级列表L的某一层的存储空间已被写满，执行移层操作 shuffleLevel()将该层中的数据转移到下一层，重复该步骤直至没有一层满为止，当最底 层满时，则服务器端S进行全局置乱处理shuffleMainPart()。
[0062] 当接收到一个请求的同时，执行端同时向服务器的隐藏存储区的每一层以及主存 储区都发送一个请求，并且只留下需要的结果，其他结果都被直接忽略。这样攻击者就无法 分辨宄竟哪一个才是用户真正想要查询的数据对，从而大大降低了攻击者通过访问模式来 猜测用户信息的风险。当用户对一条数据执行了数据项查询指令或数据项更新指令后，这 条数据就被加入到隐藏存储区中。
[0063] 如图5所示，所述的移层操作shuffleLevel()是指：将隐蔽存储区中一个等级i 的层中的数据转移到等级i+1的层中，具体步骤包括：
[0064] -、使用局部置乱处理shuffle()来置乱第i层数据。
[0065] 二、使用局部置乱处理shuffle()来置乱第i+1层数据。
[0066] 三、将第i层中不是假数据的数据对写入到第i+1层中。当一个第i层中的数据 对的id同时存在于第i+1层的数据对中，则将第i+1层中的数据对覆盖，否则将它们写入 到原本的假数据的位置。
[0067] 四、将第i层的所有数据删除。
[0068] 五、使用局部置乱处理shuffle()来置乱第i+1层数据。
[0069] 当整个结构的最后一层也满了之后，用户端C使用全局置乱处理 shuffleMainPart()来将最后一层合并到主存储区。
[0070] 所述的全局置乱处理shuffleMainPart()是指：将服务器端隐蔽存储区中底层的 数据合并到主存储区中，并且将合并后的主存储区进行置乱操作，具体包括以下步骤： [0071]I)在服务器端创建一个新的结构化的隐藏存储区，内容为空，称为同步隐藏存储 区。
[0072] II)生成一个当前服务器上隐藏存储区的副本，称为隐藏存储区副本。
[0073] III)使用局部置乱处理shuffleO置乱服务器的主存储区。
[0074] IV)使用局部置乱处理shuffleO置乱原本的隐藏存储区。
[0075] V)将隐藏存储区里的数据都更新到主存储区里。当这条数据是伪装数据，那么也 用它更新主存储区的伪装数据。
[0076]VI)使用局部置乱处理shuffleO置乱服务器的主存储区。
[0077] VII)删除隐藏存储区副本和原本的隐藏存储区。同步隐藏存储区成为新的隐藏存 储区。
[0078] 所述的局部置乱处理shuffleO是指：将服务器上某个部分的数据置乱，将他们 的id用相同的PRP算法进行变更，具体步骤包括：
[0079]1.将服务器端S上的存储空间按逻辑分为大小为0(m)的数个数据块并标记为i =1，2…#C，其中：#C= 0(MB/m)
[0080] 2.通过数据项批量查询指令GetRange依次获得每个数据块的值，然后使用数据 项批量删除指令DelRange依次从服务器上删除该数据块，并在该数据块的每个id前面加 上"i: "的前缀，然后通过数据项更新指令Put将该添加过前缀的数据块放回服务器端S上。
[0081] 3.添加完前缀后，对所有数据块进行以下遍历操作：
[0082] 3. 1)把数据块按照以下规则组成逻辑对：当块j没有被组对过，那么将它和块f 组队，其中：_f=j+21
[0083] 3.2)采用置乱函数PRPi置乱每一个数据块对，然后使用数据项批量查询指令 GetRange(j:0. . 0,j:9. . 9)和GetRangeU^O. . 0, _f:9. . 9)将数据块复制到用户端，并使用 数据项批量删除指令DelRange将对应的数据块对从服务器端S上删除，然后对每个id，令 i= 重新加密数据块，将数据块对按照新的id重新排列。在数据块对的前 半部分加上前缀"j: "，后半部分加上前缀"_f: "。使用数据项更新指令Put命令将他们都 传输到服务器上。
[0084] 3.3)在置乱索引中添加"ITi"的项目，记录这个步骤中被置乱过的数据对的信 息。
[0085] 4.置乱结束后，将步骤1和2中添加在服务器端S上所有的数据id前的前缀（i: 和j:)去掉，并将用户端C的置乱索引删除。
[0086] 上述过程用户端共发出 0((MB/m)log(MB/m))次请求，Get/PutO(Mlog(MB/m))个 数据对。
[0087] 这些置乱操作会随着用户的操作不断发生。当一个置乱操作正在发生的时候，用 户就无法继续进行查询操作了。这对于整个系统的操作体验是有很大影响。
[0088] 为了保证在对服务器的数据进行置乱操作的同时，用户端可以对服务器进行访 问，采用以下方法：
[0089] A.在置乱的时候，用户端C生成一个置乱索引，用于保存置乱目录的数据结构，来 保存一个id被置乱后的变化，这样用户端就可以从一个正在进行置乱的存储结构中准确 而有效地找到数据。
[0090] B.用户端C生成一个同步隐藏存储区，并将置乱期间所有的数据访问请求都会被 存储在里面，以防止被置乱的部分被重复访问。
[0091] C.用户端C在一次置乱期间只允许一定数量的查询请求，把过多的请求延迟或是 拒绝掉，以保证在一次置乱没有结束之前不会马上开始另一次置乱。
[0092] 实施效果：
[0093] 利用随机生成的数据进行了实验。实验主机的配置如下：内存8G，CPU主频 3.4GHz。的实验数据是二维数据，每个数据块的大小为4096,其中：前32位是坐标信息，其 余部分为数据块内容。坐标信息包含两个维度。生成的数据规模如表1所示。
[0094] 一共生成了三组实验数据，数据的条数M分别是16384条、65536条和262144条。 服务器端的数据的总大小MB分别约为64MB、256MB和1GB。用户端的大小为m= _，即 8KB、16KB、32KB。
[0095] 表1实验数据规模
[0096] 为了测试用户端的R-tree的性能，分别对三组数据进行了R-tree建模，用 LC(LeafCapacity)代表一个R-tree节点能承受的最大子节点数量。对三组数据分别进行 了测试，使用的LeafCapacity值取值和得到的R-tree大小如下：
[0097] 表2R-tree规模测试
[0098] 从图1和表格3的结果可以看到，R
-tree的规模足够小，可以存储在用户端。随 着LeafCapacity的增大，R-tree的规模也会随之减小，但是减小的速度会逐渐下降直至 停止。出于性能方面的考虑，在接下来的实验中将LeafCapacity选择为400。
[0099] 共进行了三组实验，每组进行的查询操作分别是10000次、50000次和100000次， 各做10次，取平均值。实验结果如图2:
[0100] 因为本地检索的速度非常快，和通信所花费的时间相比可以忽略，所以在整个系 统中，服务器端和用户端的通信是性能瓶颈。用户端存储的数据容量为BVM，在不考虑置乱 的情况下，每次查询请求需要的get/put次数为O(logM)。在考虑了置乱的情况下，需要的 次数则为〇〔flogMSM旦是从实验结果看，和理论数值却存在一定的偏差。原因在于，当服 务器正在进行一次置乱操作的时候，是禁止进行新的置乱操作进行的。当置乱期间用户的 请求数超过了 一定的数量时，新的请求就会被延迟。
[0101] 为了证明这个结论，统计了置乱操作期间Get/Put的I/O次数以及系统的置乱等 待时间（即从一个请求被延迟开始到置乱结束这个请求开始执行之间的时间的叠加）。次 数结果如表3,等待时间结果如图3 :
[0102] 表3置乱操作Get/Put的I/O次数
[0103] 表3的结果验证了算法的理论速度。同时也表明，当MB/m= ，系统的性能能够 达到最优。从图3的实验结果也表明，随着数据量的增加，置乱等待的时间是逐渐上升的。 这是由两方面的因素共同造成的。一方面，如同表3的结果所示，随着数据量的增加，一次 置乱需要的访问量也大大增加。这使得置乱的速度降低，从而使得等待的时间变长。另一 方面，随着数据量的增加，隐藏存储区的空间也随之扩大。这就使得置乱的次数随之降低。 与此同时，由于同步隐藏存储区也随之扩大，在置乱期间允许的请求数也随之上升。这对于 减少等待的时间也是有帮助的。
【主权项】
1. 一种基于访问模式保护的空间数据安全系统，其特征在于，包括：服务端和与之相 连的用户端，其中：用户端向服务端发出数据项查询指令，并接收服务端反馈的数据查询结 果； 所述的用户端包括：地址翻译单元和执行单元，其中：地址翻译单元根据用户指令翻 译得到查询请求，通过执行单元发送至向服务端进行查询； 服务端包括：局部置乱处理模块、移层操作模块、全局置乱处理模块和并发置乱模块， 其中：局部置乱处理模块负责进行隐藏存储区中某个层级内部或是主存储区内部的置乱操 作，移层操作模块负责进行隐藏存储区中不同层级之间的置乱操作，全局置乱处理模块负 责进行隐藏存储区和主存储区之间的置乱操作，并发置乱模块负责保证用户在置乱处理的 过程中仍然能对数据进行正常访问。2. 根据权利要求1所述的系统，其特征是，所述的地址翻译单元中包含一个动态索引 结构R- tree，将其命名为R ; 所述的执行单元中包含一个层级列表L，该层级列表L中存储着服务器上隐蔽存储区 的结构信息；当收到地址翻译模块的请求后，执行端向服务器执行查询请求，并将得到结果 并返回给用户；为了数据安全考虑，当系统开始运行的时候，必须输入一个密钥SK，IskI= k，用于数据加密。3. 根据权利要求1所述的系统，其特征是，所述的置乱处理单元包括：局部置乱处理 模块、移层操作模块、全局置乱处理模块和并发置乱模块，其中：局部置乱处理模块负责进 行隐藏存储区中某个层级内部或是主存储区内部的置乱操作，移层操作模块负责进行隐藏 存储区中不同层级之间的置乱操作，全局置乱处理模块负责进行隐藏存储区和主存储区之 间的置乱操作，并发置乱模块负责保证用户在置乱处理的过程中仍然能对数据进行正常访 问。
【专利摘要】一种基于访问模式保护的空间数据安全系统，当用户端从服务器端获取一个id的时候，要对其进行解密，并在用户端返回服务器数据时进行重加密，本发明在保证查询效率的同时，不但实现数据的加密，同时对数据的访问模式也进行隐藏和保护，从而大大降低信息泄漏的风险。
【IPC分类】H04L29/06
【公开号】CN104883370
【申请号】CN201510299797
【发明人】过敏意, 姚斌, 沈耀, 谢丁星, 周憬宇, 薛广涛
【申请人】上海交通大学
【公开日】2015年9月2日
【申请日】2015年6月3日