DE112006000260B4 - Parser for analyzing a text-coded protocol - Google Patents

Parser for analyzing a text-coded protocol Download PDF

Info

Publication number
DE112006000260B4
DE112006000260B4 DE112006000260.0T DE112006000260T DE112006000260B4 DE 112006000260 B4 DE112006000260 B4 DE 112006000260B4 DE 112006000260 T DE112006000260 T DE 112006000260T DE 112006000260 B4 DE112006000260 B4 DE 112006000260B4
Authority
DE
Germany
Prior art keywords
control unit
state
proc
match
follow
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
DE112006000260.0T
Other languages
German (de)
Other versions
DE112006000260T5 (en
Inventor
Baohua Zhao
Yugui Qu
Hao Zhou
Ye Tian
Shuo Wang
Qiyue Li
Chao Lv
Zhiwei Jin
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
University of Science and Technology of China USTC
Original Assignee
Huawei Technologies Co Ltd
University of Science and Technology of China USTC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd, University of Science and Technology of China USTC filed Critical Huawei Technologies Co Ltd
Publication of DE112006000260T5 publication Critical patent/DE112006000260T5/en
Application granted granted Critical
Publication of DE112006000260B4 publication Critical patent/DE112006000260B4/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F40/00—Handling natural language data
    • G06F40/20—Natural language analysis
    • G06F40/205—Parsing
    • G06F40/211—Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
    • H04L69/22—Parsing or analysis of headers

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Artificial Intelligence (AREA)
  • Computational Linguistics (AREA)
  • General Health & Medical Sciences (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Health & Medical Sciences (AREA)
  • Audiology, Speech & Language Pathology (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Devices For Executing Special Programs (AREA)
  • Communication Control (AREA)

Abstract

Parser zur Analyse eines textkodierten Protokolls, umfassend: ein Analyseregel-Speichermodul (102), welches dazu ausgelegt ist, Analyseregeln zur Analyse eines Pakets des textkodierten Protokolls zu speichern, wobei das Analyseregel-Speichermodul (102) dazu ausgelegt ist, einen gemäß Augmented Backus-Naur Form, ABNF, Regeln generierten Regelbaum zu speichern, wobei der Regelbaum keine stufenweise Auswahl, Sequenzgruppe oder optionale Sequenzstruktur enthält; und wobei der Regelbaum auf rekursive Weise generiert wird, indem eine Regel in dem Regelbaum als Spitze bzw. vertex verwendet wird; und ein Paketanalyse-Modul (101), welches mittels eines Logikbausteins implementiert ist und dazu ausgelegt ist, eine Zeichenfolge des Pakets zu lesen, den in dem Analyseregel-Speichermodul (102) gespeicherten Regelbaum zu erhalten, einen Wert für den Regelbaum mit der Zeichenfolge des Pakets bestimmen, um einen mit diesem Wert versehen Regelbaum zu erzeugen und den mit diesem Wert versehenen Regelbaum als ein Analyseergebnis auszugeben, wobei das Paketanalyse-Modul umfasst: eine main_proc Steuereinheit (201), die dazu ausgelegt ist, den Übergang in eine parse_term_proc Steuereinheit (202), eine match_first_proc Steuereinheit (203) und eine match_follow_proc Steuereinheit (204) jeweils zu kontrollieren basierend auf der Art eines Anfangsknotens eines Stacks; wobei Knoten des Regelbaums in dem Stack gespeichert werden; und wobei der Anfangsknoten des Stacks ein Knoten des obersten Elements des Stacks ist; wobei die parse_term_proc Steuereinheit (202) dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit (201) gestartet zu werden im Falle, dass der Anfangsknoten ein Endknoten ist und die main_proc Steuereinheit (201) nach der Analyse des Pakets zu informieren; wobei der Endknoten ein Blatt ist, d. h. ein Blatt der vereinfachten ABNF-Regel ...A parser for analyzing a text-coded protocol, comprising: an analysis rule storage module (102), which is designed to store analysis rules for analyzing a packet of the text-coded protocol, the analysis rule storage module (102) being designed to implement an augmented backus Save form, ABNF, rules generated rule tree, whereby the rule tree does not contain a step-by-step selection, sequence group or optional sequence structure; and wherein the rule tree is generated recursively using a rule in the rule tree as a vertex; and a packet analysis module (101), which is implemented by means of a logic module and is designed to read a character string of the packet, to obtain the rule tree stored in the analysis rule memory module (102), a value for the rule tree with the character string of Determine packages in order to generate a rule tree provided with this value and to output the rule tree provided with this value as an analysis result, the packet analysis module comprising: a main_proc control unit (201) which is designed to transition to a parse_term_proc control unit ( 202) to control a match_first_proc control unit (203) and a match_follow_proc control unit (204) based on the type of an initial node of a stack; wherein nodes of the rule tree are stored in the stack; and wherein the starting node of the stack is a node of the top element of the stack; wherein the parse_term_proc control unit (202) is designed to be started under the control of the main_proc control unit (201) in the event that the start node is an end node and to inform the main_proc control unit (201) after analysis of the packet; where the end node is a leaf, i. H. a sheet of the simplified ABNF rule ...

Description

Gebiet der ErfindungField of the invention

Die vorliegende Erfindung bezieht sich auf das Gebiet der Netzwerkkommunikationstechnik und insbesondere auf einen Parser zur Analyse eines textkodierten Protokolls.The present invention relates to the field of network communication technology, and more particularly to a parser for analyzing a text-coded protocol.

Hintergrund der ErfindungBackground of the invention

Die Internet Engineering Task Force (IETF) definiert Paketformate für mehrere Protokolle, beispielsweise das Session Initial Protocol (SIP), durch die Augmented Backus-Naur Form (ABNF). Wenn die Protokolle implementiert werden, müssen die Pakete entsprechend ihrer ABNF Spezifikation analysiert werden.The Internet Engineering Task Force (IETF) defines packet formats for multiple protocols, such as the Session Initial Protocol (SIP), through the Augmented Backus-Naur Form (ABNF). When the protocols are implemented, the packets must be parsed according to their ABNF specification.

Die ABNF ist eine durch die IETF in RFC2234 definierte Formatsyntax. Die ABNF ist eine abgeänderte Version der Backus-Naur Form (BNF). Die Unterschiede zwischen der ABNF und der BNF umfassen: Benennungsregeln, Wiederholungen, Alternativen, Unabhängigkeit in der Reihenfolge und Wertebereiche.The ABNF is a format syntax defined by the IETF in RFC2234. The ABNF is a modified version of the Backus-Naur Form (BNF). The differences between the ABNF and the BNF include: naming rules, repetitions, alternatives, order of order, and ranges of values.

Gegenwärtig wird ein ABNF Parser normalerweise auf einem universellen Mikroprozessor implementiert durch Software, welche einen Algorithmus zur Analyse der Wortbildung (Morphologie) und des Satzbaus (Syntax) ausführt, beispielsweise einen LL (1) Algorithmus zur Syntaxanalyse innerhalb einer kompilierenden Hauptdomäne. Der LL (1) Algorithmus zur Syntaxanalyse ist ein nicht-rekursiver Analysator. Der LL (1) Algorithmus zur Syntaxanalyse erstellt eine Tabelle zur Vorhersage-Analyse der Syntax durch Berechnung eines First Terminals Set und eines Follow Terminals Set der Syntax, um so eine Folgerung zu erstellen, entsprechend der Tabelle zur Vorhersage-Analyse. Die LL (1) Syntax ist eine eindeutige Syntax ohne Linksrekursion. Das erste „L” der Bezeichnung LL (1) bedeutet, dass eine eingegeben Zeichenfolge (string) von links nach rechts gescannt wird; das zweite „L” bedeutet, dass eine Linksableitung generiert wird; „1” bedeutet, dass sich der Algorithmus bei der Bestimmung jeder Aktion des ABNF-Parsers auf jeweils ein Eingabesymbol weiter bezieht.At present, an ABNF parser is normally implemented on a general purpose microprocessor by software executing an algorithm for word formation (morphology) and sentence structure (syntax) analysis, for example, an LL (1) algorithm for parsing within a main compiling domain. The LL (1) parsing algorithm is a non-recursive analyzer. The LL (1) parsing algorithm builds a syntax predictive analysis table by computing a First Terminal Set and a Follow Terminal Set of syntax to create an inference, according to the Predictive Analysis table. The LL (1) syntax is a unique syntax with no left recursion. The first "L" of the label LL (1) means that an input string is scanned from left to right; the second "L" means that a link derivation is generated; "1" means that when determining each action of the ABNF parser, the algorithm refers to one input symbol at a time.

Da die ABNF eine textkodierte Syntax-Definition ist, ist es für den ABNF Parser komplexer, eine Zeichenfolge (string) mit einer variablen Länge zu analysieren als binäre Daten mit einer festgelegten Länge zu analysieren. Der Vorteil des ABNF Parsers ist, dass der ABNF Parser mit geringeren Kosten und höherer Effizienz implementiert werden kann. Allerdings ist der universelle Mikroprozessor nicht speziell für den ABNF Parser vorgesehen. Daher sind oft die Verarbeitungsgeschwindigkeit, der Durchsatz und andere Leistungsparameter des Mikroprozessors beschränkt. Im Fall, dass eine höherer Verarbeitungsgeschwindigkeit benötigt wird, beispielsweise wenn ein SIP Softswitch System Millionen von Verbindungen verwalten muss, ist es notwendig, einen höherwertigen Mikroprozessor zu verwenden. Damit werden die Kosten eines ABNF Parsers unweigerlich erhöht.Since the ABNF is a text-coded syntax definition, it is more complex for the ABNF parser to parse a string of variable length than to parse binary data of a fixed length. The advantage of the ABNF parser is that the ABNF parser can be implemented at a lower cost and higher efficiency. However, the universal microprocessor is not specifically designed for the ABNF parser. Therefore, processing speed, throughput and other performance parameters of the microprocessor are often limited. In case a higher processing speed is needed, for example when a SIP softswitch system needs to manage millions of connections, it is necessary to use a higher order microprocessor. This will inevitably increase the cost of an ABNF parser.

Es existiert eine weitere Art eines ABNF Parsers, die auch auf einem universellen Mikroprozessor implementiert werden kann. Für diese Art des ABNF Parsers ist, im Hinblick auf die Merkmale der ABNF Syntaxregeln innerhalb einer speziellen Domain, eine spezielle Software entworfen worden. Was beispielsweise das SIP betrifft, so ist es eine übliche Implementierung, ein SIP Paket in mehrere Felder entsprechend des Merkmals der SIP Syntaxregel durch einen Segmentierungs-Identifikator aufzuteilen; anschließend wird die Überprüfung der entsprechenden Syntaxregel durchgeführt.There is another type of ABNF parser that can also be implemented on a universal microprocessor. For this type of ABNF parser, a special software has been designed with respect to the features of the ABNF syntax rules within a particular domain. As for the SIP, for example, it is a common implementation to divide a SIP packet into multiple fields according to the feature of the SIP syntax rule by a segmentation identifier; then the verification of the corresponding syntax rule is performed.

Die zweite Art eines ABNF Parsers ist für eine spezielle Syntaxregel erstellt worden, wodurch die Effizienz größer ist als die des ersten oben beschriebenen ABNF Parsers. Allerdings führt das spezielle Design der zweiten Art eines ABNF Parsers auch zu einer schlechten Allgemeingültigkeit. Für eine neue Syntaxregel muss der ABNF Parser neu erstellt werden. Hierdurch werden somit die Kosten fair die Entwicklung eines ABNF Parsers erhöht und die Entwicklungseffizienz wird verringert. Auf der anderen Seite, da die zweite Art des ABNF Parsers basierend auf dem universellen Mikroprozessor nach wie vor erstellt wird, existiert das beschriebene Problem hinsichtlich der ersten Art des ABNF Parsers immer noch, wenn eine hohe Verarbeitungsgeschwindigkeit erforderlich ist.The second type of ABNF parser has been created for a special syntax rule, which is more efficient than the first ABNF parser described above. However, the special design of the second type of ABNF parser also leads to poor generality. For a new syntax rule, the ABNF parser needs to be recreated. This increases the cost of developing an ABNF parser and reduces development efficiency. On the other hand, since the second type of ABNF parser is still created based on the universal microprocessor, the described problem regarding the first type of ABNF parser still exists when a high processing speed is required.

Im Stande der Technik werden zunächst in der Druckschrift US 5,916,305A Daten-Kommunikationspakete verarbeitet, um zu bestimmten ob sie zu Netzwerkprotokollen passen, die eine Analysetabelle (parser table) und einen prädiktiven Analysator verwenden. Die Analysetabelle ist von Produktionsregeln enkodiert, die von einer Netzwerkprotokoll-Definition abgeleitet sind. Die Pakete weisen Datenelemente auf, die jeweils einen Versatz von dem Beginnen des Paketes und einen Datenwert haben. Die Analysetabelle wird durch diese Versatze (offsets) und Datenwerte indiziert, wobei jeder Ort in der Tabelle, der einen Wert enthält, der anzeigt, ob ein Datenelement an dem Versatz und das einen Datenwert aufweist, ein gültiges Element für die Netzwerkprotokolldefinition ist. Sobald die Analysetabelle encodiert ist, wird die Analysetabelle mit dem prädiktiven Analysator verwendet, der Datenelemente eines Datenpaketes von einer Netzwerkquelle empfängt. Der prädiktive Analysator verwendet den Versatz und Daten Wert von jedem Datenelement um den enkodierten Wert in der Analysetabelle zu erhalten. Der prädiktive Analysator aktualisiert einen Analysestapel gemäß dem Wert von der Analysetabelle und dem gegenwertigen Wert des Analysestapels. Die Analysetabelle zeigt an, welchen Versatz, welche Wertepaare mit dem Ende des Datenpaketes oder eines anderen Teils von Interesse miteinander verbunden sind. Wenn das Ende erreicht wird, zeigt der Analysestapel an, ob das Datenpaket zu der Netzwerkprotokolldefinition gepasst hat.In the prior art are initially in the document US 5,916,305A Data communication packets are processed to determine if they match network protocols using a parser table and a predictive analyzer. The analysis table is encoded by production rules derived from a network protocol definition. The packets have data elements each having an offset from the beginning of the packet and a data value. The analysis table is indexed by these offsets and data values, where each location in the table that contains a value that indicates whether a data item at the offset and that has a data value is a valid element for the network protocol definition. Once the analysis table is encoded, the analysis table is used with the predictive analyzer, which receives data elements of a data packet from a network source. The predictive analyzer uses the offset and data value of each data item encoded by the encoded one Value in the analysis table. The predictive analyzer updates an analysis stack according to the value of the analysis table and the equivalent value of the analysis stack. The analysis table indicates which offset, which value pairs are connected to the end of the data packet or another part of interest. When the end is reached, the analysis stack indicates whether the data packet matched the network protocol definition.

Weiterhin, in der Einleitung zum RFC-Dokument 2234, ”Erweiterte BNF für Syntax Spezifikationen: ABNF”, Crocker, D; P. Overell; November 1997; Fundstelle: http://www.ietf.org/rfc/rfc2234.txt, wird eine modifizierte Version der Backus-Naur Form, BNF, behandelt, die Erweiterte BNF (Augmented BNF, ABNF) genannt wird. Die ABNF tariert Kompaktheit und Einfachheit mit vernünftiger Darstellungskraft aus. In den frühen Tagen des Arpnet, enthielt jede Spezifikation ihre eigene Definition einer ABNF. Vorstehendes enthielt die Email Spezifikationen RFC733 und dann RFD822, welche dazu gekommen sind, die allgemeinen Zitierungen zum Definieren der ABNF zu sein. [...] Die Unterschiede zwischen Standard-BNF und ABNF betreffen Namensregeln, Wiederholungen, Alternativen, Reihenfolge-Unabhängigkeit (order-independence) und Wertebereiche.Furthermore, in the introduction to RFC document 2234, "Advanced BNF for Syntax Specifications: ABNF", Crocker, D; Overell; November 1997; Reference: http://www.ietf.org/rfc/rfc2234.txt, a modified version of the Backus-Naur form, BNF, is discussed, which is called Advanced BNF (Augmented BNF, ABNF). The ABNF tared compactness and simplicity with reasonable imagination. In the early days of Arpnet, each specification contained its own definition of an ABNF. The above contained the email specifications RFC733 and then RFD822, which have come to be the general citations for defining the ABNF. [...] The differences between standard BNF and ABNF concern naming rules, repetitions, alternatives, order-independence and ranges of values.

Dann zeigt die US 2004/0088425 A1 einen Anwendungsebenen-Torweg (Application Level Gateway, ALG) in einem Datenübertragungsnetzwerk, der auf einem universellen Analysator basiert. Der vorbezeichnete ALG ermöglicht, allen Datenfluß über einen Anwendungsebenenprotokoll auf Konkordanz mit der formellen Syntax-Beschreibung des Datenübertragungsprotokolls und mit einer Sicherheitspolitik (security policy) zu prüfen. Der ALG enthält einen Übertragungs-Kontroller, universellen Analysator, und wenigstens ein Analyse-Einsteckmodul (plug-in) für jedes universelles Analysemodul. Vorgenanntes Analyse-Einsteckmodul ist spezifisc zu dem Datenübertragungsprotokoll und kann automatisch von der formalen Syntaxbeschreibung eines Datenübertragungsprotokolls erschaffen werden. Eine Sicherheitspolitik (Regeln, Einschränkungen) können in dem Analyse-Einsteckmodul und/oder in den Einstellungen (settings) implementiert werden.Then the shows US 2004/0088425 A1 an Application Level Gateway (ALG) in a communications network based on a universal analyzer. The above-mentioned ALG makes it possible to check all data flow via an application level protocol for concordance with the formal syntax description of the data transmission protocol and with a security policy. The ALG includes a transmission controller, universal analyzer, and at least one analysis plug-in module for each universal analysis module. The aforementioned analysis plug-in module is specific to the data transmission protocol and can be automatically created from the formal syntax description of a data transmission protocol. A security policy (rules, restrictions) can be implemented in the Analysis plug-in module and / or in the settings.

Und schließlich werden nach der WO 2004/079571 A2 fehlerfreie Zustandstabellen (state tables) werden automatisch von einer Spezifikation einer Gruppe von gewünschten durchführbaren Funktionen erzeugt, welche zum Beispiel in einer Programmiersprache in einer formellen Notation, wie zum Beispiel eine Backus-Naur-Form oder einer Abgeleiteten davon bereitgestellt werden, durch Unterschieden von Zeichen (token), korrespondierend zu entsprechenden durchführbaren Funktionen, Identifikationen, Argumenten, Syntax, Grammatik-Regel, speziellen Symbolen und Ähnlichem. Die Zeichen können rekursiv (z. B. unendlich) sein, in jenem Fall sie in ein endliches Automata transformiert werden, welches deterministisch oder nichtdeterministisch sein kann. Nicht-deterministische endliche Automata werden in deterministische endliche Automata transformiert und dann in Zustandsübergänge, welche verwendet werden, um eine Zustandstabelle zu bauen, welche dann gespeichert werden kann, oder, bevorzugt, in eine endliche Zustandsmaschine eines Hardware-Analysator-Beschleunigers geladen werden kann, um seine Personalität zu definieren.And finally, after the WO 2004/079571 A2 error-free state tables are automatically generated from a specification of a set of desired workable functions provided, for example, in a programming language in a formal notation, such as a backus-Naur form or a derivative thereof, by character differences (token), corresponding to corresponding executable functions, identifications, arguments, syntax, grammar rules, special symbols, and the like. The signs can be recursive (eg, infinite) in case they are transformed into a finite automata, which can be deterministic or nondeterministic. Non-deterministic finite automata are transformed into deterministic finite automata and then into state transitions, which are used to build a state table which can then be stored, or, preferably, loaded into a finite state machine of a hardware analyzer accelerator, to define his personality.

Zusammenfassung der ErfindungSummary of the invention

Die Ausführungsformen der vorliegenden Erfindung betreffen einen Parser zur Analyse eines textkodierten Protokolls, um die Effizienz der Analyse zu verbessern und die Allgemeingültigkeit des Parsers zu erhöhen.The embodiments of the present invention relate to a parser for analyzing a text-coded protocol in order to improve the efficiency of the analysis and to increase the generality of the parser.

Gemäß einer Ausführungsform der vorliegenden Erfindung umfasst ein Parser zur Analyse eines textkodierten Protokolls:
ein Analyseregel-Speichermodul 102, welches dazu ausgelegt ist, Analyseregeln zur Analyse eines Pakets des textkodierten Protokolls zu speichern, wobei das Analyseregel-Speichermodul 102 dazu ausgelegt ist, einen gemäß Augmented Backus-Naur Form, ABNF, Regeln generierten Regelbaum zu speichern, wobei der Regelbaum keine stufenweise Auswahl, Sequenzgruppe oder optionale Sequenzstruktur enthält; und
wobei der Regelbaum auf rekursive Weise generiert wird, indem eine Regel in dem Regelbaum als Spitze bzw. vertex verwendet wird; und
ein Paketanalyse-Modul 101, welches mittels eines Logikbausteins implementiert ist und dazu ausgelegt ist, eine Zeichenfolge des Pakets zu lesen, den in dem Analyseregel-Speichermodul 102 gespeicherten Regelbaum zu erhalten, einen Wert für den Regelbaum mit der Zeichenfolge des Pakets bestimmen, um einen mit diesem Wert versehen Regelbaum zu erzeugen und den mit diesem Wert versehenen Regelbaum als ein Analyseergebnis auszugeben, wobei das Paketanalyse-Modul umfasst:
eine main_proc Steuereinheit 201, die dazu ausgelegt ist, den Übergang in eine parse_term_proc Steuereinheit 202, eine match_first_proc Steuereinheit 203 und eine match_follow_proc Steuereinheit 204 jeweils zu kontrollieren basierend auf der Art eines Anfangsknotens eines Stacks; wobei Knoten des Regelbaums in dem Stack gespeichert werden; und wobei der Anfangsknoten des Stacks ein Knoten des obersten Elements des Stacks ist;
wobei die parse_term_proc Steuereinheit 202 dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden im Falle, dass der Anfangsknoten ein Endknoten ist und die main_proc Steuereinheit 201 nach der Analyse des Pakets zu informieren; wobei der Endknoten ein Blatt ist, d. h. ein Blatt der vereinfachten ABNF-Regel;
wobei die match_first_proc Steuereinheit 203 dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden im Fall, dass der Anfangsknoten kein Endknoten ist und zu einem First Terminals Set gehört, und die main_proc Steuereinheit 201 zu informieren über die Entscheidung, ob ein derzeitiges Zeichen zu dem First Terminals Set gehört oder nicht durch Abgleich des derzeitigen Zeichens mit allen Zeichen des First Terminals Set;
wobei die match_follow_proc Steuereinheit 204 dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden im Fall, dass der Anfangsknoten kein Endknoten ist und zu einem Follow Terminals Set gehört, und die main_proc Steuereinheit 201 zu informieren über die Entscheidung, ob das derzeitige Zeichen zu dem Follow Terminals Set gehört oder nicht durch Abgleich des derzeitigen Zeichens mit allen Zeichen des Follow Terminals Set.According to one embodiment of the present invention, a parser for analyzing a text-coded protocol comprises:
an analysis rule memory module 102 , which is adapted to store analysis rules for analyzing a packet of the text-coded protocol, wherein the analysis rule memory module 102 is adapted to store a rule tree generated in accordance with Augmented Backus-Naur Form, ABNF, Rules, the rule tree containing no stepwise selection, sequence group, or optional sequence structure; and
wherein the rule tree is recursively generated by using a rule in the rule tree as the vertex; and
a packet analysis module 101 which is implemented by means of a logic device and is adapted to read a string of the packet contained in the analysis rule memory module 102 to obtain a stored rule tree, determine a value for the rule tree with the string of the package to generate a rule tree provided with that value and output the rule tree provided with this value as an analysis result, the package analysis module comprising:
a main_proc control unit 201 which is designed to transition into a parse_term_proc control unit 202 , a match_first_proc control unit 203 and a match_follow_proc control unit 204 each based on the type of an initial node of a stack; wherein nodes of the rule tree are stored in the stack; and wherein the starting node of the stack is a node of the topmost element of the stack;
the parse_term_proc control unit 202 is designed to be under the control of the main_proc control unit 201 to be started in case the initial node is an end node and the main_proc control unit 201 after analyzing the package too to inform; the end node being a leaf, ie a leaf of the simplified ABNF rule;
the match_first_proc control unit 203 is designed to be under the control of the main_proc control unit 201 to be started in case the initial node is not an end node and belongs to a First Terminals set, and the main_proc control unit 201 to inform about the decision whether a current character belongs to the First Terminal Set or not by comparing the current character with all the characters of the First Terminal Set;
the match_follow_proc control unit 204 is designed to be under the control of the main_proc control unit 201 to be started in the event that the starting node is not an end node and belongs to a Follow Terminals set, and the main_proc control unit 201 to inform you of the decision whether the current character belongs to the Follow Terminal Set or not by comparing the current character with all characters of the Follow Terminal Set.

Der gemäß der Ausführungsformen der vorliegenden Erfindung bereitgestellte Parser wird basierend auf einem Hardware Logikbaustein implementiert. Verglichen mit den Software basierten Parser verbessert der Hardware basierte Parser, wie er gemäß der Ausführungsformen der vorliegenden Erfindung vorgeschlagen wird, die Analyseeffizienz und reduziert die Entwicklungskosten des Parsers. Zusätzlich analysiert der Parser gemäß der Ausführungsformen der vorliegenden Erfindung das Paket basierend auf den gespeicherten Analyseregeln und hat daher eine bessere Allgemeingültigkeit.The parser provided in accordance with the embodiments of the present invention is implemented based on a hardware logic device. Compared with the software-based parser, the hardware-based parser proposed according to the embodiments of the present invention improves the analysis efficiency and reduces the development cost of the parser. In addition, the parser according to embodiments of the present invention analyzes the packet based on the stored analysis rules, and therefore has better generality.

Kurzbeschreibung der ZeichnungenBrief description of the drawings

1 ist ein schematisches Blockdiagramm, welches die Struktur eines Parsers gemäß einer Ausführungsform der vorliegenden Erfindung zeigt. 1 Fig. 10 is a schematic block diagram showing the structure of a parser according to an embodiment of the present invention.

2 ist ein schematisches Blockdiagramm, welches die innere Struktur und das Prinzip der Implementierung eines Paketanalyse-Moduls 101 des in 1 dargestellten Parsers zeigt. 2 Figure 3 is a schematic block diagram illustrating the internal structure and principle of implementing a packet analysis module 101 of in 1 shown parser shows.

3 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten main_proc Steuereinheit 201 zeigt. 3 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated main_proc control unit 201 shows.

4 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten pars_term_proc Steuereinheit 202 zeigt. 4 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 represented pars_term_proc control unit 202 shows.

5 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten match_first_proc Steuereinheit 203 zeigt. 5 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated match_first_proc control unit 203 shows.

6 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten match_follow_proc Steuereinheit 204 zeigt. 6 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated match_follow_proc control unit 204 shows.

Detaillierte Beschreibung der ErfindungDetailed description of the invention

Die vorliegende Erfindung wird im Folgenden im Einzelnen beschrieben, bezugnehmend auf die beigefügten Zeichnungen und Ausführungsformen.The present invention will be described in detail below with reference to the accompanying drawings and embodiments.

In den Ausführungsformen der vorliegenden Erfindung ist der Parser basierend auf einem Hardware Logikbaustein implementiert, wodurch die Analyseeffizienz des Parsers verbessert wird, die Kosten des Parsers gesenkt werden und ein Parser mit einer besseren Allgemeingültigkeit bereitgestellt wird.In the embodiments of the present invention, the parser is implemented based on a hardware logic device, which improves the parser's parsing efficiency, reduces the cost of the parser, and provides a parser with better generality.

Im Folgenden ist eine Ausführungsform dargelegt, um die vorliegenden Erfindung weiter zu beschreiben.In the following, an embodiment is set forth to further describe the present invention.

1 ist schematisches Blockdiagramm, welches die Struktur des Parsers gemäß einer Ausführungsform der vorliegenden Erfindung zeigt. Der Parser umfasst: Ein Paketanalyse-Modul 101 bzw. ein Modul zur Analyse von Paketen, ein Analyseregel-Speichermodul 102 bzw. ein Modul zum Speichern von Analyseregeln, ein derzeitig analysiertes Paket-Speichermodul 103 bzw. ein Modul zum Speichern des derzeitig analysierten Paketes und ein Analyseergebnis-Speichermodul 104 bzw. ein Modul zur Speicherung des Analyseergebnisses. 1 Fig. 10 is a schematic block diagram showing the structure of the parser according to an embodiment of the present invention. The parser includes: A packet analysis module 101 or a parcel analysis module, an analysis rule storage module 102 or a module for storing analysis rules, a currently analyzed packet memory module 103 or a module for storing the currently analyzed packet and an analysis result storage module 104 or a module for storing the analysis result.

Das Analyseregel-Speichermodul 102 speichert einen Regelbaum bzw. einen Entscheidungsbaum, erstellt auf Basis der ABNF Regeln, wobei dem Regelbaum keine Werte zugewiesen sind. Die Knoten des Regelbaumes werden üblicherweise gespeichert, um dem Paketanalyse-Modul 101 zu ermöglichen, alle Knoten des Regelbaumes auf einmal auszulesen.The analysis rule memory module 102 stores a rule tree or decision tree based on the ABNF rules, with no values assigned to the rule tree. The nodes of the rule tree are usually stored to the packet analysis module 101 to allow all nodes of the rule tree to be read out at once.

In der vorliegenden Ausführungsform kann der in dem Analyseregel-Speichermodul 102 gespeicherte Regelbaum basierend auf ABNF Regeln generiert werden gemäß der folgenden Methode:

  • (1) Vereinfache jede ABNF Regel, d. h. vereinfache die Beschreibung der ABNF Regel, so dass die ABNF Regel keine komplexen Strukturen, wie zum Beispiel stufenweise Alternativen, Sequenzgruppen oder optionale Sequenzen enthält. Die vereinfachte ABNF Regel kann dann in einer Regeltabelle gespeichert werden. Jeder Eintrag in der Regeltabelle entspricht einer vereinfachten ABNF Regel. Das detaillierte Verfahren der Vereinfachung umfasst: Füge für jede ABNF Regel einen Eintrag in die Regeltabelle (beispielsweise eine Hash Tabelle) hinzu; Für eine ABNF Regel, welche eine stufenweise Alternative enthält, füge den Inhalt der stufenweisen Alternative zu der ABNF Regel hinzu und aktualisiere die Einträge in der Regeltabelle; Für eine ABNF Regel, welche eine Sequenzgruppe enthält, definiere den Inhalt der Sequenzgruppe als eine neue ABNF Regel, ersetze den Inhalt der Sequenzgruppe der ursprünglichen ABNF Regel durch die neue ABNF Regel und wiederhole diesen Vorgang, bis die neue ABNF Regel keine Sequenzgruppe mehr enthält; Für eine ABNF Regel, welche eine optionale Sequenz enthält, definiere den Inhalt der optionalen Sequenz als neue ABNF Regel, ersetze den Inhalt der optionalen Sequenz der ursprünglichen ABNF Regel durch die neue ABNF Regel und wiederhole diesen Vorgang, bis die neue ABNF Regel keine optionale Sequenz mehr enthält.
  • (2) Erstelle den Regelbaum basierend auf der Regeltabelle. Wähle insbesondere eine Regel in der Regeltabelle als Wurzel (Hauptknoten) aus, generiere rekursiv den entsprechenden Regelbaum basierend auf der Wurzel. Jede Verzweigung des Regelbaumes speichert eine maximale Anzahl von bei der ABNF definierten Abgleichzeiten.
  • (3) Berechne ein First Terminals Set und eine Follow Terminals Set für jede Verzweigung des Regelbaumes gemäß des LL (1) Algorithmus und speichere eine First Terminals Set Liste und eine Follow Terminals Set Liste.
In the present embodiment, in the analysis rule memory module 102 stored rule tree based on ABNF rules can be generated according to the following method:
  • (1) Simplify every ABNF rule, ie simplify the description of the ABNF rule so that the ABNF rule does not contain complex structures, such as stepwise alternatives, sequence groups, or optional sequences. The simplified ABNF rule can then be stored in a rules table. Each entry in the rules table corresponds to a simplified ABNF rule. The detailed procedure of simplification includes: For each ABNF rule, add an entry to the rules table (for example, a hash table); For an ABNF rule containing a staged alternative, add the content of the staged alternative to the ABNF rule and update the entries in the rules table; For an ABNF rule containing a sequence group, define the content of the sequence group as a new ABNF rule, replace the content of the sequence group of the original ABNF rule with the new ABNF rule and repeat this process until the new ABNF rule no longer contains a sequence group; For an ABNF rule that contains an optional sequence, define the content of the optional sequence as a new ABNF rule, replace the content of the optional sequence of the original ABNF rule with the new ABNF rule and repeat this process until the new ABNF rule does not have an optional sequence contains more.
  • (2) Create the rule tree based on the rule table. In particular, select a rule in the rules table as root (main node), recursively generate the appropriate rule tree based on the root. Each branch of the rule tree stores a maximum number of matching times defined at the ABNF.
  • (3) Compute a First Terminals Set and a Follow Terminals Set for each branch of the rule tree according to the LL (1) Algorithm and save a First Terminals Set List and a Follow Terminals Set List.

Das in dem derzeitig analysiertes Paket-Speichermodul 103 gespeicherte Paket kann ordnungsgemäß in der Form von Bytes gespeichert sein.That in the currently parsed packet storage module 103 stored package may be properly stored in the form of bytes.

Das Paketanalyse-Modul 101 liest eine Zeichenfolge des Pakets von dem derzeitig analysiertes Paket-Speichermodul 103, erhält den Regelbaum von dem Analyseregel-Speichermodul 102, bestimmt Werte für den Regelbaum mit der Zeichenfolge des Pakets, d. h. durch Analyse des Pakets, um einen mit Werten versehenen Regelbaum zu generieren, und gibt den mit Werten versehenen Regelbaum als Analyseergebnis an das Analyseergebnis-Speichermodul 104 zur Speicherung aus.The packet analysis module 101 reads a string of the packet from the currently parsed parcel storage module 103 , receives the rule tree from the analysis rule storage module 102 , determines values for the rule tree with the string of the package, ie, by analyzing the package to generate a valued rule tree, and outputs the valued rule tree as an analysis result to the analysis result storage module 104 for storage.

Diese Ausführungsform basiert auf dem ABNF Parser und führt die Analyse durch Ausnutzen der ABNF Regeln durch und ist anwendbar auf verschiedene ABNF basierte Anwendungen, beispielsweise die SIP und Extensibel Markup Language (XML). Daher hat diese Ausführungsform eine bessere Allgemeingültigkeit.This embodiment is based on the ABNF parser and performs the analysis by exploiting the ABNF rules and is applicable to various ABNF based applications such as the SIP and Extensible Markup Language (XML). Therefore, this embodiment has a better generality.

Das Paketanalyse-Modul 101, welches in der vorliegenden Erfindung als Kernkomponente dient, kann mittels eines Field Programmable Gate Array (FPGA) oder eines Complex Programmable Logical Device (CPLD) implementiert werden. Die Implementierung des Paketanalyse-Moduls 101 wird im folgenden ausführlich beschrieben.The packet analysis module 101 which serves as the core component in the present invention may be implemented by means of a Field Programmable Gate Array (FPGA) or a Complex Programmable Logical Device (CPLD). The implementation of the packet analysis module 101 will be described in detail below.

2 ist ein schematisches Blockdiagramm, welches die innere Struktur und das Prinzip der Implementierung eines Paketanalyse-Moduls 101 des in 1 dargestellten Parsers zeigt. Das Paketanalyse-Modul gemäß dieser Ausführungsform umfasst vier Einheiten: Eine main_proc Steuereinheit 201, drei sub_proc Steuereinheiten umfassend eine parse_term_proc Steuereinheit 202, eine match_first_proc Steuereinheit 203 und eine match_follow_proc Steuereinheit 204. Die vier Einheiten des Paketanalyse-Modul 101 werden jeweils mittels Zustandsmaschinen implementiert. 2 Figure 3 is a schematic block diagram illustrating the internal structure and principle of implementing a packet analysis module 101 of in 1 shown parser shows. The packet analysis module according to this embodiment comprises four units: a main_proc control unit 201 , three sub_proc control units comprising a parse_term_proc control unit 202 , a match_first_proc control unit 203 and a match_follow_proc control unit 204 , The four units of the packet analysis module 101 are each implemented by means of state machines.

Die main_proc Steuereinheit 201 regelt die Initiierung der parse_term_proc Steuereinheit 202, der match_first_proc Steuereinheit 203 und der match_follow_proc Steuereinheit 204, um deren jeweils relevante Funktionen auszuführen.The main_proc control unit 201 controls the initiation of the parse_term_proc control unit 202 , the match_first_proc control unit 203 and the match_follow_proc control unit 204 to perform their respective relevant functions.

Die main_proc Steuereinheit 201 startet bei externem Analyse-Kontrollsignal. Wenn die Bedingung zur Initiierung einer bestimmten sub_proc Steuereinheit erfüllt ist, so geht die Zustandsmaschine der main_proc Steuereinheit 201 in einen Zustand entsprechend der sub_proc Steuereinheit über und sendet ein Signal an die sub_proc Steuereinheit, um die sub_proc Steuereinheit zu initiieren. Nachdem die Verarbeitung der sub_proc Steuereinheit beendet ist, übermittelt die sub_proc Steuereinheit das Verarbeitungsresultat an die main_proc Steuereinheit 201 zurück. Die main_proc Steuereinheit 201 gibt ein Erfolgs- oder Fehlersignal als Analyseergebnis an das externe Netzwerk aus.The main_proc control unit 201 starts with external analysis control signal. If the condition for initiating a particular sub_proc controller is met, then the state machine of the main_proc controller goes 201 to a state corresponding to the sub_proc control unit and sends a signal to the sub_proc control unit to initiate the sub_proc control unit. After the processing of the sub_proc control unit is completed, the sub_proc control unit transmits the processing result to the main_proc control unit 201 back. The main_proc control unit 201 outputs a success or error signal as an analysis result to the external network.

Die parse_term_proc Steuereinheit 202 ist dahingehend ausgestaltet, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden, im Falle, dass ein Anfangsknoten eines stacks (Stapelspeicher bzw. Kellerspeicher) ein Endknoten ist, und die main_proc Steuereinheit 201 nach der Analyse des Endknotens zu informieren.The parse_term_proc control unit 202 is designed to be under the control of the main_proc control unit 201 in case a start node of a stack (stack) is an end node, and the main_proc control unit 201 to inform after the analysis of the end node.

Die match_first_proc Steuereinheit 203 ist dahingehend ausgestaltet, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden, im Falle, dass der Anfangsknoten eines stacks kein Endknoten ist und zu einem First Terminals Set gehört, und die main_proc Steuereinheit 201 zu informieren nach der Entscheidung, ob ein derzeitiges Zeichen zu dem First Terminals Set gehört, durch Abgleich des derzeitigen Zeichens mit allen Zeichen des First Terminals Sets.The match_first_proc control unit 203 is designed to be under the control of the main_proc control unit 201 in case the starting node of a stack is not an end node and belongs to a First Terminals set, and the main_proc control unit 201 after reconciliation, after deciding whether a current character belongs to the First Terminals Set the current character with all the characters of the First Terminal Set.

Die match_follow_proc Steuereinheit 204 ist dahingehend ausgestaltet, unter der Kontrolle der main_proc Steuereinheit 201 gestartet zu werden, im Falle, dass der Anfangsknoten eines stacks kein Endknoten ist und zu einem Follow Terminals Set gehört, und die main_proc Steuereinheit 201 zu informieren nach der Entscheidung, ob ein derzeitiges Zeichen zu dem Follow Terminals Set gehört durch Abgleich des derzeitigen Zeichens mit allen Zeichen des Follow Terminals Sets.The match_follow_proc control unit 204 is designed to be under the control of the main_proc control unit 201 in case the starting node of a stack is not an end node and belongs to a Follow Terminals set, and the main_proc control unit 201 to inform after deciding whether a current character belongs to the Follow Terminals Set by matching the current character with all characters of the Follow Terminal Sets.

Die Zustände und das detaillierte Verfahren der main_proc Steuereinheit 201 und der drei sub_proc Steuereinheiten 202, 203 und 204 werden im Folgenden jeweils ausführlich beschrieben.The states and the detailed procedure of the main_proc control unit 201 and the three sub_proc control units 202 . 203 and 204 will be described in detail below.

3 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten main_proc Steuereinheit 201 zeigt. 3 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated main_proc control unit 201 shows.

Die main_proc Steuereinheit 201 fungiert als Hauptprozess und wird durch eine Anstiegkante eines externen Taktgebers angesteuert. Die main_proc Steuereinheit 201 umfasst die folgenden Zustände wie in 3 dargestellt:
IDLE, INIT, PARSE_LOOP, REPEAT_MAX, TERM_MATCH, IN_FIRST, FIRSTSUB, ALLSUB, CHOOSESUB, NEXTSUB0, NEXTSUB1, GETSUB, JUDGE_FOLLOW, IN_FOLLOW, NEXTRULE und END_PARSE.The main_proc control unit 201 acts as a main process and is driven by a rising edge of an external clock. The main_proc control unit 201 includes the following states as in 3 shown:
IDLE, INIT, PARSE_LOOP, REPEAT_MAX, TERM_MATCH, IN_FIRST, FIRSTSUB, ALLSUB, CHOOSESUB, NEXTSUB0, NEXTSUB1, GETSUB, JUDGE_FOLLOW, IN_FOLLOW, NEXTRULE, and END_PARSE.

Die Zustandsübergänge der main_proc Steuereinheit 201 umfassen:
Sobald eine Anstiegkante eines externen Steuersignals detektiert wird, so geht die Zustandsmaschine der main_proc Steuereinheit 201 vom IDLE Zustand in den INIT Zustand über, um die main_proc Steuereinheit 201 zu initialisieren, und legt die Wurzel des Regelbaumes in dem Stark ab. Der Stack speichert während des Hauptprozesses alle Knoten des Regelbaumes. Nachdem die Initialisierung durchgeführt wurde, geht die Zustandsmaschine der main_proc Steuereinheit 201 in den PARSE_LOOP Zustand über.The state transitions of the main_proc control unit 201 include:
As soon as a rising edge of an external control signal is detected, the state machine of the main_proc control unit goes on 201 from the IDLE state to the INIT state via to the main_proc control unit 201 and initialize the root of the rule tree in the strong. The stack saves all nodes of the rule tree during the main process. After the initialization has been performed, the state machine of the main_proc control unit goes 201 in the PARSE_LOOP state via.

Im PARSE_LOOP Zustand liest die main_proc Steuereinheit 201 jeweils einen Knoten nach dem anderen aus, beginnend beim obersten Element des Stacks, um die Analyse des Pakets zu starten. Jedes Mal, wenn ein Knoten ausgelesen wird, geht die Zustandsmaschine der main_proc Steuereinheit 201 einmalig in den REPEAT_MAX Zustand über. Im Fall, dass kein nicht abgeglichenes Zeichen vorhanden ist und dass der derzeitige Knoten die Wurzel ist, geht die Zustandsmaschine der main_proc Steuereinheit 201 in den END_PARSE Zustand über.In the PARSE_LOOP state, the main_proc controller reads 201 one node at a time, starting at the top of the stack to start parsing the packet. Each time a node is read, the state machine of the main_proc control unit goes 201 once in the REPEAT_MAX state. In the event that there is no unmatched character and the current node is the root, the state machine of the main_proc controller goes 201 in the END_PARSE state via.

Im REPEAT_MAX Zustand entscheidet die main_proc Steuereinheit 201, ob die Abgleichzeiten der Knoten REPEAT_MAX erreicht haben; falls die Abgleichzeiten der Knoten REPEAT_MAX erreicht haben, geht die main_proc Steuereinheit 201 in den PARSE_LOOP Zustand zurück und bereitet den Abgleich des nächsten Knotens vor; andernfalls bestimme die Art des Anfangsknotens des Stacks und lege fest, in eine entsprechende sub_proc Steuereinheit überzugehen, je nach der Art des Anfangsknotens; hierbei wird der Stack verwendet, um einen Analysefortschritt des Regelbaumes zu verfolgen. Wie in 2 dargestellt ist das detaillierte Verfahren folgendermaßen.In the REPEAT_MAX state, the main_proc control unit decides 201 whether the matching times of the nodes have reached REPEAT_MAX; if the matching times of the nodes have reached REPEAT_MAX, the main_proc control unit goes 201 returns to the PARSE_LOOP state and prepares to match the next node; otherwise, determine the type of stack initial node and commit to transition to a corresponding sub_proc controller, depending on the type of initial node; Here, the stack is used to track an analysis progress of the rule tree. As in 2 The detailed procedure is shown as follows.

Falls der Anfangsknoten ein Endknoten ist, d. h. ein Blatt der vereinfachten ABNF Regel, setze ein match_term signal auf ein hohes Spannungslevel, um die parse_term_proc Steuereinheit 202 zu initiieren. Falls ein match_term_result Signal auf ein hohes Spannungslevel wechselt, gehe in den TERM_MATCH Zustand über und setze das match_term Signal auf ein niedriges Spannungslevel, um die parse_term_proc Steuereinheit 202 zu stoppen; kehre in den PARSE_LOOP Zustand zurück;
Falls der Anfangsknoten kein Endknoten ist, so setze das match_first Signal auf ein hohes Spannungslevel, um den match_first_proc Prozess zu initiieren, wobei das detaillierte Verfahren des match_first_proc Prozesses folgendermaßen ist:
Falls ein match_first_success Signal auf einem hohen Spannungslevel ist, so zeigt es an, dass das derzeitige Zeichen in dem First Terminals Set des Knotens ist; die Zustandsmaschine der main_proc Steuereinheit 201 geht in den FIRSTSUB Zustand über und setzt das match_first Signal auf ein niedriges Spannungslevel, um den match_first_proc Prozess zu stoppen, wählt einen korrekten Unterknoten aus und legt den Unterknoten im Stack ab und kehrt in den den PARSE_LOOP Zustand zurück, gemäß des First Terminals Set des Unterknotens. Insbesondere, detektiere jeden Unterknoten gemäß des First Terminals Set des Unterknotens; falls der Inhalt des derzeitigen Paktes in dem First Terminals Set eines bestimmten Unterknotens existiert, so legt die Zustandsmaschine der main_proc Steuereinheit 201 den Unterknoten im Stack zum Abgleich ab.If the starting node is an end node, ie a leaf of the simplified ABNF rule, set a match_term signal to a high voltage level to the parse_term_proc control unit 202 to initiate. If a match_term_result signal goes to a high voltage level, go to the TERM_MATCH state and set the match_term signal to a low voltage level to the parse_term_proc control unit 202 to stop; return to the PARSE_LOOP state;
If the starting node is not an end node, set the match_first signal to a high voltage level to initiate the match_first_proc process, with the detailed procedure of the match_first_proc process being as follows:
If a match_first_success signal is at a high voltage level, it indicates that the current character is in the first terminal set of the node; the state machine of the main_proc control unit 201 enters the FIRSTSUB state and sets the match_first signal to a low voltage level to stop the match_first_proc process, selects a correct subnode and drops the subnode in the stack and returns to the PARSE_LOOP state according to the first terminal set of under node. In particular, detect each subnode according to the first terminal set of the subnode; if the content of the current pact exists in the first terminal set of a particular sub-node, then the state machine puts the main_proc control unit 201 the subnode in the stack for matching.

Im FIRST_SUB Zustand entscheidet die Zustandsmaschine der main_proc Steuereinheit 201, ob ein Unterknoten vorliegt. Falls kein Unterknoten vorliegt, so geht die Zustandsmaschine der main_proc Steuereinheit 201 in den CHOOSESUB Zustand über; andernfalls geht sie in den ALLSUB Zustand über. Der ALLSUB Zustand zeigt an, das alle Unterknoten verarbeitet wurden, und die Zustandsmaschine der main_proc Steuereinheit 201 kehrt in den PARSE_LOOP Zustand zurück.In the FIRST_SUB state, the state machine of the main_proc control unit decides 201 whether a subnode exists. If there is no subnode, then the state machine of the main_proc control unit goes 201 in the CHOOSESUB state over; otherwise it will go into the ALLSUB state. The ALLSUB state indicates that all subnodes have been processed and the state machine of the main_proc control unit 201 returns to the PARSE_LOOP state.

Im CHOOSESUB Zustand liest die Zustandsmaschine der main_proc Steuereinheit 201 der Reihe nach jeden Unterknoten aus und entscheidet, ob der Unterknoten ein korrekter Unterknoten gemäß des First Terminals Set des Unterknotens ist. Das Ziel dieser Entscheidung ist es, die Effizienz zu verbessern. Andernfalls kann die Zustandsmaschine der main_proc Steuereinheit 201 versuchen, jeden Unterknoten abzugleichen bis der korrekte Unterknoten gefunden wurde oder alle Versuche fehlgeschlagen sind; falls der Unterknoten ein korrekter Unterknoten ist, so gehe in den GETSUB Zustand über; andernfalls gehe in den NEXTSUB0 Zustand über.In the CHOOSESUB state, the state machine reads the main_proc control unit 201 in sequence each subnode and decides whether the subnode is a correct subnode according to the first terminal set of the subnode. The goal of this decision is to improve efficiency. Otherwise, the state machine may be the main_proc control unit 201 try to match each subnode until the correct subnode is found or all attempts have failed; if the subnode is a correct subnode is, so go into the GETSUB state; otherwise go to the NEXTSUB0 state.

Im NEXTSUB0 Zustand liest die Zustandsmaschine der main_proc Steuereinheit 201 einen nächsten Unterknoten 0 aus und bestimmt, ob der Unterknoten ein korrekter Unterknoten ist; falls der Unterknoten ein korrekter Unterknoten ist, gehe in den GETSUB Zustand über. Andernfalls gehe in den NEXTSUB1 Zustand über.In the NEXTSUB0 state, the state machine reads the main_proc control unit 201 a next subnode 0 and determines if the subnode is a correct subnode; if the subnode is a correct subnode, go to the GETSUB state. Otherwise go to the NEXTSUB1 state.

Im NEXTSUB1 Zustand liest die Zustandsmaschine der main_proc Steuereinheit 201 den nächsten Unterknoten1 aus und entscheidet, ob der Unterknoten ein korrekter Unterknoten ist; im Fall, dass der Unterknoten ein korrekter Unterknoten, geht die Zustandsmaschine der main_proc Steuereinheit 201 in den GETSUB Zustand über; andernfalls kehrt sie zum PARSE_LOOP Zustand zurück.In the NEXTSUB1 state, the state machine reads the main_proc controller 201 determines the next sub-node 1 and decides whether the sub-node is a correct sub-node; in case the subnode is a correct subnode, the state machine of the main_proc control unit goes 201 in the GETSUB state about; otherwise, it returns to the PARSE_LOOP state.

Im GETSUB Zustand überführt die Zustandsmaschine der main_proc Steuereinheit 201 den ausgewählten Unterknoten in den Stack und kehrt zum PARSE_LOOP Zustand zurück.In the GETSUB state, the state machine transfers the main_proc control unit 201 the selected subnode in the stack and returns to the PARSE_LOOP state.

Falls ein match_first_fail Signal auf einem hohem Spannungslevel ist, so zeigt es an, dass das derzeitige Zeichen nicht in dem First Terminals Set des Unterknotens ist; die Zustandsmaschine der main_proc Steuereinheit 201 geht in den JUDGE_FOLLOW Zustand über.If a match_first_fail signal is at a high voltage level, it indicates that the current character is not in the first terminal set of the subnode; the state machine of the main_proc control unit 201 goes into the JUDGE_FOLLOW state.

Im JUDGE_FOLLOW setzt die Zustandsmaschine der main_proc Steuereinheit 201 das match_follow Signal auf ein hohes Spannungslevel, um den match_follow_proc Vorgang zu initiieren und wartet auf ein match_follow_success Signal oder auf ein match_follow_fail Signal, um zu entscheiden, ab der nächste Unterknoten abgeglichen werden soll; falls ein nachfolgendes Zeichen in dem Follow Terminals Set des Knotens ist, gehe in den IN_FOLLOW Zustand über; andernfalls gehe in den NEXTRULE Zustand über.In JUDGE_FOLLOW the state machine sets the main_proc control unit 201 sets the match_follow signal to a high voltage level to initiate the match_follow_proc process and waits for a match_follow_success signal or a match_follow_fail signal to decide to match the next subnode; if there is a trailing character in the node's Follow Terminals Set, go to the IN_FOLLOW state; otherwise go to the NEXTRULE state.

Der NEXTRULE Zustand zeigt an, das die Detektion des Follow Terminals Sets fehlgeschlagen ist. Er zeigt an, dass die Analyse des Pakets fehlgeschlagen ist, d. h. dass das Paket nicht der ABNF Syntax entspricht; die Zustandsmaschine der main_proc Steuereinheit 201 geht in den END_PARSE Zustand über, um die Analyse zu beenden und antwortet mit einem fehlgeschlagenen Analyse-Signal (parsing fail signal).The NEXTRULE state indicates that the detection of the Follow Terminal Set failed. It indicates that the parse has failed to parse, ie that the parcel does not conform to the ABNF syntax; the state machine of the main_proc control unit 201 goes into the END_PARSE state to end the analysis and responds with a parsing fail signal.

Im IN_FOLLOW Zustand im Fall, dass der Abgleich des Knotens mit dem Follow Terminals Set erfoglreich war, kehre zum PARSE_LOOP Zustand zurück, nimm den obersten Knoten vom Stack heraus und gleich einen neuen Anfangsknoten, d. h. den nächsten Knoten, ab.In the IN_FOLLOW state, if the node had been reconciled with the Follow Terminals Set, return to the PARSE_LOOP state, take the top node out of the stack, and immediately create a new start node, i. H. the next node, from.

4 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten pars_term_proc Steuereinheit 201 zeigt. Die parse_term_proc Steuereinheit 202 wird durch eine Anstiegkante des Taktgebers angesteuert und wird für den Abgleich eines Endknotens verwendet, wobei die entsprechenden Zustände umfassen:
IDLE, START, TERM_STRING, TERM_CODE_LIST, TERM_SUCCES und TERM_FAIL. 4 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 represented pars_term_proc control unit 201 shows. The parse_term_proc control unit 202 is driven by a rising edge of the clock and is used to align an end node, the corresponding states comprising:
IDLE, START, TERM_STRING, TERM_CODE_LIST, TERM_SUCCES and TERM_FAIL.

Bezugnehmend auf 4 im Fall, dass das match_term Signal durch die main_proc Steuereinheit 201 auf ein hohes Spannungslevel gesetzt ist, so geht die Zustandsmaschine der parse_term_proc Steuereinheit 202 vom IDLE Zustand zum START Zustand über. Im START Zustand liest die Zustandsmaschine der parse_term_proc Steuereinheit 202 ein Byte nach dem anderen des Pakets aus von dem derzeitig analysierten Paket-Speichermodul 103, bestimmt die Kodierungsart des Pakets und geht in den entsprechenden Zustand gemäß der Kodierungsart des Pakets über.Referring to 4 in the case that the match_term signal is passed through the main_proc control unit 201 is set to a high voltage level, so goes the state machine of the parse_term_proc control unit 202 from IDLE state to START state via. In the START state, the state machine reads the parse_term_proc control unit 202 one byte after the other of the packet from the currently analyzed packet memory module 103 , determines the encoding type of the packet and changes to the corresponding state according to the encoding type of the packet.

Falls die Kodierungsart des Pakets eine Zeichenfolge ist, so geht die Zustandsmaschine der parse_term_proc Steuereinheit 202 in den TERM_STRING Zustand über zum Abgleich jedes Zeichens des Pakets; falls die Zeichenfolge nur ein einzelnes Zeichen enthält oder einen ASCII Code eines einzelnen Zeichens, bestimmt die Zustandsmaschine sofort, ob der Abgleich erfolgreich war, und geht je nach Abgleichergebnis in den TERM_SUCCESS Zustand oder den TERM_FAIL Zustand über.If the encoding type of the packet is a string, the state machine of the parse_term_proc control unit goes 202 in the TERM_STRING state, over to match each character of the packet; if the string contains only a single character or an ASCII code of a single character, the state machine immediately determines whether the match was successful and, depending on the match result, transitions to the TERM_SUCCESS state or the TERM_FAIL state.

Falls die Kodierungsart des Pakets eine Code Liste ist, geht die Zustandsmaschine der parse_term_proc Steuereinheit 202 in den TERM_CODE_LIST Zustand zum Abgleich jedes einzelnen Zeichens des Pakets.If the encoding type of the packet is a code list, the state machine of the parse_term_proc control unit goes 202 in the TERM_CODE_LIST state to match each character of the package.

Wenn der Abgleich im TERM_STRING Zustand oder im TERM_CODE_LIST Zustand beendet ist, geht die Zustandsmaschine der parse_term_proc Steuereinheit 202 je nach Abgleichergebnis in den TERM_SUCCESS Zustand oder den TERM_FAIL Zustand über und setzt das term_match_result Signal auf ein hohes Spannungslevel, um die Zustandsmaschine der main_proc Steuereinheit 201 zu informieren.When the adjustment is completed in the TERM_STRING state or in the TERM_CODE_LIST state, the state machine of the parse_term_proc control unit goes 202 depending on the adjustment result in the TERM_SUCCESS state or the TERM_FAIL state and sets the term_match_result signal to a high voltage level to the state machine of the main_proc control unit 201 to inform.

Wenn die Zustandsmaschine der main_proc Steuereinheit 201 das match_term Signal auf ein niedriges Spannungslevel setzt, so kehrt der Zustand der parse_term_proc Steuereinheit 202 in den IDLE Zustand zurück und löscht das term_match_result Signal, um auf den nächsten Abgleich zu warten.If the state machine of the main_proc control unit 201 If the match_term signal is set to a low voltage level, the state of the parse_term_proc control unit returns 202 returns to the IDLE state and clears the term_match_result signal to wait for the next alignment.

5 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten match_first_proc Steuereinheit 201 zeigt. Die match_first_proc Steuereinheit 203 wird durch eine Anstiegkante angesteuert und wird für den Vergleich, ob das derzeitige Zeichen in dem First Terminals Set des Knotens existiert oder nicht, verwendet. Die entsprechenden Zuständen umfassen:
IDLE, LIST_LOOP, FIRST_STRING, FIRST_CODE_LIST, FIRST_SUCCESS und FIRST_FAIL. 5 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated match_first_proc control unit 201 shows. The match_first_proc control unit 203 is driven by a rising edge and is used to compare whether or not the current character exists in the first terminal set of the node. The corresponding states include:
IDLE, LIST_LOOP, FIRST_STRING, FIRST_CODE_LIST, FIRST_SUCCESS and FIRST_FAIL.

Bezugnehmend auf 5 im Fall, dass das match_first Signal durch die main_proc Steuereinheit 201 auf ein hohes Spannungslevel gesetzt ist, so geht die Zustandsmaschine der match_first_proc Steuereinheit 203 vom IDLE Zustand zum LIST_LOOP Zustand über. Im LIST_LOOP Zustand bestimmt die Zustandsmaschine der match_first_proc Steuereinheit 203 die Kodierungsart des Pakets und führt die entsprechenden Verfahrensschritte gemäß der Kodierungsart durch.Referring to 5 in the event that the match_first signal passes through the main_proc control unit 201 is set to a high voltage level, so the state machine of the match_first_proc control unit goes 203 from IDLE state to LIST_LOOP state via. In the LIST_LOOP state, the state machine determines the match_first_proc control unit 203 the coding type of the packet and performs the corresponding process steps according to the coding type.

Falls die Kodierungsart des Pakets eine Zeichenfolge ist, so geht die Zustandsmaschine der match_first_proc Steuereinheit 203 in den FIRST_STRING Zustand über zum Abgleich jedes Zeichens des Pakets.If the encoding type of the packet is a string, the state machine of the match_first_proc control unit goes 203 in the FIRST_STRING state via to match each character of the packet.

Falls die Zeichenfolge nur ein einzelnes Zeichen enthält oder einen ASCII Code eines einzelnen Zeichens, bestimmt die Zustandsmaschine sofort, ob der Abgleich erfolgreich war, und geht je nach Abgleichergebnis in den FIRST_SUCCESS Zustand oder den FIRST_FAIL Zustand über.If the string contains only a single character or an ASCII code of a single character, the state machine immediately determines if the match was successful and goes into the FIRST_SUCCESS state or the FIRST_FAIL state depending on the match result.

Falls die Kodierungsart des Pakets eine Code Liste ist, geht die Zustandsmaschine der match_first_proc Steuereinheit 203 in den FIRST_CODE_LIST Zustand zum Abgleich jedes einzelnen Zeichens des Pakets.If the encoding type of the packet is a code list, the state machine of the match_first_proc control unit goes 203 into the FIRST_CODE_LIST state to match each character of the package.

Wenn der Abgleich im FIRST_STRING Zustand durchgeführt wurde, geht die Zustandsmaschine der match_first_proc Steuereinheit 203 je nach Abgleichergebnis in den FIRST_SUCCESS Zustand oder den FIRST_FAIL Zustand über.If the adjustment was done in the FIRST_STRING state, the state machine of the match_first_proc control unit goes 203 depending on the adjustment result in the FIRST_SUCCESS state or the FIRST_FAIL state via.

Wenn der Abgleich im FIRST_CODE_LIST Zustand durchgeführt wurde, geht die Zustandsmaschine der match_first_proc Steuereinheit 203 je nach Analyseergebnis in den FIRST_SUCCESS Zustand oder den FIRST_FAIL Zustand über, kehrt in den LIST_LOOP Zustand zurück zum Abgleich des Inhalts einer nächsten Liste, so lange bis ein passendes First Terminals Set Element gefunden wurde oder das Ende der Liste erreicht wurde.If the match was done in the FIRST_CODE_LIST state, the state machine of the match_first_proc control unit goes 203 depending on the analysis result in the FIRST_SUCCESS state or the FIRST_FAIL state, the system returns to the LIST_LOOP state to compare the contents of a next list, until a suitable First Terminals Set element has been found or the end of the list has been reached.

Falls kein passendes First Terminals Set Element gefunden wurde, geht die Zustandsmaschine der match_first_proc Steuereinheit 203 in den FIRST_FAIL Zustand über; die Zustandsmaschine der match_first_proc Steuereinheit 203 setzt jeweils das first_match Signal und das first_match_fail Signal auf ein hohes Spannungslevel, um die Zustandsmaschine der main_proc Steuereinheit 201 über den FIRST_SUCCESS Zustand und den FIRST_FAIL Zustand zu informieren.If no matching First Terminals Set element was found, the state machine of the match_first_proc control unit goes 203 in the FIRST_FAIL state via; the state machine of the match_first_proc control unit 203 sets each of the first_match signal and the first_match_fail signal to a high voltage level to the state machine of the main_proc control unit 201 to inform about the FIRST_SUCCESS state and the FIRST_FAIL state.

Wenn die Zustandsmaschine der main_proc Steuereinheit 201 das match_first Signal auf ein niedriges Spannungslevel setzt, so kehrt die Zustandsmaschine der match_first_proc Steuereinheit 203 in den IDLE Zustand zurück und löscht das match_first_success Signal oder das match_first_fail Signal, um auf den nächsten Abgleich zu warten.If the state machine of the main_proc control unit 201 If the match_first signal is set to a low voltage level, the state machine of the match_first_proc control unit returns 203 returns to the IDLE state and clears the match_first_success signal or match_first_fail signal to wait for the next alignment.

6 ist ein schematisches Blockdiagramm, welches eine Zustandsmaschine einer in 2 dargestellten match_follow_proc Steuereinheit 204 zeigt Die match_follow_proc Steuereinheit 204 wird von einer Anstiegkante angesteuert und wird dazu verwendet, um zu entscheiden, ob das derzeitige Zeichen in dem Follow Terminals Set eines Knotens existiert. Die entsprechenden Zustände umfassen:
IDLE, LIST_LOOP, FOLLOW_STRING, FOLLOW_CODE_LIST, FOLLOW_SUCCESS und FOLLOW_FAIL. 6 FIG. 12 is a schematic block diagram illustrating a state machine of an in 2 illustrated match_follow_proc control unit 204 shows The match_follow_proc control unit 204 is driven by a rising edge and is used to decide if the current character exists in the follow terminal set of a node. The corresponding states include:
IDLE, LIST_LOOP, FOLLOW_STRING, FOLLOW_CODE_LIST, FOLLOW_SUCCESS, and FOLLOW_FAIL.

Bezugnehmend auf 6 im Fall, dass das match_follow Signal durch die main_proc Steuereinheit 201 auf ein hohes Spannungslevel gesetzt ist, so geht die Zustandsmaschine der match_follow_proc Steuereinheit 204 vom IDLE Zustand zum LIST_LOOP Zustand über. Im LIST_LOOP Zustand bestimmt die Zustandsmaschine der match_follow_proc Steuereinheit 204 die Kodierungsart des Pakets und führt die entsprechenden Verfahrensschritte gemäß der Kodierungsart durch.Referring to 6 in the case of the match_follow signal through the main_proc control unit 201 is set to a high voltage level, so does the state machine of the match_follow_proc control unit 204 from IDLE state to LIST_LOOP state via. In the LIST_LOOP state, the state machine determines the match_follow_proc control unit 204 the coding type of the packet and performs the corresponding process steps according to the coding type.

Falls die Kodierungsart des Pakets eine Zeichenfolge ist, so geht die Zustandsmaschine der match_follow_proc Steuereinheit 204 in den FOLLOW_STRING Zustand über zum Abgleich jedes Zeichens des Pakets.If the encoding type of the packet is a string, the state machine of the match_follow_proc control unit goes 204 in the FOLLOW_STRING state, over to match each character of the package.

Falls die Zeichenfolge nur ein einzelnes Zeichen enthält oder einen ASCII Code eines einzelnen Zeichens, bestimmt die Zustandsmaschine sofort, ob der Abgleich erfolgreich war, und geht je nach Abgleichergebnis über in den FOLLOW_SUCCESS Zustand oder den FOLLOW_FAIL Zustand.If the string contains only a single character or an ASCII code of a single character, the state machine immediately determines if the match was successful and, depending on the match result, enters the FOLLOW_SUCCESS state or the FOLLOW_FAIL state.

Falls die Kodierungsart des Pakets eine Code Liste ist, geht die Zustandsmaschine der match_follow_proc Steuereinheit 204 in den FOLLOW_CODE_LIST Zustand zum Abgleich jedes einzelnen Zeichens des Pakets.If the encoding type of the packet is a code list, the state machine of the match_follow_proc control unit goes 204 in the FOLLOW_CODE_LIST state to match each character of the package.

Wenn der Abgleich im FOLLOW_CODE_LIST Zustand durchgeführt wurde, geht die Zustandsmaschine der match_follow_proc Steuereinheit 204 je nach Abgleichergebnis in den FOLLOW_SUCCESS Zustand oder den FOLLOW_FAIL Zustand über, oder kehrt in den LIST_LOOP Zustand zurück zum Abgleich des Inhalts einer nächsten Liste, so lange bis ein passendes Follow Terminals Set Element gefunden wurde oder das Ende der Liste erreicht wurde.If the match was done in the FOLLOW_CODE_LIST state, the state machine of the match_follow_proc control unit goes 204 depending on the adjustment result in the FOLLOW_SUCCESS state or the FOLLOW_FAIL state, or returns to the LIST_LOOP state to compare the content of a next list, until a suitable Follow Terminals Set element has been found or the end of the list has been reached.

Falls kein passendes Follow Terminals Set Element gefunden wurde, geht die Zustandsmaschine der match_follow_proc Steuereinheit 204 in den FOLLOW_FAIL Zustand über, setzt jeweils das follow_match_success Signal und das follow_match_fail Signal auf ein hohes Spannungslevel, um die Zustandsmaschine der main_proc Steuereinheit 201 über den FOLLOW_SUCCESS Zustand und den FOLLOW_FAIL Zustand zu informieren.If no matching Follow Terminals Set element was found, the state machine of the match_follow_proc control unit goes 204 in the FOLLOW_FAIL state, sets the follow_match_success signal and the follow_match_fail signal respectively to a high voltage level to the state machine of the main_proc control unit 201 to inform about the FOLLOW_SUCCESS state and the FOLLOW_FAIL state.

Wenn die Zustandsmaschine der main_proc Steuereinheit 201 das match_follow Signal auf ein niedriges Spannungslevel setzt, so kehrt die Zustandsmaschine der match_follow_proc Steuereinheit 204 in den IDLE Zustand zurück und löscht das match_follow_success Signal oder das match_follow_fail Signal, um auf den nächsten Abgleich zu warten.If the state machine of the main_proc control unit 201 If the match_follow signal is set to a low voltage level, the state machine of the match_follow_proc control unit returns 204 returns to the IDLE state and clears the match_follow_success signal or match_follow_fail signal to wait for the next alignment.

Basierend auf den genannten Zustandsmaschinen kann das Paketanalyse-Modul durch einen Hardware Logikbaustein implementiert werden, wie beispielsweise durch einen FPGA oder einen CPLD; so kann ein universeller auf ABNF basierender Syntax Parser zur Analyse eines textkodierten Protokolls implementiert werden.Based on said state machines, the packet analysis module may be implemented by a hardware logic device, such as an FPGA or a CPLD; For example, a universal ABNF-based syntax parser can be implemented to parse a text-encoded protocol.

Das vorangehend Gesagte ist nur eine bevorzugte Ausführungsform der vorliegenden Erfindung. Der Schutzumfang der vorliegenden Erfindung ist allerdings nicht auf die obige Beschreibung beschränkt. Jede Änderung oder Ersetzung innerhalb des durch die vorliegenden Erfindung offenbarten technischen Schutzbereichs, welche dem Fachmann geläufig ist, ist durch den Schutzumfang der vorliegenden Erfindung mit umfasst. Der Schutzumfang der vorliegenden Erfindung soll daher im Einklang stehen mit dem Schutzumfang, wie er durch die Ansprüche festgelegt wird.The foregoing is just one preferred embodiment of the present invention. However, the scope of the present invention is not limited to the above description. Any change or replacement within the technical scope disclosed by the present invention, which is familiar to those skilled in the art, is included within the scope of the present invention. The scope of the present invention should therefore be consistent with the scope of protection as defined by the claims.

Claims (8)

Parser zur Analyse eines textkodierten Protokolls, umfassend: ein Analyseregel-Speichermodul (102), welches dazu ausgelegt ist, Analyseregeln zur Analyse eines Pakets des textkodierten Protokolls zu speichern, wobei das Analyseregel-Speichermodul (102) dazu ausgelegt ist, einen gemäß Augmented Backus-Naur Form, ABNF, Regeln generierten Regelbaum zu speichern, wobei der Regelbaum keine stufenweise Auswahl, Sequenzgruppe oder optionale Sequenzstruktur enthält; und wobei der Regelbaum auf rekursive Weise generiert wird, indem eine Regel in dem Regelbaum als Spitze bzw. vertex verwendet wird; und ein Paketanalyse-Modul (101), welches mittels eines Logikbausteins implementiert ist und dazu ausgelegt ist, eine Zeichenfolge des Pakets zu lesen, den in dem Analyseregel-Speichermodul (102) gespeicherten Regelbaum zu erhalten, einen Wert für den Regelbaum mit der Zeichenfolge des Pakets bestimmen, um einen mit diesem Wert versehen Regelbaum zu erzeugen und den mit diesem Wert versehenen Regelbaum als ein Analyseergebnis auszugeben, wobei das Paketanalyse-Modul umfasst: eine main_proc Steuereinheit (201), die dazu ausgelegt ist, den Übergang in eine parse_term_proc Steuereinheit (202), eine match_first_proc Steuereinheit (203) und eine match_follow_proc Steuereinheit (204) jeweils zu kontrollieren basierend auf der Art eines Anfangsknotens eines Stacks; wobei Knoten des Regelbaums in dem Stack gespeichert werden; und wobei der Anfangsknoten des Stacks ein Knoten des obersten Elements des Stacks ist; wobei die parse_term_proc Steuereinheit (202) dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit (201) gestartet zu werden im Falle, dass der Anfangsknoten ein Endknoten ist und die main_proc Steuereinheit (201) nach der Analyse des Pakets zu informieren; wobei der Endknoten ein Blatt ist, d. h. ein Blatt der vereinfachten ABNF-Regel; wobei die match_first_proc Steuereinheit (203) dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit (201) gestartet zu werden im Fall, dass der Anfangsknoten kein Endknoten ist und zu einem First Terminals Set gehört, und die main_proc Steuereinheit (201) zu informieren über die Entscheidung, ob ein derzeitiges Zeichen zu dem First Terminals Set gehört oder nicht durch Abgleich des derzeitigen Zeichens mit allen Zeichen des First Terminals Set; wobei die match_follow_proc Steuereinheit (204) dazu ausgelegt ist, unter der Kontrolle der main_proc Steuereinheit (201) gestartet zu werden im Fall, dass der Anfangsknoten kein Endknoten ist und zu einem Follow Terminals Set gehört, und die main_proc Steuereinheit (201) zu informieren über die Entscheidung, ob das derzeitige Zeichen zu dem Follow Terminals Set gehört oder nicht durch Abgleich des derzeitigen Zeichens mit allen Zeichen des Follow Terminals Set.Parser for analyzing a text-coded protocol, comprising: an analysis rule memory module ( 102 ), which is adapted to store analysis rules for analyzing a packet of the text-coded protocol, wherein the analysis rule memory module ( 102 ) is adapted to store a rule tree generated in accordance with Augmented Backus-Naur Form, ABNF, rules, the rule tree containing no stepwise selection, sequence group, or optional sequence structure; and wherein the rule tree is recursively generated by using a rule in the rule tree as a vertex; and a packet analysis module ( 101 ) which is implemented by means of a logic device and is adapted to read a string of the packet which is stored in the analysis rule memory module ( 102 Determine a value for the rule tree with the string of the packet to generate a rule tree provided with this value and output the rule tree provided with this value as an analysis result, the packet analysis module comprising: a main_proc control unit (FIG. 201 ), which is adapted to transition into a parse_term_proc control unit ( 202 ), a match_first_proc control unit ( 203 ) and a match_follow_proc control unit ( 204 ) each based on the type of an initial node of a stack; wherein nodes of the rule tree are stored in the stack; and wherein the starting node of the stack is a node of the topmost element of the stack; the parse_term_proc control unit ( 202 ) is designed under the control of the main_proc control unit ( 201 ) in case the initial node is an end node and the main_proc control unit ( 201 ) after the analysis of the package; the end node being a leaf, ie a leaf of the simplified ABNF rule; the match_first_proc control unit ( 203 ) is designed under the control of the main_proc control unit ( 201 ) in case the initial node is not an end node and belongs to a First Terminals set, and the main_proc control unit ( 201 ) to inform you of the decision whether a current character belongs to the First Terminal Set or not by comparing the current character with all the characters of the First Terminal Set; the match_follow_proc control unit ( 204 ) is designed under the control of the main_proc control unit ( 201 ) in case the initial node is not an end node and belongs to a Follow Terminals set, and the main_proc control unit ( 201 ) to inform you of the decision whether the current character belongs to the Follow Terminal Set or not by comparing the current character with all the characters of the Follow Terminal Set. Parser nach Anspruch 1, wobei der Logikbaustein jeweils umfasst: ein Field Programmable Gate Array, FPGA, und ein Complex Programmable Logical Device, CPLD.The parser of claim 1, wherein the logic device each comprises: a Field Programmable Gate Array, FPGA, and a Complex Programmable Logical Device, CPLD. Parser nach Anspruch 1, wobei die main_proc Steuereinheit (201), die parse_term_proc Steuereinheit (202), die match_first_proc Steuereinheit (203) und match_follow_proc Steuereinheit (204) des Paketanalyse-Moduls (101) als Zustandsmaschinen implementiert sind.Parser according to claim 1, wherein the main_proc control unit ( 201 ), the parse_term_proc control unit ( 202 ), the match_first_proc control unit ( 203 ) and match_follow_proc control unit ( 204 ) of the packet analysis module ( 101 ) are implemented as state machines. Parser nach Anspruch 3, wobei die Zustandsmaschine der main_proc Steuereinheit (201) umfasst: einen PARSE_LOOP Zustand, welcher dazu ausgelegt ist, das Paket zu analysieren, einen REPEAT_MAX Zustand, welcher dazu ausgelegt ist, zu entscheiden, ob der Anfangsknoten des Stack, welcher den Regelbaum speichert, ein Endknoten ist, einen TERM_MATCH Zustand, welcher dazu ausgelegt ist, einen Abschluss abzugleichen und die parse_term_proc (202) Steuereinheit zu initiieren, einen IN_FIRST Zustand, welcher dazu ausgelegt ist, ein First Terminals Set festzustellen und die match_first_proc (203) Steuereinheit nach der Feststellung, dass das First Terminals Set existiert, zu initiieren, einen ALLSUB Zustand, welcher dazu ausgelegt ist, angenommen zu werden, wenn alle Unterknoten in dem IN_FIRST Zustand verarbeitet wurden, und in den PARSE_LOOP Zustand zurückzukehren; einen JUDGE_FOLLOW Zustand, welcher dazu ausgelegt ist, ein Follow Terminals Set zu festzustellen, in einen IN_FOLLOW Zustand überzugehen nach der Feststellung, dass das Follow Terminals Set existiert, und die match_follow_proc Steuereinheit (204) zu initiieren oder in einen NEXT_RULE Zustand überzugehen, falls kein Follow Terminals Set existiert, und in den PARSE_LOOP Zustand zurückzukehren, falls der Stack nicht leer ist.Parser according to claim 3, the state machine of the main_proc control unit ( 201 ) comprises: a PARSE_LOOP state configured to parse the packet, a REPEAT_MAX state configured to decide whether the initial node of the stack storing the rule tree is an end node, a TERM_MATCH state, to which is designed to reconcile a deal and the parse_term_proc ( 202 ) Initiate an IN_FIRST state, which is adapted to determine a First Terminals Set and the match_first_proc ( 203 ) Control unit upon determining that the first terminals set exists, an ALLSUB state which is adapted to be accepted when all subnodes in the IN_FIRST state have been processed, and return to the PARSE_LOOP state; a JUDGE_FOLLOW state configured to detect a Follow Terminal Set to transition to an IN_FOLLOW state after determining that the Follow Terminals Set exists, and the match_follow_proc control unit ( 204 ) or to enter a NEXT_RULE state if there is no Follow Terminals Set, and to return to the PARSE_LOOP state if the stack is not empty. Parser nach Anspruch 4, wobei die Zustandsmaschine der parse_term_proc Steuereinheit (202) umfasst: einen TERM_STRING Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Zeichenfolge abzugleichen, einen TERM_CODE_LIST Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Code Liste abzugleichen, einen TERM_SUCCESS Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines erfolgreichen Abgleichs zu informieren, einen TERM_FAIL Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines fehlgeschlagenen Abgleichs zu informieren.A parser according to claim 4, wherein the state machine of the parse_term_proc control unit ( 202 ) comprises: a TERM_STRING state adapted to match each individual character of a string, a TERM_CODE_LIST state adapted to match each individual character of a code list, a TERM_SUCCESS state adapted to the main_proc control unit ( 201 ) to inform about the result of a successful alignment, a TERM_FAIL state, which is designed to enable the main_proc control unit ( 201 ) to inform about the result of a failed reconciliation. Parser nach Anspruch 3, wobei die Zustandsmaschine der match_first_proc Steuereinheit (203) umfasst: einen LIST_LOOP Zustand, welcher dazu ausgelegt ist, zu bestimmen, ob eine Kodierungsart eines Pakets eine Zeichenfolge oder Code Liste ist, einen FIRST_STRING Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Zeichenfolge abzugleichen, einen FIRST_CODE_LIST Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Code Liste abzugleichen, einen FIRST_SUCCESS Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines erfolgreichen Abgleichs zu informieren, einen FIRST_FAIL Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines fehlgeschlagenen Abgleichs zu informieren.The parser of claim 3, wherein the state machine of the match_first_proc control unit ( 203 ) comprises: a LIST_LOOP state which is adapted to determine whether a coding type of a packet is a string or code list, a FIRST_STRING state adapted to match each individual character of a string, a FIRST_CODE_LIST state adapted thereto is to match each individual character of a code list, a FIRST_SUCCESS state, which is designed to be the main_proc control unit ( 201 ) to inform about the result of a successful match, a FIRST_FAIL state, which is adapted to the main_proc control unit ( 201 ) to inform about the result of a failed reconciliation. Parser nach Anspruch 3, wobei die Zustandsmaschine der match_follow_proc Steuereinheit (204) umfasst: einen LIST_LOOP Zustand, welcher dazu ausgelegt ist, zu bestimmen, ob eine Kodierungsart eines Pakets eine Zeichenfolge oder Code Liste ist, einen FOLLOW_STRING Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Zeichenfolge abzugleichen, einen FOLLOW_CODE_LIST Zustand, welcher dazu ausgelegt ist, jedes einzelne Zeichen einer Code Liste abzugleichen, einen FOLLOW_SUCCESS Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines erfolgreichen Abgleichs zu informieren, einen FOLLOW_FAIL Zustand, welcher dazu ausgelegt ist, die main_proc Steuereinheit (201) über das Ergebnis eines fehlgeschlagenen Abgleichs zu informieren.The parser of claim 3, wherein the state machine of the match_follow_proc control unit ( 204 ) comprises: a LIST_LOOP state which is adapted to determine whether a coding type of a packet is a string or code list, a FOLLOW_STRING state which is adapted to match each individual character of a string, a FOLLOW_CODE_LIST state which is adapted thereto is to match each individual character of a code list, a FOLLOW_SUCCESS state, which is designed to be the main_proc control unit ( 201 ) to inform about the result of a successful match, a FOLLOW_FAIL state, which is designed to change the main_proc control unit ( 201 ) to inform about the result of a failed reconciliation. Parser nach Anspruch 1, des weiteren umfassend ein Analyseergebnis-Speichermodul (102), welches dazu ausgelegt ist, ein Analyseergebnis zu speichern, nachdem die Analyse des Paketanalyse-Modul (101) durchgeführt wurde.The parser of claim 1, further comprising an analysis result storage module ( 102 ), which is adapted to store an analysis result after the analysis of the packet analysis module ( 101 ) was carried out.
DE112006000260.0T 2005-01-21 2006-01-23 Parser for analyzing a text-coded protocol Active DE112006000260B4 (en)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
CN200510001782.1 2005-01-21
CNB2005100017821A CN100505752C (en) 2005-01-21 2005-01-21 Universal parser for text encoding protocols
PCT/CN2006/000118 WO2006076869A1 (en) 2005-01-21 2006-01-23 A text coding type protocol parser

Publications (2)

Publication Number Publication Date
DE112006000260T5 DE112006000260T5 (en) 2008-01-24
DE112006000260B4 true DE112006000260B4 (en) 2014-04-10

Family

ID=36691991

Family Applications (1)

Application Number Title Priority Date Filing Date
DE112006000260.0T Active DE112006000260B4 (en) 2005-01-21 2006-01-23 Parser for analyzing a text-coded protocol

Country Status (4)

Country Link
US (1) US7636787B2 (en)
CN (1) CN100505752C (en)
DE (1) DE112006000260B4 (en)
WO (1) WO2006076869A1 (en)

Families Citing this family (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1842081B (en) * 2005-03-30 2010-06-02 华为技术有限公司 Method and device for matching and parsing extended backusian form string pattern
US8291058B2 (en) * 2010-02-19 2012-10-16 Intrusion, Inc. High speed network data extractor
US8745748B2 (en) * 2010-10-15 2014-06-03 Microsoft Corporation Cancelling digital signatures for form files
WO2012171166A1 (en) * 2011-06-13 2012-12-20 华为技术有限公司 Method and apparatus for protocol parsing
KR101913313B1 (en) * 2011-12-28 2018-10-31 삼성전자주식회사 A implementation method of contents centric network in a gateway using internet protocol based networks and a gateway thereof
US9343506B2 (en) 2014-06-04 2016-05-17 Micron Technology, Inc. Memory arrays with polygonal memory cells having specific sidewall orientations
CN105354282A (en) * 2015-10-30 2016-02-24 青岛海尔智能家电科技有限公司 XML file retrieval method and apparatus
US10298482B2 (en) * 2017-01-25 2019-05-21 Ringcentral, Inc. Systems and methods for regulating network resources to improve data-transmission quality
AU2018316966B2 (en) * 2017-08-18 2021-10-07 Nippon Telegraph And Telephone Corporation Intrusion prevention device, intrusion prevention method, and program
CN111061482B (en) * 2019-10-24 2023-12-08 贝壳技术有限公司 Method and device for analyzing parameters in character string, storage medium and electronic equipment
US11449496B2 (en) * 2019-10-25 2022-09-20 Servicenow, Inc. Enhanced natural language processing with semantic shortcuts
CN112860233B (en) * 2019-11-28 2024-03-15 华为云计算技术有限公司 Target syntax tree generation method and related equipment
CN110933077A (en) * 2019-11-29 2020-03-27 深圳市风云实业有限公司 Message parsing system and method

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5916305A (en) * 1996-11-05 1999-06-29 Shomiti Systems, Inc. Pattern recognition in data communications using predictive parsers
US20040088425A1 (en) * 2002-10-31 2004-05-06 Comverse, Ltd. Application level gateway based on universal parser
WO2004079571A2 (en) * 2003-02-28 2004-09-16 Lockheed Martin Corporation Hardware accelerator state table compiler

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6778949B2 (en) * 1999-10-18 2004-08-17 Sony Corporation Method and system to analyze, transfer and generate language expressions using compiled instructions to manipulate linguistic structures
DE50013051D1 (en) * 2000-04-14 2006-08-03 Tektronix Berlin Gmbh & Co Kg Method and device for analyzing data
JP3985944B2 (en) * 2001-11-22 2007-10-03 株式会社日立超エル・エス・アイ・システムズ Network device and program
US20030185220A1 (en) * 2002-03-27 2003-10-02 Moshe Valenci Dynamically loading parsing capabilities
US7187694B1 (en) * 2002-03-29 2007-03-06 Pmc-Sierra, Inc. Generic packet parser
US7062680B2 (en) * 2002-11-18 2006-06-13 Texas Instruments Incorporated Expert system for protocols analysis
EP1581869A2 (en) 2003-01-07 2005-10-05 International Business Machines Corporation A method and system for dynamically creating parsers in a message broker
CN100356727C (en) 2003-03-19 2007-12-19 华为技术有限公司 Method for analysing signalling
US7293113B1 (en) * 2003-05-28 2007-11-06 Advanced Micro Devices, Inc. Data communication system with hardware protocol parser and method therefor
US7451299B2 (en) * 2003-07-18 2008-11-11 Bea Systems, Inc. System and method for generating multi-way branches
US7328403B2 (en) * 2003-10-22 2008-02-05 Intel Corporation Device for structured data transformation
US7570661B2 (en) * 2005-06-14 2009-08-04 Microsoft Corporation Script-based parser

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5916305A (en) * 1996-11-05 1999-06-29 Shomiti Systems, Inc. Pattern recognition in data communications using predictive parsers
US20040088425A1 (en) * 2002-10-31 2004-05-06 Comverse, Ltd. Application level gateway based on universal parser
WO2004079571A2 (en) * 2003-02-28 2004-09-16 Lockheed Martin Corporation Hardware accelerator state table compiler

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
Crocker, d., Overell, P.: Augmented BNF for Syntax Specification: ABNF. IETF : RFC 2234, November 1997. - ISBN -. http://www.rfc-editor.org/rfc/pdfrfc/rfc2234.txt.pdf [abgerufen am 17.10.2012] *

Also Published As

Publication number Publication date
US20080040496A1 (en) 2008-02-14
CN1809053A (en) 2006-07-26
US7636787B2 (en) 2009-12-22
WO2006076869A1 (en) 2006-07-27
CN100505752C (en) 2009-06-24
DE112006000260T5 (en) 2008-01-24

Similar Documents

Publication Publication Date Title
DE112006000260B4 (en) Parser for analyzing a text-coded protocol
DE60222575T2 (en) A method for generating a DFA machine, wherein transitions are grouped into classes for the purpose of saving memory
DE112012002624B4 (en) Regex compiler
DE602005000984T2 (en) Method and device for storing input filter criteria and for specifying trigger point templates at the time of service implementation
DE10301362B4 (en) A block data compression system consisting of a compression device and a decompression device, and methods for fast block data compression with multi-byte search
DE60115615T2 (en) SYSTEM, DEVICE AND METHOD FOR FAST PACKAGE FILTERING AND PROCESSING
DE2210044C2 (en) Procedure for converting code words
DE68926483T2 (en) Process for processing hierarchical data
DE102005011845A1 (en) protocol emulator
DE112011103561T5 (en) Network processor and method for accelerating data packet parsing
DE69727933T2 (en) METHOD AND DEVICE FOR DESCRIPTING A DEFINED INTERFACE, OPERATION AND DATA TYPE IN AN INTERFACE DEFINITION LANGUAGE
DE69331044T2 (en) Device and method for syntactic signal analysis
DE60225785T2 (en) PROCESS FOR CODING AND DECODING A PATH IN THE TREE STRUCTURE OF A STRUCTURED DOCUMENT
EP1495611B1 (en) Representation of boolean expressions for specifying filters using xml
DE112019005382T5 (en) DESIGN AND PERFORMANCE OF A CHARACTER PATTERN RECOGNITION IN A CIRCUIT AT THE DATA LEVEL
DE60124722T2 (en) METHOD FOR TRANSMITTING A MOBILE AGENT IN A NETWORK; TRANSMITTER, RECEIVER AND ASSOCIATED MOBILE AGENT
DE102005013301A1 (en) Distributed data model
DE60030930T2 (en) Apparatus and method for maintaining a routing table
EP3991064B1 (en) Method and processor device for changing a data format of communication data of a device commmunication, and motor vehicle
DE60210986T2 (en) METHOD AND DEVICE FOR TRANSMITTING SNMP MESSAGES USING UDP WITH COMPIATION OF PERIODICALLY REPRODUCING SEQUENCES
DE102021201028A1 (en) GENERIC INSERT AND REMOVAL OF PACKAGE HEADERS
DE60303775T2 (en) Network unit for forwarding Ethernet packets
WO2023025764A1 (en) Device and method for processing data units
DE10219390B4 (en) Server, buffer memory and browser for accelerated transmission of hypertext documents
EP2157525B1 (en) Method for recognising malware

Legal Events

Date Code Title Description
OP8 Request for examination as to paragraph 44 patent law
R016 Response to examination communication
R016 Response to examination communication
R018 Grant decision by examination section/examining division
R020 Patent grant now final
R020 Patent grant now final

Effective date: 20150113

R079 Amendment of ipc main class

Free format text: PREVIOUS MAIN CLASS: H04L0012260000

Ipc: H04L0043000000

OSZAR »