利用字典编码的安全数据库

摘要

实施例利用字典编码提供数据库安全性，其中某些功能在安全环境中实施，例如可信执行环境(TEE)。特别地，安全环境从数据所有者接收秘密密钥，并从查询引擎接收加密查询范围和字典引用。基于使用秘密密钥解密的查询范围以及从数据库加载的字典，安全环境搜索字典以产生对应于查询范围的值标识符列表。值标识符被传送到安全环境之外给查询引擎用于进一步处理(例如，生成RecordID)，最终为用户产生查询结果。特定实施例可以利用存储器内数据库引擎的处理能力，以便执行与安全环境交互的查询引擎的角色。

权利要求

1.一种计算机实施的方法，包括：安全环境接收秘密密钥；

所述安全环境从位于所述安全环境之外的查询引擎接收对应于用户发出的查询的加密查询范围；

所述安全环境从所述查询引擎接收对字典的引用；

所述安全环境使用所述秘密密钥解密所述加密查询范围；

所述安全环境根据所述秘密密钥解密所述字典的值；

所述安全环境搜索所述字典以产生匹配所述加密查询范围的值标识符列表；和所述安全环境将所述值标识符列表返回给所述查询引擎，使得响应于接收到所述值标识符列表，所述查询引擎被配置为根据所述值标识符列表来引用存储在数据库中的向量属性信息，并且为查询结果生成记录标识符列表，并且所述查询引擎被配置为将所述查询结果返回给用户。

2.如权利要求1所述的方法，还包括所述安全环境从数据库加载所述字典。

3.如权利要求2所述的方法，其中所述数据库包括面向列的数据库。

4.如权利要求1所述的方法，其中，所述字典指示从安全强度、性能速度和存储器消耗中的至少一个中选择的特性。

5.如权利要求1所述的方法，其中所述安全环境包括可信执行环境(TEE)。

6.如权利要求5所述的方法，其中在接收所述秘密密钥之前，TEE的证明特征被引用用于认证。

7.如权利要求1所述的方法，其中所述数据库包括存储器内数据库。

8.如权利要求7所述的方法，其中所述查询引擎包括所述存储器内数据库的存储器内数据库引擎。

9.如权利要求7所述的方法，其中所述存储器内数据库包括混合数据库。

10.如权利要求1所述的方法，其中所述数据库包括面向行的数据库。

11.一种体现用于执行方法的计算机程序的非暂时性计算机可读存储介质，所述方法包括：安全环境接收秘密密钥；

所述安全环境从位于所述安全环境之外的查询引擎接收对应于用户发出的查询的加密查询范围；

所述安全环境从所述查询引擎接收对字典的引用；

所述安全环境从面向列的数据库加载所述字典；

所述安全环境使用所述秘密密钥解密所述加密查询范围；

所述安全环境根据所述秘密密钥解密所述字典的值；

所述安全环境搜索所述字典以产生匹配所述加密查询范围的值标识符列表；和所述安全环境将所述值标识符列表返回给所述查询引擎，使得响应于接收到所述值标识符列表，所述查询引擎被配置为根据所述值标识符列表来引用存储在所述数据库中的向量属性信息，并且为查询结果生成记录标识符列表，并且所述查询引擎被配置为将所述查询结果返回给用户。

12.如权利要求11所述的非暂时性计算机可读存储介质，其中，所述字典确定从安全强度、性能速度和存储器消耗中的至少一个中选择的特性。

13.如权利要求11所述的非暂时性计算机可读存储介质，其中：所述安全环境包括可信执行环境(TEE)；和在接收所述秘密密钥之前，TEE的证明特征被引用用于认证。

14.如权利要求11所述的非暂时性计算机可读存储介质，其中：所述面向列的数据库包括面向列的存储器内数据库；和所述查询引擎包括所述面向列的存储器内数据库的存储器内数据库引擎。

15.一种计算机系统，包括：

一个或多个处理器；

可在所述计算机系统上执行的软件程序，所述软件程序被配置成使得安全环境：接收秘密密钥；

从位于所述安全环境之外的存储器内数据库的存储器内数据库引擎接收对应于用户发出的查询的加密查询范围；

从所述存储器内数据库引擎接收对字典的引用；

使用所述秘密密钥解密所述加密查询范围；

根据所述秘密密钥解密所述字典的值；

搜索所述字典以产生匹配所述加密查询范围的值标识符列表；和将所述值标识符列表返回到所述存储器内数据库引擎，使得响应于接收到所述值标识符列表，所述存储器内数据库引擎被配置为根据所述值标识符列表来引用存储在所述数据库中的向量属性信息，并且为查询结果生成记录标识符列表，并且所述存储器内数据库引擎被配置为将所述查询结果返回给用户。

16.如权利要求15所述的计算机系统，其中，所述软件程序还被配置成使得所述安全环境从所述存储器内数据库加载所述字典。

17.如权利要求15所述的计算机系统，其中，所述存储器内数据库是面向列的存储器内数据库。

18.如权利要求15所述的计算机系统，其中所述字典确定从安全强度、性能速度和存储器消耗中的至少一个中选择的特性。

19.如权利要求15所述的计算机系统，其中：所述安全环境包括可信执行环境(TEE)；和在接收所述秘密密钥之前，TEE的证明特征被引用用于认证。

20.如权利要求15所述的计算机系统，其中，所述存储器内数据库包括面向行的存储器内数据库。

说明书

利用字典编码的安全数据库

背景技术

[0001] 除非在此另有说明，否则本部分中描述的方法不是本申请中权利要求的 现有技术，并且不通过包含在本部分中而被承认为现有技术。

[0002] 数据仓库可能被公司用于商业智能和决策支持。这些仓库可以包含巨大 的数据集，并且底层数据库针对复杂的面向读取的分析查询进行了优化。

[0003] 将数据和查询处理外包给云，更具体地说，外包给数据库即服务 (Database-as-a-Service，DBaaS)提供商，可以降低成本、减少维护工作量并 带来更高的可用性。然而，至少出于安全考虑，公司可能不愿意将敏感数据 外包给不可信DBaaS提供商。

发明内容

[0004] 在某些功能性在安全环境(例如可信执行环境(Trusted  Execution Environment，TEE))中实施的情况下，实施例利用字典编码提供数据库安全 性。特别地，安全环境从数据所有者接收秘密密钥。然后，安全环境从查询引 擎接收加密查询范围和字典引用。字典可以从安全环境外部加载，或者可以 已经存在于安全环境内部。基于使用秘密密钥解密的查询范围，安全环境搜 索与查询匹配的值，并编译相应值标识符的列表。值标识符被传送到安全环 境之外给查询引擎用于进一步处理(例如，生成RecordID)，最终为用户产生 查询结果。特定实施例可以利用存储器内数据库引擎的处理能力，以便执行 与安全环境交互的查询引擎的角色。

[0005] 不同类型的加密字典的可供使用的可用性在提供安全存储方面提供了灵 活性。特别地，如稍后结合示例性实施例所述，各种加密字典可以提供关于 特性的不同折衷，这些特性可以包括但不限于：所提供的安全性的强度；性 能(例如速度)；和/或存储(例如，存储器)消耗。

[0006] 以下详细描述和附图提供了对各种实施例的性质和优点的更好理解。

附图说明

[0007] 图1示出了根据实施例的系统的简图。

[0008] 图2示出了根据实施例的方法的简化流程图。

[0009] 图3描绘了字典编码的简化示例。

[0010] 图4呈现了根据特定示例的以字典编码为特征的存储器内数据库的实施 例的高级概览。

[0011] 图5是根据示例呈现九种加密字典的表格。

[0012] 图6示出了用于示例的数据类型中的一种类型的字典编码。

[0013] 图7示出了呈现了针对示例的数据类型中的一种类型在飞地(enclave) 内执行的函数的过程。

[0014] 图8示出了示例的数据类型中的一种类型的字典编码。

[0015] 图9示出了用于根据示例的数据类型在飞地内部进行处理的过程。

[0016] 图10示出了可以处理加密的包装数据的特殊二进制搜索过程。

[0017] 图11示出了示例的数据类型中的一种类型的字典编码。

[0018] 图12示出了执行线性扫描的过程。

[0019] 图13呈现了随机实验的过程。

