专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US08938454B2 Using a tunable finite automaton for regular expression matching 有权
标题翻译：使用可调谐有限自动机进行正则表达式匹配
公开(公告)号：US08938454B2
公开(公告)日：2015-01-20
申请号：US13648438
申请日：2012-10-10
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： G06F17/30985
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

2. 发明授权

US10129181B2 Controlling the reactive caching of wildcard rules for packet processing, such as flow processing in software-defined networks 有权
公开(公告)号：US10129181B2
公开(公告)日：2018-11-13
申请号：US14461372
申请日：2014-08-16
申请人： Yang Xu , H. Jonathan Chao
发明人： Yang Xu , H. Jonathan Chao
IPC分类号： H04L12/931 , H04L12/851 , H04L12/947 , H04L12/715 , H04L12/819
摘要： Software-Defined Networking (“SDN”) enables flexible flow control by caching policy rules at OpenFlow switches. Compared with exact-match rule caching, wildcard rule caching can better preserve the flow table space at switches. However, one of the challenges for wildcard rule caching is the dependency between rules, which is generated by caching wildcard rules overlapped in field space with different priorities. Failure to handle the rule dependency may lead to wrong matching decisions for newly arrived flows, or may introduce high storage overhead in flow table memory. A wildcard rule caching system, which may be used for SDN partitions the field space into logical structures called buckets, and caches buckets along with all the associated wildcard rules. Doing so resolves rule dependency while using control network bandwidth efficiently. Further, controller processing load and flow setup latency are reduced.

3. 发明授权

US09455996B2 Generating progressively a perfect hash data structure, such as a multi-dimensional perfect hash data structure, and using the generated data structure for high-speed string matching 有权
标题翻译：逐渐生成完美的散列数据结构，如多维完美散列数据结构，并使用生成的数据结构进行高速字符串匹配
公开(公告)号：US09455996B2
公开(公告)日：2016-09-27
申请号：US13409947
申请日：2012-03-01
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F17/30 , H04L29/06 , G06F21/55
CPC分类号： H04L63/1416 , G06F17/30946 , G06F17/30949 , G06F17/30958 , G06F17/30985 , G06F21/55 , H04L63/0245
摘要： A multi-dimensional perfect hash table construction technique is based on which the well-known AC automaton, and can be implemented by very compact perfect hash tables. The technique may place transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table by: (a) dividing the transitions into multiple independent sets according to their respective source states; (b) ordering the sets of transitions based on the number of transitions belonging to the set, thereby defining an order of the sets from largest to smallest; and (c) constructing a perfect hash table by, for each of the sets of transitions, in the order from largest to smallest, hashing the transitions of the set into the hashing table to generate a perfect hashing table.
摘要翻译：一种多维完美的散列表构建技术是基于众所周知的AC自动机，可以通过非常紧凑的完美散列表来实现。该技术可以将自动机的每个从源状态到目的地状态的转换放置到散列表中，以通过以下方式产生完美的散列表：（a）根据它们各自的源状态将转换分为多个独立集合; （b）基于属于集合的转移次数来排序转换集合，由此定义从最大到最小的集合的顺序; 并且（c）通过按照从最大到最小的顺序对于每个转换集合构建完美散列表，将集合的转换散列到散列表中以生成完美散列表。

4. 发明授权

US08943063B2 Generating a tunable finite automaton for regular expression matching 有权
标题翻译：生成用于正则表达式匹配的可调谐有限自动机
公开(公告)号：US08943063B2
公开(公告)日：2015-01-27
申请号：US13648432
申请日：2012-10-10
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： H04L41/16 , H04L43/028
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

5. 发明授权

US08862585B2 Encoding non-derministic finite automation states efficiently in a manner that permits simple and fast union operations 有权
标题翻译：非限制性有限自动化编码以允许简单快速的联合操作的方式有效地进行状态化
公开(公告)号：US08862585B2
公开(公告)日：2014-10-14
申请号：US13648452
申请日：2012-10-10
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： H04L43/028 , H04L63/1416
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

6. 发明申请

