Eagle+: A fast incremental approach to automaton and table online updates for cloud services

摘要

AbstractAutomaton or table-based multi-pattern matching methods have been widely used in cloud services, i.e., virtual Firewall service, virtual IDS service, etc. In cloud, a large scale of patterns in such services are frequently updated causing by users’ joining or quitting and adjustment of security and management policies. Therefore, how to quickly and accurately update the Automaton and Table becomes an important issue. In this paper, we propose Eagle+, an incremental approach for updating the matching Automaton and Table whilst avoiding recalculating the whole patterns after each change. In Eagle+, we attain efficiency by computing only the latest update set of patterns when updating the Automaton and Table. Moreover, Eagle+ achieves accurately local updating based on three atomic operations, adding, updating and deleting, each of which modifies values on classical Aho–Corasick (AC) automaton, Set Backward Oracle Matching (SBOM) automaton and Wu–Manber (WM) table. Compared with existing pattern updating methods, Eagle+ reduces the computation complexity fromO(n2)toO(n). The experimental results show that Eagle+ can save nearly 72%–92% of the time consumption in updating automatons and perform 100X faster in WM table.Highlights•We propose Eagle+, an incremental approach for updating the matching Automaton and Table.•Eagle+ can reduce nearly 92% of the time consumption in AC automaton and SOBM automaton.•Eagle+ can perform 100x faster than the global update approaches in WM table.