一种基于分布式平台的规则处理架构*

陈孟东，原 昊，谢向辉，吴 东

(数学工程与先进计算国家重点实验室，江苏 无锡 214125)

1 引言

随着计算机技术的发展和互联网规模的扩大，互联网安全问题也越来越受到公众的关注，为确保私人、企业乃至国家的网络安全，人们采取多种手段来保护自身的信息安全。其中很常用的方式就是对重要信息或系统进行身份认证，除军事、金融等对安全性要求极高的领域之外，操作系统、数据库、文件加密应用、流行的网络应用(如电子邮件、即时通讯工具、论坛等)都依靠身份认证机制进行用户账户或者使用权限的认证[1]。广泛使用的身份认证机制需要一个用户名和安全字符串组合的身份信息。通常使用单向哈希函数来计算摘要值，并将摘要值与用户凭据一同存储。当用户进行身份验证时，其认证系统通过接收用户输入的安全字符串，重新使用哈希函数把用户名和安全字符串转换成摘要值，并和系统存储的摘要值进行对比，以此完成认证过程[2]。通常使用的哈希函数包括MD4、MD5和SHA1等。

身份认证机制在提供安全保障的同时，也会带来一些问题。过多或者过于复杂的安全字符串会给用户带来记忆负担，一旦遗忘字符串，用户将无法获取权限或者无法访问文档，因而带来不便和损失。同时，采用安全字符串认证的系统和文档也会对国家安全部门的取证工作造成阻力[3]。为满足个人、企业和政府在这方面的需求，安全字符串的恢复技术应运而生。安全字符串的恢复通过在大量候选字符串上进行哈希运算并验证，从而找到丢失或遗忘的正确字符串，它已经成为密码学的重要研究方向之一[4]。安全字符串的恢复方法主要有暴力搜索法、字典法和时空折衷法等，其中字典法通过搜集已知的安全字符串可能的取值，形成一个字典文件，恢复时仅从这个字典文件中取值进行正向的哈希运算并和存储摘要进行比较，具有搜索空间小、命中率高的特点，是一种行之有效的方法。然而字典法也存在问题，其恢复的成功率与字典的质量密切相关，如何提高字典的覆盖空间、提升字典的质量是一个重点[5]。

由于人的记忆力限制以及个人习惯等因素，人们在设置安全字符串时常常是基于一个基础加以简单变形形成新的字符串，如增加前缀、增加后缀、大小写变换、修改部分字母等，每种变形称为一个基本规则[6,7]。几个基本规则可以组合在一起共同对字符串进行处理，称为一次变换。相反地，在字符串恢复过程中，将每一个字典条目按照一定的规则进行变形变换，形成新的安全字符串，膨胀扩大了原字典文件的规模和覆盖率，是提升字典质量的有效方法。基于规则变换的安全字符串恢复方式通过模拟人在设置安全字符串时的内在规律，进一步提升字典的质量，巧妙设置的字典结合规则变换，可以在满足搜索规模、时效等限制时，显著提升恢复的命中率。同时，使用规则变换对字典进行扩充，在处理单元内部进行规则的处理以及新字符串的生成，还可以减少字典本身的存储和传输需求，解决哈希计算模块和字典存取模块之间的速度差异问题，保证整体的恢复效率。这种恢复方式越来越受到重视，多个研究证明了采用规则变换的有效性[8 - 10]。基于规则变换的安全字符串恢复过程如图1所示，图中虚线框内为规则的处理过程，新生成的字符串数量是原字典条目数与变换条目数的乘积。

Figure 1 Secure string recovery process based on rule transformation图1 基于规则变换的安全字符串恢复过程

业界有许多总结积累而成的字符串变形规则，多个安全字符串恢复工具[6,7,11]都有自己支持的规则，并提供字典加规则的恢复模式。这其中，hashcat[6]应用广泛，是一款多平台的免费恢复套件，支持包括CPU、GPU(支持NVIDIA GPU和AMD GPU)、DSP、FPGA等包含OpenCL运行时的各种平台，支持Linux、Windows、MacOS多种操作系统，支持分布式处理，支持近200种算法，支持多种恢复模式，支持字典与规则的处理，其规则的处理过程主要在CPU和GPU上进行。

