John Fremlin's blog

Bits of hash to avoid a clash

2012-01-05T06:41:04Z

Suppose you have n objects which you cannot for some reason index sequentially, but for each one you can create a hashed value, and instead of transmitting the objects you want when possible to transmit the hashed values, in order to save communication bandwidth. Now if the hashes have fewer bits than those necessary to encode all the possible objects there will certainly be collisions where a hash value does not uniquely identify an object. Suppose this is acceptable if the probability of collision is less than or equal to p. How many bits of a perfectly distributed hash does one need, or equivalently if the hash can take values from 0 to h-1 inclusive, how large should h be?

This is related to the birthday collision demonstration — in a classroom of children it is expected that two will share the same birthday.

The probability of no collision q = 1-p is 0 if h < n and otherwise the product (1 - k/h) for k from 1 to n. Now if we look at the powers of h, then this is 1 - n(n+1)/2h + a₂/h² - a₃/h³ + … where the coefficients a_i are functions of n. Now if we say that h > n(n+1) then we can show elementarily that a_i+1 < a_i by comparing the components of the constituent sum, so q > 1 - n²/2h.

Therefore given p = 1-q, the probability of collision we are willing to tolerate, we have h < n²/2p so we simply choose an h as large as n²/2p to keep us very safe.

WPA supplicant and TKIP pairwise cipher

2011-10-03T11:49:26Z

On some wifi routers, the CCMP WPA pairwise cipher does not work with wpa_supplicant, though the key is correct, but the TKIP cipher will work. The router advertises Pairwise Ciphers (2) : TKIP CCMP.

wpa_supplicant says

State: 4WAY_HANDSHAKE -> 4WAY_HANDSHAKE
WPA: RX message 1 of 4-Way Handshake from xx:xx:xx:xx:xx:xx (ver=2)
WPA: PTK derivation - A1=xx:xx:xx:xx:xx:xx A2=xx:xx:xx:xx:xx:xx
WPA: PMK - hexdump(len=32): [REMOVED]
WPA: PTK - hexdump(len=48): [REMOVED]
WPA: WPA IE for msg 2/4 - hexdump(len=24): 
WPA: Sending EAPOL-Key 2/4
Authentication with xx:xx:xx:xx:xx:xx timed out.

WPA: 4-Way Handshake failed - pre-shared key may be incorrect

To workaround, add pairwise=TKIP to the entry in wpa_supplicant.conf.

Designing user interfaces to computer systems

2011-09-27T02:51:39Z

It's hard to make a functional user interface and impossible to make one that delights everybody. Especially when designing a website there is a huge temptation to simply expose functionality in the easiest way possible. But this is backwards because probably a vast number of users will interact with the website and any unintuitive behaviour means they in the aggregate waste vast amounts of time.

Instead of exposing functionality in the easiest way, one should add expected behaviours — if the user presses the delete key, what should happen? If a user clicks on any part of the page, probably he or she some intent in mind and if one were watching, one could guess it. Guess ahead of time and add the behaviour! Each user action signifies an intent that it is unkind to ignore.

Doubling and shuffling grains to make a pile

2011-08-24T00:00:00Z

There is an old story that a munificent king demanded to bounteously reward a sage: the sage requested that the king give him one grain for the first square of the chess board, two grains for the second, four grains for the fourth, and so on doubling the amount each square. There being 64 squares on the chessboard the munificence of the monarch was exceeded and he beheaded the sage. Here is an even more dangerous mechanism which involves only six squares (piles) but vastly more than 2⁶⁴ profit.

Starting with an ordered set of n piles of grains, you can perform one of two moves: double a grain by removing one from a pile and adding two to the pile on the right of it, or shuffle by removing a grain and then swapping the positions of the two piles immediately on the right. The objective is to create as many grains as possible. Piles cannot be created, so the doubling move cannot be used on the rightmost pile, and the shuffling move cannot be used on the rightmost or the one just to the left of that. Given six piles each with a single grain, can you create exactly 2010^{2010²⁰¹⁰} grains?

This is IMO 2010 problem 5. It seems there are solutions all over the web now including at that polymath link; however, I'm not sure that they convey the glorious magnificence of the system.

Now suppose we define a function f(n, b, e) as the maximum number of grains that one can obtain with n piles, the leftmost containing b grains and the rightmost e grains, and all the rest empty. Surprisingly, this function grows very quickly in n, rather in the manner of Knuth's arrow operator.

