Evaluating Different Genetic Algorithms for a State-machine Combining Assignment Problem

Abstract: Deep packet inspection (DPI) is useful as a tool for analyzing internet traffic. Regular expressions (regexps) can be used to detect the network traffic patterns that the DPI is able to identify. These regexps can be represented as state-machines, and sometimes combining smaller state-machines into larger state-machines can result in more efficient processing. This thesis looks at how to decide which state-machines used in DPI-classes should be combined with which other state-machines in an efficient manner using genetic algorithms. The goal being to create as few resulting state-machines from the combination while still maintaining a upper limit on the size of the resulting state-machines. The problem is modelled as an assignment problem for which an emulated surrogate problem is used in order to make experimental evaluations. Several genetic algorithms are suggested in an attempt to explore a wide range of parameters. It is also evaluated if different genetic algorithms perform differently depending on if the state-machines represent DPI-classes used to parse UDP or TCP traffic. A 2-dimensional representation is used that allows for a better capture of the underlying assignment problem. Different approaches to fitness are explored and found to have different efficacy in different situations. Several genetic algorithm operators are suggested for different situations and a difference is found between what works for UDP and for TCP.