Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

DFA compression method and apparatus, and regular expression matching method and system

A technology of compression method and compression device, which is applied in the field of network security, can solve the problem of high memory usage of DFA, and achieve the effect of high compression rate and less memory

Active Publication Date: 2017-07-25
TSINGHUA UNIV
View PDF6 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] In order to solve the problem of excessive DFA memory usage in regular expression matching, the present invention provides a DFA compression method and device, a regular expression matching method and system

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • DFA compression method and apparatus, and regular expression matching method and system
  • DFA compression method and apparatus, and regular expression matching method and system
  • DFA compression method and apparatus, and regular expression matching method and system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0054] The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

[0055] DFA is constructed from different types of fragments, such as DFA constructed from all string fragments split by regular expressions, DFA constructed from all anchored string fragments or anchored fragments containing only a single chaotic factor, etc. Among them, the chaos factor is defined as the symbol combination ".*", "[^□]*", ".+", "[^□]+", ".{□}" or "[^□]{□}" .

[0056] For a DFA constructed from string fragments, also known as a front-end DFA, the syntax of the fragments is concatenation. Such as figure 1 as shown, figure 1 It is the DFA state transition diagram and state transition table corresponding to the string fragments "FIL", "CMD" and "URL". For...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a DFA (Deterministic Finite Automaton) compression method and apparatus, and a regular expression matching method and system. The DFA compression method comprises the steps of constructing a DFA according to a regular expression set, wherein the DFA comprises characters, states and transitions, corresponding to the characters, of the states, and corresponding to each character, the transition points to a state corresponding to the character from a current state; marking the states and the transitions according to the same transitions in the DFA, wherein the same transitions are transitions pointing to the same state; and compressing the DFA according to the marking of the states and the transitions. By marking the states and the state transitions in the DFA and compressing the DFA according to the marking of the states and the transitions, a relatively high compression rate can be achieved without influencing a search rate, thereby enabling the DFA to occupy less memory.

Description

technical field [0001] The present invention relates to the technical field of network security, and more specifically, to a DFA compression method and device, and a regular expression matching method and system. Background technique [0002] Regular expression-based pattern matching, referred to as regular expression matching, is the next generation firewall (NextGeneration Firewall, NGFW), intrusion detection / defense system (Intrusion Detection Systems / Intrusion Prevention System, IDS / IPS), unified threat management (Unified Threat Management) Management, UTM) and other key modules of security gateway systems, and high-performance regular expression matching is its core technology. The regular expression matching monitors or filters the network packet (Packet) by checking and processing the network packet load (Payload) of the application layer of the TCP / IP protocol. [0003] Regular expression matching is mainly realized through two data structures: Deterministic Finite...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F17/30H04L29/06
CPCG06F16/90344H04L63/0245H04L63/1408
Inventor 王凯李军
Owner TSINGHUA UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com