Optimizing MySQL and Apache for a low-memory VPS.

Diagnosing the problem.

My last post had a plug about the migration of our WordPress instance to a new server. However, it didn’t go completely smoothly. The site had gone down a few times in the first day after the migration, with WordPress throwing “Error establishing a database connection.” Sure enough, MySQL had gone down. A simple restart of MySQL would bring the site back up, but what caused the crash in the first place?

A peek into /var/log/mysql/error.log yielded this:

2016-10-12T21:20:50.588667Z 0 [ERROR] InnoDB: mmap(137428992 bytes) failed; errno 12
2016-10-12T21:20:50.588702Z 0 [ERROR] InnoDB: Cannot allocate memory for the buffer pool
2016-10-12T21:20:50.588728Z 0 [ERROR] InnoDB: Plugin initialization aborted with error Generic error
2016-10-12T21:20:50.588749Z 0 [ERROR] Plugin 'InnoDB' init function returned error.
2016-10-12T21:20:50.588758Z 0 [ERROR] Plugin 'InnoDB' registration as a STORAGE ENGINE failed.
2016-10-12T21:20:50.588767Z 0 [ERROR] Failed to initialize plugins.
2016-10-12T21:20:50.588772Z 0 [ERROR] Aborting

So it looks like an out-of-memory error. This VPS only has 512 MB of RAM, so I wouldn’t be surprised. Clearly, some tuning would be necessary. First, we’ll reduce the size of MySQL’s buffer pool, then shrink Apache’s worker pool, and finally add a swapfile just in case memory pressure remains a problem.

Optimizing MySQL.

The error that we saw was for the allocation of a buffer pool for InnoDB, one of MySQL’s storage engines. We can see from the log that it’s trying to allocate somewhere around 128 MB using mmap. This corresponds to the default value of the innodb_buffer_pool_size configuration option. Let’s go ahead and trim this down to about 20 MB — it’ll reduce MySQL’s performance, but we don’t have much of a choice on a machine this small.

On Ubuntu, I put this option in /etc/mysql/mysqld.conf.d/mysqld.cnf:

innodb_buffer_pool_size = 20M

Issue sudo service mysql restart, and rejoice as MySQL no longer uses 25% of your RAM.

Optimizing Apache.

Most of Apache’s memory usage comes from the fact that it preemptively forks worker processes in order to handle requests with low latency. This is handled by the mpm_prefork module, and if enabled, its config can be found in /etc/apache2/mods-enabled/mpm_prefork.conf (on Ubuntu, at least).

By default, Apache will create 5 processes at startup, keep a minimum of 5 idle processes at all times, allow up to 10 idle processes before they’re reaped, and spawn up to 256 processes at a time under load. Let’s reduce these to something more sane given the constraints of our system:

<IfModule mpm_prefork_module>
 StartServers 3
 MinSpareServers 3
 MaxSpareServers 5
 MaxRequestWorkers 25
 MaxConnectionsPerChild 0

Now, sudo service apache2 restart and you’re done.

Creating a swapfile.

Most VPSes don’t give you a swap partition by default, like you would probably create on a dedicated server or your desktop. We can create one using a file on an existing filesystem, in order to make sure there’s extra virtual memory available in case our tuning doesn’t handle everything perfectly.

First, let’s pre-allocate space in the filesystem. We can do this using the fallocate command. I made a 2 GB swapfile:

sudo fallocate -l 2G /swapfile

Now, give it some sane permissions:

sudo chmod 600 /swapfile

Next, format the file so it looks like a swap filesystem:

sudo mkswap /swapfile

And finally, tell the OS to use it as swap space:

sudo swapon /swapfile

Now, we’ve got swap for the time being, but it won’t persist when we reboot the system. To make it persist, simply add a line to /etc/fstab:

/swapfile none swap sw 0 0

Congratulations, you’re now the proud owner of some swap space.

Hopefully this post will help anyone suffering stability problems with MySQL and Apache on a small VPS. I’ve adapted the instructions here from several sources, most notably this StackOverflow post, and this article from DigitalOcean.

This blog is illegal!

At Zeall, we offer our employees the courtesy of free hosting for their personal blogs, in hopes of furthering their professional image. Today, we completed the migration of the employee Wordpress instance from a shared hosting provider to its own VPS, and simultaneously deployed TLS certificates (thanks, Let’s Encrypt!) for all domains hosted there (including this one).