[0020] 图14示出了示例的数据类型中的一种类型的字典编码。

[0021] 图15示出了根据实施例的专用计算机器的硬件，该专用计算机器被配置 为根据某些实施例实施字典编码的存储器内数据库。

[0022] 图16示出了示例计算机系统。

具体实施方式

[0023] 本文描述的是根据各种实施例实施数据库转换的模拟的方法和装置。在 以下描述中，出于解释的目的，阐述了许多示例和具体细节，以便提供对根 据本发明的实施例的透彻理解。然而，对于本领域的技术人员来说，很明显， 由权利要求限定的实施例可以单独地或与下面描述的其他特征相结合地包括 这些示例中的一些或全部特征，并且可以进一步包括本文描述的特征和概念 的修改和等同物。

[0024] 图1示出了根据实施例的被配置为执行数据库字典编码的示例系统100 的简化视图。具体而言，可信数据所有者102寻求外包其数据用于存储和由 位于客户环境105中的用户104以安全的方式查询。

[0025] 虽然图1将数据所有者和用户显示为分离的实体，但这不是必需的。根 据某些实施例，数据所有者和用户可以是相同的实体。

[0026] 最初，数据所有者在本地准备其未加密的数据。作为数据准备的一部分， 根据字典加密安全方案，未加密数据的每一列被分离成字典和属性向量。这 将在下面结合图3进一步讨论。

[0027] 然后，数据所有者选择基于列的字典编码107。这种基于列的字典编码可 以是明文编码。数据所有者不在本地进一步处理这种明文列。

[0028] 然而，所选的基于列的字典编码可以是加密数据类型。如下结合图5所 述，各种不同的加密字典可以提供关于诸如以下特性的某些折衷：

[0029] ·所提供的安全强度；

[0030] ·性能(例如速度)；和/或

[0031] ·存储(例如存储器)消耗。

[0032] 数据所有者在两个步骤中在本地处理具有加密字典的列。首先，根据所 选的加密数据类型修改字典和属性向量。第二，所有字典条目都在秘密密钥 120下用随机加密单独加密。

[0033] 接下来，数据所有者将秘密密钥供应给用户104和安全环境110两者， 数据所有者的角色将在下面讨论。在某些实施例中，安全环境的证明 (attestation)特征可以用于认证和建立安全连接，以向安全环境供应秘密密 钥。

[0034] 数据所有者还部署125字典127和属性向量数据128，以便于存储在存 储层132的数据库130中。该存储层可以由DBaaS提供商管理。

[0035] 从这一点开始，数据库中呈安全形式的数据设置现在已经完成。用户可 以自由制定并向数据库发出加密查询134。

[0036] 此类查询可以基于相等选择、反相等选择、大于选择(包含性的和排除 性的)、小于选择(包含性的和排除性的)和范围选择(包含性和排除性)。其 他查询功能(诸如计数、聚合和平均计算)可以是可用的。

[0037] 在由用户发出之前，查询可以被转换成范围选择，并且范围开始和范围 结束用随机加密133加密。转换为范围选择提供了附加的益处，即最终接收 查询的不可信服务器无法区分查询类型。此外，不可信服务器无法了解这些 值之前是否被查询过。

[0038] 所得到的加密查询134被发出到应用层144的查询引擎142。如稍后结 合该示例所述，加密查询最初可以通过验证查询语法并检查所请求的表格和 列的存在来处理。加密查询的高级查询语言(例如，SQL)可以被转换成要在 每列上执行的一组代数操作。评估可能的查询计划，并做出关于高效的查询 计划执行的决定。

[0039] 虽然图1已经示出了位于覆盖数据库的应用层中的查询引擎，但这不是 必需的。特定实施例可以利用存储器内数据库引擎的处理能力来执行本文描 述的一个或多个功能。具体而言，图1(稍后描述)示出了存储器内数据库的 实施，其中位于数据库中的单个存储器内数据库引擎处理查询功能和数据存 储(例如，属性向量、字典)功能两者。

[0040] 返回图1，查询引擎然后只处理传入查询对于其包括筛选表达式的列(即， 对该列执行范围查询)。对于这些列，查询引擎获取相应的元数据，并根据查 询计划逐个处理这些列。

[0041] 作为查询的一部分进行处理的明文列，按照底层存储层的定义定期处理。

[0042] 相比之下，加密字典的列作为查询的一部分在以下两个步骤中进行处理，：

[0043] (1)在安全环境110中进行字典搜索109；和

[0044] (2)在安全环境之外进行属性向量111搜索。

[0045] 简而言之，安全环境保证加载在其中的代码和数据在机密性和完整性方 面受到保护。一种类型的安全环境是由某些处理器体系结构提供的可信执行 环境(Trusted Execution Environment，TEE)。

[0046] TEE作为独立的执行环境提供了安全特征，诸如独立执行、与TEE一起 执行的应用的完整性以及它们的资产的机密性。这种TEE的具体示例包括但 不限于：

[0047] ●可从加利福尼亚州圣克拉拉的高级微设备公司(Advanced Micro Devices， AMD)获得的平台安全处理器(Platform Security Processor，PSP)；

[0048] ●可从AMD获得的AMD安全执行环境；

[0049] ●可从加利福尼亚州圣何塞的ARM获得的信任区(TrustZone)；

[0050] ●可从加利福尼亚州圣克拉拉的英特尔公司获得的可信执行技术；

[0051] ●可从英特尔获得的SGX(SoftwareGuard Extensions，软件保护扩展)软 件保护扩展；

[0052] ●在英特尔凌动处理器上可用的“寂静之湖(Silent Lake)”；

[0053] ●可从RISC-V基金会获得的MultiZoneTM安全可信执行环境。

[0054] 加密字典的处理从查询引擎将以下内容传递到安全环境开始：

[0055] ·加密范围150，以及

[0056] ·对相应字典的引用152，

[0057] 安全环境使用密钥解密范围。然后，安全环境在字典中执行搜索109。

[0058] 这是通过从数据库加载156字典127并单独解密适当的值来完成的。虽 然图1将数据库示出为位于安全环境之外，但这不是必需的。根据一些实施 例，数据库可以位于安全环境中。数据库可以位于同一台机器上，也可以来 自安全环境的任何其他机器上。

[0059] 字典搜索109可以调用TEE函数。如下例所述，在安全环境中如何执行 该字典搜索取决于经筛选的列的具体加密字典。但是，结果总是安全环境返 回ValueID列表。这表示，安全环境根据实施例在执行查询处理中的有限参 与。

[0060] 作为字典搜索的结果，安全环境向查询引擎返回ValueID列表160。查询 引擎依次引用该ValueID列表，以便在存储在数据库中的属性向量中执行搜 索111。

[0061] 由查询引擎收集所有经筛选的列的所得到的RecordID。在对表格的多个 列执行“和”或“或”筛选器的情况下，可能会组合或扣除(deducted)RecordID。

[0062] 所得到的RecordID用于从相应的字典中获取加密值。筛选器的RecordID 还用于检索仅被选择的列的相对应的加密值。

[0063] 查询引擎将所有结果添加到结果集中，并将加密查询结果170传递回用 户。在那里，根据秘密密钥解密172查询结果，以渲染为用户可理解的形式。

[0064] 在整个查询处理中，强调只有较小子集(即范围解密；字典搜索)实际上 是在安全环境中执行的。这允许存储层的现有数据库功能(例如，持久性管 理、多版本并发控制或访问管理)保持不变，同时仍然为数据所有者和用户 提供所期望的安全性。

[0065] 图2是示出根据实施例的方法200中采取的各种动作的流程图。在202， 安全环境接收秘密密钥。

[0066] 在204，安全环境从位于安全环境外部的查询引擎接收对应于由用户发 出的查询的加密查询范围。在206，安全环境从查询引擎接收对根据加密字典 的字典的引用，并将其存储在数据库中。

[0067] 在208，安全环境使用秘密密钥解密加密查询范围。在210，安全环境从 数据库加载字典。

[0068] 在212，安全环境搜索字典以产生对应于第一加密查询范围的值标识符 列表。在214，值标识符被传送到查询引擎进行处理，最终得到查询结果。

[0069] 现在结合以下示例提供关于在存储器内数据库中实施字典编码的细节。

[0070] 示例

