面向申威眾核處理器的規(guī)則處理優(yōu)化技術(shù)

張振東 王 彤 劉 鵬,3

1 （浙江大學(xué)信息與電子工程學(xué)院 杭州 310027）

2 （之江實(shí)驗(yàn)室智能超算研究中心 杭州 311100）

3 （數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 江蘇無(wú)錫 214125）

（zhendong404@zju.edu.cn）

隨著以申威系列處理器[1]和“神威·太湖之光”[2]為代表的國(guó)產(chǎn)處理器和國(guó)產(chǎn)超算性能的突飛猛進(jìn)，越來(lái)越多的應(yīng)用[1,3]開(kāi)始利用申威處理器的主核+從核陣列的架構(gòu)優(yōu)勢(shì)實(shí)現(xiàn)性能提升. 口令恢復(fù)系統(tǒng)因其對(duì)信息安全、國(guó)防軍工的重要意義也成為了申威處理器平臺(tái)上的熱門(mén)研究問(wèn)題.

一般口令恢復(fù)系統(tǒng)可以分為口令生成和口令驗(yàn)證2 個(gè)部分，其中口令生成負(fù)責(zé)產(chǎn)生可能包含正確口令的口令搜索空間，口令驗(yàn)證則負(fù)責(zé)驗(yàn)證口令搜索空間中的口令的正確性. 當(dāng)前大多數(shù)基于申威處理器的口令恢復(fù)系統(tǒng)研究主要關(guān)注對(duì)口令驗(yàn)證部分的并行優(yōu)化. 常見(jiàn)的方案是利用主核產(chǎn)生口令，然后將口令驗(yàn)證部分劃分并分配給申威處理器的從核陣列，利用多個(gè)從核并行執(zhí)行實(shí)現(xiàn)加速. 對(duì)于口令生成部分，這些研究均只采用了掩碼方式生成口令. 由于掩碼方式的生成速度較快，這種方案不會(huì)產(chǎn)生口令生成性能瓶頸，但掩碼方式的猜測(cè)命中率較低，因此不能覆蓋實(shí)際應(yīng)用場(chǎng)景.

基于規(guī)則的口令生成是另一種主流的口令生成方式，相關(guān)研究[4]表明使用規(guī)則可以獲得比字典和掩碼方式更高的猜測(cè)命中率，因此規(guī)則模式也成為了Hashcat[5]和John the Ripper[6]等主流口令恢復(fù)工具中流行的口令生成方式. 然而由于規(guī)則處理的過(guò)程比掩碼更加復(fù)雜，規(guī)則模式下的口令生成速度成為性能瓶頸. 以神威·太湖之光超算使用的SW26010 處理器為例，其單個(gè)主核的規(guī)則處理速度約為3 MPPS（million passwords per second），而SW26010 處理器單個(gè)從核陣列執(zhí)行NTLM，MD5 等加密算法時(shí)速度可達(dá)到100 MPPS 以上，現(xiàn)有方案下申威處理器的規(guī)則模式性能大約只有其理論峰值性能的1/30.申威處理器平臺(tái)上規(guī)則處理實(shí)現(xiàn)方案造成性能瓶頸的原因有2 個(gè)方面：一是現(xiàn)有方案下規(guī)則處理算法由主核完成，一個(gè)主核要負(fù)責(zé)生成64 個(gè)從核需要的口令，對(duì)于包括NTLM，MD5，SHA1 在內(nèi)的眾多加密算法，64 個(gè)從核每秒消耗的口令數(shù)量遠(yuǎn)大于一個(gè)主核每秒生成的口令數(shù)量；二是當(dāng)前大多數(shù)加密算法都使用了申威單指令多數(shù)據(jù)流（single instruction multiple data, SIMD）指令集進(jìn)行向量?jī)?yōu)化，而規(guī)則處理算法的SIMD 向量?jī)?yōu)化則缺少相關(guān)研究，因此規(guī)則處理算法的速度瓶頸表現(xiàn)得更加突出.

為了突破申威處理器上的規(guī)則處理速度瓶頸，進(jìn)一步提升口令恢復(fù)系統(tǒng)的性能，增強(qiáng)申威處理器平臺(tái)上口令恢復(fù)應(yīng)用的實(shí)用性，本文提出了面向申威處理器平臺(tái)的規(guī)則處理算法優(yōu)化方法，主要內(nèi)容和創(chuàng)新點(diǎn)包括4 點(diǎn)：

1） 從線程級(jí)、數(shù)據(jù)級(jí)2 個(gè)維度分析了規(guī)則處理算法的可并行度，針對(duì)申威處理器主核執(zhí)行規(guī)則處理算法速度慢的問(wèn)題，提出了并行任務(wù)映射機(jī)制，實(shí)現(xiàn)了規(guī)則處理算法的并行任務(wù)分解和從核陣列加速.

2） 針對(duì)如何高效利用從核局部數(shù)據(jù)存儲(chǔ)器（local data memory, LDM）空間降低口令和規(guī)則數(shù)據(jù)傳輸開(kāi)銷的問(wèn)題，提出了從核緩沖區(qū)配比優(yōu)化機(jī)制，通過(guò)對(duì)從核數(shù)據(jù)通信量、通信時(shí)間建模，運(yùn)用非線性優(yōu)化理論求解了最優(yōu)的口令、數(shù)據(jù)緩沖區(qū)容量配比，相比等容量分配策略使數(shù)據(jù)通信時(shí)間和通信量分別減少了40.5%和44.7%；通過(guò)變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制減緩了規(guī)則數(shù)據(jù)冗余造成的通信開(kāi)銷問(wèn)題，使通信時(shí)間和通信量分別下降了89.0%和89.3%.

3） 針對(duì)從核間計(jì)算量分配不均勻?qū)е碌募铀俦认陆祮?wèn)題提出了負(fù)載均衡機(jī)制，使負(fù)載不均勻情況下的規(guī)則處理整體執(zhí)行時(shí)間減少了13.5%.

4） 針對(duì)現(xiàn)有規(guī)則函數(shù)實(shí)現(xiàn)不能充分利用申威SIMD 指令集優(yōu)勢(shì)的問(wèn)題，提出了41 種規(guī)則函數(shù)的SIMD向量?jī)?yōu)化方案，結(jié)合不同類型規(guī)則函數(shù)的計(jì)算訪存模式，利用申威SIMD 指令集提供的特殊指令實(shí)現(xiàn)了大小寫(xiě)轉(zhuǎn)換、字符匹配、字符移動(dòng)等操作的向量?jī)?yōu)化，將部分規(guī)則函數(shù)執(zhí)行的時(shí)鐘周期降低了50%.

實(shí)驗(yàn)結(jié)果表明，應(yīng)用本文提出的優(yōu)化方案后，現(xiàn)有口令恢復(fù)系統(tǒng)的規(guī)則模式口令恢復(fù)速度在不同規(guī)則集下提升了30～101 倍.

1 研究背景與相關(guān)工作

1.1 申威處理器指令集架構(gòu)

圖1 展示了神威·太湖之光超算中使用的申威系列SW26010 處理器的核組架構(gòu)[7]. 每個(gè)核組包含一個(gè)主核和一個(gè)從核陣列，每個(gè)從核陣列由8 行8 列共64 個(gè)從核組成. 核組內(nèi)部，主核與從核陣列的運(yùn)行頻率均為1.5 GHz，每個(gè)主核包含5 條整數(shù)流水線和2條SIMD 浮點(diǎn)流水線. 主核的L1 指令緩存、L1 數(shù)據(jù)緩存均為32 KB，L2 緩存大小為512 KB.從核陣列中每個(gè)從核包含1 條整數(shù)流水線和1 條SIMD 流水線.每個(gè)從核還配備了64 KB 的LDM，從核訪問(wèn)LDM 的開(kāi)銷為4 個(gè)時(shí)鐘周期，因此LDM 被廣泛用于緩存外部主存中的數(shù)據(jù). 在存儲(chǔ)器方面，每個(gè)核組可通過(guò)本地存儲(chǔ)控制器訪問(wèn)8 GB DDR3 外部存儲(chǔ)器. 主核與從核陣列可以離散地訪問(wèn)外部存儲(chǔ)器中的數(shù)據(jù)，也可以通過(guò)直接存儲(chǔ)訪問(wèn)（direct memory access, DMA）方式批量訪問(wèn)從而提高訪存性能.

Fig.1 Architecture of a SW26010 processor core group圖1 SW26010 處理器核組架構(gòu)

指令集方面SW26010 處理器采用了申威自主設(shè)計(jì)的64 b 精簡(jiǎn)指令集體系架構(gòu)，該指令集除了支持常用的標(biāo)量8 b，16 b，32 b，64 b 整數(shù)運(yùn)算和單精度、雙精度浮點(diǎn)運(yùn)算外，還支持256 b 的SIMD 向量指令.利用申威SIMD 指令集，SW26010 處理器每個(gè)從核每個(gè)時(shí)鐘周期最多可以完成8 次單精度浮點(diǎn)運(yùn)算或4次雙精度浮點(diǎn)運(yùn)算或8 次32 b 整數(shù)運(yùn)算. 此外，申威SIMD 指令集還支持256 b 整數(shù)運(yùn)算指令，此時(shí)SIMD 向量寄存器中的數(shù)據(jù)被視為1 個(gè)256 b 的整數(shù)，對(duì)該整數(shù)可以進(jìn)行邏輯左移、邏輯右移等操作. 合理利用此類指令可以高效地實(shí)現(xiàn)規(guī)則處理算法中的部分規(guī)則函數(shù).

1.2 規(guī)則與規(guī)則函數(shù)

在口令生成領(lǐng)域，規(guī)則本質(zhì)上是一種形式化描述語(yǔ)言. 一條規(guī)則由1 個(gè)或多個(gè)規(guī)則函數(shù)組成，這些規(guī)則函數(shù)可以實(shí)現(xiàn)對(duì)口令的修改、截取、擴(kuò)展、復(fù)制等操作.表1 列舉了Hashcat 中部分常用的規(guī)則函數(shù)，完整的規(guī)則函數(shù)列表可見(jiàn)Hashcat 官網(wǎng)[8]. 每個(gè)規(guī)則函數(shù)都使用一個(gè)字符作為其標(biāo)識(shí)符，例如“u”“T”“*”“r”“^”. 部分規(guī)則函數(shù)在其標(biāo)識(shí)符后面還跟隨了1 個(gè)或2 個(gè)字符組成的參數(shù)，例如“^X”的參數(shù)為X，“*NM”的參數(shù)為N和M. 通過(guò)分析真實(shí)的泄露口令庫(kù)的特征并將其表達(dá)成各種規(guī)則函數(shù)的組合形式，基于規(guī)則的口令恢復(fù)成為了最靈活、準(zhǔn)確且高效的口令恢復(fù)方式[8].

Table 1 Part of the Frequently Used Rule Functions表1 常用的部分規(guī)則函數(shù)

1.3 基于規(guī)則處理的口令生成過(guò)程

在Hashcat 和John the Ripper 中，規(guī)則模式均是常用且命中率較高的恢復(fù)模式. 如圖2 所示，在使用規(guī)則模式進(jìn)行口令恢復(fù)前，用戶需要分別指定一個(gè)字典文件和一個(gè)規(guī)則文件. 字典文件中存儲(chǔ)了用于規(guī)則處理的基礎(chǔ)口令；規(guī)則文件中存儲(chǔ)了以字符串形式表示的規(guī)則，一條規(guī)則包含了若干規(guī)則函數(shù). 隨后，口令恢復(fù)系統(tǒng)依次從字典文件和規(guī)則文件中取出1條輸入口令和1 條規(guī)則，組合后送入規(guī)則變換模塊生成待驗(yàn)證口令.

