A bloom filter with the optimal number of hash functions (= bits per element) usually occupies a space in memory that is N * log2(e) * log2(1/P) bits, where N is the number of elements that you want to store, and P is the false-positive probability. To put things into perspective, let’s say you want to store 100K elements with 1 false positive every 8K elements. Given that log2(8K) ≈ log2(8192) = 13, and log2(e) ≈ 1.44, you need 100K * 1.44 * 13 bits ≈ 1828 KiB ≈ 1.78 MiB.

The theoretical minimum for a similar probabilistic data structure would be N * log2(1/P), so a bloom filter is roughly using 44% more memory than theoretically necessary (log(e) = 1.44). GCS is a way to get closer to that minimum.

GCS is well suit in situations where to want to minimize the memory occupation and you can afford a slightly higher computation time, compared to a Bloom filter. Google Chromium, for instance, uses it to keep a local (client) set of SSL CRL; they prefer lower memory occupation because it is specifically important in constrained scenarios (e.g.: mobile), and they can afford the structure to be a little bit slower than Bloom filter since it’s still much faster than a SSL handshake (double network roundtrip).

Turning words into values

GCS is actually quite simple, and I will walk you through it step by step. First, let’s agree on a dictionary of words you want to put into the set, for instance, the NATO alphabet:

['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot',
 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike',
 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra',
 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee',
 'zulu']

We want to create a data-structure for these words with a 1 on 64 false-positive probability. This means that we expect that we will be able to check the whole english dictionary against it, and about 1 word every 64 will result to be present even if it’s not.

We compute a single hash key for each different element, as integers in the range [0, N*P). Since N=26 (the length of the NATO alphabet) and P=64, the range is [0, 1664]. As in the case of Bloom filters, we want this hash to be uniformly distributed across the domain, so a cryptographic hash like MD5 or SHA1 is a good choice (and no, the fact that there are pre-image attacks on MD5 does not matter much in this scenario). We will need a way to convert a 128-bit or 160-bit hash to a number in the range [0, 1664], but the moral equivalent of the modulus is the enough to not affect the distribution. We will then compute the hash as follows:

def gcs_hash(w, (N,P)):
    """
    Hash value for a GCS with N elements and 1/P probability
    of false positives.
    We just need a hash that generates uniformally-distributed
    values for best results, so any crypto hash is fine. We
    default to MD5.
    """
    h = md5(w).hexdigest()
    h = long(h[24:32],16)
    return h % (N*P)

If we apply this function over the input words, we get these hash values:

[('alpha', 1017L), ('bravo', 591L), ('charlie', 1207L), ('delta', 151L),
 ('echo', 1393L), ('foxtrot', 1005L), ('golf', 526L), ('hotel', 208L),
 ('india', 461L), ('juliet', 1378L), ('kilo', 1231L), ('lima', 192L),
 ('mike', 1630L), ('november', 1327L), ('oscar', 997L), ('papa', 662L),
 ('quebec', 806L), ('romeo', 1627L), ('sierra', 866L), ('tango', 890L),
 ('uniform', 1134L), ('victor', 269L), ('whiskey', 512L), ('xray', 831L),
 ('yankee', 1418L), ('zulu', 1525L)]

Let’s now just get the hash values and sort them. This is the result:

[151L, 192L, 208L, 269L, 461L,
 512L, 526L, 591L, 662L, 806L,
 831L, 866L, 890L, 997L, 1005L,
 1017L, 1134L, 1207L, 1231L,
 1327L, 1378L, 1393L, 1418L,
 1525L, 1627L, 1630L]

Remember that the range was [0, 1664). Given that we used a cryptographic hash, we expect these values to be uniformly distributed across that range. They look like it at glance, and obviously it gets much better with real-world data sets which are much larger. If we plot these values, we can double-check the distribution:

Let's compress

We now want to compress this set of number in the most efficient way. General purpose algorithms like zlib are obviously the wrong choice here, since they work by finding repetition of strings, and the 16-bit or 32-bit encoding of the above numbers would look like random data to zlib. Some compression theory comes to the rescue: the best way to compress an unordered uniform data set is to compute the array of differences, which will be a geometric distribution, and then use the Golomb encoding. Did I lose you? Let's see it one step at a time.

If we compute the increments (differences) between a uniformly distribute set of values, the result is a geometric distribution. Recall that we originally decided for a range of exactly 26*64, and then we picked 26 uniformly distributed values within it. If you were to bet on the most likely distance between a value and the next one, wouldn't you say "64"? Yes. And we can argue that most distances are going to be numbers pretty close to the value 64, and far larger values are extremely unlikely. This intuition matches with the geometric distribution (whose correspondent in the continuos domain is the exponential distribution).

In our example, this is the array of differences:

[151L, 41L, 16L, 61L, 192L, 51L, 14L, 65L, 71L, 144L,
 25L, 35L, 24L, 107L, 8L, 12L, 117L, 73L, 24L, 96L,
 51L, 15L, 25L, 107L, 102L, 3L]

Again, we can check this with a little plot (after sorting them):

The parameter p of this geometric distribution should be exactly the false probability we chose above (1/64). To double-check, we can estimate the parameter p by dividing the number of values by their sum: 26 / 1438 = 0.0175320, which is close enough to 1 / 64 = 0.015625. Again, with a larger input set, the numbers would be even closer.

