Signature-based network intrusion detection systems (S-IDS) have become an important security tool in the protection of an organisation’s infrastructure against external intruders. By analysing network traffic, S-IDS’ detect network intrusions. An organisation may deploy one or multiple S-IDS’, each working independently with the assumption that it can
monitor all packets of a given flow to detect intrusion signatures. However, emerging technologies (e.g., Multi-Path TCP) violate this assumption, as traffic can be concurrently sent across different paths (e.g., WiFi, Cellular) to boost network performance. Attackers may exploit this capability and split malicious payloads across multiple paths to evade traditional signaturebased network intrusion detection systems. Although multiple monitors may be deployed, none of them has the full coverage of the network traffic to detect the intrusion signature. In this paper, we formalise this distributed signature-based intrusion detection problem as an asynchronous online exact string matching problem, and propose an algorithm for it. To demonstrate its effectiveness we conducted comprehensive experiments. Our results show that the behaviour of our algorithm depends only on the packet arrival rate: delay in detecting the signature grows linearly with respect to the packet arrival rate and with small communication overhead.