Fig.2 Rule-based password generation process圖2 基于規(guī)則的口令生成過(guò)程

若以集合P={p0,p1, …,pN-1}表示輸入口令集，以集合R={r0,r1, …,rK-1}表示規(guī)則集，則規(guī)則處理過(guò)程可以用算法 1 描述，其中對(duì)每個(gè)“口令-規(guī)則”組合（pi, rj）的具體變換過(guò)程為：口令生成系統(tǒng)解析當(dāng)前的規(guī)則字符串rj，獲取其中的規(guī)則函數(shù)列表F={f0,f1, …,fs-1}，并令輸出口令t = pi，從第1 個(gè)規(guī)則函數(shù)f0開(kāi)始，依次解析出規(guī)則函數(shù)的標(biāo)識(shí)符RID 和2 個(gè)參數(shù)a0，a1，然后根據(jù)RID 調(diào)用規(guī)則函數(shù)庫(kù)中對(duì)應(yīng)的規(guī)則函數(shù)并傳入口令t和參數(shù)a0，a1，生成新的口令覆蓋t，之后重復(fù)對(duì)口令t應(yīng)用剩余規(guī)則函數(shù)，最后一個(gè)規(guī)則函數(shù)fs-1的輸出結(jié)果t即為基礎(chǔ)口令pi和規(guī)則rj生成的待驗(yàn)證口令qi×K+j. 上述過(guò)程要求任意一條口令都要和每一條規(guī)則組合1 次，因此最終生成的待驗(yàn)證口令數(shù)量為基礎(chǔ)口令數(shù)量N和規(guī)則數(shù)量K之積.換言之，通過(guò)規(guī)則處理后一個(gè)字典被擴(kuò)充為原來(lái)的K倍.

為了便于區(qū)分，后文將對(duì)規(guī)則集和口令集的處理稱為“規(guī)則處理”，對(duì)“口令-規(guī)則”組合的處理稱為“規(guī)則變換”.

算法1.基于規(guī)則的口令生成算法.

輸入：輸入口令集P，規(guī)則集R；

輸出：輸出口令集Q.

1.4 國(guó)內(nèi)外相關(guān)工作

由于申威系列眾核處理器主要應(yīng)用于國(guó)產(chǎn)超級(jí)計(jì)算機(jī)系統(tǒng)，所以目前基于申威眾核處理器的口令恢復(fù)系統(tǒng)研究主要集中在國(guó)內(nèi). 湖南大學(xué)陳玥丹[9]提出了一種神威·太湖之光上的AES 算法的異構(gòu)并行加速方案，該方案綜合利用DMA 技術(shù)與并行流水技術(shù)實(shí)現(xiàn)了高效的AES 算法加解密，相較于串行AES算法減少了89%的執(zhí)行時(shí)間；鄭州大學(xué)任必晉[1]在太湖之光上實(shí)現(xiàn)了PDF，WinZip，NTLM 這3 種算法的口令恢復(fù)加速，該方案采取了MPI+Athread 的2級(jí)并行實(shí)現(xiàn)，并使用DMA 加載切片后的口令，但該方案僅使用了主核生成口令且只實(shí)現(xiàn)了掩碼模式，因此存在規(guī)則模式的性能瓶頸；中原工學(xué)院董本松等人[3]基于SW26010 處理器實(shí)現(xiàn)了Office 加密算法的優(yōu)化方案，優(yōu)化技術(shù)包括從核并行、DMA 訪存優(yōu)化、SIMD 向量化等，但該方案中的口令生成部分仍舊為簡(jiǎn)單的掩碼模式；張恒等人[10]研究了SW26010處理器上MD5 算法的優(yōu)化技術(shù)，但同樣僅使用了掩碼模式生成口令. 可以看到，當(dāng)前基于申威系列眾核處理器的口令恢復(fù)研究均未涉及諸如規(guī)則處理等更復(fù)雜的口令生成方法，因此現(xiàn)有口令恢復(fù)系統(tǒng)在規(guī)則模式下的性能難以滿足需求，亟需對(duì)規(guī)則處理進(jìn)行優(yōu)化.

在其他處理器平臺(tái)方面，Hashcat[5]是目前主流的基于GPU 的口令恢復(fù)工具，為了解決CPU 口令生成速度瓶頸問(wèn)題，Hashcat 在GPU 上實(shí)現(xiàn)了掩碼和規(guī)則2 種口令生成算法內(nèi)核，使得口令生成和口令驗(yàn)證均在GPU 核心上完成，從而避免了大量的口令數(shù)據(jù)傳輸并且提高了口令生成速度，但Hashcat 的規(guī)則函數(shù)實(shí)現(xiàn)專門(mén)針對(duì)GPU，在申威處理器上的執(zhí)行效率不高；謝鑫君等人[11]提出了一種基于GPU 的對(duì)口令進(jìn)行窮舉的技術(shù)，該技術(shù)本質(zhì)上與基于掩碼的口令生成類似，通過(guò)GPU 多線程加速，將口令生成速度相較于CPU 提升了4 個(gè)數(shù)量級(jí)；鄭州大學(xué)董婉瑩[12]提出了一種基于口令字典樹(shù)的口令生成方法，該方法通過(guò)統(tǒng)計(jì)口令字符的頻率構(gòu)建字典樹(shù)，然后基于字典樹(shù)生成掩碼，最后利用掩碼生成口令，該方法還采用FPGA 對(duì)掩碼生成口令的過(guò)程進(jìn)行了加速，實(shí)現(xiàn)了平均12.85 倍的加速比.Zhang 等人[13]基于FPGA 提出了一種專用規(guī)則處理加速器（RUPA），解決了CPUFPGA 異構(gòu)口令恢復(fù)系統(tǒng)的口令生成瓶頸，使系統(tǒng)性能提升了245.4 倍.

在使用規(guī)則進(jìn)行口令生成的研究中，Weir 等人[14]較早地提出使用概率上下文無(wú)關(guān)文法(probabilistic context-free grammars, PCFG)學(xué)習(xí)公開(kāi)口令集的分布特征從而生成規(guī)則集，消除了傳統(tǒng)規(guī)則集設(shè)計(jì)需要依賴人工專家的弊端；Marechal[15]提出的rulesfinder工具和Kacherginsky[16]提出的PACK 工具，能夠利用機(jī)器學(xué)習(xí)自動(dòng)產(chǎn)生規(guī)則集；Nam 等人[17]利用對(duì)抗生成網(wǎng)絡(luò)方法產(chǎn)生了REDPACK 規(guī)則集，使規(guī)則處理的猜測(cè)命中率提升了至多26%；Li 等人[18]提出了一種基于密度聚類的規(guī)則生成方法，所生成的規(guī)則集的猜測(cè)命中率提升了104%. 經(jīng)過(guò)不斷的研究和探索，目前規(guī)則處理已經(jīng)成為Hashcat 和John the Ripper 中最高效的口令恢復(fù)模式，其猜測(cè)命中率接近神經(jīng)網(wǎng)絡(luò)的同時(shí)，生成速度可達(dá)到神經(jīng)網(wǎng)絡(luò)的10 倍以上[19-20].

2 規(guī)則處理算法的可并行度分析

2.1 線程級(jí)可并行度

線程級(jí)并行優(yōu)化的前提是將計(jì)算任務(wù)分解為若干相對(duì)獨(dú)立的子任務(wù)，通過(guò)圖2 可知，在規(guī)則處理過(guò)程中，一對(duì)“口令-規(guī)則”組合是其最小的處理單元，且任意“口令-規(guī)則”組合的規(guī)則變換過(guò)程互不干涉，因此可以將一次規(guī)則變換作為一個(gè)子任務(wù). 盡管一次規(guī)則變換中還包括了若干次規(guī)則函數(shù)的調(diào)用，但這些調(diào)用之間存在次序關(guān)系，因此子任務(wù)不能繼續(xù)細(xì)分到規(guī)則函數(shù)層次. 結(jié)合圖2 分析，若口令集P和規(guī)則集R的大小分別為N和K，則規(guī)則處理算法的總?cè)蝿?wù)數(shù)量為N×K，假設(shè)不同子任務(wù)具有相同的運(yùn)算時(shí)間w，則規(guī)則處理算法在串行處理器上的執(zhí)行時(shí)間為T(mén)s=N×K×w. 由于規(guī)則處理算法的各個(gè)子任務(wù)互相獨(dú)立可以完全并行執(zhí)行，根據(jù)Amdahl 定律[21]，其在并行處理器上的執(zhí)行時(shí)間為T(mén)p=N×K×w/C，其中C為并行處理器的最大線程數(shù)，因此規(guī)則處理算法的線程級(jí)可并行度為T(mén)s/Tp=C，在SW26010 處理器單個(gè)核組上的最大加速比為64.

2.2 數(shù)據(jù)級(jí)可并行度

規(guī)則處理算法經(jīng)過(guò)分解成為規(guī)則變換子任務(wù)后，每個(gè)處理器核心需要依次完成屬于自己的子任務(wù).在單個(gè)處理器核心中，規(guī)則變換子任務(wù)之間已經(jīng)無(wú)法并行. 而規(guī)則變換本質(zhì)上是對(duì)口令應(yīng)用規(guī)則函數(shù)，因此規(guī)則函數(shù)是規(guī)則變換的核心與關(guān)鍵，規(guī)則函數(shù)的性能也決定了規(guī)則變換的性能. 為了提升規(guī)則變換子任務(wù)的執(zhí)行效率，還需要探索規(guī)則函數(shù)的數(shù)據(jù)級(jí)可并行度. 在Hashcat 和John the Ripper 中常用的規(guī)則函數(shù)有41 種，這些規(guī)則函數(shù)數(shù)量眾多且類型繁雜，有必要針對(duì)其計(jì)算特點(diǎn)進(jìn)行分類討論.

根據(jù)1.3 節(jié)的分析，規(guī)則函數(shù)的輸入為口令p和2 個(gè)參數(shù)a0，a1，輸出為口令q，其C 語(yǔ)言應(yīng)用程序編程接口（application programming interface, API）如圖3所示. 在現(xiàn)有實(shí)現(xiàn)中，輸入口令p通過(guò)長(zhǎng)度為N的字符數(shù)組p[N]儲(chǔ)存，輸出口令通過(guò)字符數(shù)組q[N]存儲(chǔ)，N的取值決定了口令恢復(fù)系統(tǒng)能夠處理的最大口令長(zhǎng)度，通常取N=32.此外，口令恢復(fù)系統(tǒng)從字典文件中加載口令時(shí)會(huì)單獨(dú)計(jì)算出口令的長(zhǎng)度L，和數(shù)組p[N]一起存放于口令結(jié)構(gòu)體pwd_t中，為了提高口令的傳輸效率，口令結(jié)構(gòu)體中定義了額外的3 個(gè)占位符以保證其內(nèi)存占用為4 B 的整數(shù)倍. 參數(shù)a0，a1 主要為部分帶有可變參數(shù)的規(guī)則函數(shù)提供額外的信息，根據(jù)規(guī)則函數(shù)的不同，其意義也會(huì)產(chǎn)生變化，部分規(guī)則函數(shù)沒(méi)有可變參數(shù)，此時(shí)a0，a1 的取值對(duì)函數(shù)執(zhí)行結(jié)果無(wú)影響.