Golomb encoding

We now want to compress this set of differences with Golomb encoding. As Wikipedia says, "alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values". In fact, we are going to use simplified sub-case of Golomb encoding, in which the parameter p is a power of 2 (like 64 is, in our case). This sub-case is called Rice encoding.

Back to the intuition: we are going to compress values which are very likely to be as small as the value 64, and very unlikely to be much bigger; 128 is unlikely, 192 is very unlikely, 256 is very very unlikely, and so on. Golomb encoding splits each value in two parts: the quotient and the remainder of the division by the parameter. Given what we just said about the likeness, you must expect the quotient to be likely 0 or 1, unlikely to be 2, very unlikely to be 3, very very unlikely to be 4, etc. On the other hand, the remainder is probably just a random number we can't infer much about, it's the high frequency oscillation which is impossible to predict. Golomb (Rice) coding simply encodes the quotient in base 1 (unary encoding) and the remainder in base 2 (binary encoding). Unary encoding might sound weird at first, but it's really simple:

So we emit as many 1s as the number we want to encode (the quotient) followed by a zero. Then, we emit the binary encoding of the remainder using exactly 6 bits (since it will be a number between 0 and 63). Thus, a number between 0 and 63 will be exactly 7 bits long: 1 bit for the quotient (0) and 6 bits for the remainder. A number between 64 and 127 will be 8 bits long (quotient 10, plus the remainder); A number between 128 and 191 will be 9 bits long (quotient 110); and so on. Smaller numbers are as compact as possible, higher and unlikely numbers gets longer and longer. Let's see our array of differences properly encoded:

And if we concatenate all the output, we get our final Golomb-coded set of numbers:

11001011 10101001 00100000 11110111
10000000 01100110 00111010 00000110
00011111 00100000 01100101 00011001
10001010 10110001 00000011 00101101
01100010 01001100 01010000 00110011
00011110 01100110 10101110 10011000
00011

197 bits (25 padded bytes) to encode 26 arbitrary-long words with a 1.5% of false positives. That's 7.57 bits per word. Not bad! The theoretical minimum number of bits was 26 * log2(64) = 156, so we're still a little off in this example, but still better than an optimal Bloom filter which would require 225 bits. The example I chose is obviously too small and thus it's very impacted by the specific words and the output of the MD5. I ran the same algorithm over a 640K-words English dictionary with expected false probability 1/1024, and I got a 7,405,432 bits GCS, which is about 11.58 bits per word. An optimal Bloom filter for the same set would take 9,227,646 bits, while the theoretical minimum would be 6,396,530 bits. Quite an improvement, in fact.

Decompression and query improvements

So how do we now query for a word to see if it's in the set or not? We just need to reverse all the steps.

We start going through the bits. We extract the quotient Q by simply counting the number of consecutive 1s before the terminating 0; then we extract the fixed-size remainder R (exactly P bits, 6 in our example). We compute the original difference (Q*P+R), and we accumulate it into an integer so that we regenerate the original sorted set of hash values, one element at a time. We don't need to actually expand the whole set in memory: as we go through the bits and compute one hash value at a time, we can compare it with the one that we are being queried for, to see if there's a match.

After you reverse the encoding and difference steps, the underlying hash value set is sorted. So going through the set in linear order sounds like slower than it could be. One would think of doing a bisect search, but there is no easy way to jump to an arbitrary index in the encoded set, since the encoded elements have different size in bits, and they can be decoded only one at a time in linear order.

What we can do to improve query time a bit is to compute an index that allows to seek within the encoded set. For instance, if you want to make the query time 32 times faster, you can split the original domain [0...N*P) in 32 subdomains of equal size N*P/32. Then, for each subdomain, you find the smallest hash value that is part of the subdomain, and save its bit-index in the encoded GCS within the index. Since the hash values are uniformly distributed, each subdomain will contain roughly N/32 values, so by seeking into it while querying you will need to decode only 1/32th of the whole GCS, thus getting the 32x speed increase in query time. In the full English dictionary example cited above, an additional index made of 32 indices of 32-bits each is just 1,204 bits of additional memory; compared to a 7 million bits GCS, it's a good deal to obtain a 32x speed increase in query time!

Play with the code

The full code is available on GitHub. I wrote both a Python and a C++ implementation that you can compare. The Python code is meant to be really simple and not really optimized (e.g.: it even streams the set from the disk when you do a query). The C++ is a little bit more optimized, though still mostly an academic example. Notice that the code does not implement the index to speed up decompression. Even if it's good deal, it's obviously not mandatory and just an optimization.

Let’s step back a little. We all know that SSL is kind of broken because of the need to rely on certificate authorities. Moxie himself has a great blog post on the subject. In a word, we don’t want to pay certificate authorities, we have too many of them (up to 70 in recent browsers/OS), we can’t really trust all of them, and we don’t have an easy way to revoke trust in the certificates they issue.

Convergence starts from the idea that it would be really great to avoid CAs altogether and use self-signed certificates, but self-signed certificates are vulnerable to man-in-the-middle (MITM) attacks. So the clever idea is noting that MITM is a local attack: it’s either someone next to you drinking a coffee at Starbucks, or someone that hacked your ISP’s DNS, or maybe someone working for a corrupted government that’s hijacking traffic at the BGP level. It’s unrealistic that the same MITM attack can affect you, someone in Iceland, someone in China, someone in West Virgina, and someone in Italy at the same time, right? And that’s what Convergence exploits: it gives you a way to compare SSL certificates fetched from the website you want to visit from many different servers in the world, called “notaries”. If they all match, a MITM attack is impossible, and you can trust the self-signed certificate and proceed logging in into your bank. Right?

