Thursday, June 27, 2013

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.

Sunday, June 23, 2013

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.

Saturday, September 29, 2012

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

Friday, September 14, 2012

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.

Saturday, July 21, 2012

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.

Friday, March 23, 2012

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

Sunday, February 19, 2012

LLVM pass on Windows: integrating with opt

I've been using LLVM for a few weeks now and my primary interaction with it has been writing custom passes. LLVM has a very nice system for handling user defined passes: you create an independent plug-in and load it dynamically using the opt tool. A full explanation can be found in the LLVM pass documentation.

Unfortunately, plug-ins are dynamically linked in LLVM which excludes this approach on Windows (without relying on Cygwin). For all my searching I was not able to find instructions on integrating a pass directly with the opt tool but I needed to support custom passes on Windows without using Cygwin. Mostly as a note for myself, I am listing here the steps I used to create my own custom pass as part of the opt tool; hopefully they will be useful for others as well.

I've followed as best I could the format used by existing infrastructure within LLVM. This does not mean that I have not missed something critical or what I have provided adheres to LLVM policy and/or standards.

N.B. These examples assume you are:
  •  already familiar with writing a custom pass as described by the LLVM documentation
  •  capable of understanding Makefiles and how to modify them to suit your needs
  •  using llvm-3.0 (that is the version used in these examples)
These examples will build a pass named mypass which will simply print out all function names. This pass will be part of the Custom library (also created here).

The first step is to create a new directory named Custom under llvm/lib/Transforms. This is where all passes for the new library will live. Create a very simple function pass and place it in this new directory - I used the following (MyPass.cpp)
#define DEBUG_TYPE "mypass"
#include "llvm/Function.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Custom.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;

namespace {
  struct MyPass : public FunctionPass {
    static char ID;
    MyPass() : FunctionPass(ID) {
      initializeMyPassPass(*PassRegistry::getPassRegistry());
    }

    /*
     * Just print the function name 
     */
    bool runOnFunction(Function &F) {
      bool Changed = false;
      errs().write_escaped(F.getName()) << "\n";
      return Changed;
    }
  };
}

char MyPass::ID = 0;
INITIALIZE_PASS(MyPass, "mypass", "Print all function names",
                false, false)

FunctionPass *llvm::createMyPassPass() {
  return new MyPass();
}
To load this, and multiple other custom passes, it is necessary to create an initialization routine that iterates over all passes in the library. In this example the only call in that routine is the call to the pass above. Still in the Custom directory, create the following as Custom.cpp:
#include "llvm/InitializePasses.h"
#include "llvm-c/Initialization.h"

using namespace llvm;

/// initializeCustom - Initialize all passes in the Custom library
void llvm::initializeCustom(PassRegistry &Registry) {
  initializeMyPassPass(Registry);
}

/// LLVMInitializeCustom - C binding for initializeCustom.
void LLVMInitializeCustom(LLVMPassRegistryRef R) {
  initializeCustom(*unwrap(R));
}
You will also need to support either build system with a Makefile and CMakeLists.txt.
LEVEL = ../../..
LIBRARYNAME = LLVMCustom
BUILD_ARCHIVE = 1

include $(LEVEL)/Makefile.common

add_llvm_library(LLVMCustom
  MyPass.cpp
  Custom.cpp
  )
That is the entirety of writing a new pass library for LLVM. The remainder of the work is integrating that new code into the larger system.

First, you need to define a way for LLVM to create an instance of your pass. Save the following as Custom.h in llvm/include/llvm/Transforms/
#ifndef LLVM_CUSTOM_H
#define LLVM_CUSTOM_H

namespace llvm {

FunctionPass *createMyPassPass();

}

#endif
Then you need to provide the prototypes for the two initialization routines. Add the following two lines to llvm/include/llvm/InitializePasses.h - make sure you do so inside the llvm namespace.
void initializeCustom(PassRegistry&);
void initializeMyPassPass(PassRegistry&);
Next, you need to set any passes to be linked by adding entries into llvm/include/llvm/LinkAllPasses.h
#include "llvm/Transforms/Custom.h"

// This part must reside in the constructor of struct ForcePassLinking
(void) llvm::createMyPassPass();
Updates are required to all relevant makefiles in the source tree. You will need to adjust the following to account for the additions discussed above:
  • llvm/lib/Transforms/Makefile
  • llvm/lib/Transforms/CMakeLists.txt
  • llvm/tools/opt/Makefile (add link dependency for 'custom')
  • llvm/tools/opt/CMakeLists.txt (add link dependency for 'custom')
  • llvm/tools/bugpoint/Makefile (add link dependency for 'custom')
  • llvm/tools/bugpoint/CMakeLists.txt (add link dependency for 'custom')
Finally, add the code to load the custom library in opt. Add the initialization call in the appropriate place in opt.cpp
initializeCustom(Registry);
The new pass should now be visible (on all platforms) without having to load a library with opt.
    -mergereturn                               - Unify function exit nodes
    -module-debuginfo                          - Decodes module-level debug info
    -mypass                                    - Print all function names
    -no-aa                                     - No Alias Analysis (always returns 'may' alias)
    -no-path-profile                           - No Path Profile Information