Hacks & Code

I just stumbled across a pretty cool algorithm to compute Fibonacci number algorithm. So, I guess everybody knows the traditional recursive definition

fib(n) = fib(n-1) + fib(n-2)

fib(1) = 1

fib(0) = 1

Well, the disadvantage of this algorithm is that you can only compute fib(n) when you've computed fib(n-1) and fib(n-2) before. Well, with Binet's formula, you can compute the nth Fibonacci number without knowing any other Fibonacci number. The following C sample code shows how:

#include <math.h>

#include <stdio.h>



float fib(unsigned int n) {

  double a, b;

  a = (1.0/2.0)*(1.0+sqrt(5));

  b = (1.0/2.0)*(1.0-sqrt(5));

  return ((1.0/sqrt(5))*(pow(a,n+1)-pow(b,n+1)));

}





int main(void) {

  unsigned int n;

  for (n=0;n<100;++n) {

    printf("%f\n",fib(n));

  }

  return 0;

}

A few days ago, Clifford Wolf and I released trapdoor2. trapdoor2 allows remote users to execute local commands by sending 'magic cookies'. This is meant to be used to temporarily alter firewall rules, i.e. to open some kind of trapdoor so that users can access a service like ssh on a machine only from their current machine for a short period.



But trapdoor2 can be used for more than just that. Another ideas would be restarting services. For this use case, the WAP/WML (Wireless Application Protocol/Wireless Markup Language) support comes in handy: all you need is a mobile phone with GPRS to do important system administration tasks. Of course, trapdoor2 also support "traditional" HTML. For security reasons, trapdoor2 is HTTPS only. It even supports several SSL/TLS libraries, i.e. OpenSSL and GNU TLS. So you will be left in the rain when yet another vulnerability in OpenSSL is being found.

Some of my five readers might remember my little hack ContraPolice. Well, today, I did some little research out of pure boredom, and look where it is being referenced:

• The Annvix Project uses ContraPolice for hardening dietlibc.


• ContraPolice is in the bibliography to a vulnerability analysis seminar at the University of California in Santa Barbara.

This is just great. I never expected this little hack to spread so widely. But still, I'm happy that my code is being adopted, actually being used an probably making the (security) world a better place.

Ladies and gentlemen, I proudly present the successor to the infamous Pretty Good Privacy (PGP) software: Pretty Good Double ROT13 Privacy, or short, PG2ROT13P. It is based on the latest research from the #mum cryptolabs, and will revolutionize the world of IT security. A demo version that both support encryption and decryption can be downloaded from here.



