Exponential backup rotation, part 2

27.06.2015 17:45

I've been writing previously about Chris Forno's log2rotate algorithm. After using my Python implementation for a while, one problem became apparent: the algorithm is quite bad at handling missing backups.

Missing backups happen in practice. For instance, a host might be down or without network connectivity at the time the daily backup Cron job is supposed to run. So every once in a while, a daily backup might be skipped. Unfortunately, log2rotate makes a strong assumption that new backups always come in a regular time series. The worst case happens if a backup that is selected by the algorithm for long-term storage is missing. This can double the age of restored files after a data loss.

Chris' original implementation does a simple check: if an expected backup is not there, it simply throws a fatal error. You can ignore the error with the --unsafe switch, but then it makes no promises as to what the resulting backup series will be.

My initial Python port of the algorithm basically mimicked this behavior (although with a bit smarter check that avoided some false alarms). Now, I've added another step in the algorithm that selects which backups to keep. I still calculate the pattern of retained backups using Chris' algorithm. However after that, I do a search for a backup that actually exists, within some limited time interval.

Most recent backup age versus time of data loss.

The graph above demonstrates this improvement. It shows the age of the most recent backup in a case that data loss occurred at some past point in time. On the horizontal axis, present day is day 100 and day 0 is the day the oldest backup was made.

The black dashed line shows the ideal case - using log2rotate algorithm and no missing backups. For example, if we wanted to restore a file that we know was lost on day 60 (40 days ago), the age of the most recent retained backup that still contains the file (created on day 32) is 28 days.

The blue line shows the worst case for a single missing backup using the original algorithm, but overriding errors with --unsafe. For restoring a file that was lost on day 60, the worst case is if backup on day 32 is missing. In that case, the next most recent backup is from day 0, which is 60 days old.

Finally, the red line shows the situation with the fuzzy matching algorithm. In this case, if backup on day 32 is missing, the algorithm retains the backup on day 31. So when restoring data lost on day 60, the most recent backup is only one day older compared to when no backups are missing.


The updated code is on GitHub. Documentation is somewhat lacking at the moment, but the algorithm is pretty well tested (backups are always a bit of a sensitive thing). If I see some interest, I might clean it up and push it to PyPi.

Posted by Tomaž | Categories: Code | Comments »

Identifying USB serial devices

19.06.2015 20:04

Many devices use a simulated serial line to talk over the USB port. This is by far the simplest way of adding USB connectivity to an embedded system - either by adding a dedicated RS232-to-USB hardware converter or by implementing USB CDC ACM protocol on a microcontroller with an USB peripheral. For instance, Arduino boards use one of these approaches depending on the model.

On Linux systems, such devices typically get device files like /dev/ttyUSBx or /dev/ttyACMx associated with them. For example, if you want to talk to a device using pySerial, you have to provide the path to such a device file to the library.

A common problem is how to match such a device file to a device that has been plugged into an USB port. My laptop for instance, already has /dev/ttyACM0 through /dev/ttyACM2 on boot with nothing connected externally. USB devices conveniently identify themselves using bus addresses, product and vendor identifiers, serial number and so on. However these back end identifiers are not accessible in any way through /dev/tty* device files, which are merely front ends to the Linux kernel terminal subsystem.

Surprisingly, this appears to be quite a complicated task to do programmatically. For instance in Python, PyUSB is of no assistance in this matter as far as I can see. Browsing the web you can find plenty of recipes that all appear overly convoluted (running a regexp over dmesg wins in this respect). You can crawl through the sysfs, but this seems like a brittle solution.

The best (as in, simplest to implement and reasonably future-proof) solution I found so far is to ask udev. udev takes care of various tasks related to hot-plugging devices and hence knows about many aspects of how a physical device is registered in the kernel. It also seems to be pretty universal these days, at least on Linux. So I guess it's not a terribly bad dependency to add. pyudev (apt-get install python-pyudev on Debian) provides a nice Python interface. udevadm gets you much of the same information from a command line.

For instance, to list all terminal devices connected over the USB bus and pretty print their properties:

import pyudev
import pprint

context = pyudev.Context()

for device in context.list_devices(subsystem='tty', ID_BUS='usb'):
	pprint.pprint(dict(device))

The device file path is in the DEVNAME property, as you can see below. Other identificators from the USB bus are available in other properties. You can use them to find the specific device you need (list_devices() arguments work as a filter):

