IP Library › Granted Patent US 12,437,210
Granted Patent B2
US 12,437,210 · App. 17/968,591 · Granted Oct 7, 2025

Data pattern analysis using optimized deterministic finite automaton

Inventors: Aleksandr Dubrovsky (San Mateo, CA); Justin Michael Brady (San Jose, CA); Roman Yanovsky (Los Altos, CA); Boris Yanovsky (Saratoga, CA)
Assignee: SonicWALL Inc.
G06N5/02G06F16/9024G06F21/552G06N5/00H04L63/1416H04L63/02
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,437,210
App. No.
17/968,591
Granted
Oct 7, 2025
Kind
B2
Abstract

Techniques for data pattern analysis using deterministic finite automaton are described herein. In one embodiment, a number of transitions from a current node to one or more subsequent nodes representing one or more sequences of data patterns is determined, where each of the current node and subsequent nodes is associated with a deterministic finite automaton (DFA) state. A data structure is dynamically allocated for each of the subsequent nodes for storing information associated with each of the subsequent nodes, where data structures for the subsequent nodes are allocated in an array maintained by a data structure corresponding to the current node if the number of transitions is greater than a predetermined threshold. Other methods and apparatuses are also described.

Claims (36)

1. A method for data pattern analysis, the method comprising:

receiving a plurality of data packets sent over a communication network to a network access device;

inspecting the plurality of data packets to identify a set of states corresponding to a set of transitions associated with a set of nodes, wherein the set of transitions is associated with movement from a first state to one or more second states of the set of states;

dynamically allocating a data structure maintained for each of the second states based on a comparison of a number of transitions associated with a number of the second states to a predetermined number of transitions; and

performing the data pattern analysis in accordance with the data structure maintained for each of the second states, wherein performing the data pattern analysis includes accessing the data structure allocated by a first type of data structure or a second type of data structure.

2. The method of claim 1 , wherein the data structure includes information about the second states, and wherein the information includes target data, match data, or link references to different data structures.

3. The method of claim 1 , wherein dynamically allocating the data structure is further based on the set of states having at least a threshold number of transitions in the set of transitions.

4. The method of claim 3 , wherein the data structure is allocated by the first type of data structure when the set of states has at least the threshold number of transitions, wherein the first type of data structure is an array.

5. The method of claim 3 , wherein the data structure is allocated by the second type of data structure when the set of states has less than the threshold number of transitions, and wherein the second type of data structure is in a linked-list configuration.

6. The method of claim 5 , wherein the linked-list configuration includes a link referencing an address of the second data structure.

7. The method of claim 1 , wherein a data structure of a first node allows for direct access to a data structure of a second node.

8. The method of claim 1 , wherein the data structure is dynamically allocated based on a comparison of a distance between a first node and a second node of the set of nodes to a predetermined distance.

9. The method of claim 8 , wherein the data structure is allocated by the first type of data structure when the second node is within the predetermined distance, wherein the first type of data structure is an array.

10. The method of claim 8 , wherein the predetermined distance is specified in a data structure of the first node.

11. A system for data pattern analysis, the system comprising:

a set of one or more nodes; and

a network access device that includes:

a communication interface that receives a plurality of data packets over a communication network,

a memory, and

a processor that executes instructions stored in the memory to:

inspect the plurality of data packets to identify a set of states corresponding to a set of transitions associated with the set of nodes, wherein the set of transitions is associated with movement from a first state to one or more second state of the set of states;

dynamically allocate a data structure maintained for each of the second states based on a comparison of a number of transitions associated with a number of the second states to a predetermined number of transitions; and

perform the data pattern analysis in accordance with the data structure maintained for each of the second states, wherein performing the data pattern analysis includes accessing the data structure allocated by a first type of data structure or a second type of data structure.

12. The system of claim 11 , wherein the data structure includes information about the second states, and wherein the information includes target data, match data, or link references to different data structures.

13. The system of claim 11 , wherein dynamically allocating the data structure is further based on the set of states having at least a threshold number of transitions in the set of transitions.

14. The system of claim 13 , wherein the data structure is allocated by the first type of data structure when the set of states has at least the threshold number of transitions, wherein the first type of data structure is an array.