Our TLS deployment is perhaps a bit untimely, as it comes just a few days behind news that the UK is prosecuting someone for “developing an encrypted version of his blog site.”

Now, in the interest of reducing the clickbait-factor of this article, I’ll comment that it’s a terrorism case, and there is apparently some evidence that this guy was planning something sinister. Even so, running a blog over HTTPS is hardly something that should be tacked on to his case.

I don’t disagree with the fact that charges were brought against this guy, but I am pretty upset that crypto is pretty much illegal in the UK. The law currently considers anything pertaining to crypto research, education, or deployment to be terrorism. So if you’re reading this right now, you’re guilty. 😉

Information-centric networking for laymen.

The design of the current Internet is based on the concept of connections between “hosts”, or individual computers. For example, when you visit a website, your computer (a host) always connects to a particular server (another host) and retrieves content through a session-oriented pipe. However, the amount of content hosted on the Internet and the number of connected devices are both growing. This is a crisis scenario for the current Internet architecture — it won’t scale.

Several proposals for Next-Generation Network (NGN) architectures have been proposed in recent years, aimed at better handling immense amounts of traffic and orders of magnitude more pairwise connections. Information-Centric Networking (ICN) is one NGN paradigm which eschews the concept of connections entirely, removing the host as the basic “unit” of the network and replacing it with content objects.

In other words, the defining feature of an ICN is that instead of asking the network to connect you to a particular server (where you may hope to find a content you desire), you instead ask the network for the content itself.

Several distinct ICN architectures have been proposed, however for the remainder of this article I will focus on Named-Data Networking (NDN) and Content-Centric Networking (CCN), the two most popular designs in recent literature. NDN and CCN both share the core concept of consumer-driven communication, wherein a consumer (or client) issues an Interest packet (a request) for a content object and hopes to receive a Data packet in return. Interest and Data packets are both identified by a Name, which is in essence a immutable, human-readable name for a particular content object.

Whereas current Internet routers rely on only one lookup table (i.e., a forwarding table) in order to route packets toward a destination, NDN/CCN routers use three main data structures in order to locate content objects. A Pending Interest Table (PIT) keeps track of outstanding requests, a Content Store (CS) caches content objects, and a Forwarding Information Base (FIB) stores default forwarding information.

When a router receives an Interest, it will first check its CS to see if it can serve the content immediately from its cache. If it is not found there, then the router checks its PIT to see if there is an outstanding request for the same content; if there is then the request does not need to be forwarded again, since the data for the previous request can satisfy both that request and the new one. Finally, if an existing Interest is not found, the router checks the FIB for a route toward the appropriate content provider; once a route has been identified, the Interest is forwarded and the PIT is updated.

Though ICN requires routers to store more state and make more complicated forwarding decisions, it is still expected to reduce the overall network load by virtue of Interest aggregation and content caching. Caching in particular also benefits the end-user, since the availability of content nearby reduces download time. Since content downloads are independent of any particular connection, ICN also allows multi-RAT (Radio Access Technology) communication to be exploited by mobile devices, further improving the user’s QoE (Quality-of-Experience).

Last week, I presented a collaborative caching scheme for NDN at ACM ICN 2016, the leading conference in the ICN domain (slides, paper) which is able to satisfy up to 20% of Interests without leaving the home ISP’s network. Additionally, we published an article in IEEE Communications Magazine about the advantages of ICN for mobile networks (paper). These works, as well as those of the larger ICN community, have the potential to influence the acceptance of ICN as the foundation of the future Internet. Only with continued research will we find a holistic solution for scalability in the face of billions of connected devices and billions of terabytes of traffic.

Why are tuples greater than lists?

I pose this question in quite a literal sense. Why does Python 2.7 have this behavior?

>>> (1,) > [2]

No matter what the tuple, and no matter what the list, the tuple will always be considered greater. On the other hand, Python 3 gives us an error, which actually makes a bit more sense:

>>> (1,) > [2]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: unorderable types: tuple() > list()

The following post is a journey into some CPython internals, with a goal of finding out why 2.7 gives us such a weird comparison result.

Those of you who have implemented nontrivial classes in Python are probably aware of the two different comparison interfaces in the data model: rich comparison, and simple comparison. Rich comparison is implemented by defining the functions __lt__, __le__, __eq__, __ne__, __gt__, and __ge__. That is, there is one function for each possible comparison operator. Simple comparison uses only one function, __cmp__, which has a similar interface to C’s strcmp.

