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

Wednesday, January 25, 2012

Return on Investment

About a year ago, a friend and I were discussing the evolution of learning new tools while working under time constraints. He claimed that, regardless of the pressure, it is almost always better to sacrifice the upfront time in learning a new tool than to stay in your comfort zone to construct the illusion of progress. By illusion he simply meant that early stage progress is shadowed by the long-term effect of having to maintain and update a homegrown solution.

He used the following illustration to convey his point:



The effect is that if you choose to develop your own tools you satisfy the immediate gratification of results but the final solution is more likely to end up as a house of cards.

I had forgotten about this conversation until recently. The program I am currently working on had me in line to provide relevant results in a shortened amount of time. I am working with the llvm compiler infrastructure and it's unique assembly language. Part of what I needed to do is understand, at a high level, the contents of an llvm assembly file. My natural reaction to this was to implement some minimal parser in Ruby to get to a working set of results quickly. Things went well until I wanted to make a decent tool for broader use within the team: I was starting to spend more time on developing the Ruby code than making headway on my tasks. Not only did I dig myself a grave in that respect but since I was quick to satisyfy the initial demand for results I set an expectation that the work was less complicated than it truly is (and will continue to be). I was building a house of cards.

I ended up scrapping the Ruby implementation and I'm now happily coming up to speed on how to manage llvm code with, well, llvm tools. This is not without effect from the leads of the program, of course. Live and learn, I suppose.

Monday, January 16, 2012

Just making sure

I was pouring over some code recently and came across one expression that really made me shake my head:
buff[strlen(buff)] = 0;
I pretty sure the intent was
buff[strlen(buff) - 1] = 0;
Either that, or they really wanted to make sure the string was null-terminated.