Wrong. Because you know what else self-signed certificates are vulnerable too, in addition to MITM? Lies. And you know who lies? A phisher. So if a phisher registers bankoffamerica.com (pay attention to the typo!) and self-signs the website with a SSL certificate saying that the organization behind the website really is Bank of America Corporation incorporated in Delaware, all notaries will report that the certificate is exactly the same as fetched from different parts of the world, and you will get absolutely no warning.

And what is worse is that you will lose any EV indication while browsing with Convergence, since Convergence simply does not currently support any way to validate the identity of the website. As Moxie himself says, “Convergence does not enable EV for self-signed certs. It is concerned with authenticity, not identity”.

So to clarify: if you start browsing today with Convergence (and assuming you get a good set of notaries to bootstrap), you get the following effects:

1. You will be immune to MITM attacks with rogue certificates, like in the current Diginotar’s debacle.
2. The CA list in your browser will be effectively ignored.
3. You will stop seeing any information from EV certificates (identities of the sites your browse).

I personally don’t consider this a good compromise. It might be that I don’t live in China or Iran, but MITM attacks are an order of magnitude less common than phishing attacks, and people are slowly learning to trust EV certificates when browsing the Internet. It’s true that EV SSL certificates could be forged as well, I don’t dispute that. But right now with Convergence, I’m going to trade a simple protection against a common set of attacks with a good protection against a rare set of attacks.

I reached Moxie with these concerns, and he clarified that, technically speaking, Convergence could be enhanced to check for existing EV SSL certificates (through a custom notary), but that he doesn’t see EV certificates as solving any real problem nowadays. I beg to disagree: I don’t like EV per-se as well, but I think the identity problem is still something that must be solved on the Internet, and it’s probably even more important than solving the MITM problem.

Given that the number of websites which are targets of phishing attacks are relatively small because it’s mainly a group of high-profile sites (banks, web mails, social networks, etc.), and given that SSL certificates do not change so often (usually no more than once in a year for a high-profile website), there must be a way to conceive a global list of validated certificates for which an identity can be certified, even through a crowd-sourced mechanism. It has to be simpler than what GPG attempts to do with key-signing parties, because we don’t need to certify the identity of Mr John Green that you never met before, plus other 1 billion people; you just need to certify that Google is Google and PayPal is Paypal, for a one thousand of high profile websites. If you ask 10 people in 10 different countries to give you the SSL fingerprint for “Google, Inc.”, and you get 10 identical fingerprints, you can be 100% sure that the certificate you get is really for “Google, Inc.”. And if Google commits to use the same certificate for the next 3 months, you could globally cache this information, and distribute it to web users through notaries in a way that their address bar says “This is a certified Google Inc. website”. Or, in other words, “This is the same Google Inc. website that 1 million of people have visited in the last 2 hours, and 100 millions in the last 24 hours”.

If Convergence could be augmented to do something similar, I think we would be getting closer to the final solution of the SSL problem.

Image via Wikipedia

A friend asked me some time time ago how his bank’s OTP token worked. Most tokens that banks use (at least in Italy) are products of the “RSA SecurID” family, which are proprietary and secret (and rumored to have been compromised), but the general cryptography behind them is well-known and there are open standards that can be easily deployed by companies that want to add an extra layer of security. An emerging standard for OTP generation is called OATH, and given the general availability of free implementations, I will detail its algorithms in this post.

Some background on CSPRNG

OTPs (one-time passwords) are based on the concept of a so-called cryptographically-secure pseudo-random number generator (aka CSPRNG). As many programmers know, pseudo-random generator (as found in the standard library of most programming languages, such as C’s rand()) are algorithms that generate a repeatable sequence of numbers that are “random looking”; there are several way to measure how random a sequence is, but the important property that differentiate PRNG from CSPRNG is not really concerned with randomness per-se, but rather with how easy is to predict the next number just by looking at the previous ones. This is important in the OTP context because obviously an attacker might get to know the previous numbers generated by the system (eg. through a key-logger installed on user’s computer), so it is paramount to make sure that he cannot exploit this knowledge to generate the next number.

Once we have chosen a suitable CSPRNG, it is sufficient that the server and the client agrees on the “seed” to be used for the sequence; in fact, both sides will be able to independently generate the same sequence and thus for the server it will be easy to check if the numbers generated by the client are the same that it generates by itself. As long as the algorithm is truly secure and the “seed” is not leaked, the ability of generating the next number can be considered a good authentication mechanism, since nobody else should be able to generate the same sequence. By embedding the seed onto an off-line physical device (the token), leaking the seed becomes almost impossible. If the device is stolen, it is sufficient to revoke it and assign a new device to the user (with a new “seed”).

I’m putting the word seed between quotes because it does not tell all the truth. Any PRNG algorithm works by keeping an internal state; when the next number is requested, the algorithm manipulates (changes) the internal state in some way, and then produces a number as result of this computation. In the simplest of all random algorithms (the same used by many implementation of C’s rand()), the internal state is simply the previous number being generated, but this is obviously not good for a CSPRNG. What we want is a way to generate a number from an internal state in a way not to leak any information (if possible at all) about the internal state. The “seed” is just a way to initializes the internal state, but if the PRNG is not secure, it will eventually leak enough information to let an attacker reconstruct the internal state, even if the seed itself was never leaked.

