Uncovering a 24-year-old bug in the Linux Kernel
When one side’s receive buffer (Recv-Q) fills up (in this case because the rsync process is doing disk I/O at a speed slower than the network’s), it will send out a zero window advertisement, which will put that direction of the connection on hold. When buffer space eventually frees up, the kernel will send an unsolicited window update with a non-zero window size, and the data transfer continues. To be safe, just in case this unsolicited window update is lost, the other end will regularly poll the connection state using the so-called Zero Window Probes (the persist mode we are seeing here).
Apparently, the bug was in the bulk receiver fast-path, a code path that skips most of the expensive, strict TCP processing to optimize for the common case of bulk data reception. This is a significant optimization, outlined 28 years ago² by Van Jacobson in his “TCP receive in 30 instructions” email. Apparently the Linux implementation did not update snd_wl1 while in the receiver fast path. If a connection uses the fast path for too long, snd_wl1 will fall so far behind that ack_seq will wrap around with respect to it. And if this happens while the receive window is zero, there is no way to re-open the window, as demonstrated above. What’s more, this bug had been present in Linux since v2.1.8, dating back to 1996!
The Design of the Roland Juno oscillators
This article is a comprehensive guide to the Roland Juno’s digitally-controlled analog oscillators (DCOs). I fell in love with the Juno early in my synthesizer journey and I’ve spent the last year or so doing research on its design so that I could create my own Juno-inspired DCO, Winterbloom’s Castor & Pollux.
PLATYPUS With Great Power comes Great Leakage
With classical power side-channel attacks, an adversary typically attaches an oscilloscope to monitor the energy consumption of a device. Since Intel Sandy Bridge CPUs, the Intel Running Average Power Limit (RAPL) interface allows monitoring and controlling the power consumption of the CPU and DRAM in software. Hence, the CPU basically comes with its own power meter. With the current implementation of the Linux driver, every unprivileged user has access to its measurements.
Using PLATYPUS, we demonstrate that we can observe variations in the power consumption to distinguish different instructions and different Hamming weights of operands and memory loads, allowing inference of loaded values. PLATYPUS can further infer intra-cacheline control flow of applications, break KASLR, leak AES-NI keys from Intel SGX enclaves and the Linux kernel, and establish a timing-independent covert channel.
With SGX, Intel released a security feature to create isolated environments, so-called enclaves, that are secure even if the operating system is compromised. In our work, we combine PLATYPUS with precise execution control of SGX-Step. As a result, we overcome the hurdle of the limited measuring capabilities of Intel RAPL by repeatedly executing single instructions inside the SGX enclave. Using this technique, we recover RSA keys processed by mbed TLS from an SGX enclave.
Rainbow – an attempt to display colour on a B&W monitor
The aim of this project was to display a colour image on a black and white monitor, by overlaying an acetate bayer filter over the monitor and mosaicing a colour image.
SAT solver on top of regex matcher
A SAT problem is an NP-problem, while regex matching is not. However, a quite popular regex ‘backreferences’ extension extends regex matching to a (hard) NP-problem.
KVM host in a few lines of code
KVM is a virtualization technology that comes with the Linux kernel. In other words, it allows you to run multiple virtual machines (VMs) on a single Linux VM host. VMs in this case are known as guests. If you ever used QEMU or VirtualBox on Linux - you know what KVM is capable of.
But how does it work under the hood?
The Success and Failure of Ninja
Ninja has been by far my most successful open source project, depending on how you quantify success. (Other projects of mine like Chrome have more users, but I was responsible for only parts of Chrome; Ninja also has had important contributions by collaborators but it feels more like “mine”.) I released Ninja in 2011, gave ownership of the Ninja project away in 2014, and it has since been passed on again to a third maintainer, so now that my part in the story is pretty much over I here would like to reflect on what I learned.
Ten Lessons I Wish I Had Learned Before I Started Teaching Differential Equations
One of many mistakes of my youth was writing a textbook in ordinary differential equations. It set me back several years in my career in mathematics. However, it had a redeeming feature: it led me to realize that I had no idea what a differential equation is. The more I teach differential equations, the less I understand the mystery of differential equations.
Introducing Glush: a robust, human readable, top-down parser compiler
It’s been 45 years since Stephen Johnson wrote Yacc (Yet another compiler-compiler), a parser generator that made it possible for anyone to write fast, efficient parsers. Yacc, and its many derivatives, quickly became popular and were included in many Unix distributions. You would imagine that in 45 years we would have further perfected the art of creating parsers and would have standardized on a single tool. A lot of progress has been made, but there are still annoyances and problems affecting every tool out there.
This is great, even just for the overview of parsing.
The CYK algorithm (named after Cocke–Younger–Kasami) is in my opinion of great theoretical importance when it comes to parsing context-free grammars. CYK will parse all context-free parsers in O(n3), including the “simple” grammars that LL/LR can parse in linear time. It accomplishes this by converting parsing into a different problem: CYK shows that parsing context-free languages is equivalent to doing a boolean matrix multiplication. Matrix multiplication can be done naively in cubic time, and as such parsing context-free languages can be done in cubic time. It’s a very satisfying theoretical result, and the actual algorithm is small and easy to understand.
The history of Tetris randomizers
In Tetris, a randomizer is a function which returns a randomly chosen piece. Over the years, the rules of how pieces are chosen has evolved, affecting gameplay and actual randomness.
Several of them have been reversed engineered and documented. I’ve curated a list of ones that I believed to be important and show how the state of Tetris has changed over the years.
Running from the past
Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It’s a change of perspective that can have a big impact on how we reason about our code. But it’s also a change of perspective that can be useful in mathematics and I’d like to give an example: a really beautiful technique that alows you to sample from the infinite limit of a probability distribution without needing an infinite number of operations.
Solving Rush Hour, the Puzzle
How I created a database of all interesting Rush Hour configurations.
Parsing: a timeline
The results of 1961 transformed the Operator Issue. Before ALGOL, parsing operator expressions essentially was parsing. After ALGOL, almost all languages will be block-structured and ad hoc string manipulatons are no longer adequate -- the language as a whole requires a serious parsing technique. Parsing operator expressions becomes a side show, or so it seems.
From Markov to now. With references.
CSS3 Patterns Gallery
Go & Versioning
We need to add package versioning to Go. More precisely, we need to add the concept of package versions to the working vocabulary of both Go developers and our tools, so that they can all be precise when talking to each other about exactly which program should be built, run, or analyzed. The go command needs to be able to tell developers exactly which versions of which packages are in a particular build, and vice versa.
Shortest Addition Chains
A finite sequence of positive integers a0, a1, ..., ar is called an addition chain iff for each element ai, but the first a0 which equals 1, there exist elements in the list with smaller indexes j and k such that ai = aj + ak.
Preciser this is called an addition chain of length r for its last number ar. It can be interpreted like calculating n = ar starting from 1 by addition of only previous calculated numbers.
Social Decay: Illustrations by Andrei Lacatusu
Photo realistic images of company logos as abandoned diner signs.
A Water-based Solution of Polynomial Equations
Quinto: Resurrecting an Abandoned Board Game
Quinto is basically Scrabble, except with numbers instead of letters.