韩立毛， 赵跃华， 朱伟玲

(①盐城工学院 信息工程学院，江苏 盐城 224051；②江苏大学 计算机科学与通信学院，江苏 镇江 212013)

0 引言

在嵌入式系统中，物理存储空间是除了CPU之外最基本、最重要的资源，在系统中的管理效率对于整个系统的效率起着决定性的作用，内存和外存中存放的数据是安全嵌入式数据库管理系统 (ESDBMS，Secure and Embedded Database Management System)的重要保护对象。所以，如何高效地管理内存和外存空间，如何尽快的查找到数据库文件中的有用信息，如何实现存储管理的安全性等[1]，这些都是设计和实现ESDBMS安全后端模块需要解决的问题。安全后端模块作为与嵌入式操作系统联系紧密的模块，如何使其不受平台影响，也是需要解决的问题。

1 安全后端模块的框架设计

安全后端模块的设计采用分层设计的思想，屏蔽掉各层之间的差异性，实现高层向低层的透明调用，这样有利于降低层次之间的耦合度。对于ESDBMS的其它功能模块，它们可以透明地调用安全后端模块最高层提供的标准接口，而不需要了解安全后端模块的底层实现机制，这样有利于安全后端模块的拆卸和扩充[2]，有利于实现ESDBMS整体的模块化。

1.1 安全后端模块的框架结构

安全后端模块处理的主要是存储管理及其安全性的问题，它的框架结构设计如下页图1所示。

1.2 安全后端模块的子模块划分

表和索引管理子模块。通过使用B+树对页面组织管理，对页面空间进行分配和回收，以利于高效存储、查找与组织元组。对执行回收操作页面内容的清除也是本模块的任务[3]。

Cache管理子模块。主要是在内存和外存之间移动页面并对页面进行管理。如何组织Cache中的页面，如何对Cache中的页面进行读、写、替换操作，这些是此模块所要解决的重点。在将Cache中的内容提交给文件系统后，需要及时清除Cache中所包含的内容，这就是客体重用的任务。Cache管理子模块实现如何把以字节为存取单位的文件提取为以页为单位存取的文件。B+树将目标元组所在页码传送给Cache管理子模块，Cache管理子模块返回一个指向该元组所在页的指针。

加密子模块。通过加密，当非法用户通过用户认证进入系统获得存储在数据库中的数据时，得到的只是密文，依然无法理解其含义。

0S接口。则用来屏蔽不同操作系统间的差异，从而为上层提供一种抽象层，以方便将来能运行于其它的操作系统上。

图1 安全后端模块框架结构

2 安全后端模块的子模块设计

2.1 Cache管理子模块

2.1.1 Cache管理方案的选取与Cache的组织

Cache管理方案的选取[4]。Cache管理子模块是本地文件系统和其它上层模块之间的中间模块，它是通过本地操作系统IO API访问本地数据库和日志文件的模块，即定义一个易于使用、独立于文件系统的接口，用来从数据库文件中访问页面。表和索引管理子模块总是通过Cache管理子模块来访问数据库，并且从来不直接访问数据库或者日志文件，它将数据库文件视为页面的逻辑结构。

对每个数据库文件来说，在文件和Cache之间移动页面是页面缓冲管理作为Cache管理器的基本功能。页面的移动对表和索引管理子模块和更高层次的模块来说是透明的。为了提高数据库的运行速度，本系统利用哈希表来组织内存中的页。

Cache的组织。利用哈希表来组织Cache页，为了区分内存和外存中的页，在外存中的页为Page，在内存中的页为Slot，即任何的Slot可以存储任何的Page。哈希表最初是空的，随着页面要求的不断增加，Cache管理子模块建立新的Slot并且把Slot插入到哈希表中。

Cache管理子模块的功能就是将用户所需要的数据项从数据库文件中读入内存，并在内存中操作，如果有需要，再把它写回数据库文件。这种功能可以归结为Cache读操作、Cache写操作和Cache替换操作。

2.1.2 Cache管理子模块中客体重用的实现

客体重用安全机制对废弃的客体进行“漂白”操作，实现起来比较简单。设计客体重用安全机制最关键的是执行时机的选择，对于一般安全嵌入式数据库管理系统而言，可以在客体释放、存储空间回收、存储空间分配等时刻执行该安全机制。

由于内存管理和文件系统的存储介质的物理特性存在很大的区别，所以内存管理和文件系统中执行该安全机制的时机是不同的。对于内存管理，根据其具体设计，在Cache回收时执行“垃圾”内存块的擦除操作。即在Cache读、写和替换函数中插入Cache擦除操作函数来实现该安全机制。

