1 of 32

1

Farzana Ahmed Siddique, Tommy James Tracy II, Nathan Brunelle, Kevin Skadron

University of Virginia

7^th December 2022

Deterministic vs. Non-deterministic Finite Automata in Automata Processing

2 of 32

Automata Processing for Pattern Matching

MOTIVATION

2

Network Security

Genomics

Machine Learning

Regex

Finite State Automata

Anti Virus

Grapefruit’ 20

Impala’ 20

SPM’ 16

REAPR’ 19

Hybrid-FA’ 07

Hyperscan’ 19

Hardware

von Neumann Architecture

(CPU, GPU)

Spatial Architecture (FPGA, ASIC)

3 of 32

Finite Automata Variants

MOTIVATION

3

Network Security

Genomics

Machine Learning

Anti Virus

Regex

Finite State Automata

Hardware

Deterministic Finite Automata (DFA)

Non-deterministic Finite Automata (NFA)

von Neumann Architecture

(CPU, GPU)

Spatial Architecture (FPGA, ASIC)

It is important to carefully choose an optimal hardware and computation model pair, to design an efficient pattern matching engine.

4 of 32

Differences in Finite Automata Variants

MOTIVATION

4

DFA activates only one state per symbol.
NFA may activate many states per symbol.
If an NFA has n states, its equivalent DFA can have at most 2ⁿ states.

1

3

2

b

a

4

a,b

b

a,b

1

3

4

2

b

a

b

DFA

NFA

5 of 32

DFA can be more compact than the NFA?!

MOTIVATION

5

Lower transition density -> DFA states growth rate polynomial to sub-exponential.
Higher transition density -> minimized DFAs have smaller state count than the NFAs.

DFA’s state count is greater than or equal to the NFA.

Used synthetic automata with different transition density^[2].

[1] D. Tabakov, MY. Vardi,LPAR’ 05

[2] For each symbol, ratio of the total number of transition to the total number of states.

Were they not optimal?

Previous work on automata processing done in UVA, uses NFA.

This paper answer this question!

6 of 32

Experiments

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA
DFA VS. NFA PERFORMANCE ANALYSIS ON FPGA
CPU VS. FPGA PERFORMANCE ANALYSIS

6

7 of 32

Benchmark/Application Used

EXPERIMENTS

7

Benchmark Suite: AutomataZoo

Regex-based: Snort, ClamAV & Brill
Mesh: Levenshtein & Hamming
Synthetic: DotStar

The benchmarks are represented as NFAs.
Each benchmark comprises multiple distinct patterns.

Benchmark/Application	#Patterns
Brill	5,946
Snort	2,348
ClamAV	33,000
Hamming	1,000
Levenshtein	1,000
Random Forest	8,000

8 of 32

1. State Count Analysis: Minimized DFA vs. Optimized NFA

8

9 of 32

Methodology

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

9

State Count Analysis

Individual Pattern

Multiple Pattern

Use Brzozowski’s algorithm to get the minimized DFA.
Use heuristics to get optimized NFA.

Incrementally (1, 2, 3, ...) add patterns to a single automaton.
Use Brzozowski’s algorithm to get the minimized DFA and heuristics to get optimized NFA.

10 of 32

DFA Minimization

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

10

Two different algorithms:

Hopcroft
Brzozowski

Brzozowski’s algorithm instead of Hopcroft’s because Hopcroft does not take NFA as an input!

11 of 32

NFA Optimization

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

11

NFA minimization is a PSPACE-complete problem.
Heuristic-based approach

If multiple states have equivalent outgoing transitions (for all the symbols, they transition into the same states), merge those states into a single state.
If multiple states have equivalent incoming transitions, merge those states to a single state.

12 of 32

NFA Optimization: Example

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

12

2

1

12

16

13

17

3

4

15

19

14

18

101

116

97

108

114

2

1

12

16

3

4

15

19

14

18

101

116

97

108

114

101

2

1

12

3

4

15

19

14

18

101

116

97

108

114

101

13 of 32

NFA Optimization: Example

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

13

2

1

12

3

4

15

19

14

101

116

97

108

114

101

Complexity : O(n²)

n = #states in the NFA.

2

1

3

4

15

19

14

101

116

97

108

114

14 of 32

NFA Optimization

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

14

Plotted in log-log scale.
Contains data points form different benchmarks.
The diagonal line represents x=y.

15 of 32

Findings (Individual Patterns)

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

15

Snort

Plotted in log-log scale.
Distinct DFA generated for each distinct pattern, does not show exponential growth for any of the benchmarks!

ClamAV

16 of 32

Findings (Individual Patterns)

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

16

