Learn more about R-Scope Advanced Threat Detection »

On the Bottleneck Structure of Positive Linear Programming

Publication Source: 2019 SIAM Workshop on Network Science

Positive linear programming (PLP), also known as packing and covering linear programs, is an important class of problems frequently found in fields such as network science, operations research, or economics. In this work we demonstrate that all PLP problems can be represented using a network structure, revealing new key insights that lead to new polynomial-time algorithms.  

Google Scholar    Article

Selective Packet Capture at High Speed Rates

Publication Source: Zeek (Bro) Workshop 2019, CERN, Switzerland

Full packet capture (FPC) consists in capturing all packets and storing them into permanent storage to enable offline forensic analysis. FPC however suffers from a scalability issue: at today's normal traffic speed rates of 10Gbps or above, it either becomes intractable or requires highly expensive hardware both in processing and storage, which rapidly decreases the economic viability of the technology.

The first good news is that for many practical cases, full packet capture is not necessary. This rationale stems from the well-known law of heavy tailed traffic: from an analysis standpoint, most of the interesting features found in network traffic—such as a network attack, although not limited to it—are found in a very small fraction of it. Further, in some cases full packet capture is not only unnecessary but could represent a liability as sensitive information is kept in non-ephemeral storage. The second good news is that all the heavy lifting done by Zeek in processing network traffic can be leveraged to overcome both the intractability and the liability problems. Indeed, Zeek can be brought into the loop to perform selective packet capture (SPC), a process by which the Zeek workers themselves decide which traffic must be stored into disk in a selective and fine granular manner.

In this talk Reservoir Labs will present a workflow to perform selective packet capture using the Zeek sensor at very high speed rates. The workflow allows Zeek scripts to directly trigger packet captures based on the real time analysis of the traffic itself. We will describe key data structures needed to efficiently perform this task and introduce several Zeek scripts and use cases illustrating how SPC can be used to capture just the necessary packets to enable meaningful forensic analysis while minimizing the exposure to the liability risk.

Contact us to receive a copy of this presentation or for a demonstration.

A Pragmatic Approach of Determining Heavy-Hitter Traffic Thresholds

Publication Source: 2018 IEEE European Conference on Networks and Communications (EuCNC), Ljubljana, Slovania

Heavy-hitter flows or Cheetah Flows (CF), which are high-rate flows can result in increased packet losses and delay in general Internet traffic. A Cheetah Flow Traffic Engineering System (CFTES) is presented, which can dynamically compute a heavy-hitter or CF threshold using information from the general background traffic. The system works in conjunction with a Cheetah Flow Identification Network Function (CFINF) to detect CFs at high-link rates using an SDN controller for actions involving redirection of CFs to a lower priority scavenger queue.
Google Scholar    Article

Algorithms and Data Structures to Accelerate Network Analysis (Extended Version)

Publication Source: Elsevier: Future Generation Computer Systems Volume 86, September 2018

As the sheer amount of computer generated data continues to grow exponentially, new bottlenecks are unveiled that require rethinking our traditional software and hardware architectures. In this paper, we present five algorithms and data structures (long queue emulation, lockless bimodal queues, tail early dropping, LFN tables, and multiresolution priority queues) designed to optimize the process of analyzing network traffic. We integrated these optimizations on R-Scope, a high performance network appliance that runs the Bro network analyzer, and present benchmarks showcasing performance speed-ups of 5X at traffic rates of 10 Gbps.
Google Scholar    Article

A high-speed cheetah flow identification network function (CFINF)

Publication Source: 2017 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), Berlin, Germany

Cheetah flows, which are high-rate flows, can cause increased packet delays and losses in other flows. Leveraging the flexibility offered by the NFV paradigm, our proposed Cheetah Flow Identification Network Function (CFINF) uses a novel method in which a new measure, short-duration flight rate, which is the rate of a flight of packets received over a fixed (short) time interval, is computed and compared against a threshold to identify cheetah flows from packets mirrored to the CFINF by a router. A Cheetah Flow Traffic Engineering System (CFTES) and SDN controller use the CFINF-identified cheetah flow identifiers to set filter rules in the router to isolate cheetah-flow packets. We evaluated the CFINF on a commodity ×86 processor based server. When using 10 cores, CFINF could handle a 1-min 10-Gbps real Center for Applied Internet Data Analysis (CAIDA) traffic trace that contained 1.5M flows and 38M packets. To improve efficiency, we ran CFINF in an 8-core configuration. However, there were packet drops (max. rate of 0.036%) with this configuration. When we added an optimization, i.e., flows with only small packets were filtered out, the median number of CFINF-dropped packets fell by 83%, with only 10% loss in accuracy of reported cheetahs.
Google Scholar    Article

1 2 3 4