2.2 表和索引管理子模块

Cache管理子模块实现把以字节为存取单位的文件提取为以页为存取单位的文件，在这里主要实现把以页为单位存取的文件提取为以元组为单位存取的文件。

2.2.1 元组组织方式的选取

一个表格或者索引的元组可以以多种方式组织，如线性表、B树等。对于顺序结构而言，若元素已按关键字排序，则可采用更高效的检索法，如折半检索。但是若元素没有按关键字排序，在作插入和删除时，需移动大量元素，付出很高的时间代价。对于链式存储来说，它虽然没有顺序存储的缺点，但随机存储性差。

B-树是目前为止基于DBMS的外部存储的最重要的索引结构。B-树是存储搜集类似数据记录，并通过它们的键排序次序的一种组织方法。B-树是一种深度平衡的树，所有的Leaf节点在同一个水平。搜索信息存储在Internal节点和Leaf节点。B-树提供所有树操作中最适宜的性能，比如插入、删除、搜索和搜索下一个。B+树具备B-树所有的优点，只将所有的元组存储于Leaf节点，而不是像B-树那样将元组存于Leaf和Internal节点。B+树中，元组是成对的，包括键值和数据值，它们按健值排序。Internal节点只包含搜索信息和孩子指针，键是按排序存储的，它们用来直接搜索孩子节点。

安全后端模块元组的组织方式选择B+树结构。B树结构显然比线性表结构查询快捷，而实时性是嵌入式系统在对其他方面没有大影响的前提下，首要考虑的因素，故选择B树结构。由于B+树所有的元组都存放在Leaf页中，Internal页只存储搜索信息和孩子指针。这样就将Leaf页和Internal页的管理简单化，降低设计难度。B-树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同，最小时间复杂度为1，而B+树的时候复杂度对某建成的树是固定的。

2.2.2 元组组织方式设计

ESDBMS通过分配根页来创建一棵树。每一棵树通过它的根页号码来区分，号码存储在主目录表中，主目录表的根始终在Page 1。ESDBMS的tree节点包括Internal节点和Leaf节点，如下页图2所示。元组内容是Leaf页的一部份，每个元组的键和数据组成Payload，如果Payload超过了此页的大小，那么就将其溢出至Overflow Page。

2.2.3 元组的分配和回收

表和索引管理子模块帮助安全数据库引擎模块把所有的表和索引组织成B+树。每棵树由一个或多个数据库Page组成。数据库引擎能存储和搜索任何树中可变长度的元组，在任何时候删除树中的元组。表和索引管理子模块可在任意时候从数据库引擎收到插入和删除记录的要求。一个插入操作需要在Tree Page和Overflow Page中分配空间。一个删除操作清空Tree Page和Overflow Page中占据的空间。管理空闲空间对于有效分配和回收空间是至关重要的。空闲空间主要包括Free Page的空闲空间和Tree Page的空闲空间。

元组分配：空间分配运算不分配小于4个字节的空间，请求分配的的空间都应大于或等于4。假设请求分配nRequired个字节，这nRequired个字节来自一个Page，当这个Page总共有nFree个字节。如果nRequired〉nFree，则请求失败。如果nRequired≤nFree，则进行分配；如果在本页中无法存储，那就对此树扩充，从Freelist上取下一个Page，添加到树上。

元组回收：假设一个请求来了，要求释放由先前分配的nFree个字节。分配算符创建一个nFree个字节的空闲块，在适当的位置把它插入到空闲块列表中。此时，它开始在附近合并释放空闲块。如果在邻近的空闲块中有一个碎片，它就把块和碎片合并。如果空间块在指针队列和元组内容之间的未分配区域就将其回收至此。

2.2.4 表和索引管理子模块中客体重用安全机制的实现

由于内存管理和文件系统中执行客体重用安全机制只是时机的不同，故内存中客体重用机制的实现方法与文件系统中这种安全机制的实现方法类同。

对于文件系统，在当一个Page从树上移走，并将这个Page增加到Freepage链接表的时刻执行该策略。此时调用函数ESDBMSPcmerase0实现客体重用安全机制。

2.3 加密子模块

2.3.1 加密分析与方案选择

此加密模块除具备基本的加密功能之外，还需要尽量减少时间和空间的开销。考虑到这些因素，设计此模块需要解决如下两个问题：