15. The system of claim 13 , wherein the data structure is allocated by the second type of data structure when the set of states has less than the threshold number of transitions, wherein the second type of data structure is in a linked-list configuration.

16. A non-transitory, computer-readable storage medium, having embodied thereon a program executable by a processor to perform a method for data pattern analysis, the method comprising:

receiving a plurality of data packets sent over a communication network to a network access device;

inspecting the plurality of data packets to identify a set of states corresponding to a set of transitions associated with a set of nodes, wherein the set of transitions is associated with movement from a first state to one or more second states of the set of states;

dynamically allocating a data structure maintained for each of the second states based on a comparison of a number of transitions associated with a number of the second states to a predetermined number of transitions; and

performing the data pattern analysis in accordance with the data structure maintained for each of the second states, wherein performing the data pattern analysis includes accessing the data structure allocated by a first type of data structure or a second type of data structure.

17. The non-transitory, computer-readable storage medium of claim 11 , wherein the data structure includes information about the second states, and wherein the information includes target data, match data, or link references to different data structures.

18. The non-transitory, computer-readable storage medium of claim 16 , wherein dynamically allocating the data structure is further based on the set of states having at least a threshold number of transitions in the set of transitions.

19. The non-transitory, computer-readable storage medium of claim 18 , wherein the data structure is allocated by the first type of data structure when the set of states has at least the threshold number of transitions, wherein the first type of data structure is an array.

20. The non-transitory, computer-readable storage medium of claim 18 , wherein the data structure is allocated by the second type of data structure when the set of states has less than the threshold number of transitions, wherein the second type of data structure is in a linked-list configuration.

