US Patent No: 7,996,424

Number of patents in Portfolio can not be more than 2000

Methods and systems for multi-pattern searching

Stats

ALSO PUBLISHED AS: 20080133523
ATTORNEY / AGENT: (SPONSORED)
 

Importance

Loading Importance Indicators... loading....

Abstract

Embodiments of the present invention relate to systems and methods for optimizing and reducing the memory requirements of state machine algorithms in pattern matching applications. Memory requirements of an Aho-Corasick algorithm are reduced in an intrusion detection system by representing the state table as three separate data structures. Memory requirements of an Aho-Corasick algorithm are also reduced by applying a banded-row sparse matrix technique to the state transition table of the state table. The pattern matching performance of the intrusion detection system is improved by performing a case insensitive search, where the characters of the test sequence are converted to uppercase as the characters are read. Testing reveals that state transition tables with sixteen bit elements outperform state transition tables with thirty-two bit elements and do not reduce the functionality of intrusion detection system using the Aho-Corasick algorithm.

Loading the Abstract Image... loading....

First Claim

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
SOURCEFIRE, INC.COLUMBIA, MD23

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Norton, Marc A Eldersburg, MD 10 116
Roelker, Daniel J Arlington, VA 10 116

Cited Art

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (12)
5,404,488 Realtime data feed engine for updating an application with the most currently received data from multiple data feeds 78 1993
5,901,307 Processor having a selectively configurable branch prediction unit that can access a branch prediction utilizing bits derived from a plurality of sources 28 1996
5,999,937 System and method for converting data between data sets 67 1997
6,684,332 Method and system for the exchange of digitally signed objects over an insecure network 14 1998
2004/0010,684 METHOD AND SYSTEM FOR THE EXCHANGE OF DIGITALLY SIGNED OBJECTS OVER AN INSECURE NETWORK 21 1998
6,199,181 Method and system for maintaining restricted operating environments for application programs or operating systems 153 1998
6,754,826 Data processing system and method including a network access connector for limiting access to the network 32 1999
6,993,706 Method, apparatus, and program for a state machine framework 36 2002
2005/0076,066 Method, system, and program for retaining versions of files 56 2003
2005/0108,393 Host-based network intrusion detection systems 24 2003
2006/0174,337 System, method and program product to identify additional firewall rules that may be needed 24 2005
2006/0294,588 System, method and program for identifying and preventing malicious intrusions 29 2005
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (10)
5,430,842 Insertion of network data checksums by a network adapter 63 1992
6,393,474 Dynamic policy management apparatus and method using active network devices 150 1998
6,320,848 Methods of altering dynamic decision trees 31 1999
7,134,141 System and method for host and network based intrusion detection and response 65 2001
6,999,998 Shared memory coupling of network infrastructure devices 23 2001
2003/0083,847 User interface for presenting data for an intrusion protection system 20 2001
2003/0101,353 Method, computer-readable medium, and node for detecting exploits based on an inbound signature of the exploit and an outbound signature in response thereto 44 2001
6,983,323 Multi-level packet screening with dynamically selected filtering criteria 27 2002
2004/0064,726 Vulnerability management and tracking system (VMTS) 31 2002
2005/0172,019 Network management 23 2005
 
CISCO TECHNOLOGY, INC. (8)
6,324,656 System and method for rules-driven multi-phase network vulnerability assessment 219 1998
6,415,321 Domain mapping method and system 100 1998
6,499,107 Method and system for adaptive network security using intelligent packet analysis 206 1998
6,487,666 Intrusion detection signature analysis using regular expressions and logical operators 197 1999
7,054,930 System and method for propagating filters 26 2000
2003/0212,910 Method and system for reducing the false alarm rate of network intrusion detection systems 16 2003
7,350,077 802.11 using a compressed reassociation exchange to facilitate fast handoff 58 2003
2007/0195,797 Network device that determines application-level network latency by monitoring option values in a transport layer message 16 2006
 
