Time protection: the missing OS abstraction
Time protection: the missing OS abstraction Ge et al., EuroSys’19
Ever since the prominent emergence of timing-based microarchitectural attacks (e.g. Spectre, Meltdown, and friends) I’ve been wondering what we can do about them. When a side-channel is based on observing improved performance, a solution that removes the improved performance can work, but is clearly undesirable. In today’s paper choice, for which the authors won a best paper award at EuroSys’19 last month, Ge et al., set out a principled basis for protecting against this class of attacks. Just as today’s systems offer memory protection, they call this time protection. The paper sets out what we can do in software given today’s hardware, and along the way also highlights areas where cooperation from hardware will be needed in the future.
Timing channels, and in particular microarchitectural channels, which exploit timing variations due to shared use of caches and other hardware, remain a fundamental OS security challenge that has eluded a comprehensive solution to date… We argue that it is time to take temporal isolation seriously, and make the OS responsible for time protection, the prevention of temporal inference, just as memory protection prevents spatial inference.
Master of web puppets: abusing web browsers for persistent and stealthy computation
Master of web puppets: abusing web browsers for persistent and stealthy computation Papadopoulus et al., NDSS’19
You’ve probably heard about crypto-currency mining and the like in hijacked browsers.
From a security perspective, a fundamental problem of web applications is that by default their publisher is considered as trusted, and thus allowed to run JavaScript code (even from third parties) on the user side without any restrictions… On the positive side JavaScript execution so far has been constrained chronologically to the lifetime of the browser window or tab that rendered the compromised or malicious website.
Not any more! This paper shows how modern browsers with support for Service Workers can be stealthily connected into a botnet, with a connection that persists until the user closes the browser completely: “in contrast to previous approaches for browser hijacking, a key feature of MarioNet is that it remains operational even after the user browses away from the malicious webpage.”
MarioNet building blocks: Service Workers and WebRTC
Service Workers are non-blocking modules that reside in the user’s browser. Once registered they can run in the background without requiring the user to continue browsing on the originating site. In addition, service workers have Continue reading
Don’t trust the locals: investigating the prevalence of persistent client-side cross-site scripting in the wild
Don’t trust the locals: investigating the prevalence of persistent client-side cross-site scripting in the wild Steffens et al., NDSS’19
Does your web application make use of local storage? If so, then like many developers you may well be making the assumption that when you read from local storage, it will only contain the data that you put there. As Steffens et al. show in this paper, that’s a dangerous assumption! The storage aspect of local storage makes possible a particularly nasty form of attack known as a persistent client-side cross-site scripting attack. Such an attack, once it has embedded itself in your browser one time (e.g. that one occasion you quickly had to jump on the coffee shop wifi), continues to work on all subsequent visits to the target site (e.g., once you’re back home on a trusted network).
In an analysis of the top 5000 Alexa domains, 21% of sites that make use of data originating from storage were found to contain vulnerabilities, of which at least 70% were directly exploitable using the models described in this paper.
Our analysis shows that more than 8% of the top 5,000 domains are potentially susceptible to a Continue reading
How bad can it git? Characterizing secret leakage in public GitHub repositories
How bad can it git? Characterizing secret leakage in public GitHub repositories Meli et al., NDSS’19
On the one hand you might say there’s no new news here. We know that developers shouldn’t commit secrets, and we know that secrets leaked to GitHub can be discovered and exploited very quickly. On the other hand, this study goes much deeper, and also provides us with some very actionable information.
…we go far beyond noting that leakage occurs, providing a conservative longitudinal analysis of leakage, as well as analyses of root causes and the limitations of current mitigations.
In my opinion, the best time to catch secrets is before they are ever committed in the first place. A git pre-commit hook using the regular expressions from this paper’s appendix looks like a pretty good investment to me. The pre-commit hook approach is taken by TruffleHog, though as of the time this paper was written, TruffleHog’s secret detection mechanisms were notably inferior (detecting only 25-29%) to those developed in this work (§ VII.D). You might also want to look at git-secrets which does this for AWS keys, and is extensible with additional patterns. For a belt and braces approach, also Continue reading
Ginseng: keeping secrets in registers when you distrust the operating system
Ginseng: keeping secrets in registers when you distrust the operating system Yun & Zhong et al., NDSS’19
Suppose you did go to the extreme length of establishing an unconditional root of trust for your system, even then, unless every subsequent piece of code you load is also fully trusted (e.g., formally verified) then you’re open to post-boot attacks. This is especially true in a context where lots of third-party application code (e.g. apps on a mobile phone) gets loaded.
Many mobile and IoT apps nowadays contain sensitive data, or secrets, such as passwords, learned models, and health information. Such secrets are often protected by encryption in the storage. However, to use a secret, an app must decrypt it and usually store it as cleartext in memory. In doing so, the app assumes that the operating system (OS) is trustworthy. OSes are complex software and have a large attack surface… Increasingly abundant evidence suggests that prudent apps should not trust the OS with their secrets.
Instead of trying to protect absolutely everything, Ginseng assumes that some data matters more than others. It arranges things such that this sensitive data is only ever in the clear in registers Continue reading
Establishing software root of trust unconditionally
Establishing software root of trust unconditionally Gligor & Woo, NDSS’19
The authors won a best paper award for this work at NDSS this year. The main result is quite something, but as you might expect the lines of argument are detailed and not always easy to follow (and certainly not critically!) for non-experts like me. I’ll use today’s write-up to convey the big ideas as I understand them. Close reading of the original paper (and it’s accompanying technical report) will be essential if you then want to dig deeper.
The problem: establishing a root of trust
Root of trust (RoT) establishment on an untrusted system ensures that a system state comprises all and only content chosen by the user, and the user’s code begins execution in that state. All implies that no content is missing, and only that no extra content exists. If a system state is initialized to content that satisfies security invariants and RoT establishment succeeds, a user’s code begins execution in a secure initial state.
That is to say, even in the presence of persistent malware e.g. in the firmware of peripheral controllers, network interface cards, disk and USB controllers, and so on, root of Continue reading
The crux of voice (in)security: a brain study of speaker legitimacy detection
The crux of voice (in)security: a brain study of speaker legitimacy detection Neupane et al., NDSS’19
The key results of this paper are easy to understand, but the implications are going to take us a long time to unravel. Speech morphing (voice morphing) is the process of translating a speaker’s voice to sound like a given impersonation target. This capability is now available off-the-shelf —this paper uses the CMU Festvox voice converter— and is getting better all the time. Being able to impersonate someone’s voice takes things like social engineering attacks to a whole new level…
…voice imitation is an emerging class of threats, especially given the advancement in speech synthesis technology seen in a variety of contexts that can harm a victim’s reputation and her security/safety. For instance, the attacker could publish the morphed voice samples on social media, impersonate the victim in phone conversations, leave fake voice messages to the victim’s contacts, and even launch man-in-the-middle attacks against end-to-end encryption technologies that require users to verify the voices of the callers, to name a few instances of such attacks.
So voice should sit alongside images and video as a source we can’t trust in our new Continue reading
Calvin: fast distributed transactions for partitioned database systems
Calvin: fast distributed transactions for partitioned database systems Thomson et al., SIGMOD’12
Earlier this week we looked at Amazon’s Aurora. Today it’s the turn of Calvin, which is notably used by FaunaDB (strictly “_FaunaDB uses patent-pending technology inspired by Calvin…”). As the paper title suggests, the goal of Calvin is to put the ACID back into distributed databases. I’ve put these systems back-to-back because they are both vying for attention in the serverless world, but note that really this is an apples-to-oranges thing as Aurora scales out MySQL and PostgreSQL with single writer multi-reader models, whereas Calvin supports distributed transactions over distributed databases. A closer comparison with Calvin in the AWS world would be DynamoDB, which recently added limited transaction support (single region tables). Calvin is more commonly compared against Google’s Spanner. See Daniel Abadi on this topic (note that Abadi is one of the authors of the Calvin paper, and an advisor to FaunaDB), and also on “It’s time to move on from two-phase commit.”
Calvin [is] a transaction processing and replication layer designed to transform a generic, non-transactional, un-replicated data store into a fully ACID, consistently replicated distributed database system. Calvin supports horizontal scalability Continue reading
Amazon Aurora: on avoiding distributed consensus for I/Os, commits, and membership changes
Amazon Aurora: on avoiding distributed consensus for I/Os, commits, and membership changes, Verbitski et al., SIGMOD’18
This is a follow-up to the paper we looked at earlier this week on the design of Amazon Aurora. I’m going to assume a level of background knowledge from that work and skip over the parts of this paper that recap those key points. What is new and interesting here are the details of how quorum membership changes are dealt with, the notion of heterogeneous quorum set members, and more detail on the use of consistency points and the redo log.
Changing quorum membership
Managing quorum failures is complex. Traditional mechanisms cause I/O stalls while membership is being changed.
As you may recall though, Aurora is designed for a world with a constant background level of failure. So once a quorum member is suspected faulty we don’t want to have to wait to see if it comes back, but nor do we want throw away the benefits of all the state already present on a node that might in fact come back quite quickly. Aurora’s membership change protocol is designed to support continued processing during the change, to tolerate additional failures while Continue reading
Amazon Aurora: design considerations for high throughput cloud-native relational databases
Amazon Aurora: design considerations for high throughput cloud-native relational databases Verbitski et al., SIGMOD’17
Werner Vogels recently published a blog post describing Amazon Aurora as their fastest growing service ever. That post provides a high level overview of Aurora and then links to two SIGMOD papers for further details. Also of note is the recent announcement of Aurora serverless. So the plan for this week on The Morning Paper is to cover both of these Aurora papers and then look at Calvin, which underpins FaunaDB.
Say you’re AWS, and the task in hand is to take an existing relational database (MySQL) and retrofit it to work well in a cloud-native environment. Where do you start? What are the key design considerations and how can you accommodate them? These are the questions our first paper digs into. (Note that Aurora supports PostgreSQL as well these days).
Here’s the starting point:
In modern distributed cloud services, resilience and scalability are increasingly achieved by decoupling compute from storage and by replicating storage across multiple nodes. Doing so lets us handle operations such as replacing misbehaving or unreachable hosts, adding replicas, failing over from a writer to a replica, scaling the size Continue reading
Slim: OS kernel support for a low-overhead container overlay network
Slim: OS kernel support for a low-overhead container overlay network Zhuo et al., NSDI’19
Container overlay networks rely on packet transformations, with each packet traversing the networking stack twice on its way from the sending container to the receiving container.
There are CPU, throughput, and latency overheads associated with those traversals.
In this paper, we ask whether we can design and implement a container overlay network, where packets go through the OS kernel’s network stack only once. This requires us to remove packet transformation from the overlay network’s data-plane. Instead, we implement network virtualization by manipulating connection-level metadata at connection setup time, saving CPU cycles and reducing packet latency.
Slim comes with some caveats: it requires a kernel module for secure deployment, has longer connection establishment times, doesn’t fit with packet-based network policies, and only handles TCP traffic. For UDP, ICMP, and for its own service discovery, it also relies on an existing container overlay network (Weave Net). But for longer lasting connections managed using connection-based network policies it delivers some impressive results:
- memcached throughput up by 71%, with latency reduced by 42%, and CPU utilisation reduced by 56%.
- Nginx CPU utilisation reduced by 22-24%
- PostgreSQL Continue reading
Understanding lifecycle management complexity of datacenter topologies
Understanding lifecycle management complexity of datacenter topologies Zhang et al., NSDI’19
There has been plenty of interesting research on network topologies for datacenters, with Clos-like tree topologies and Expander based graph topologies both shown to scale using widely deployed hardware. This research tends to focus on performance properties such as throughput and latency, together with resilience to failures. Important as these are, note that they’re also what’s right in front of you as a designer, and relatively easy to measure. The great thing about today’s paper is that the authors look beneath the surface to consider the less visible but still very important “lifecycle management” implications of topology design. In networking, this translates into how easy it is to physically deploy the network, and how easy it to subsequently expand. They find a way to quantify the associated lifecycle management costs, and then use this to help drive the design of a new class of topologies, called FatClique.
… we show that existing topology classes have low lifecycle management complexity by some measures, but not by others. Motivated by this, we design a new class of topologies, FatClique, that, while being performance-equivalent to existing topologies, is comparable to, or Continue reading
Datacenter RPCs can be general and fast
Datacenter RPCs can be general and fast Kalia et al., NSDI’19
We’ve seen a lot of exciting work exploiting combinations of RDMA, FPGAs, and programmable network switches in the quest for high performance distributed systems. I’m as guilty as anyone for getting excited about all of that. The wonderful thing about today’s paper, for which Kalia et al. won a best paper award at NSDI this year, is that it shows in many cases we don’t actually need to take on that extra complexity. Or to put it another way, it seriously raises the bar for when we should.
eRPC (efficient RPC) is a new general-purpose remote procedure call (RPC) library that offers performance comparable to specialized systems, while running on commodity CPUs in traditional datacenter networks based on either lossy Ethernet or lossless fabrics… We port a production grade implementation of Raft state machine replication to eRPC without modifying the core Raft source code. We achieve 5.5 µs of replication latency on lossy Ethernet, which is faster than or comparable to specialized replication systems that use programmable switches, FPGAs, or RDMA.
eRPC just needs good old UDP. Lossy Ethernet is just fine (no need for fancy lossness Continue reading
Exploiting commutativity for practical fast replication
Exploiting commutativity for practical fast replication Park & Ousterhout, NSDI’19
I’m really impressed with this work. The authors give us a practical-to-implement enhancement to replication schemes (e.g., as used in primary-backup systems) that offers a signification performance boost. I’m expecting to see this picked up and rolled-out in real-world systems as word spreads. At a high level, CURP works by dividing execution into periods of commutative operation where ordering does not matter, punctuated by full syncs whenever commutativity would break.
The Consistent Unordered Replication Protocol (CURP) allows clients to replicate requests that have not yet been ordered, as long as they are commutative. This strategy allows most operations to complete in 1 RTT (the same as an unreplicated system).
When integrated with RAMCloud write latency was improved by ~2x, and write throughput by 4x. Which is impressive given that RAMCloud isn’t exactly hanging around in the first place! When integrated with Redis, CURP was able to add durability and consistency while keeping similar performance to non-durable Redis.
CURP can be easily applied to most existing systems using primary-backup replication. Changes required by CURP are not intrusive, and it works with any kind of backup mechanism (e.g., Continue reading
Cloud computing simplified: a Berkeley view on serverless computing
Cloud programming simplified: a Berkeley view on serverless computing Jonas et al., arXiv 2019
With thanks to Eoin Brazil who first pointed this paper out to me via Twitter….
Ten years ago Berkeley released the ‘Berkeley view of cloud computing’ paper, predicting that cloud use would accelerate. Today’s paper choice is billed as its logical successor: it predicts that the use of serverless computing will accelerate. More precisely:
… we predict that serverless computing will grow to dominate the future of cloud computing.
The acknowledgements thank reviewers from Google, Amazon, and Microsoft among others, so it’s reasonable to assume the major cloud providers have had at least some input to the views presented here. The discussion is quite high level, and at points it has the feel of a PR piece for Berkeley (there’s even a cute collective author email address: serverlessview at berkeley.edu), but there’s enough of interest in its 35 pages for us to get our teeth into…
The basic structure is as follows. First we get the obligatory attempt at defining serverless, together a discussion of why it matters. Then the authors look at some of the current limitations (cf. ‘Serverless Continue reading
Efficient synchronisation of state-based CRDTs
Efficient synchronisation of state-based CRDTs Enes et al., arXiv’18
CRDTs are a great example of consistency as logical monotonicity. They come in two main variations:
- operation-based CRDTs send operations to remote replicas using a reliable dissemination layer with exactly-once causal delivery. (If operations are idempotent then at-least-once is ok too).
- state-based CRDTs exchange information about the resulting state of the data structure (not the operations that led to the state being what it is). In the original form the full-state is sent each time. State-based CRDTs can tolerate dropped, duplicated, and re-ordered messages.
State-based CRDTs look attractive therefore, but over time as the state grows sending the full state every time quickly becomes expensive. That’s where Delta-based CRDTs come in. These send only the delta to the state needed to reconstruct the full state.
Delta-based CRDTs… define delta-mutators that return a delta (
), typically much smaller than the full state of the replica, to be merged with the local state. The same
buffer, to be periodically propagated to remote replicas. Delta-based CRDTs have been adopted in industry as part of the Akka Distributed Data framework and IPFS.
), typically much smaller than the full state of the replica, to be merged with the local state. The same 
buffer, to be periodically propagated to remote replicas. Delta-based CRDTs have been adopted in industry as part of the Akka Distributed Data framework and IPFS.So far so good, but Continue reading
A generalised solution to distributed consensus
A generalised solution to distributed consensus Howard & Mortier, arXiv’19
This is a draft paper that Heidi Howard recently shared with the world via Twitter, and here’s the accompanying blog post. It caught my eye for promising a generalised solution to the consensus problem, and also for using reasoning over immutable state to get there. The state maintained at each server is monotonic.
Consensus is a notoriously hard problem, and Howard has been deep in the space for several years now. See for example the 2016 paper on Flexible Paxos. The quest for the holy grail here is to find a unifying and easily understandable protocol that can be instantiated in different configurations allowing different trade-offs to be made according to the situation.
This paper re-examines the problem of distributed consensus with the aim of improving performance and understanding. We proceed as follows. Once we have defined the problem of consensus, we propose a generalised solution to consensus that uses only immutable state to enable more intuitive reasoning about correctness. We subsequently prove that both Paxos and Fast Paxos are instances of our generalised consensus algorithm and thus show that both algorithms are conservative in their approach.
The Continue reading
Keeping CALM: when distributed consistency is easy
Keeping CALM: when distributed consistency is easy Hellerstein & Alvaro, arXiv 2019
The CALM conjecture (and later theorem) was first introduced to the world in a 2010 keynote talk at PODS. Behind its simple formulation there’s a deep lesson to be learned with the power to create ripples through our industry akin to the influence of the CAP theorem. It rewards time spent ruminating on the implications. Therefore I was delighted to see this paper from Hellerstein & Alvaro providing a fresh and very approachable look at CALM that gives us an excuse to do exactly that. All we need now is a catchy name for a movement! A CALM system is a NoCo system, “No Coordination.”
When it comes to high performing scalable distributed systems, coordination is a killer. It’s the dominant term in the Universal Scalability Law. When we can avoid or reduce the need for coordination things tend to get simpler and faster. See for example Coordination avoidance in database systems, and more recently the amazing performance of Anna which gives a two-orders-of-magnitude speed-up through coordination elimination. So we should avoid coordination whenever we can.
So far so good, but when exactly can we avoid Continue reading
Efficient large-scale fleet management via multi-agent deep reinforcement learning
Efficient large-scale fleet management via multi-agent deep reinforcement learning Lin et al., KDD’18
A couple of weeks ago we looked at a survey paper covering approaches to dynamic, stochastic, vehicle routing problems (DSVRPs). At the end of the write-up I mentioned that I couldn’t help wondering about an end-to-end deep learning based approach to learning policy as an alternative to the hand-crafted algorithms. Lenz Belzner popped up on Twitter to point me at today’s paper choice, which investigates exactly that.
The particular variation of DSVRP studied here is grounded in a ride-sharing platform with real data provided by Didi Chuxing covering four weeks of vehicle locations and trajectories, and customer orders, in the city of Chengdu. With the area covered by 504 hexagonal grid cells, the centres of which are 1.2km apart, we’re looking at around 475 square kilometers. The goal is to reposition vehicles in the fleet at each time step (10 minute intervals) so as to maximise the GMV (total value of all orders) on the platform. We’re not given information on the number of drivers, passengers, and orders in the data set (nor on the actual GMV, all results are relative), but Chengdu has a Continue reading
Large scale GAN training for high fidelity natural image synthesis
Large scale GAN training for high fidelity natural image synthesis Brock et al., ICLR’19
Ian Goodfellow’s tweets showing x years of progress on GAN image generation really bring home how fast things are improving. For example, here’s 4.5 years worth of progress on face generation:
And here we have just two years of progress on class-conditional image generation:
In the case of the faces, that’s a GAN trained just to generate images of faces. The class-conditional GANs are a single network trained to generate images of lots of different object classes. In addition to feeding it some noise (random input), you also feed the generator network the class of image you’d like it to generate (condition it).
I was drawn to this paper to try and find out what’s behind the stunning rate of progress. The large-scale GANs (can I say LS-GAN?) trained here set a new state-of-the-art in class-conditional image synthesis. Here are some images generated at 512×512 resolution.
The class-conditional problem is of course much harder than the single image class problem, so we should expect the images to be not quite so stunning as the pictures of faces. In fact, using a measure called Continue reading