（计算机应用技术专业论文）安全嵌入式数据库管理系统的分析与设计.pdf

江苏大学硕士学位论文 摘要 嵌入式h l t e m e t 技术的飞速发展和广泛应用以及大量数据的处理需求，给应用 于电力控制领域的软件系统带来了新的挑战数据处理的安全性和高效性。于 是安全嵌入式数据库管理系统便应运而生，本论文分析并设计了一个应用于电力 控制领域的、安全的嵌入式数据库管理系统，为了便于描述，将其简称为e s d b m s ( s e c u r ea 1 1 de m b e d d e dd a t a b a s em a i l a g e m e n ts y s t e m ) 。该嵌入式数据库管理系统不 仅满足了电力控制领域对系统的功能性要求，而且保证了系统的安全性。 本论文首先介绍了嵌入式数据库管理系统的历史、现状和趋势，然后描述了 论文的研究背景，并指出e s d b m s 的研发在实用性、学术研究方面的意义。 在e s d b m s 的总体设计中，本论文首先对嵌入式数据库管理系统和安全数 据库管理系统的设计原则进行介绍，然后根据电力系统的背景，进行需求分析， 对e s d b m s 的整体框架进行设计，并对e s d b m s 进行了模块的划分，最后确定 了每个模块的功能。本论文主要完成其中的安全后端模块的设计和丌发，并分析 了安全数据库引擎，完成安全前端模块和安全事务管理模块的设计。 在安全后端模块的设计与实现中，为了有效，快速地对数据进行查找、操作， 本论文分别对c a c h e 管理组织方案和元组组织方式进行分析，并选择合适解决方 案，对其进行设计开发。在这些工作的基础上，本论文在c a c h e 管理子模块，表 和索引管理子模块中设计出其所涉及的客体重用机制，然后对加密进行分析，选 择合适的加密方案，最后实现了数据库的加密。 在安全数据库引擎模块的分析与设计中，针对电力系统子站采集的数据类型 不一定符合规定存储类型的情况，采用“弱类型”记录格式，解决静态类型格式对 于不符合规定类型数据的摒弃问题。在安全前端模块的设计中，结合操作系统的 安全机制设计用户认证和自主访问控制子模块，既避免了安全机制的冗余又确保 了系统的安全性。 在安全事务管理模块的分析与设计中，首先对并发控制实现方法进行分析， 选择合适的方法，然后分析了e s d b m s 锁与操作系统文件锁的融合问题，最后 对日志管理和事务处理操作进行了设计，保证了事务并发执行的有效性，数据的 安全性和完整性。 最后，对整个系统的执行流程进行分析，搭建测试及运行平台，制定安全后 端模块和自主访问控制机制的测试方案，根据测试结果，做出相应的分析。 关键词：嵌入式数据库，数据库管理系统，e s d b m s ，安全数据库，自主访问控 制，加密 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密 学位论文作者签名：亲钐多垒 p 毯年6 只f o b 下 素了奶汨 堑 旧 教 ，尉刁 能 年 z 9六 ， 参 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：亲钐砂垒 日期：w o 辟多月。日 江苏大学硕士学位论文 1 1 引言 第一章绪论 随着移动通讯、手持电脑、数字家电等的发展以及r i 技术在工业、交通、 军事等领域里的渗透，嵌入式系统已经成为r r 行业的热门。 所谓的“嵌入式系统( e m b e d d e ds v s t e m ) ”指的是以应用为中心和以计算 机技术为基础的，并且软硬件是可裁剪的，能满足应用系统对功能、可靠性、 成本、体积、功耗等指标的严格要求的专用计算机系统。它可以实现对其它设 备的控制、监视、管理等功能。 嵌入式系统的发展可以追溯到1 9 7 1 年h l t e l 公司生产的第一个微处理器 4 0 0 4 ，从那时候起嵌入式系统经历了3 0 多年的发展，纵观嵌入式技术的发展过 程，大致可以分为四个阶段： 1 、第一阶段是以单芯片为核心的可编程控制器形式的系统，具有与监测、 伺服、指示设备相配合的功能，这类系统一般应用于一些专业性强的工业控制 系统中，一般没有操作系统的支持，通过汇编语言编程对系统进行直接控制。 这一阶段的嵌入式系统的主要特点是：系统结构和功能相对单一，效率较低， 存储容量小，几乎没有用户接口。 2 、第二阶段是以嵌入式c p u 为基础，以简单操作系统为核心的嵌入式系 统。该阶段的主要特点是：c p u 种类繁多、通用性比较差，系统开销小、效率 高，操作系统达到一定的兼容性和扩展性，应用软件较专业化，但用户界面不 够友好。 3 、第三阶段是以嵌入式操作系统为标志的嵌入式系统。该阶段的主要特点 是：嵌入式操作系统能运行于不同类型的微处理器上，兼容性好；操作系统的 内核小，效率高，并且具有高度的模块化和扩展性；具备文件和目录管理、多 进程、网络支持、图形窗口以及用户界面等功能；具有大量的应用程序接口“心i 接口1 、开发应用程序较简单【l j 。 4 、第四阶段是以h l t e m e t 为标志的嵌入式系统。i i l t e m e t 技术在嵌入式系统 中的应用和推广，将提高嵌入式系统的协作能力、改善系统间的通信状况，提 高企业的控制水平，降低运作成本，所以嵌入式1 1 1 t e m e t 技术必然会对嵌入式系 统产生极其深远的影响。当前嵌入式系统的发展主要处在这个阶段。 综上所述，嵌入式系统技术日益完善，它与网络、i n t e m e t 结合日益密切， 因而它的应用必将日益广泛。从家用电器、手持通讯设备到航天航空、军事装 备，从信息终端、仪器仪表到制造工业、过程控制，都可以找到嵌入式系统的 江苏大学硕士学位论文 霎i 1 引言 第一章绪论 随着移动通讯、手持电脑、数字家电等的发展以及挈季! 技术在工业、交通、 军事等领域里的渗透，嵌入式系统已经成为r r 行业的热门。 所谓的“嵌入式系统( e m b e d d e ds v s t e m ) ”指的是以应用为中心和以计算 机技术为基础的，并且软硬件是可裁剪的，能满足应用系统对功能、可靠性、 成本、体积、功耗等指标的严格要求的专用计算机系统。它可以实现对其它设 备的控制、监视、管理等功能。 嵌入式系统的发展可以追溯到1 9 7 1 年蓁i t e l 公司生产的第一个微处理器 4 囊奏4 ，从那时候起嵌入式系统经历了3 0 多年的发展，纵观嵌入式技术的发展过 程，大致可以分为四个阶段： 1 、第一阶段是以单芯片为核心的可编程控制器形式的系统，具有与监测、 伺服、指示设备相配合的功能，这类系统一般应用于一些专业性强的工业控制 系统中，一般没有操作系统的支持，通过汇编语言编程对系统进行直接控制。 这一阶段的嵌入式系统的主要特点是：系统结构和功能相对单一，效率较低， 存储容量小，几乎没有用户接口。 2 、第二阶段是以嵌入式c p u 为基础，以简单操作系统为核心的嵌入式系 统。该阶段的主要特点是：c p u 种类繁多、通用性比较差，系统开销小、效率 高，操作系统达到一定的兼容性和扩展性，应用软件较专业化，但用户界面不 够友好。 3 、第三阶段是以嵌入式操作系统为标志的嵌入式系统。该阶段的主要特点 是：嵌入式操作系统能运行于不同类型的微处理器上，兼容性好；操作系统的 内核小，效率高，并且具有高度的模块化和扩展性；具备文件和目录管理、多 进程、网络支持、图形窗口以及用户界面等功能；具有大量的应用程序接口“心i 接口1 、开发应用程序较简单i i j 。 4 、第四阶段是以囊i t e m e t 为标志的嵌入式系统。i i i t e m e t 技术在嵌入式系统 中的应用和推广，将提高嵌入式系统的协作能力、改善系统间的通信状况，提 高企业的控制水平，降低运作成本，所以嵌入式i i i ；蠡m e t 技术必然会对嵌入式系 统产生极其深远的影响。当前嵌入式系统的发展主要处在这个阶段。 综上所述，嵌入式系统技术日益完善，它与网络、雪薹雪e m e t 结合日益密切， 因而它的应用必将日益广泛。从家用电器、手持通讯设备到航天航空、军事装 备，从信息终端、仪器仪表到制造工业、过程控制，都可以找到嵌入式系统的 江苏大学硕士学位论文 以及操作系统接口。 第4 章，对本系统的安全前端模块和数据库引擎模块进行了分析和设计。 第5 章，安全事务管理模块的分析和设计。 第6 章，分析了e s d b m s 的执行流程，制定了安全后端模块和自主访问控 制的测试方案，并对测试结果进行了分析。最后，作者在第7 章中对论文内容 进行了总结，并根据自己的研究成果和体会，提出了未来进一步研究的方向。 6 江苏大学硕士学位论文 2 1 2 安全数据库管理系统的设计原则 在安全数据库管理系统的设计方面，作为保存数据和信息记录的数据库系 统的管理系统，应当提供对信息和数据的安全存取的服务，即在向授权用户提 供可靠的信息数据服务的同时，又要拒绝非授权的对数据的存取访问请求，保 证数据库管理下的数据的可用性、完整性和一致性，进而保护数据库所有者和 使用者的合法权益。其基本安全要求为： 1 、保密性，这是指其中的数据信息不被直接或间接的泄露，即防止非授权 访问，这是安全最重要的要求。保密性定义了哪些信息不能被窥探，哪些系统 资源不能被未授权的用户访问。 2 、完整正确，包含物理、逻辑乃至数据元素的完整正确。信息在存储或传 输过程中保持不被修改、不被破坏和不丢失，是信息安全的基本要求。破坏信 息的完整性则是对信息安全发动攻击的目的之一。 3 、可用性，这是实施所有安全措施的最终目的。对可用性的攻击则是阻断 信息的可用性。 上述的嵌入式数据库管理系统与通用安全数据库管理系统的设计原则是设 计安全嵌入式数据库管理系统的指导方针，在安全嵌入式数据库管理系统的设 计过程中结合电力控制系统的具体情况执行。 2 2 需求分析 电力调度自动化子站软件系统存在的大量数据，可以分为实时数据和非实 时数据两类。实时数据是从站实时接收的各种现场的模拟量和数字量，它们反 映了当i j i 电网运行状况，当电力系统受到突发事件的干扰时，短时间内要接收、 记录、处理和报告大量的事故事件。因此，要求系统能实时对数据进行处理和 响应。非实时数据包括各类静态配置数据，其特点是实时性要求不高、数据的 存储量大、保存的时间长。 主站对子站的访问主要是控制，子站对主站的操作主要是写。 由以上分析可知，对嵌入式数据库管理系统的要求可总结为如下三大方面： 1 、子站对数据库管理系统的整体性能要求 嵌入式系统本身就具有实时性强、可靠性高、可扩展性好等特点。电力系 统是一个复杂的非线性、高维、互联大系统。基于嵌入式系统特有的优点，其 在电力系统中的应用主要用于底层来实现数据采集、监视控制与仪表计量等功 能，而上层应用，由于对数据处理与存储能力、人机交互( m m i ) 、网络通信等 方面要求甚高，一般都是由p c 系统或局域网( l 悄) 的形式来实现。总的来 说，嵌入式系统在电力系统中的应用有以下几个方面的要求： 8 江苏大学硕士学位论文 ( 1 ) 实时性强 以电力系统的稳定观测与控制为例，实时性就是其首先要解决的问题。这 是因为电网的安全稳定性通常在事故后几十到几百毫秒内就有可能受到严重威 胁，并且过迟的稳定控制措施不仅起不到预想的作用，造成经济上的损失，甚 至可能引起其他的安全问题。这里的实时性不仅指获得数据的实时性，而且还 包括数据处理、分析、决策的实时性。因此这对嵌入式系统的硬件与软件都是 一种较为苛刻的要求。 可靠性高 现代化大生产与居民生活中电能的使用是最普遍的，因此在利用嵌入式系 统实现对电力系统的控制时硬件与软件的可靠性也就成为人们极为关注的问 题。通常，人们不仅希望嵌入式系统能按照预先设计好的流程正常工作，而且 也对嵌入式系统的抗干扰能力与智能性提出了一定的要求。 ( 3 ) 可扩展性好 目前大多数的嵌入式系统的开发语言都采用c c + + ( 也包括少量的汇编语 言) ，因此灵活性好，可移植性强，可适用于各种类型的运用；另外尽量采用模 块化设计与工业组态软件，这不仅可以方便生产调试厂家，而且可以解放用户。 当需要增减某项功能时，只需要增减相应的模块即可。 ( 4 ) 安全性高 当电网的各个工作站之间的联网、整个电网的整体控制成为一种发展趋势 时，安全问题就是一个不得不面对的问题。这里的安全包括对一些重要和敏感 数据的保护以及对整个电网控制的保护。这些安全性问题的实现也离不开 e s d b m s 的支持，所以设计e s d b m s 时，也必须提供安全性方面的设计。 2 、子站对数据库管理系统的功能性要求 ( 1 ) 数据存取 提供用户对数据的操作功能，实现对数据库数据的检索，插入，修改和删 除。一个好的数据库管理系统应该能够提供功能强大，易学易用的数据操纵语 言，方便的操作方式和较高的数据存取效率。 ( 2 ) 数据库运行管理 包括事务的管理和自动恢复，并发检测和死锁防止，运行日志的组织管理 等，这些功能保证了数据库系统的正常运行。 ( 3 ) 数据组织，存储和管理 数据库管理系统要分类组织，存储和管理各种数据。要确定以何种文件结 构和存取方式在存取级别上组织这些数据，如何实现数据之问的关系。数据组 织和存储的基本目标是提高存储空间的利用率和方便存取，提供快捷的存取方 式以提高存取效率【1 0 】。 9 江苏大学硕士学位论文 3 、子站对数据库管理系统的安全性要求 根据一般数据库管理系统的基本安全要求，在嵌入式系统子站中，数据库 管理系统遇到的安全威胁主要包括： ( 1 ) 假冒攻击 这种类型也称为身份攻击，指用户身份被非法窃取，也就是攻击者伪装成 另一合法用户，利用安全体制所允许的操作，去破坏数据库安全。为防止假冒， 用户在对数据进行操作之前，必须对其身份进行认证和访问控制检查【1 1 】。 ( 萄窃取重要信息 在一个信息系统中，特别是机密单位的信息系统中，通常都保存有大量的 机密信息，攻击者可以通过多种访问方式来窃取系统中所存储的机密文件和数 据。因此，当前在大多数系统中都采取了多种措施，来防止信息的外泄，比如 用户身份验证和访问控制两种基本技术。但是有时还广泛采取对存储在数据库 中的数据进行加密的措施，使攻击者即使窃取到了重要数据，也无法理解其含 义【13 1 。 针对以上子站数据库管理系统所遇到的安全威胁，将在下一小节制定出安 全策略。 2 3 嵌入式数据库管理系统安全策略的分析与制定 安全策略( s e c u r i t yp o l i c y ) 就是指有关管理、保护和发布敏感信息的法律， 规定和实施细则。简单地说，就是用户对安全需求的描述【14 1 。 基于安全策略的内涵，可以把安全策略分为访问控制策略s sc o n t r o l p o l i c ”和访问支持策略( a c c e s ss u p p o r t i i l gp o l i c y ) 两大类。下面我们根据电力系 统安全需求，从访问控制策略和访问支持策略两个方面制定出e s d b m s 的安全 策略。 2 3 1 访问控制策略 访问控制策略反映系统的机密性和完整性要求，它确立相应的访问规则以 控制对系统资源的访问。访问控制策略主要有自主访问控制策略和强制访问控 制策略两种。 ( 1 ) 自主访问控制 自主访问控制是最常见的一类存取控制机制，之所以称为“自主”是因为： 一方面，客体的拥有者可以按照自己的意愿精确指定系统中的其它主体对其拥 有客体的访问权；另一方面，对其它具有授予某种访问权力的主体能够“自主地” 将访问权或访问权的某个子集授予另外的客体。自主访问控制能够提供一种很 1 0 江苏大学硕士学位论文 2 、更加易用：在e s d b m s 中不进行系统空间和用户空间的划分，可以在很 大的程度上方便程序员，使得程序员可以更大限度地利用系统提供的功能，这 和嵌入式数据库管理系统设计的易用性原则相符。 3 、具备库函数模型自身的一些优点，比如，功能模块易于扩充和裁剪、整 体结构简单易于理解、容易维护等等，这些都是符合嵌入式数据库管理系统的 具体设计需求的。 4 、虽然c s 结构模型可以提供标准的数据库接口，但是标准的数据库接口 在电力系统这些工业控制领域是不需要的，工业控制领域通过操作a p i 控制数 据库更合适。 2 5e s d b m s 框架设计与模块划分 2 5 1e s d b m s 框架设计 对应用于电力系统的e s d b m s 安全策略和数据库结构模型确定以后， e s d b m s 的框架结构也就顺理成章了。本论文把数据库管理系统划分为四个模 块：安全后端模块、安全数据库引擎模块、安全前端模块和安全事务处理模块。 在每个模块的具体设计中，将有机地融合安全功能，从而保证数据库管理系统 整体的安全性。安全嵌入式数据库管理系统的框架结构如图2 2 所示。 图2 2e s d b m s 框架结构 2 5 2e s d b m s 各模块功能分析 e s d b m s 划分为四个模块，各个模块的功能和设计思路如下： 1 、安全前端模块 安全前端模块包括用户认证，自主访问控制，a p i 接口，s q l 编译器和代 码生成器。它的主要流程是：用户提交用户名和密码，确定是合法用户后，就 1 4 江苏大学硕士学位论文 2 、更加易用：在e s d b m s 中不进行系统空间和用户空间的划分，可以在很 大的程度上方便程序员，使得程序员可以更大限度地利用系统提供的功能，这 和嵌入式数据库管理系统设计的易用性原则相符。 3 、具备库函数模型自身的一些优点，比如，功能模块易于扩充和裁剪、整 体结构简单易于理解、容易维护等等，这些都是符合嵌入式数据库管理系统的 具体设计需求的。 4 、虽然c s 结构模型可以提供标准的数据库接口，但是标准的数据库接口 在电力系统这些工业控制领域是不需要的，工业控制领域通过操作a p i 控制数 据库更合适。 2 5e s d b m s 框架设计与模块划分 2 5 1e s d b m s 框架设计 对应用于电力系统的e s d b m s 安全策略和数据库结构模型确定以后， e s d b m s 的框架结构也就顺理成章了。本论文把数据库管理系统划分为四个模 块：安全后端模块、安全数据库引擎模块、安全前端模块和安全事务处理模块。 在每个模块的具体设计中，将有机地融合安全功能，从而保证数据库管理系统 整体的安全性。安全嵌入式数据库管理系统的框架结构如图2 2 所示。 图2 2e s d b m s 框架结构 2 5 2e s d b m s 各模块功能分析 e s d b m s 划分为四个模块，各个模块的功能和设计思路如下： 1 、安全前端模块 安全前端模块包括用户认证，自主访问控制，a p i 接口，s q l 编译器和代 码生成器。它的主要流程是：用户提交用户名和密码，确定是合法用户后，就 1 4 江苏大学硕士学位论文 第三章安全后端模块的设计与实现 在嵌入式系统中，物理存储空间是除了c p u 之外最基本、最重要的资源。 物理存储空间主要包括内存和外存。物理存储空间在系统中的管理效率对于整 个系统的效率起着决定性的作用，内存和外存中存放的数据也是e s d b m s 的重要 保护对象。所以，如何高效地管理内存和外存空间、如何尽快的查找到数据库 文件中的有用信息、如何实现存储管理的安全性等【2 们，这些都是设计和实现 e s d b m s 安全后端模块需要解决的问题。 另外，安全后端模块作为与嵌入式操作系统联系紧密的模块，如何使其不 受平台影响，也是本论文需要考虑的问题。 本章先介绍安全后端模块管理对象一数据库文件的组织方式，然后对安全 后端模块进行整体框架设计，对其进行子模块划分，最后分别对各个子模块进 行详细设计与开发。 3 1 数据库文件的组织方式 为了简化空间管理和从数据库中读写数据的复杂度，把数据库分成固定大 小的区域，称为页面。也就是说一个数据库文件是由一系列的页组成的，这一 系列页的索引称为页码。 1 、页面类型 页面有四种类型：l e a f ，i n t e m a l ，o v e m o w 和肌e 。f r e ep a g e 是非活动的， 即当前没有用过的页面；其它的都是活动页面。i n t e m a lp a g e 包含用于查询的索 引信息，k a f p a g e 存储真正的数据。l e a f p a g e 和i n t e m a lp a g e 合称为t r e ep a g e 。 如果一行数据在单个l e a fp a g e 页中无法存储，那么余下的部分则被保存在 o v e m o w p a g e 中。 2 、数据库文件头 为了便于对各个数据库文件进行存储和查询，e s d b m s 对每个数据库文件 定义其文件头，它的主要作用是对数据库文件结构进行描述，在建立数据库文 件的时候，首先初始化此文件头。除了p a g e1 ，e s d b m s 可以用任何数据库页 面作为数据库文件头的页面( p a g e l 只能为e s d b m s 系统自身所用) 。文件头这 一页包含了1 0 0 字节的文件头记录，这些记录都从偏移量0 开始存储。文件头 的格式如表3 1 所示。 1 6 江苏大学硕士学位论文 表3 1 数据库文件头结构 偏移量 大小解释 o1 2 头字符 1 2 1 最人有效载荷 1 34 文件改变次数 1 7 4 第一个f r e e l i s t 页地址 2 14 f r e e l i s t 中页的数目 2 51r e s e r v e db y t e 2 67 0s h a r e ds i z e 9 6 4 备用空间 下面是对每个头文件元素的描述： 头字符 这是一个1 2 字节的字符：“e s d b m sf o 衄a t ”。 最大内部有效载荷 最大内部有效载荷值( 偏移量1 2 ) 是一个元组在一页中可用空间的大小百 分比( 默认为2 5 ) ，这个空间将存储标准b + 树i n t e m a l 结点的元组。如果一个 元组的p a y l o a d 超过最大值，那么额外的p a y l o a d 就被溢出至o v e m o wp a g e s 。 文件改变次数 事务中要用到的有用信息( 偏移量1 3 ) 。这个值随着每个事务的变化而变 化。 f r e e l i s t 上第一个f 把ep a g e 的地址 f r e e l i s t 上未用的页面开始于文件头偏移量1 7 ，f r e ep a g e 的总数存储在偏移 量为2 1 的地方。 r e s e e d b y t e 设置事务对文件的r e s e r ：v e d 锁。 s h a r e ds i z e 放置s h a r e d 锁。 3 。2 安全后端模块的框架设计 为了减少开发难度，安全后端模块的设计采用分层设计的思想，屏蔽掉各 层之间的差异性，实现高层向低层的透明调用，这样有利于降低层次之问的耦 合度。并且对于e s d b m s 的其它功能模块，它们可以透明地调用安全后端模块最 高层提供的标准接口，而不需要了解安全后端模块的底层实现机制，这样有利 于安全后端模块的拆卸和扩充，有利于实现e s d b m s 整体的模块化。 由于安全后端模块处理的主要是存储管理及其安全性的问题，它的大体框 1 7 江苏大学硕士学位论文 3 3 安全后端子模块核心数据结构的设计 1 、页面缓冲管理结构一c m s n u c t p c m j o u m a l o p e n ； 如果日志文件有效，则为真 i u l s i g l l e dc h a rs t 2 l t e ；锁状态，为n o l o c k 、s h a r e d 、 r e s e r v e d 、e x c l u s i v e 中的一种 u n s i g n e dc h a rt e m p f i l e ；为真，则表示z f i l e n 锄e 是一个临时文件 u n s i 印e dc h a rr e a d o n l y ； 表示数据库只读 u n s i g n e dc h a rd i 啊c a c h e ； 如果c a c h ep a g e 内容改变，则为t m e nd b s i z e ； 现在数据库文件人小 i n to r i g d b s i z e 数据库文件改变之前的人小，在事务处理恢复时使用 i n tn r e c ； 写入口志文件中的p a g e 号 i n tn p a g e ； 内存数据库中总的p a g e 数 硫n r e f 内存中p g h d r n r e 今o 的p a g e 数 c h a r 幸z f i l e n 锄e ；数据库文件名 c h a r 宰z j o u m a l ；日志文件名 p g h d r 木p f i r s t ，+ p l a s t ； 骶ep a g e 列表指针 p g h d r 木p f i r s t s y n c e d ；p 窖h d r n e e d s y n c = 0 白勺第个】自r e ep a g e p g h d r 搴a h 2 u s h n _ p g j 认s h 】； 影用米映射p a g e 号给p g h d r 的哈希表 ) ； 这个数据结构在安全后端模块中非常重要，每个打开的数据库文件都通过 单独的一个p c i n 实例来处理，并且每个p 锄实例只与一个数据库文件联系。表 和索引管理子模块用数据库文件的时候就会创建一个新的p 锄实例，并且用这 个实例作为句柄来把页面级别的操作映射到文件上。c a c h e 管理子模块利用旬柄 来跟踪关于类似于文件锁，日志文件，数据库状态，日志状态等信息。 2 、c a c h e 中页头结构_ p g h d r s 缸1 j c tp g h d r p c m 木p p c m ；指向此页所属的p c m p 印op 印o ；指出它所表示的数据库页面的页码 p g h d r 木p n e x t h a s h ，幸p p r e v h a s h ；用来连接在同一个b u c k e t 中的页 p g h d r 幸p n e x t f r e e ，幸p p r e v f r e e ；用来连接所有f r e ep a g e p g h d r 木p n e x t s t m t ，幸p p r e v s t m t ； 用来连接在声明日志中的页 u n s i g n e dc h a ri o 啪a l ；如果页面已经被写入回滚日志， 那么i n j o u r n a l 变量就为t r u e u i l s i 印e dc h a rd i n y ；如果页面已经被修改过，并且新的值还没有被写 同数据库文件中，那么d i r t y 变量为仃u e 啪s i 印e dc h a rn e e d s ”c ；在写同数据库文件之前，如果日志需要清空， 那么n e e d s y n c 变量就为t r u e 1 9 江苏大学硕士学位论文 s h o r ti n tn r e t 这个页的用户的数量 p g h d r 幸p d i n ) r ；p d i r t y 指针连接所有d i r t yp a g e ) ； 存储在c a c h e 中的页面都是这个数据结构的实例。p g h d r 只对页面缓冲管 理模块是可见的，并且对于表和索引管理子模块和更高层次的模块是不可见的。 用户程序在对页进行修改之前需要调用e s d b m s p c b _ r i t e o 这个写函数， 该函数调用中，原来的页面内容就会首先写入回滚同志，p g h d r i n j o u m a l ， p g h d r n e e d s y n c 等参数就会置位，内容写回到文件后，置位消除，保证了数据 库文件内容的安全性和完整性。 3 、字段信息结构c e l l h l f o s t r u c tc e l l i i l f o u 8 宰p c e l l ；指向元组内容开始地址的指针 i 6 4n k e y ；主键数据 u 3 2n d a 元组内容大小 u 1 6n h e a d e r ；，元组头的大小 u 1 6i o v e m o w ；内容溢出至o v e r f l o wp a g e 的页码，如果是0 ，则没有溢出 ) ； 这个数据结构是用来对元组进行管理的，一个页中除了页头就是元组区域 了，这是用户进行操作的关键区域。 3 4 c h e 管理子模块的设计与实现 3 4 1c a c h e 管理方案选取与c a c h e 的组织 1 、c a c h e 管理方案的选取1 2 2 j c a c h e 管理子模块是本地文件系统和其它上层模块之间的中问模块。它是通 过本地操作系统1 0 a p i 访问本地数据库和日志文件的模块，即定义一个易于使 用，独立于文件系统的接口，用来从数据库文件中访问页面。表和索引管理子 模块总是通过c a c h e 管理子模块来访问数据库，并且从来不直接访问数据库或 者日志文件，它将数据库文件视为页面的逻辑结构。 对每个数据库文件来说，在文件和c a c h e 之间移动页面是页面缓冲管理作 为c a c h e 管理器的基本功能。页面的移动对表和索引管理子模块和更高层次的 模块来说是透明的。 为了提高数据库的运行速度，本系统利用哈希表来组织内存中的页，选择 2 0 江苏大学硕士学位论文 的理由是： ( 1 ) 哈希表查找快速 哈希表是一种高效的数据结构，最大的优点就是把数据的存储和查找消耗 的时间大大降低，几乎可以看成是常数时间，而代价仅仅是消耗比较多的内存。 然而在当前嵌入式系统可利用内存越来越多的情况下，用空问换时间的做法是 值得的口3 】【2 4 】【2 5 1 。 ( 2 ) 编码比较容易 由于很多数据库产品都采用这种页面的组织方式，此方法编码比较成熟， 可以节省很多开发的时间。 2 、c a c h e 的组织 本论文利用哈希表来组织c a c h e 页，为了区分内存和外存中的页，在外存 中叫p a g e ，在内存中叫s l o t 。即任何的s l o t 可以存储任何的p a g e 。哈希表最初 是空的，随着页面要求的不断增加，c a c h e 管理子模块建立新的s l o t 并且把s l o t 插入到哈希表中。具体的组织结构设计如图3 2 所示。 图3 2c a c h e 组织结构 图中的p c l l l 实例对应于一个数据库文件，即建立一个数据库就会建立一个 p c i l l 实例。每个数据库文件都有自己的c a c h e 管理，p c m 实例中的a h a s h 和哈 希队列( h a s ha r r a y ) 用于将想要查找的p a g e 号映射给c a c h e 中的哈希桶，桶的 设置是为了避免地址的冲突，每个桶是由两页组成的，这两页被组织成无序的 双重连接表，通过哈希桶最终找到c a c h e 中的目标页，然后就可以对其进行读， 写或者替换操作。通过哈希表可访问到c a c h e 中的所有页。p c m 实例中p f i r s t 2 1 江苏大学硕士学位论耋 箝囊i 丽髓羹霎丽瞄j 囊藩需蒌雾蓁i 鞋薰嚣蓁燮霎蓁篓霪i i l 篓冀冀薹霹鐾翼 萋燃i 厦瞪筠擢秀捌蠲裙各娶雾嚣酗鞴汹翱霎耋耋霪蓬矍量；曩曩封羔| 羹| 睦l 囊羹蠢冀惩； 蓄孟濯瓴溺j 鐾焉薹i 削弱雉薅霎。餐霎囊霸副薹臻誉； 鬟曜缕粥i 撼讲并一瞬二 蓁和索鐾li 莹! 鄞篓到辅j ；墓琴荔噩一候对羹项螺l 霎。 羹薹隧意；矗静龄甄群；警“辩琴薹蒌童掣藿薹冀i 嘉萋茎 d b m s 对每一页按照如下协 x 江苏大学硕士学位论文 m e m c p y ( p p a g e ，p d a t 如p p c m - p a g e s i z e ) ； i f ( p p c m d b s i z e p 印o ) 更新数据库文件大小 p p c m 一 d b s i z e2p p 乎 p 弘o ； p p g - d i n y = o ；清d i r t y 标志 ) 其中每次页面上w d t e 函数被调用，就置位d i r t y 标志；只有当c a c h e 管理 模块把此页的内容写回到数据库文件中，才清除n a g 标志。 3 、c a c h e 替换操作 回 图3 5c a c h e 替换操作流程图 当c a c h e 已经用完，此时需要移出c a c h e 中的旧页，以便为新页腾出地方。 即在c a c h e 读时，当一个请求的页不在c a c h e 中，并且在c a c h e 中并没有f 把es l o t ， 那么c a c h e 管理模块就会替换掉一个s l o t 。这个被替换掉的s l o t 按照c a c h e 替换 江苏大学硕士学位论文 r o o t 页 l e a 顶o v e r l l o w 页 l e a 顶 图3 6e s d b m s 中的b + 树结构 e s d b m s 的t r e e 节点包括i n t e m a l 节点和1 e a f 节点，如图3 6 所示。元组内 容是k a f 页的一部份，每个元组的键和数据组成p a y l o a d ，如果p a y l o a d 超过了 此页的大小，那么就将其溢出至o v e m o wp a g e 。 3 5 3 各种页面的组织结构 表和索引管理子模块管理所有的页，包括t r e ep a g e ( i n t e m a l 或l e 鸡、o v e m o w p a g e 和f r e ep a g e 。 1 、t r e ep a g e 组织结构 每个t r e ep a g e 的逻辑内容分为四部分，如图3 7 所示。 p a g e 头 元组指针队列 未分配空间 元组内容区 i n t e m a ln o d ep a g el2 字节 l e a f n o d ep a g e8 字节 l 元组存储循序2 字节 v l 任意顺序存储 图3 7 饥ep a g e 结构 下面分别介绍： p a g e 头 p a g e 头只包含当前p a g e 的管理信息，头始终存储在一个p a g e 低地址部分。 p a g e 头的结构如表3 2 所示。 江苏大学硕士学位论文 表3 2 仃e ep a g e 头结构 偏移量大小解释 0l 标记1 ：i n t k e y ，2 ：z e r o d a 饥4 ：1 e a f d a 8 ：l e a f l2 第一块此页中的空闲块的偏移地址 32 p a g e 上元组数目 52 元组内容区的第一个字节 71 空闲碎片大小 84 右孩子指针，l e a f 节点没有 元组指针队列 元组指针队列和元组内容区是同时增加的，元组指针队列是用来映射 元组的逻辑存储到元组的物理存储。 未分配空间 元组内容区 元组是变长字符串，一个元组包含一个p a y l o a d 。元组是t f e ep a g e 中分配或 回收的存储空间单位。元组的结构如表3 3 所示。 表3 3 元组结构 大小解释 4 孩子指针。 v a “1 9 ) d a t ai m a g e 中的字节数。 v a r ( 1 - 9 )k e yi m a g e 中的字节数。 p a y l o a d 4 第一个o v e r f l o wp a g e 地址。 描述如下： 孩子指针：对于i n t e m a lp a g e ，每个元组包含4 字节的孩子指针；对于 l e a fp a g e ，没有孩子指针。 d a t ai m a g e 中的字节数：元组数据的字节数。如果z e r o d a t a 在p a g e 头 被置位，则d a t ai m a g e 不存在 k e yi m a g e 中的字节数：元组键的字节数 p a y l o a d ：是指k e y 和d a t a 的总的地址，由于i n t e m a lp a g e 中只包括指 向其孩子结点的指针，所以只在l e a f p a g e 中存在此参数。 o v e m o w p a g e ：第一个o v e f f l o wp a g e 地址，o v e m o wp a g e 是链表形式， 所以知道第一个就知道所有。如果没有o v e m o wp a g e ，则忽略为n u l l 。 图3 8 描述了元组格式：( a ) 元组的结构，( b ) p a y l o a d 结构。如果l e a fp a g e 中元组内容超过最大的页容量，此时额外的内容就会溢出到o v c m o w p a g e 链中。 江苏大学硕士学位论文 元组结构 臣豆 二匠 p a y i o a d 结构 图3 8 元组格式 2 、o v e m o wp a g e s 和f r e ep a g e 组织结构 多个元组可以放在单独一个t r e ep a g e ，但当元组太大时可以跨越存储在多 个o v e r f l o wp a g e 。元组的o v e m o wp a g e 由一个单独的链表形成。 f r e ep a g e 也是由一个单独的链表组成的。 3 5 4 元组的分配和回收 表和索引管理子模块帮助安全数据库引擎模块把所有的表和索引组织成 b + 树。每棵树由一个或多个数据库p a g e 组成。数据库引擎能存储和搜索任何树 中可变长度的元组，在任何时候删除树中的元组。 表和索引管理子模块可在任意时候从数据库引擎收到插入和删除记录的要 求。一个插入操作需要在t r e ep a g e 和o v e m o wp a g e 中分配空间。一个删除操作 清空t r e ep a g e 和o v e m o wp a g e 中占据的空间。管理空闲空间对于有效分配和回 收空间是至关重要的。空闲空间主要包括f r e ep a g e 的空闲空间和t r e ep a g e 的空 闲空间，下面分别介绍。 1 、f r e ep a g e s 管理 当一个p a g e 从树上移走时，这个p a g e 就增加到f r e ep a g e 链接表，下次可 以继续使用。当一棵树需要扩充时，从f r e ep a g e 链接表上取下一个p a g e ，添加 到树上。如果f r e ep a g e 链接表为空，则从本地文件系统上取一个p a g e ，插入到 f r e ep a g e 链接表中。 2 、t r e ep a g e 空间管理 一个t r e ep a g e 上的空闲空间有三种情况： 空闲块在元组指针队列和元组内容区中间 空闲块在元组内容区 在元组内容区的分散的碎片 下面对分配和回收两种情况分别加以说明： ( 1 ) 元组分配 空问分配运算不分配小于4 个字节的空间。假设请求分配n r e q u i r e d ( n r e q u i r e d = 4 ) 个字节，这n r e q u i r e d 个字节来自一个p a g e ，当这个p a g e 总 共有n f r e e 个字节。如果n r e q u i r e d n f r e e ，则请求失败。如果n r e q u i r e d = i l f r e e ，则分配流程图如图3 9 所示。 江苏大学硕士学位论文 入口参数：宰p 印。一用来指向特定页的页码。 返回参数：无返回参数。 其中关键部分伪代码如下： e s d b m s f r e e ( p p c m ) ； 释放当前页 当前页的参数复位； m e m s e t ( p p c m ，0 ，p a g e s i z e ) ) ； 当前c a c h e 复位 取消锁； 3 6 加密子模块的设计与实现 3 6 1 加密分析与方案选择 此加密模块除具备基本的加密功能之外，还需要尽量减少时间和空间的开 销。考虑到这三个因素，设计此模块需要解决如下几个问题： 加密粒度 在数据库加密系统中，数据库具有的文件，记录，字段多层次的概念，故 必须综合考虑选择合适的加密粒度。对记录或者字段进行加密存储在嵌入式系 统中是不现实的，对记录或者字段进行加密，其密钥的管理会成为一个特别棘 手的问题，这对有快速，精简要求的嵌入式而言不适合。而选择对文件进行加 密虽然粒度较粗，容易造成对不必要信息进行加密，但在电力系统从站中，数 据量不大且数据类型很少，若采用计数器模式加密方法则不会增加任何的空间 开销，与明文大小等同。其密钥的管理也相当简单。 加密算法 加密算法是数据加密的核心，从加解密的密钥是否相同可以分为对称加密 算法和非对称加密算法。 对称加密算法，适用于对数据库和文件加密，且速度较快，有时比非对称 加密算法快1 0 0 0 倍，这个特点特别适合嵌入式系统，常用的对称加密算法为： d e s ，r c 4 4 e s 等。 非对称加密算法加解密的速度慢，强度低，对选择明文攻击比较脆弱。常 用的非对称加密算法包括：r s a ，e 1g a m a l 等。 对称加密算法由于其加解密的快速性在嵌入式系统中应用比较广泛。a e s 就是一种很成熟的对称加密算法。 3 6 2 密钥的管理 1 、基于口令的加密 3 2 江苏大学硕士学位论文 图3 1 0 加密流程 为了简化，加密和解密用的是相