{u'DEVLINKS': u'/dev/serial/by-id/usb-Olimex_Olimex_OpenOCD_JTAG-if01-port0 /dev/serial/by-path/pci-0000:00:1d.0-usb-0:1.1:1.1-port0',
 u'DEVNAME': u'/dev/ttyUSB1',
 u'DEVPATH': u'/devices/pci0000:00/0000:00:1d.0/usb4/4-1/4-1.1/4-1.1:1.1/ttyUSB1/tty/ttyUSB1',
 u'ID_BUS': u'usb',
 u'ID_MM_CANDIDATE': u'1',
 u'ID_MODEL': u'Olimex_OpenOCD_JTAG',
 u'ID_MODEL_ENC': u'Olimex\\x20OpenOCD\\x20JTAG',
 u'ID_MODEL_FROM_DATABASE': u'OpenOCD JTAG',
 u'ID_MODEL_ID': u'0003',
 u'ID_PATH': u'pci-0000:00:1d.0-usb-0:1.1:1.1',
 u'ID_PATH_TAG': u'pci-0000_00_1d_0-usb-0_1_1_1_1',
 u'ID_REVISION': u'0500',
 u'ID_SERIAL': u'Olimex_Olimex_OpenOCD_JTAG',
 u'ID_TYPE': u'generic',
 u'ID_USB_DRIVER': u'ftdi_sio',
 u'ID_USB_INTERFACES': u':ffffff:',
 u'ID_USB_INTERFACE_NUM': u'01',
 u'ID_VENDOR': u'Olimex',
 u'ID_VENDOR_ENC': u'Olimex',
 u'ID_VENDOR_FROM_DATABASE': u'Olimex Ltd.',
 u'ID_VENDOR_ID': u'15ba',
 u'MAJOR': u'188',
 u'MINOR': u'1',
 u'SUBSYSTEM': u'tty',
 u'UDEV_LOG': u'3',
 u'USEC_INITIALIZED': u'220805300741'}
{u'DEVLINKS': u'/dev/serial/by-id/usb-STMicroelectronics_VESNA_SpectrumWars_radio_32A155593935-if00 /dev/serial/by-path/pci-0000:00:1d.0-usb-0:1.2:1.0',
 u'DEVNAME': u'/dev/ttyACM3',
 u'DEVPATH': u'/devices/pci0000:00/0000:00:1d.0/usb4/4-1/4-1.2/4-1.2:1.0/tty/ttyACM3',
 u'ID_BUS': u'usb',
 u'ID_MM_CANDIDATE': u'1',
 u'ID_MODEL': u'VESNA_SpectrumWars_radio',
 u'ID_MODEL_ENC': u'VESNA\\x20SpectrumWars\\x20radio',
 u'ID_MODEL_ID': u'5740',
 u'ID_PATH': u'pci-0000:00:1d.0-usb-0:1.2:1.0',
 u'ID_PATH_TAG': u'pci-0000_00_1d_0-usb-0_1_2_1_0',
 u'ID_REVISION': u'0200',
 u'ID_SERIAL': u'STMicroelectronics_VESNA_SpectrumWars_radio_32A155593935',
 u'ID_SERIAL_SHORT': u'32A155593935',
 u'ID_TYPE': u'generic',
 u'ID_USB_DRIVER': u'cdc_acm',
 u'ID_USB_INTERFACES': u':020201:0a0000:',
 u'ID_USB_INTERFACE_NUM': u'00',
 u'ID_VENDOR': u'STMicroelectronics',
 u'ID_VENDOR_ENC': u'STMicroelectronics',
 u'ID_VENDOR_FROM_DATABASE': u'SGS Thomson Microelectronics',
 u'ID_VENDOR_ID': u'0483',
 u'MAJOR': u'166',
 u'MINOR': u'3',
 u'SUBSYSTEM': u'tty',
 u'UDEV_LOG': u'3',
 u'USEC_INITIALIZED': u'245185375947'}

If you intend to use a device on a certain host in a more permanent fashion, a better solution is to write a custom udev rule for it. A custom rule also allows you to set a custom name, permissions and other nice things. But the above seems to work quite nicely for software that requires a minimal amount of setup.

Posted by Tomaž | Categories: Code | Comments »

Weather radar image artifacts

16.06.2015 21:49

The Slovenian environment agency (ARSO) operates a 5 GHz Doppler weather radar on a hill in the eastern part of the country (Lisca). They publish a map with rate of rainfall estimate based on radar returns each 10 minutes.

Gašper of the opendata.si group has been archiving these rainfall maps for several years now as part of the Slovenian weather API project. A few days ago I've been playing with the part of this archive that I happened to have on my disk. I've noticed some interesting properties of the radar image that show up when you look at statistics generated from many individual images.

