1 专利名称

一种基于可信执行环境的数据库密态索引访问方法、系统及介质

2 技术背景

• 全密态数据库：一种由数据库提供的安全特性，指数据库在处理数据的过程中，确保数据在传输、计算、存储等全生命周期阶段，于任何不可信的介质或环境中，始终处于加密状态。
• 全密态数据库实现方案：目前，业界较成熟的方案，是基于可信执行环境，实现全密态数据库，该方案主要分为2个模块：1)驱动加密：应用向数据库发送SQL语句时，应用侧的数据驱动自动加密SQL语句中的数据，数据库接收与处理数据密文。2)机密计算：数据库无法再密文上进行计算，将密文发送至可信执行环境（TEE）中，由可信模块完成解密与计算。
• 数据库索引结构：数据库中，最常见的索引为b+树索引。以tpcc测试模型为例，数据量低于100亿条时，b+树一般不超过4层。每一层的节点，即索引节点，是固定大小的page，分root index-page，internal index-page，leaf index-page。1个index-page中，存储多个index-item。其中，root和internal index-page中的index-item，存储数据和下一层index-page的位置。leaf index-page中的index-item，存储数据和table-page的位置。
• 加密性能：在加解密数据时，影响加密性能的因素中，加密次数的影响远高于数据长度。例如，1次加密8k数据，比40次加密200字节数据的性能高10+倍。
• 密态索引：在全密态数据库中，数据库只存储数据密文，在等值、范围查询等场景，为提高查询效率，避免全表扫描，需要在密文上构造索引。因此，需要见密文传输至可行执行环境TEE中，在TEE中临时解密数据，比较数据大小，构造索引。
• 现有方案缺陷：在构造密态索引时，现有方案存在以下缺陷：1)交互开销高：以索引元组为粒度，与TEE交互，交互次数多，交互开销高。2)加解密开销高：在索引页内比较元组大小时，需要多次解密索引元组。对于顶层的索引页，访问评率高，加解密频率也较高。3)内核修改多：为适配TEE，对索引构造、索引查询、并发控制等修改多，破坏生态兼容性等。

3 发明内容

• 发明目的：本发明针对在密文数据上构造索引、扫描索引的场景，提供一种通用的、高性能、低改造的方案，基于可信执行环境，大幅降低交互开销、加解密开销，并且，充分复用索引分裂、并发访问的机制，对内核侵入修改度低。

• 技术方案：
  本发明的关键创新如下：

1. 构造索引：应用插入数据时，驱动以字段为粒度，加密数据。数据库接收数据密文，TEE解密数据，构造索引，并以索引页为粒度，重新加密数据。
2. 访问索引：结合索引的访问特点，每个index-item不独立加密与解密，每次以index-page为粒度加密与解密，降低加解密次数。
3. 发送索引：数据库向TEE发生索引时，每次以index-page为粒度发送，降低交互次数。
4. 缓存索引：在TEE中，针对索引中root和internal page访问频率高、修改频率低的特点，缓存解密后的page，降低解密次数、与TEE的交互次数。
5. 内核改造：数据库中，访问索引时，只在需要比较大小时，才与TEE交互，保留已有索引分裂、并发访问机制。

以tpcc模型为例，当warhouse为10000时：

• 基表：bmsql_customer表中，数据行数为3亿，表大小约250G
• 索引：bmsql_customer主键索引中，index-item数为3亿，索引文件大小约9.5G，索引层数为4层，每层page数量分别：1、17、4400、114万，每个page中page-item数量约260个。插入1条数据，index-page平均分裂次数为0.0034次。

在该场景中，使用本发明的方案，考虑index-page分裂、TEE缓存偶尔未命中等所有可能产生额外交互、加密、解密的情况下：

4 附图及附图的简单说明

4.1 密态索引结构

密态索引中，所有index-page中，只存储数据密文。在TEE中，以page为粒度加密，PageHeader、PageTail中，不存储用户数据，无需加密。
此处，以一个简单的3层索引为例，展示明文索引、密态索引的区别：

4.2 密态索引插入流程

在图1的示例中，向索引中插入1条数据，流程如下：

上述流程中，步骤12至20可通过缓存优化。以tpcc为例，index-item为3亿时，索引层数为4，索引文件大小约9.5G，root page数为1，internal page数为17+4000，缓存大小为31.38MB。