Getting to the code

So, how do we make sure that we can generate a number from a state without leaking information? What we are looking for is called a one-way function. Luckily, in cryptography, we have plenty of one-way functions available: they are called “secure hash functions”, MD5 and SHA1 being the most popular. If we decide that we trust SHA-1 as a good one-way function (that is, we accept that our CSPRNG be as strong as SHA-1, and broken as soon as SHA-1 will be broken), then we don’t need a complex internal state: we can simply use a progressive counter for that. SHA-1′s properties in fact already guarantee that, given SHA1(N), there is no way to reconstruct N; and for every N’ very “similar” to N (eg: obtained by bit-flipping, or a simple increment), there is no correlation at all between SHA1(N’) and SHA1(N).

So, the sequence SHA1(0), SHA1(1), SHA1(2), etc. can be considered a CSPRNG. But it is just one sequence; it’s true that can be arbitrary long, but how can we obtain different sequences for different users? The first solution that comes to mind is to use the same technique that is used to differentiate hashes of the same password: a salt. If we assign each user a random salt S, we can prefix it to the counter and obtain a unique sequence by computing SHA1(S + N). Let’s see this at work with some basic Python:

import os
from hashlib import sha1
def OTP(salt=None, n=0, digits=6):
    if salt is None:
        salt = os.urandom(8)
        print "Salt:", salt.encode("hex")
    while True:
        hash = sha1(salt + repr(n)).hexdigest()
        num = long(hash, 16) % (10**digits)
        yield "%06d" % num
        n += 1
o = OTP()
print o.next()
print o.next()

which produces an output just like this:

Salt: e4cd2b5b4dbbed47
031049
163172

Up until now I have used the word “salt” but this is in fact incorrect. The term salt is supposed to indicate a random string of bytes which is generated for each invokation of the hash/cipher. In the CSPRNG case, instead, the random data is generated once per user, and reused through the life of the sequence. Together with the counter, this “salt” is actually the secret state of the algorithm. The correct term for that string is “secret key”; if it is leaked, the CSPRNG is basically broken (since recovering the current counter is just a matter of generating the whole sequence up until the match).

The real OATH (RFC 4226)

OATH is basically the above algorithm, with only a few variations to make it more secure in face of future attacks to the underlying SHA1 hash function:

• “Mutating” a hash through a secret key is a common need in cryptography, and there is a stronger algorithm to achieve it: HMAC. HMAC-SHA1(S,N) is basically the stronger version of SHA1(S+N), with S fixed and N changing. OATH uses HMAC-SHA1.
• A longer (20 bytes) secret key is used, as required/suggest by HMAC-SHA1.
• The counter is always converted to a 8-byte string (its big-endian binary representation). The above code was using repr as a simple way to obtain a string from a counter.
• To extract the final 6 digits that form the OTP, we convert the whole SHA1 digest (20 bytes) into a number and then we calculate the modulo with 1,000,000. This means that we basically use the last few bytes of the SHA1 digest and discard the rest. This is not a problem right now because SHA1 is still secure, but to minimize risks OATH describes a way to extract 6 digits taking all 20 bytes into account. The exactly details can be read in the specifications.

Even with the above changes, OATH is quite easy to implement, and in fact there exist many different free implementations. For instance, you can download a generic OATH client for both iOS and Android, which are very good substitutes for a hardware token (with just the inconvenience that it is much much easier to extract the secret key in case an attack has physical access to the device for a while).

C optimizations

If you are an average C programmer, you know that simple code can be trusted to be evaluated at compile-time thanks to optimizers. For instance, if you write something like:

void square(int x) { return x*x; }
void foo(void)
{
   int k = square(32);
   /* ... */
}

you trust your compiler to evaluate the square at compile-time, when optimizations are on. When things get more hairy:

int factorial(int x)
{
    int result = x;
    while (--x)
         result *= x;
   return result;
}
void foo(void)
{
   int k = factorial(8);
   /* ... */
}

C programmers get immediately less confident about what will happen at run-time. For instance, would you say that your compiler is able to expand the above code at compile-time or not? Actually, the answer is “yes” in this particular case (unless you are using a very old compiler), but the point is still valid: this is not C code that one would write if he wants to be sure that the whole calculation be folded at compile-time.

There is also another issue: since the language does not mandate that the value is folded (and in fact, it is not folded when optimizations are disabled), you cannot create a constant out of it, such as by assigning it to a const variable.

When things get hairy

Now, let’s try with a (very naive and simple) solution of problem #1 of Project Euler:

#include <stdio.h>
int euler1(int max)
{
   int i,res=0;
   for (i=1; i<max; i++)
   {
       if ((i % 3) == 0 || (i % 5) == 0)
           res += i;
   }
   return res;
}
int main()
{
   int r10 = euler1(10);
   int r1000 = euler1(1000);
   printf("%d %d\n", r10, r1000);
   return 0;
}

This program simply calculates the sum of all divisors of 3 or 5 below 1000. But if you look at the generated code with GCC under -O3, you will see that the actual results are not computed at compile-time, but rather calculated at runtime. I believe any average C programmer would agree that we should not expect this code to be folded at compile time.