This is a sum of approximately 17676 individual rainfall maps, taken between December 2012 and April 2013:

Sum of 17676 weather radar images from ARSO.

Technically what this image shows is how often each pixel indicated non-zero rainfall during this span of time. In other words, the rainiest parts, shown in red, had rain around 18% of the time according to the radar. I ignored the information about the rate of rainfall.

More interesting is how some artifacts become visible:

  • There is a blind spot around the actual location of the radar. The radar doesn't scan above a certain elevation angle and is blind for weather directly above it.

  • There are triangular shadows centered on the radar location. These are probably due to physical obstructions of the radar beam by terrain. I've also heard that some of these radars automatically decrease sensitivity in directions where interference is detected (weather radars share the 5 GHz band with wireless LAN). So it is also possible that those directions have higher noise levels.

  • Concentric bands are clearly visible. The image is probably composed of several 360° sweeps at different elevation angles of the antenna. Although it is curious that their spacing decreases with distance. They might also be result of some processing algorithm that adjusts for the distance in discrete steps.

  • It's obvious that sensitivity is falling with distance. Some parts of the map in the north-western corner never show any rain.

  • Some moiré-like patterns are visible in the darker parts of the image. They are probably the result of interpolation. The map has rectangular pixels aligned with latitude and longitude while the radar produces an image in polar coordinates.

I should mention that ARSO's weather radar system got upgraded in 2014 with a second radar. Newer rainfall maps are calculated from combined data from both radars. They likely have much fewer artifacts. Unfortunately, the format of the images published on the web changed slightly several times during that year, which makes them a bit less convenient to process and compare.

Posted by Tomaž | Categories: Life | Comments »

OpenCT on Debian Jessie

03.06.2015 17:12

I use a Schlumberger Cryptoflex (e-Gate) USB key to store some client-side SSL certificates. This is an obsolete device that has been increasingly painful to keep working with each new Debian release. I was especially worried when upgrading my desktop to Debian Jessie since the openct package was removed in this release cycle.

The old openct binary package from Wheezy is still installable in Jessie. In fact, on my system it was left installed (but marked as obsolete) by the upgrade process. The problem was that the USB key was very unreliable. In most cases, it errored out with some random-looking error:

$ pkcs15-tool -D
Using reader with a card: Axalto/Schlumberger/Gemalo egate token 00 00
Failed to connect to card: Generic reader error
$ pkcs15-tool -D
Using reader with a card: Axalto/Schlumberger/Gemalo egate token 00 00
Failed to connect to card: Unresponsive card (correctly inserted?) 

But on a few occasions it would actually work correctly:

$ pkcs15-tool -D
Using reader with a card: Axalto/Schlumberger/Gemalo egate token 00 00
PKCS#15 Card [OpenSC Card]:
	Version        : 0
	Serial number  : ...

After much digging through the internals of the smart card framework, I found out that the e-Gate is only supported by the pcscd daemon through the openct driver (which is just one of the many drivers you can install in Debian). OpenCT starts its own daemon per each connected USB key called ifdhandler. This daemon communicates over a socket with the rest of the framework and must run as long as the USB key is inserted. The main problem on Jessie is that this daemon gets killed at some random time by the new systemd-udevd. Somewhere along the pipeline, something reacts badly to the fact that the ifdhandler disappears, hence the random error messages.

A simple workaround is simply to start the daemon by hand after inserting the USB key:

$ sudo /usr/sbin/ifdhandler -F -H -dddddd -p egate usb /dev/bus/usb/002/104

A better solution is to fix the udev configuration installed by the openct package, so that the daemon doesn't get killed. Fortunately, the solution to this was already found by Mike Kazantsev, who has a a nice write-up on this topic. Of course, I only found his blog post after spending several hours finding the root of the problem.

I've prepared an updated set of openct packages that can be installed on Jessie and have this problem fixed, at least for my specific USB key model. I didn't fix several other packaging problems reported by lintian. The binaries for amd64 can be found here. The updated source is also in a git repository (use git-buildpackage):

$ git clone http://www.tablix.org/~avian/git/openct.git

Other smart card-related packages work for me as-shipped in Jessie (e.g. opensc 0.14.0-2 and pcscd 1.8.13-1). Also note that my new packages depend on systemd. It is possible that the old Wheezy openct package still works correctly if you prevent the upgrade from migrating your init to systemd.

Other than that, my old instructions on how to set things up on Wheezy still work. One peculiarity I noticed though is that you need to insert the USB key before starting Firefox/Iceweasel. Otherwise the browser will not pick up any client certificate from the key.

Posted by Tomaž | Categories: Code | Comments »