FPGA做正则匹配和网络安全，究竟有多大的优势？
网络安全已经被提升为国家战略的高度，高校里面的新增的一级学科，去年9月份，*网信办、教育部公布了“一流网络安全学院建设示范项目高校”名单。但网络安全的范围实在太大，平常所说的黑客、网络病毒等软件、操作系统、固件级别的网络攻击或防范办法仅仅是常见的传统网络安全范畴，本文所说的是基于硬件级别的网络安全方法，比较学术的分类有可信芯片研究、网络安全防护的硬件实现等。硬件领域网络安全的研究随着近几年挖矿芯片、AI芯片等专用芯片的广泛普及和宣传，越来越多的人逐渐意识到了FPGA或者专用芯片去实现某些传统的软件算法，会带来几个数量级的加速效果。目前，基于FPGA或者ASIC的硬件网络防护网卡已经在云平台、网络数据中心等广泛应用。随着网络带宽的不断提升，未来某一天，可能每一台PC机上的网卡都会带有硬件网络防护芯片。
基于FPGA的入侵检测
随着信息技术的不断发展，网络安全问题引起了人们的广泛关注。网络攻击者对不受保护的网络或系统进行入侵和攻击，从而传播计算机病毒、获得内部信息、摧毁主机、破坏重要数据等，给用户带来不可挽回的损失。
2014年4月，国内两个大型物流公司的内部网络系统遭到黑客攻击，1400多万条快递信息遭到泄露；
2015年5月，美国国税局系统遭到黑客攻击，十万多名纳税人的网上资料泄露，损失5000万美元；
2016年4月，济南市免疫规划系统网络被非法入侵，20多万名儿童信息泄露，包括儿童的姓名、联系方式、家庭住址等；
2017年5月12日，全球范围爆发了WannaCry勒索病毒攻击，该计算机网络病毒攻击了一百多个国家，涉及金融、能源、医疗等众多行业，损失高达80亿美元（约合人民币550亿元）。国内多所高校也受到了病毒攻击，大量重要的文档和数据被锁定加密，无法正常工作，影响巨大。
随着人们对网络的依赖性不断增大，网络攻击带来的损失也会越大，所以面对网络安全问题，应该要做到防患于未然，积极主动应对网络攻击。一个安全的计算机系统应保护它的数据和资源免于非授权访问、篡改和拒绝使用。1980年，JamesAnderson在《计算机安全威胁的控制》的技术报告中首次提出了入侵检测的概念[1]。入侵检测简单来说就是检测并响应针对计算机系统或网络的入侵行为，它包括检测对计算机系统的非法访问、越权访问和恶意试探，监测系统的运行状态等。
入侵检测系统（intrusion detection system，简称“IDS”）是能够执行入侵检测任务的软件、硬件或者是软硬件相结合的系统，可以对网络传输进行监视，并在发现可疑数据时发出警报或者采取主动应对措施。IDS利用已知的入侵行为构建模式集合，通过检测网络数据包，发现是否存在不符合安全策略的行为或被攻击的迹象。与传统防火墙不同，IDS不仅检测网络数据包的包头，还会对数据包的净荷部分进行检测。
入侵检测系统是一个复杂的系统，其中最核心的部分是入侵检测引擎，即检测数据包中是否包含攻击。早期的入侵检测引擎主要采用软件方式实现，但随着网络速度的不断增长和网络攻击数目的急剧增多，软件实现逐渐暴露出两个问题。首先，软件系统处理速度有限，最快只能达到几百兆的处理速度，已远远不能满足如今高速的网络需求；其次，检测过程占用大量的CPU运行时间，以经典入侵检测系统Snort为例，检测过程会占用30%~80%的CPU时间[2]，严重影响系统的性能。基于以上两点，设计适合于硬件实现的入侵检测算法和结构对实现高性能入侵检测系统至关重要[3]。
除了入侵检测之外，也可以以硬件的形式发起某一种攻击，如DDoS攻击，会给对方致命的打击。本公众号之前的文章，如西电免流量限制上网攻略！Python实现PPPOE攻击工具，秒杀拨号上网，笔者所在实验室已实现基于FPGA的PPPoE的DDoS攻击，效果显著。
目前，国内外已有多家公司推出了入侵检测的产品，下面介绍一些主流的入侵检测产品。世界上最大的网络设备制造商Cisco公司的CiscoSecure IDS是一个软硬件结合的系统，作为路由器和交换机产品设计的附加模块，用于实现入侵检测功能；NFR公司的NID系统，该系统是一种基础规则检测的网络入侵检测系统，同时也具备异常检测的功能[4]；华为的NIP系列入侵检测系统，定位各种网络威胁和违反安全策略的流量，并提供详细有效的指导措施，以实现防护检测技术；绿盟网络入侵检测系统是对防火墙的有力补充，与同类产品相比，具有高性能、高安全性、高可靠性和易操作性等优势[5]。
网络数据包分为包头和净荷两部分，包头长度比较短，并且每个域的信息固定，所以现在对包头部分的硬件检测方案的研究相对比较成熟。但在很多情况下，仅对数据包包头进行检测是不够的，如很多病毒等攻击会隐藏在数据包的净荷部分，所以对数据包净荷部分进行检测也非常必要。数据包净荷部分比较长，并且对应的规则长短不一，针对这一部分的检测成为限制入侵检测引擎性能的瓶颈之一[6]。
近年来，对网络数据包净荷的检测主要有两类解决方案，基于逻辑的解决方案（Logic-based）和基于存储器的解决方案（Memory-based）。基于逻辑的解决方案将规则集合中的规则直接用硬件逻辑实现。当规则集合规模变大时，这种方法硬件实现成本过高。针对这一问题，John Lockwood引入了状态机的方法[7]，通过规则之间共用前缀减少对硬件资源的消耗，该方法将规则集合中的全部规则转换成有限状态机，用硬件描述语言实现，最后映射到FPGA。HyunJin Kim 等人将状态机中的转移状态进行压缩，使其用FPGA实现时，能够充分利用查找表的输入输出端口，大大增大了硬件利用率[8]。基于逻辑的解决方案由于充分利用了硬件并行性，查找速度极快，吞吐率可达到8~10Gbps，但硬件资源消耗非常大，尤其随着规则集合规模越来越大，这一问题更加突出；另外，该类方法每次更新规则集合都需要重新进行FPGA映射，影响匹配效率。
基于存储器的解决方案首先对规则集合中的规则进行预处理，并将结果存储在存储单元中，与基于逻辑的解决方案最大的不同是，规则集合的信息存储在存储单元中，对逻辑资源消耗较少，并且每次进行规则更新时只需要重写存储单元的内容[9]。如今，用于净荷检测的规则集合非常庞大，并且需要经常更新，所以基于存储器的解决方法越来越有优势[10]。这类方法最早借鉴了经典的多模式匹配算法AC算法[11]，首先将规则集合中的规则信息转换成状态跳转表，存储在存储器中；检测数据时，通过输入数据的特征，读取存储器相应位置的信息，通过状态跳转完成规则匹配。当规则集合规模越来越大时，利用AC算法生成的状态跳转表会变得非常庞大，对存储空间的需求随之增大，在很多情况下片上的存储资源无法满足，但如果借助于片外存储单元，读取存储单元时延时较长，严重影响检测速度。因此不少研究人员针对这一问题提出了改进方法。IBM研究实验室的Jan vanLunteren提出了对AC算法转移规则的改进方法[12]，通过加入通配符和优先级，减少了AC算法中的转移规则，进而减小了状态转移表的大小；SarangDharmapurikar等人将AC算法与BF算法相结合[13]，BF算法所需存储资源极小，利用片上存储单元实现，AC算法所需存储资源较大，利用片外存储单元实现，该方法先利用BF算法对待检测数据进行快速过滤，可过滤掉大多数安全数据，只有当BF算法检测出疑似攻击的数据时，才启动AC算法对数据包进行检测，在占用极小片上资源的情况下，完成了对数据的快速检测；Tsern-Huei Lee将AC算法和WM算法相结合，先利用WM算法对数据进行预过滤，再利用AC算法进行检测[14]；Hong-Jip Jung 提出将AC算法与bit-split算法结合[15]，将AC算法中大状态机拆分成4个小状态机，该算法在保留AC算法性能的基础上，大大减小了存储空间。
随着规则集合的日益庞大，基于AC算法的方法很难实现较好的性能，因此Yi-Hua E. Yang等人开始利用树结构存储规则集合中的规则信息[16]，利用规则前缀建树，形成分级结构，加入流水线技术之后，每一时钟周期可处理一个字符，与之前算法相比，需要的存储空间更少，速度更快；采用树结构存储规则信息时，树的深度等于规则集合中最长的模式串长度，当最长的模式串长度较长时，会导致树的深度极大，影响匹配性能，Weirong Jiang在此基础上进行了进一步改进，将树结构和AC算法相结合[17]，将树的深度减少至8级，且AC算法中比例较大的交叉规则大大减少，存储空间相应减小。
基于存储器的解决方案对规则集合的更新比较方便，并且硬件逻辑资源消耗较小，但由于该类方法需要对规则集合中的规则进行预处理，利用规则的前缀关系生成状态跳转表或树型结构存储在存储单元中，因此其检测性能严重依赖于规则集合中的规则特征，规则之间的前缀关联性和预处理后的结果密切相关，因此即使是同样规模的规则集合，检测性能也会有很大的差异。另外，这类方法主要通过访问存储单元获取下一跳转状态，没有充分利用硬件的并行性，单个检测引擎的处理速度仅为1~3Gbps，在高速的网络应用中，需要采用多个检测引擎来满足需求，因此处理速度有待提高。
随着网络安全的重要性日益增强，基于FPGA或者专用芯片的入侵检测技需求必定会暴增。同时，随着挖矿芯片，AI芯片等的普及和推广，越来越多的人也逐渐认识到做某些事情，硬件的实现方式效率会数量级的提升。因此，基于FPGA或者芯片的网络安全防护也会越来越受到关注。
前面讲的太学术了，下面让我们以通俗的语言举一个例子来解释一下。
知名厂商举例
总部位于北爱尔兰贝尔法斯特的泰坦IC是北爱尔兰贝尔法斯特皇后大学安全信息技术中心（CSIT）的分拆公司。TITAN IC在硬件和内容处理和网络处理方面的发展处于世界领先地位。所提供的解决方案包括正则表达式（ReGEX）加速，用于网络安全的所有方面，包括：入侵检测/预防、应用检测、反病毒、内容/ URL过滤。这些解决方案可用作包含在网络服务器上的PCIE卡，如AWS F1上基于云的服务，作为可编程的知识产权，用于现场可编程门阵列（FPGA）和用于定制专用集成电路（ASIC）的硅知识产权（SIP）。
其中，最核心的技术就是正则表达式识别加速。这个跟Perl语言里面的正则表达式匹配是一样的。区别在于，通过硬件的方式在网络上快速的匹配出用户关心的数据内容。如下图是该公司通过硬件正则表达式处理器解析一封E-Mail的流程示意图。通过把规则配置到设备内部，就能实现对网络数据的快速识别和解析。
或许有人不以为然，这有什么啊，随便一台电脑上用个WireShark之类的抓包工具抓下来就可以分析出来。但我告诉你它的处理性能的时候你就明白区别了。
该公司的HeliOS ReGeX处理器架构在FPGA平台上可以实现达到100 Gbps的全网络吞吐量率数据的线速正则表达式匹配处理，并可以并行扫描多达100万个复杂正则表达式。
这是软件的方式能实现的吗？如果可以，那得需要多少台通用处理器并行工作啊。
下图是他们正则匹配的举例。
可以看到，除了应用识别外，还支持Snort等常见的入侵检测和防病毒签名以及数据丢失防护功能。
笔者想起2012年左右做HINOC2.0芯片的时候，里面也嵌入了规则匹配的模块，不过当时网口速率要求是1Gbps，要求做到字段无关、协议无关可自定义可更新，跟上面介绍的正则匹配实质是一样的。下图是当时实现的结构，规则表的查找还采用较为原始的顺序查找比对的方法，等做到HINOC3.0的时候，网口速率要求到了10Gbps，顺序查找比对的方式就无法满足线速处理的要求了。
HINOC3.0和单端口100Gbps SDN接入项目实现的时候，网口速率要求到了10Gbps和100Gbps，这时需要采用效率更高效的并行BV（Bit Vector，可参考参考文献[18]IEEE TPDS杂志文章）查找方法（类似于TCAM的工作方式）。如下图。
我们修改了参考文献[18]的实现方式，提出了也可以用来做范围匹配的BV算法（RSBV：Range Supported Bit Vector）和支持多字段匹配BV算法（AFBV：Bit Vector for All Type of Fields），在速率为100Gbps的以太网网络中，一个最短帧（最短帧帧长为64 字节、加上7字节前导码、1 字节起始符和12字节帧间隔）的最短处理时间为
使用我们自己提出的改进BV算法FPGA验证时，FPGA时钟频率为150MHz，一个数据帧的处理时间为一个时钟周期，为