Security of Czech army information and communication systems - On-line monitoring, Visualization and Packet Filtration. Computer Incident Response Capability Development in the Cyber Defence EnvironmentEfficient NetFlow Pairing Algorithm

NetFlow protocol data used for high speed networks monitoring always contains only information from one direction of communication. Thus, in the case of communication between the server and client, we obtain two different NetFlow data streams.

Within the objectives of the project, we implemented a new efficient algorithm that performs the pairing of network flows into communication couples. The aim of this implementation, which performs pairing at the collector level of network flows, was to replace the original inefficient pairing algorithm. The former solution saved network flows into the database at first, from where the pairing was subsequently carried and thus the overall performance of the algorithm was not sufficient for the deployment in a real network.

The new algorithm was successfully implemented and the detailed testing and validation were carried out. We likewise focused on the performance of the new implementation in detail. The several orders of magnitude acceleration of new implementation compared to the original solution has been observed. Another important result is improving the time complexity of pairing, which grows linearly with the number of flows compared to the quadratic complexity of the original pairing algorithm.

Thanks to new solution the pairing algorithm can be deployed in current high-speed networks. This algorithm can be deployed also in high-speed networks due to its scalability in the future. Main applications are:

  • Profiling of network devices, namely the role of the device determination (server or client).
  • Elimination of "noise" in aggregated statistics having form of unpaired flows; i. e., one-way flows can be easily filtered.
  • Simplification of network anomaly detection (port scanning and exploration of services network are trivial cases).
  • Operational problems troubleshooting (most of common network protocols work use two-way connection).

Run times of particular parts of the new pairing algorithm

The speed comparison of the original and the new pairing algorithm