Now, meet the equivalent D code:

int euler1(int max)
{
   int i,res=0;
   for (i=1; i<max; i++)
   {
       if ((i % 3) == 0 || (i % 5) == 0)
           res += i;
   }
   return res;
}
int main()
{
   int r10 = euler1(10);
   int r1000 = euler1(1000);
   printf("%d %d\n", r10, r1000);
   return 0;
}

Deja-vu? Yes, it is exactly the same, barring the initial include statement that is not required (actually, there is no preprocessor in D and modules refer to each other with the import statement, but printf is a builtin). Of course, the above example was hand-crafted to make it both valid C and D code, but being D an evolution of C, the basic syntax is the same.

Meet CTFE

And now the hattrick: in D, we can request the compiler to evaluate euler1 at compile-time by simply using the static keyword at invocation time:

   static int r10 = euler1(10);
   static int r1000 = euler1(1000);

Great, isn’t it? Now the result of the above function call are evaluated by the compiler, irrespective of the optimization levels. If the function cannot be evaluated at compile-time (usually because it has side-effects, like any kind of I/O), it will trigger a compile-time error.

We can verify that the above constants really do appear in the generated code by compiling with gdc -save-temps euler1.d and then inspecting euler1.s:

D6euler14mainFZi3r10i:
        .long   23
.globl _D6euler14mainFZi5r1000i
        .align 4
        .type   _D6euler14mainFZi5r1000i, @object
        .size   _D6euler14mainFZi5r1000i, 4
_D6euler14mainFZi5r1000i:
        .long   233168
        .section        .rodata
.LC0:
        .string "%d %d\n"
        .text
.globl _Dmain
        .type   _Dmain, @function
_Dmain:
.LFB3:
        pushq   %rbp
.LCFI3:
        movq    %rsp, %rbp
.LCFI4:
        movl    _D6euler14mainFZi5r1000i(%rip), %edx
        movl    _D6euler14mainFZi3r10i(%rip), %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        movl    $0, %eax
        leave
        ret

Notice how the compiler has calculated the values 23 and 233168 (respectively, results of euler1(10) and euler1(1000)) and put them in the data section of the executable.

If you are curious of what happens when the compiler cannot do the whole evaluation at compile-time, it is sufficient to stick a printf() call somewhere in the euler() function. Since printf() does some I/O, it breaks CFTE, and the compiler will happily tell you about that:

euler1.d:9: Error: cannot evaluate printf("hello, world!\x0a") at compile time
euler1.d:15: Error: cannot evaluate euler1(10) at compile time
euler1.d:16: Error: cannot evaluate euler1(1000) at compile time

Closing words

CTFE is simple yet very powerful. The fact that it is triggered at the call site (rather than being an attribute of the function, like the inline keyword) is a very smart design choice: it makes perfectly sense for the same function to be used at both run-time and compile-time, depending on the inputs.

For the C++ guys reading, C++0x has grown a constexpr keyword that, while looking superficially similar, it is a lot less powerful, since it can only be used on very simple functions (basically, one-liners). In fact, the keyword is meant to be use while declaring a function, and not at the call-site, so it has to apply only on small functions which can be proved to always yield a constant value.

In the next weeks, I will post a more complete real-world example of the power of CTFE from BeRTOS. Stay tuned!

Greylisting

Greylisting is a very common anti-spam technology: whenever a potential spam arrives, our MTA replies with a temporary failure code (SMTP code: 4xx), and writes down the IP address of the sender MTA (the server that is sending the e-mail) in a DB; when facing a 4xx code, any RFC-compliant MTA will simply try to deliver the same e-mail again after a while, at which point our MTA will let the mail through (because the IP address is already present in the DB). On the other hand, most spammers do not follow the RFC (how bizarre): they would not bother retrying and would simply move on; this is because each retry is a memory/CPU cost for them (they need to note down the server which is temporary failing, keep a queue around, etc.); after all, if it was a real temporary failure, that server might still be failing for a few hours, and it would be a real waste of bandwidth to try again, just to stop at the same temporary failure.

What it is interesting about greylisting is that such a simple idea can achieve impressive results. If you google around, you will find enthusiastic people reporting at least 80% of spam blocked, with few of them citing numbers as high as 95%. All modern mail servers support greylisting either out of the box or through a plugin. For the famous open source server Postfix, the postgrey extension is easily available and widely deployed.

There obviously are some cons to greylisting:

• Since normally greylisting is applied to all incoming e-mails, regular e-mail delivery is delayed. In fact, a RFC-compliant MTA will eventually retry, but how soon is an implementation detail. It might be one minute or one day (even though most servers usually retry in a few minutes). Obviously, mature greylisting implementations will keep the IP address of a good server in the DB for a long time (eg: one day or one week), effectively whitelisting it; so, the delay only happens on one e-mail per server. Most people don’t see this delaying as a problem, but I do: I believe that a good anti-spam pipeline should never impact regular e-mails whatsover. I don’t want a very important e-mail to be delayed for an unknown period of time because I cannot fight spam in other ways.
• Some servers could be RFC-compliant and still fail to delivery e-mail to a server using greylisting. How & why? Simple: think of  large shop like gmail. They have dozens of SMTP servers. When a server tries to deliver an e-mail and it receives the 4xx code back, can you be absolutely sure that the same SMTP server will retry later? What if they have an unique queue of e-mail, and another server picks the same e-mail up and retries? This other server will also be greylisted.  Can you see the problem now? I won’t enter details, but many greylist implementations suggest using manually-compiled (and maintained) whitelists. Uh-oh. Less funny now.