MCAFEE, INC. (6)
6,343,362 System and method providing custom attack simulation language for testing networks 41 1999
7,315,801 Network security modeling system and method 64 2000
6,851,061 System and method for intrusion detection data collection using a network protocol stack multiplexor 49 2000
7,096,503 Network-based risk-assessment tool for remotely detecting local computer vulnerabilities 36 2001
7,152,105 System and method for network vulnerability detection and reporting 67 2002
2003/0009,699 Method and apparatus for detecting intrusions on a computer system 76 2002
 
FUJITSU LIMITED (5)
5,963,942 Pattern search apparatus and method 64 1996
5,995,963 Apparatus and method of multi-string matching based on sparse state transition list 79 1997
2005/0210,098 Storage management system and method 2004
2005/0210,098 Storage management system and method 2004
2005/0210,098 Storage management system and method 2004
 
MICROSOFT CORPORATION (4)
6,766,320 Search engine with natural language-based robust parsing for user query and relevance feedback learning 162 2000
7,644,275 Pass-thru for client authentication 14 2003
2004/0210,756 Pass-thru for client authentication 31 2003
2004/0268,358 Network load balancing with host status information 84 2003
 
NCIRCLE NETWORK SECURITY, INC. (3)
7,073,198 Method and system for detecting a vulnerability in a network 57 2000
6,957,348 Interoperability of vulnerability and intrusion detection systems 54 2001
7,181,769 Network security system having a device profiler communicatively coupled to a traffic monitor 45 2003
 
SOURCEFIRE, INC. (3)
7,305,708 Methods and systems for intrusion detection 28 2004
7,313,695 Systems and methods for dynamic threat assessment 20 2004
7,317,693 Systems and methods for determining the network topology of a network 29 2004
 
COMPUTER ASSOCIATES THINK, INC. (2)
5,796,942 Method and apparatus for automated network-wide surveillance and security breach intervention 258 1996
2005/0273,673 Systems and methods for minimizing security logs 13 2005
 
ETELEMETRY, INC. (2)
7,133,916 Asset tracker for identifying user of current internet protocol addresses within an organization's communications network 25 2003
2007/0288,579 NETWORK ASSET TRACKER FOR IDENTIFYING USERS OF NETWORKED COMPUTERS 24 2006
 
GOOGLE INC. (2)
2002/0133,481 Methods and apparatus for providing search results in response to an ambiguous search query 15 2000
2002/0133,481 Methods and apparatus for providing search results in response to an ambiguous search query 15 2000
 
HITACHI, LTD. (2)
5,604,910 Method of and vector processor for searching text for key words based on candidate character strings obtained from the text using parallel processing 29 1990
4,985,863 Document storage and retrieval system 149 1990
 
INTEL CORPORATION (2)
6,587,876 Grouping targets of management policies 137 1999
7,174,566 Integrated network intrusion detection 48 2002
 
INTELLECTUAL VENTURES I LLC (2)
6,590,885 IP-flow characterization in a wireless point to multi-point (PTMP) transmission system 150 1999
2005/0268,331 Extension to the firewall configuration protocols and features 24 2004
 
NETWORKS ASSOCIATES TECHNOLOGY, INC. (2)
6,789,202 Method and apparatus for providing a policy-driven intrusion detection system 111 1999
6,546,493 System, method and computer program product for risk assessment scanning based on detected anomalous events 113 2001
 
NOVELL INTELLECTUAL PROPERTY HOLDINGS, INC. (2)
5,919,257 Networked workstation intrusion detection system 291 1997
6,539,381 System and method for synchronizing database information 111 1999
 
SRI INTERNATIONAL (2)
6,321,338 Network surveillance 348 1998
2004/0179,477 Method and apparatus for processing network packets 26 2004
 
SYMANTEC CORPORATION (2)
7,032,114 System and method for using signatures to detect computer intrusions 73 2000
7,065,657 Extensible intrusion detection system 53 2000
 
TREND MICRO INCORPORATED (2)
7,076,803 Integrated intrusion detection services 54 2002
2008/0168,561 HOST INTRUSION PREVENTION SERVER 19 2007
 
ABACA TECHNOLOGY CORPORATION (1)
6,772,196 Electronic mail filtering system and methods 121 2000
 
AIRDEFENSE, INC. (1)
2003/0217,283 Method and system for encrypted network management and intrusion detection 33 2002
 