[0071] 以下示例取自在支持大数据集的高性能加密分析云数据库环境中的实施 例的生产性实施。此示例用于基于面向列的字典编码的存储器内数据库，该 数据库是利用可从MonetDB基金会获得的MonetDB体系结构创建的。

[0072] 具体而言，对于该示例，面向列的数据存储优化了分析性工作负载的处 理。存储器内处理提高了整体性能，字典编码降低了大型(加密)数据集的存 储空间开销。

[0073] 此特定示例提供了九个不同的加密字典，数据所有者可以从中选择列粒 度。这些提供了关于各个方面的折衷，包括但不限于：

[0074] ·安全性(顺序和频率泄漏)；

[0075] ·性能；和

[0076] ·存储消耗。

[0077] 该特定示例集成到支持查询优化和辅助数据库功能(例如存储、交易和 数据库恢复管理)的MonetDB数据库管理系统(MonetDB Database Management System，DBMS)中。数据值用概率加密进行加密。可信计算基 (Trusted Computing Base，TCB)仅代表大约1500行代码。

[0078] 如下文详细描述的，该示例对具有超过1000万条目的列上的真实数据进 行评估。与明文版本相比，加密数据的处理引入了亚毫秒级的开销。此外，加 密列比明文列需要更少的存储。

[0079] 现在提供关于该示例的更多细节。

[0080] 传统上，数据库系统针对磁盘存储进行了优化。为了优化性能，数据可 能被缓存到主存储器中，但主数据驻留在磁盘上。

[0081] 相反，存储器内数据库将主数据永久存储在主存储器中，并将磁盘用作 辅助存储。存储器内数据库的益处是，与磁盘存储相比，主存储器的访问时 间更短。

[0082] 这加快了需要磁盘访问的每一次数据访问。此外，它还导致并发控制中 的更短的锁定时间，从而导致更少的缓存刷新，更好的CPU利用率。

[0083] 也存在混合数据库。混合数据库仅将部分数据存储在主存储器中。例如， 它们区分在存储器内处理的访问次数最多的(热)数据和按需加载到主存储 器中的剩余(冷)数据。

[0084] 存储器内数据库面临的挑战是主存储器的易失性。机器的预期或意外断 电会清除所有数据。因此，可以使用基于磁盘的持久性构思，诸如交易日志 记录，并小心处理，以免在运行时引入性能瓶颈。

[0085] 此外，可以采用平稳重启。两种可能性是：一次将所有数据从磁盘加载 到主存储器，或者按需加载数据。非易失性随机存取存储器(NVRAM)可以 用来处理掉电的情况，但是比传统的主存储器具有更高的访问时间。

[0086] 几个商业和开源数据库支持存储器内处理，例如：

[0087] ·可从德国沃尔多夫思爱普系统有限公司获得的HANA存储器内数据库；

[0088] ·来自加利福尼亚州红杉海岸甲骨文公司的甲骨文RDBMS(Relational database management system，关系型数据库管理系统)；

[0089] ·VoltDB；和

[0090] ·MonetDB。

[0091] 现在讨论面向列和行的数据库方法。关系型数据库(例如，MySQL和 PostgreSQL)可以将面向行的二维表存储到存储装置(主存储器或磁盘)中， 即数据被逐行连续存储。例如，存储具有三行三列的表的数据库，首先存储 第一行的所有属性，然后存储第二行的所有属性，并且最后存储第三行的所 有属性。这种面向行的存储可能有利于交易处理，例如，更新几行上的所有 列或插入新行。

[0092] 另一个概念是存储面向列的数据，即连续存储每列的连续值，并(隐式 地)引入代理标识符来连接行。对于刚才提到的示例，这导致属于第一个属 性的三个值首先被存储，然后存储属于第二个属性的三个值，并且最后存储 属于最后一个属性的三个值。

[0093] 面向列存储的潜在挑战可能包括：(1)所谓的元组重构对于重新组装涉 及多个属性的投影是必要的；以及(2)元组的插入和更新被写入非连续的存 储位置。然而，由于几个可能的原因，这些问题在例如数据仓库和商业智能 等的分析应用的情况中并不严重。

[0094] 首先，分析查询通常涉及对所有元组的大百分比进行扫描，但只扫描所 有列的小子集。此外，在这种情况下经常使用大容量数据加载，然后执行复 杂、长时间的只读查询。

[0095] 示例查询是某个价格范围内产品在每个国家的总销售额报告。只需加载 查询中涉及的几个列。它们可以顺序处理，这是有益的，因为它减少了现代 CPU的缓存未命中。

[0096] 当与存储器内数据库一起使用时，面向列的存储展现了其全部潜力，因 为缓存未命中的数量是存储器内处理性能的一个决定因素。上面提到的特定 存储器内数据库也支持面向列的存储。

[0097] 现在讨论基于面向列的字典编码的存储器内数据库。现代数据库可以使 用数据压缩机制来利用数据中的冗余。

[0098] 各种数据库压缩方案，例如空抑制、游程编码和字典编码，可以应用于 面向列的数据库。面向列的数据库受益于这种压缩。

[0099] 如果可能的话，查询操作符直接处理压缩数据，而不需要CPU的密集解 压缩，并且解压缩被延迟到绝对必要的时候。这提高了存储器带宽，并且可 以通过处理固定长度的整数而不是底层解压缩数据来优化算法。例如，整数 上的等式比较比(可变长度)字符串上的等式比较快得多，因为CPU针对这 一操作进行了优化。

[0100] 为了进一步降低压缩和解压缩的开销，轻量级压缩方案可能是优选的。 字典编码是面向列的数据库中普遍使用的一种压缩，并且它是轻量级的。

[0101] 字典编码的思想是将原始列拆分成两个结构：字典和属性向量。字典中 填充了该列的所有唯一值。本字典中的每个值都隐含地由一个所谓的ValueID 索引。原始列中的值被对应于该值的(小)ValueID替换。所得到的列被表示 为属性向量，其位置被称为RecordID。

[0102] 图3呈现了基于第一名字列(FName)的片的示例。例如，Jessica被插 入到字典中的位置30，并且包含Jessica的原始列中的所有位置都被属性向量 中的该ValueID替换(参见RecordID 49、52和54)。

[0103] 如果列只包含很少的唯一值，但包含许多频繁值，则字典编码具有最佳 压缩率，因为每个值只需存储一次。本示例的评估中使用的真实数据(如下 所述)表明，这是数据仓库中许多列的特性。

[0104] 请注意，属性向量需要的空间比原始列少得多。这是因为i位的固定长度 ValueID足以表示2i个不同的值。(可变长度)值只需在字典中存储一次，这 在许多情况下会带来显著的存储优势。

[0105] 例如，包含10000个字符串(每个字符串10个字符，但只有256个唯一 值)的列，字典需要256·10B，属性向量需要10000·1B。总的来说，字典编 码将所需的存储从100000字节减少到12650字节。字典编码实现的高压缩率 很少使用存储器内数据库的稀缺资源——主存储器的大小。

[0106] 现在简要说明搜索，其中基于以下示例使用字典编码：

[0107] SELECT FName,LName FROM t1 WHERE FName＝′Archie′。

[0108] 假设表t1包括来自图3中的FName列，LName列包含相应的姓氏。 LName也被拆分成字典和属性向量。

[0109] 首先，在FName字典中搜索Archie。Archie的ValueID是31。该ValueID 用于扫描FName的属性向量，从而得到RecordID 51和55。这些RecordID存 储在中间结果列中，并且它们被用于访问LName的属性向量。相应位置处的 ValueID用作第二个中间结果列。最后一步，两个字典都用来用实际值替换两 个中间结果列的ValueID。

[0110] 现在讨论英特尔软件保护扩展(SGX)。英特尔SGX是英特尔SKYLAKE 一代推出的指令集扩展。从那时起，它几乎存在于所有英特尔CPU中。

[0111] 主要思想是提供可信执行环境(TEE)功能，即保证代码和数据的机密性 和完整性保护的安全处理区域。换句话说，它支持在不可信环境中独立执行。

[0112] 现在描述这个示例所利用的SGX的特征的高级概述。提供存储器隔离。 在SGX平台上，程序可以分为两部分：不可信部分；和独立、可信的部分。