US20130086017A1 GENERATING PROGRESSIVELY A PERFECT HASH DATA STRUCTURE, SUCH AS A MULTI-DIMENSIONAL PERFECT HASH DATA STRUCTURE, AND USING THE GENERATED DATA STRUCTURE FOR HIGH-SPEED STRING MATCHING 有权
标题翻译：产生一个完整的HASH数据结构，如多维完整的HASH数据结构，并使用生成的数据结构进行高速匹配
公开(公告)号：US20130086017A1
公开(公告)日：2013-04-04
申请号：US13409947
申请日：2012-03-01
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00
CPC分类号： H04L63/1416 , G06F17/30946 , G06F17/30949 , G06F17/30958 , G06F17/30985 , G06F21/55 , H04L63/0245
摘要： A multi-dimensional perfect hash table construction technique is based on which the well-known AC automaton, and can be implemented by very compact perfect hash tables. The technique may place transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table by: (a) dividing the transitions into multiple independent sets according to their respective source states; (b) ordering the sets of transitions based on the number of transitions belonging to the set, thereby defining an order of the sets from largest to smallest; and (c) constructing a perfect hash table by, for each of the sets of transitions, in the order from largest to smallest, hashing the transitions of the set into the hashing table to generate a perfect hashing table.
摘要翻译：一种多维完美的散列表构建技术是基于众所周知的AC自动机，可以通过非常紧凑的完美散列表来实现。该技术可以将自动机的每个从源状态到目的地状态的转换放置到散列表中，以通过以下方式产生完美的散列表：（a）根据它们各自的源状态将转换分为多个独立集合; （b）基于属于集合的转移次数来排序转换集合，由此定义从最大到最小的集合的顺序; 并且（c）通过按照从最大到最小的顺序对于每个转换集合构建完美散列表，将集合的转换散列到散列表中以生成完美散列表。

7. 发明授权

US08935250B2 Regrouping non-derministic finite automaton active states to minimize distinct subsets 有权
标题翻译：重新分组非破坏性有限自动机活动状态以最小化不同的子集
公开(公告)号：US08935250B2
公开(公告)日：2015-01-13
申请号：US13648446
申请日：2012-10-10
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： H04L63/1416
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

8. 发明授权

US08775393B2 Updating a perfect hash data structure, such as a multi-dimensional perfect hash data structure, used for high-speed string matching 有权
标题翻译：更新完美的散列数据结构，如用于高速字符串匹配的多维完美散列数据结构
公开(公告)号：US08775393B2
公开(公告)日：2014-07-08
申请号：US13409974
申请日：2012-03-01
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F17/30 , G06F12/00 , G06F7/00 , H04L29/06
CPC分类号： H04L63/1416 , G06F17/30946 , G06F17/30949 , G06F17/30958 , G06F17/30985 , G06F21/55 , H04L63/0245
摘要： A representation of a new rule, defined as a set of a new transition(s), is inserted into a perfect hash table which includes previously placed transitions to generate an updated perfect hash table. This may be done by, for each new transition: (a) hashing the new transition; and (b) if there is no conflict, inserting the hashed new transition into the table. If, however, the hashed new transition conflicts with any of the previously placed transitions, either (A) any transitions of the state associated with the conflicting transition are removed from the table, the hashed new transition is placed into the table, and the removed transitions are re-placed into the table, or (B) any previously placed transitions of the state associated with the new transition are removed, and the transitions of the state associated with the new transition are re-placed into the table.
摘要翻译：定义为一组新的转换的新规则的表示被插入到完美的哈希表中，其包括先前放置的转换以生成更新的完美散列表。对于每个新的过渡，这可能会被完成：（a）散列新的过渡; 和（b）如果没有冲突，将散列的新转换插入表中。然而，如果散列的新转换与任何先前放置的转换冲突，则（A）与冲突转换相关联的状态的任何转换从表中移除，将散列的新转换放入表中，并将其移除过渡被重新放置到表中，或者（B）除去与新转换相关联的状态的任何先前放置的转换，并且将与新转换相关联的状态的转变重新放置到表中。

9. 发明授权