RBLs

RBLs are blacklists of servers/zombies that deliver spam, listed by IP address, and queried through the DNS protocol. In short, if you want to ask super-blacklist.example if 1.2.3.4 is listed there, it is sufficient to try to resolve the hostname 4.3.2.1.super-blacklist.example; if it resolves to an IP address (any IP address, it doesn’t matter), it’s listed; otherwise it is not listed.

Blacklists can be deployed within a mail server at different levels. For instance, you can use them in a score system to increase the probability for a mail to be treated as spam. Or you can use them to simply reject the e-mail at the SMTP level, even before the body is transferred (since everything you need to query the blacklist is the MTA IP address, and you have this information as soon as the TCP connection is initiated to your MTA).

Of course, not all blacklists are equal. If you rely on them for rejecting your e-mails, you better be sure that the blacklist is well-maintained, has a good reputation and that you are using it correctly. For instance, if we analyze the famous Spamhaus Zen blacklist, we find out that it is made of three different blacklists, one of which is the PBL. The PBL is (quoting) “a DNSBL database of end-user IP address ranges which should not be delivering unauthenticated SMTP email to any Internet mail server except those provided for specifically by an ISP for that customer’s use”. Rephrasing: it is a list of all dynamic IP ranges in the world; all home ADSL users are listed here. That’s it. There is no connection with spam altogether, it is just a list of dynamic IP addresses. Now, while most dynamic IP addresses will never deliver an e-mail directly to your server (and instead go through their ISP’s MTA), are you ready to block these hosts at the SMTP level? What if someone (one in ten thousands) runs a legitimate MTA server on their ADSL line? They are not violating any RFC, so why should you blacklist them? In fact, SpamHaus itself suggests against using this list for outright rejection of e-mail.

So, is there anything we can do with PBL at the SMTP level, which is in the middle between outright rejection and a SpamAssassin-like score system? Yes we can: we can greylist!

Greylisting & RBLs together

There are many different anti-spam technologies that can be done at the SMTP level, by looking at the so-called SMTP envelope (the SMTP conversation that happens before the actual e-mail is delivered). For instance, some people configure their servers so that they will reject e-mails based on the HELO command, eg: if its argument is not a FQDN hostname, as required by the RFC. Others (including myself) consider an outright rejection too risky, because there might be misconfigured MTAs out there and it’s not their users fault (nor your users fault!). Traditionally, you could either choose to implement one of these enforcements or not. But there is an alternative: greylisting.

Let’s get back to the PBL example. Using PBL for filtering e-mails is attracting:

• Almost all regular e-mail will arrive from a non dynamic consumer IP address.
• Almost all e-mails that you get from dynamic consumer IP addresses will be spam (basically, zombie Windows PCs running malwares that deliver spam).

But almost is not always, and I don’t want to risk rejecting any regular e-mail, even if it happens once a year. I don’t want to impact regular e-mails whatsover. So, you can do like me and just greylist entries from IPs that are in the PBL. The worst thing that can happen is that those e-mails are slighly delayed, but given the unlikeness of such event, it is probably an acceptable compromise.

If you think of it, this is just a smarter alternative way of deploying greylisting. Instead of greylisting each and every e-mail and causing delays to all your users, you greylist only those e-mails that are very dark grey but not really black. And if you google around for SMTP anti-spam tricks, you can find many of them which follows in this dark grey area: they’re so dark that some mail admins reject e-mail altogether, but they’re not fully black, so other more conservative admins just punt. Don’t punt: greylist!

This is why I greylist all e-mails from IPs in the PBL. And I also greylist all e-mails whose HELO string is not a FQDN, so that the occasionally misconfigured server is just delayed a little while, but not rejected, and I still block lots of spam very early in the pipeline.

And now, give me the code!

As much as I find this kind of greylisting deployment so sexy, it is depriving to see that there is basically no support around in mail servers for such a setup. The abandonware spftware called gl4rbl is the best I could find around, and we succesfully deployed an enhanced version of it with qmail in Develer for a long time.

When we switched to Postfix, we had to reimplement this, because the existing postgrey plugin does not allow conditional greylisting.

In the next days, we will post our own Postfix Policy Server that implements greylisting on RBL. It is a very compact Python script, less than 200 lines including comments. We also have some ideas on making it more generically useful so that it can be used to implement other kinds of conditional greylisting, and I will discuss them in the same post.

In case you did not know, you can avoid missing it by subscribing to the RSS feed.

What is a COW?

COW can sound nasty at first, but it is a good C++ citizen

An object with COW semantic (sometimes also called “implicit sharing”) has an interesting property: whenever you copy it, it does not really do a “deep copy” but simply shares the underlying data between the original object and its copy, and increments a reference counter to track this. Only at the moment that any of the copies is further modified (written to), the deep copy is really performed.

Now, it is important to realize that the overhead imposed by the COW semantic is usually very tiny: the object just needs to bookkeep a counter at every copy, and check it before any modification. The latter is even lighter than it sounds because the compiler can strip off many checks thanks to constant propagations.