Fig.3 The unified C-language API of rule functions圖3 規(guī)則函數(shù)的C 語(yǔ)言統(tǒng)一應(yīng)用程序編程接口

根據(jù)函數(shù)內(nèi)部對(duì)字符數(shù)組p[N]的計(jì)算模式，規(guī)則函數(shù)可分為5 類：

1） 全字符遍歷變換

全字符遍歷變換（operation on all characters，OAC）函數(shù)的計(jì)算模式偽代碼如圖4 所示.OAC 函數(shù)中輸出口令與輸入口令長(zhǎng)度相同，輸出字符q[i]是與其位置相同的輸入字符p[i]，a0 和a1 的函數(shù)ROP（p[i]，a0，a1），這里函數(shù)ROP泛指包括大小寫(xiě)轉(zhuǎn)換、數(shù)值加減、移位等操作在內(nèi)的各種變換函數(shù).OAC 類型函數(shù)包括lowercase，uppercase，toggle等.

Fig.4 The computing pattern of OAC-type functions圖4 OAC 類型函數(shù)的計(jì)算模式

2） 指定字符變換

指定字符變換（operation on specified characters，OSC）函數(shù)的計(jì)算模式偽代碼如圖5 所示. 與OAC 函數(shù)類似，OSC 函數(shù)的輸出口令長(zhǎng)度與輸入口令長(zhǎng)度相同，但只有輸出字符q[a0]是輸入字符p[a0]的ROP變換，其余位置的輸出字符與輸入字符相同.OSC 類型函數(shù)包括overwrite，toggle@等.

Fig.5 The computing pattern of OSC-type functions圖5 OSC 類型函數(shù)的計(jì)算模式

3） 全字符遍歷移動(dòng)

全字符遍歷移動(dòng)（move across all chacracters，MAC）函數(shù)的計(jì)算模式偽代碼如圖6 所示.MAC 函數(shù)的輸出口令長(zhǎng)度L_new與輸入口令長(zhǎng)度L不一定相同，L_new的值由L，a0，a1 共同決定，每一個(gè)輸出字符q[i]由某個(gè)輸入字符p[idx]直接移動(dòng)得到，p[idx]的位置坐標(biāo)idx通過(guò)CalcIndex（i，L）計(jì)算得到.MAC 函數(shù)包括reverse，duplicate等.

Fig.6 The computing pattern of MAC-type functions圖6 MAC 類型函數(shù)的計(jì)算模式

4） 指定字符移動(dòng)

指定字符移動(dòng)（move across specified characters，MSC）函數(shù)的計(jì)算模式偽代碼如圖7 所示. MSC 函數(shù)的輸出口令長(zhǎng)度L_new同樣取決于L，a0，a1，但只有輸出字符q[a0]和q[a1]由其他位置的輸入字符p[idx]直接移動(dòng)得到，其余位置的輸出字符與輸入字符相同. MSC 函數(shù)包括swap_front，swap_back，replace_N+1 等.

Fig.7 The computing pattern of MSC-type functions圖7 MSC 類型函數(shù)的計(jì)算模式

5） 指定字符清除

指定字符清除函數(shù)purge是單獨(dú)成類的一個(gè)規(guī)則函數(shù)，其計(jì)算模式與前面4 種函數(shù)有較大差異，如圖8 所示. 函數(shù)purge的功能是去除口令p[N]中ASCII 值等于a0 的所有字符，留下其余的字符作為輸出字符. 這種情況下，盡管輸出字符q[i]仍由某個(gè)輸入字符p[idx]直接移動(dòng)得到，但p[idx]的位置坐標(biāo)idx無(wú)法通過(guò)i和L直接計(jì)算，而是與輸入字符的ASCII值p[0]，p[1]，…，p[N-1]有關(guān)，因此必須依次讀取并比較所有輸入字符的值才能最終確定輸出字符.

Fig.8 The computing pattern of the purge function圖8 函數(shù)purge 的計(jì)算模式

上述5 類規(guī)則函數(shù)的主體部分均為一個(gè)for 循環(huán)，循環(huán)次數(shù)為輸入口令長(zhǎng)度L或輸出口令長(zhǎng)度L_new，除函數(shù)purge外，OAC，OSC，MAC，MSC 函數(shù)中的for循環(huán)體之間均無(wú)依賴關(guān)系，因此各循環(huán)體理論上可以完全并行執(zhí)行，其數(shù)據(jù)級(jí)可并行度為L(zhǎng)或L_new.然而現(xiàn)有規(guī)則函數(shù)實(shí)現(xiàn)方案無(wú)法發(fā)揮SW26010 處理器從核核心的數(shù)據(jù)級(jí)并行能力，這是因?yàn)槊總€(gè)從核核心只具有1 條整數(shù)流水線和1 條256 b 的SIMD 流水線，現(xiàn)有規(guī)則函數(shù)實(shí)現(xiàn)方案只能利用其中的整數(shù)流水線達(dá)成每條指令處理4 個(gè)字符，而無(wú)法利用256 b 的SIMD 流水線.

3 線程級(jí)并行優(yōu)化技術(shù)

3.1 主從核任務(wù)分配機(jī)制

SW26010 處理器的一個(gè)核組主要由1 個(gè)主核與64 個(gè)從核構(gòu)成，其中主核適合復(fù)雜邏輯運(yùn)算和I/O 操作，從核適合相對(duì)簡(jiǎn)單但可并行的運(yùn)算，主核、從核需要合理的分工才能發(fā)揮各自的性能優(yōu)勢(shì). 圖9 展示了本文提出的規(guī)則處理系統(tǒng)的主從核任務(wù)分配機(jī)制，圖中的處理器系統(tǒng)被簡(jiǎn)化為主核、從核陣列和主存3 個(gè)部分. 其中，主核負(fù)責(zé)解析輸入?yún)?shù)，根據(jù)輸入?yún)?shù)從硬盤(pán)中讀取字典文件和規(guī)則文件，并對(duì)字典文件和規(guī)則文件進(jìn)行預(yù)處理，生成口令數(shù)組、規(guī)則數(shù)組以及口令數(shù)量、規(guī)則數(shù)量等參數(shù)，然后啟動(dòng)從核陣列進(jìn)行規(guī)則變換；從核陣列主要負(fù)責(zé)處理規(guī)則變換子任務(wù)，根據(jù)主核生成的參數(shù)，每個(gè)從核找到自己對(duì)應(yīng)的子任務(wù)集然后執(zhí)行規(guī)則變換，規(guī)則變換生成的輸出口令集存儲(chǔ)于LDM 中，供后續(xù)口令驗(yàn)證任務(wù)使用.

Fig.9 Task assignment policy of the master core and the slave core圖9 主從核任務(wù)分配機(jī)制

3.2 子任務(wù)映射機(jī)制

在線程級(jí)并行優(yōu)化中，如何將規(guī)則變換子任務(wù)映射到眾核處理器的各個(gè)從核是首先要解決的問(wèn)題.根據(jù)2.1 節(jié)所述，大小分別為N和K的口令集和規(guī)則集組合成的子任務(wù)集大小為N×K，此處暫時(shí)假定所有子任務(wù)的運(yùn)算量相同，按照規(guī)則處理的流程，需要將子任務(wù)集劃分為64 等份分配給64 個(gè)從核，其中每份的子任務(wù)數(shù)量為N×K/64.為實(shí)現(xiàn)子任務(wù)集的劃分，一般有共用口令映射（share passwords mapping, SPM）和共用規(guī)則映射（share rules mapping, SRM）兩種方案，如圖10 所示. 在共用口令映射方案中，規(guī)則集R被均勻劃分為64 個(gè)子集R0，R1，…，R63，分別分配給從核0、從核1、…、從核63，而口令集則不經(jīng)劃分直接分配給所有從核. 與之相反，共用規(guī)則映射方案中，口令集被均勻劃分并分配給64 個(gè)從核，規(guī)則集則不劃分.

Fig.10 Sub-task mapping scheme of slave cores圖10 從核子任務(wù)映射方案

在規(guī)則處理的過(guò)程中，由于從核的局存不能存儲(chǔ)完整的口令集和規(guī)則集，因此必須以分塊的方式進(jìn)行加載. 口令和規(guī)則的加載也有2 種方案：一種是口令外循環(huán)-規(guī)則內(nèi)循環(huán)（password-out-rule-in, PORI），即在外部循環(huán)中讀取口令分塊，在內(nèi)部循環(huán)中讀取規(guī)則分塊；另一種則是口令內(nèi)循環(huán)-規(guī)則外循環(huán)（passwordin-rule-out, PIRO）. 任務(wù)映射方式和數(shù)據(jù)加載方式兩兩組合能夠得到4 種方案，分別為SRM-PORI，SRM-PIRO，SPM-PORI，SPM-PIRO.

任務(wù)映射方式和口令規(guī)則加載方式主要影響了從核陣列整體與主存間的數(shù)據(jù)通信量，若每條口令數(shù)據(jù)大小為u字節(jié)，每個(gè)口令塊包含x條口令，每條規(guī)則數(shù)據(jù)大小為v字節(jié)，每個(gè)規(guī)則塊包含y條規(guī)則，則以上4種方案下核組的總數(shù)據(jù)通信量可由式（1）近似計(jì)算：

由式（1）可以看出

因此在PORI 方案下使用SRM 映射的數(shù)據(jù)通信量更小，在PIRO 方案下則應(yīng)該使用SPM 機(jī)制，而WSRM-PORI與WSPM-PIRO的大小關(guān)系則與N，K，u，v，x，y的具體取值有關(guān)，后文若無(wú)特別說(shuō)明，默認(rèn)基于SRMPORI 方案展開(kāi)討論.

3.3 從核緩沖區(qū)配比優(yōu)化機(jī)制

SW26010 處理器中每個(gè)從核具有64 KB 的LDM，利用好局部緩存提升從核的數(shù)據(jù)訪問(wèn)效率同樣是并行優(yōu)化的關(guān)鍵. 在規(guī)則處理算法中，輸入口令集P、規(guī)則集R，以及生成的輸出口令集Q都需要一定的存儲(chǔ)空間. 通常情況下，上述3 個(gè)集合占用的空間均遠(yuǎn)大于從核的局部緩存空間，因此必須對(duì)輸入口令集P、規(guī)則集R、輸出口令集Q進(jìn)行分塊讀取和寫(xiě)入，這里不妨將它們對(duì)應(yīng)的局部緩沖區(qū)稱為P 緩沖、R 緩沖和Q 緩沖，優(yōu)化P，R，Q 這3 種緩沖區(qū)的容量配置能夠減少?gòu)暮藢?duì)主存的數(shù)據(jù)訪問(wèn)量，提升規(guī)則處理訪存性能和降低訪存能量消耗.