[0113] 可信部分(在SGX术语中称为飞地)位于物理RAM的专用部分。SGX 硬件对这部分存储器实施额外保护。特别是，系统上的其他软件(包括诸如 OS、管理程序和固件等特权软件)无法访问飞地存储器。

[0114] 不可信部分作为虚拟存储器地址空间内的普通进程执行，并且飞地存储 器被映射到不可信主机进程的虚拟存储器中。这种映射允许飞地访问其主机 进程的整个虚拟存储器，而(不可信)主机进程只能通过定义良好的接口调 用飞地。

[0115] 此外，独立的代码和数据当驻留在CPU外部时被加密。当数据被加载到 CPU时，执行解密和完整性检查。

[0116] 对于存储器管理，SGX将固定数量的系统的主存储器(RAM)专门用于 飞地和相关元数据。在某些示例中，该存储器可能限制为128MB，用于SGX 元数据和飞地本身的存储器。后者称为飞地页面缓存(Enclave Page cache，EPC)，约为96MB。

[0117] SGX存储器在早期引导阶段被保留，并且在整个系统运行期间是静态的。 由于可以并行加载和执行的飞地的数量实际上是无限的，OS动态管理飞地存 储器。

[0118] OS可以将(部分)存储器分配给各个飞地，并在飞地运行期间更改这些 分配。特别是，OS可以换出飞地页面。SGX确保换出的页面的完整性、机密 性和新鲜度。

[0119] 关于证明(attestation)，SGX具有远程证明特征，允许在远程系统上验证 代码完整性和真实性。这是通过散列(在SGX术语中称为测量)加载到飞地 的初始代码和数据来实现的。

[0120] 测量的真实性以及测量来源于良性飞地的事实由SGX的证明特征提供 的签名来保证。这一签名是由SGX的组件提供的，称为引用飞地(quoting enclave，QE)。

[0121] QE仅接受来自硬件的测量，硬件确保仅测量正确的飞地。测量结果可以 提供给外部方，以证明飞地的正确创建。

[0122] 此外，远程证明特征允许在外部方和飞地之间建立安全通道。该安全通 道可以用于将敏感数据直接部署到飞地，而不需要硬件所有者具有对其的访 问权。

[0123] 图4呈现了本示例的高级设计。该图区分了可信和不可信实体。

[0124] 主不可信实体是DBaaS提供商，即在云中运行面向列的存储器内数据库 的云提供商。该DBaaS提供商在支持SGX的服务器上部署安全云数据库。

[0125] 只有一小部分数据库功能在飞地内运行。其余的在不可信环境中运行。

[0126] 假设可信数据所有者想要外包其数据，并且可信应用查询数据。来自可 信应用的请求及对其的所有响应都通过可信代理传递。

[0127] 最初，数据所有者在本地准备数据(参见图4中的步骤1)。如上所述， 数据所有者的既有系统的每一列都被分离为字典和属性向量。

[0128] 这时，数据所有者为每列选择字典编码。这可以是常规明文字典编码或 加密字典。本示例提供了九(9)个不同的加密字典，在安全性、性能和存储 消耗方面有不同的折衷。

[0129] 不再进一步处理明文列，但分两步处理其他列。首先，根据选定的加密 数据类型修改字典和属性向量。第二，所有字典条目都是在秘密密钥下用随 机加密单独加密的。

[0130] 在下一步(2)，数据所有者向代理和飞地供应秘密密钥。安全的带外部 署用于代理。

[0131] SGX的证明特征用于认证飞地，并建立与其的安全连接(如上所述)。此 安全连接用于将秘密密钥部署到飞地。

[0132] 作为一次性设置的最后一步，在步骤(3)中，数据所有者将数据(即字 典和属性向量)部署到DBaaS提供商。作为混合存储器内数据库的示例特征， 存储器内数据库的存储管理将所有数据持久地存储在磁盘上，并额外将其(部 分)加载到主存储器中。

[0133] 从此，应用可以向数据库发送任意数量的查询-步骤(4)。

[0134] 这样的查询可能包括相等选择、反相等选择、大于选择(包含性的和排 除性的)、小于选择(包含性的和排除性的)和范围选择(包含性的和排除性 的)。可以添加其他查询功能，例如计数、聚合和平均值计算。

[0135] 查询通过代理进行路由，在代理中它们被截取、转换为范围选择，并且 范围开始和结束用随机加密进行加密。

[0136] 查询类型可以转换为范围选择。这种转换具有附加溢出，即不可信服务 器无法区分查询类型。此外，由于随机加密，不可信服务器也无法了解这些 值以前是否被查询过。

[0137] 所得到的加密查询被传递给DBaaS提供商的查询管道-参见步骤(5)。查 询管道在DBMS之间不相同。但是，在高级别上，查询管道以如下所述的方 式处理查询。

[0138] 首先，查询解析器验证查询语法并检查所请求的表和列的存在。查询分 解器将高级查询语言(例如，SQL)转换成要在每列上执行的一组代数操作， 数据库内核可以理解这些操作。

[0139] 查询优化器评估可能的查询计划，并决定最有效的执行。它还将相应的 列加载到主存储器中(如果它们只驻留在磁盘上的话)。

[0140] 最后，与查询评估引擎共享查询计划。查询评估引擎仅处理对于其的传 入查询包含筛选表达式的列(即，对该列执行范围查询)。对于这些列，查询 评估引擎获取元数据，并根据查询计划逐个处理这些列。

[0141] 每个需要处理的明文列如由底层DBMS定义那样定期处理。在两个步骤 中处理加密字典的列：飞地中的字典搜索和不可信领域中的属性向量搜索。

[0142] 处理开始于查询评估引擎将加密范围和对相应字典的引用传递给飞地- 参见步骤(6)。

[0143] 飞地通过单独加载和解密适当的值来解密范围并在字典中执行搜索-参 见步骤(7)和(8)。

[0144] 在步骤(9)中，飞地返回ValueID列表，查询评估引擎使用该列表在属 性向量中执行搜索——参见步骤(10)。

[0145] 在步骤(11)中，所有筛选列的得到的RecordID被传递给结果渲染器。 如果在一个表的多列上执行了“and”或“or”筛选，RecordID可能会被组合 或扣除。

[0146] 所得到的RecordID用于从相应的字典中获取加密值。筛选器的RecordID 还用于检索仅被选择的列的相应加密值。

[0147] 在步骤(12)，结果渲染器将结果添加到结果集中，并将其传递回代理。 在步骤(13)中，结果集被解密并转发给应用。

[0148] 值得注意的是，只有一小部分查询处理是在可信飞地内执行的。不需要 更改辅助数据库功能，诸如持久性管理、多版本并发控制或访问管理。尽管 如此，整个处理仍受到保护。

[0149] 现在讨论假设和攻击者模型。攻击者模型认为数据所有者、应用和代理 是可信的。

[0150] 在服务器侧，假设诚实但好奇的攻击者。也就是说，攻击者是被动的攻 击者，其遵循协议，但试图获取尽可能多的信息。

[0151] 假设DBaaS提供商在支持英特尔SGX的系统上运行此示例。然而，根 据替代实施例，SGX可以由提供例如如下的所需能力的任何其他TEE替换：

[0152] ·完整性

[0153] ·代码和数据的机密性保护，

[0154] ·远程证明；

[0155] ·安全的数据供应。

[0156] 假定代码没有故意的数据泄漏。然而，SGX可能容易受到各种侧通道攻 击，例如缓存攻击、利用时序效应或页面错误。实施例可以被设计成具有最 小的飞地代码，因此保护应当容易与对性能的较小影响结合。

[0157] 除了受TEE保护的代码和数据之外，攻击者还完全控制在DBaaS提供 商处运行的所有软件。其中包括操作系统、固件和DBMS。

[0158] 因此，攻击者能够访问存储在磁盘和主存储器上的数据，并且能够观察 到对它们的访问模式。此外，攻击者可以跟踪飞地与其外部资源之间的所有 通信，以及代理和DBMS之间的所有网络通信。

[0159] 请注意，这包括其中仅数据值被加密的传入查询。查询的其余部分是明 文。

[0160] 假设攻击者独立地以每个数据库列为目标，即他没有利用相关信息来以 列为目标。不考虑对TEE的硬件攻击。拒绝服务(Denial of Service，DoS) 攻击也在范围之外，因为假设云提供商不拒绝服务具有商业利益。客户端和 DBaaS提供商之间的网络连接也是如此。