But what are the advantages of using COW? The first and foremost advantage is the possibility to have a clean API with respect to return values.

Returning a COW

If you have programmed C++ long enough, you know that all C++ functions that should return a complex data structure (anything which is larger than a small structure, like a container, a memory buffer, and so on) will instead accept a reference or a pointer to an object that the caller must provide and that will be “filled in” as return value. This is absolutely awful. If you don’t see it as awful, it’s about time you take a break from C++ and switch to other languages for a while. For instance:

std::vector<Node> nodes;
cur_node.children(nodes);
printf("Number of children: %u\n", nodes.size());

The Node::children() function, in any other language, would have returned a vector of Nodes. But idiomatic C++ says that you should not impose the overhead of doing an additional copy of the vector onto your user, and thus ask him to pass you the container to fill. This is really unreadable because it breaks the common syntax of functions by intermixing return values to arguments. Moreover, it imposes additional troubles to the API; eg: what happens if you call Node::children() with a non-empty vector? Will the function just append its data to the vector? Or would it clear it at the beginning?

Now, think of a world where std::vector is a COW data structure. All these problems suddenly disappear because returning the vector would not cause a copy anymore. Bam, problem solved! And when you have a clear API, where return values really are return values, you get all the benefits from it:

printf("Number of children: %u\n", cur_node.children().size());

Three lines merged into one. No more temporary named variable. And if Node happens to internally store its children as a vector, this code is even faster than the non-COW version, because there is no copy performed at all: you get the same speed as if children() returned a reference to the internal vector, even though it does not.

COWs to the rescue

Other advantages of COW data structures:

1. You can nest COW data structures without overhead. Think of a vector<vector<int>>. Without COW, whenever the outer data structure resizes, the inner data structures will all be reallocated and copied. With COW, there is no copy at all: the internal data structures are basically moved over in constant time.
2. You can stop abusing const references everywhere. In C++, most functions will receive arguments by const references instead of simple values. Again, this is to save the overhead of a copy, and again this is almost useless with COW data structures. Const references are also nasty because they represent a first leak of const-correctness in your code (I also hate the whole const-correctness in C++, but this is for another day; if you like it, you can still make your functions accept const values if you feel too).

Norwegian COWs

Nokia’s Qt has designed all objects and data structures with COW. They even made them reentrant (for multithreading purposes) by using atomic reference counting through native CPU instructions. Finally, they expose the guts of COW through a simple QSharedData template that you can use to reimplement your own COW objects.

I could not agree with Qt’s designers more.

This is another example of how COW can positively influence API design:

QByteArray fileHash(QString fn)
{
   QFile f(fn);
   QCryptographicHash h(QCryptographicHash::Sha1);
   while (!f.atEnd())
        h.addData(f.read(16*1024));
   return h.result();
}

See how I can simply pass the buffer returned by QFile::read() to addData() without having to worry about memory copying.

Counting COWs

So, the next time you design an API which asks for a return value among the arguments, think of a C++ world where COW is everywhere. And dream on.

PyInstaller comprises many advanced features to make your life easier when packaging a Python program. In my opinion, its main advantage over py2exe/py2app (besides the obvious fact that it is a multi-platform tool) is that it includes many workarounds and quirks necessary to make applications work after packaging. What py2exe “fixes” by adding a page to their wiki, PyInstaller implements it properly, for everybody’s pleasure.

A very good example of this philosophy is the support for ctypes. I am sure most of you are familiar with this little gem, which allows a programmer to dynamicall bind to a shared library and invokes its functions without writing a binding. For instance, let’s say you have some existing and very complicated C code like the following:

/* foobar.c */
#include <stdio.h>
void fooize(int a)
{
   printf("Fooized %d!\n", a);
}

Which is compiled to a shared library:

$ gcc -shared -fPIC -o foobar.so foobar.c

Now, you can access this from Python by simply doing something like:

#!/usr/bin/env python
# example.py
from ctypes import *
foobar = CDLL("foobar.so")
foobar.fooize(4)

which obviously produce the following output when executed:

$ LD_LIBRARY_PATH=. python example.py
Fooized 4!

ctypes handled all the magic for me: it called dlopen(3) to access the dynamic library, it called dlsym(3) to access the symbol fooize, and it even handled marshalling of arguments. This is great.

But what happens if I want to package this application? Well, with py2exe/py2app, it wouldn’t work. In fact, they would totally miss the dependency of the example program on the foobar.so file. This obviously happens because they support only the simplest forms of dependency: a plain Python import statement or dependencies between shared librarys (eg: foo.dll that depends on bar.dll).

Now, watch PyInstaller in action:

$ python ~/src/pyinstaller/Makespec.py --onefile example.py
wrote /tmp/ct/example.spec
now run Build.py to build the executable
$ python ~/src/pyinstaller/Build.py example.spec
checking Analysis
building Analysis because outAnalysis0.toc non existent
running Analysis outAnalysis0.toc
Analyzing: /home/rasky/src/pyinstaller/support/_mountzlib.py
Analyzing: /home/rasky/src/pyinstaller/support/useUnicode.py
Analyzing: example.py
Warnings written to /tmp/ct/warnexample.txt
checking PYZ
rebuilding outPYZ1.toc because outPYZ1.pyz is missing
building PYZ outPYZ1.toc
checking PKG
rebuilding outPKG3.toc because outPKG3.pkg is missing
building PKG outPKG3.pkg
checking EXE
rebuilding outEXE2.toc because example missing
building EXE from outEXE2.toc
Appending archive to EXE /tmp/ct/dist/example
$ ./dist/example
Fooized 4!
$ ls -la ./dist
totale 2927
drwxr-xr-x 2 rasky rasky      72 2010-03-19 03:33 .
drwxr-xr-x 4 rasky rasky     344 2010-03-19 03:33 ..
-rwxr-xr-x 1 rasky rasky 2991835 2010-03-19 03:33 example