為了分析有限LDM 空間下P，R，Q 這3 種緩沖區(qū)容量的最佳配比，首先需要介紹本文提出的從核規(guī)則處理任務(wù)執(zhí)行機(jī)制，如算法 2 所示. 首先每個(gè)從核使用系統(tǒng)調(diào)用函數(shù)GetSlaveCoreID獲得自己的從核ID 號(hào)cid（cid= 0，1，…，63），然后根據(jù)cid和任務(wù)映射機(jī)制M計(jì)算從核需要處理的口令集和規(guī)則集的起始位置和大小. 共用口令映射時(shí)口令集的起始位置p_idx= 0，口令集大小n=N， 規(guī)則集的起始位置r_idx=K×cid/64，規(guī)則集大小k=K/64；共用規(guī)則映射時(shí)p_idx=N×cid/64，n=N/64，r_idx= 0，k=K. 確定從核需要處理的口令集和規(guī)則集后，從核進(jìn)入一個(gè)雙重循環(huán)，在外循環(huán)（口令循環(huán)）中從核每次加載x條口令到P 緩沖中，然后執(zhí)行內(nèi)循環(huán)（規(guī)則循環(huán)），在內(nèi)循環(huán)中，從核每次加載y條規(guī)則到R 緩沖中，然后對(duì)P緩沖和R 緩沖中的口令子集和規(guī)則子集進(jìn)行處理，生成的輸出口令子集存儲(chǔ)于Q 緩沖中，用于后續(xù)口令驗(yàn)證過(guò)程，不寫(xiě)回主存.

算法2.從核規(guī)則處理任務(wù)執(zhí)行機(jī)制.

輸入：輸入口令集P，規(guī)則集R，映射機(jī)制M；

輸出：是否破解成功cracked.

①cid←GetSlaveCoreID（）；

②p_idx，n←GetMyPasswordSet（M，cid）；

③r_idx，k←GetMyRuleSet（M，cid）；

④i← 0；

⑤ whilei＜ndo

⑥Pbuf←DMALoadPassword（P，p_idx+i，x）；

⑦j← 0；

⑧ whilej＜kdo

⑨Rbuf←DMALoadRule（R，r_idx+j，y）；

⑩cracked←RunRuleProcess（Pbuf，Rbuf）；

?j←j+y；

? end while

?i←i+x；

? end while

? returncracked；

? procedureRunRuleProcess（Pbuf，Rbuf）

?cracked← 0；

?s← 0；

? fori= 1 →xdo

? forj= 1 →ydo

?Qbuf[s]←ApplyRule（Pbuf[i]，Rbuf[j]）；

?s←s+ 1；

? ifs=zthen

?cracked←PasswordValidate（Qbuf）；

?s← 0；

? end if

? end for

? end for

? ifs＞ 0 then

?cracked←PasswordValidate（Qbuf）；

? end if

? returncracked；

? end procedure

下面首先考慮算法 2 中單個(gè)從核與主存間的數(shù)據(jù)通信量和通信時(shí)間. 設(shè)每條口令占用的存儲(chǔ)空間為u字節(jié)，每條規(guī)則占用的存儲(chǔ)空間為v字節(jié)，于是口令循環(huán)的循環(huán)次數(shù)為「n/x」，每次循環(huán)讀取的口令數(shù)據(jù)量為ux；規(guī)則循環(huán)的循環(huán)次數(shù)為「k/y」，每次循環(huán)讀取的規(guī)則數(shù)據(jù)量為vy；因此算法 2 中口令數(shù)據(jù)總讀取量為WP=ux×「n/x」、規(guī)則數(shù)據(jù)總讀取量為WR=vy×「k/y」×「n/x」. 由于輸出口令集Q不會(huì)被寫(xiě)回主存，Q 緩沖的大小不影響數(shù)據(jù)通信量和通信時(shí)間，所以參數(shù)z未出現(xiàn)在WP和WR的表達(dá)式中. 盡管WP和WR的表達(dá)式中所有變量均為自然數(shù)，為了簡(jiǎn)化分析，后文中將其取值范圍定為[1, +∞），即不小于1 的實(shí)數(shù).

在算法 2 中，從核使用DMA 技術(shù)與主存進(jìn)行數(shù)據(jù)傳輸，DMA 讀寫(xiě)數(shù)據(jù)的開(kāi)銷可以分為兩部分：一部分是DMA 啟動(dòng)的固定開(kāi)銷D；另一部分是隨傳輸數(shù)據(jù)量線性增加的數(shù)據(jù)傳輸開(kāi)銷g. 因此算法 2 中數(shù)據(jù)傳輸?shù)目倳r(shí)間T可以用式（3）計(jì)算. 由于大多數(shù)情況下有n?x和k?y，并且程序會(huì)自動(dòng)調(diào)整最后一輪循環(huán)加載的數(shù)據(jù)量，因此式（3）中的向上取整符號(hào)可以近似忽略.

根據(jù)需要分析的參數(shù)不同，式（3）有不同的詮釋方法，顯而易見(jiàn)的有：

1） 口令集和規(guī)則集越大，則n和k越大，通信時(shí)間T越大；

2） DMA 的傳輸速率越大、固定開(kāi)銷越小，則g和D越小，通信時(shí)間T越小；

3） 單條口令和規(guī)則的存儲(chǔ)空間越小，則u和v越小，通信時(shí)間T越小.

當(dāng)研究給定口令集和規(guī)則集下的最佳P 緩沖和R 緩沖配比（即x和y的取值）時(shí)，式（3）中u，v，k，n，g，D可以視為常數(shù)，并且P 緩沖、R 緩沖、Q 緩沖的總?cè)萘看笮∈軓暮薒DM 大小限制，x、y還應(yīng)滿足ux+vy≤S，其中S為除去Q 緩沖外可用于緩沖的LDM空間大小. 因此數(shù)據(jù)通信時(shí)間T的最小值計(jì)算可轉(zhuǎn)化為一個(gè)非線性優(yōu)化問(wèn)題，如式（4）所示. 對(duì)式（4）求解可得式（5）.

通過(guò)實(shí)際測(cè)試SW26010 中從核DMA 的性能，測(cè)得式（5）中g(shù)≈ 2.069×10-9s/B，D≈ 5.172×10-7s. 此外，通常單條規(guī)則數(shù)據(jù)大小4 ≤v≤128，規(guī)則數(shù)量k＞ 100，據(jù)此可計(jì)算出式（5）中

由于1/kv?1/40，該項(xiàng)可忽略不計(jì)，因此式（5）中x*和y*幾乎不隨k的取值發(fā)生變化. 換言之，P 緩沖、R 緩沖大小的最佳配比與口令集大小n和規(guī)則集大小k均無(wú)關(guān). 根據(jù)這一結(jié)論，設(shè)計(jì)程序時(shí)可以結(jié)合實(shí)際可用的LDM 空間計(jì)算最佳的P 緩沖、R 緩沖大小，從而減少?gòu)暮岁嚵信c主存的通信時(shí)間和通信量.

3.4 口令規(guī)則數(shù)據(jù)結(jié)構(gòu)優(yōu)化技術(shù)

式（3）揭示了從核數(shù)據(jù)通信時(shí)間T與口令數(shù)據(jù)大小u和規(guī)則數(shù)據(jù)大小v正相關(guān)，因此減小口令數(shù)據(jù)大小和規(guī)則數(shù)據(jù)大小能夠降低從核數(shù)據(jù)通信開(kāi)銷.在現(xiàn)有實(shí)現(xiàn)中，每條口令采用36 B 存儲(chǔ)，每條規(guī)則采用128 B 存儲(chǔ)，其C 語(yǔ)言結(jié)構(gòu)體如圖11 所示. 其中每個(gè)規(guī)則結(jié)構(gòu)體rule_t由一個(gè)數(shù)組rfs[32]構(gòu)成，數(shù)組rfs[32]中的每個(gè)元素為一個(gè)規(guī)則函數(shù)結(jié)構(gòu)體，每個(gè)規(guī)則函數(shù)結(jié)構(gòu)體包括了函數(shù)名稱（name）、參數(shù)0（a0）、參數(shù)1（a1）和占位符（pos），每個(gè)規(guī)則結(jié)構(gòu)體可存儲(chǔ)的規(guī)則函數(shù)最多為32 個(gè).

Fig.11 Data structure of the password and the rule圖11 口令與規(guī)則的數(shù)據(jù)結(jié)構(gòu)體

圖11 中口令和規(guī)則的結(jié)構(gòu)體的定義方式不能充分利用從核的LDM 空間. 首先口令結(jié)構(gòu)體為了保持4 B 對(duì)齊以提高傳輸效率，浪費(fèi)了3 B 的空間作為占位符，對(duì)此，本文將口令結(jié)構(gòu)體中的最大口令長(zhǎng)度N設(shè)置為31，并去除了占位符，從而在保持4 B 對(duì)齊的情況下將口令結(jié)構(gòu)體縮小為32 B，考慮到絕大部分正確口令長(zhǎng)度小于16 B，將最大口令長(zhǎng)度減少1 B 的影響可以忽略不計(jì).

另一方面，規(guī)則結(jié)構(gòu)體中固定包含32 個(gè)規(guī)則函數(shù)結(jié)構(gòu)體，然而實(shí)際使用的規(guī)則中包含的規(guī)則函數(shù)數(shù)量平均為3 個(gè)左右，因此按照?qǐng)D11 中的定義方式平均浪費(fèi)了90.6%的空間. 為了解決這一問(wèn)題，本文提出了變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制，如圖12 所示展示了2 條相鄰的規(guī)則“uT2”和“Cp2$AsAB”，其中規(guī)則“uT2”由規(guī)則函數(shù)“u”和“T2”組成，規(guī)則“Cp2$AsAB”由規(guī)則函數(shù)“C”“p2”“$A”“sAB”組成. 注意到每個(gè)規(guī)則函數(shù)使用4B 存儲(chǔ)，在原定義方式下第4 個(gè)字節(jié)為占位符，而在變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制中，第4 個(gè)字符為規(guī)則結(jié)束指示符. 當(dāng)指示符為0 時(shí)，表示當(dāng)前規(guī)則后面還有其他規(guī)則函數(shù)，當(dāng)指示符為1 時(shí)表示當(dāng)前規(guī)則結(jié)束. 通過(guò)變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制，圖12 中2 條規(guī)則需要的存儲(chǔ)空間由256 B 降至24 B.

Fig.12 Variable length rule storage policy圖12 變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制

3.5 從核間負(fù)載均衡機(jī)制

3.1～3.4 節(jié)的分析假定了規(guī)則處理算法的各個(gè)子任務(wù)具有相同的運(yùn)算復(fù)雜度，然而在實(shí)際中，不同子任務(wù)的運(yùn)算復(fù)雜度往往是不同的，差異來(lái)源主要有3 個(gè)方面：一是不同規(guī)則包含不同數(shù)量的規(guī)則函數(shù)，一般而言規(guī)則函數(shù)越多運(yùn)算復(fù)雜度越大；二是不同規(guī)則函數(shù)的運(yùn)算復(fù)雜度不同，例如函數(shù)append（“$X”）只需在口令最后添加一個(gè)字符X，而函數(shù)lowercase則需要遍歷口令中的所有字符，判斷其大小寫(xiě)狀態(tài)并對(duì)其修改；三是同一規(guī)則函數(shù)在處理不同口令時(shí)運(yùn)算復(fù)雜度不同，例如函數(shù)lowercase在處理8 B 長(zhǎng)度的口令時(shí)需要至少8 次運(yùn)算，而處理16 B 長(zhǎng)度的口令時(shí)需要至少16 次運(yùn)算.