[0161] 现在给出了符号和定义，接着是概率认证加密(Probabilistic Authenticated Encryption，PAE)和硬件安全字典搜索(Hardware Secured Dictionary Search， HSDS)的定义。

[0162] 对于字典编码，列C具有C.#v个值，即C＝(C.v0,…,C:v(C.#v-1))。un(C) 表示C中唯一值的数量，oc(C.v)表示相同值v∈C出现的次数。

[0163] 字典编码将每个列C拆分成两个结构：字典D和属性向量AV。D可以 表示为包含D.#v个值的数组：D＝(D.v0,…,D.v(D.#v)-1)。在标准字典中，D.#v 匹配被拆分的列的un(C)。字典条目D.vi的索引i也是对应于该值的ValueID (vid)。我们对属于列C的属性向量AV使用相等的符号，它包含与C(C.#v)中 的条目数量匹配的AV.#vid个ValueID。AV.vidj是AV中j位置处的条目，索 引j也是它的RecordID(rid)。

[0164] 为了便于注释，我们有时忽略列C的拆分。在这种情况下，C.vi指的是 通过访问AV.vidi并在D中定位相应值而获得的值。

[0165] 概率认证加密(PAE)包括三个多项式时间算法：PAE＝(PAE_Gen(1λ)、 PAE_Enc(SK,IV,v)、PAE_Dec(SK,c)。概率认证加密提供机密性、完整性和 真实性。PAE_Gen采取安全参数1λ作为输入并生成秘密密钥SK。PAE_Enc 以密钥SK、随机初始化向量IV和值v作为输入并返回密文c。未加密的IV 是c的一部分。如果v在初始化向量IV和密钥SK下用PAE Enc加密， PAE_Dec采取密钥SK和密文c作为输入并返回v，。否则，它将返回┴。请 注意，IV不是PAE_Dec的参数，因为它是c的一部分。PAE是经认证的IND- CCA安全加密，例如，GCM模式下的AES-128。

[0166] 硬件安全字典搜索(HSDS)是在基于加密的面向列的字典编码的存储器 内数据库中搜索数据的概念。

[0167] 定义1(HSDS)：硬件安全字典搜索(HSDS)是六个多项式时间过程的 元组(HSDS_Setup；HSDS_EncDB；HSDS_DecRes；HSDS_Process-Query； HSDS_DictSearch)。

[0168] 数据所有者处执行以下过程：

[0169] SKDB←HSDS_Setup(1λ)：采取安全参数λ为输入并输出秘密密钥SKDB。

[0170] EDB←HSDS_EncDB(SKDB,PDB,dt)：采取秘密密钥SKDB、明文数据库 PDB和列字典编码dt为输入。输出加密数据库EDB。

[0171] 代理处执行以下过程：

[0172] eQ←HSDS_EncQuery(SKDB,Q)：采取秘密密钥SKDB和明文查询Q为输 入。该查询包含在一个表的多个列上选择和筛选。输出加密查询eQ，其中所 有值都被加密。

[0173] C←HSDS_DecRes(SKDB,eC)：采取秘密密钥SKDB和多个加密列eC作 为输入。输出明文列C。

[0174] 以下过程在不可信硬件上的服务器处执行：

[0175] eC←HSDS_ProcessQuery(eQ)：采取加密查询eQ作为输入。输出一组加 密列eC。

[0176] 在安全硬件的服务器处执行以下过程：

[0177] vid←HSDS_DictSearch(τ,eD)：采取加密范围τ和加密列eC作为输入。 输出一组ValueID vid。

[0178] HSDS的正确性定义如下。定义2(正确性)。让D表示由定义1中描述 的六种算法组成的HSDS方案。给定诚实但好奇的攻击者，如果对于所有λ∈ N，对于HSDS_Setup(1λ)输出的所有SKDB，对于HSDS_EncDB(SKDB,PDB,dt) 用来输出EDB的所有明文数据库PDB和数据类型dt，对于 HSDS_EncQuery(SKDB,Q)用来输出eQ的所有查询Q，对于 HSDS_ProcessQuery(eQ)输出的所有eC，HSDS_DecRes(SKDB,eC)输出的列C 是与查询Q匹配的结果集，我们就说D是正确的。

[0179] 前面的图4提供了支持对加密数据的搜索的实施例。它可以部署在任何 现有的基于面向列的字典编码的存储器内数据库上。只有字典搜索部署在英 特尔SGX飞地(或另一个类似的TEE)内。

[0180] 底层DBMS的进一步查询处理，诸如：

[0181] ·查询解析，

[0182] ·查询分解，以及

[0183] ·查询优化，

[0184] 是不可更改的并在不可信领域中执行。

[0185] 辅助数据库功能也是如此，

[0186] ·存储，

[0187] ·交易，以及

[0188] ·数据库恢复管理。

[0189] 以下描述通过介绍实施例如何初始化正确的HSDS方案而集中于受实施 例影响的查询处理步骤。随后，我们描述了我们的九个加密字典的特性，它 们在顺序泄漏、频率泄漏和存储开销方面提供了不同的折衷。

[0190] 注意，实施例可以处理任意数量的选择、筛选器和不同数据类型的列。 甚至加密和明文列也可以在同一个查询中处理。为了便于解释，我们只考虑 具有选择和筛选的一个列的查询。该列的数据类型是我们的九个加密字典之 一。

[0191] 根据本示例的加密查询处理在系统设置和运行时期间根据所选的加密字 典而有所不同。

[0192] 系统设置涉及数据所有者、代理和DBaaS提供商。但是，只有数据所有 者通过依次执行以下两个步骤来发挥积极作用。

[0193] 1)SKDB←HSDS Setup(1λ)。数据所有者使用λ执行PAE Gen并输出SKDB＝PAE_Gen(1λ)。然后，数据所有者使用在成功远程证明期间建立的安全通道 与DBaaS服务器的飞地共享SKDB(如上所述)。此外，SKDB经由安全的带外 机制部署在代理上。

[0194] 2)EDB←HSDS EncDB(SKDB,PDB,dt)。然后，数据所有者获取其明文 数据库PDB，并定义每列的字典编码(dt)。可以自由选择明文字典编码或随后 定义的九个加密字典中的任何一种。九个加密字典在安全性、性能和存储消 耗方面提供了不同的折衷，应考虑列的敏感性来对其进行选择。所有具有明 文字典编码的列都被拆分成字典和属性向量，并被添加到加密数据库EDB。 加密字典的所有列也被拆分，但是字典和属性向量被进一步处理。处理取决 于加密字典的具体细节，但是该处理涉及以特定的方式对字典进行排序(以 隐藏数据顺序)，并且有可能向字典添加重复项(duplicate)(以隐藏频率)。 细节也将在后面介绍。属性向量必须根据字典中的更改进行修改，以仍然表 示与原始列相同的值。在此处理之后，数据所有者使用主要数据库密钥SKDB以及表和列名称为每个字典(SKD)导出单独的密钥。字典中的每个值都用属 于字典的SKD和随机IV下的PAE_Enc加密。所得到的字典和属性向量被添 加到EDB。

[0195] 作为设置的最后一步，数据所有者使用DBaaS提供商的导入功能来部署 EDB。

[0196] 现在讨论加密查询处理的运行时阶段。运行时从应用向代理.W.l.o.g发出 SQL查询开始。我们假设Q选择并筛选一个列。筛选可以是相等选择、反相 等选择、大于选择(包含性或排除性)、小于选择(包含性或排除性)和范围 选择(包含性或排除性)。实施例还可以处理其他查询功能，例如计数、聚合 和平均计算。