US09094350B2 Finding nonequivalent classifiers to reduce ternary content addressable memory (TCAM) usage 有权
标题翻译：寻找非等价分类器来减少三元内容可寻址内存（TCAM）的使用
公开(公告)号：US09094350B2
公开(公告)日：2015-07-28
申请号：US13837490
申请日：2013-03-15
申请人： H. Jonathan Chao , Rihua Wei , Yang Xu
发明人： H. Jonathan Chao , Rihua Wei , Yang Xu
IPC分类号： G06N5/04 , H04L12/56 , H04L12/743 , H04L12/701 , H04L12/54
CPC分类号： H04L45/7457 , H04L12/56 , H04L45/00
摘要： The problem of providing an efficient physical implementation of a (first) classifier defined by a first rule set, at least a part of which first classifier having a sparse distribution in Boolean space, is solved by (1) converting the first classifier, having a corresponding Boolean space, into a second classifier, wherein the second classifier has a corresponding Boolean space which is not semantically equivalent to the Boolean space corresponding to the first classifier, and wherein the second classifier is defined by a second set of rules which is smaller than the first set of rules defining the first classifier; and (2) defining a bit string transformation which transforms a first bit string into a second bit string, wherein applying the first bit string to the first classifier is equivalent to applying the second bit string to the second classifier. In at least some example embodiments, the first bit string includes packet header information. In at least some example embodiments, the second classifier is implemented on a TCAM. In at least some example embodiments, the bit string transformation is implemented on an FPGA.
摘要翻译：提供由第一规则集（其至少其中一部分具有布尔空间中具有稀疏分布的第一分类器）定义的（第一）分类器的有效物理实现的问题通过（1）转换第一分类器，具有相应的布尔空间，转换成第二分类器，其中所述第二分类器具有对应的布尔空间，其在语义上等同于与所述第一分类器相对应的布尔空间，并且其中所述第二分类器由小于定义第一个分类器的第一组规则; 以及（2）定义将第一位串变换为第二位串的位串变换，其中将第一位串应用于第一分类器等效于将第二位串应用于第二分类器。在至少一些示例性实施例中，第一位串包括分组报头信息。在至少一些示例性实施例中，第二分类器在TCAM上实现。在至少一些示例实施例中，位串转换在FPGA上实现。

10. 发明申请

US20140269715A1 FINDING NONEQUIVALENT CLASSIFIERS TO REDUCE TERNARY CONTENT ADDRESSABLE MEMORY (TCAM) USAGE 有权
标题翻译：查找无效的分类器以减少三次内容可寻址存储器（TCAM）的使用
公开(公告)号：US20140269715A1
公开(公告)日：2014-09-18
申请号：US13837490
申请日：2013-03-15
申请人： H. Jonathan Chao , Rihua Wei , Yang Xu
发明人： H. Jonathan Chao , Rihua Wei , Yang Xu
IPC分类号： H04L12/743
CPC分类号： H04L45/7457 , H04L12/56 , H04L45/00
摘要： The problem of providing an efficient physical implementation of a (first) classifier defined by a first rule set, at least a part of which first classifier having a sparse distribution in Boolean space, is solved by (1) converting the first classifier, having a corresponding Boolean space, into a second classifier, wherein the second classifier has a corresponding Boolean space which is not semantically equivalent to the Boolean space corresponding to the first classifier, and wherein the second classifier is defined by a second set of rules which is smaller than the first set of rules defining the first classifier; and (2) defining a bit string transformation which transforms a first bit string into a second bit string, wherein applying the first bit string to the first classifier is equivalent to applying the second bit string to the second classifier. In at least some example embodiments, the first bit string includes packet header information. In at least some example embodiments, the second classifier is implemented on a TCAM. In at least some example embodiments, the bit string transformation is implemented on an FPGA.
摘要翻译：提供由第一规则集（其至少其中一部分具有布尔空间中具有稀疏分布的第一分类器）定义的（第一）分类器的有效物理实现的问题通过（1）转换第一分类器，具有相应的布尔空间，转换成第二分类器，其中所述第二分类器具有对应的布尔空间，其在语义上不等于对应于所述第一分类器的布尔空间，并且其中所述第二分类器由小于定义第一个分类器的第一组规则; 以及（2）定义将第一位串变换为第二位串的位串变换，其中将第一位串应用于第一分类器等效于将第二位串应用于第二分类器。在至少一些示例性实施例中，第一位串包括分组报头信息。在至少一些示例性实施例中，第二分类器在TCAM上实现。在至少一些示例实施例中，位串转换在FPGA上实现。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式