在當(dāng)前規(guī)則處理方案中，子任務(wù)在從核間按照數(shù)量均勻分配，由于并行處理器每個(gè)核心的運(yùn)算能力相同，若各個(gè)核心分配到的子任務(wù)總運(yùn)算復(fù)雜度差異較大則會(huì)導(dǎo)致部分核心提前于其他核心完成任務(wù)，從而處于空閑狀態(tài)，浪費(fèi)了算力導(dǎo)致加速比下降.對(duì)此一種樸素的解決方案是提前計(jì)算出各個(gè)子任務(wù)的執(zhí)行時(shí)間，進(jìn)而依照子任務(wù)的執(zhí)行時(shí)間在核心間均勻分配，但是口令集和規(guī)則集的隨機(jī)性以及計(jì)算子任務(wù)時(shí)間的開(kāi)銷使得這種方案不可行.

為了解決這一問(wèn)題，本文設(shè)計(jì)一種從核間負(fù)載均衡機(jī)制，其原理如圖13 所示. 主核從字典文件中加載口令時(shí)計(jì)算出輸入口令的總數(shù)量，并將輸入口令集分為大小均為m的子集，然后在主存中設(shè)置一個(gè)信號(hào)量s記錄待處理的子集總數(shù)量. 處理開(kāi)始后，每個(gè)從核依次讀取主存中的信號(hào)量s，并將其減1 然后更新s. 這一過(guò)程采用原子操作進(jìn)行，避免多個(gè)從核同時(shí)更新s而發(fā)生錯(cuò)誤. 之后根據(jù)s的值計(jì)算需要處理的口令的起始地址并對(duì)其執(zhí)行規(guī)則處理.

Fig.13 Workload balance policy between slave cores圖13 從核負(fù)載均衡機(jī)制

圖13 所述的負(fù)載均衡機(jī)制可以使不同從核的處理時(shí)間的極差不超過(guò)m條口令的處理時(shí)間. 因此若要盡可能減小不同從核的處理時(shí)間差異，則需使m的取值盡可能小. 但是當(dāng)m很小時(shí)，從核會(huì)頻繁地對(duì)信號(hào)量s進(jìn)行原子更新操作，考慮到從核對(duì)主存的訪問(wèn)開(kāi)銷，整體的規(guī)則處理時(shí)間反而會(huì)增大. 實(shí)踐中應(yīng)綜合考慮上述因素的影響選取最佳的參數(shù)設(shè)置.

4 數(shù)據(jù)級(jí)并行優(yōu)化技術(shù)

數(shù)據(jù)級(jí)并行優(yōu)化技術(shù)主要針對(duì)單次規(guī)則函數(shù)的執(zhí)行過(guò)程，2.2 節(jié)以字符為單位分析了各類規(guī)則函數(shù)的數(shù)據(jù)級(jí)可并行度，對(duì)絕大部分規(guī)則函數(shù)，理想情況下每個(gè)字符的處理都可以完全并行，然而以字符為單位進(jìn)行處理意味著從核中每條指令最多處理1 個(gè)字符，而SW26010 中從核最多可以同時(shí)執(zhí)行2 條指令，因此以字符為單位的處理方式在從核上的執(zhí)行時(shí)可并行度最多為2.盡管在Hashcat 中對(duì)規(guī)則函數(shù)進(jìn)行了優(yōu)化，將4 個(gè)字符當(dāng)作一個(gè)32 b 的無(wú)符號(hào)整型數(shù)據(jù)進(jìn)行了處理，使得部分規(guī)則函數(shù)的性能得到了提升，但這種優(yōu)化仍然不能充分發(fā)揮SW26010 處理器從核的性能. 一方面每條指令最多只能處理4 個(gè)字符，不能充分利用從核中向量寄存器256 b 的位寬；另一方面部分規(guī)則函數(shù)的實(shí)現(xiàn)未能高效利用申威SIMD 指令集中的特殊指令，無(wú)法達(dá)到最佳優(yōu)化效果.

為了進(jìn)一步提升規(guī)則函數(shù)的執(zhí)行效率，本文提出了基于申威SIMD 指令集的規(guī)則函數(shù)優(yōu)化方案，該方案的核心是通過(guò)合理使用SIMD 指令，降低執(zhí)行規(guī)則函數(shù)需要的指令數(shù)量，進(jìn)而降低規(guī)則函數(shù)的執(zhí)行時(shí)間. 使用SIMD 指令實(shí)現(xiàn)規(guī)則函數(shù)的基本思路是將輸入口令存儲(chǔ)于SIMD 向量寄存器中，利用SIMD 指令對(duì)口令中的多個(gè)字符同時(shí)進(jìn)行相同的操作，最后將SIMD 向量寄存器中的輸出口令寫(xiě)回主存. 根據(jù)2.2 節(jié)中的分析，現(xiàn)有的41 種規(guī)則函數(shù)可以分為OAC，OSC，MAC，MSC 這4 種類型和函數(shù)purge. 除單獨(dú)的規(guī)則函數(shù)purge較為特殊外，其余4 類規(guī)則函數(shù)均有明顯的計(jì)算訪存特征，因此相應(yīng)的SIMD 實(shí)現(xiàn)也圍繞其計(jì)算訪存特征展開(kāi).

1） 對(duì)于OAC 類型規(guī)則函數(shù)，其特點(diǎn)為對(duì)所有輸入口令字符的操作完全相同且互不依賴. 互不依賴的特性決定了對(duì)每個(gè)字符的操作可以完全并行，對(duì)所有輸入口令字符的操作完全相同決定了這些操作可以用完全相同的指令完成，這一特點(diǎn)非常契合SIMD指令的設(shè)計(jì)思路，所以對(duì)OAC 類型函數(shù)直接使用SIMD 指令將其并行化即可得到很好的加速效果.

2） 對(duì)于OSC 類型規(guī)則函數(shù)，其特點(diǎn)在于只對(duì)特定位置的1 個(gè)字符采取操作，其余位置字符保持不變. 由于申威SIMD 指令集不支持單獨(dú)對(duì)SIMD 向量中的1B 進(jìn)行操作，所以O(shè)SC 類函數(shù)必須結(jié)合掩碼實(shí)現(xiàn)，即首先生成一個(gè)待處理字節(jié)位置全為“1”、其余位置全為“0”的掩碼，然后對(duì)原口令向量中所有字符進(jìn)行相同操作生成新口令向量，最后根據(jù)掩碼組合的原口令向量與新口令向量得到輸出口令向量. 組合方式為：掩碼為“1”的位置使用新口令向量的值，掩碼為“0”的位置使用原口令向量的值.

3） 對(duì)于MAC 類型規(guī)則函數(shù)，其特點(diǎn)為對(duì)所有字符采用特定的方式進(jìn)行位置變換. 在以字符為單位的處理方式中，對(duì)每個(gè)字符直接進(jìn)行位置變換都會(huì)產(chǎn)生1 次讀操作和1 次寫(xiě)操作，要生成長(zhǎng)度為L(zhǎng)的輸出口令則會(huì)產(chǎn)生2L次讀/寫(xiě)操作，帶來(lái)可觀的時(shí)間開(kāi)銷. 要提升此類函數(shù)的性能就必須盡量減小讀/寫(xiě)操作的數(shù)量，申威SIMD 指令集中提供了向量移位指令和向量混洗指令，利用這2 類指令可以在SIMD 向量中同時(shí)變換多個(gè)字符的位置，并且無(wú)需讀寫(xiě)存儲(chǔ)器.

4） 對(duì)于MSC 類型規(guī)則函數(shù)，其特點(diǎn)為對(duì)特定的1 個(gè)或2 個(gè)字符進(jìn)行位置變換. 由于申威SIMD 指令集不支持對(duì)SIMD 向量中的單個(gè)字節(jié)進(jìn)行移動(dòng)，所以要實(shí)現(xiàn)MSC 類型函數(shù)同樣需要結(jié)合掩碼，即首先生成目標(biāo)字節(jié)位置處的掩碼，然后對(duì)原口令向量中的所有字符進(jìn)行移動(dòng)生成新口令向量，最后通過(guò)掩碼組合原口令向量與新口令向量得到輸出口令向量.

5） 對(duì)于函數(shù)purge，由于對(duì)其各個(gè)字符的操作之間存在數(shù)據(jù)依賴，因此難以使用SIMD 指令實(shí)現(xiàn)，本文仍舊采用普通標(biāo)量指令集對(duì)其進(jìn)行實(shí)現(xiàn).

在上述SIMD 優(yōu)化思路的基礎(chǔ)上，本文提出了4種SIMD 優(yōu)化方案.

4.1 口令數(shù)據(jù)向量化

在2.2 節(jié)規(guī)則函數(shù)實(shí)現(xiàn)中，口令數(shù)據(jù)以結(jié)構(gòu)體方式存儲(chǔ)，每條口令占據(jù)32 B 存儲(chǔ)空間. 為了使用SIMD 指令進(jìn)行規(guī)則函數(shù)實(shí)現(xiàn)，必須首先將口令數(shù)據(jù)加載到SIMD 向量寄存器中，由于SW26010 的向量寄存器位寬為256，因此恰好能夠存放1 條口令. 將口令數(shù)據(jù)加載到向量寄存器時(shí)，位置靠前的字符被存儲(chǔ)于向量寄存器的低位，例如p[0]存儲(chǔ)于向量寄存器的第0～7 位，p[1]存儲(chǔ)于向量寄存器的第8～15 位，以此類推. 口令數(shù)據(jù)向量化的優(yōu)勢(shì)和劣勢(shì)并存. 其優(yōu)勢(shì)在于對(duì)口令中字符的所有操作均在寄存器中進(jìn)行，避免了存儲(chǔ)讀寫(xiě)；其劣勢(shì)在于將口令數(shù)據(jù)加載到向量寄存器以及將向量寄存器中的口令數(shù)據(jù)寫(xiě)回LDM 的過(guò)程會(huì)帶來(lái)額外的開(kāi)銷. 口令數(shù)據(jù)的加載開(kāi)銷可以通過(guò)多次復(fù)用輸入口令進(jìn)行均攤，而口令數(shù)據(jù)的寫(xiě)回開(kāi)銷則無(wú)法避免.

4.2 大小寫(xiě)轉(zhuǎn)換向量?jī)?yōu)化

大小寫(xiě)轉(zhuǎn)換是規(guī)則函數(shù)中出現(xiàn)頻率最高的一類ROP變換操作，在41 種常用的規(guī)則函數(shù)中，使用到大小寫(xiě)轉(zhuǎn)換的規(guī)則函數(shù)共有8 種，分別為lowercase，uppercase，capitalize，invert_capitalize，toggle，toggle@N，title，title_w/separator. 通常大小寫(xiě)轉(zhuǎn)換的實(shí)現(xiàn)采用條件分支語(yǔ)句，如圖14 所示，首先判斷字符c為大寫(xiě)字母還是小寫(xiě)字母，若為大寫(xiě)字母則將其ASCII 值加32，若為小寫(xiě)字母則將其ASCII 值減32.這種實(shí)現(xiàn)方式存在2 個(gè)弊端，首先條件運(yùn)算會(huì)導(dǎo)致同一口令中的不同字符可能具有不同的執(zhí)行分支，這將破壞SIMD 指令的應(yīng)用條件，使其無(wú)法使用SIMD 指令加速；其次申威SIMD 指令集中不包含8b 向量加/減法指令，若以32b 向量加/減法指令實(shí)現(xiàn)“c+32”和“c-32”語(yǔ)句則每條指令最多只能同時(shí)處理8 個(gè)字符，降低了執(zhí)行效率.

