一種基于分布式平臺的規則處理架構*

陳孟東，原 昊，謝向輝，吳 東

(數學工程與先進計算國家重點實驗室，江蘇 無錫 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有顯著提升，隨著分布式規模的擴大可以達到很高的計算性能，滿足實際工程需求。