Offset-FA: A Uniform Method to Handle Both Unbounded and Bounded Repetitions in Regular Expression Matching

Area of Science:

• Computer Science
• Cybersecurity
• Network Security

Background:

• Cyber-physical systems (CPSs) are increasingly vulnerable to attacks, necessitating robust intrusion detection.
• Deep-packet inspection using regular expression matching (REM) is crucial for identifying threats in network traffic.
• State explosion in REM, caused by repetitive patterns, poses a significant challenge to efficient threat detection.

Purpose of the Study:

• To propose Offset-FA, a novel automaton designed to uniformly handle bounded and unbounded repetitions in REM.
• To address the state explosion problem in REM for enhanced CPS security.
• To improve the efficiency of intrusion detection mechanisms in CPS environments.

Main Methods:

• Offset-FA extracts repetitive elements from strings, compiling them into a fragment-DFA.
• It utilizes a fragment relation table and a reset table to maintain connections and offsets.
• This approach uniformly manages both bounded (counting) and unbounded (closures) repetitions.

Main Results:

• Offset-FA effectively eliminates state explosion by managing repetitions within string fragments.
• Experiments show Offset-FA significantly outperforms existing solutions in space cost and matching speed.
• The proposed method achieves matching speeds comparable to DFA on practical rule sets while ensuring correctness.

Conclusions:

• Offset-FA provides a unified mechanism for handling complex repetitions in REM, overcoming state explosion.
• This advancement offers a more efficient and effective solution for intrusion detection in CPS.
• The method demonstrates superior performance in space efficiency and detection speed for network security applications.