10 points: 10 plots

As an exercise in expanding my ability to display data I challenged myself to present 10 data points in 10 ways that were as distinct as possible. The idea was simple: use 10 random data points; minimize the axis and other ancillary information so as to focus on the data as much as possible; and try to minimize the overlap between each of the approaches.

Initially, I expected this would be a trivial task - something that would take a single sitting and a little bit of thought. A few attempts later and I kept circling back on a few common ideas while considering just how many approaches I'd not considered. What exists below is a collection of the results of that exercise with explanation if necessary.

1 - Standard Cartesian (scatterplot)

2 - Derivative Cartesian: uses labels instead of points to eliminate the need for tick marks on the x-axis.

3 - Impulses. Mixing the number and characters on the x-axis tick marks is questionable and could just as well have been labels at the top of each impulse

4 - Sorted derivative Cartesian

5 - Boxplot

6 - Barplot

7 - Radial. Points are interpreted as radians and placed starting from 0 radians

8 - Heatmap

9 - Cumulative Sum

10 - Financial/Intensity: Positive values are blue, negative are red. Absolute values define the radius of the circle used.

I considered others such as LOESS fit but they either needed the points to accompany them (to show what was being fitted) which made them too close to the Cartesian plot, or they were too complex for just 10 points.

It was interesting to see how difficult it turned out to be to stretch 10 points into 10 distinct presentation approaches.

Walk this way

I recently found a handy mechanism for walking a directory tree in Linux. In
general, the way I used to do this was to use facilities found in dirent.h and
write my own recursive directory walker. Something similar to:

#include <stdio.h>
#include <string.h>
#include <dirent.h>

void reclist (const char* dirname) {

    DIR* dir = opendir (dirname);
    struct dirent* entry = 0;
    char name[1024] = {0};

    if (! dir) { return; }

    entry = readdir (dir);
    while (entry) {
        if (strncmp (entry->d_name, ".", 1)) {
            switch (entry->d_type) {
                case DT_REG:
                    printf ("%s\n", entry->d_name);
                    break;
                case DT_DIR:
                    snprintf (name, 1024, "%s/%s", dirname, entry->d_name);
                    reclist (name);
                    break;
            }
        }
        entry = readdir (dir);
    }
    closedir (dir);
}

int main(int argc, char** argv) {
    const char * dir = ".";
    if (argc == 2) { dir = argv[1]; }
    reclist (dir);
    return 0;
}

While that does work, it is rather verbose (especially once you get used to
environments like Ruby and Python). It turns out that ftw.h provides a more
concise way to do the above while managing all the little details like
avoiding '.' and '..' and managing the current path string. Here is what that
looks like to do the same as the above:

#include <stdio.h>
#include <ftw.h>

int handle_entry (const char *entry, const struct stat *sb, int type) {
    if (type == FTW_F) {
        printf("%s\n", entry);
    }
    return 0;
}

int main() {
    ftw(".", handle_entry, 10);
    return 0;
}

I also like the fact that a callback is used to operate on each of the files
found. It makes managing changes much easier as the tree walking is separated
from the code that handles the logic associated with inspecting the files.

That's the key

A while back I cam across a post on Stephen Wolfram's blog where he presented the personal analytics of his life. As part of this post, there is a plot showing the keystroke activity of his life over the last 10 years. I want to ignore the resolve needed to conduct such an experiment for a moment and consider how he might have set something like that up.

[Update: see the corollary to this post - generating keyboard events - here]

I'm interested in data. I have a few logs of things I do on a daily basis but they are all collected proactively - I write entries into these logs in order to keep them current. I want to set up something similar to this key logger to automate this process for me. I'll mostly ignore that this is a potential security risk in that I will be capturing all keystrokes on the computer - including username and password information. To partially mitigate this I wont store the key information, I'll only keep the time the event occurred. This limits the amount of information in my database - I wont be able to see how my distribution of characters matches that of commonly used data, for instance - but it saves me from having to worry about how and where I store this information. Stephen Wolfram's post includes details about the actual keys so if my data starts to look interesting perhaps I'll transition to keeping that information as well.

