The Discrepancy of the Megaflow Cache in OVS, Final Episode
Speakers: Levente Csikor, National University of Singapore; Vipul Ujawanae, IIT Kharagpur; and Dinil Mon Divakaran, Trustwave
In the previous talks, we demonstrated that the Tuple Space Search (TSS) scheme, used for packet classification algorithm in the MegaFlow Cache (MFC) of OVS, has an algorithmic deficiency that can be abused by an attacker in different ways by pushing this generally high performing packet classifier to its corner case of degraded performance. We called this attack as Tuple Space Explosion (TSE). In TSE, a legitimately looking low-rate attack traffic (with no particular pattern) inflates the tuple space making the cardinal linear search process in TSS to spend an unaffordable time for classifying each packet; this eventually leads to a complete denial-of-service (DoS) for the users [2].
In the first part [4], we focused on a limited attack scenario. In particular, we demonstrated that for each set of flow rules, e.g., Access Control Lists (ACL), there exists a well-engineered traffic trace from which almost every packet creates a new tuple. We showed that the basic Whitelist+DefaultDeny ACLs tenants are typically given as default in cloud systems are particularly vulnerable. However, in order to carry out this attack, the adversary has to have access to or knowledge of the installed ACLs.
In Part II [3], we analyzed that when the attacker is not aware of the ACL, to what extent a randomized traffic trace can inflate the tuple space. Particularly, we showed that with less than 7 Mbps attack rate, significant degradation of 88% could be achieved.
Both works above, however, had one crucial aspect in common. We focused on one type of datapath, exclusively, namely the kernel datapath installed by the underlying system’s own packet manager. In many real-world (production) environments, administrators simply rely on the built-in software tools to install applications to reduce or even completely avoid all the crux around manual installations and compilations from source code, e.g., via apt-get install openvswitch-common in Debian-based Linux distributions. Even though in most of the cases, we eventually end up having the same application with negligible (performance) difference, when applications also have modules supplied by the underlying kernel (e.g., in the case of Open vSwitch since the Linux 3.3 kernel debut in 2012 [5]), there can be significant deviations among the implementations. In particular, as it turned out after the discussions (with some of the OVS developers) during our previous talks, (i) the kernel networking stack developers do not prefer exact flow caching; therefore, the kernel datapath of OVS lacks the first-level Exact Match Cache (EMC). This means that the whole fast-path only comprises the MFC, thereby making TSE more efficient. On the other hand, (ii) while the userspace datapath provided by Intel’s DPDK significantly improves the packet processing performance (by avoiding context-switching, interrupt-based packet handling, and the side-effects of OS schedulers), it essentially shares the same code base, and most parts of the algorithms are implemented according to the same original design.
[1] B. Bodireddy and A. Fischetti, OVS-DPDK Datapath Classifier, Intel Blogpost, https://intel.ly/3kCbIi8, October 2016 [Accessed: Oct 2020].
[2] L. Csikor, D. M. Divakaran, M. S. Kang, A. Korosi, B. Sonkoly, D. Haja, D. P. Pezaros, S. Schmid, and G. Rétvári, Tuple Space Explosion: A Denial-of-Service Attack Against a Software Packet Classifier In ACM CoNEXT 2019, Dec 2019.
[3] L. Csikor, M. S. Kang, and D. M. Divakaran, The Discrepancy of the Megaflow Cache in OVS, Part II., Full talk at OVS+OVN Conference, https://bit.ly/2SsfGh7, Dec. 2019.
[4] L. Csikor and G. Rétvári, The Discrepancy of the Megaflow Cache in OVS, Full talk at OVS Fall Conference, https://bit.ly/30A5qb9, Dec. 2018.
[5] S. M. Kerner, Open vSwitch (OVS) Becomes a Linux Foundation Collaborative Project, Aug 2016 [Accessed: Jun 2020].
by Open vSwitch
linux foundation
