Boost Range for Humans

Boost Range encapsulates the common C++ pattern of passing begin/end iterators around by combining them into into a single range object. It makes code that operates on containers much more readable. One wonders why such functionality was not included in the C++ standard library in the first place, and indeed, similar ideas could be added to C++17, see N4128 and Ivan Cukic's Meeting C++ presentation. In my opinion, Boost Range is something that every C++ programmer should know about.

The library is reasonably well documented, but I was often missing concrete code examples and an explicit mention what headers are required for which function. Since this presumably happens to other people as well, I invested the time to change that situation.

Thus, I present Boost Range for Humans. It contains working example code for every function in Boost Range, along with required headers and links to the official documentation and the latest source code. I hope it will make Boost Range more accessible and furthers its adoption.

Next week, we'll look into some of the highlights of what Boost Range can offer.

published tagged boost, c++

Debugging riddle of the day

One of our services failed to start on a test system (Ubuntu 12.04 on amd64). The stdout/stderr log streams contained only the string “Permission denied” – less than helpful. strace showed that the service tried to create a file under /run, which it doesn't have write permissions to. This caused the it to bail out:

open("/run/some_service", O_RDWR|O_CREAT|O_NOFOLLOW|O_CLOEXEC, 0644) = -1 EACCES (Permission denied)

Grepping the source code and configuration files for /run didn't turn up anything that could explain this open() call. Debugging with gdb gave further hints:

Breakpoint 2, 0x00007ffff73e3ea0 in open64 () from /lib/x86_64-linux-gnu/libc.so.6
(gdb) bt
#0  0x00007ffff73e3ea0 in open64 () from /lib/x86_64-linux-gnu/libc.so.6
#1  0x00007ffff7bd69bf in shm_open () from /lib/x86_64-linux-gnu/librt.so.1
#2  0x0000000000400948 in daemonize () at service.cpp:93
#3  0x00000000004009ac in main () at main.cpp:24
(gdb) p (char*)$rdi
$1 = 0x7fffffffe550 "/run/some_service"
(gdb) frame 2
#2  0x0000000000400948 in daemonize () at service.cpp:93
9           int fd = shm_open(fname.c_str(), O_RDWR | O_CREAT, 0644);
(gdb) p fname
$2 = {...., _M_p = 0x602028 "/some_service"}}

The open("/run/some_service", ...) was caused by an shm_open("/some_service", ...).

This code is working on other machines, why does it fail on this particular one? Can you figure it out? Bonus points if you can explain why it is trying to access /run and not some other directory. You might find the shm_open() man page and source code helpful.

I'll be waiting for you.

Caaaaaaaaat!

The solution is pretty evident after examining the Linux version of shm_open(). By default, it tries to create shared memory files under /dev/shm. If that doesn't exist, it will pick the first tmpfs mount point from /proc/mounts.

In Ubuntu 12.04, /dev/shm is a symlink to /run/shm. On this machine the symlink was missing, which caused shm_open() to go hunting for a tmpfs filesystem, and /run happened to be the first one in /proc/mounts.

Re-creating the symlink solved the problem. Why it was missing in the first place is still unclear. In the aftermath, we're also improving the error messages in this part of the code to make such issues easier to diagnose.


libconf - a Python reader for libconfig files

This weekend, I uploaded my first package to PyPI: libconf, a pure-Python reader for files in libconfig format. This configuration file format is reminiscent of JSON and is mostly used in C/C++ projects through the libconfig library. It looks like this:

version = 7;
window: {
   title: "libconfig example"
   position: { x: 375; y: 210; w: 800; h: 600; }
};
capabilities: {
   can-do-lists: (true, 0x3A20, ("sublist"), {subgroup: "ok"})
   can-do-arrays: [3, "yes", True]
};

There are already two Python implementations: pylibconfig2 is a pure-Python reader licensed under GPLv3 and python-libconfig provides bindings for the libconfig C++ library. The first one I didn't like because of it's licensing, the second one I didn't like because of the more involved installation procedure. Also, I kind of enjoy writing parsers.

