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. / Deep packet inspection (DPI) ̈ar användbart som ett verktyg f ̈or att analysera internettrafik. Regular expressions (regexps) kan användas för att detektera trafik mönster somDPI:n kan identifiera. De här regexps kan representeras som state-machines, och ibland så kan kombinationen av mindre state-machines till större state-machines resultera i mer effektiv bearbetning. Den här tesen undersöker hur man kan bestämma vilka state-machines som används iDPI-klassen bör bli kombinerade på ett effektivt sätt med genetiska algoritmer. Målet är att skapa så fǻ resulterande state-machines från kombineringen på ett sådant sätt att storleken på alla resulterande state-machines håller sig under en övre gräns. Problemet är modellerat som ett assignment problem för vilket ett emulerat surrogatproblem används för att tillåta experiment att utföras. Ett flertal genetiska algoritmer är föreslagna i ett försök att undersöka en bred räckvidd av parametrar. Det är också undersökt om olika genetiska algoritmer har olika prestanda beroende på om state-machines representerar DPI-klasser använda för UDP eller TCP trafik. En 2-dimensionell representation som fångar det underliggande problemet på ett bras sätt är använd. Olika tillvägagångssätt för att representera fitness är undersökta och är upptäckta att ha olika effektivitet i olika situationer. Ett flertal genetiska algoritm operatorer är föreslagna för olika situationer och en skillnad är hittad mellan vad som fungerar för UDP och vad som fungerar för TCP.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kau-79019 |
| Date | January 2020 |
| Creators | Hillblom, Jonathan |
| Publisher | Karlstads universitet |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0171 seconds