Saturday, January 16, 2010

My first steps with the Arduino

I recently received the arduino I ordered on Makershed. Actually, I took a starter kit to play with this small piece of hardware. The board has an ATMEGA328 uproc (8-bit) with few I/Os to play with.

They offer a nice tiny sdk to write your code/compile and upload. I've nothing to say, it's working great, they did a good job, however, since I am an emacs aficionados (and I'm not a Java fan), I wanted do the process manually.

The first was to analyze a bit was was given in the arduino (software) package. The file being in arduino-0017/hardware/cores/arduino/Makefile gives you the makefile to compile your programs. We can already notice that it does not work out of the box and that you've to modify it.

Here are my modifications:

INSTALL_DIR = $(HOME)/arduino-0017
PORT = /dev/ttyUSB0

AVR_TOOLS_PATH = /usr/bin
SRC = $(ARDUINO)/pins_arduino.c $(ARDUINO)/wiring.c \
$(ARDUINO)/wiring_analog.c $(ARDUINO)/wiring_digital.c \
$(ARDUINO)/wiring_pulse.c \

AVRDUDE_FLAGS = -V -F -C $(INSTALL_DIR)/hardware/tools/avrdude.conf \

Well, you notice that one file somehow disappeared in SRC. I simply removed it and it seems to be working. Also, the AVR_TOOLS_PATH was pointing on a wrong directory.

Now, for compiling your stuff, a simple make must be enough.

The next step was the upload that was a big deal for me. Actually, it was working with the Java interface, but not with avrdude. Actually, I was using the following command, because I saw it somewhere:

avrdude -V -F -C ~/arduino-0017/hardware/tools/avrdude.conf -p m328p -P /dev/ttyUSB0 -c stk500 -b 19200 -U flash:w:applet/Fading.hex -vvvvvv

Well, I got the following message:

avrdude: Send: 0 [30] [20]
avrdude: Send: 0 [30] [20]
avrdude: Send: 0 [30] [20]
avrdude: ser_recv(): programmer is not responding
avrdude: stk500_recv(): programmer is not responding

So WTF (Huh, btw, I entered twice avrdude avrdude [...], it segfaults after trying one :)) ? How so it's working with the Java App, but not with the avrdude ? As a wise guy said once "one week of trial and error can save up to half an hour of reading documentation", well, actually I could have read the Arduino troubleshooting section, but...

My idea was to sniff the what's going on /dev/ttyUSB0 when using the Java IDE and compare it with the avrdude command. To sniff it, I found jpnevulator as being usefull.

When running it, ./jpnevulator --read --tty /dev/ttyUSB0, turned out that I was getting the "programmer is not responding" error message even in the Java IDE :), this meant that the Java IDE was calling avrdude somehow (since this is an avrdude error message).

Cool, I downloaded the Java files from their svn and started to grep on these. In arduino/app/src/processing/app/debug/ I found something interesting:

if (verbose || Preferences.getBoolean("upload.verbose")) {
for(int i = 0; i < commandArray.length; i++) {
System.out.print(commandArray[i] + " ");

So, since I did not want to recompile all the files (lazy ?), I just wanted to set this boolean upload.verbose to true. Turns out that the preferences are read from a file ~/.arduino/preferences.txt, so you just have to add "upload.verbose=true" somewhere in there.

Now we run the Java program again and we the nice working avrdude command. We can use it directly after resetting the device (by pushing the button or directly sending a reset signal).

The command it now:

/usr/bin/avrdude -V -F -C ~/arduino-0017/hardware/tools/avrdude.conf -p atmega168 -P /dev/ttyUSB0 -c stk500v1 -b 57600 -U flash:w:applet/Fading.hex

Basically, the speed was wrong. Again, don't forget to push the reset button before shipping the code on the board

Monday, January 11, 2010

Finding the number of parameters directly in the assembly

Recently, when working on my library tracer, I wanted to know the number of parameters a function uses. I did not have any access to source code or debug info, so I had to find another way to get this information. Programs like ltrace/strace have an extra file, usually located in /etc/ to define the prototype of certain functions. When ltrace does not know a specific function prototype, it simply sets the number of parameters to 5 by default. However, by doing a simple analysis of the assembly code we can infer the number of parameters with a pretty high success rate. In my study I assumed we are using a x86_64 Linux box that binaries have not been obfuscated.

We will focus on regular registers, but the theory applies for FPU registers too. By convention, on x86_64, GCC will use the registers to pass the arguments (before using the stack), in the following order: %di - %si - %dx - %cx - %r8 and %r9. Thus, without loss of generality, up to 6 parameters can be passed through registers (before using the stack), with some exceptions for bigger data structures.

We define a block as being the set of instructions between two instructions changing the control flow (e.g.: ret / call / j). First, we localize this instructions in the disassembled program. From there, we move backward to retrieve the different parameters.

Let's do it on a example. The following snippet of code defines 4 blocks:

402406: 84 c0 test %al,%al
402408: 0f 84 62 ff ff ff je 402370
40240e: 40 84 ff test %dil,%dil
402411: 74 e0 je 4023f3
402413: 83 3d e2 5e 21 00 03 cmpl $0x3,0x215ee2(%rip)
40241a: 75 d7 jne 4023f3
40248c: 48 8b 2d 35 69 21 00 mov 0x216935(%rip),%rbp
402493: ba 05 00 00 00 mov $0x5,%edx
402498: be 88 0b 41 00 mov $0x410b88,%esi
40249d: 31 ff xor %edi,%edi
40249f: e8 24 fb ff ff callq 401fc8

If we take the last block, and we perform a backward analysis, we figure out that the registers %di, %si, %dx (and %bp) are modified. According to the _cdecl_ calling convention, it is likely that the function will take 3 arguments before jumping into the plt trampoline.

Sadly, this is not always as clear as in the previous example. For instance, we can see that the others block does not follow this nice rule, but can we deduce the function are not expecting any parameter ? As it was previously stated, it is very rare that a function in called only once. Although, the main purpose of a function is exactly the opposite, ie being called as often as possible from various parts of the program. Thus, by applying the previous criterion over all functions, we can deduce a heuristics that will retrieve the number of arguments with a good success rate.

Every time we encounter a function call, we save the set of registers of the block. A map looks like the following: (%di. %si. %dx. %cx, %r8, %r9). Every element is a boolean and says whether the register was used or not.

Let's take the same function as before, dcgettext(..) from /bin/ls. The function is called around 15 times in the overall program, but all the registers cannot be retrieved every time.

(0, 0, 1, 1, 0, 0)
(0, 0, 1, 0, 0, 0)
(0, 1, 1, 0, 0, 0)
(1, 0, 1, 0, 0, 0)
(1, 1, 1, 0, 0, 0)

Typically, (0, 0, 1, 1, 0, 0) means that only registers %dx and %cx were used. Thus, we take the set that has been used the most frequently. Let's assume the set appearing the most often is: (0, 0, 1, 0, 0, 0). This would mean that only register %dx is used. However, we do have a discrepancy compared to the official _cdecl_, because the first parameter must be sent through the %di register.

A good practice is to set to 1 all the registers that are on the left of the top-right register in the map. Thus, (0, 0, 1, 0, 0, 0) will become (1, 1, 1, 0, 0, 0). This means that register %di and %si are also used. To make sure our theory is correct, we can check in the man pages that the prototype is correct:

char * dcgettext (const char * domainname, const char * msgid, int category);

For the function having an associated man page, this technique has been shown to be very effective, by retrieving correctly the number of registers 90% of the time. When the mean gives us a guessable output, we will always choose the value that have more registers set, in order not to miss any of them. Note that this technique is very light, since it does not require to go into the called function to analyze the parameters in there.

To implement this, I chose Perl for a simple reason: I get the binary output from objdump and then I can parse into it pretty easily with simple regex. Using this kind of techniques we can also infer the type of the parameters, but this is another story 8).