So, I set down during the easter weekend and wrote libconf. It's a pure-Python reader for libconfig files with an interface similar to the Python json module. There are two main methods: load(f) and loads(string). Both return a dict-like data-structure that can be indexed (config['version']), but supports attribute access as well (config.version):

import libconf
>>> with open('example.cfg') as f:
...     config = libconf.load(f)
>>> config['window']['title']
'libconfig example'
>>> config.window.title
'libconfig example'

It was a fun little project. Creating a recursive descent parser is pretty straightforward, especially for such a simple file format. Writing documentation, packaging and uploading to GitHub and PyPI took longer than coding up the implementation itself.

published tagged Python


Requesting certificates the whirlwind way

As a follow-up to last post, let's take a closer look at certificates. Specifically, when you'd want one and how you'd go about obtaining it.

When would you need a certificate?

The most common reason is to provide access to a service over a secure connection, e.g. HTTPS for web traffic or IMAPS for emails. This requires a certificate signed by a CA that's recognized by browsers and operating systems. Signatures by these CAs indicate control over the internet domain for which the certificate was issued (e.g. greek0.net). They are used to prove to users that they are talking to the real thing, not to some scammer who hijacked their internet connection. This kind of certificate is often called "server certificate".

Instead of proving the identity of a server, certificates can also be used to authenticate a client. Unsurprisingly, this is called "client certificate" and can serve as a more secure alternative to password-based authentication. For example, Apple Push Notifications (for sending notifications to apps on an iPhone) require a certificate signed by Apple to prove that someone is allowed to send push notifications. Several VPN technologies also rely on client certificates for authentication.

How do you go about obtaining a certificate?

You need to create a certificate signing request (CSR) and submit it to the CA. Last time we saw that a certificate consists of a keypair identifier (hash), metadata, and signatures. A CSR contains only the first two of these: a hash that uniquely identifies a keypair and metadata relating to the intended use of the certificate.

Obviously, this means there can be no CSR without a keypair!1

For most purposes, it's best to start with a new keypair that hasn't been used anywhere else. So we'll first generate that and then create a CSR for it.

Those are two pretty simple operations, they just get complicated by the horrific user interface of OpenSSL. For most people, these commands equate to mystical incantations that must be recited to work their magic. That's unfortunate: it just deepens the confusion about how this certificate shebang is supposed to work. OpenSSL is the most widely available and popular tool for the job, though, so for better or worse we'll have to put up with it.

On Linux, OpenSSL should be available from the package manager, if it isn't installed already. On MacOS, OpenSSL is probably pre-installed, if not, it can be obtained from Homebrew. Windows binaries can be found here.

Creating a CSR

First, generate a keypair:

openssl genrsa -out certtest.key 2048

This will write a new keypair to the file "certtest.key". The number 2048 is the desired key size, with larger keys being more secure but also slower. As of 2016, 2048 bits is a reasonable default.

Next create a CSR for that keypair:

openssl req -new -sha256 -key certtest.key -out certtest.csr

OpenSSL will ask some questions to set the CSR metadata. For server certificates, the crucial field is "Common Name", which has to be the internet address of the server the certificate is intended for. The other fields are for informational purposes only. You may set them, or you may write a single dot (".") to leave the field blank. Not typing anything at all at the question prompts will give you OpenSSL's default values, don't do that.

Here is a screen capture of the process:

csr-generation-graphic

Before submitting the CSR for signing, it's a good practice to re-check the metadata fields:

openssl req -noout -text -in certtest.csr

This outputs several lines of data, the important part is the "Subject" line at the very top. Check that all the fields are what you expect them to be.

Submitting the CSR for signing

The details of submitting a CSR for signing vary from CA to CA, typically it involves an upload on a web page. Depending on the intended use of the certificate, additional steps may be required, such as proving your real-life identity and/or proving that you have control over some domain (for server certificates). Fortunately, these steps are typically quite thoroughly described in the CA's documentation or on the internet.

