## 3 Network Anomaly Detection
### String Matching  
When inspecting a packet, useful information may be contained in its payload, and one effective way to detect the presence of signatures in it is using regular expression (RegEx), which provides a concise manner to identify strings, substrings and even patterns of characters.  
Snort [43], one of the most used open-source IDS, for example, uses signature matching to generate an alert when an anomaly is found. Considering there is a unique expression in a packet that identifies an anomaly, a known attack can be detected with Snort. For instance, there is the buffer overflow in the Samba server (CVE-1999-0811) where the byte pattern 0 xEB2F5 FEB4A5E89 FB893E89F2 [44] is detected, and it characterizes an attack exploiting that vulnerability.  
As regular expressions allow the use of wildcards and ranges, it can also be used to search for packets addressed or originated from a specific subnetwork (when matching against the _destination_ or _source_ fields, respectively, of the datagram), with the purpose of investigating only the events related to that subnetwork. This also applies to the other fields in any layer of the packets, for example, filtering during an investigation for packets transmitted in a time range, from a specific Media Access Control(MAC) address or packets of a specific protocol. Table 3 shows some other scenarios in which RegEx are useful.  
This string matching approach provides some advantages to an investigation, as it is simple and easy to understand what the detection tool is looking for and, thus, when a match is found for some signatures, it may be interpreted that an attack has been detected discarding false positives matching. It is also easy to add and share many signatures, creating a library of known malicious signatures and/or other string patterns to be searched for in a packet's payload.  
Using RegEx in DPI, however, is not that simple and results in difficulties that make it unpractical in some cases. Firstly, because the string matching process must be, at least, as fast as the line speed to detect threats in real time. Secondly, the detection of a known malicious string may not always imply in the occurrence of an attack, as there are many signatures that also occur in a normal packet flow, resulting in too many false positive alerts overloading dashboards with incorrect information.  
A stateful analysis of the payload string decreases the rate of false positive detections. Thereby, not only the payload of each packet is compared against the known malicious strings, but also the state of the conversation between the two devices. For instance, if supposedly malicious content is expected, then an alert should not be emitted because of its occurrence.  
[PERSON] and [PERSON] [58] cite as an example the CVE-2000-0778, whose signature is :_Translate:_\(F\) and it is common in normal flows. The authors also describe the use of regular expression with context in DPI to reduce the false positive occurrence.  
For the string matching process to be fast enough, it is necessary dedicated hardware and software. However, RegEx requires large bandwidth, many algorithms and other string matching implementations, which have been studied to solve this issue--among them, bloom filters [59] that accelerate the string matching process with a controllable false positive rate and finite state machines [60; 61; 62], such as Deterministic Finite Automaton and Nondeterministic Finite Automaton.