Assignments (8)
FIRST LIEN IP SUPPLEMENT Recorded Jun 30, 2025
From: SONICWALL US HOLDINGS INC.
To: UBS AG, STAMFORD BRANCH, AS COLLATERAL AGENT
Reel/Frame 071777/0641 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 21, 2022
From: QUEST SOFTWARE INC.
To: SONICWALL US HOLDINGS INC.
Reel/Frame 061741/0470 →
CHANGE OF NAME Recorded Oct 19, 2022
From: PSM MERGER SUB (DELAWARE), INC.
To: SONICWALL, INC.
Reel/Frame 061472/0958 →
MERGER Recorded Oct 19, 2022
From: SONICWALL L.L.C.
To: DELL SOFTWARE INC.
Reel/Frame 061473/0322 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 19, 2022
From: DUBROVSKY, ALEKSANDR; BRADY, JUSTIN MICHAEL; YANOVSKY, ROMAN; YANOVSKY, BORIS
To: SONICWALL, INC.
Reel/Frame 061471/0891 →
CHANGE OF NAME Recorded Oct 19, 2022
From: DELL SOFTWARE INC.
To: QUEST SOFTWARE INC.
Reel/Frame 061727/0083 →
CHANGE OF NAME Recorded Oct 19, 2022
From: SONICWALL, INC.
To: SONICWALL L.L.C.
Reel/Frame 061727/0071 →
MERGER Recorded Oct 19, 2022
From: SONICWALL, INC.
To: PSM MERGER SUB (DELAWARE), INC.
Reel/Frame 061472/0579 →
Continuity (5)
Continuation 15445687 · Feb 28, 2017
Continuation 14096866 · Dec 4, 2013
Continuation 13196484 · Aug 2, 2011
Continuation 11778546 · Jul 16, 2007
Related Publication 20230041014A1 · Feb 9, 2023
References Cited (75)
US 5796942A · Esbensen · 1998 [cited by applicant]
US 5945933A · Kalkstein · 1999 [cited by applicant]
US 6088803A · Tso et al. · 2000 [cited by applicant]
US 6108782A · Fletcher et al. · 2000 [cited by applicant]
US 6119236A · Shipley · 2000 [cited by applicant]
US 6178448B1 · Gray et al. · 2001 [cited by applicant]
US 6219706B1 · Fan et al. · 2001 [cited by applicant]
US 6449723B1 · Elgressy et al. · 2002 [cited by applicant]
US 6851061B1 · Holland et al. · 2005 [cited by applicant]
US 7134143B2 · Stellenberg et al. · 2006 [cited by applicant]
US 7152164B1 · Loukas et al. · 2006 [cited by applicant]
US 7185368B2 · Copeland, III · 2007 [cited by applicant]
US 7304996B1 · Swenson et al. · 2007 [cited by applicant]
US 7849502B1 · Bloch et al. · 2010 [cited by applicant]
US 7991723B1 · Dubrovsky · 2011 [cited by applicant]
US 8626689B1 · Dubrovsky · 2014 [cited by applicant]
US 9582756B2 · Dubrovsky · 2017 [cited by applicant]
US 11475315B2 · Dubrovsky · 2022 [cited by applicant]
US 20020083331A1 · Krumel · 2002 [cited by applicant]
US 20030061361A1 · Bacik et al. · 2003 [cited by applicant]
US 20030065800A1 · Wyschogrod et al. · 2003 [cited by applicant]
US 20030084328A1 · Tarquini et al. · 2003 [cited by applicant]
US 20030110208A1 · Wyschogrod et al. · 2003 [cited by applicant]
US 20030145228A1 · Suuronen et al. · 2003 [cited by applicant]
US 20030154399A1 · Zuk et al. · 2003 [cited by applicant]
US 20040093513A1 · Cantrell et al. · 2004 [cited by applicant]
US 20040123155A1 · Etoh et al. · 2004 [cited by applicant]
US 20040199790A1 · Lingafelt et al. · 2004 [cited by applicant]
US 20040255163A1 · Swimmer et al. · 2004 [cited by applicant]
US 20050120243A1 · Palmer et al. · 2005 [cited by applicant]
US 20050216770A1 · Rowett et al. · 2005 [cited by applicant]
US 20050262556A1 · Waisman et al. · 2005 [cited by applicant]
US 20060020595A1 · Norton et al. · 2006 [cited by applicant]
US 20060069787A1 · Sinclair · 2006 [cited by applicant]
US 20060075206A1 · Bouchard · 2006 [cited by examiner]
US 20070058551A1 · Brusotti et al. · 2007 [cited by applicant]
US 20080034073A1 · McCloy et al. · 2008 [cited by applicant]
US 20080271147A1 · Mohanan et al. · 2008 [cited by applicant]
EP 1122932 · 2001 [cited by applicant]
EP 1528743 · 2005 [cited by applicant]
WO WO9739399 · 1997 [cited by applicant]
Watson, Bruce W. “Practical optimizations for automata.” International Workshop on Implementing Automata. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. (Year: 1997). [cited by examiner]
Bernstein, David, Doron Cohen, and Dror E. Maydan. “Dynamic memory disambiguation for array references.” Proceedings of the 27th annual international symposium on Microarchitecture. 1994. (Year: 1994). [cited by examiner]
Aggarwal, N., “Improving the Efficiency of Network Intrusion Detection System”, Indian Institute of Technology, pp. 1-40, May 3, 2006. [cited by applicant]
Bellovin, S., “Firewall-Friendly FTP,” Network Working Group, RFC No. 1579, AT&T Bell Laboratories, Feb. 1994, Http://www.ietf.org/rfc1579.txt?number=1579, downloaded Jul. 15, 2002, 4 pages. [cited by applicant]
Blyth, Andrew, “Detecting Intrusion”, School of Computing, University of Glamorgan, 14 pages. [cited by applicant]
Branch, Joel, “Denial of Service Intrusion Detection Using Time Dependent Deterministic Finite Automata”, RPI Graduate Research Conference 2002, Oct. 17, 2002. 7 pages. [cited by applicant]
Gateway Anti-Virus, Anti-Spyware and Intrusion Prevention Service, Unified Threat Management, Intelligent Real-time Protection, © 2005, 2 pp. [cited by applicant]
Giles, C., “Learning a Class of Large Finite State Machines with a Recurrent Neural Network”, Neural Networks, vol. 8., No. 9, pp. 1359-1365, 1995. [cited by applicant]
Holzmann, G., “A Minimized Automaton Representation of Reachable States”, Int J STTT 2, pp. 270-278, 1999. [cited by applicant]
Juniper Networks, “Architecture,” www.juniper.net/products/intrusion/architecture.html, downloaded Jun. 11, 2004, 3 pages. [cited by applicant]
Juniper Networks, “Attack Detection,” www.juniper.net/products/intrusion/detection.html, downloaded Jun. 11, 2004, 7 pages. [cited by applicant]
Juniper Networks, “Attack Prevention,” www.juniper.net/products/intrusion/prevention.html, downloaded Jun. 11, 2004, 2 pages. [cited by applicant]
Juniper Networks, “Intrusion Detection and Prevention,” www.juniper.net/products/intrusion/downloaded Jun. 11, 2004, 2 pages. [cited by applicant]
Juniper Networks, “Juniper Networks NetScreen-IDP 10/100/500/1000,” Intrusion Detection and Prevention, Spec Sheet, Apr. 2004, 2 pages. [cited by applicant]
Lucas, S., “Learning Deterministic Finite Automata with a Smart State Labeling Evolutionary Algorithm”, IEEE Transaction on Pattern Analysis and Machine Intelligence , vol. 27, No. 7, pp. 1063-1074 Jul. 2005. [cited by applicant]
Krugal, Christopher, “Using Decision Trees to Improve Signature-Based Intrusion Detection”, Sep. 8, 2003, RAID 2003: recent Advance in Intrusion Detection, 20 pages. [cited by applicant]
Roberts, Paul, “NetScreen Announces Deep Inspection Firewall,” IDG News Service, Oct. 20, 2003, http://www.nwfusion.com/news/2003/1020netscannou.html, downloaded Jun. 11, 2004. [cited by applicant]
Roesch, Martin and Green, Chris, “Snort Users Manual,” Snort Release 2.0.0, M. Roesch, C. Green, Copyright 1998-2003 M. Roesch, Copyright 2001-2003 C. Green, Copyright 2003 Sourcefire, Inc. dated Dec. 8, 2003 (53 pgs). [cited by applicant]
“Snort™: The Open Source Network Intrusion Detection System”, accessed at: http://www.snort.org/about.html on Jun. 23, 2004, last updated Jun. 23, 2004, 2 pages. [cited by applicant]
SonicWALL Complete Anti-Virus, Automated and Enforced Anti-Virus Protection, © 2005, 2 pp. [cited by applicant]
SonicWALL Content Filtering Service, Comprehensive Internet Security™, © 2005, 2 pp. [cited by applicant]
SonicWALL Content Security Manager Series, Easy-to-use, Affordable, Content Security and Internet Threat Protection, © 2006, Dec. 2006. 4 pp. [cited by applicant]
SonicWALL Endpoint Security: Anti-Virus, Automated and Enforced Anti-Virus and Anti-Spyware Protection, © 2007, Mar. 2007, 2 pp. [cited by applicant]
SonicWALL Internet Security Appliances, “Content Security Manager Integrated Solutions Guide”, Version 3.0, © 2007, 160 pp. [cited by applicant]
SonicWALL Internet Security Appliances, “SonicOS 3.8 Standard Administrator's Guide”, © 2007, 362 pp. [cited by applicant]
SonicOS Standard 3.8.0.2 Release Notes, SonicWALL secure Anti-Virus Router 80 Series, SonicWALL, Inc., Software Release: Apr. 11, 2007, 13 pp. [cited by applicant]
“The Ultimate Internet Sharing Solution, WinProxy, User Manual,” Copyright 1996-2002 Osistis Software, Inc., dated Feb. 2002 (290 pgs). [cited by applicant]
Van Engelen, R., “Constructing Finite State Automata for High-Performance XML Web Services”, International Symposium on Web Services and Applications, pp. 1-7, 2004. [cited by applicant]
EP Application No. EP 04 02 5579, European Search Report dated May 23, 2005, 3 pages. [cited by applicant]
U.S. Appl. No. 11/778,546; Final Office Action mailed Oct. 22, 2010. [cited by applicant]
U.S. Appl. No. 11/778,546; Office Action mailed Jul. 7, 2010. [cited by applicant]
U.S. Appl. No. 13/196,484; Office Action mailed Apr. 2, 2013. [cited by applicant]
U.S. Appl. No. 14/096,866; Office Action mailed Apr. 21, 2016. [cited by applicant]
U.S. Appl. No. 14/096,866; Office Action mailed Jan. 6, 2022. [cited by applicant]