hashcat所采用的规则具有代表性，其共支持基本规则41种，表1列出了几种典型的基本规则，并以字符串p@ssW0rd为输入，举例说明了基本规则的变形结果。hashcat自带301 472个条目的变换文件，每次变换由一到几个基本规则组成。例如变换“{$0l”代表先循环左移，然后将字符“0”作为后缀，然后再全部变换为小写字母，所有3个基本规则处理结束后才生成1个新的字符串。

Table 1 Examples of typical rules表1 典型规则示例

性能和功耗成本是规则处理乃至安全字符串恢复系统的重要考虑因素。基本规则包括几十种，而且还有复杂的组合情况，实际使用中，在任务规模大的情况下，字典文件可能多达几亿个条目，变换文件可能包含几十万次变换，规则处理过程是一项计算量大、对处理时间要求很高的任务，到目前为止公开的实现方式中，不管是开源工具[6,7]还是学术研究[12 - 14]都是基于CPU和GPU进行处理，在处理速度、系统功耗等方面有诸多不足。本文针对hashcat自带的基本规则及其变换文件，基于现有工程中使用的安全字符串恢复系统，提出了一种适用于规则的分布式处理架构。实验结果表明该处理架构满足实际工程需求，在处理性能、系统能效等方面表现良好。

2 分布式的规则处理架构

2.1 分布式平台介绍

本文的分布式规则处理架构基于“蚁群”平台实现，蚁群平台是由众多可重构计算结点构成的计算系统，每个计算结点内含1块Zynq芯片(Zynq7030)，有低功耗 CPU 和 FPGA 混合计算核心[15]，2种异构计算资源通过高速的互连总线紧密耦合，可以支持通用计算任务和加速计算任务的并行协同执行。混合核心外围集成了1 GB的低功耗DDR内存、32 GB Flash存储器、千兆以太网接口、高速环形网接口等。蚁群硬件系统采用了模块化设计的方法，16个低功耗混合计算核心的异构结点通过2套环网构成计算板，多块计算板组成ATCA机箱，按照需求可组建包含数千、数万个结点的计算加速系统，系统结构如图2所示。

Figure 2 Structure of distributed computing platform图2 分布式计算平台结构

结点内，CPU和FPGA通过高级可扩展接口AXI(Advanced eXtensible Interface)总线相连，有4个高速接口可用于数据传输，总带宽可超过4 GB/s。结点间，FPGA通过高速串行口GTX组成高速环网，单端口传输带宽可达6.6 Gb/s；CPU通过千兆以太网相连。蚁群系统中，结点内的混合核心以及结点间均有着很高的数据传输带宽。

2.2 规则的分布式拆分

安全字符串的恢复需要在短时间内完成规则的处理，生成新的字符串以便进行验证工作，而单个计算结点的计算能力毕竟有限，因此充分利用蚁群分布式的计算资源，提升规则处理速度很有必要。如图1所示，规则处理的过程需要对所有的字典条目和规则变换条目进行处理，不同变换间、不同字典条目之间没有关联性，没有数据的交互，可以通过拆分变换文件和字典文件，将整体任务分割成不同的子任务，进行分布式并行处理，通过分布规模的扩大，提高整体的处理速度。

此外，硬件资源的限制也对分布式处理提出了需求。规则的处理是同哈希算法的验证过程结合一起使用的，规则处理生成的安全字符串需要正向的哈希运算来计算摘要值，从而和存储的摘要值进行比较，以便找到正确的安全字符串。在蚁群结点内部，主要的计算能力来自可重构FPGA，规则的处理工作以及哈希运算工作主要都是在FPGA上进行。当在1个芯片内同时实现41种基本规则时，需要占用较多的硬件资源，通过前期实验发现，在1个结点内实现所有的规则处理功能需要占用Zynq 7030芯片约70%的硬件资源，此时，对于一些简单的哈希算法，可以利用剩余30%的资源进行片上的运算验证，而对于一些复杂的哈希算法已经没有足够的面积和资源来进行片内的验证运算。而在分布式环境中，考虑将规则组合进行拆分，每个结点支持不同的基本规则，仅对部分变换进行支持，通过多个结点支持所有的规则变换功能。同时，单个结点仅支持几个基本规则，可以有足够的硬件资源来对处理的流程进行优化，从而提升每个结点内规则处理的速度。

如图3所示，对41种基本规则进行拆分，根据拆分的结果将变换文件也进行拆分，每个计算结点仅支持几种基本规则，仅处理由这几种基本规则组合形成的变换。

Figure 3 Schematic diagram of splitting of rules and transformation files图3 规则与变换文件拆分示意图

对规则的拆分，基于已有的规则变换文件进行。本文用“N组合”来表示1次变换中使用的基本规则的种类数，理论上N的取值可以从1～41。但是，对301 472个已有规则变换进行分析，可以发现N的取值只是从1～6，即并不是41种基本规则都存在组合在一起使用的情况。表2统计了已有变换文件中所有N组合出现的种类数，占据大多数的是1组合、2组合和3组合。如3组合一共出现了4 934种，这个数字是小于C(41,3)的，即不是41种基本规则中任意3种都存在组合的情况。表2的第2行是该种组合覆盖的总的变换数量，可见1组合、2组合和3组合覆盖了总的变换的99.6%，由于1组合包含在2组合和3组合中，所以规则的拆分主要针对2组合和3组合进行。

Table 2 Statistical results of rule combinations表2 规则组合的统计结果

如果每个结点仅支持1种规则组合的情况，将需要太多的计算结点，所以对规则进行拆分时，每个结点在满足资源限制的情况下应支持尽量多的规则组合。所要恢复的哈希算法已经通过硬件实现，可以知道其在芯片中的资源占用，据此可以确定剩余给规则处理的资源，而每种基本规则的资源占用情况通过前期实验也可以获得。根据以上数据，可以将基本规则拆分成不同的组合，具体拆分时，按照图4所示流程进行。根据基本规则拆分的结果，将三十余万个变换也进行拆分，形成较小的任务课题，对应到蚁群结点上。

Figure 4 Flow chart for rule splitting图4 规则拆分流程图

2.3 硬件规则处理器

对基本规则进行拆分后，每个结点仅需要支持几个基本规则即可。规则的处理功能主要在可重构FPGA上实现，只需占用较少的硬件资源，保证哈希算法的处理性能。处理时，该结点对应的字典文件和变换文件存放于片外DDR内存中，通用ARM核心配置好字典文件与变换文件的大小以及存储位置，FPGA便可以自动通过AXI总线从片外获取字典和变换，并解析处理，生成新的字符串。

硬件规则处理器总体结构如图5所示，其主体为规则执行单元REU (Rule Execute Unit)。REU负责各个规则的处理功能；译码电路负责对变换中的基本规则进行译码，对各个REU进行调度；总线接口电路包含AXI总线接口，并负责与片外的数据交互；预处理电路负责将连续存储在一起的变换和字典数据处理成变换条目和字典条目，数据交互网络负责REU间数据的交互以及将最终生成的安全字符串写入FIFO中供哈希算法模块使用。

Figure 5 Hardware structure rule processor图5 硬件规则处理器结构图

因为哈希算法模块以流水线实现，每个时钟周期都可以对1个安全字符串进行验证，对规则执行的速度提出很高的要求，为了尽量提升规则执行的速度，设计中将单个规则执行的过程进行优化，使其在1个时钟周期内完成，在译码电路的调度下，做到1个时钟周期处理完1个基本规则，当规则组合在一起进行1次变换时，1次变换的执行过程示意图如图6所示，图6以3次规则组合使用为例进行说明，3个时钟周期执行完毕。

Figure 6 Schematic diagram of execution process of one transformation图6 1次变换的执行过程示意图

对于大量存在的规则组合使用的情况，即便1个基本规则在1个时钟周期之内执行完成，完整的变换过程处理完毕，生成1个新的字符串仍需要多个周期，几个规则组合在一起便需要几个周期完成。此时，每个时刻只有1个REU在工作，处理效率较低。因此，需要在译码电路的控制下，尽量将整个变换过程做到全流水实现。

在只有1套规则处理单元的情况下，只有满足同一时刻不能有处理单元的冲突，才可以做到全流水处理。通过对hashcat自带变换文件的分析发现，大多数情况下，1次变换不使用相同的基本规则，据此设计了全流水的执行结构，执行结构的示意图如图7所示。此时，每1个时钟周期都有1个安全字符串处理完毕，都有1个新的字符串产生，每1个时刻都有多个规则执行单元在同时工作，无需插入气泡，无需等待，最大限度提升了规则处理的效率。对于另外少部分的情况，在1次变换中存在相同基本规则时，通过译码电路的有效控制，字符串严格按照串行方式进行处理，1个安全字符串完全处理完毕后才开始下1个处理工作，此时生成1个新的字符串需要多个时钟周期。

Figure 7 Rule execution architecture supporting full flow图7 支持全流水的规则执行结构

3 实验结果

为验证所设计的分布式规则处理架构的功能正确性和性能指标，本文在蚁群分布式平台上进行了开发实现，并针对不同的情况进行了测试，分析了其性能以及功耗情况，并与其他平台的运行结果进行了对比分析。

3.1 硬件规则处理器实验

在蚁群结点的ARM通用计算核心上开发配置管理程序，通过Vivado工具对FPGA设计部分进行综合与实现，结果显示，单结点的硬件规则处理器运行结果正确，可以达到的最高工作频率为150 MHz。

本文首次以FPGA硬件进行规则的解析处理工作，并与Intel CPU和NVIDIA GPU上的软件实现进行对比。将相同的规则文件和字典文件分别在CPU和GPU上运行，并与本文的硬件规则处理器的结果进行对比分析，对比了处理性能和功耗2个方面。软件实现采用最新的hashcat 5.1.0进行，hashcat号称是业界最快的恢复工具[6]，软件的结果与其运行平台有很大的关系，如NVIDIA GPU中其桌面产品和专门用于高性能计算的产品，计算能力差距非常大，本文选取主流偏上的产品平台进行实验，采用的CPU平台为：Intel(R)Core(TM)i7-6700 CPU @ 3.40 GHz，32 GB内存，GPU平台为：NVIDIA GeForce GTX 1080 Ti。

对于变换情况，在每种平台上分别测试了1组合、2组合和3组合的情况，字典中字符串的长度以8个字符为例进行实验，处理性能以每秒生成多少兆个新字符串进行统计，结果如表3所示。

Table 3 Performance comparison of different platforms when dictionary length is 8表3 字典长度为8时不同平台的性能对比 M个/s

通过分析可以发现：在全流水情况下，规则的组合情况对本文处理器的处理性能没有影响，但对CPU和GPU平台的影响较大，规则组合的次数越多，其处理性能越差。2或者3个基本规则组合在一起进行1次变换占据绝大多数情况，此时规则处理器每秒生成150M个新字符串，处理性能优于CPU平台，差于GPU平台。然而，当使用该规则处理器来构建大规模、分布式的规则处理系统时，其计算能力会显著增加。

在规则处理过程中，对蚁群结点和GPU平台的运行功耗进行观测，CPU的功耗以65 W计算，计算性能功耗比(每瓦特每秒可以处理的规则变换数量)，结果如图8所示。对于2个或者3个基本规则组合在一起的情况，本文硬件规则处理器的性能功耗比相比于GPU提升1.4倍～2.1倍，相比于CPU提升49～70倍，在能效方面具有优势。

Figure 8 Comparison of energy efficiency on different platforms图8 不同平台间的能效对比

3.2 分布式拆分实验

根据每个结点可以使用的硬件资源，将41种基本规则拆分成不同的小的集合，利用蚁群系统的分布式资源，支持所有三十余万条目的规则变换。对规则进行拆分时，结合2种实际的工作环境进行：一种是哈希算法较复杂，留给规则处理的硬件资源较少的情况；另一种是哈希算法较简单的情况。在分布式环境中，利用每个计算结点有限的硬件资源，实现完整的规则处理功能所需要的拆分数量如表4所示。

Table 4 Results of rules splitting 表4 规则拆分结果

对表4进行分析可以发现，所需要的拆分数量受可用资源的影响较大。对于复杂算法，单个结点上留给规则处理的硬件资源较少，需要较大的分布规模才能完全实现所有的规则处理功能。对于简单算法，片上留给规则处理的资源较多，只需较小的分布规模即可实现完整的规则处理功能。

在192个结点规模的蚁群系统上进行分布式规则处理架构的实现，此时蚁群系统的形态为14U的标准ATCA机箱。通过脚本语言开发自动化工具，调用Vivado工具，对规则拆分后各结点的FPGA逻辑进行综合与实现，生成比特流文件；在ARM通用计算核心上开发配置管理程序，对硬件规则处理器进行配置管理；根据分布式系统的规模限制，结合FPGA的可重构特性，对字典和变换文件进行划分，形成子课题；通过蚁群系统的Condor分布式管理程序进行任务的分配管理。最终结果显示，分布式规则处理架构运行结果正确。因为规则处理任务结点间没有数据的交互，结合课题的划分和FPGA的重构，实际运行性能为单结点的192倍，性能相比GPU提升2.4～3.6倍，相比CPU提升288～411倍，能效相比GPU提升1.4～2.1倍，相比CPU提升49～70倍。

4 结束语

字符串变换规则在安全字符串的恢复中具有重要作用，其处理过程复杂，对处理性能、系统功耗有很高的要求，本文针对这些需求，提出分布式的规则处理架构，并首次采用FPGA硬件加速规则的处理过程，有效利用蚁群计算平台的分布式计算资源，利用FPGA高并行、低功耗的特点，构建了规则处理架构，并进行了设计实现。实验结果表明，该分布式规则处理架构处理性能高、运行功耗低，能效相比CPU、GPU有显著提升，随着分布式规模的扩大可以达到很高的计算性能，满足实际工程需求。