Fig.14 Toggle case function圖14 大小寫(xiě)轉(zhuǎn)換函數(shù)

本文對(duì)大小寫(xiě)轉(zhuǎn)換函數(shù)的優(yōu)化實(shí)現(xiàn)如圖14 中的函數(shù)opt_toggle_case所示. 其基本原理為互相對(duì)應(yīng)的大寫(xiě)字母與小寫(xiě)字母的ASCII 值相差固定為32.在二進(jìn)制角度，大寫(xiě)字母與小寫(xiě)字母的ASCII 值僅第5 位不同，大寫(xiě)字母的第5 位為“0”，小寫(xiě)字母的第5 位為“1”，因此將任何小寫(xiě)字母的ASCII 值與“0x20”異或即可得到其對(duì)應(yīng)的大寫(xiě)字母的ASCII 值，反之亦然. 但在此之前，必須先保證輸入字符c是大寫(xiě)字母或小寫(xiě)字母，函數(shù)opt_toggle_case中展示的方法可以篩選出ASCII 碼在[64, 128）區(qū)間內(nèi)且低5 位在[1, 26]區(qū)間內(nèi)的字符，滿足此條件的字符即為大寫(xiě)字母或小寫(xiě)字母. 將滿足條件的字符與“0x20”異或即可完成大小寫(xiě)轉(zhuǎn)換. 此方法不會(huì)產(chǎn)生條件分支語(yǔ)句，因此可以直接向量化，如函數(shù)opt_toggle_case_vector所示.

4.3 字符匹配向量化

在OAC 類型規(guī)則函數(shù)中，replace（“sXY”），title（“E”）和title_w/separator（“eX”）是較為特殊的3種函數(shù). 其他OAC 類型規(guī)則函數(shù)（例如lowercase）對(duì)所有字符執(zhí)行同樣的ROP操作，而這3 種函數(shù)則只對(duì)特定ASCII 值（假設(shè)為X）的字符執(zhí)行ROP操作，因此必須首先找到ASCII 值為X的字符的位置. 在傳統(tǒng)實(shí)現(xiàn)方案中，這一字符匹配的過(guò)程只能通過(guò)依次遍歷輸入口令中的每個(gè)字符實(shí)現(xiàn). 本文使用SIMD 指令對(duì)字符匹配進(jìn)行了向量?jī)?yōu)化，如圖15 所示為函數(shù)replace向量?jī)?yōu)化前后的代碼. 由于申威SIMD 指令集中不存在以8 b 字符為基本元素的比較指令，因此必須將一個(gè)32 b 整型數(shù)的4 B 分開(kāi)比較. 經(jīng)過(guò)simd_veqvw指令同或操作后，口令中所有ASCII 值等于X的字符均會(huì)變?yōu)椤?xff ”. 然后保留值為“0xff ”的字節(jié)并將其他字節(jié)置為0 形成掩碼，最后通過(guò)此掩碼進(jìn)行字符替換.

Fig.15 Vector optimization of the replace function圖15 函數(shù)replace 的向量?jī)?yōu)化

4.4 基于向量移位指令的優(yōu)化

在MAC 和MSC 類型規(guī)則函數(shù)中存在很多向輸入口令中增加或減少字符的函數(shù)，例如函數(shù)delete刪除口令中的第1 個(gè)字符，函數(shù)insert向口令的第N個(gè)字符位置插入字符M，這些函數(shù)均需要對(duì)輸入口令中的全部或部分字符進(jìn)行移動(dòng). 在傳統(tǒng)的以單個(gè)字符為基本操作單元的實(shí)現(xiàn)中，移動(dòng)一個(gè)字符需要4個(gè)步驟：計(jì)算源字符坐標(biāo)、計(jì)算目的字符坐標(biāo)、讀取源字符、寫(xiě)入目的字符. 對(duì)多個(gè)字符進(jìn)行這4 個(gè)步驟會(huì)產(chǎn)生大量的讀寫(xiě)指令. 值得注意的是這類函數(shù)中對(duì)字符的移動(dòng)存在規(guī)律性，即所有字符的移動(dòng)方向和步長(zhǎng)是相同的，因此可以通過(guò)整體移動(dòng)進(jìn)行優(yōu)化.

SW26010 處理器提供了一類向量移位指令，該類指令可以同時(shí)移動(dòng)256b 向量中的32 個(gè)字符，以函數(shù)truncate_left為例，圖16 展示了其SIMD 優(yōu)化前后的代碼. 原本需要L_new次的字符移動(dòng)操作利用simd_srlow指令只需要1 條指令即可完成，提高了函數(shù)執(zhí)行效率. 其他類似的規(guī)則函數(shù)也可以利用向量移位指令實(shí)現(xiàn)并行優(yōu)化，例如函數(shù)rotate_left，rotate_right，insert，prepend等，篇幅所限此處不再贅述.

Fig.16 Vector optimization of the truncate_left function圖16 函數(shù)truncate_left 的向量?jī)?yōu)化

4.5 基于向量混洗的優(yōu)化

在MAC 和MSC 類型函數(shù)中還存在若干改變輸入口令字符位置的函數(shù)，例如函數(shù)reverse，reflect，duplicate_all，這些函數(shù)不同于4.4 節(jié)中增加或減少字符的函數(shù)，其字符移動(dòng)的方向和步長(zhǎng)不統(tǒng)一，因此無(wú)法單純通過(guò)向量移位指令實(shí)現(xiàn). 對(duì)這些規(guī)則函數(shù)的向量?jī)?yōu)化利用了SW26010 處理器中的向量混洗指令simd_vshuffle，該指令能夠?qū)⑾蛄考拇嫫髦械? 個(gè)32 b整型數(shù)據(jù)以任意順序重新排列，以函數(shù)reverse為例，圖17 展示了使用向量混洗指令優(yōu)化前后的代碼.

Fig.17 Vector optimization of the reverse function圖17 函數(shù)reverse 的向量?jī)?yōu)化

5 實(shí)驗(yàn)評(píng)估

為了評(píng)估各項(xiàng)優(yōu)化技術(shù)的實(shí)際效果，本文基于神威·太湖之光超級(jí)計(jì)算機(jī)設(shè)計(jì)了實(shí)驗(yàn)，實(shí)驗(yàn)中使用了單個(gè)核組硬件資源，其參數(shù)如表2 所示.

Table 2 Hardware Resource Configuration of a Single Core Group in SW26010 Processor表2 SW26010 處理器單核組硬件資源配置

在表2 所示的硬件平臺(tái)上，本文測(cè)試了不同口令恢復(fù)系統(tǒng)架構(gòu)和規(guī)則函數(shù)實(shí)現(xiàn)版本下的系統(tǒng)性能指標(biāo)，各種系統(tǒng)架構(gòu)和規(guī)則函數(shù)實(shí)現(xiàn)的可選項(xiàng)如表3所示. 系統(tǒng)架構(gòu)方面，本文測(cè)試了主核處理（MASTER）和從核加速（SLAVE）這2 種規(guī)則處理方案；規(guī)則函數(shù)實(shí)現(xiàn)方面，本文測(cè)試了不同版本的規(guī)則函數(shù)實(shí)現(xiàn)代碼，其中CWISE 每條指令處理1 個(gè)字符，OPT32為Hashcat 中實(shí)現(xiàn)的版本，每條指令處理4 個(gè)字符. 為了表述方便，后文以“口令恢復(fù)系統(tǒng)架構(gòu)-規(guī)則函數(shù)實(shí)現(xiàn)版本”組合表示一種具體的配置，例如“SLAVESWV”表示采用從核進(jìn)行口令生成，規(guī)則函數(shù)實(shí)現(xiàn)針對(duì)申威SIMD 指令集進(jìn)行了優(yōu)化. 測(cè)試程序使用sw5cc進(jìn)行編譯，版本號(hào)為“5.421-sw-500”，編譯優(yōu)化級(jí)別為“O2”. 實(shí)驗(yàn)中的性能指標(biāo)通過(guò)讀取SW26010 處理器中的實(shí)時(shí)時(shí)鐘計(jì)數(shù)器并換算得到.

Table 3 Configurable Arguments of the Benchmark Program表3 測(cè)試程序可配置參數(shù)

實(shí)驗(yàn)選取了5 個(gè)具有代表性的Hashcat 規(guī)則集作為測(cè)試規(guī)則集，分別為best64，d3ad0ne，dive，rockyou-30000，unix-ninja-leetspeak.其中best64 是最常用的規(guī)則集，d3ad0ne 中包含了多個(gè)函數(shù)purge，dive 是最大的規(guī)則集，rockyou-30000 不包含函數(shù)purge，unix-ninjaleekspeak 只包含OAC 和OSC 類型規(guī)則函數(shù)，且規(guī)則長(zhǎng)度較大.

5.1 并行任務(wù)映射機(jī)制

表4 列出了4 種映射機(jī)制方案下單個(gè)從核的數(shù)據(jù)通信時(shí)間、數(shù)據(jù)通信量和DMA 次數(shù). 實(shí)驗(yàn)中P 緩沖、R 緩沖、Q 緩沖的大小分別為16 KB，16 KB，4 KB，口令集數(shù)量為64 萬(wàn)條，規(guī)則集數(shù)量為16 384 條，單條規(guī)則采用128 B 存儲(chǔ). 由表4 中數(shù)據(jù)可以看出，在當(dāng)前實(shí)驗(yàn)設(shè)置下，SPM-PIRO 方案具有最小的數(shù)據(jù)通信量和最小的數(shù)據(jù)通信時(shí)間，但與SRM-PORI 和SRM-PIRO 這2 種方案差距不大，而SPM-PORI 方案的數(shù)據(jù)通信量和通信時(shí)間最大，這是因?yàn)镾PM 映射下從核需要處理的口令數(shù)量最多，使得口令外循環(huán)的次數(shù)增多，進(jìn)一步導(dǎo)致規(guī)則內(nèi)循環(huán)的次數(shù)增加，通過(guò)口令和規(guī)則分塊的DMA 傳輸次數(shù)可以驗(yàn)證這一結(jié)論，因此在口令數(shù)量遠(yuǎn)多于規(guī)則數(shù)量的情況下，應(yīng)該避免采用SPM-PORI 方案.

Table 4 Comparison of Communication Overhead of a Single Slave Core under Different Task Mapping Policies表4 不同任務(wù)映射機(jī)制下單個(gè)從核的通信開(kāi)銷比較

5.2 從核緩沖區(qū)配比優(yōu)化機(jī)制

為了驗(yàn)證從核緩沖區(qū)配比優(yōu)化機(jī)制的效果，本文實(shí)驗(yàn)測(cè)試了最優(yōu)策略、等容量策略、等數(shù)量策略這3 種不同的緩沖區(qū)分配策略下的數(shù)據(jù)通信時(shí)間與通信量，其中最優(yōu)策略依據(jù)式（5）計(jì)算得出，等容量策略將P 緩沖和R 緩沖設(shè)置為相同容量，等數(shù)量策略令P 緩沖和R 緩沖中存儲(chǔ)的口令和規(guī)則數(shù)量相等.實(shí)驗(yàn)中使用的口令集大小為64 萬(wàn)條，規(guī)則集大小為16 384 條. 在測(cè)試最優(yōu)策略的性能時(shí)，實(shí)驗(yàn)還選取了與理論最優(yōu)緩沖區(qū)配置相近的其他配置以驗(yàn)證理論最優(yōu)是否為實(shí)測(cè)最優(yōu)，實(shí)驗(yàn)結(jié)果如圖18 所示.