After the submission, it may take some time for the certificate to be signed, then you can download it from the CA's web page.

Pretty simple, right?


1 For users of the Apple Keychain application this can be a bit confusing, because there is an assistant to generate CSR's, but it doesn't mention keypairs anywhere. Under the hood, it does create a new keypair and add it to the keychain, it just doesn't tell you.


A whirlwind introduction to the secure web

How secure internet connections work is often a mystery, even for fairly technical people – let's rectify this!

Although some fairly complicated mathematics lays the foundation, it's not necessary to grasp all of it to get a good high-level understanding of the secure web. In this post, I'll give an overview of the major components of the secure web and of how they interact. I want to shed some light on the wizardry that both your browser and webservers do to make secure communication over the internet possible. Specifically, the focus is on authentication: how the public key infrastructure (PKI) guarantees you that you are really talking to your bank not to some scammer.

This is going to be a high-level overview with a lot of handwaving. We'll gloss over some of the nitty gritty details, and focus on the big picture.

Keypairs

Let's start off with the basic building block of public-key cryptography, the public/private keypair. It consists of two halves: the public part can be shared with the world, the private half must stay hidden, for your eyes only. With such a keypair, you can do three pretty nifty things:

  • People can encrypt data with your public key, and only you can decrypt it.
  • You can prove to other people (who have your public key) that you know the private key. In some sense, they can verify your identity.
  • You can sign data with your private key, and everyone with the public key can verify that this data came from you and was not tempered with.

Let's look at an example to see how cool this is: let's say your bank has a keypair and you know their public key (it could be printed in large letters on the walls of their building, it's public after all). You can then securely communicate with your bank, without anyone being able to listen in, even if they can intercept or modify the messages between you and the bank (encryption). You can be sure you really are talking to the bank, and not to a fraudster (verification). And the bank can make statements that anyone who has their public key can ascertain is genuine, i.e. it really came from the bank (signing).

The last part is nice because the bank can sign a statement about your balance, give it to you, and you can forward it to your sleazy landlord who wants proof of your financial situation. The bank and the landlord never directly talk with each other, nevertheless the latter has full certainty that the statement was made by the bank, and that you didn't tamper with it.

So it's cool that we can securely communicate with our banks. We can do the same with websites: once we have the public key of e.g. Google, it's easy to setup an encrypted communication channel. Via the verification function of keypairs, it's also easy to prove we really are talking to that Google, and not to some kid who's trying to steal our password to post dog pictures in our cat groups.

How do we get Google's public key? — This is where things start going downhill.

In the bank example, we'd gotten the public key personally from the bank (written on its front wall). With Google, it'd be kind of difficult to travel to Mountain View just to get get their public key. And we can't just go and download the key from google.com, the whole point is that we're not sure that the google.com we're talking to is the real Google.

Are we completely out of luck? Can we communicate securely over the internet only if we manually exchange keys before, which we usually can't? It turns out we are only sort-of out of luck: we are stuck with certificates and the halfway-broken system of certificate authorities.

Certificates

A certificate contains several parts:

  • an identifier (a hash) that uniquely identifies a keypair
  • metadata that says who this keypair belongs to
  • signatures: statements signed by other keys that vouch that the keypair referenced here really belongs to the entity described in the metadata section

It's important to note that certificates don't need to be kept secret. The keypair identifier doesn't reveal the private key, so certificates can be shared freely. The corollary of this is that a certificate alone can't be used to verify you're talking to anyone in particular. To be used for authentification, it needs to be paired with the associated private key.

With that out of the way, let's look at why certificates are useful. Say someone gives you a certificate and proves they have the associated private key. You've never met this person. However, the certificate carries signatures from several keys that you know belong to close friends of yours. All of those signatures attest that this person is called "Hari Seldon". If you trust your friends, you can be pretty certain that the person is really called that way.

When you think about this, it's kind of neat. A stranger can authenticate to you (prove that they say who they are) just because someone you trust made a statement confirming the stranger's identity. That this statement is really coming from your trusted friend is ensured, because it's signed with their private key.

The same concept can be applied websites. As long as there's someone you trust and you have their public key, they can sign other people's certificates to affirm that identity to you. For example, they can sign a certificate for Google that says "This really is the real google.com". When you see that certificate and verify that the other party has the associated private key, you'll have good reason to believe that you really are talking to Google's google.com server, not some scam version by a North Korean hacker.

Certificate Authorities

So how do you find someone you can trust? And how does that person make sure that the certificate they are signing really belongs to Google? They face the same problems confirming that fact as you did! Does this even improve the situation in any way?

It does – let's take the questions in order. The reality on the internet is: it's not you trusting someone, it's your browser that does the trusting. Your browser includes public keys from so-called "certificate authorities" (CA's). You can find the list of CA's trusted by your own browser in its options, under Advanced / Security / Certificates / Authorities. If the browser sees certificates signed by any one of these keys, it believes them to be true. It trusts CA's not to sign any bogus certificates.