I run Linux so I figured this would be rather straightforward: somehow hook into the X windowing subsystem and register for all keyboard events. Unfortunately, such an approach is not directly possible using Xlib (depending on which stackoverflow answer you read, it may not be possible at all). It turns out that it is rather difficult to ask X to just 'give me everything.' Things, as it were, are destined for a particular location (read: window) and asking for other windows' events doesn't make much sense in the general case. I had hoped there would be something akin to a callback list for registered components that I would be able to insert an entry into. Xlib is not designed that way (at least not in any documentation I can find).

To avoid having to hack the X window event delivery system I started to look at how these events are realized by X itself. In the guts of the device initialization configuration there is something similar to the following:

Section "InputClass"
    Identifier "evdev keyboard catchall"
    MatchIsKeyboard "on"
    MatchDevicePath "/dev/input/event*"
    Driver "evdev"
EndSection

which is using one of the /dev/input/event* devices. These are character devices set up by evdev to handle generic input events from a variety of sources: joysticks, mice, keyboards, and so on. One nice thing about these devices is they can be opened and read from as if they were regular files. So, if I can figure out which of the /dev/input/event* devices corresponds to the keyboard I should have access to the events that X is handing off to the child windows.

It turns out that there are two directories that exist to facilitate this type of search: /dev/input/by-id/ and /dev/input/by-path/. Searching either of the two of them for something like *-kbd you can find the exact device linked to a keyboard (if you have multiple keyboards attached you will need to further disambiguate). For example, in my /dev/input/by-path/ there are the following:

pci-0000:00:04.0-event-mouse -> ../event4
pci-0000:00:06.0-usb-0:1:1.0-event-mouse -> ../event3
pci-0000:00:06.0-usb-0:1:1.0-mouse -> ../js0
platform-i8042-serio-0-event-kbd -> ../event2
platform-i8042-serio-1-event-mouse -> ../event5
platform-i8042-serio-1-mouse -> ../mouse1

According to this (and some mappings provided in /usr/include/linux/input.h) I can now collect all keystrokes generated by my machine from /dev/input/event2 without having to devise a way to convince X to hand them over.

GCC Bug 53812

I was [un]lucky enough to stumble upon a gcc bug recently. I was working on an interpreter for a simple calculator language and in building the jump table for the instructions I was using a construct similar to:

---

struct Processor {
    bool initialized_;
    std::map< std::string, void* > jump_table;
    Processor () : initialized_(false) {}
    long execute (Program& prog) {
        if (! initialized_) {

            jump_table["+"] = &&block_add;
            jump_table["-"] = &&block_sub;
            jump_table["*"] = &&block_mul;
            jump_table["/"] = &&block_div;
            jump_table[";"] = &&block_end;
            initialized_ = true;
            return execute (prog);
        }
block_add:
        prog.value (prog.arg (0) + prog.arg (1));
        goto *jump_table[prog.next_op ()];
block_sub:
        prog.value (prog.arg (0) - prog.arg (1));
        goto *jump_table[prog.next_op ()];
block_div:
        prog.value (prog.arg (0) / prog.arg (1));
        goto *jump_table[prog.next_op ()];
block_mul:
        prog.value (prog.arg (0) * prog.arg (1));
        goto *jump_table[prog.next_op ()];
block_end:
        return prog.result ();
    }
};

---

Trying to compile that with g++ 4.6.3 leads to the following error:

---

calc.cc: In member function 'long int Processor::execute(Program&)';
calc.cc:75:1: internal compiler error: in lower_stmt, at gimple-low.c:432

---

This bug also manifests itself in 4.7.0 and 4.7.1 but in a another location (verify_gimple_stmt). The oldest copy of gcc I have is 4.3.2 and the bug is not evident in that version.

Granted I was using non-standard constructs in my code but it still felt pretty cool to uncover a bug in such a well-known piece of software.

You can find the bug report (and current status) here

All your heap are belong to us

This is a port and slight expansion of the ideas presented here.

