GPS is perhaps one of the most audacious geo-engineering feats ever undertaken, and its traces can be felt with just an antenna and a motive.

All that said, it’s not as though there’s a cacophony of navigation data swarming around you, deafening if you could just hear it. In reality, the GPS signals surrounding you are astoundingly weak. To take an analogy: imagine a normal light bulb, like the one that might be above you now. Pull it twenty thousand kilometers away from the room you’re in, and have it flash, on, off, on, off, a million times a second. Imagine straining your eye to watch the shimmer of the bulb, two Earths away, and listen to what it’s telling you.

source: trivium

While looking through the fpng source code, I noticed that its vectorized adler32 implementation seemed somewhat complicated, especially given how simple the scalar version of adler32 is. I was curious to see if I could come up with a simpler method, and in doing so, I came up with an algorithm that can be up to 7x faster than fpng’s version, and 109x faster than the simple scalar version.

source: trivium

This is the story of how I figured out a way to turn my ThinkPad X1 Carbon 6th Gen laptop into a programmable USB device by enabling the xDCI controller.

As a result, the laptop can now be used to emulate arbitrary USB devices such as keyboards or storage drives. Or to fuzz USB hosts with the help of Raw Gadget and syzkaller. Or to even run Facedancer with the help of the Raw Gadget–based backend. And do all this without any external hardware.

The journey of enabling xDCI included fiddling with Linux kernel drivers, xHCI, DWC3, ACPI, BIOS/UEFI, Boot Guard, TPM, NVRAM, PCH, PMC, PSF, IOSF, and P2SB, and making a custom USB cable

source: trivium

Well, it’s 2024 and leap day has come once again. As I’ve done in prior leap years, I’ve captured as many bug reports and outages as I can, along with links to the source where possible.

source: trivium

And you know what’s special about 2040? It’s after 2038.

source: trivium

I really like the “tech debt” metaphor. A lot of people don’t, but I think that’s because they either don’t extend the metaphor far enough, or because they don’t properly understand financial debt.

Pretty good financial debt explainer, too.

source: trivium

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!

source: trivium

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.

source: trivium

Part of Computer Arithmetic. http://www.quadibloc.com/comp/cp02.htm

And How does a computer work? http://www.quadibloc.com/comp/cpint.htm

source: trivium

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.

source: trivium

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.

source: trivium

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.

source: trivium

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?

Also: https://lwn.net/Articles/658511/

source: trivium

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.

source: trivium

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.

source: trivium

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.

source: trivium

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.

source: trivium

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.

source: trivium

How I created a database of all interesting Rush Hour configurations.

source: trivium

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.

source: trivium