Why are these keys trustworthy? Because CA's are mostly operated by large companies that have strict policies in place to make sure they only sign stuff that's legit. How do they do that? After all, as an individual you'd have a pretty tough time verifying that the public key offered by google.com really belongs to Google. Don't CA's face the same problem?

Not really. There are billions of people accessing google.com. There are only about 200 CA's that are trusted by the common browsers. And Google needs a signed certificate by only one of them (one signature is enough to earn the browser's trust). So Google can afford to prove it's identity to a CA: by sending written letters, a team of lawyers, or whatever. Once Google gets a certificate for google.com signed by any reputable CA, it is recognized by pretty much every device in the world.

Similarly, I, as a private person, can get a certificate for greek0.net by proving my identity and my ownership of this domain to the CA. The identity part is usually done by submitting a scan of a driver's license or passport. Ownership of the domain can be shown by uploading a file supplied by the CA to the webserver. Once the CA confirms that the file is there, it knows I have control of that domain.

So instead of me having to prove my identity to every single user visiting this website, I can prove it once to a CA, and all browsers coming here will recognize this as good enough. This way, CA's make the problem of authentication of servers ("I'm the real google.com, not a cheap fake") tractable. It's a system that has made the large-scale deployment of secure internet traffic via HTTPS possible.

The half-broken part

Let's get back to the analogy of a stranger authenticating to you via a certificate signed by someone you know. What if the signature wasn't from a close friend of yours, but from a seedy guy you meet occasionally when going out? Would you still have full confidence in the certificate? Hopefully not.

What does this mean for the web?

Not all of the CA's included in the common web browsers are the equivalent of a trusted friend:

  • They may be in control of some government who wants a certificate for gmail.com, so it can read dissident's emails
  • An employee with access to the certificate authority key may create certificates for bank websites and sell them on the black market
  • The computer network where the CA keys are stored could have been hacked

I'm pretty sure all three of those have actually happened in the past. Given that a single forged certificate can be used to attack millions of users, CA's are juicy targets. As soon as forged certificates are detected in the wild, they tend to be blacklisted (blocked by browsers) very quickly, but there is still a window of vulnerability.

For this reason, the whole CA system has been questioned over the last few years, but replacing it does not seem feasible at the moment. There are techniques (such as public key pinning) to augment the CA-based authentication, but it takes time for them to be picked up by website owners.

While this is a problem, it mostly affects the largest websites (obtaining a forged certificate is difficult and costly). Together with browser vendors, they are developing new mitigation techniques against forged certificates. In the meantime, the rest of us is still pretty well served by the current CA system, even though it is not perfect.

Wrapup