It simply worked. What PyInstaller behind the hood is:

• Scan the bytecode of example.py, looking for usages of ctypes
• Collect all the shared libraries used by ctypes calls. Notice that it can’t infer all filenames potentially used by the source code (how would you handle the case where the library named is specified interactively by the user?), but it handles all simple cases (see this page for more details).
• Resolve pathnames using the OS’ library search path.

Notice how foobar.so was also included within the single-file package produced by PyInstaller. And how can this possibly work? Let strace show us the trick:

$ strace -ff ./dist/example 2>&1 | grep foobar.so
stat("/tmp/_MEIDG0H9t/foobar.so", 0x7fff92f09480) = -1 ENOENT (No such file or directory)
open("/tmp/_MEIDG0H9t/foobar.so", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 4
[pid 13942] open("/tmp/_MEIDG0H9t/foobar.so", O_RDONLY) = 6
stat("/tmp/_MEIDG0H9t/foobar.so", {st_mode=S_IFREG|0700, st_size=7985, ...}) = 0
unlink("/tmp/_MEIDG0H9t/foobar.so")     = 0

What happens at runtime is that foobar.so is extracted in a temporary directory, so that ctypes can find it.

So: PyInstaller is designed to do everything required to package an application. If you like this philosophy and you are tired of chasing workarounds in wikis, you should give it a try!

• HTML5 for videos (H.264), which means that we will be holding a Adobe “Flash For Video” funeral pretty soon now. I notice that most geeks don’t care about usages of Flashes besides videos, but there are still many of them (both filling gaps in HTML standard, like in the case of multi-file uploads, and for animations/interactions/games where HTML5 Canvas+JS is still too slow).
• Fast JavaScript engine: aka JIT. Given how slow IE8 is in benchmarks, this is very good news for development of rich web applications on the Internet.
• CSS3, DOM, SVG: they are really supporting a lots of new features available in nowadays standards. I think the support for SVG will make many people wonder if Christmas came for Easter this year. And yes, it is indeed coming.

A very interesting news is that Microsoft is announcing GPU Acceleration for IE9. Now, we are a little short on details (and I’m not at MIX10 where IE9 is being presented) but I still see legends floating around.

Microsoft: not so much graved in stone anymore, it seems (Image via Wikipedia)

First, there is absolutely no way that IE9 (or any browser, for that matter) could offload to the GPU the whole Javascript engine (and not even the compilation step required by the JIT). Modern GPUs are massively paralleled calculators. They are very good at executing a 100-lines mathematical function at the same time in 4096 cores, which is exactly what you need to do graphics (2D, 3D, whatever) and heavy calculations like physics, simulations, and so on; but they can’t really go beyond this. Moreover, there is a measurable overhead in starting each GPU task (use DMA to fill internal memory, upload the task) and fetching results (DMA the results off the video memory into main RAM).  So there is basically no way to use such a horse for running custom Javascript code.

In fact, what Microsoft is saying is that it will recompile Javascript in a different thread/process, offloading it to a different core of the CPU. This is probably a step forward in the right direction. IE8 already had a multi-process architecture much like Chrome does, and offloading the JIT itself to another process looks like a very good idea. I wonder what Chrome developers think of it.

So, what about GPU acceleration? It will be used in these main areas:

• Video decoding: Modern video cards have hardware support for H.264 decompression. This is already supported by Windows drivers, and if you use a Windows system to watch a H.264 HD video, you will see that the CPU usage is indeed pretty low. Alas, since H.264 is a patent encumbered format, this acceleration is not supported in Linux and probably will never be. The most Linux can achieve is YUV HW compositing, which is nothing like offloading the whole H.264 decoding to hardware.
• HTML5 Canvas: through the new Direct2D API, it will be easier to leverage hardware acceleration within Canvas. Notice that Direct2D, to the best of my understanding, is just a better API (both at the user-space level and driver level) to access the existing programmable graphics hardware. It is not different from what Cairo or Qt’s QPainter already offer, but it is fully accelerated. If you use Firefox on Linux, you get cairo -> xlib -> xrender, and then you’re doomed.
• Font rendering: rendering text is a big part in a browser, and the new DirectWrite API will take care of hardware acceleration for fonts. DirectWrite is a whole font-rendering stack that has been designed with hardware acceleration in mind. It is like Freetype of the next millennium. I believe there is absolutely no equivalent for DirectWrite in the OSS world.

I plan to do a quick benchmark of IE9 this week. I will specifically be focusing on HTML5 canvas rendering, since that is the part where it is meant to shine, even compared to Chrome.

Stay tuned!

This is my first attempt in many years to maintain a blog. Many people have encouraged me to open a blog in the past few years, but my previous attempts were not very successful. So let’s see how this works out. I’m not good at introductions (I do skip them myself, while starting books), so let’s call it a day post.