Kangaroo：并行小规模FSM加速高效字符串匹配

"袋鼠（Kangaroo）是一项针对高性能字符串匹配的创新技术，旨在提高网络安全应用中的效率，如网络入侵检测系统和反病毒扫描器。在这些场景中，实时检查每个数据包的负载与数千个模式匹配是关键任务。随着互联网传输速率的提升，对字符串匹配引擎的速度需求也随之增长，现有的基于确定性有限自动机（DFA）的方法虽然可以实现高吞吐量，但其内存消耗极高，这使得它们在芯片内存资源有限的情况下显得不适用。 为了兼顾速度和内存效率，本研究论文提出了一种名为Kangaroo的紧凑字符串匹配方案。Kangaroo的核心理念是并行运行多个小型有限状态机（FSMs），同时处理多个字符，以此实现加速。每台小FSM负责处理特定部分的字符串，这样既能够分散计算负担，又不会过度占用内存。 Kangaroo的关键在于设计高效的并行机制，使得多个FSM能在有限的内存空间内协同工作，减少了单个机器所需的内存容量。它巧妙地将输入字符串分解成较小的部分，然后分配给每个FSM处理，每个FSM根据预定义的规则进行状态转移，当遇到匹配的模式时，这些FSM会协同确认并报告结果。这种并行处理策略显著提升了整体匹配速度，同时控制了内存消耗，使其更适合资源受限的嵌入式或物联网设备环境。 此外，论文还提供了理论证明，展示了Kangaroo在实际应用中的性能优势，包括处理时间和内存占用的优化分析。通过实验对比，Kangaroo在保证匹配准确性的前提下，能够在高带宽互联网环境中提供显著的性能提升，从而满足现代网络安全的需求，对于未来高效、低耗能的网络应用具有重要意义。"