So, this is it for an overview of the public key infrastructure that enables secure connections to internet sites, from the basics of public key cryptography to certificate authorities. If you want to dig deeper, I recommend starting with the Wikipedia articles I linked throughout the article. If you are interested in cryptography in general, I highly recommend Bruce Schneier's book Applied Cryptography. It's 20 years old now, and still enormously relevant today.

I hope this text helps a bit to clear up the confusion associated with public key cryptography and the secure web. If you liked it, or if you have any suggestions for improvement, please let me know in the comments!


dh_virtualenv and long package names (FileNotFound error)

Interesting tidbit about Linux:

A maximum line length of 127 characters is allowed for the first line in a #! executable shell script.

from man execve

Should be enough, right?

Wrong.

Well, not if you are using dh_virtualenv with long package names, anyway:

Installing pip...
  Error [Errno 2] No such file or directory while executing command /tmp/lo...me/bin/easy_install /usr/share/python-virtualenv/pip-1.1.tar.gz
...Installing pip...done.
Traceback (most recent call last):
  File "/usr/bin/virtualenv", line 3, in <module>
virtualenv.main()
  File "/usr/lib/python2.7/dist-packages/virtualenv.py", line 938, in main
never_download=options.never_download)
  File "/usr/lib/python2.7/dist-packages/virtualenv.py", line 1054, in create_environment
install_pip(py_executable, search_dirs=search_dirs, never_download=never_download)
  File "/usr/lib/python2.7/dist-packages/virtualenv.py", line 643, in install_pip
filter_stdout=_filter_setup)
  File "/usr/lib/python2.7/dist-packages/virtualenv.py", line 976, in call_subprocess
cwd=cwd, env=env)
  File "/usr/lib/python2.7/subprocess.py", line 679, in __init__
errread, errwrite)
  File "/usr/lib/python2.7/subprocess.py", line 1249, in _execute_child
raise child_exception
OSError: [Errno 2] No such file or directory
Traceback (most recent call last):
  File "/usr/bin/dh_virtualenv", line 106, in <module>
sys.exit(main() or 0)
  File "/usr/bin/dh_virtualenv", line 83, in main
deploy.create_virtualenv()
  File "/usr/lib/python2.7/dist-packages/dh_virtualenv/deployment.py", line 112, in create_virtualenv
subprocess.check_call(virtualenv)
  File "/usr/lib/python2.7/subprocess.py", line 511, in check_call
raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['virtualenv', '--system-site-packages', '--setuptools', 'debian/long-package-name/usr/share/python/long-package-name']' returned non-zero exit status 1
make: *** [binary-arch] Error 1
dpkg-buildpackage: error: fakeroot debian/rules binary gave error exit status 2

dh_virtualenv is used to create Debian packages that include Python virtualenvs. It is one of the better ways of packaging Python software, especially if there are Python dependencies that are not available in Debian or Ubuntu. When building a .deb package, it creates a virtualenv in a location such as:

/<build-directory>/debian/<packagename>/usr/share/python/<packagename>

This virtualenv has several tools under its bin/ directory, and they all have the absolute path of the virtualenv's Python interpreter hard-coded in their #! shebang line:

#!/<build-directory>/debian/<packagename>/usr/share/python/<packagename>/bin/python

Given that <build-directory> often contains the package name as well, it's easy to overflow the 128 byte limit of the #! shebang line. In my case, with a ~30 character package name, the path length grew to 160 characters!

Consequently, the kernel couldn't find the Python executable anymore, and running any of the tools from the bin/ directory gave an ENOENT (file not found) error. This is what happened when virtualenv tried to install pip during the initial setup. The root cause of this error is not immediately obvious, to say the least.

To check whether this affects you, check the line length of any script with wc:

head -n 1 /path/to/virtualenv/bin/easy_install | wc -c

If that's larger than 128, it's probably the cause of the problem.

The fix is to change the package name and/or the build location to something shorter. The alternative would be to patch the Linux kernel, which – depending on your preferences – sounds either fun or really unpleasant. Suit yourself!


