J_Hybrid_Fa Documentation

This page contains the J_Hybrid_Fa Package documentation.

The j_hybrid_fa Module

Module for pattern match: algorithm for Hybrid Finite Automat.

class netbench.pattern_match.algorithms.j_hybrid_fa.j_hybrid_fa.JHybridFA

Bases: netbench.pattern_match.b_automaton.b_Automaton

Class for Hybrid Finite Automat.

Hybrid automaton is saved in:
  • self.dfa - Head DFA part of Hybrid FA
  • self.nfas - Tails NFA parts of Hybrid FA
  • self.tran_aut - List of border states

Indexes in self.tran_aut reffer to self.nfas list for particular NFA tails.

Based on:
“A hybrid finite automaton for practical deep packet inspection” ISBN: 978-1-59593-770-4 URL: http://portal.acm.org/citation.cfm?id=1364656

Approach split each input regular expression to DFA prefix and NFA suffix by blow up pattern. It is the pattern where autmaton reachs much more states than before. For example pattern: /ab[a-z]*cd/ has blow up pattern [a-z]* and it will be split into /ab/ pattern to DFA part and /[a-z]*.cd/ pattern to be set into NFA tail. DFA part is determinised as usual and than are joined NFA tails.

Approach works with input text file and split input patterns - not input NFA. This idea comes from Jaroslav Suchodol <xsucho04@stud.fit.vutbr.cz>

compute()
Computes Hybrid automaton.
create_by_parser(parser)

This function is used to create automaton from set of regular expressions.

This method is forbidden because approach work with input text file. Set parser instance by set_parser() method and input file with regular expressions by load_file().

Parameter:nfa_parser_class (nfa_parser) – An instation of nfa_parser class.
Returns:False if creation of automaton failed or True if creation was successful.
Return type:boolean

This method sets _compute to False, and get_compute() will return False until compute() is called.

Raises:general_not_implemented()
create_from_nfa_data()

Create automaton from nfa_data object.

This method is forbidden because approach work with input text file. Set parser instance by set_parser() method and input file with regular expressions by load_file().

Parameters:
  • nfa (nfa_data) – nfa_data object, from which automaton is created.
  • safe (boolean) – If True perform deep copy, otherwise set reference. Default value is True.

This method sets _compute to False, and get_compute() will return False until compute() is called.

Raises:general_not_implemented()
get_automaton()

DFA head of automaton is save in self.dfa, NFA tails are in self.nfas. Read instruction in __init__ method.

Raises:empty_automaton_exception()
get_state_num()

Return number of states in Hybrid automaton.

Returns:Number of states in Hybrid automaton
Return type:int
get_trans_num()

Return number of transitions in Hybrid automaton.

Returns:Number of transitions in Hybrid automaton
Return type:int
load_file(file_name)

Set path to file with regular expression.

Parameter:file_name (string) – Path to file with regular expression
report_memory_naive()

Report consumed memory in bytes. Read documentaion in b_dfa and b_nfa methods for more information.

Returns:Returns number of bytes.
Return type:int
report_memory_optimal()

Report consumed memory in bytes. Read documentaion in b_dfa and b_nfa methods for more information.

Returns:Returns number of bytes.
Return type:int
save_to_file(file_name)

DFA head of automaton is save in self.dfa, NFA tails are in self.nfas. Read instruction in __init__ method.

Raises:empty_automaton_exception()
search(input_string)

Function will find patterns in the given string.

Parameters:
  • input_string – Input string.
  • input_string – string
Returns:

Bitmap of matched regular expressions.

Return type:

list(int)

set_parser(parser_instance)

Set parser instance to be used in approach.

Parameter:parser_instance (nfa_parser) – Parser instance to be used in approach.
show(file_name)

Print states, alphabet, start, transitions, final, Flags of DFA part and NFA parts. And save graphviz dot file, representing graphical structure of nfa_data.

Parameter:file_name (string) – Name of output DOT file

The test_j_hybrid_fa Module

class netbench.pattern_match.algorithms.j_hybrid_fa.test_j_hybrid_fa.test_JHybridFA(methodName='runTest')

Bases: unittest.TestCase

Test module for class JHybridFA.

test___init__()
__init__()
test__find_first_occurence_of_blowup()
_find_first_occurence_of_blowup()
test__split_expresion()
_split_expresion()
test_compute()
compute()
test_get_state_num()
get_state_num()
test_get_trans_num()
get_state_num()
test_report_memory_naive()
report_memory_naive()
test_report_memory_optimal()
report_memory_optimal()
search()
test_set_parser()
set_parser()

Table Of Contents

Previous topic

Hybrid_Fa Documentation

Next topic

Sindhu_Prasana_Nfa Documentation

This Page