Any comparison operation you write in Python compiles down to the COMPARE_OP bytecode, which itself is handled by a function called cmp_outcome. For the types of comparisons we’re concerned with today (i.e., inequalities rather than exact comparisons), this function will end up calling PyObject_RichCompare, the user-facing comparison function in the C API.

At this point, the runtime will attempt to use the rich comparison interface, if possible. Assuming that neither operand’s class is a subclass of the other, the first class’s comparison functions will be checked first; the second class would be checked if the first class does not yield a useful result. In the case of tuple and list, both calls return NotImplemented.

Having failed to use the rich comparison interface, we now try to call __cmp__. The actual semantics here are quite complicated, but in the case at hand, all attempts fail. One penultimate effort before hitting the last-ditch “default” compare function is to convert both operands to numeric types (which fails here, of course).

CPython’s default_3way_compare is somewhat of a collection of terrible ideas. If the two objects are of the same type, it will try to compare them by address and return that result. Otherwise, we then check if either value is None, which would be considered smaller than anything else. The second-to-last option, which we will actually end up using in the case of tuple vs. list, is to compare the names of the two classes (essentially returning strcmp(v->ob_type->tp_name, w->ob_type->tp_name)). Note, however, that any numeric type would have its type name switched to the empty string here, so a number ends up being considered smaller than anything non-numeric. If we end up in a case where both type names are the same (either they actually have the same name, or they are incomparable numeric types), then we get a final result by comparing pointers to the type definitions.

To validate our findings, consider the following:

>>> tuple() > list()
>>> class abc (tuple):
... pass
>>> abc() > list()
>>> class xyz (tuple):
... pass
>>> xyz() > list()

The only difference between classes abc and xyz (and tuple, even) are their names, however we can see that the instances are compared differently. Now, we have certainly found quite the footgun here, so it’s fortunate that Python 3 has a more sane comparison operation.

The single most hideous line of code I’ve ever seen

Have you ever used a ternary expression inside a condition? I hope not. It seems that whoever wrote the Java drivers for MongoDB didn’t have this much sense.

The offending line of code can be found here: ConnectionStatus.java

It basically goes like this:

try {
    // a bunch of stuff
} catch (Exception e) {
    if (!((_ok) ? true : (Math.random() > 0.1))) {
        // silently ignore error
    else {
        // log error

The intent appears to be to log just 10% of errors that result in an “okay” status, while logging all “not okay” errors. However, this condition is utterly unreadable, and I believe this awful implementation actually yields the opposite result.

I’m not even going to talk about how revolting this line of code is. Instead, I will dedicate the rest of my post to trying to figure out its logic. Let’s start by breaking down that ternary statement into something that makes a little more sense.

bool condition;

if(_ok) {
    condition = true;
else {
    condition = Math.random() > 0.1;

if(!condition) {
    // silently ignore error
else {
    // log error

Now we can see that “condition” is true if either the “ok” flag is true, or we drew a random number greater than 0.1 (90% chance). Therefore, we can write this:

if(!(_ok || Math.random() > 0.1)) {
    // silently ignore error
else {
    // log error

Now, applying the negation (using DeMorgan’s law):

if(!_ok && Math.random() <= 0.1) {
    // silently ignore error
else {
    // log error

So what is the result? We silently ignore 10% of “not-okay” error conditions. We log 90% of “not-okay” errors, and all of the “okay” errors. Is there a chance this was the intended behavior? Sure. Does it make sense? Hell no.

The moral of this story: code review is important.

Quick postfix & dovecot config with virtual hosts (Ubuntu 16.04)

This morning, I received an email from my VPS host notifying me that they will no longer accept PayPal. Instead, my only payment option would be Bitcoin. Not willing to go through this trouble, I decided to migrate from this host (which I had been using for my personal servers for about five years now) to DigitalOcean (which fortunately accepts normal forms of payment).

Part of my server migration was to move email for two of my domains: le1.ca and lo.calho.st. Setting up a new mailserver is a notoriously arduous task, so I’m documenting the process in this post — mostly for my future reference, but also to benefit anyone who might stumble upon my blog in their own confusion.

Since I’m serving mail for two domains, I will be using a simple “virtual hosts” configuration. I’ll talk about the process in four parts: local setup, postfix, dovecot, and DNS configuration.

Local Setup

We must prepare a few things before we’re ready to configure the actual mail services. The first thing I’d like to do is install a SSL certificate, so that we can access the mail server securely. This is easy with Let’s Encrypt:

$ sudo apt-get install letsencrypt # (if you don't have it installed already)
$ letsencrypt certonly --standalone -d mail.le1.ca -d mail.lo.calho.st

I’m using the standalone option here, because I do not have an HTTP daemon installed on this server. If you’re also serving HTTP from your mail machine, you will need to follow the appropriate instructions for your configuration.

Now that we have an SSL cert, we can set up the directory structure for our virtual mailboxes. I’m going to make the root for this environment /var/spool/mail, and in that directory, I’m going to create one folder for each domain I’m serving:

$ mkdir -p /var/spool/mail/le1.ca
$ mkdir -p /var/spool/mail/lo.calho.st

The next step is to configure passwords for each of your users. I’m doing this the easy way, since I’m the only person using the mail server. If you need users to be able to change their own passwords, this is going to be more difficult; you’ll need to find an alternate authentication configuration.

You will need to calculate a password hash for each user you want to serve:

$ doveadm pw -u foo@le1.ca

Each time, it should spit out a hash that looks like this:


For each of your domains, create a ‘shadow’ file in the corresponding /var/spool/mail/* directory. For example, I will create /var/spool/mail/le1.ca/shadow. Add a username:password line for each virtual user you want to create.


Next, let’s create a “virtual mail” user and configure him as the owner of these mail directories.

$ sudo adduser vmail
$ sudo chown -R vmail:vmail /var/spool/mail/

Find out the UID and GID of this new user and remember it for later. An easy way to do this is grep vmail /etc/passwd. The UID and GID are the third and fourth columns, respectively.

That’s it for initial setup. Now let’s deal with postfix.

Configuring Postfix

Postfix is responsible for delivering received mail to the correct locations on our server, as well as sending mail on our behalf.

There’s some initial configuration we can do interactively before we start poking around in config files. If you haven’t installed postfix yet, this configuration will start automatically when you do apt-get install postfix. If you do already have it installed, then you can run dpkg-reconfigure postfix to get there.

Here are the responses you should enter to this wizard:

  • Type of mail configuration: Internet Site
  • System mail name: Use your “primary” mail domain here. I used “le1.ca”
  • Root and postmaster recipient: Enter your primary email address here. It will be used as the destination for administrative mail.
  • Destinations to accept mail for: Enter any aliases of your machine here, but don’t enter the domains you’re going to use in your virtual mailboxes. A good list is something like “my-hostname, localhost.localdomain, localhost”
  • Everything else: Leave it at the default value

The main configuration file for postfix is /etc/postfix/main.cf. Let’s break down the config into three sections: SSL, virtual mailboxes, and SASL. I’m only including lines that need to be modified here. Everything else should stay at its default value.

First, SSL-related configs:


Virtual mailbox configs:

virtual_mailbox_domains = /etc/postfix/virtual_domains
virtual_mailbox_maps = hash:/etc/postfix/virtual_mailbox
virtual_mailbox_base = /var/spool/mail
virtual_uid_maps = static:1001 # Replace with the UID of your vmail user
virtual_gid_maps = static:1001 # Replace with the GID of your vmail user

SASL configs (to pass authentication duties to Dovecot):

smtpd_sasl_auth_enable = yes
smtpd_sasl_type = dovecot
smtpd_sasl_path = private/auth
smtpd_sasl_security_options = noanonymous
smtpd_sasl_local_domain =
smtpd_relay_restrictions = permit_mynetworks permit_sasl_authenticated defer_unauth_destination
smtpd_recipient_restrictions = permit_sasl_authenticated, permit_mynetworks, reject_unauth_destination

Hopefully you noticed that the virtual mailbox configs refer to some new files. We’re going to have to create /etc/postfix/virtual_domains and /etc/postfix/virtual_mailbox in order to create the mappings for our domains.

The virtual_domains file is easy, just a list of the domains you’re serving. In my case:


The virtual_mailbox file is also pretty easy. It just maps email addresses to mailbox folders, relative to the virtual_mailbox_base directory. For example, if I want both foo@le1.ca and bar@le1.ca to go to the mailbox le1.ca/foobar, and baz@lo.calho.st to go to lo.calho.st/baz:

foo@le1.ca le1.ca/foobar/
 bar@le1.ca le1.ca/foobar/
 baz@lo.calho.st lo.calho.st/baz/

You can create as many aliases as you want here. Whatever is on the right will end up determining your login username (in this case, foobar@le1.ca and baz@lo.calho.st are my usernames), and the addresses on the left create aliases.

Postfix now requires us to hash this map file. Run the following command from within /etc/postfix:

$ postmap virtual_mailbox

This should create a file called virtual_mailbox.db.

The last part of the postfix config is to enable the “user-facing” SMTP port, 587. Just paste this block in master.cf somewhere:

submission inet n - y - - smtpd
-o smtpd_tls_security_level=encrypt
-o smtpd_sasl_auth_enable=yes
-o smtpd_sasl_type=dovecot
-o smtpd_sasl_path=private/auth
-o smtpd_sasl_security_options=noanonymous
-o smtpd_sasl_local_domain=$myhostname
-o smtpd_client_restrictions=permit_sasl_authenticated,reject
-o smtpd_sender_login_maps=hash:/etc/postfix/virtual_mailbox
-o smtpd_recipient_restrictions=reject_non_fqdn_recipient,reject_unknown_recipient_domain,permit_sasl_authenticated,reject

The next step is to configure dovecot.

Configuring Dovecot

Dovecot is much easier to configure than postfix. Create /etc/dovecot/dovecot.conf with the following content (delete it if it already exists):

protocols = imap
log_path = /var/log/dovecot.log

ssl = required
ssl_cert = </etc/letsencrypt/live/albatross.le1.ca/fullchain.pem
ssl_key = </etc/letsencrypt/live/albatross.le1.ca/privkey.pem
ssl_cipher_list = ALL:!LOW:!SSLv2:!EXP:!aNULL

disable_plaintext_auth = no
mail_location = maildir:/var/spool/mail/%d/%n

auth_verbose = yes
auth_mechanisms = plain login

passdb {
 driver = passwd-file
 args = /var/spool/mail/%d/shadow

userdb {
 driver = static
 args = uid=vmail gid=vmail home=/var/spool/mail/%d/%n

protocol lda {
 postmaster_address = root@le1.ca

service auth {
 unix_listener /var/spool/postfix/private/auth {
 mode = 0660
 user = postfix
 group = postfix

Now you should be ready to restart postfix and dovecot:

$ sudo service dovecot restart
$ sudo service postfix restart

If everything went smoothly, we’re ready to configure DNS records.

DNS Records

For each of your domains, you will need three DNS records:

  • Either a CNAME or an A record pointing to the mailserver
  • An MX record designating the mailserver as the destination for the domain’s mail
  • A SPF record designating the server as a permitted origin for mail

The A record is easy. Just create an A record for “mail.yourdomain.com” pointing to the IP address of the server.

The MX record might be even easier: set the mailserver for “yourdomain.com” to “mail.yourdomain.com”

The SPF record is also very straightforward. Many people overlook its importance, but without it, mail from your domain is likely to go into recipients’ spam folders. There exist wizards to create custom SPF records, but I find the one below to be sufficient for most purposes. Just insert this as a TXT record for “yourdomain.com”:

"v=spf1 mx a ptr ~all"

And that’s it. Allow a few minutes for your DNS records to propagate, then test out your new mailserver.

An easy way to visualize git activity

Today, I wrote gitply — a fairly simple Python script for visualizing the weekly activity of each contributor to a git repository.

It started out as a run-once script to get some statistics for one of my projects, but I ended up improving it incrementally until it turned into something friendly enough for other people to use.

What it does:

In short, gitply will show you how much code (and how many commits) a repository’s contributors have written each week. Its output looks something like this:


You’ll get a graph like this for each contributor. What all do we see here?

  • Lines inserted (green bars, left axis, log scale)
  • Lines deleted (red bars, left axis, log scale)
  • Commits made (blue line, right axis, linear scale)

You also get a textual representation of the same data:

History for anon2
  2016, week  6:  2 commits, +366  -26  
  2016, week  7:  4 commits, +325  -5   
  2016, week  8:  2 commits, +224  -3   
  2016, week  9: 21 commits, +2617 -219 
  -- Gap of 2 weeks
  2016, week 12: 10 commits, +4066 -614 
  2016, week 13:  6 commits, +2480 -432 
  2016, week 14:  2 commits, +654  -490 
  -- Gap of 1 week
  2016, week 16:  2 commits, +661  -229 
  -- Gap of 2 weeks
  2016, week 19:  3 commits, +1508 -47  
  -- Gap of 2 weeks
  2016, week 22:  1 commits, +1490 -29  

History for anon1
  2016, week 12:  1 commits, +143  -89  
  2016, week 13:  2 commits, +58   -16  
  2016, week 14:  3 commits, +137  -17  
  2016, week 15:  2 commits, +403  -106 
  -- Gap of 2 weeks
  2016, week 18:  5 commits, +134  -38  
  -- Gap of 3 weeks
  2016, week 22:  1 commits, +13   -1   
  2016, week 23:  1 commits, +485  -1   

If you just want to download it and use it already, check out the project on GitHub. For those who are interested, some implementation details follow.

How does it work?

The first thing gitply does is invoke the standard git client to retrieve a log:

git log --numstat --date=short --no-notes

Then, it analyzes the log line-by-line in real time (thanks, Python iterators) in order to get the data we need. Essentially, we create an iterator that yields tuples of (email, date, stats) for each commit, where stats is the pair (insertions, deletions).

Once we create this iterator over the commit history, we can attribute each commit to a user and ultimately fill in a dictionary that will help us print the analysis. We sum the insertions, deletions, and commits for each ISO week, then iterate through the weeks and print out the final results.

Now, if for some reason you need an iterator over the commits in a repository, you can import my iterate_commits function from this script and use it yourself.

What’s next?

Right now, gitply supports aggregating statistics from several repositories into one report. One planned feature is to use stacked bars and lines to show the amount of activity per-project, per-user, per-week. Until then, the data from multiple repositories will all be displayed together.

Adventures in image glitching

Databending is a type of glitch art wherein image files are intentionally corrupted in order to produce an aesthetic effect. Traditionally, these effects are produced by manually manipulating the compressed data in an image file. As a result, this is a trial-and-error process; often, edits will result in the file being completely corrupted and unopenable.

Someone recently asked me whether I knew why databending different types of image files produces different effects — and particularly, why PNG glitches are the most interesting. I didn’t know the answer, but the question inspired me to do a little research (mostly reading the Wikipedia articles about the compression techniques used in different image formats). I discovered that most compression techniques are not all that different. Most of them just employ some kind of run-length encoding or dictionary encoding, and then a prefix-free coding step. The subtle differences between the compression algorithms could not explain the wildly different effects we observed (except for in JPEGs, perhaps, since the compression is done in the frequency domain). However, PNG used a pre-filtering step which made it stand out.

PNG’s pre-filtering is basically a heuristic to try to make the image data more compressible. It tries to translate each pixel of the image into some delta based on pixels in the previous row or column. Since the core compression algorithms have no idea about the two-dimensional nature of an image, this two-dimensional filtering step actually makes a pretty big impact.

There are five main line filters defined by the PNG format. Most PNG encoders will try to optimize their choices of filters for each line in the image, in order to reduce the compressed size of the image. However, each filter also yields its own unique glitches.

Thus, an idea was spawned , and I wrote a Python script that glitches images not by manipulating their raw representations, but by applying one of the PNG filters and modifying the pixels in that representation.

PNG Filter Glitches

Since this article is about glitching — not image compression — we’re going to focus on the different visual effects we get from each filter. Usually, PNG codecs alternate between filters for each line, however for the sake of demonstration I configured my script to use one filter throughout the whole image.

All of the following glitches are made from a scale-down version of this wallpaper from Wallhaven.

Two of the simplest PNG filters are the Up filter and the Sub filter. While Up creates a delta from the adjacent pixel in the previous row, Sub creates a delta from the previous pixel in the same row. The results of glitching on the filters are similar — Up gives us vertical lines, and Sub gives us horizontal lines.

Glitch result from the Up filter

A more interesting one is the Average filter. This filter looks at the both the above-pixel and the left-pixel and takes their average, then computes a delta using that value. Glitching on the Average filter results in smears of altered color that slowly defuse away across the image.


My favorite is actually the Paeth filter, which heuristically chooses either the above-pixel, left-pixel, or above-and-to-the-left pixel as the basis for the delta, depending on a function of all three. Glitches applied to this filter give us rectangular disturbances which slowly fade out, however stack together to create harsher effects.


I mentioned that there are five filters, but so far I’ve only mentioned four. The reason for this is simple — the fifth filter is the Null filter, which has no effect whatsoever.

Mixing Filters

To simulate the mixed effects one can observe in a typical PNG glitch, I implemented a glitching procedure which uses a random filter on each line. The results are pretty intriguing:

Random line filters
Random line filters

In this example, I’ve only allowed a 5% chance for the filter to change from one line to the next; without this provision, the results are quite boring.

To make the glitches even cooler, I started stacking filters on top of each other. Here’s an example with an extra pass through the Average filter applied after the randomized filtering stage:

Randomized + Average
Randomized + Average

Glitch Glitches

Overall, my favorite filters were the ones that had bugs when I wrote them. My original implementation of the Paeth filter had an error due to the use of unsigned integers in the predictor (when really I needed signed ones). However, this version resulted in some cool effects that acted like a combination of the normal Paeth and Average behaviors:

Buggy Paeth filter
Buggy Paeth filter

I also wrote a buggy Average filter that resulted in some bold vertical lines and some subtler horizontal artifacts:

Buggy Average filter

Try it Yourself

I’ve posted my glitch scripts on GitHub, so you can try them out too. The original version was pure Python and incredibly slow, but I’ve now converted the core functionality into a C module and it is several orders of magnitude faster. This is also my first foray into the intricacies of the Python C API, but that’s a topic for another post…

To conclude, have two more glitches achieved by mixing various filters:

test (2)

test (1)

Blue Coat’s position as a Certificate Authority, and what it means for you.

Recently, Blue Coat Systems has been approved as an intermediate certificate authority. If you aren’t versed in network security, this means nothing to you. However, be assured that it is a big deal.

Blue Coat is primarily known as  a vendor of application-layer (deep packet inspection) firewalls. In other words, they help people sniff your data — primarily in order to censor the Internet. Maybe your company’s firewall blocks access to YouTube and Facebook while you’re at work. That’s no big deal — Blue Coat delivers something a bit more sinister.

Countries such as Burma, Syria, Bahrain, China, Egypt, Kuwait, Russia, and Saudi Arabia have utilized Blue Coat’s products (or similar offerings) to enable Internet censorship and tracking. This is not a good reputation to carry. However, Blue Coat’s impact has been limited to unencrypted traffic thus far. Now that they are a trusted CA, they’re capable of much more.

In this article, I will give an overview of how our Internet communications are normally secured, then explain why it is a problem that Blue Coat how has this authority.

What is a Certificate Authority?

To encrypt data on the Internet, we use a protocol called Transport Layer Security, or TLS (you might be more familiar an older but similar protocol called SSL, or Secure Sockets Layer). Basically, if a URL starts with https://, then you’re accessing it through TLS; if your browser shows you a green lock icon (or something similar), you can typically be assured that your connection is secure.

A browser will trust a website and display this lock icon if it presents a valid certificate signed by a trusted certificate authority (CA). A certificate is a pretty simple thing — it is essentially just a public key for the website, accompanied by the signature of a CA. Your operating system (or web browser, depending on which one you use) trusts a handful of CAs by default. These are called root CAs. However, root CAs can often delegate the authority to sign certificates to other entities called intermediate CAs. Intermediate CAs don’t have to be explicitly trusted by your computer; the fact that a root CA has vouched for them makes them trusted by extension. Because another CA has vouched for them, Blue Coat is now capable of issuing certificates.

How can a CA be harmful?

To understand Blue Coat’s new role might be harmful, it is important to know a few more details about certificates and how they’re used.

A certificate is always restricted to some domain name (effectively representing a single website). Normally, a CA only gives a website a certificate if it can prove that it is legitimately operating under the name that they have requested; consequently, the certificate is tied to that name and won’t be valid for any other website.

Normally, a rogue website can’t impersonate a legitimate website because it will be unable to obtain a certificate for the website’s domain name. If the rogue site does somehow obtain a certificate, there is essentially no way for a normal user to know they aren’t visiting the legitimate site. We rely on CAs to check that any entity requesting a certificate can prove that it is authorized to represent the domain that it wants a certificate for; this is the entire basis of our security and privacy on the Internet.

Okay, so what?

Since Blue Coat produces hardware and software that enables Internet censorship, we can only imagine how badly they’re itching to be able to sniff our TLS-encrypted Internet traffic to be able to filter it. In order to sniff traffic arbitrarily, they would need to essentially impersonate whatever website you want to reach. Impersonating a website in this way is called a man-in-the-middle (MiTM) attack.

In general, a man-in-the-middle attack works like this:

  • You try to connect to example.com.
  • I intercept your connection so that you connect to my server instead.
  • I act as a middleman between you and example.com, and I am able to filter and manipulate your conversation however I want.

TLS normally prevents this. In the case that TLS is being used, a normal connection would work like this:

  • You try to connect to example.com.
  • Example.com sends you a certificate, signed by some CA.
  • You check to see if the certificate is valid, and decide that it is okay; you then proceed to communicate with example.com.

A MiTM against a TLS-secured website would typically go like this:

  • You try to connect to example.com.
  • I intercept the connection so that you connect to my server instead.
  • I send you a bogus certificate.
  • You look at my certificate and decide it is fake, and disconnect.

This is great; this is what should happen if someone manages to intercept your connection to a website. However, if a company like Blue Coat is a CA, they can actually create a fake certificate in order to pull off the MiTM successfully:

  • You try to connect to example.com.
  • Blue Coat intercepts the connection so that you connect to their server instead.
  • They send you a certificate that looks legitimate, since they have signed it and you trust them as an intermediate CA.
  • You accept the certificate, then proceed to communicate with them instead of the website you intended.
  • Blue Coat can monitor and filter your conversation with example.com however they see fit.

It should be clear why this is a huge problem for security and privacy on the Internet. Essentially, a de-facto lord-of-the-web (a CA) has given Blue Coat free reign to impersonate whatever website they want to. As a result, you can be easily fooled into thinking your connection is secure when really it can be monitored or filtered by a government, corporation, or some other potentially-malicious entity.

What can I do about it?

If you run a website where security and privacy are a concern, you should be employing a mechanism called Key Pinning. This will essentially allow a user’s browser to detect if your site’s purported certificate isn’t signed by the entity you’d expect. It is not foolproof, but will work most of the time unless the user has been subjected to the MiTM ever since their first visit to your site.

If you’re just an end-user, you might want to explicitly distrust Blue Coat. This will essentially tell your computer/browser that despite its certificate being signed by an otherwise-trustworthy CA, you should not trust the certificates that it signs. Apparently, it is pretty easy on OS X but is a little more difficult on Linux because it has a more varied trust ecosystem. I have not yet been able to obtain any information about untrusting the certificate on Windows.

Unnecessary mathematics: queuing delay for two types of network traffic

This morning I asked myself what I thought was an interesting question:

  • If there are two types of traffic in a network, where one is much less common than the other, will the two types experience different queuing delays?

If you have more common sense than me, you’ve already figured out that the answer is “No.” But it took me about an hour to figure this one out.

I designed a simple model of the scenario: there is a queue of N packets, and one of them is of a different type than the rest. Let’s call the two types A and B.

We can assume that the position in the queue reflects the queuing delay of the packet, so then we only need to be interested in the average position in the queue for each type of traffic: E[P(A)] , and E[P(B)].

We assume that there are N-1 packets of type A, and one packet of type B. We can place the type-B packet at any of the N positions in the queue with equal probabilities:

  • E[P(A)] = \frac{1}{N} \sum_{i=0}^{N-1} \left( \frac{1}{N-1} \left( \left( \sum_{j=0}^{N-1} j\right) - i \right) \right)
  • E[P(B)] = \frac{1}{N} \sum_{i=0}^{N-1} \left( i \right)

The term summed in the formula for E[P(A)] represents the average position of all N-1 type-A packets. In E[P(B)], there is only one packet so the term doesn’t need another sum inside of it.

Well, it turns out that E[P(A)] and E[P(B)] both simplify to \frac{N-1}{2}.

This should be immediately obvious in the formula for E[P(B)], and it takes just a little more work to derive for E[P(A)]. Yep, it couldn’t have been simpler.

If you think about it, this result makes a lot of sense and I shouldn’t have needed to compute it — if I’m at a random position in line, then so is everyone else. So it doesn’t matter whether I’m averaging over a group of N-1 people, or only worrying about myself. We’ll all wait the same amount of time (on average, of course).