变长存储块Hash完整性校验方法1 引言数据的完整性是计算机系统中数据安全的基本属性之一，它是指防止数据被非授权的改动。一般的，完整性保护既可以是一种“阻断”措施，也可以是一种“探测”措施。“阻断”措施是在修改行为发生之前对使用者的合法性进行验证，可拒绝非法的修改行为。但从抗拒硬件攻击的角度而言，由于无法物理地阻止攻击者的主动篡改行为，“阻断”对于硬件攻击行为是难于施行的，而“探测”措施是可行且相对易于施行的。完整性校验是指记录系统中的当前信息，用于随后的比较以发现内容的变动。完整性校验被处理器、文件系统和数据库等用来校验非可信存储的数据，以此发现数据的篡改。为实现完整性校验，一般的结构是采用安全处理器构成校验的可信计算基，原理是利用存储在可信计算基中不可被非法篡改的信息，通过某种算法，对外部非可信存储器实施完整性校验。存储器完整性校验方式可分为脱机 (Offline) 和联机(Online )校验1。脱机校验是指在一个存储器操作序列完成后实施检测，比如校验程序执行结果的完整性，它适用于不需精确探测异常的情形，它不需明确指明是哪个结果被篡改；联机校验是指在每一次存储器操作后马上实施校验，这种方式可以杜绝错误结果提交所造成的影响，但联机校验需要更频繁的检测，因而比脱机校验代价更高。本文的研究是为系统提供一个高性能、低代价的完整性校验方案，即提供一个抗硬件攻击的篡改证明环境。为集中讨论，本文针对的非可信存储器特指计算机系统存储器(memory)，即内存。本文基于联机方式的存储器完整性校验，提出了变长存储块的基于 Hash 树的存储器完整性校验方法。该方法基于Hash 树校验, 利用访问的局部性原理，分别对热访问区和非热访问区设置了不同的存储块大小值，从而更快速完成完整性校验。通过分析与模拟实验表明，该方法可有效提高存储器完整性联机校验的效率。本文组织如下：第二部分讨论了相关的研究工作；第三部分是重点，首先提出了一个变长存储块的基于Hash树的完整性校验方法，然后讨论了变长存储块的规则和算法；第四部分基于前面建立的框架，完成模拟工作，并进行了分析；最后部分得出了结论。 2相关研究关于数据完整性校验，国内外学者做了一定的研究，这里简要讨论现有的针对单处理器的典型存储器完整性校验技术，特别是以Hash 树为基础的校验方法，然后分析了各种方法存在的问题。 2.1 MAC 消息认证码（Message Authentication Code，MAC）2是较常见的一种完整性校验方式，MAC是指对每个存储器块进行Hash计算所得到的结果。它验证的基本原理是：首先对要保护的存储器分成多个相等的块，针对每个存储器块进行 Hash计算，保存所得结果，并将结果同存储器块附着在一起，当再次访问时，重新计算存储器块的MAC值，并同原始附着的MAC值进行比较，从而判断该存储器块的内容是否完整。同时为了对抗入侵者将一个合法块的内容拷贝到另一块中，MAC在计算时包含块所在的地址信息。 MAC的优点是可以被快速计算及比较，但 MAC 不能用于动态修改的存储器的完整性校验，它无法应对重放攻击（Replay Attack），因为MAC可以保证是处理器保存的，但不能确保内容是最新的。因此目前MAC方法多与其他方法一起使用。2.2 Hash树Hash 树（Hash Tree）也叫Merkle 树（MerkleTree）3，它是完整性校验的一种常用方法，它可以检测出包括重放攻击在内的篡改存储器的行为，它的基本原理是：类似于MAC，首先将存储器分成多个等长块，并进行编号，每个存储块对应Hash树的叶节点，每个内部节点为下属两个节点Hash计算的结果，一直到根节点。树的根节点处于安全的存储区（一般置于处理器内的L2-Cache内，这一区域内数据不能被篡改）。非可信存储器中进行对于一个 m 叉(m=2) Hash 树而言，每次更新数据将导致 logm N次Hash计算，这里N是要校验的存储器块数。Hash树校验存在的问题是每次校验的开销很大；当内存块尺寸增大时，Hash计算量会迅速加大，导致系统性能显著下降。2.2 CHtree校验缓冲型Hash 树（Cache Hash Tree）是MIT提出的完整性校验方法4，它是基本Hash树的一种优化方法，基本思想是利用处理器的片内Cache来提高基于Hash树的完整性校验效率。该方法假定在CPU内Cache（含L1-Cache和L2-Cache）是可信的，完整性校验装置同L2-Cache并在一起，用作完整性检查的Hash树内部节点被缓冲在L2-Cache中而维持可信，从而校验路径只需到达缓冲在L2-Cache中的节点即可停止，而不必一直进行到根节点。这种方法通过降低校验路径的长度，使得所需Hash计算的次数大大减小，因此可明显提高校验速度，测试结果表明该方法可使校验的性能代价减小到约25%。 该方法的主要问题是需要较大的L2-Cache以便缓冲足够多的Hash树的内部节点，其次是需要占用较大L2-Cache空间 ，造成其它程序的运行效率下降。2.3 LHash 和H-LHashLHash （Log Hash Integrity Checking，日志型Hash完整性检测）和H-LHash（Hierarchical Scheme of Log Hash Integrity Checking，日志型 Hash完整性检测的层次式方案）方法5，是MIT提出的“Lazy”型存储器完整性校验技术。通过维护一个存储器读写的操作日志，可以在稍后的某个时间一次性校验一系列存储器访问结果的完整性。LHash是一种脱机校验(Offline checking)，通过减少不必要的校验次数而降低整个校验过程的代价。H-LHash在LHash的基础上利用L2-Cache来缓冲部分节点，能够允许比LHash更频繁的检测，但基本与LHash相似。LHash / H-LHash由于多数时间只记录日志，因而“运行时性能”好，但一次校验代价会更大。因此，若想有效发挥LHash的性能，检验必须是不频繁的。测试结果表明，这一“不频繁”的性能拐点约在(106次访问)/(1次检验)，当检验比上述折点更频繁时，LHash/H-LHash的性能将显著下降。2.4 HW-HTreeHW-HTree（Hot Access Window based Hash Tree Optimizing Approach，基于热访问窗口的Hash树优化算法）6是国防科大侯方勇博士提出来的，它的核心思想是通过缩短校验路径以减小代价，使用的也是Hash树校验的方法，其主要思想是：维持 Hash 树的基本结构不变，为其添加热点区域。热点区域是指被频繁访问的区域，通过优化热点区域从而提高校验性能。将这一概念应用到 Hash树上，得到带热点窗口(HotWin)的 Hash树。此方法在校验数据以前，先保存每个HotWin的子树顶节点到安全区，这样在校验数据时，每次只校验到子树顶节点，不需要校验到根节点；同时在更新数据时，也只更新到子树顶节点；只有在HotWin平移时，才将更新的节点向上传递到根节点。 这种方法是Hash树的另一种改进，由于每次只需要校验到子树顶节点，缩短了校验路径，一定程度上提高了校验效率。但它采用统一的存储块划分方式，当要保护的存储区很大时，进行Hash校验的开销仍较大。3 基于变长存储块的Hash树完整性校验Hash 树是一种存储器完整性校验的可靠方法，但实现代价大，而改善性能的主要手段是减小校验所需路径的长度，从而减小所需访问的节点数量与所需进行的 Hash计算量。针对HW-HTree方法采用统一的存储块划分方式存在的问题，本文提出了“变长存储块的Hash树优化方法”（Changeable Chunk based Hash Tree Optimizing Approach，简称为CC-HTree）。3.1 CC-HTree基本原理CC-HTree基本思想是：维持Hash树的基本结构不变，将存储区分为热访问区域和非热访问区域，通过在热访问区和非热访问区设置不同的数据块大小，来减少Hash树的叶节点总数（树的规模也相应变小），从而缩短校验路径，减小Hash计算次数，最终达到减小代价、提高校验性能的目的。另CC-HTree采用联机校验方式，即每次存储器修改都立即更新Hash树。由局部性原理可知，并非整个存储器空间中任何区域在给定时间段内都被等概率地访问，而是存在频繁与不频繁之分，这里被频繁访问的区域（访问聚簇区）即为热访问区域。其他区域均为非热访问区，根据执行的程序不同，热访问区可大可小，且位置可不连续。 这一想法与Hash树相结合，得到了带热访问区域的Hash树。如图2所示，在每个热访问区，将内存区域分成多个大小相等的、较小的存储器块。而在非热访问区，将内存区域分成多个大小相等的存储块，且存储块比热访问区设置的更大（一般成倍数关系）。这样在存储区一定的情况下，非热访问区的存储块数量会相应减少，叶节点的数量也相应减少，进而降低树的高度，也即缩短校验路径。 图3 变长存储块的Hash树从整个被保护的空间来看，热访问区在整个被保护区所占比例较小，非热访问区所占比例较大。在校验和更新数据时，由局部性原理，热访问区有更高的访问频率，同时存储块较小(计算速度快)，即进行频繁且快速的Hash计算；而非热访问区访问频率较低，同时存储块较大(计算速度慢)，即进行不频繁且慢速的Hash计算，从而使总的代价降低，CC-HTree结构如图3所示，图中节点h1-h8和相应Hash树内部节点组成了热访问区，其余为非热访问区（仅为了说明问题，实际的热访问区可能很大，且不止一个）。为方便说明，借鉴了文献4中访问窗口的概念。在热访问区中更小的访问区称为热访问窗口（HotWin），一个热访问区可有一个或多个HotWin，图3中h1-h4构成了一个HotWin；在非热访问区的更小的访问区称为冷访问窗口（CoolWin），一个冷访问区也可有一个或多个CoolWin。32 变长存储块规则和算法为使模型高效工作，定义若干规则和相应的算法，规则如下：(1) 访问窗口具有固定的宽度，整个被保护的存储器空间为窗口宽度的整数倍。(2) 访问窗口仅可以随着访问区的平移而在水平方向按等间距(按窗口宽度)平移。(3) HotWin 和CoolWin可为多个，其中HotWin可以连续分布以覆盖一个更大的访问聚簇区；也可以离散分布以对应多个位置不连续的访问聚簇区。(4) HotWin 和CoolWin中叶节点对应的内存块大小不同（CoolWin内对应内存块更大）。在符合规则的前提下，定义如下处理过程： 1. 切分访问区(建立访问窗口)(1) 切分热访问区根据热访问区大小，将当前热访问区内的数据切分为多个相等的HotWin，如一个HotWin不够，可设置多个HotWin来覆盖热访问区。HotWin的个数HotNum为(1) 式：HotNum=HotSpace/ HWSpace (1)其中HotSpace为热访问区对应的内存空间，HWSpace为HotWin对应的内存空间(2) 切分非热访问区将其余的要保护内存空间（即非热访问区）再切分为大小相等的，较大尺寸的CoolWin，切分的CoolWin数目CoolNum为(2)式：CoolNum=(AllSpaceHotSpace)/CoolSpace (2)其中AllSpace为所有被保护空间，HotWSpace为热访问区对应数据块大小，CoolSpace为CoolWin对应数据块大小。2. 初始化Hash树 (1) 根据上面的划分，为每