[0197] eQ←HSDS EncQuery(SKDB,Q)。作为HSDS_EncQuery的第一步，代理 将所有可能的筛选转换为范围选择。请注意，这种转换始终是可能的。例如， SQL查询SELECT FName FROM t1 WHERE FName<′Ella′，被转换为SELECT FName FROM t1 WHERE FName>＝-∞and FName<′Ella′，其中-∞是通用最 小值的占位符。如果需要最大值的占位符，则使用∞。在下文中，我们将范围 选择的范围表示为R＝(Rs,Re)，并且在我们的注释中不区分包含范围性和排 除性范围。接下来，代理使用主要数据库密钥SKDB以及表和列名称来导出 SKD。然后，它使用随机初始化向量，用PAE Enc(SKD,IV,·)加密Rs和Re。加 密范围表示为τ＝(τs,τe)。在上面的示例中，所得到的加密查询eQ是SELECT FName FROM t1 WHERE FName>＝PAE_Enc(SKDB,IV1,-∞)和FName< PAE_Enc(SKDB,IV2,′Ella′)。代理将eQ发送给DBaaS提供商。请注意，使用 概率认证加密会导致不同的范围查询，即使查询的范围实际上是相等的。

[0198] eC←HSDS_ProcessQuery(eQ)。加密查询eQ由特定于底层DBMS的处 理管道处理。管道以各种方式尝试优化查询执行的性能。我们唯一的假设是， 它最终从eQ中提取(eD,AV,τ)元组，即必须执行的加密字典、明文属性向量 和加密范围筛选。元组被传递给查询评估引擎，该查询评估引擎分两步对数 据执行范围查询。

[0199] 首先，它调用TEE函数HSDS_DictSearch(τ,eD)。在飞地内如何执行搜 索取决于筛选列的加密字典，但是飞地总是返回ValueID(vid)列表。我们将 在下面描述细节。这是DBMS与TEE交互的唯一点。

[0200] 其次，查询评估引擎扫描整个属性向量AV，寻找传递的ValueID(vid)。 每个值AV.vid∈AV都必须与vid中的所有值进行比较，这可能会导致许多比 较。然而，此时使用整数比较，这提高了性能，并且扫描是高度并行的。除了 稍后解释的小调整，这个函数对于所有加密字典都是相等的。这一步会得到 AV中所有匹配的条目的RecordID rid列表。

[0201] 如果还应该对同一表中的另一列执行范围查询，则该列表将用于预筛选 该同一表中的另一列。此外，如果在另一列上执行选择，将使用该列表。在我 们的情况下，单个加密结果列eC(＝eC)是通过撤消对rid中所有条目进行拆 分成字典和属性向量而创建的，即eC＝(D.vj|j＝AV.vidi∧i∈rid)。最后，eC 用列元数据(表和列名称)进行了丰富，并将其传递回给代理。

[0202] C←HSDS_DecRes(SKDB,eC)。代理从DBaaS提供商接收(在我们的示 例中)一个加密列eC，并使用附加的列元数据来导出列特定的密钥SKD。eC 中的每个条目都用SKD单独解密，得到一个明文列C。C(＝C)被传递回对于 其整个过程是透明的应用。

[0203] 现在描述根据这个特定示例的加密字典。实施例的目标是向数据所有者 提供性能、安全性和存储消耗之间的灵活折衷。

[0204] 在这个特定的示例中，提供了九个不同的加密字典。图5呈现了九个加 密字典的概述，表示为ED*。

[0205] 数据所有者可以在设置阶段期间选择在列粒度上应使用哪个加密字典。 以两个不同的安全性维度来设计加密字典：

[0206] (1)顺序泄漏等级；和

[0207] (2)频率泄漏等级。

[0208] 换句话说，攻击者能够了解多少关于加密数据的其顺序的方面的情况， 以及多少关于其频率的情况。这两种泄漏都可以用于对加密数据的不同攻击。

[0209] 加密字典被表示为ED*.°，其中*和°分别表示三种不同的频率和顺序泄漏 等级。三个加密字典ED*.1为顺序泄漏提供了折衷，但泄漏了频率。三个ED*.2 减少了不同顺序泄漏折衷下的频率泄漏。三个ED*.3抑制了频率泄漏。

[0210] 九个加密字典在三个位置处不同地处理：

[0211] (1)在数据所有者处创建加密字典期间(HSDS_EncDB)，

[0212] (2)在飞地内的字典搜索期间(HSDS_DictSearch)，以及

[0213] (3)在属性向量搜索由HSDS_DictSearch返回的ValueID期间。

[0214] 这些细节是下面讨论的重点，因为剩余的处理对所有加密字典都是相同 的。

[0215] 现在详细描述ED*.1。这包括具有三种不同级别的顺序泄漏的三个不同 的加密字典：ED1.1、ED2.1和ED3.1。对于这些值，字典仅包括每个值一次， 因此提供了字典编码可能的理想压缩率。

[0216] 缺点是攻击者可以将字典和属性向量组合到列C中。C中的每个值都是 加密的(用概率加密)，但是攻击者仍然可以获知每个加密值的频率。加密字 典ED*.2和ED*.3的描述中解决了此问题。

[0217] 对于ED1.1，如前所述，数据所有者将PDB的所有列在HSDS_EncDB中 被拆分为字典D和属性向量AV。ED1.1的基本思想是在该加密字典的字典创 建过程(HSDS_EncDB_1.1)中按字典顺序对D进行排序。AV中的ValueID 被相应地设置。图6呈现了ED1.1的字典编码的示例。

[0218] 图7显示了过程1。该过程1呈现了HSDS_DictSearch_1.1， HSDS_DictSearch_1.1是在ED1.1的飞地内执行的函数。该函数获得加密范围 τ和加密字典eD作为输入。首先，该过程1使用表和列名称来生成SKD，并 使用SKD来分别解密范围的开始和结束。然后，该过程1分别对范围的开始 和结束执行最左边和最右边的二进制搜索。这些二进制搜索几乎像教科书二 进制搜索一样执行：将搜索值与给定数组的中间元素进行比较；不再考虑搜 索值不能在其中的那一半；在具有中间元素的另一半中继续搜索，并重复这 一过程，直到找到(最左边或最右边的)搜索值或确定它不存在。唯一的区别 是中间值存储在不可信存储器中，并且在我们的示例中是加密的。

[0219] 在与搜索值进行比较之前，飞地将SKD加载到飞地中并在那里对SKD进 行解密。这导致对数数量的加载、解密和比较操作(相对于D的大小)。最左 边和最右边的搜索以及是否找到值的信息(在过程中没有提到)对于处理值 不存在的情况是必要的。