5 具体实施方式

5.1 创建密态索引

1. 管理员：创建密钥 CREATE DATA KEY dk1(..);
2. 数据库驱动：通过密钥服务或密码机生成密钥，缓存密钥，向数据库发送密钥信息
3. 数据库：在系统表中，存储密钥信息，包括：密钥名、密钥Oid等。
4. 管理员：创建加密表和索引：CREATE TABLE t1(c1 INT ENCRYPTED BY dk1, c2 TEXT)，CREATE INDEX i1 ON t1(c1);
5. 数据库：存储加密信息，包括：表名、列名、密钥名等。

5.2 向索引插入1条数据

1. 前置条件：已创建密态索引
2. 应用：连接数据库
3. 数据驱动：连接数据库，查询加密信息、密钥信息，并缓存
4. 数据库驱动：从密钥服务或密码机获取密钥，与可信执行环境建立安全通道，并传输密钥
5. 可信执行环境：缓存密钥
6. 应用：向数据库存储数据：INSERT INTO t1 VALUES (13, ‘data1’);
7. 数据库驱动：对SQL进行语法解析，识别加密列字段，并加密字段，并改写SQL：INSERT INTO t1 VALUESS (cipher[13], ‘data1’);
8. 数据库：向基表t1插入数据(cipher[13], ‘data1’)，准备构造索引
9. 数据库：向TEE中，发送密文 cipher[13]
10. 可信执行环境：解密cipher[13]，获取明文(13)
11. 可信执行环境：查找缓存的root page，如果未找到，请求数据库发送root page，解密并缓存root page
12. 可信执行环境：在root page中，二分查找，获取internal page位置
13. 可信执行环境：查找缓存的internal page，如果未找到，请求数据库发送internal page，解密并缓存internal page
14. 可信执行环境：在internal page中，二分查找，获取leaf page位置
15. 可信执行环境：请求数据库发送leaf page。解密leaf page
16. 可信执行环境：如果leaf page已满，触发分裂流程，此处不展开说明
17. 可信执行环境：在leaf pag中，二分查找，获取插入位置
18. 可信执行环境：在leaf page中，插入数据(13, 基表t1中13的存储位置)
19. 可信执行环境：加密leaf page，向数据库返回加密后的leaf page
20. 数据库：重新存储加密后的leaf page

5.3 从索引中查找1条数据

查询流程，与插入流程大部分一致：

1. 前置条件：已创建密态索引
2. 应用：连接数据库
3. 数据驱动：连接数据库，查询加密信息、密钥信息，并缓存
4. 数据库驱动：从密钥服务或密码机获取密钥，与可信执行环境建立安全通道，并传输密钥
5. 可信执行环境：缓存密钥
6. 应用：从数据库中查询数据：SELECT * FROM t1 WHERE c1 = 13;
7. 数据库驱动：对SQL进行语法解析，识别加密列字段，并加密字段，并改写SQL：SELECT * FROM t1 WHERE c1 = cipher[13];
8. 数据库：向TEE中，发送密文 cipher[13]
9. 可信执行环境：解密cipher[13]，获取明文(13)
10. 可信执行环境：查找缓存的root page，如果未找到，请求数据库发送root page，解密并缓存root page
11. 可信执行环境：在root page中，二分查找，获取internal page位置
12. 可信执行环境：查找缓存的internal page，如果未找到，请求数据库发送internal page，解密并缓存internal page
13. 可信执行环境：在internal page中，二分查找，获取leaf page位置
14. 可信执行环境：请求数据库发送leaf page。解密leaf page
15. 可信执行环境：在leaf pag中，二分查找，获取数据(13)对应的索引项
16. 可信执行环境：从数据(13)对应的索引项中，获取基表t1中对应的位置
17. 可信执行环境：向数据库返回基表t1中(13)的存储位置
18. 数据库：从基表t1中，获取数据(13)对应的数据(cipher[13], ‘data1’)
19. 数据库：向数据库驱动返回数据(cipher[13], ‘data1’)
20. 数据库驱动：接受(cipher[13], ‘data1’)，解密cipher[13]为数据(13)
21. 应用：获取数据(13, ‘data1’)