Propz go out to oli`, psychoKen, mik, f1r3, nulpie, herp, terrorgrl and all the other 24/7 hardcore idlers of the #mum cryptolab crew.

Today I ported an OpenSSL-based application over to GNU TLS (which implements SSL 3.0 and TLS 1.0), just to see how easily it can be done and how GNU TLS is different from OpenSSL. Well, first of all, GNU TLS is a bit simpler to program than OpenSSL. While you still need a lot of function calls to get SSL established, it's a lot less than in OpenSSL, and - most importantly - all library calls are lower case. Regarding key and certificate files, GNU TLS is perfectly compatible with OpenSSL. So applications that already have some kind of abstraction layer to make it easier to use OpenSSL or to make the use of SSL optional can be ported within an hour.



But still, GNU TLS has some issues: what is most annoying is that the SSL handshake takes almost infinitely long (around 5 to 10 seconds), while OpenSSL does that within a second (in my test scenario, it was always OpenSSL on the client side and OpenSSL and GNU TLS on the server side). When a had a look at GNU TLS using strace(1), I immediately saw what the problem was: GNU TLS continously polls the PID, the current time and some resource usage stuff. This is absolutely not necessary, and should be improved.



Another annoying thing was that GNU TLS has major issues with certain rlimits set. For example, when you limit the maximum CPU time using setrlimit(2), the SSL handshake is likely to fail with too few CPU time set (with OpenSSL, I experienced no problems so far). GNU TLS also gets problems when you set the maximum number of open files too low. The symptom: SSL handshake issues. GNU TLS needs to have more than 32 open files at the same time. I don't exactly know how many, but 64 work. On the contrary, OpenSSL works with less than 16 open files.

golbikiw 0.3 is available for download. This version now features almost all features you know from other weblog software, like

• a posting archive


• categories (golbikiw even allows a posting to be of more than just one category)


• a permalink for every posting


• the wiki functionality, where every article is assigned a WikiWord, and where WikiWords insides articles are expanded


• a search function


• an RSS feed


• posting, editing and deleting articles

What is still missing is a comment function. I'm sure that will still take some time, as I don't really need it right now.



Now that the main work for golbikiw has been finished, it is time for a little summary: first of all, I never thought that writing a weblog software would be that easy. The Ruby language, a few well-designed classes written in it that do the weblog's core parts, Ruby HTML templates and bits [;-)] of Ruby glue code made everything really smooth. During development, I fell into a few Ruby traps (like in Java, variables are only references to objects), but all in all, development went great. It's also interesting what sloccount thinks about golbikiw:

Total Physical Source Lines of Code (SLOC)                = 473

Development Effort Estimate, Person-Years (Person-Months) = 0.09 (1.09)

 (Basic COCOMO model, Person-Months = 2.4  (KSLOC**1.05))

Schedule Estimate, Years (Months)                         = 0.22 (2.59)

 (Basic COCOMO model, Months = 2.5  (person-months**0.38))

Estimated Average Number of Developers (Effort/Schedule)  = 0.42

Total Estimated Cost to Develop                           = $ 12,310

 (average salary = $56,286/year, overhead = 2.40).

SLOCCount is Open Source Software/Free Software, licensed under the FSF GPL.

Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."

Of course, these numbers are ridiculous, as it took not 1.09 person-months, but something like 3 persons-days. And it cost me not US-$ 12,310, but exactly US-$ 0 (well, except for electricity and food, and my time, but that would have been spent even if hadn't written golbikiw).


I think, writing free software definitely makes me happier person. I can feel that, now that I again accomplished a project that is (IMHO) not only interesting, but could also actually be useful to some people.

golbikiw 0.2 is available. This version features WikiWord detection and linking, permalinks and several bugfixes (including the bug that ate all characters but [a-zA-Z ] in the subject).



I have to admit, I never thought it would be so early with the integration of the Wiki functionality. But hey, the sooner, the better. And I never thought that it would be that easy. Now, there are only two more features on my TODO list that I want to address, and that is comments and setting categories for each posting.

Today I released golbikiw 0.1, the very first version of my very own weblog software which will act as a framework for my experiments with weblog concepts. You will need at least Ruby 1.8 to run it, because the CGI module of Ruby 1.6 behaves completely different to the one from 1.8, and it seems a bit buggy, too. You will probably have to adapt all the *.cgi files, because they point to /usr/local/bin/ruby as interpreter in the shebang path, while on most Ruby installations, the interpreter can be found in /usr/bin. OSX users need to install Ruby 1.8 by hand, because even OSX 10.3 ships with Ruby 1.6. Additionally, you will need the html-template module from the Ruby Application Archive.



After extracting the package and adapting the shebang paths, you have to make sure that the entries subdirectory is writable to the user under which your webserver runs. That's because golbikiw is solely based on flat files. All the configuration files can be found in the conf subdirectory, and should be fairly self-explaining.



Version 0.1 is likely to be buggy in some places, so if you try it out, and see some bugs, please report them to me.

Today I had a (IMHO) simple but good idea on how to combine weblogs with wiki systems: every weblog entry also represents a wiki entry. Whenever you post a new entry to your weblog, the software assigns a wiki name to the entry. This entry is then available just like a wiki entry, and these entries can be referenced with this wiki name from inside the weblog, which makes it not only a weblog, but also a wiki. And since I liked the idea, I decided to implement it by myself. Yes, currently, I'm creating my own weblog software. Unlike the other common weblog systems, my system -- which I called 'golbikiw', which is 'wikiblog' reverse -- is written in 100 % pure Ruby, uses Ruby HTML templates (just like Perl HTML templates) and doesn't need any database. Yes, you read correctly, it doesn't store anything to any database. All the entries are managed with the help of the operating system's file system, where one file represents one entry in the weblog.



Currently, reading and posting works, I still need to add some kind of authentication and functionality to actually edit and delete entries. And timestamps should be shown for each entry. And I have to resolve some bug something (Ruby? Apache? The browser?) seems to eat special characters like '?' or '!' in the subject when trying to post anything. And as soon as this is done, I will do the first release.

Since the last posting about cuttle I had quite some time to do further tests and improvments on cuttle. It now runs more stable than before, reacting on even the more obscure exception that may be triggered during execution. On Mac OS X, you need a Ruby version more recent than the 1.6.8 that comes with OSX 10.3 or the 1.6.7 from fink, because these versions are buggy (TCPSocket.gethostbyname segfaults after 20 to 30 calls to this method). You can download the most current version from http://synflood.at/tmp/cuttle.rb.

Right now I finished my first Rendezvous hack, which is a patch against nullmailer 1.00RC7 that enables zeroconf/Rendezvous support to nullmailer: when the environment variable USE_RENDEZVOUS is set, nullmailer-send tries to look up the SMTP server (actually _smtp._tcp.) via Rendezvous instead of looking at the remotes configuration file. Unfortunately, the programming model is howl is pretty crappy, so I had to fork, wait until I got a resolved reply (or until I had reached a timeout of 5 seconds), and then write it to the parent process of nullmailer-send that waits for the result. Not very nice, but AFAIK there is no better way to solve this. Oh, well...



BTW: the patch is not (yet) thoroughly tested, feedback is welcome (as usual). Ah, before I forget it: after applying the patch you have to run autoconf to build a new configure script. I just didn't want to include the configure diff, as it would have been about 90 % of the whole diff file's size.

As a quick hack, I ported the latest systrace patch to the current Linux 2.6.0 kernel. You can find the patch here: systrace-linux-2.6.0-v1.4.diff. This is totally untested. The only thing I actually tested is whether it compiles, and it does. So, feedback is definitely welcome.



BTW: the "totally untested" is not that bad, actually, since I based the patch on the systrace patch for 2.5.59, which I first adapted for 2.6.0, and then merged in all changes between 1.1 (the version the 2.5.59 patch is based on) and 1.4 (the latest systrace version).

NFL, the naive functional language, is finally released as version 0.1. I encourage everyone to download it and try it out. Many changes were done compared to the last preview version, lots of bugs were fixed, a number of string functions were added (including Perl-like split and join functions), and more test programs were added.



Feedback is welcome (as usual), should you write an nfl program, please send them to me so that I can include them as examples and/or test programs into the official nfl package.

Right now, I decided to put out a new preview version of scheme0 (working title), my interpreter for my highly naive functional programming language. This is also the first preview version that comes with a brief documentation for all intrinsic functions that scheme0 provides. You can download the preview here.



I'm still searching for a better name than 'scheme0' (that sound and looks so stupid), and still I had no better idea than NFL, the naive functional language. Input is always welcome (when it's about names, I never was really creative).

Last friday I wrote that I wanted to write code. And that's what I did. During the last few days, I created a small interpreter for my very own functional programming language. It doesn't yet have any official name, but since it has a scheme-like syntax, I gave it the working title "scheme0". But I think this will change. A name I already thought about was "NFL", for "naive functional language". The interpreter is naive, because I'm naive. I never did any course on writing compilers or interpreters, and so I simply did it the way I thought it would work. Anyway, for anybody interested in actual code, you can download a preview version here.


To give an example on how source code of my language looks like, here you can see an implementation a well-known algorithms to compute a number's factorial (i.e. n! := n*(n-1)!, 1! := 1, recursively solved):

(defun (fact 'x) (if (eq 'x 1) 1 (mul 'x (fact (minus 'x 1) ) ) ) )

For more (simple) examples have a look into the preview .tar.gz. Please play with it, and implement other algorithms, to test whether the interpreter works correctly. So, feedback is welcome (as usual).