Richi's blog

Category: Software

  • Roomba vacuum cleaner hacking

    Late last year I got a Roomba vacuum cleaner from a friend. My wife and I wanted to evaluate such a device for a while. The battery was completely dead, and before spending lots of money on a  new battery, for a device that I didn’t know if it still worked, I tried to hook it up with the battery from my old netbook. That didn’t work out, so I ordered an original part. The friend didn’t want the Roomba anymore, so I thought if it’s not good for cleaning, I would use it as base to build some robot.

    We still use it to clean the floor. Well, it doesn’t quite meet the cleanliness requirements of my wife, but she does clean the floor less often manually. Nonetheless, I looked around how to hack the device. I found lots of information on how to connect to it through the serial connector as well as an alternative firmware. The connector is a mini-din 7 and it is said that a MacMini connector should work as well. The local Mac store didn’t have a MacMini cable, so I ordered a mini-din-7 connector from Conrad. I had the cable soldered together quickly.

    Of course the ideal device to connect to the Roomba would have wireless connectivity already in place as you don’t want to span wires across the floor as it drives around. As it turns out I have my old OpenMoko Freerunner still laying around, waiting for a new purpose. A perfect fit, i thought. Especially since I wanted to implement some SLAM for the roomba, and that could well run on the freerunner. (more…)

  • Full disk encryption with the crypto stick

    Last week I finished the udacity applied cryptography course. I did not as well as in the other courses, nonetheless I learned a lot and it was (as always) really interesting. We learned about symmetric and asymmetric encryption, hashes as well as key exchange and management. Each week in addition to the regular homework, we got a challenge question. For most of them, I invested some time, but then had to surrender. Well, I still managed to complete some of the challenges. The most fun for me was a side channel attack on the diffie hellman key exchange protocol. We had information on how many multiplications were required for the fast exponentiation of the RSA key on one end. That was enough to decypher the secret message. It was a good illustration of what has to be taken into account when developing real world cryptographic algorithms. And it reminded me of how some smart cards were hacked by closely monitoring the power consumption.

    Now, it was time to put my crypto stick to use. My netbook still ran Ubuntu Maverick due to the horrible graphics card (gma500). So I waited for the release of Linux Mint 13 LTS. In the 3.3 line of kernels there is a poulsbo driver already included.

    First I prepared the crypto stick according to this tutorial. After initially generating the keys on the stick for maximum security, I let myself convince to generate them on the computer to be able to make backups. I could not regenerate the authentication key so far, and thus I can’t use it for ssh at the moment. I’m still looking for a solution on that.

    Then I installed the operating system along with the full disk encryption according to this tutorial. At first it didn’t work, but then I discovered that there was a mount command missing in the tutorial and thus the generated ramdisk was not written to the correct boot partition.

    Here is how it works (as I understand it):

    • grub loads the kernel along with the initial ramdisk which contains everything necessary to communicate with the card.
    • The ramdisk also contains the keyfile for the encrypted root partition. Upon entering the correct pin, the smart card decrypts the key file (asymmetrically).
    • The key file in turn is used to (symmetrically) on the fly decrypt (and encrypt) all accesses to the root partition.

    It was new to me how to put stuff into the vmlinuz ramdisk. Apparently the script to ask for the key and decrypt the key file, as well as the keyfile itself and all the other required stuff can be added by installing a hook that is executed whenever a new ramdisk is created. For example when installing a new kernel.

    Not that I would have something stored on the harddisk, that would require such a level of security. But it’s interesting to set up and see how it works in action. The crypto stick adds a fair bit of security. As it has a smart card built in, a trojan couldn’t get hold of the private key, and a 2048 bit key is way harder to crack than a password that one can remember and type in every time.

  • Driving assistant

    Recently I completed the udacity class “programming a robotic car”, where Sebastian Thrun thought us what makes the self driving cars tick. He drew from his experience of winning the DARPA grand challenge in 2005. Now he’s leading the Google self driving car project. It was a very interesting course. Some stuff was already covered in the ai-class, but was a lot more detailed this time. We got homework assignments in python that we could complete directly within the website’s integrated editor. So, we implemented some of the key components in simpified form. Namely Kalman Filters, Particle Filters, Motion Planners with smoothing, and last and most interresting, SLAM.

    So, a while ago an idea started forming in my head. Todays smartphones should be powerfull enough to run some computer vision algorithms to help the driver identify obstacles, or warn him when he’s about to leave the lane. In fact, some premium cars already have such systems installed. First I looked in the android market, but found nothing. So I started looking around for how to integrate OpenCV in Android. I knew this part had been done before. I was not too keen to start yet another time consuming toy project, as I’m very busy at the moment. Another more extensive search in the Android market revealed some apps. And I was releaved to find some that implemented just what I was thinking about. There are two that I installed on my phone and am currently testing. Although I must confess, instead of increasing the security, they can also distract.

    Drivea

    The first app that I installed was Drivea. It may not be as polished as competing apps, but I like it when yu have the feeling, you know how it works. On my Galaxy S it runs smoothly without any problems other than some inaccuracies in the classifiers. Would be great if ot were opensource, so we all could learn from it, and maybe even contribute to the evolution.

    iOnRoad

    A bit too shiny for my taste. The core of it works really smooth. The classifiers and filters are better tuned than with the competing apps I tested.

  • Robot arm part 2 : ROS connection

    As the name implies, ROS is not just another library to get familiar with. It is an operating system for robots. That is also quite different to a traditional operating system. As I didn’t want to learn a whole bunch of stuff first, I learn about the concepts and facilities as I move along.

    After I modeled the robot arm with a urdf xml file, and it moved in the simlator, I wanted to connect ros to the physical arm. I found some tutorials for rosserial on how to connect to an arduino. So, I adapted these examples to the robot arm. The microcontroller board has many similarities to an arduino, but some things are different. First, I compiled the firmware. I had to copy some files from rosserial_arduino, and modified them accordingly. Hooking up the servos as ros subscribers is actually quite easy. The arduino examples use a standard python script on the computer. It looked as if I could use the same. But the robot arm only runs when the RTS level is high. As most libs and programs don’t do that by default, my robot arm did nothing. So, I copied some scripts from rosserial and modified them. In the process I learned about the statserial program that displays the status of the different serial pins. Now, the arm moved to the initial position and waited. Meanwhile I tried to connect to it with the modified python script, but I still got “Lost sync with device, restarting…”.

    (more…)

  • Optimizing compile time of a large C++ project

    The codebase of our PointLine CAD is certainly quite large. sloccount calculated roughly  770’000 lines of C++ code. I know, this is not a very good metric to describe a project, but it gives an idea. Over time the compile time steadily increased. Of course we also added a lot of new stuff to the product. We also used advanced techniques to reduce the risk of bugs, that have to be paid with compile time. But still, the increase was disproportionate. We mitigated it by using IncrediBuild. Just like distcc, it distributes the compilation load across different machines on the LAN. If I’m lucky, I get about 20 cores compiling for me.

    About once a year, one of us does some compile time optimization and tunes the precompiled headers. I did so about three years ago, and then this week it was my turn again. Reading what I could find about precompiled headers on the internet and applying that, I could get only a small speedup, roughly 10%. So I cleaned up the physical structure of the codebase. Here are some things I performed: (more…)

  • OpenCL First Steps

    There is an increasing noise about GPGPU computing and how much faster than CPU (even parallel) it is. If you didn’t hear about all that, GPGPU is about using the computer’s graphics card(s) to do general purpose computations. The key to the performance lies in the parallel architecture of these devices. From what I read, an average graphics card has 64 parallel units, but they are not as versatile as the CPU of which a typical PC these days has 4 cores. That means, if the task is well suited, it can boost performance significantly, but if not, it’s nothing more than a lot of wasted work.

    So I wanted to see for myself. To get started I read the book “OpenCL Programming Guide“. It gave a good overview. But now it was time to give it a try.

    (more…)

  • CyanogenMod and Ubuntu on my Samsung Galaxy S

    I wanted to install a real debian based linux distro and Cyanogen on my Android smartphone for a long time. First I was scared off by voiding the warranty on a new phone. But now it’s one and a half years old. And recently they announced that there will be no more firmware upgrades for my device.

    First step was rooting. There are lots of tutorials and descriptions online. Most of them are way too compilcated. Effectively, you just have to find a rooted kernel suitable for your device, and then: (more…)

  • packaging libboost compiled with llvm clang

    I read many articles and posts over the last year or so, citing how great llvm clang is. On one side it shall have a static checker that makes lint redundant, and on the other side the optimizer has an -o4 where the -o3 shall be comparable to other optimizers. On top of that, compilation speed shall be really fast. And the part that makes it interesting for folks like Apple (who uses and contributes), is that it’s licensed under a BSD style license. What more could you want?

    (more…)

  • Screen went black

    This morning, I had a short moment of horror when I turned on my Netbook. After the ubuntu splash screen, it went black and didn’t respond to any keys. The only response was for the power key, where it displayed the ubuntu splash screen again and shut down.

    My Acer aspire one has the dreaded Intel gma500 poulsbo graphics card. This graphics chipset was bought by Intel, and it’s absymal driver support has embarassed them ever since. It is also the reason I still run maverick on the netbook. Knowing that, I was even more horrified by the screen turning black.

    First thing was trying to boot an older kernel. In case you’re not presented with a grub menu, press shift after the BIOS.  Didn’t help, not even in recovery mode.

    So I booted to a console, and examined

    $cat /var/log/apt/history.log | tail