Now f(1,h,h) = h, f(2, b, e) = 2b + e. The first indication of fun comes with f(3, b, e) ≥ 2^be or 2^b+1— with three piles, double all the grains in the middle pile into the right pile, then use the left pile to swap this pile back into the middle and double it again.

The real heart is that the swapping rule effectively allows a reapplication of the function f(n-1, ...) to its previous value. This can be extended to n > 3, provided b ≥ 2: spend one grain by doubling to the right and then using one of the new grains to double again to the right to fill the intervening piles with one grain each, and then use these grains to shuffle the pile at the end back into the second from leftmost position, and then use another grain in the leftmost to bring the pile into the first from leftmost. Therefore f(n,b,e) ≥ f(n,b-2,f(n-1,e+4,0)) for n ≥ 4 and b ≥ 2.

With six piles with a single grain 1 1 1 1 1 1, we initially double to get 2 2 2 0 7, then apply the exponential rule for n = 3 to get 2 2 0 0 28, and then the repeated exponential (tetration) rule for n = 4 to get 2 0 0 0 2³³, and then using the reapplication rule we have to evaluate 2³³+4 0 0 0, in comparison to our target of 2010^{2010²⁰¹⁰}. As we can waste grains by shuffling empty piles, we need not worry if we exceed the target.

In other words, we need to get a lower bound for the tetration f(4, 2³³+4, 0). This is by the reapplication rule greater than exponentiation repeated 2³² times, or 2 ↑ ↑ 2³² in Knuth's notation.

Is this clearly greater than c = 2010^{2010²⁰¹⁰}? Suppose we take log base 2. Then log₂ c < 11 2010²⁰¹⁰ and log₂ log₂ c < 4 + 11 . 2010 < 25 000.

But log₂ log₂ 2 ↑ ↑ 2³² is just 2 ↑ ↑ (2³² - 2) and 2 ↑ ↑ 4 > 65 000 so we have an scale of headroom that is difficult to relate to quantities in our universe.

From the two rules of moving and adding one to the right, and removing and shuffling, a system is created that makes more grains than one can comfortably represent with exponential notation. Amazing!

Thanks to David B for bringing the problem to my attention, it was a lot of fun, and many thanks to Rob Backhouse for proofreading and improving the method.

BTRFS hard links in the same directory limit is too small

2011-08-21T16:13:46Z

BTRFS is a next generation filesystem for Linux that has some pleasant features which set it apart from ext4. For example, checksums, snapshots, and online defragmentation. In many respects it is inspired by ZFS.

I was converting a filesystem from ext4 to btrfs when I came upon a problem: it seems that BTRFS supports only 256 hard-links for files in the same directory (that is, up to 256 names for the same inode in one directory) though across directories you can have up to 2³² names for the same inode.

This restriction causes btrfs-convert 0.19 to crash out with a segfault and no helpful message: something like btrfs-convert: segfault at ffffffffcfb25fb9 ip 000000000040f9f1 sp 00007fffddefb398 error 6 in btrfs-convert[400000+21000].

It seems a priori that there should not be any need for more than 256 names for the same file in the same directory. However, the GNUS mailreader's nnmaildir backend uses hardlinks to mark email messages read, and instead of creating a separate inode for each marked message, uses a hardlink to a single markfile. This means that there maybe thousands of hardlinks to the same inode in a single directory.

You can use the command find -type f -links +255 to locate such troublesome files, however this will not indicate whether the links are in the same directory or not, so there can be false positives.

The reason designing file-systems and other system infrastructure is hard is that the range of at first glance nonsensical configurations that people will expect to work seamlessly. I hope that as BTRFS matures it will be able to handle these use-cases — the nnmaildir link hack to use the filesystem as a mark database is not altogether unreasonable.

Splitting sticks

2011-06-26T00:00:00Z

A rather nice puzzle with thanks to Mr Chen and Mr B: given a stick of integer length n > 1, split it at an integer point below n, multiply the product of the two pieces and for each piece larger than length 1, do the same thing. What is the sum of all the products?

The answer follows — maybe you would like to take a moment to puzzle it out by yourself?

Firstly, why should the sum of the products not depend at all on the strategy? If one were not restricted to integer divisions in some way, then the strategy would probably become important, depending how the puzzle were then defined. The use of multiplication indicates area; the use of integers indicates blocks. Given that we must have area, we have defined a shape — it should have some symmetry as we can rotate the stick, and balance the increase in one piece of the split with an equal and opposite decrease — thus we guess a triangle.

