Abstract:

In shared environments such as operating systems, servers (databases, key-value stores), and hypervisors, multiple tenants with varied requirements compete to access the shared resources, making strong performance isolation necessary. Locks are widely used synchronization primitives that provide mutual exclusion in such environments. This dissertation focuses on the concurrency issues arising from sharing synchronization primitives amongst multiple tenants.

Shared data structures change as multiple tenants execute their workloads. These state changes can lead to a situation where the critical section sizes vary significantly. In this dissertation, we ask the following question: what happens to performance and fairness when a single lock protects variable-sized critical sections?

To answer the above question, in the first part of this dissertation, we introduce the idea of lock usage that deals with the time spent in the critical section. We then study unfair lock usage in benign and hostile settings. For benign settings, unfair lock usage can lead to a new problem called scheduler subversion where the lock usage patterns determine which thread runs instead of the CPU scheduler. In a hostile setting, unfair lock usage can lead to a new problem we call adversarial synchronization. Using Linux containers, we introduce a new class of attacks — synchronization attacks — that exploit kernel synchronization to harm application performance. Furthermore, a subset of these attacks — framing attacks — persistently harm performance by expanding data structures even after the attacker quiesces. We demonstrate three such attacks on the Linux kernel, where an unprivileged attacker can target the inode cache, the directory cache, and the futex table.

In the second part of the dissertation, to mitigate scheduler subversion, we introduce Scheduler-Cooperative Locks (SCLs), a new family of locking primitives that control lock usage and aligns with system-wide scheduling goals; our initial work focuses on proportional share schedulers. Unlike existing locks, SCLs provide an equal or proportional time window called lock opportunity within which each thread can acquire the lock one or more times. We design and implement three different SCLs — a user-level mutex lock (u-SCL), a reader-writer lock (RW-SCL), and a simplified kernel implementation (k-SCL).Our evaluation shows that SCLs are efficient and achieve high performance with minimal overhead under extreme workloads. We port SCLs in two user-space applications (UpScaleDB and KyotoCabinet) and the Linux kernel to show SCLs can guarantee equal or proportional lock opportunity regardless of the lock usage patterns.

In the third part of the dissertation, to mitigate adversarial synchronization, we design Trātṛ, a Linux kernel extension. Trātṛ can detect and mitigate synchronization and framing attacks with low overhead, prevent attacks from worsening, and recover by repairing data structures to their pre-attack performance. Trātṛ comprises four mechanisms: tracking, detection, prevention, and recovery. Our evaluation shows that Trātṛ can detect an attack within seconds, recover instantaneously while guaranteeing similar performance to baseline, and detect simultaneous attacks.

Full Paper: PDF   BibTeX

Publications