Fig.18 Communication overhead under different buffer sizes圖18 不同緩沖區(qū)大小下的通信開(kāi)銷

圖18 中使用的緩沖區(qū)總?cè)萘縎為32 KB，單條規(guī)則數(shù)據(jù)v大小為128 B，此時(shí)式（5）計(jì)算得到的最優(yōu)P 緩沖口令條數(shù)x*約為944，最優(yōu)R 緩沖規(guī)則條數(shù)y*約為20，而在“944-20”配置下的實(shí)測(cè)通信時(shí)間同樣也取得了最小值，說(shuō)明理論結(jié)果與實(shí)測(cè)結(jié)果吻合，驗(yàn)證了3.3 節(jié)中數(shù)據(jù)通信時(shí)間模型的準(zhǔn)確性. 相比于等容量策略和等數(shù)量策略，最優(yōu)策略對(duì)應(yīng)的緩沖區(qū)配置將數(shù)據(jù)通信時(shí)間分別縮短了40.5%和76.1%，將通信量分別減少了44.7%和77.8%.

5.3 變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制

為了驗(yàn)證變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制的優(yōu)化效果，本文實(shí)驗(yàn)比較了應(yīng)用變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制前后的數(shù)據(jù)通信時(shí)間和通信量，如表5 所示. 由于統(tǒng)計(jì)上每條規(guī)則包含的規(guī)則函數(shù)數(shù)量約等于3，因此應(yīng)用變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制后，平均每條規(guī)則數(shù)據(jù)的大小為12 B，此時(shí)由于每條規(guī)則數(shù)據(jù)占用的局存空間變小，從核每次DMA可以加載更多的規(guī)則到局存中，從而大幅度減少了加載規(guī)則的DMA 次數(shù). 同時(shí)由于規(guī)則集的總大小減小，從核的數(shù)據(jù)通信時(shí)間和通信量分別減少了89.0%和89.3%.

Table 5 Communication Time and Data Traffic Under Different Rule Sizes表5 不同規(guī)則數(shù)據(jù)大小下的通信時(shí)間與通信量

5.4 負(fù)載均衡機(jī)制

為了測(cè)試負(fù)載均衡機(jī)制的優(yōu)化效果，本文實(shí)驗(yàn)構(gòu)造了一個(gè)包含1 280 萬(wàn)條口令的字典，字典中的口令按照長(zhǎng)度由短到長(zhǎng)排序，最短的口令長(zhǎng)度為1，最長(zhǎng)的口令長(zhǎng)度為28，然后比較了均勻數(shù)量方案與負(fù)載均衡方案下64 個(gè)從核的規(guī)則變換執(zhí)行時(shí)間與執(zhí)行時(shí)間的標(biāo)準(zhǔn)差，結(jié)果如圖19 所示. 實(shí)驗(yàn)中使用了Hashcat中使用頻率最高的規(guī)則集best64 作為測(cè)試規(guī)則集，規(guī)則函數(shù)的實(shí)現(xiàn)版本為CWISE，每個(gè)工作集包含的口令數(shù)量為256.從圖19 中可以發(fā)現(xiàn)，在均勻數(shù)量方案下各個(gè)從核執(zhí)行規(guī)則變換最短時(shí)間為3.10 s，最長(zhǎng)為4.80 s，二者相差1.70 s，這意味著在這1.70 s 內(nèi)，很多從核處于空閑狀態(tài)，沒(méi)有得到充分利用. 而在負(fù)載均衡方案下，每個(gè)從核的規(guī)則變換執(zhí)行時(shí)間均為4.15 s，所有從核自始至終均處于忙碌狀態(tài)，因此負(fù)載均衡方案下從核陣列的規(guī)則變換執(zhí)行總時(shí)間比均勻數(shù)量方案少了13.5%.

Fig.19 Rule mangling execution time of the slave cores under different policies圖19 不同方案下從核的規(guī)則變換執(zhí)行時(shí)間

為了驗(yàn)證工作集大小對(duì)負(fù)載均衡機(jī)制優(yōu)化效果的影響，本文實(shí)驗(yàn)還測(cè)試了不同工作集大小下的從核陣列規(guī)則變換執(zhí)行時(shí)間，結(jié)果如表6 所示. 觀察表6 可以發(fā)現(xiàn)，負(fù)載均衡方案下各個(gè)從核執(zhí)行時(shí)間的均值大于均勻數(shù)量方案，這是因?yàn)樨?fù)載均衡方案需要訪問(wèn)主存中的信號(hào)量，因此產(chǎn)生了額外的開(kāi)銷.工作集太小時(shí)（例如64），從核陣列需要重新獲取工作集的次數(shù)最多，并且不能充分利用局存中的P 緩沖，因此開(kāi)銷也越大. 隨著工作集的大小增加，從核陣列重新獲取工作集的次數(shù)減少，但這也導(dǎo)致不同從核間的規(guī)則變換執(zhí)行時(shí)間極差變大. 綜合考慮以上因素，將工作集大小設(shè)置為與P 緩沖同等大小較為合適.

Table 6 Rule Mangling Execution Time of the Slave Cores Under Different Workset Sizes表6 不同工作集大小下從核的規(guī)則變換執(zhí)行時(shí)間

5.5 SIMD 優(yōu)化效果對(duì)比

本文實(shí)驗(yàn)測(cè)試了CWISE，OPT32，SWV 這3 種規(guī)則函數(shù)實(shí)現(xiàn)版本中執(zhí)行單次規(guī)則函數(shù)需要的平均時(shí)鐘周期數(shù). 為了充分展現(xiàn)并行優(yōu)化的效果，實(shí)驗(yàn)中大部分規(guī)則函數(shù)使用長(zhǎng)度為24 的口令進(jìn)行測(cè)試，部分會(huì)使輸出口令長(zhǎng)度加倍的規(guī)則函數(shù)則使用長(zhǎng)度為15的口令進(jìn)行測(cè)試以避免輸出口令超出最大口令長(zhǎng)度.

圖20 比較了OAC 類型規(guī)則函數(shù)的優(yōu)化效果，8種規(guī)則函數(shù)中除了函數(shù)replace外其余函數(shù)均包含了大小寫(xiě)轉(zhuǎn)換操作. 由圖20 可以看出，OPT32 版本的時(shí)鐘周期數(shù)約為CWISE 版本的1/3，SWV 版本的時(shí)鐘周期數(shù)約為CWISE 版本的1/6、OPT32 版本的1/2，這說(shuō)明提升單條指令同時(shí)處理的字符數(shù)能夠有效減少OAC 類型規(guī)則函數(shù)消耗的時(shí)鐘周期. 從圖20 中還可以發(fā)現(xiàn)，CWISE 版本的函數(shù)toggle_case消耗的時(shí)鐘周期數(shù)約為函數(shù)lowercase的2 倍，這是因?yàn)镃WISE版本函數(shù)中既要判斷一個(gè)字符是否為小寫(xiě)字母，也要判斷其是否為大寫(xiě)字母，這導(dǎo)致執(zhí)行時(shí)間加倍，OPT32 版本和SWV 版本因?yàn)椴捎昧藘?yōu)化后的大小寫(xiě)判斷機(jī)制沒(méi)有發(fā)生此現(xiàn)象.OAC 類型規(guī)則函數(shù)中還包括3 種使用了字符匹配的規(guī)則函數(shù)title，title_w/separator，replace. 比較函數(shù)replace的性能可以發(fā)現(xiàn)，由于CWISE 版本和OPT32 版本均采用了逐個(gè)字符匹配替換方案，因此二者性能相同. 而SWV 版本使用了SIMD 并行字符匹配方案，不僅提升了字符匹配的速度，而且便利了匹配完成后的字符并行替換操作，因此提升了性能.

Fig.20 Optimization results of the OAC-type rule functions圖20 OAC 類型規(guī)則函數(shù)的優(yōu)化效果

圖21 比較了OSC 類型規(guī)則函數(shù)的優(yōu)化效果，由于此類規(guī)則函數(shù)實(shí)質(zhì)上只對(duì)單個(gè)字符進(jìn)行了操作，所以CWISE 版本和OPT32 版本執(zhí)行時(shí)間非常短，而在申威SIMD 指令集中由于沒(méi)有對(duì)向量中單個(gè)字節(jié)進(jìn)行操作的指令，要實(shí)現(xiàn)對(duì)單個(gè)字節(jié)的修改，必須首先生成掩碼，然后對(duì)所有字符執(zhí)行同樣修改，最后通過(guò)掩碼將單個(gè)字符修改合并回原向量，這一過(guò)程使得SIMD 優(yōu)化后的規(guī)則函數(shù)性能反而下降.

Fig.21 Optimization results of the OSC-type rule funtions圖21 OSC 類型規(guī)則函數(shù)的優(yōu)化效果

注意到SWV 版本的相鄰2 次規(guī)則函數(shù)調(diào)用之間使用SIMD 向量傳遞口令，而CWISE 和OPT32 版本則使用局存?zhèn)鬟f口令，因此無(wú)法將SWV 版本函數(shù)與CWISE 或OPT32 版本函數(shù)混合使用，這會(huì)帶來(lái)更大的口令數(shù)據(jù)轉(zhuǎn)換開(kāi)銷，所以實(shí)際應(yīng)用中若OSC 類型規(guī)則函數(shù)占比過(guò)多，反而會(huì)導(dǎo)致整體性能下降.

圖22 比較了MSC 類型規(guī)則函數(shù)以及函數(shù)purge和函數(shù)nothing的優(yōu)化效果，其中函數(shù)nothing實(shí)質(zhì)上不做任何操作，因此函數(shù)nothing的執(zhí)行周期數(shù)可以作為衡量函數(shù)調(diào)用開(kāi)銷的指標(biāo)，即單次規(guī)則函數(shù)開(kāi)銷約為60 個(gè)時(shí)鐘周期.MSC 類型規(guī)則函數(shù)包含了1或2 次字符移動(dòng)，這種情況下SIMD 指令難以發(fā)揮其并行能力，并且需要多條指令組合才能實(shí)現(xiàn)移動(dòng)，因此導(dǎo)致性能下降. 函數(shù)purge由于其特殊性，難以使用SIMD 指令實(shí)現(xiàn)相同功能，所以SWV 版本中先將向量寄存器中的口令存儲(chǔ)于局存空間，然后使用普通標(biāo)量指令對(duì)其進(jìn)行操作，最后再將結(jié)果存回向量寄存器，這導(dǎo)致SWV 版本的函數(shù)purge實(shí)現(xiàn)包含了一次SIMD 向量存儲(chǔ)開(kāi)銷和一次SIMD 向量加載開(kāi)銷，其性能變?yōu)镃WISE 版本和OPT32 版本的3 倍. 由于函數(shù)purge在實(shí)際應(yīng)用中占比約為0.2%，所以SWV版本的性能下降不會(huì)對(duì)整體性能產(chǎn)生明顯影響.

Fig.22 Optimization results of the MSC-type rule functions and purge, nothing rule funtions圖22 MSC 類型規(guī)則函數(shù)以及規(guī)則函數(shù)purge，nothing 的優(yōu)化效果