ALCATEL CANADA INC. (1)
5,917,821 Look-up engine for packet-based network 146 1996
 
APPLE INC. (1)
6,477,648 Trusted workstation in a networked client/server computing system 103 1997
 
ARBOR NETWORKS, INC. (1)
7,596,807 Method and system for reducing scope of self-propagating attack code in network 12 2003
 
AT&T IPM CORP. (1)
5,459,841 Finite state machine with minimized vector processing 24 1993
 
AVAYA INC. (1)
2009/0041,020 CLOCK MANAGEMENT BETWEEN TWO ENDPOINTS 11 2007
 
BAAN DEVELOPMENT, B.V. (1)
5,987,473 Interactive configuration via network 37 1997
 
BELL TELEPHONE LABORATORIES, INCORPORATED (1)
4,550,436 Parallel text matching methods and apparatus 73 1983
 
BELLSOUTH INTELLECTUAL PROPERTY CORPORATION (1)
7,113,789 Method and system for tracking facilities related information 22 2001
 
BULL HN INFORMATION SYSTEMS INC. (1)
5,497,463 Ally mechanism for interconnecting non-distributed computing environment (DCE) and DCE systems to operate in a network system 177 1992
 
CHECK POINT SOFTWARE TECHNOLOGIES, INC. (1)
2005/0273,857 System and Methodology for Intrusion Detection and Prevention 28 2005
 
CIENA CORPORATION (1)
7,310,688 Relative addressing for network elements 36 2000
 
CITRIX SYSTEMS, INC. (1)
6,141,686 Client-side application-classifier gathering network-traffic statistics and application and user names using extensible-service provider plugin for policy-based network control 287 1998
 
COVELIGHT SYSTEMS, INC. (1)
2005/0188,079 Methods, systems and computer program products for monitoring usage of a server application 33 2004
 
CROSSBEAM SYSTEMS, INC. (1)
2007/0192,863 SYSTEMS AND METHODS FOR PROCESSING DATA FLOWS 69 2006
 
GENERAL DYNAMICS GOVERNMENT SYSTEMS CORPORATION (1)
6,711,127 System for intrusion detection and vulnerability analysis in a telecommunications signaling network 98 1998
 
GLOBALFOUNDRIES INC. (1)
5,870,554 Server selection method where a client selects a server according to address, operating system and found frame for remote booting 47 1996
 
HIGH TOWER SOFTWARE, INC. (1)
2004/0193,943 Multiparameter network fault detection system using probabilistic and aggregation analysis 47 2004
 
INSIDE SECURE (1)
6,678,734 Method for intercepting network packets in a computing device 62 1999
 
INVENSYS SYSTEMS, INC. (1)
2007/0027,913 System and method for retrieving information from a supervisory control manufacturing/production database 26 2005
 
IPOLICY NETWORKS PRIVATE LTD. (1)
7,058,821 System and method for detection of intrusion attacks on packets transmitted on a network 36 2002
 
KABUSHIKIGAISHA TEAMGIA (1)
2003/0140,250 Method and system of monitoring vulnerabilities 59 2002
 
LOCKHEED MARTIN CORPORATION (1)
2004/0172,234 Hardware accelerator personality compiler 35 2003
 
LUCENT TECHNOLOGIES INC. (1)
6,678,824 Application usage time limiter 48 1999
 
LUCID SECURITY CORPORATION (1)
2004/0073,800 Adaptive intrusion detection system 32 2003
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
5,495,409 Constructing method of finite-state machine performing transitions according to a partial type of success function and a failure function 23 1994
 
MATSUSHITA ELECTRIC WORKS, LTD. (1)
4,912,748 Infrared intrusion detector with a plurality of infrared ray detecting elements 52 1988
 
MISSION FOUNDSTONE, INC. (1)
7,257,630 System and method for network vulnerability detection and reporting 54 2003
 
MORGAN STANLEY & CO., INCORPORATED (1)
5,193,192 Vectorized LR parsing of computer programs 38 1990
 
MOTOROLA, INC. (1)
5,222,081 Method of performing an autobaud function using a state flow machine 37 1991
 