Start-Date: 2012-01-24  21:15:04
Commandline: apt-get install python-pyopencl
Install: nvidia-current:i386 (260.19.06-0ubuntu1, automatic), nvidia-settings:i386 (260.19.06-0ubuntu1, automatic), python-pyopencl:i386 (0.92~beta+git20100709-1ubuntu1), python-pytools:i386 (10-7, automatic), python-decorator:i386 (3.2.0-1, automatic)
End-Date: 2012-01-24  21:20:26

    The only thing I installed yesterday was python-pyopencs as it was the only package in the repository that seemed like a starting point to experiment with OpenCL. It has dependencies to nvidia drivers, but I didn’t think that installing these would break my system.

    So, all I had to do was “apt-get purge python-pyopencs nvidia-current nvidia-settings” and the system would boot again normally.

    It’s amazing how a linux system that doesn’t boot can almost always be saved relatively easily. With a Windows system that has the same symptoms you’re fucked.

  • Robot Arm part 1 packaging and simple manipulation

    Another project that I had in mind for a while was to experiment with robot arm path planning and inverse kinematics. If you don’t know what that is, think about how robot arms could be programmed. The simplest form would be capture and replay, in which you have a controller which which you record how you manually move the joints. The robot can then replay the movements. We humans have developed a good  intuition for moving our body parts and grasping, but when it comes to formally describing what you do with the joints of your arm, it quickly becomes difficult. My younger son is in the phase of learning to grasp right now, and it’s amazing to see how the eye arm coordination evolves. The second approach would be to program it like a CNC milling machine with something like G-codes.  This is a bit more general and more exact, but it’s also more difficult to do collision avoidance. And it’s complicated to calculate as most joints tend to be revolutionate. Both these approaches are only suited for repetitive tasks often found in industry automation, but completely unsuited for robots in dynamic environments. Now with inverse kinematics, you can tell the robot where the arm should move to in cartesian coordinates, and it does all the arm geometry calculations and positions the gripper to the correct position in the desired orientation. Maybe there are obstacles in between the current and the target position. To navigate around these, you also need path planning. That is usually done in configuration space. Real robots have also to care about dynamics such as inertia, but I won’t go that far.

    (more…)