Brill

Plotted in log-log scale.
Distinct DFA generated for each distinct pattern, does not show exponential growth for any of the benchmarks!

Levenshtein

17 of 32

Findings (Individual Patterns)

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

17

DFA state count = NFA state count for Hamming and Random Forest.

Hamming

Graph is plotted in log-log scale.

DFAs generated for individual patterns are comparable to the equivalent NFAs in state count.

18 of 32

Findings (Multiple Patterns)

STATE COUNT ANALYSIS: MINIMIZED DFA VS. OPTIMIZED NFA

18

One large DFA generated for distinct patterns, can show exponential growth!
Can be expensive in terms of computation time (hours/days)

DFAs generated by merging patterns can be expensive in terms of conversion time and state count.

19 of 32

The Paper That Motivated This

19

Performs an empirical run time analysis between Hopcroft’s and Brzozowski’s algorithm.
Generated random NFAs and compares state count for minimized DFA vs NFA.

20 of 32

2. DFA vs. NFA Performance Analysis on FPGA

20

21 of 32

Grapefruit

DFA VS. NFA PERFORMANCE ANALYSIS ON FPGA

21

FPGA Architecture (taken from Xilinx website)

Automata Mapped to LUTs

1. STE represents a state and the symbols that activates that state.

2. STE is implemented using Look up tables (LUT).

22 of 32

Methodology

DFA VS. NFA PERFORMANCE ANALYSIS ON FPGA

22

NFA vs. DFA Performance Analysis on FPGA

Minimized DFA

Optimized NFA

Used Grapefruit to log the maximum frequency and calculate the throughput.

23 of 32

Findings

DFA VS. NFA PERFORMANCE ANALYSIS ON FPGA

23

FPGA has higher throughput for NFA.
For some benchmarks

FPGA has equal/higher throughput for DFAs.

Benchmark	Computation Model	Max Fan-Out	Avg Node Degree
YARA	NFA	133	1.1
YARA	DFA	5	1.1
ER	NFA	3	3.5
ER	DFA	3	3

24 of 32

High Fan-Out a Performance Bottleneck

DFA VS. NFA PERFORMANCE ANALYSIS ON FPGA

24

Why High fan-out or node degree works as a performance bottleneck for FPGA?

Components (STE) tries to accommodate its children as close as possible.
If #connected component is large enough that some of them has long interconnect distance, that may become the critical path.

Throughput

Frequency

Benchmarks that have high fan out or node degree for NFA, may use DFAs while processing on FPGA

25 of 32

3. CPU vs. FPGA Performance Analysis

25

26 of 32

Hyperscan

CPU VS. FPGA PERFORMANCE ANALYSIS

26

Pattern as Regex.
Regex decomposition.
Mostly uses DFA.
DFA crosses the state count threshold, uses NFA.
SIMD (Single Instruction Multiple Data) bit vector based NFA processing.

Hyperscan Regex Decomposition

27 of 32

Methodology

CPU VS. FPGA PERFORMANCE ANALYSIS

27

Performance Analysis: CPU vs. FPGA

CPU

FPGA

Used Hyperscan toolchain to calculate the throughput.

Used Grapefruit to calculate the throughput.

28 of 32

Findings

CPU VS. FPGA PERFORMANCE ANALYSIS

28

Grapefruit has higher (> 1000x speedup) throughput than the CPU for most of the benchmarks.
Hyperscan outperforms Grapefruit for ClamAV, YARA & FileCarve.
Grapefruit can not process the entire ClamAV benchmark.

29 of 32

Why Grapefruit Performs Poorly for Some Benchmarks?

CPU VS. FPGA PERFORMANCE ANALYSIS

29

FileCarve is a special case (only 9 patterns).
ClamAV & YARA -> small #pattern_matched/input.

30 of 32

Hyperscan’s throughput is sensitive to pattern matching rate!

CPU VS. FPGA PERFORMANCE ANALYSIS

30

Pick a symbol (x) from the accepted symbol list

X is accepted by the state

X is not accepted by the state

Terminate

Empty state list

Nonempty state list

31 of 32

Summary

CONCLUSION

31

1. If we keep the patterns separate, minimized DFAs are comparable in state count to their equivalent optimized NFAs. However, generating a large DFA for an entire application is infeasible.

2. DFAs can also be used as computation model for FPGA and can outperform NFAs on FPGA.

3. Compared to FPGA-based automata processing engine, the performance of CPU-based is application and workload sensitive.

32 of 32

Thanks!

QUESTION?

32

Acknowledgement: Tommy Tracy, Abdullah Tahsin Mughrabi, Alif Ahmed, Kevin Skadron