圖23 比較了MAC 類型規(guī)則函數(shù)的優(yōu)化效果，此類函數(shù)大多包含了字符移動(dòng)操作，以truncate_left函數(shù)為例，要對(duì)長(zhǎng)度為24 的口令應(yīng)用truncate_left操作，需要將23 個(gè)字符各向左移動(dòng)1 B，CWISE 版本和OPT32 版本中均不能一次完成，而SWV 版本則可以通過(guò)向量整體移位用1 條指令完成. 其他函數(shù)中也或多或少用到了向量整體移位指令，由于缺少相關(guān)指令，申威SIMD 指令集不擅長(zhǎng)在口令末尾添加、修改字符的操作，因此在少量函數(shù)上SWV 版本的性能出現(xiàn)了下降，例如append_character，duplicate_last_N，truncate等，這一點(diǎn)類似于OSC 類型規(guī)則函數(shù). 在函數(shù)reverse，reflect，duplicate_all中，SWV 版本使用了向量混洗指令，取得了1 倍以上的性能提升.

Fig.23 Optimization results of the MAC-type rule functions圖23 MAC 類型規(guī)則函數(shù)的優(yōu)化效果

5.6 整體優(yōu)化效果

圖24～26 展示了本文提出的優(yōu)化方案的整體優(yōu)化效果，實(shí)驗(yàn)測(cè)試了不同口令恢復(fù)系統(tǒng)實(shí)現(xiàn)方案下NTLM，MD5，SHA1 這3 種加密算法的口令恢復(fù)速度. 在系統(tǒng)架構(gòu)方面，本文實(shí)驗(yàn)測(cè)試了純主核口令生成方案（MASTER）和從核口令生成方案（SLAVE），其中MASTER 方案為主核負(fù)責(zé)口令生成、從核負(fù)責(zé)口令驗(yàn)證，SLAVE 方案為本文提出的方案，口令生成與口令驗(yàn)證均由從核負(fù)責(zé). 在規(guī)則函數(shù)實(shí)現(xiàn)方面，本文實(shí)驗(yàn)測(cè)試了CWISE，OPT32，SWV 這3 種版本，其中CWISE 版本和OPT32 版本代碼均來(lái)自于Hashcat，SWV 版本為本文提出的SIMD 優(yōu)化版本. 組合上述方案一共可以得到6 種具體實(shí)現(xiàn)方案，但由于SW26010 主核不支持部分SIMD 指令，因此無(wú)法測(cè)試MASTER-SWV 方案的性能. 因?yàn)椴煌?guī)則集包含的規(guī)則數(shù)量、規(guī)則函數(shù)的分布均有所差異，相應(yīng)的口令恢復(fù)速度亦有所不同，本文實(shí)驗(yàn)選取了具有代表性的5 個(gè)常用規(guī)則集進(jìn)行測(cè)試，它們分別為best64，rockyou-30000，unix-ninja-leetspeak，dive，d3ad0ne.

Fig.24 Password recovery speed of NTLM algorithm under different implementations圖24 不同實(shí)現(xiàn)方案下NTLM 算法的口令恢復(fù)速度

Fig.25 Password recovery speed of MD5 algorithm under different implementations圖25 不同實(shí)現(xiàn)方案下MD5 算法的口令恢復(fù)速度

Fig.26 Password recovery speed of SHA1 algorithm under different implementations圖26 不同實(shí)現(xiàn)方案下SHA1 算法的口令恢復(fù)速度

以NTLM 算法為例分析，對(duì)比MASTER-CWISE和SLAVE-CWISE 這2 種方案，可以發(fā)現(xiàn)前者的速度僅為后者的2.9% ～ 4.4%，顯然這是因?yàn)橹骱说囊?guī)則處理速度遠(yuǎn)小于從核的口令驗(yàn)證速度，因此成為了性能瓶頸，而將規(guī)則處理映射到從核后速度大幅度提升，進(jìn)而使整體性能得到了提升. 對(duì)于NTLM，MD5，SHA1 這3 種算法而言，將規(guī)則處理映射到從核陣列帶來(lái)的性能提升分別為34.1，41.7，36.5 倍.

對(duì)比SLAVE-CWISE，SLAVE-OPT32，SLAVE-SWV這3 種方案，可以發(fā)現(xiàn)三者在不同規(guī)則集上的速度表現(xiàn)有所差異. 在best64 規(guī)則集上，OPT32 版本的性能低于CWISE 版本和SWV 版本，這是因?yàn)閎est64 規(guī)則集包含大量的規(guī)則函數(shù)rotate_left，rotate_right，對(duì)此類規(guī)則函數(shù)，OPT32 版本的性能表現(xiàn)不佳. 在unixninja-leetspeak 規(guī)則集中，所有的規(guī)則函數(shù)均為函數(shù)replace，因此CWISE 版本，OPT32 版本的速度相同，而SWV 版本的速度提升了44.5%，這一結(jié)果與圖20中單次函數(shù)replace的執(zhí)行周期數(shù)相符. 總體來(lái)看，在best64， rockyou-30000， unix-ninja-leetspeek， dive 規(guī)則集上，SWV 版本的規(guī)則函數(shù)實(shí)現(xiàn)相較于CWISE 版本使系統(tǒng)速度提升了12.4% ～ 266.2%，相較于OPT32版本使系統(tǒng)速度提升了7.4% ～ 113.3%. 在d3ad0ne 規(guī)則集上，SWV 版本的性能劣于CWISE 版本和OPT32版本，原因在于該規(guī)則集包含了大量SWV 版本不占優(yōu)勢(shì)的規(guī)則函數(shù)swap@N，overwrite@N，purge等.

5.7 與其他工作對(duì)比

本文實(shí)驗(yàn)測(cè)試了應(yīng)用本文優(yōu)化方案后NTLM，MD5，SHA1 這3 種算法在完整的SW26010 處理器上的性能，并與業(yè)界主流的Hashcat 系統(tǒng)進(jìn)行了對(duì)比.Hashcat 系統(tǒng)運(yùn)行于臺(tái)式工作站，CPU 型號(hào)為Intel Core i7-10 700，GPU 型號(hào)為AMD Radeon Pro WX3200.由于Hashcat 能夠在純CPU 模式和GPU 加速模式下運(yùn)行，本文實(shí)驗(yàn)分別將這2 種模式命名為Hashcat-CPU 方案和Hashcat-GPU 方案. 測(cè)試結(jié)果如圖27～29 所示.

Fig.27 Password recovery speed comparison of NTLM algorithm圖27 NTLM 算法的口令恢復(fù)速度對(duì)比

Fig.28 Password recovery speed comparison of MD5 algorithm圖28 MD5 算法的口令恢復(fù)速度對(duì)比

Fig.29 Password recovery speed comparison of SHA1 algorithm圖29 SHA1 算法的口令恢復(fù)速度對(duì)比

測(cè)試結(jié)果表明，經(jīng)過(guò)本文方案優(yōu)化后的SW26010單節(jié)點(diǎn)口令恢復(fù)系統(tǒng)性能大幅度超越運(yùn)行于Intel 和AMD 處理器上的Hashcat 系統(tǒng)，在NTLM，MD5，SHA1這3 種算法上分別提升了1.94，2.74，3.04 倍以上，充分體現(xiàn)了國(guó)產(chǎn)申威眾核處理器在口令恢復(fù)領(lǐng)域相較于國(guó)外處理器的性能優(yōu)勢(shì).

6 結(jié) 論

本文的研究目標(biāo)是申威眾核處理器平臺(tái)上口令恢復(fù)系統(tǒng)的性能優(yōu)化問(wèn)題. 針對(duì)規(guī)則模式下口令生成速度性能瓶頸，本文首先從線程級(jí)和數(shù)據(jù)級(jí)2 個(gè)維度分析了規(guī)則處理算法的可并行度，然后結(jié)合SW26010 處理器的硬件架構(gòu)，提出了切實(shí)可行的優(yōu)化方法，其中主從核任務(wù)映射和從核任務(wù)分配機(jī)制解決了規(guī)則處理算法的并行分解問(wèn)題，使其能夠通過(guò)從核陣列進(jìn)行加速；從核緩沖區(qū)配比優(yōu)化機(jī)制解決了如何將LDM 空間高效分配給口令數(shù)據(jù)和規(guī)則數(shù)據(jù)的問(wèn)題，降低了從核陣列的數(shù)據(jù)通信時(shí)間和通信量；變長(zhǎng)規(guī)則存儲(chǔ)機(jī)制消除了規(guī)則數(shù)據(jù)的存儲(chǔ)冗余，減少了數(shù)據(jù)通信量；負(fù)載均衡機(jī)制提高了從核的利用率，降低了整體執(zhí)行時(shí)間；最后，基于申威SIMD指令集實(shí)現(xiàn)的規(guī)則函數(shù)向量?jī)?yōu)化減少了規(guī)則函數(shù)執(zhí)行消耗的時(shí)鐘周期，進(jìn)一步提升了規(guī)則處理的速度.

本文基于神威·太湖之光超算節(jié)點(diǎn)進(jìn)行了實(shí)驗(yàn)評(píng)估，測(cè)試了應(yīng)用本文優(yōu)化方案前后的NTLM，MD5，SHA1 這3 種算法的規(guī)則模式口令恢復(fù)速度. 實(shí)驗(yàn)結(jié)果表明，本文提出的優(yōu)化方案將原有系統(tǒng)的規(guī)則模式口令恢復(fù)速度提升了30 ～ 101 倍，從而解決了原有系統(tǒng)中基于規(guī)則的口令生成速度瓶頸問(wèn)題，增強(qiáng)了申威處理器平臺(tái)上口令恢復(fù)應(yīng)用的實(shí)用性.

同時(shí)，本文實(shí)驗(yàn)也表明，申威處理器在執(zhí)行規(guī)則處理任務(wù)時(shí)仍存在一些不足，首先SW26010 處理器的SIMD 指令集不支持以8b（1B）為基本操作單元的指令，導(dǎo)致指定字符變換（OSC）和指定字符移動(dòng)（MSC）類型規(guī)則函數(shù)的SIMD 實(shí)現(xiàn)效果不佳，性能甚至低于原有實(shí)現(xiàn)；其次，口令數(shù)據(jù)與SIMD 向量的互相轉(zhuǎn)化開(kāi)銷較大，這也導(dǎo)致了函數(shù)purge的SIMD 向量化實(shí)現(xiàn)速度較慢；最后，SW26010 處理器本質(zhì)上仍是馮·諾依曼架構(gòu)的通用處理器，由于通用處理器依賴指令操作數(shù)據(jù)且數(shù)據(jù)必須經(jīng)由存儲(chǔ)器在不同指令間傳遞，在口令恢復(fù)這種數(shù)據(jù)密集型應(yīng)用中會(huì)產(chǎn)生大量的存儲(chǔ)器讀寫(xiě)開(kāi)銷，增加了能耗. 目前看來(lái)，突破馮·諾依曼架構(gòu)探索更加專用的領(lǐng)域架構(gòu)，是未來(lái)提升口令恢復(fù)系統(tǒng)的性能和能效的解決方案.

作者貢獻(xiàn)聲明：張振東提出了研究思路和實(shí)驗(yàn)方案，并完成主要實(shí)驗(yàn)和論文撰寫(xiě)；王彤負(fù)責(zé)了部分實(shí)驗(yàn)；劉鵬提出研究思路并修改論文.