Fastly, Inc.
MINIMIZATION OPTIMIZATIONS FOR WEB APPLICATION FIREWALLS

Abstract:

Technology is disclosed herein for optimizing the process of minimization a graph so as to produce a minimized version of the graph for a web application firewall in less time than otherwise and consuming fewer resources. In particular, multiple optimizations are disclosed herein that include: a first optimization that groups states based on their distance to a final state; a second optimization that removes equivalence classes that have less than two states; a third optimization that splits equivalence classes while in-place; and a fourth optimization that splits equivalence classes using the label set that occurs in a given class. The minimization optimizations may be implemented individually or in combination with one another.