The premise of that article is that underneath the interface provided by an application the handling of sensitive information is done in memory provided on the heap (via malloc/new). With that in mind, capturing the memory before it was released by the application would potentially expose hidden details. The system used in that article was OSX and the applications were Twitter-based but I decided to port to Linux and look at ssh.

First, the port:

---

#include <stdio.h>
#define __USE_GNU
#include <dlfcn.h>

void (*real_free)(void *);

void free (void * mem) {
    char buff[256] = {0}, * p = mem;
    int i = 0;

    if (! mem) { return; }

    while (*p) {
        buff[i++] = *p++;
        if (i > 254)
            break;
    }

    buff[i] = 0;
    fprintf (stderr, "[free] %s\n", buff);

    real_free = dlsym (RTLD_NEXT, "free");
    real_free (mem);
}

---

Nothing new here, just a version of free that will be interposed by this library. Compiling that and running the following:

LD_PRELOAD=/tmp/heapgrab.so ssh ezpz@sandbox 2>heapgrab.log

Produces a log with a substantial amount of information in it. However, the password is not included anywhere. It seems that ssh sanitizes buffers before freeing them - the next logical step is to provide a version of memset that does the same thing to try and capture where the memory is sanitized:

---

void* (*real_memset)(void*, int, size_t);

void * memset (void * mem, int c, size_t size) {
    char buff[256] = {0}, * p = mem;
    int i = 0;

    if (! mem ) { return; }

    while (*p) {
        buff[i++] = *p++;
        if (i > (size - 1) || i > 254)
            break;
    }

    buff[i] = 0;
    fprintf (stderr, "[memset] %s\n", buff);

    real_memset = dlsym(RTLD_NEXT, "memset");
    return real_memset (mem, c, size);
}

---

With that, our log now contains the following:

[free] publickey,password
[free] keyboard-interactive
[free] publickey
[memset] ezpz_awesome_password
[memset] xxxxx
[memset] ezpz_awesome_password

I've played with interpositioning a bit over the past few years but I never considered using it in exactly this way. Thanks to Joe Damato for the initial idea and original OSX code.

gcc constructor attribute

It is sometimes helpful to provide a way to 'initialize the system' when you are writing a library. Many times, this manifests itself in the form of a lib_init() call. Similarly, any convenience cleanup would be provided via lib_close(). For a concrete example look at ncurses which provides initscr() and endwin() for this use.

In the case when these routines are required (as they are in ncurses) there is an easier way to provide the proper setup without placing the onus to call these methods on the developer. GCC provides __attribute__((constructor)) and __attribute__((destructor)) which allow for calling methods when a library is loaded and unloaded respectively. These calls happen outside the scope of main. For example,

#include <stdio.h>

__attribute__((constructor)) void init() {
    fprintf (stderr, "constructor\n");
}

int main () {
    return fprintf(stderr, "main\n");
}

This program will output the following:

constructor
main

In the case of a library such as ncurses this is a perfect place to invoke the necessary initialization and cleanup routines. A simplified example library:

__attribute__((constructor))
static void setup() { do_some ("setup"); }

__attribute__((destructor))
static void breakdown() { do_some ("breakdown"); }

void mylib_method (const char * thing) { do_some (thing); }

Now, if a developer links against your library setup() is called when your library is loaded and breakdown() is called when it is unloaded. A nicety of this approach is that it provides the same functionality if the library is pulled in when the executable is loaded or at some later point (via dlopen/dlsym, for example) thus always ensuring a consistent environment for your code.

This is obviously not a fit for all libraries. Only those with setup and cleanup that can be self-contained and are always required would benefit from such an approach. In those cases, however, I prefer this method to the alternative of burdening the developer with requirements of my library.

Fisheye

I've recently been working on a design of an interface and have been doing some prototyping in d3 to support that effort. One of the effects we are considering is a 'fisheye' swell when mousing over a set of options.

I put together a small demo of what this would look like in practice. It is a work in progress for anything that may become useful but I like the idea so far.

You can find the code on github: fisheye