NETCLARITY, INC. (1)
7,346,922 Proactive network security system to protect against hackers 33 2004
 
NETWORK SECURITY SYSTEMS, INC. (1)
2001/0034,847 Internet/network security method and system for checking security of a client from a remote facility 97 2001
 
NEXUS NABOT RESEARCH L.L.C. (1)
2005/0160,095 System, method and computer program product for guaranteeing electronic transactions 27 2005
 
ORACLE INTERNATIONAL CORPORATION (1)
2002/0112,185 Intrusion threat detection 101 2001
 
RIVERBED TECHNOLOGY, INC. (1)
7,363,656 Event detection/anomaly correlation heuristics 34 2003
 
SAMIR GURUNATH KELEKAR (1)
2005/0005,169 System for real-time network-based vulnerability assessment of a host/device via real-time tracking, vulnerability assessment of services and a method thereof 28 2004
 
SENSORY NETWORKS, INC. (1)
2005/0114,700 Integrated circuit apparatus and method for high throughput signature based network applications 40 2003
 
SITKA SPRUCE SECURITY LLC (1)
6,002,427 Security system with proximity sensing for an electronic device 142 1997
 
SOORIYA NETWORKS, INC. (1)
2002/0083,344 Integrated intelligent inter/intra networking device 80 2001
 
SPONTANEOUS NETWORKS, INC. (1)
2002/0035,639 Systems and methods for a packet director 46 2001
 
SPYDER NAVIGATIONS L.L.C. (1)
2005/0268,332 Extensions to filter on IPv6 header 22 2004
 
SURFCONTROL, INC. (1)
6,219,786 Method and system for monitoring and controlling network access 148 1998
 
SYTEX, INC. (1)
2004/0221,176 Methodology, system and computer readable medium for rating computer system vulnerabilities 30 2003
 
TENABLE NETWORK SECURITY, INC. (1)
2005/0229,255 System and method for scanning a network 30 2004
 
THE UNITED STATES OF AMERICA AS REPRESENTED BY THE SECRETARY OF THE NAVY (1)
4,857,912 Intelligent security assessment system 219 1988
 
URO DENSHI KOGYO KABUSHIKI KAISHA (1)
4,570,157 Infrared intrusion alarm system capable of preventing false signals 34 1983
 
VERIZON SERVICES CORP. (1)
5,666,293 Downloading operating system software through a broadcast channel 460 1995
 
VIRGINIA COMMONWEALTH UNIVERSITY (1)
6,334,121 Usage pattern based user authenticator 74 1999
 
WYSE TECHNOLOGY INC. (1)
2003/0229,726 Default device configuration system and method for thin devices 18 2003
 
OTHER [CHECK PATENT PROFILE FOR ASSIGNMENT INFORMATION] (6)
2002/0087,716 System and method for transmitting customized multi priority services on a single or multiple links over data link layer frames 53 2000
2002/0165,707 Methods and apparatus for storing and processing natural language text data as a sequence of fixed length integers 51 2001
2002/0066,034 Distributed network security deception system 101 2001
2004/0093,582 Method for allowing a computer to be used as an information kiosk while locked 28 2003
2009/0028,147 Segmenting data packets for over-network transmission at adjustable fragment boundary 17 2008
2009/0132,648 CONTENT DELIVERY AND GLOBAL TRAFFIC MANAGEMENT NETWORK SYSTEM 2009

Patent Citation Ranking

Forward Cites

  • No Forward Cites to Display

Maintenance Fees

Fee Large entity fee small entity fee micro entity fee due date
3.5 Year Payment $1600.00 $800.00 $400.00 Feb 9, 2015
7.5 Year Payment $3600.00 $1800.00 $900.00 Feb 9, 2019
11.5 Year Payment $7400.00 $3700.00 $1850.00 Feb 9, 2023
Fee Large entity fee small entity fee micro entity fee
Surcharge - 3.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge - 7.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge - 11.5 year - Late payment within 6 months $160.00 $80.00 $40.00
Surcharge after expiration - Late payment is unavoidable $700.00 $350.00 $175.00
Surcharge after expiration - Late payment is unintentional $1,640.00 $820.00 $410.00