We therefore present a visualisation of the problem as a triangle with n-1 1x1 blocks all on a line, n-2 blocks above them, n-3 above those stacked from the left until at the top left a single 1x1 block stands. The choice of point to split the stick now resolves to a choice of block on the diagonal - given a choice of such a block k < n, subtract it and the k x k square underneath and to the left of it from the stack of blocks; this leaves up to two triangular piles corresponding to the up to two remaining pieces with length greater than one; each triangle is of the right size so the analogy holds and the answer is the area of the first triangle of blocks: (n-2)(n-1)/2.

Alternatively, one can trivially see it algebraically by induction, but that is less fun.

A new information security stone age: the no-Santa clause

2011-04-30T00:00:00Z

[And now a guest post from my good friend, Thomas Köppe.]

We have been taught that the internet can be made to keep our bank data and our work documents and our love letters secure (whatever that means, but who doesn't want to feel secure?), as long as we look out for the little padlock in the address bar. But a major link in the security chain that makes all this happen has been compromised. The attitude of our modern information society is dangerously askew.

Last month, one of the so-called certificate authorities (CA), which issue the cryptographic certificates that websites use to prove their authenticity to the user, and which contemporary browsers are practically hard-coded to trust, has been involved in a major security breach. The US-based CA, called Comodo, was conned into issuing fraudulent certificates to an unknown entity (presumed of Iranian origin) for major websites including (but not limited to) Google, Yahoo, Skype and Mozilla. Anyone who holds such a certificate, which browsers trust automatically, can pretend to be that website and link themselves into your communication, eavesdropping and perhaps tampering with the information you believe to come from the genuine source.

In the wake of the recent security fiasco at Comodo [1a, 1b], I was at first pleasantly surprised that this event made it into the mainstream news [2a, 2b], but then it struck me: Almost everybody who is going to get this news flash from any of the mainstream sources will respond (if at all) with a perplexed frown, a mental shrug and move on to something more tangible or relevant to their lives. The Comodo hack has demonstrated one of the greatest weaknesses of the way we currently deal with trust on the internet, which has potentially profound implications, but it will be nigh impossible to get anyone concerned about this, let alone change their every day Internet behaviour.

In fact, whenever I do suggest to friends and colleagues things that could help make their information security a little more robust, it is almost invariably clear that they won't change their behaviour, given that everything works just fine as it is, and they have nothing to hide. (For those interested in the details: for example, SSH is another secure protocol that is generally accepted to do a very good job, but the price is that the user has to make a trust decision every time they connect to a new peer.)

At this point I would like to invoke what I call the No Santa Clause: nothing is free. It was once considered a milestone on the way to adulthood to shed one's belief in a universal benefactor who would bring things and ask nothing in return. Yet, in a turn most curious, our modern society seems to be turning this on its head, and when faced with computer technology, enlightened, educated adults are now more and more of the conviction that they should just get lots of stuff for free.

Before the advent of computers, it was generally possible for most people to understand large parts of their every-day environment, or at least know in principle how they could come by the understanding. A. C. Clarke's sufficiently advanced technology was certainly not magic to us, and while an uncontacted South American tribe might be genuinely incapable of fathoming what makes a car move, none of us consider cars magic and could, at gunpoint, explain the basic idea of a combustion engine. But it is worth remembering that the combustion engine is just a miniature version of a steam engine (as are nuclear power plants), and steam engines have been around for centuries.

However, with the advent of computers, we are facing a new situation, quite possibly a first in the history of civilisation. To most people, modern computers and networks are quite literally magic. We have simply no idea what makes them work. All we know is that if I edit my Google Spreadsheet in London today, I can open a browser in Calcutta tomorrow and continue writing. How does any of this work? I don't care, it just does, leave me alone. More and more of modern people's lives are being transferred entirely into the cloud, this magical vapour that has your photos and knows your friends wherever you are.

But wait — a service which allows you to access your entire life from anywhere in the world, instantly, and safely and securely? This really is a big deal, a huge service! And now we must wake up and realise that there is no Santa Claus: This service is not free. Perhaps (for the first time since the inception of money millennia ago) this service does not require us to pay money. But what it does require is responsibility.

The world of online information processing and security is a complex and complicated one indeed. But it is where most of our lives are now taking place. Just like we demand car drivers to pass a test and drive responsibly, we absolutely must demand of everyone who uses computers and networks as integral parts of their lives to do so responsibly. And this simply requires a certain extent of understanding of the subject matter. Security design is an art that nobody understands at this point, and there are no secure systems. (Anyone who claims otherwise is either dishonest or incompetent.) As security experts repeatedly put it [3a, 3b], everyone in the security chain avoids making the critical decisions and passes the burden around like a hot potato, until it eventually lands in the hands of the _one_ person who is least capable of making the right choice: The user. Anyone who has wildly clicked browser certificate warnings away in anger knows what I mean.

For the first time it would appear that many people are using tools that are way above their own level of competence, but they do so with little worry or desire to improve that competence. People's attitude has made a leap for which I struggle to find a historic precedent: from having observed at the end of the last century that computers can make some things easier, we have suddenly and inexplicably leapt to the immodestly entitled assumption that computers should make everything entirely free and easy. Nowadays, a suggestion that one should think about one's tools before using them will only earn you confused looks, and possibly accusations of elitism, neediness or lack of a sex life. Companies that specialise on making tools for people who like to work above their limitations have certainly helped foster this attitude, but what happened — why do we believe that everything should be easy and just work?

I think complaining of our collective failure to understand security design is not helpful. Sure, there are a lot of things hardware and software vendors could improve. But ultimately, questions of security and trust require the user, you, to make a decision, and you will need enough basic understanding of How Stuff Works to make those calls. As it stands, our civilisation has come full circle, and it is no longer the Amazonian tribe (who doesn't use SSL), but it is us modern, enlightened people for whom most of our everyday technology is now so advanced that it is magic. If we continue to build a world in which the inner workings of most of our waking lives are understood only by a tiny elite of wizards, we may truly be coming around to face a medieval future. Santa hopes you have been good.

Meta-programming normally

2011-04-27T19:57:19Z

There was a time at Bell Labs when the so-called Area 10 from where so much of UN*X sprang evangelised the the dual view of programs as both tools and text (Derman: My Life as a Quant). Tools like the yacc parser generator and lex were invented there. Nowadays the fashion has swung to handwriting those things which were once generated. Programming systems have become more expressive, and integrated with debugger and editor environments so the benefits of a specialised language are lower and the costs in terms of loss of convenience higher.

The increased expressiveness of modern mainstream programming languages over the FORTRAN of yore paradoxically has caused an explosion in boilerplate as people painstakingly reimplement operator precedence in their parsers by hand.

Full meta-programming is a huge boon to the development of application specific software, which is in the end, any large project. There is an unfortunate hysteresis in that using an application specific language brings vast costs: it is expensive to start using a new language (which as a project becomes sufficiently large is inevitable). Then it is expensive to maintain the separate compilation stage or auxiliary systems, and then expensive to redesign or replace the language once its deficiencies become unbearable (which as the project ages is also inevitable).

Given — for example — that the increased expressiveness of C++0x allows much to be done without macros that used to need macros, what advantage does first-class meta-programming have over template-based or type-system structured meta-programming? Well, clearly, a huge reduction in complexity: what is the point of wedging a Turing complete template language to be executed at compile time over a Turing complete base language, when one language would suffice perfectly well?

It is now quite possible to flexibly define and register functions for an RPC layer purely in C++; it is even possible to do it relatively neatly handling type-conversions without overhead at compile time. It was not before; should all the systems that have been built to do this be abandoned?

One problem still unsolvable in C++ or weaker systems like Scala, etc. is that one cannot define readily define types that should be represented in memory in a special way (for example, position independently or with persistence to a backing store). For example, in tpd2 there is a set of objects (including comments on this blog) that are automatically persisted to disk. These are defined with a custom "defrecord" instead of a standard "defstruct" and that is all; there is no need for runtime reflection to determine the static type of the object.

Fully flexible first-class meta-programming has the advantage there is a single language to learn, not a language and then language within it for specifying dependent types. It is most important as projects grow. Metaprogramming is all about scaling; scaling a codebase is hard enough without being shocked by new techniques. Meta-programming should be a normal tool not an extra-ordinary one.

Uncompromising meta-programming

2011-03-10T00:00:00Z

Meta-programming is using programs to generate or transform programs, like a compiler, it's difficult to explain how it can be both easy and useful. One simple example is efficient serialization: automatically generating converters for between in-memory and network or disk data-representations as efficiently as writing the conversion programs by hand. There is no compromise between efficiency and syntax.

As another example, in tpd2, which is designed for high performance, meta-programming is used to allow a convenient syntax for outputting HTML templated strings with performance as good as hand generated code, compile time safety in terms of spell-checking of attributes and that TD (table cell) elements appear only inside TR (table row) elements, etc.

Syntax becomes independent of implementation: meta-programming explicitly allows convenient syntax, without repetitive drudgery while achieving optimal behaviour: having efficient code is possible without compromising syntactical elegance and forcing the human programmer to repeatedly apply optimization tricks to complicate the program, making it harder to understand and modify.

The basic syntax for the HTML generation in TPD2 is in appearance like a function call: (<h1 "Hello") returns "<h1>Hello</h1>", and nested tags with attributes are handled: so that (<p "This is a " (<a :href "link.html" "link")) goes to "<p>This is a <a href="link.html">link</a></p>". Anywhere a literal string appears a function can be called instead, or a variable substituted, so that dynamic generation of content is easy. This syntax can be naively implemented by defining functions <p, <a, <h1 etc.

Efficiency can be achieved with this simple syntax: an example might be

(defun greet (name) 
       (<div 
       	   (<h1 "Hello " name) 
	   (<p "Pleased to meet you, " name ", thanks for reading.")))

Performing string concatenations at runtime is O(n²), but not running string concatenations means that the scatter gather IO must be used with small fragments which is inefficient in the kernel as each fragment needs to be access checked, and having many fragments puts pressure on the GC. In fact in tpd2, string concatenation was wasting the majority of time in some benchmarks.

With a naive implementation, the <h1 would boil down to (strcat "<h1>" "Hello " name "</h1>"), or even worse and there would be no way to merge the "<div>" with the "<h1>" tags. With Lisp's convenient meta-programming, where the <div operator is no longer a function, however, it can inspect its arguments and perform an optimization across boundaries: in this case transforming the greet function to the optimal (given an optimal strcat operator which is complicated in itself):

(defun greet (name)
       (strcat "<div><h1>Hello " 
       	       name 
       	       "</h1><p>Pleased to meet you, " 
	       name 
	       "</p></div>"))

Guaranteed safety achieved through static analysis of the properties of the program, even domain specific ones is better than turning up bugs in time consuming testing; properties are proved rather than gathering statistical evidence about them. The domain specific transformations with meta-programming techniques naturally tend to allow compile time checks.

For example, with the tpd2 HTML generation, attributes are spell-checked so that, for example, an href attribute is not allowed in an <p> element. This would be impossible to check with HTML validation tools unless every codepath that could generate HTML were exercised. Additionally, the HTML DTD specifies that only some tags can appear in others; for example, a <div> cannot appear in an <h1>. Where possible, violations of these constraints are also reported at compile time; however, as tag contents can be generated by arbitrary programs, it is not possible to find all violations. In fact, this brings up a major weakness of Lisp meta-programming: a sophisticated compiler may have a strong understanding of the potential control flow with powerful constant propagation and type inference, but that is not exposed to the macro-expansion facilities.

I hope I have been able to present a practical example of the utility of convenient meta-programming; of course many more sophisticated things are possible (like compiling regular expressions to machine code or allowing convenient definition of object relational mappings). It allows one to keep a pretty syntax while achieving optimal machine code generation and simultaneously increasing safety. Additionally, it a natural interface barrier between the application programmer and the systems programmer that allows either to comfortably modify their design and implementation independently. No compromise is necessary and none is made.

Reflecting on meta-programming

2011-02-20T15:44:05Z

I've been having revealing conversations with people in the Scala and F# communities where I discover that my definition of meta-programming is not widely shared. Personally, I think that the two most misunderstood computer languages are C++ and Lisp: and one reason for that is that they both offer real meta-programming — in the sense not of Ruby's dynamic reflection and redefinition, but in the sense that one can write programs to write other programs.

Reflection, in terms of looking at what functions and types have already been defined, is in my view normal programming — however, fiddling around dynamically at run-time depending on the compile-time definitions of the program, while probably ugly and inefficient, is able to work around problems that would naturally be solved with meta-programming facilities, if they were available. This does not excuse their absence, just makes it slightly less unbearable and introduces unnecessary runtime costs.

Can one come up with a well-defined real-world example task that can be solved with meta-programming but not reflection? Of course not — meta-programming does not make a system more than Turing complete. In the same way that anything achievable with subroutines can be achieved with gotos. The argument that must be advanced for meta-programming is more nuanced: for someone who has never imagined a function call, then a tangled spaghetti of goto statements is all they see before them.

Writing programs to write programs is a powerful tool which naturally side-steps whole classes of systemic deficiencies; being able to do it fluidly in Lisp rather than in a contrived and round-about fashion with C++ template trickery renders it appropriate for many more tasks. I hope to present a few strong examples from the tpd2 project in greater detail - more are welcome!