[go: up one dir, main page]

Haber et al., 2013 - Google Patents

Efficient submatch extraction for practical regular expressions

Haber et al., 2013

View PDF
Document ID
13378773886615779082
Author
Haber S
Horne W
Manadhata P
Mowbray M
Rao P
Publication year
Publication venue
International Conference on Language and Automata Theory and Applications

External Links

Snippet

A capturing group is a syntax used in modern regular expression implementations to specify a subexpression of a regular expression. Given a string that matches the regular expression, submatch extraction is the process of extracting the substrings corresponding to those …
Continue reading at www.labs.hpe.com (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/50—Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
    • G06F21/55—Detecting local intrusion or implementing counter-measures
    • G06F21/56—Computer malware detection or handling, e.g. anti-virus arrangements
    • G06F21/562—Static detection
    • G06F21/563—Static detection by source code analysis
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30958—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/27—Automatic analysis, e.g. parsing
    • G06F17/2705—Parsing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/27—Automatic analysis, e.g. parsing
    • G06F17/2765—Recognition
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/02—Indexing scheme relating to groups G06F7/02 - G06F7/026
    • G06F2207/025—String search, i.e. pattern matching, e.g. find identical word or best match in a string
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/70—Software maintenance or management
    • G06F8/75—Structural analysis for program understanding

Similar Documents

Publication Publication Date Title
US9305116B2 (en) Dual DFA decomposition for large scale regular expression matching
Becchi et al. Memory-efficient regular expression search using state merging
US9990583B2 (en) Match engine for detection of multi-pattern rules
US7962434B2 (en) Extended finite state automata and systems and methods for recognizing patterns in a data stream using extended finite state automata
Yu et al. Fast and memory-efficient regular expression matching for deep packet inspection
US20120221494A1 (en) Regular expression pattern matching using keyword graphs
US8793251B2 (en) Input partitioning and minimization for automaton implementations of capturing group regular expressions
Yu et al. Revisiting state blow-up: Automatically building augmented-fa while preserving functional equivalence
Van Der Merwe et al. Turning evil regexes harmless
Obeidat et al. Developing a faster pattern matching algorithms for intrusion detection system
WO2013137864A1 (en) Submatch extraction
Rasool et al. A novel json based regular expression language for pattern matching in the internet of things
Shaul et al. cgspan: Closed graph-based substructure pattern mining
Lin et al. Reverse engineering input syntactic structure from program execution and its applications
Yang et al. Fast submatch extraction using OBDDs
CN103166942A (en) A network protocol analysis method for malicious code
Haber et al. Efficient submatch extraction for practical regular expressions
CN117201138B (en) A smart contract vulnerability detection method, system and device based on vulnerability subgraphs
Kallmeyer et al. A polynomial-time parsing algorithm for TT-MCTAG
CN114595148B (en) Java null pointer reference detection method and system based on data stream propagation analysis
Khalid et al. Si-dfa: Sub-expression integrated deterministic finite automata for deep packet inspection
Fujinami et al. Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping (Extended Version)
千田忠賢 On the Repair of Denial of Service in Real-World Regular Expressions
Su et al. A Novel Machine Learning-Based Model
Van Litsenborgh An investigation into performance-related issues of regular expression matching