Friday, October 29, 2010

Revenge of the unit test

I wrote some unit tests a while ago, but I was too lazy to run them. I looked into FOSS Continuous Integration (CI) testing solutions, but couldn't really find anything that really caught my eye.
I played around some more with CDash (, which was at the top of my list. Unfortunately, it currently still seems pretty SVN/CVS oriented and without previous experience with CDash, the entry barrier to use it seems relatively high. Its natural zone of comfort seems to be SVN/CMake/Doxygen. There is a test server on the Kitware website at . I also tried to setup a local server which I may have had more luck with, but I couldn't get one of the dependencies installed. I'm told that Kitware is moving to git for one of their projects, so support for git might be cleaner in the near future.
I was also recommended to look into CIJoe ( Unfortunately, it seems to crash for me. This may be because Fedora runs an olllld version of Ruby. Since this will be a dedicated virtual server anyway, I'll try to setup a VM to give it a better shot. They have a cool logo thought and even sell merchandise with it:

In the end, I decided my current needs are very modest and it would be better to get some crude hacked together server running than nothing at all. So, enter UVBuilder. It can be found at util/uvbuilder . Basically it uses a JSON config file to checkout, update, build, and run the code. It then e-mails results if there seems to be some change in status. Its very simplistic and has some dumb features like needing to checkout two copies of the code that can be solved with minor effort if I care.
I also played some more with using Valgrind to extensivly test the code. I had noticed that sometimes I would hexdump a data object and valgrind would trigger on that object if there was an error. So, I added a function that I called "poke" that would iterate over a block of memory that effectively does nothing. However, it makes the control flow appear to depend on the values by executing a statement like if( *ptr ) doNothing(); on each value. I found that it seems that std::map might leave uninitialized values though, so I'll have to make more custom Valgrind ignore files if I want testing to be truly effective at these tests.
So, next steps are to get all of the existing unit tests to pass (3 regressions, they all seem related to the same issue), and then beef up the unit tests now that I don't have to keep manually running them.

EDIT: all original unit tests pass after various fixes. Now to write a bunch of FLIRT tests.
EDIT: obj2pat unit tests created. And I'll try to get back to the comment below in the near future

Wednesday, October 27, 2010

FLIRT nearing completion

bfd based .pat generation is probably at an acceptable level. The behavior for handling short length names is kinda ill defined, so I'm not sure if there's much I can do about that. Additionally, FLAIR implements some x86 specific linker relocation fixup that I currently don't support since its currently all architecture independent. Also, while the basic architecture is there, much of the code should be moved out of the uvdbfd plugin and into the main engine. If I write a .pat generator for the uvdasm plugin (configuration file based architecture), this should be accomplished at the same time. I also figured out what one of the bits meant in the .sig format that has been annoying me for a bit. The reference .sig dumper had showed some of the function offsets being negative which didn't make sense to me. However, I finally figured out that this refers to local symbols (ie the a static global function in C/C++).
Generally, I'd consider .pat generation much harder than .sig since .pat is very platform specific and I'm guessing .pat stuff more or less isn't. I'm hoping that by Monday I should have uvpat2sig working smoothly. For starters, the old signature file dumping code was not integrated into the engine. Now, the signature file is actually loaded and then printed by dumping the loaded database. This is critical since in order to actually do signature matching, I'll need to load these up.
There are several issues with the current FLIRT engine. First, I haven't nailed down the overall file checksum computation. I'm guessing its just a CRC16 on the tree section (ie excluding the header), but haven't confirmed this. Second, compression/decompression isn't implemented. This isn't a high priority item and can be done later with presumably little impact on the loading mechanism. Next, the .sig file seems to leave out a lot of items from the .pat file. I need to figure out more accurately what items it leaves out and why. In particular, it looks like it only keeps one (the first?) external reference in a function. Finally, there is some attribute in the .sig file I don't understand. It seems to be some sort of referenced data with an offset and value, but I haven't yet devoted time to figure out what it refers to.

Sunday, October 17, 2010

Misc progress

There were some irregularities in the FLAIR output vs my output. The first is that I realized I had misunderstood what FLAIR calls modules. When I had seen FLAIR stuff before, it had been all windows junk and every line corresponded to one function. However, the test file I worked with was a .a file. Since a .a file contains .o files, this made it so each library module was actually a collection of functions in each .o file. I think was done because of the way linking groups object files on desktop / operating systems. However, this assumption is not valid for embedded systems due to the heavy static analysis done. I'll add a policy option to control how these signatures are generated. Additionally, there was a bug resulting in skipping functions that had multiple defined names. Code did something like size = next - current positions. If size is 0, assume undefined symbol and skip. However, this 0 size turns out to because of multiple names at the same file position and I was mentally mixing up the tables for all symbols vs defined symbols.
Regarding GUI progress, I've been trying to learn how to write a custom QAbstractScrollArea. This is the long term solution to disassembly, hex, and other complex scroll area issues. Instead of generating just the current page using hacks, a proper widget will be implemented that can fix things up as needed. Not going so well so far, but at least I know roughly what I need to do. It looks like the options are basically to implement QAbstractScrollArea directly or subclass QTextEditor or similar. I tried messing with subclassing QTextEdit, and it looks like it would become a hackish mess quickly. Signals were changing some of the values I tried to override and who knows how it would stand up to future or past Qt revisions. The other solution seems more manageable and proper way to do things. I'll probably implement a hex viewer first since its simpler to toy with than using the full uvudec engine.

Saturday, October 9, 2010

Object architecture plugin-able

The object engine is now pluginable. This was the last major planned core architecture enhancement for the semester. Object plugins allow say, to create a plugin for Microchip's C18 compiler if it used some format (I think it did, but I don't remember for sure). However, this did result in one hack that I haven't figured out if is actually a good idea or really is a hack. There is now a function getPrimaryExecutableAddressSpace() that returns the area where the main program is expected to reside. It seems this will work in most cases for the general "just disassemble the binary" case, so maybe this isn't an issue. Or maybe I should iterate over all executable segments? The issue with the latter is that often these aren't desirable to print. For example, on Linux x86 with ELF files, those aren't desirable. However, one of the engine enhancements was grouping object file format, architecture, operating system (future placeholder), and debugger (future placeholder) into a UVDRuntime class. This makes it so that if enough information is given, it is possible to combine attributes to resolve these special cases.
There are still several parts of the code that need to be improved and will be hammered out more as I need to support a more advanced architecture like x86. The specific semantics of how to read data from within a memory section need to be refined. For example, should the encapsulated data object actually do the mappings for the virtual address space? For example, say the address space actually starts at 0x08400000. Should the first valid address be 0 or 0x08400000 on that data object? One issue with the latter is that if an architecture does not provide byte level addressing, a lot of functions may not make sense. It seems most if not all architectures base their addressing on bytes, not words, so this may not be an issue. Since the number of memory spaces should be fairly small with perhaps up to a thousand on a large Windows program with many DLL dependencies, it may not hurt to provide objects that can map the addresses in both ways as a convenience since it looks like each mapper object only consumes about 24 bytes (virtual func table, target data, start target address, end target address, start read address, end read address) which is relatively small.
Now that the core engine enhancements are done, I will work on the library recognition enhancements. There are several large action items. First, make the BFD output matches FLAIR output exactly. There are some advanced reference features and my lack of understanding of the symbol references that are getting in the way of that. Second, decouple FLIRT code from bfd code. This will mean that if someone can write an object module that finds relocations, it can generate pat files. Finally, implement library recognition in the analysis engine. This is a lower priority since the generated .pat and .sig files can be used in other programs, so are not useless by themselves.
I'm also still trying to figure out GUI issues. The short term solution seems to be to make the scroll bar based on address only and only render the area currently shown. An example software that does this is the Metasm GUI.
  • Much faster render time
  • It will be easier to figure out scroll bar position. Changing data analysis does not mean we'd have to recalculate our position. For a large program, and most are probably large enough, the user probably wouldn't notice this difference anyway due to the huge number of elements at each position
  • We must perform our own logic when an address is clicked on instead of using tags. This was probably going to happen eventually anyway in case we jumped address spaces
  • To make scrolling be line (which seems more intuitive to me), we will have to buffer some of the nearby rendering and feed it line by line
  • Some advanced level text editor/viewer features may be lost (copy text over multiple pages, etc)

Sunday, October 3, 2010

Plugin away at architecture enhancements

Okay so I wrote this at 1:30 AM or something and I'm really tired, but its hopefully at least somewhat coherent brain dump.
With the new semester comes many new goals. One of the major goals was to get a plugin system up and running.
The first part of this was to modularize the architecture instead of assuming UVD Disassembler config file based architecture which is obviously not gong to work in every case. I spent most of a day or two a few weekends ago and this is now done. First, I separated the code out so that it worked as a dynamically assigned UVDArchitecture object. The second part was to make it a plugin. Although I don't like the way load paths and such are treated (security issues for starters), I have at least a basic system running. Example output:
[mcmaster@gespenst bin]$ ./uvudec.dynamic --help
uvudec version 0.3.0
libuvudec version 0.3.0
Copyright 2009-2010 John McMaster
Portions copyright GNU (MD5 implementation)

Usage: ./uvudec.dynamic
--debug-general (debug.flag.general): set given debug flag
--debug-flirt (debug.flag.flirt): set given debug flag
--help ( print this message and exit
--version (action.version): print version and exit
--plugin ( load given library name as plugin
--plugin-path (plugin.path.append): append dir to plugin search path
--plugin-path-prepend (plugin.path.prepend): prepend dir to plugin search path
--input (target.file): source file for data
--output (output.file): output program (default: stdout)

Loaded plugins (1 / 1):

Plugin uvdasm:
--config-language (config.language): default config interpreter language (plugins may require specific)
python: use Python (default)
--config-language-interface (config.language_interface): how to access a specifc interpreter (options as availible)
exec: execute interpreter, parse results
API: use binary API to interpreter (default)
--arch-file (arch.file): architecture/CPU module file
Which reminds me, the GNU hash thing doesn't need to be in there and should be removed since its GPL contamination. Plugins can be also added easily by third parties as the recursive make simply tries to execute all makefiles one level down from the $ROOT/plugin dir. So, also you have to do is copy an example plugin and you can try it out without editing any of the core makefiles. Maybe I'll do something similar to Linux style kernel modules where you latch onto an installed build system. There is an issue with current code installing nicely and having modules compile the same because installed headers will all be prefixed with uvd/, but for dev they currently aren't. I could put all headers in a uvd dir. I was thinking of simply sym linking uvd dir to main code dir. This wouldn't work on native Windows builds, but I don't know if I will ever support that anyway. Probably Cygwin or mingw at best. I should look at some projects like libxml2 that I know do this and see how their build system handles it.
The other major area that needs to be improved, and more so than architecture, is object file abstraction. Assuming input files were only raw binaries leads to lazy addressing throughout the code where its assumed all addresses are absolute. This isn't quite true as RAM is in a different address space as code (on some architectures), but since I'm not doing heavy analysis yet, these haven't been well separated. These improvements will be primarily driven by the need to abstract the object file formats and provide the ability to write plugins
I've never written a plugin architeiture before and so I've played around with several design patterns to try to make it work smooth. Ultimately, it seems different components need different interfaces to work well. What its seeming to boil down to though is that analysis events are best broadcasted as events and if people need to listen to them they register to a single callback and filter out the ones they don't want. However, with heavier duty objects such as architecture instantiation, I haven't quite decided on the exact mechanism. There are several constraints influencing this decision. First, ability to register loaders should be accessible for non-plugins as I haven't strictly made binary loaders and such have to be dynamic libraries and such yet. This requirement may change in the future as it would make the code more regular. Second, it is probably a good idea for factory methods to automatically unregister themselves if a plugin is unloaded. Third, for interactive purposes, it is desirable to be able to probe how good of a match a loader is to an input format without actually instantiating the engine, if possible.
To deal with the first issue, there needs to be a non-plugin way to register creation callbacks. So, simply iterating over the loaded plugins and calling a loadObjectFile or such function is not enough. At the very least, there would also need to be an additional list of registered callbacks. So, this seems to favor the latter method exclusively as it simplifies the code. The main downside is that plugins may have to be more aware of architectural changes. I might make it so that the plugin engine registers loader handlers to give an additional option if its not too much effort.
For the second, using the hybrid plugin and registration method would solve this and I might do that. For the last issue, this creates the issue of needing to maintain correlated function sets. Its certainly easier to do this with plugins since they provide coordinated data structures. Otherwise, I would have to create some hash maps during registration to correlate them. And, since there was no identifier returned to know what engine (plugin) it was, it would be difficult to track which engine it was that provided the best loading. These factors seem to indicate that the best long term solution would be to make every architecture and binary format loader its own plugin.
As far as the actual design of the object abstraction itself, I've been looking into several existing object abstraction frameworks. Mostly though I'm going off of binutils since its what I'm most familiar with. They seem to have a bias towards ELF, but do in fact support a lot of architectures and object formats.
On the GUI side. I tried adding clickable address links, but led to performance issues with large documents. I'll have to look into this some more. I'm thinking of making a custom "scroll" bar that shows the address locations and generates the screen only as needed. I know from time to time I like to copy and paste stuff though, and this might make doing that difficult, but possible, over areas larger than one screen. Also, IDA 6 has been released with a new spiffy Qt driven GUI. I probably won't get to try it out at least until February if I go work for MIT Lincoln Labs full time. But I did get to look at some screenshots and it looks nice.