Behold the power of perf-tools

perf-tools is a collection of scripts for system-wide tracing on Linux. It's really, really cool. It's what the perf command should have included from day one, but didn't.

It is packaged in Debian and Ubuntu, but those versions miss some key features. As perf-tools consists of shell scripts (no compilation necessary), I recommend using the GitHub version directly:

git clone https://github.com/brendangregg/perf-tools.git

Two tools that are included are execsnoop and opensnoop, which trace new program executions and open() calls across the whole system.

$ sudo ./execsnoop
TIME        PID   PPID ARGS
21:12:56  22898  15674 ls --color=auto -la
21:12:56  22899  15674 git rev-parse --is-inside-work-tree
21:12:56  22900  15674 git rev-parse --git-dir
...

$ sudo ./opensnoop
Tracing open()s. Ctrl-C to end.
COMM             PID      FD FILE
opensnoop        22924   0x3 /etc/ld.so.cache
gawk             22924   0x3 /usr/lib/locale/locale-archive
top              15555   0x8 /proc/1/stat
...

Maybe the most interesting tool is uprobe. It's magic: it traces function calls in arbitrary user-space programs. With debugging symbols available, it can trace practically every function in a program. Without them, it can trace exported functions or arbitrary code locations (specified by raw address). It can also trace library code, e.g. libc). Having these possibilities on a production system without any prior setup is staggering.

$ sudo user/uprobe -F -l /tmp/a.out | grep quicksort
_Z9quicksortN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEES5_
$ sudo user/uprobe -F p:/tmp/a.out:_Z9quicksortN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEES5_
Tracing uprobe _Z9quicksort[snip] (p:_Z9quicksort[snip] /tmp/a.out:0x8ba). Ctrl-C to end.
   a.out-23171 [000] d... 1860355.891238: _Z9quicksort[snip]: (0x80488ba)
   a.out-23171 [000] d... 1860355.891353: _Z9quicksort[snip]: (0x80488ba)
   ...

(To demangle the C++ function names, use the c++filt tool.)

perf-tools really shows the power of the Linux perf/ftrace infrastructure, and make it usable for the broad masses. There are several other tools that analyze latency and cache hit rates, trace kernel functions, and much more. To finally have such functionality in Linux is fabulous!

published tagged linux

Running strace for multiple processes

Just a quick note about strace, the ancient Linux system-call tracing tool.

It can trace multiple processes at once: simply start it with multiple -p arguments (the numbers give the processes' PIDs):

sudo strace -p 2916 -p 2929 -p 2930 -p 2931 -p 2932 -o /tmp/strace.log

This is great for tracing daemons which use separate worker processes, for example Apache with mpm-prefork.

published tagged linux

Plotting maps with Folium

Data visualization in Python is a well solved problem by now. Matplotlib and it's prettier cousin Seaborn are widely used to generate static graphs. Bokeh generates HTML files with interactive, JavaScript-based graphs. It's a great way of sharing data with other people who don't have a Python development environment ready. Several other libraries exist for more specialized purposes.

What has been missing for a long time was good map libraries. Plotting capabilities were fine, but basemap support of the existing libraries was very limited. For example, the popular Matplotlib-basemap has great plot types (contour maps, heatmaps, ...) but can't show any high-resolution maps: it only has country/state shapes or whole-world images. Consequently, it's useless for drawing city or street level maps, unless you want to set up your own tile server (you don't).

Along comes Folium, a library that generates interactive maps in HTML format based on Leaflet.js. It supports, among others, OpenStreetMap and MapBox base layers which look great and provide enough details for large-scale maps.

Here is an example that shows some GPS data I cleaned up with a Kalman filter:

def plot(points, center):
    map_osm = folium.Map(location=center, zoom_start=16, max_zoom=23)
    map_osm.line(locations=points)
    map_osm.create_map(path='folium-example.html')

Here's what it looks like. I find it pretty neat, especially given that it took only 3 lines of code to create: