Static Linking: A Thing of the Past

Oftentimes, I am asked why I disapprove of static linking. The time has come for me to write an article about this issue and to propose a solution. Unfortunately, the great majority of programmers understand what static linking does and/or how it is used, but not its goals. In fact, people generally tend to take things for granted. Given that we live in an imperfect world, I would postulate that it is impossible to become a good programmer without being a freethinker as well.

That said, let's start by listing static linking's merits:

• It comes to the aid of build systems, helping them improve build times by avoiding unnecessary recompilations when the leaf dependencies of executable or shared object files have remained unchanged. (This also applies to relocatable files, but they invariably are mere mediators—including them on the list of virtues would result in circular logic.)
• When a common ABI (application binary interface) is employed, linking statically makes it possible for programs written in one language to execute code written in another without OS (operating system) intervention.
• It allows vendors to distribute closed-source libraries in the form of object files.

The former two points are of a technical nature, while the latter is of a political one. I will address them in the same order and then provide some extra criticism.

For those of you unfamiliar with the usual building process, here's a quick recap. In order to build a target, all of its dependencies must be up-to-date. If they are not, they, too, become targets—it's a recursive procedure on a DAG (directed acyclic graph), called chaining. Finally, to actually build a target, a set of rules must be executed. So far, so good.

A change in qux.c propagates throughout the DAG.

The foremost problem arises from the fact that starting at the translation unit level means we get a coarse-grained chain. Imagine changing qux.c in the above diagram, in a way that doesn't affect qux.o, such as adding a comment or modifying a routine qux.o doesn't call. As it can be seen, this would result in four extraneous targets—again, a recursive drill. For very large projects, build times can go through the roof because of this.

Courtesy of Randall Munroe.

Regarding this particular argument, I would like to point out that it's really the design of current build systems that is fundamentally flawed; static linking just happens to be the building block that facilitates the problem because object file time stamps alone do not hold any information regarding what was modified in a translation unit and what wasn't, nor about what in their dependencies targets rely upon.

At first glance, using static linking in order to connect code written in different languages seems like the way to go. Dynamic linking would be a workaround, while compiler-specific extensions would result in loss of portability. Although I have nothing to complain about regarding this specific practice, the penultimate paragraph discusses an issue that encompasses it.

While I may not be a huge fan of making sacrificial technical decisions for political gains, I recognize that different people have different needs. What would it take for me to accept static linking as a solution to the closed-source library distribution problem? Well, it would have to be the only realistic approach—it obviously isn't. Evidently, dynamic linking works just as well for libraries, if not better given its benefits in loading overhead and memory footprint.

Something else that static linking will screw up is micro-optimization, as this is much more difficult to get right at this stage in the building process. In particular, it will get in the way of the compiler deciding what should be inlined and what should not. Furthermore, because calling conventions are so rigid, it will also bungle register and/or stack allocation across object file boundaries.

What I advocate is whole-program compilation by compilers with translation caches; this would integrate the build system more tightly with the compiler, meaning better granularity in correctly choosing dependencies. One benefit is that, for clean builds, this strategy is capable of whole-program optimization. As for other builds, the amount of non-incremental compilation, which would likely result in more optimal code, can be constrained by the preferred compilation time; this should be particularly useful in JIT compilers, which could combine this idea with runtime profiling. If multiple languages are required, the ABI could define an IR (intermediate representation), perhaps bytecode.

New Heights in Quantum Cryptography

I recently came across this article, which reports a successful attempt to establish a quantum communication channel over a record distance of 144 km. I take this as a good indication that quantum cryptography may soon become practical, improving everyone's security and privacy. Of course, we should still be weary of borked implementations.

As you may already know, having a pair of entangled particles, one's state can be inferred just by observing the other's. Alas, this by itself is not useful for transmitting information, as the end points cannot decide what said state is (a no-communication theorem can be proved). We need to be a bit more creative.

During World War II, Claude Shannon proved that in order for a cipher to have perfect secrecy, the key needs to be at least as long as the plaintext. (His work was declassified only after the war, in 1949—even then, by mistake.) Although keys can sometimes be exchanged in advance, this is generally considered impractical because if two parties have a way of securely exchanging such large keys they should probably use it to exchange the messages instead.

It turns out that such a secure cipher had already been invented in 1882, when Frank Miller came up with the OTP (one-time pad), which is a symmetric-key algorithm that performs a bit-wise xor (exclusive or) operation on the plaintext and key (that is, E(k, m) = m ⊕ k and D(k, c) = c ⊕ k). However, as Joseph Mauborgne later realized, reusing keys in whole or in part, results in ciphertexts susceptible to attacks (because E(k, m₁) ⊕ E(k, m₂) = m₁ ⊕ m₂, on which a number of attacks are possible). Although incepted much later, this is one of the vulnerabilities of WEP (Wired Equivalent Privacy).

	⊕		=
				⊕
	⊕		=
				=

(As an aside, I was taken slightly aback by learning that the symbol for the xor operation has not been standardized by ISO 80000-2.)

Unfortunately, the OTP had been forgotten until 2011, when Steven Bellovin found it in an old telegraph codebook. It was only in 1919, over three and a half decades after Miller's original invention, that Gilbert Vernam issued a patent that used a very similar idea. Vernam ciphers, like the aforementioned WEP, lie at the intersection of stream ciphers and the OTP: the only difference between them and the latter is that their plaintext-sized keystream is generated by a PRNG (pseudorandom number generator), where the seed is usually a password. Due to the fact that the seed is almost always very small compared to the message, the key space is almost always much smaller than the message space. Thus, stream ciphers strive for semantic security rather than perfect secrecy.

Vernam's proposed implementation.

The exact definition of semantic security, as introduced by Shafi Goldwasser and Silvio Micali, is a bit convoluted so I won't go into it here further than to say that, knowing some bits of the key, adversaries must be unable to guess in polynomial time what any of the other ones are, with a probability greater than 1/2 + ϵ, where ϵ is a negligible value. To achieve this, a special class of PRNG's, known as CSPRNG's (cryprographically secure PRNG's), must be employed. The definition of CSPRNG security is even more flaky, given that it is based on our guess of the lack of efficient adversaries, whose nonexistence we have yet to prove.

Note that nothing in the above paragraph is specific to stream ciphers, as all classical, elliptic, and hyperelliptic curve cryptography is based on the idea that adversaries must be able to solve a hard problem, such as factorization, in order to beat a semantically secure cipher. If we took out the requirement for efficiency, the hypothesis would become unsatisfiable (unlike your mom). Moreover, a proof that efficient CSPRNG adversaries exist would be quite surprising, as it would imply that P = NP (P vs NP, originally posed by Kurt Gödel in a letter to John von Neumann but introduced independently to the world by Stephen Cook in 1971, is the most important open problem in theoretical computer science; it's one of the Millenium Prize Problems).

Courtesy of Randall Munroe.

Quantum entanglement is so seductive for our purposes because of QKD (quantum key distribution): it allows establishing secure communication channels for transmitting large keys, meaning that we can switch from semantic security to perfect secrecy. As for keystream generation, quantum mechanics also helps us make the shift from PRNG's to RNG's. Furthermore, eavesdropping implies measuring the system and thus disturbing it, as per Heisenberg's uncertainty principle. A minor downside is that both parties will have to simultaneously be online.

I'd like to end this post with the observation that a system is like a chain: as secure as its weakest link. Current cryptographic constructions are typically the strongest link. This begs the question: Is there more to quantum cryptography than just the intellectual appeal? I will try to make a case for this in a future post.

Foreword

Hi,

Some of you may already know me by my screen name, Love4Boobies, from communities such as the Austin Group (the committee in charge of standardizing the UNIX System), OSDev.org (a community of hobby OS developers), Freenode (a technology-oriented IRC server), etc.

Courtesy of Randall Munroe.

I've started this blog for two reasons: first, because I've promised numerous folks that I would document some of my numerous software and hardware projects (please bear with me—as you may already know, the majority of them end up on the back burner after a while, as I keep getting distracted by the next exciting thing); secondly, to write about things that I think are interesting as I undergo my own explorations of philosophy, logic, mathematics, computer science, and computer engineering.

Don't worry if any of these doesn't fall under your area of expertise. I will try my best to write for a wider audience. So long as you're a geek, like me, you should be fine. :-)

Cheers,
Bogdan

PS: This is not a place of free expression—comments shall be moderated. I will only accept constructive criticism, valuable suggestions, pertinent questions phrased in accordance with these rules, remarks that I feel have the potential to carry the discussion forward, and... maybe praise. :-)