① 加密粒度。在数据库加密系统中，数据库具有的文件、记录、字段多层次的概念，故必须综合考虑选择合适的加密粒度。对记录或者字段进行加密存储在嵌入式系统中是不现实的，对记录或者字段进行加密，其密钥的管理会成为一个特别棘手的问题，这对有快速，精简要求的嵌入式而言不适合。而选择对文件进行加密虽然粒度较粗，容易造成对不必要信息进行加密，但在电力系统从站中，数据量不大且数据类型很少，若采用计数器模式加密方法则不会增加任何的空间开销，与明文大小等同[5]。其密钥的管理也相当简单；

② 加密算法。加密算法是数据加密的核心，从加解密的密钥是否相同可以分为对称加密算法和非对称加密算法。对称加密算法由于其加解密的快速性在嵌入式系统中应用比较广泛，AES就是一种很成熟的对称加密算法。

2.3.2 密钥的管理

基于口令的加密。在密钥学的许多应用中，用户安全性最终取决于一个或多个秘密文本值或口令。口令不是直接可用作密码系统的密钥，相反，需要对口令进行一些处理才能用它进行密码操作。

密钥的产生。采用基于口令的加密方案，其密钥产生的过程：首先选择一个S和一个迭代次数C；其次选择导出密钥的字节长度dkLen；再其次将密钥导出函数应用于口令P、S、迭代次数和密钥长度以生成一个导出密钥DK(P，S，C，dkLen)；最后输出导出的密钥。其中S用于产生对应于给定口令的一个大集合的密钥，依据该S从中随机选取一个密钥。迭代计数C传统上用于增加从口令生成密钥的代价，从而增加攻击的难度。密钥导出函数是一个散列函数，包括MD2、MD5、SHA-1或SHA256等。导出密钥的字节长度dkLen与密钥导出函数有关，MD2和MD5是16字节，SHA-1是20字节。本加密模块采用的是SHA256，密钥长度是32字节。

2.3.3 加密子模块设计

具体过程。首先将整个数据库划分成块，每个块都可以作为一个单独的AES加密块，在计数器和由口令和盐产生的密钥作用下加密。加密和解密用的是相同的算法Rijndael算法。首先初始化一个进程的计数器。把数据库分成一个一个的块，每个都作为一个单独的AES加密块，每个块都从0开始编号，依据传入编码函数的Page Size和Page Number参数，算出计数块内的计数值和偏移量，然后用它来初始化加密流。

加密模块提供的接口。加密模块完成之后，给用户提供了用于加密的API接口EDBMS_keyO，EDBMS-rekeyO。此加密模块为可剪裁的模块，用户可以根据自己的需要对其进行增删。

2.4 OS接口子模块

OS接口的作用是为上层模块提供了一种抽象层，用来屏蔽不同操作系统的差别，为将来能移植到其它操作系统作铺垫。它的最终结果就是：不管是在哪种操作系统上，上层模块只看到一种单一的接口[6]。这样设计，不仅使其它模块不用考虑操作系统，从而编写的代码更简单，而且使模块问的关系整洁有序。

在OS接口模块中，主要是完成文件的一系列操作以及对文件锁的处理，包括文件的打开、关闭、删除和读锁、写锁信息的取得。由于不同的操作系统有自己独特的机制，这里只是说明了适用于Linux的的接口函数，如果以后扩展，可以对函数进行修改。

3 结语

本文采用分层设计的思想，设计和实现了ESDBMS的安全后端模块，屏蔽掉了各层之间的差异性，实现了高层向低层的透明调用，有利于降低层次之间的耦合度。对于ESDBMS的其它功能模块，它们可以透明地调用安全后端模块最高层提供的标准接口，而不需要了解安全后端模块的底层实现机制，这样有利于安全后端模块的拆卸和扩充，有利于实现ESDBMS的整体模块化。设计的ESDBMS安全后端模块能有效的管理存储空间、快速检索数据库文件中的信息、提高了存储管理的安全性，具有良好的实用性和创新性。

[1] 崔文静.实时数据库系统中并发控制的研究[D].济南:山东大学,2004.

[2] 王利青,武仁杰,兰安怡.Web安全测试及对策研究[J].通信技术，2008,41(06):29-32.

[3] 武森,高学东,[德]M．巴斯蒂安.数据仓库与数据挖掘[M].北京:冶金工业山版社,2003.

[4] WolfSon O,Huang Y X.Competive Analysis of Cashing in Distributed Database[J].IEEE Trans on Parallel and Distributed Systems,1998,l9(04):391-409.

[5] 赵跃化,蔡贵贤，蒋军.面向电力应用的嵌入式安全文件系统实现[J].计算机工程与应用,2006,57(30):193-196.

[6] 刘启军,程明. 嵌入式 linux中以太网设备驱动的设计与实现[J].通信技术,2009,42(09):145-147.