[0220] 作为与通用HSDS_DictSearch的微小偏差，HSDS_DictSearch_1.1返回 ((eD.vstart,eD.vend)——被搜索的范围开始和结束的字典索引——而不是所有 匹配的ValueID(vid)。

[0221] 请注意，此操作只需要较小的恒定飞地存储器。这与字典的大小无关。 所有其他加密字典的HSDS_DictSearch也是如此。

[0222] 如前所述，HSDS_ProcessQuery使用HSDS_DictSearch的结果线性扫描 AV。所解释的偏差的好处是，HSDS_ProcessQuery只需检查每个值是否在 eD.vstart和eD.vend之间，而不是将其与每个匹配值进行比较。这将对性能产生 重大影响，尤其是在eD.vstart和eD.vend之间的距离很大的情况下。 HSDS_ProcessQuery的其余部分如前所述执行。

[0223] ED1.1具有最高的顺序泄漏，因为攻击者知道最小(和最大)值是什么， 尽管数据是用PAE加密的。

[0224] 对于ED2.1，基本思想是在HSDS_EncDB_2.1期间对D进行排序和随机 包装。换句话说，ValueID被轮转(rotate)了一个值，我们称之为WrapIndex modulo D.#v。图8示出了其中使用WrapIndex 3的示例。例如，“Jessica”在 排序的字典中具有ValueID2。在包装字典中，ValueID为1(＝(2+3)％4)。

[0225] 数据所有者用SKD和随机IV下的PAE加密WrapIndex。所得到的 encWrapIndex作为列的元数据附加到EDB。

[0226] 在这种情况下，飞地内部的处理更加复杂。如图9所显示，过程2对此 进行了说明。

[0227] 除了范围的解密之外，encWrapIndex也被解密。然后，二进制搜索的一 个特殊变体被称为范围的开始和结束，我们将在下面进行解释。搜索结果是 最小索引vidmin和最大索引vidmax，这将被进一步分析。如果两者都低于或高 于WrapIndex，函数将返回一个从vidmin到vidmax的范围。唯一的其他可能性 是vidmin高于WrapIndex并且vidmax低于wrap index。vidmin等于eD.#v表示在 D中找不到范围开始，但它高于D.v(D.#v)-1处的值。在这种情况下，将返回从 零到vidmax的ValueID范围。在最后一种情况下，vidmin大于vidmax，这表明结 果范围超过了ValueID的包装范围。因此，必须返回两个ValueID范围：(0, vidmax)和(vidmin,eD.#v-1)。

[0228] 对于ED2.1类型的列，HSDS_ProcessQuery必须检查每个值AV.vid∈AV 是否在一个(或两个)ValueID范围之间。

[0229] 图10中示出的过程3呈现了特殊二进制搜索的细节，对范围开始和结束 的处理略有不同。目标是执行具有与未包装的字典上的二进制搜索相同的访 问模式的二进制搜索。原因是通过考虑WrapIndex简单地访问轮转的中间的 常规的二进制搜索将直接泄漏WrapIndex。这将完全阻碍额外的保护。

[0230] 特殊二进制搜索使用一种编码，其将任意值转换为整数表示，保留字典 式数据顺序。这是通过将每个字符单独转换成固定长度的整数，并将它们连 接成一个结果整数来实现的。例如，AB的编码将是3334，BA将导致3433。 编码整数被额外填充到最大长度的任何可能明文。对于最大长度为5，AB的 编码和填充版本为3334000000。在大多数数据库中，列的最大宽度是清楚的， 因为数据所有者必须在定义列的过程中定义它。例如，数据所有者定义字符 串列可以包含30个字符或64位整数。飞地能够访问此列元数据。

[0231] 在初始化搜索的低值和高值之后，该过程对D可能包含的最高值进行编 码，从而得到N。这是可能的，因为列的最大宽度是已知的。接下来，对D 中的第一个值进行解密和编码，得到r，并且搜索值sVal也被编码。从sVal 中减去r，如果WrapIndex不为零，则结果取模N。由于WrapIndex是随机的， 这可能会发生。搜索期间访问的所有中间值都以相同的方式处理。

[0232] 请注意，编码是即时完成的，不会存储结果。该操作的运行时开销很小， 并且节省了存储空间。

[0233] 包装减少了数据顺序泄漏，因为攻击者通过查看D不知道最小值(和最 大值)在哪里。请注意，每列的包装是独立的，因为数据所有者会为每列绘制 随机的WrapIndex。

[0234] 转到ED3.1，字典未排序。在HSDS_EncDB_3.1期间，来自PDB的每个 值都在随机位置插入到D中。创建AV以匹配原始列。图11显示了加密字典 ED3.1的示例。

[0235] 该加密字典ED3.1的优点是它完全隐藏了数据顺序。但是，它有缺点， 即它阻止在HSDS_DictSearch_3.1期间使用任何对数运行时搜索。

[0236] 相反，在用SKD解密τ后，必须对eD中的所有值进行线性扫描。这显示 在图12的过程4中。这包括将每个条目加载到飞地中，解密它，并检查它是 否落入该范围。结果是ValueID vid列表。

[0237] HSDS_ProcessQuery必须将每个RecordID AV.vid与vid中的每个值进行 比较。如果vid包含许多ValueID，这些比较的数量就会变大。然而，在这一 点上使用整数比较，并且它是高度可并行化的。

[0238] 现在描述ED*.2。上面，我们查看了具有不同级别的顺序泄漏的三个不同 的加密字典(ED*.1)。现在，我们解释当前的频率泄漏，并研究减轻它的方 法。我们提出了一种可参数化的机制，它可以在HSDS_EncDB期间应用于 ED1.1、ED2.1和ED3.1。随后，我们解释了需要对HSDS_DictSearch_X:1进 行的小修改。这得到了另外三个加密字典：ED1.2、ED2.2和ED3.2

[0239] 一种观点认为每个加密字典eD都包含加密值eD.v，但是每个明文值只 以唯一的ValueID呈现一次。攻击者可以通过扫描AV以获得ValueID i，轻 松计算出eD.vi在列中出现的频率。这种频率泄漏可能被用来揭示底层明文值。 作为一种对策，我们建议在HSDS_EncDB期间，基于概率机制，将明文多次 插入到D中，我们称之为均匀频率平滑(Uniform Frequency Smoothing，UFS)。

[0240] 对于HSDS_EncDB，数据所有者将每个C∈PDB拆分成字典D和属性向 量AV。C有un(C)个唯一值，并且到目前为止，每个值只插入D恰好一次。 现在，数据所有者对C中的每一个唯一值进行随机实验，以确定它被插入到 D中的频率以及这些“重复项”中的每个被AV引用的频率。我们说明文值v 被拆分成多个储存桶(bucket)，每个储存桶都有特定的大小。

[0241] 作为随机实验的输入，数据所有者对相同值v∈C(oc(C.v))出现的次数进 行计数。此外，他还定义了储存桶的最大大小(bsmax)。

[0242] 图13所显示的过程5详细呈现了随机实验。额外储存桶的随机大小从离 散均匀分布U{1，bsmax}中选取，直到总大小高于oc(C.v)。然后设置最后一个 储存桶的大小，使总大小与oc(C.v)相匹配。实验返回储存桶大小(bssizes)和 选择了多少储存桶(#bs)。

[0243] 根据#bs，数据所有者将重复项插入D。然后，他扫描C中以获得所有重 复项。对于每一个匹配的C.vi，他随机地在AV.vidi中插入#bs个可能的ValueID 中的一个。同时，他考虑每个ValueID的使用频率，这是由bssizes定义的。

[0244] 对于ED1.2，D中的值随后被排序。对于ED2.2，它们被排序和包装。对 于ED2.3，它们被随机改组(shuffle)。属性向量会相应调整。图14显示了 bsmax＝3和WrapIndex＝1的ED2.2的示例。

[0245] 最后，D中的所有值都用PAE.Enc加密。由于初始化向量是为每个值随 机选取的，密文是不同的，即使明文是相等的。

[0246] 关于HSDS_DictSearch，只需调整飞地内的一个字典搜索，以支持字典中 存在重复项。HSDS_DictSearch_1.2＝HSDS_DictSearch 1.1，因为已经使用了 最左边和最右边的二进制搜索。因此，它会自动找到潜在重复块的开始和结 束。另外，HSDS_DictSearch_3.2＝HSDS_DictSearch_3.1，因为线性扫描会找 到D中的所有重复项，并将它们添加到vid中。

[0247] HSDS_DictSearch_2.2变得更加复杂，因为它必须处理拐角情况。原因是， D中最后一个和第一个条目的明文值可能相等(如图14所示的示例)。因此， 在HSDS_DictSearch_2.2中，vidmin和vidmax的后处理变得更加复杂。

[0248] 现在讨论bsmax影响。数据所有者可以根据自己的要求自由选择列粒度的 bsmax。选择的值影响多个维度：

[0249] (1)存储成本，

[0250] (2)性能，以及

[0251] (3)频率泄漏。

[0252] 例如，一个小的bsmax会导致D内部的许多重复条目。首先，必须存储 这些重复项，这会对字典编码提供的压缩率产生负面影响。其次，在飞地内 的HSDS_DictSearch期间，需要更多的数据加载、更多的解密和更多的比较。 ED1.2和ED2.2在这方面只有对数增长，因为使用了二进制搜索。ED2.3中 的线性扫描受它影响。第三，频率泄漏很低，因为频率是平滑的，因为每个 ValueID出现的次数保证在1和(低)bsmax之间。大的bsmax有相反的效果。

[0253] 现在讨论ED*.3。我们刚刚介绍了UFS，平滑频率泄漏的概念。现在，我 们讨论完全阻止频率泄漏的完美频率平滑(Perfect Frequency Smoothing，PFS)。 构思很简单：对于原始列中的每个值将自己的条目添加到字典中。这可以在 HSDS_EncDB期间用于ED1.1、ED2.1和ED3.1，从而导致ED1.3、ED2.3和 ED3.3。

[0254] 对应的字典搜索与ED*.2中的相等，因为重复项的数量只是“更高”。 事实上，通过将bsmax设置为1，PFS可以被解释为UFS的特例。因此，优点 和缺点与针对小bsmax的优点和缺点相同。特别是字典编码提供的压缩已经不 再存在了，但是每个ValueID的频率完全相等。

[0255] 现在描述动态数据方面。到目前为止，我们只讨论了由数据所有者准备 的静态数据，然后上传到DBaaS提供商，DBaaS提供商使用以字典加密为特 征的存储器内数据库。对于大多数分析场景来说，这就足够了，因为大容量 数据加载通常在这种情况下使用，复杂的只读查询会在之后执行。

[0256] 在下文中，我们将介绍这样的方法，该方法关于如何在需要时允许插入 数据。我们建议利用称为增量存储(Delta Store)(或差异缓冲区)的概念来 允许写入查询，例如插入、删除和更新。该构思是将数据库(特别是每一列) 拆分成读取优化主存储和写入优化增量存储。

[0257] 列中的更新不会更改现有行。相反，所有数据更改都在增量存储中执行。 简单地附加新值。更新的值通过使用两个存储概念的有效性向量来处理。该 向量存储每个条目的值是否有效。删除可以通过对有效性位进行更新来实现。 该列的整体状态是两个存储的组合。因此，读取查询变得更加复杂：它在两 个存储上正常执行，然后在检查条目有效性的同时合并结果。增量存储应该 保持比主存储小几个数量级，以便有效地处理读取查询。这是通过定期将增 量存储的数据合并到主存储中来实现的。

[0258] 对于特定实施例，任何加密字典都可用于主存储，并且ED3.3可用于增 量存储。新条目可以通过用随机IV重新加密飞地内的传入值简单地附加到 ED3.3类型的列中。通过执行HSDS_DictSearch_3.3定义的线性扫描，可以实 现在该增量存储中的搜索。因此，在插入和搜索过程中，数据顺序和频率都 不会泄漏。ED3.3的缺点是它具有高存储器空间开销和低性能。然而，定期合 并缓解了这个问题。飞地必须处理合并过程：重新加密D中的每个值，重新 包装ED2.°类型列的值，以及改组ED3.°。该处理必须以不泄漏新旧主存储中 值之间关系的方式实施。

[0259] 现在描述这个说明性示例的具体实施方式。对于我们的实验，我们实施 了基于MonetDB的原型，MonetDB是开源的面向列的存储器内数据库DBMS。 MonetDB专注于以读取为主的分析工作负载，并且因此适合我们的使用场景。 它是成熟的关系DBMS，其被设计用于利用现代计算机系统的大主存储器进 行处理，并其利用磁盘存储以获得持久性。

[0260] MonetDB对所有字符串列使用字典编码的变体。与前面描述的编码相比， MonetDB采用了更复杂的方法。

[0261] 属性向量仍然包含字典的偏移，但是字典按照其插入的顺序包含数据(对 于非重复项)。如果字典很小(小于64kB)，则完全消除重复项，并使用哈希 表和冲突列表来定位条目。如果字典变大，则不再使用冲突列表。因此，字典 可能会多次存储值。总的来说，开发人员已经创建了被读取优化并且也直接 支持写入操作的字典。

[0262] MonetDB的前端查询语言是SQL。所有查询都被解析、验证并转换为后 端查询语言，称为MonetDB汇编语言(MonetDB Assembly Language，MAL)， 并且所有的SQL数据类型都被转换为MonetDB内部的ATOM数据类型。在 这个示例中，我们向MonetDB添加了九个SQL类型，它们对应于上面呈现 的九个不同的加密字典。基础数据类型是字符串。它们可以像任何其他数据 类型一样在SQL创建表语句中使用，例如CREATE TABLE t1(c1 ED1.1,c2 ED3.2,...)。因此，数据所有者可以针对每一列灵活地在顺序泄漏和频率泄漏 之间选择适合的折衷方案。我们还在MonetDB的数据库内核中引入了九个新 的ATOM数据类型，以在传入的查询转换为MAL后处理这些查询。

[0263] 我们进一步将每个字典拆分为加密字典的字典头和字典尾。字典尾包含 可变长度值，该可变长度值在GCM模式下用AES-128加密。这些值以随机 顺序依次存储。字典头包含相对于字典尾的固定大小偏移，并且这些值根据 具体加密数据类型排序。

[0264] 进行这种拆分是为了支持可变长度数据，同时允许执行高性能的二进制 搜索。对于字典搜索，我们将指向加密字典头和字典尾的指针传递到飞地中， 并且字典搜索直接从不可信主机进程加载数据。因此，只需要一个上下文切 换。

[0265] 虽然前面的示例侧重于结合面向列的数据库实施，但这不是必需的。替 代实施例可以结合面向行的数据库结构来实施。

[0266] 图15示出了根据实施例的被配置为实施字典加密的存储器内数据库的 专用计算机器的硬件。特别地，计算机系统1701包括处理器1702，其与包括 数据库1703的非暂时性计算机可读存储介质进行电子通信。该计算机可读存 储介质上存储有对应于引擎的代码1705。代码1704对应于属性字典数据。代 码可以被配置为引用存储在非暂时性计算机可读存储介质的数据库中的数据， 例如可以存在于本地或远程数据库服务器中的数据。软件服务器一起可以形 成计算机系统的集群或逻辑网络，这些计算机系统用软件程序编程，这些软 件程序相互通信并一起工作以处理请求。

[0267] 图16示出了示例计算机系统1800。计算机系统1810包括总线1805或 用于传送信息的其他通信机制，以及与总线1805耦合用于处理信息的处理器 1801。计算机系统1810还包括耦合到总线1805的存储器1802，用于存储将 由处理器1801执行的信息和指令，包括例如用于执行上述技术的信息和指令。 该存储器还可以用于在处理器1801执行指令期间存储变量或其他中间信息。 该存储器的可能实施方式可以是但不限于随机存取存储器(RAM)、只读存储 器(ROM)或两者。还提供存储设备1803用于存储信息和指令。存储设备的 常见形式包括，例如，硬盘、磁盘、光盘、CD-ROM、DVD、闪存、USB存 储器卡或计算机可以读取的任何其他介质。例如，存储设备1803可以包括源 代码、二进制代码或用于执行上述技术的软件文件。存储设备和存储器都是 计算机可读介质的示例。

[0268] 计算机系统1810可以经由总线1805耦合到显示器1812，诸如阴极射线 管(CRT)或液晶显示器(LCD)，用于向计算机用户显示信息。诸如键盘和 /或鼠标的输入设备1811耦合到总线1805，用于从用户向处理器1801传送信 息和命令选择。这些组件的组合允许用户与系统通信。在一些系统中，总线 1805可以被分成多个专用总线。

[0269] 计算机系统1810还包括与总线1805耦合的网络接口1804。网络接口 1804可以提供计算机系统1810和本地网络1820之间的双向数据通信。例如， 网络接口1804可以是数字用户线路(digital subscriber line，DSL)或调制解 调器，以通过电话线提供数据通信连接。网络接口的另一个示例是局域网 (LAN)卡，用于提供到兼容LAN的数据通信连接。无线链接是另一个示例。 在任何这样的实施方式中，网络接口1804发送和接收携带代表各种类型信息 的数字数据流的电、电磁或光信号。

[0270] 计算机系统1810可以通过本地网络1820、内部网或互联网1830通过网 络接口1804发送和接收信息，包括消息或其他接口动作。对于本地网络，计 算机系统1810可以与多个其他计算机机器通信，诸如服务器1815。因此，计 算机系统1810和由服务器1815代表的服务器计算机系统可以形成云计算网 络，该云计算网络可以用本文描述的过程编程。在互联网示例中，软件组件 或服务可以驻留在网络上的多个不同的计算机系统1810或服务器1831-1835 上。例如，上述过程可以在一个或多个服务器上实施。服务器1831可以通过 互联网1830、本地网络1820和网络接口804从一个组件向计算机系统1810 上的组件传输动作或消息。例如，上述软件组件和过程可以在任何计算机系 统上实施，并且通过网络发送和/或接收信息。

[0271] 上面的描述说明了本发明的各种实施例以及如何实施本发明各方面的示 例。上述示例和实施例不应被认为是唯一的实施例，并且呈现这些示例和实 施例是为了说明由所附权利要求限定的本发明的灵活性和优点。基于以上公 开和以下权利要求，其他布置、实施例、实施方式和等同物对于本领域技术 人员来说将是显而易见的，并且可以在不脱离由权利要求限定的本发明的精 神和范围的情况下使用。