AK's weblog

There are certain C standard library functions whose potentially insecure behaviour is well known. These functions, such as sprintf() or strcpy() are usually avoided these days. But today, while reviewing some security-related code, that there is one function where you wouldn't really expect any weird oder unusual behaviour. The function that I'm talking about is strtoul().

Most people will automatically know and/or associate that it's the unsigned long variant of the strtol() function that is used to convert strings to integers. Some may also think about using this function to verify that the result of the string to integer conversion can never be negative, and thus, strtoul() completely ignores negative numbers. But this is wrong: strtoul() does check for a + or - sign, and if it finds a "-" before the actual number to be converted, it negates the the scanned value prior to returning it. That's what the manpage and the official SuSv2/v3 documentation say, and it sounds innocuous. But it definitely isn't, and this little test program will show this: Let's see how this program behaves when feeding it some numbers: To sum this up:

• Positive numbers are scanned correctly, except for ULONG_MAX.
• Negative numbers are scanned, and their (negative) value is casted to an unsigned type. In the case of -1 that becomes 4294967295, this also (incorrectly) signals an error during conversion, in the case of -2 it doesn't.
• Numbers that are too large are signaled as such.

In my opinion, this behaviour is clearly unacceptable, as it is completely counter-intuitive, it can lead to incorrect error signaling, and is a hazard for anybody who wants to stick to unsigned integers only. It's nothing but a thinly disguised (unsigned long)strtol(...). So don't use it. Use strtol() and explicitly manually exclude negative values instead, and explicitly cast it to an unsigned value afterwards. That limits the maximum value that you can scan, but hey, the world isn't perfect.

David Tanzer recently blogged about comparing performance of equivalent C and C++ programs. He did so in order to be able to decide which of the two languages he should use as implementation language for his diploma thesis. In C, he used a classical dispatching mechanism, while in C++, he used inheritance and virtual methods. His result was that C++ was about 7 times slower with his test program. I couldn't believe this, and so I conducted my own tests, with a slightly modified source which can be downloaded here. I conducted tests of binaries with different optimization levels, all done with gcc/g++ 4.2.3 as provided by Debian unstable:

Optimization	C (average of 3 runs; [s])	C++ (average of 3 runs; [s])
-Os	38.778	34.001
-O3	27.951	32.722
-O2 -fomit-frame-pointer	27.985	31.562
-O0	33.271	34.192

Auf die wirklich ekligen Sachen kommt man erst drauf, wenn man versucht, Unix-Legacy-Code auf einem aktuellen Linux oder OSX zum Laufen zu bringen. Da bin ich z.B. draufgekommen, dass es in C unter Linux ein Symbol "end" gibt (wer es zur Verfügung stellt, konnte ich ad hoc nicht rausfinden), auf jeden Fall muss man es nur deklarieren, und schon ist es verwendbar:Draufgekommen bin ich darauf nur, weil ich sort(1) von Ultrix-11 auf Linux portiert habe, und diesen Code wiederum unter OSX zum Laufen bringen wollte. Und dabei ist mir folgender Code untergekommen:Dieser Code legt nahe, dass "end" das aktuelle Ende des Datensegments enthält, und obiger Code holt sich das Ende, zählt einen großen Betrag (für damalige Zeiten...) dazu, und verringert ihn solange um 512 (welche Einheit?), bis brk(2) OK gegangen ist, und das Datensegment vergrößert ist. Sowas ist in Zeiten von 4GB+ RAM und Memory Overcommitment natürlich höchst obsolet. Trotzdem ist es bemerkenswert, wie damals(tm) noch programmiertechnisch gearbeitet wurde.

Endrekursionen sind Rekursionen, bei denen der rekursive Funktionsaufruf die letzte Operation zum Berechnen des Funktionsergebnisses ist. Eine wichtige Eigenschaft von Endrekursionen ist, dass sie zu Iterationen transformiert werden können, d.h. der Speicherverbrauch auf dem Stack bleibt konstant, während bei nicht-endrekursiven Funktionen der Speicherverbrauch auf dem Stack mit der Rekursiontiefe wächst. Das ist insbesondere relevant für funktionale Sprachen, deren einziges Mittel zur Iterationen die Rekursion darstellt. Das sei einmal der Theorieteil.

Gestern hab ich mir aufgrund einer Diskussion mit nion zu dem Thema mal angeschaut, was der gcc mit endrekursiven Funktionen in C denn genau macht. Und siehe da: der gcc transformiert endrekursive C-Funktionen doch tatsächlich zu Iterationen! Folgende Codesnippets zeigen es deutlich:

wird zu
Damit das auch etwas praxisrelevanter wird, hier der Code zum rekursiven Freigeben einer verketteten Liste:
Der gcc macht folgendes daraus:
Coole Sache. In beiden Assembler-Snippets ist weder ein "call sum" noch ein "call delete_word_r" zu finden.

Nachdem meine verehrte Leserschaft über meine Berichte über die Entwicklung von newsbeuter das ncurses-UI-Toolkit STFL zumindest vom Namen her kennt, möchte ich ein wenig mehr über die Eigenschaften und Features dieser genialen Library schreiben, da sie mir bisher sehr beim Erstellen von Konsolen-UIs geholfen hat.

Die Basis von STFL ist die Layout-Beschreibungssprache, mit der man die grundsätzliche Ausrichtung und Positionierung sämtlicher Controls inklusive (optional) des Inhalts und der Farbgebung. Diese Beschreibungssprache wird in eine Datenstruktur geparsed, die dann später zur Laufzeit einfach modifiziert und abgefragt werden kann. Ein wichtiges Prinzip des Layouting bei STFL sind dabei Horizontal und Vertical Boxes. Man stelle sich z.B. den gesamten Bildschirm vor, den man zuerst in mehrere Boxen "untereinander" teilt. In so eine Box kann man dann ein Control platzieren, oder eine weitere vbox (macht nicht sehr viel Sinn), oder aber eine hbox, welche die Box wiederum in mehrere Boxen nebeneinander teilt, usw. usf. Zusätzlich kann man jeder Box noch die Information mitgeben, in welche Richtung sie expandieren soll. Mit diesem simplen Konzept hat man ein mächtiges Werkzeug bei der Hand, um brauchbare und komplexe Layouts für Konsolen-UIs zu designen.

Zur Laufzeit wird diese Layoutbeschreibung dann eingelesen (entweder aus einer Zeichenkette oder aus einem externen File, ich persönlich verwende dieses Skript um STFL-Layouts direkt in Programme einzubinden, aber trotzdem die Layouts in schönen externen Files im Sourcetree liegen zu haben), und die resultierende Datenstruktur wird dem Programmierer dann als opakes "stfl_form *" zur Verfügung gestellt. Dieses Handle kann dann verwendet werden, um den aktuellen Inhalt von Controls auszulesen, zu verändern, den aktuellen Fokus zu bestimmen und zu ändern, und auch um die Datenstruktur selbst zu modifizieren (damit ließe sich theoretisch zur Laufzeit das Layout umstellen, auch wenn das in der Praxis i.A. wenig zielführend ist). Und natürlich kann man das Formular starten und kriegt Benutzereingaben weitergereicht, auf die man entsprechend reagieren kann.

Eine derartige Layoutbeschreibung sieht übrigens so aus:

Das ist das Layout der Feedlist, wie sie bei newsbeuter beim Programmstart erscheint. Es besteht aus einer vbox, welches von oben nach unten ein Label für die Überschrift, eine Liste mit den Feeds, ein Label mit Keyboard Shortcuts sowie ein Label für Information und Fehler enthält, alles gespickt mit diversen Details wie Farbgebung und der Information für die Labels, dass sie horizontal expandieren sollen, sowie für die Liste, dass sie horizontal und vertikal expandieren soll (und damit den meisten Platz ausfüllt).

Insgesamt ist das Interface von STFL sehr kompakt (14 API-Funktionen). Die Konstruktion eines Programms erfolgt meistens nach dem gleichen Prinzip: Initialisierung - Event Loop - Ressourcenfreigabe. Die Initialisierung ist bei STFL eine ganz simple:


Der erste Schritt ist immer, ein Formular anzulegen, und zwar mit stfl_create(). Dabei gibt es zwei Varianten, und zwar, einen normalen String mitzugeben, dann wird der String als Layoutbeschreibung geparsed, oder aber, man übergibt einen String, der mit '<' anfängt, und mit '>' endet, dann wird der Inhalt der Datei, deren Name zwischen '<' und '>' steht, als Layoutbeschreibung verwendet. Damit kann man auch Layouts aus externen Dateien laden, ohne diese Datei selbst öffnen und auslesen zu müssen, und man muss auch keinen extra API-Call bedienen.

Der nächste Schritt ist dann, das Formular zu starten, und optional auch auf Eingaben des Users zu warten. Und zwar funktioniert das mit stfl_run().

Der zweite Parameter gibt dabei, wie lange auf Benutzereingabe gewartet werden soll, welche dann zurückgegeben wird. Der Wert "-1" bedeutet, dass keine Benutzereingaben eingelesen werden (wenn man z.B. lediglich das Formular neu zeichnen will), und 0 bedeutet, dass unendlich lange auf Benutzereingabe gewartet wird. Bei einem Wert > 0 wird soviele Sekunden gewartet. Findet bis dahin keine Benutzereingabe statt, so wird von stfl_run() NULL zurückgeliefert. Hierbei sollte man allerdings auf jeden Fall beachten, dass es auch sein kann, dass auch bei einer Wartezeit von 0 NULL als Rückgabewert zurückkommen kann, weil z.B. ein Tastendruck von dem Widget, das den Fokus hat, "konsumiert" wurde.

Die zurückgegebene Eingabe kann folgendes sein:

• "TIMEOUT": bei einem Timeout
• "ENTER": wenn die Eingabetaste gedrückt wurde
• "ESC": wenn die Escape-Taste gedrückt wurde
• "F0" .. "F63": wenn eine F-Taste gedrückt wurde
• "CHAR(%u)" (wobei %u einem unsigned integer entspricht): eine andere Taste wurde gedrückt, und der numerische Wert dieser Taste befindet sich zwischen den Klammern. Der numerische Werte für die Taste "a" ist z.B. 97. Und auch Ctrl-Tastenkombination sind damit abfragbar, so ist etwa Ctrl-A der numerische Wert 1, Ctrl-B der Wert 2, usw.

Am Ende eines Programmes ist es dann noch zweckmäßig, die Funktion stfl_reset() aufzurufen, um den Bildschirm entsprechend zu resetten. Mit diesem Wissen kann man schon ein nettes kleines Programm schreiben, das so eine typische Event Loop demonstriert, und zusätzlich führe ich auch noch ein paar weitere Funktionen ein:

Was man hier sieht, ist eine klassische Event Loop, wobei auf die Tasten a bis e sowie q reagiert wird. Es werden ja nach Tastendruck ein Label bzw. die Liste modifiziert. Mit der Taste e enthält man zusätzlich noch Informationen über die aktuelle Auswahl in der Liste.

Man kann noch wesentlich mehr mit der STFL machen, und dieser Artikel soll nur einen kleinen Einblick in die grundsätzliche Funktionsweise von STFL bringen, um dem einen oder anderen unter euch das Entwickeln von eigenen, neuen Texttools schmackhaft zu machen. Für mehr Informationen sowie andere Widgets wie Eingabefelder oder mehrzeige Text Views ist es ratsam, in die STFL-Dokumentation sowie die existierenden Beispielprogramme reinzuschauen. Es lohnt sich.

Wer übrigens die STFL "C++iger" verwenden will, den kann ich nur auf meinen "stflpp"-Wrapper hinweisen, den man hier (Header) und hier (Source) findet (MIT/X-Lizenz, BTW). Die STFL selbst unterstützt neben C übrigens auch SPL, Ruby, Python und Perl.

Es soll ja alte Systeme geben, auf den die Funktion strdup() noch nicht vorhanden ist. Sun OS 3 ist angeblich so ein Kandidat. Nun, was macht man, wenn man diese Funktion nicht zur Verfuegung hat? Man implementiert sie selbst. Und hier ist das grosse Problem: kaum einer macht es richtig. Vor ein paar Wochen hab ich einen Patch an den fetchmail-Maintainer (gluecklicherweise hat ESR das abgegeben) deswegen geschickt. Und was sehe ich heute in der APR (die Apache Portable Runtime)? Dieses da:
Zum Haare raufen. Also bin ich auf die Idee gekommen, einfach Google Codesearch zu verwenden, um eigene strdup()-Implementierungen zu finden. Tja, und das ging ziemlich schnell. Hier z.B..
enca_malloc() enthaelt uebrigens keinerlei Pruefung auf NULL, ausser ein assert(), d.h. wenn man mit CFLAGS=-DNDEBUG compiled, und in eine OOM-Situation geraet, fuehrt das zum gleichen Mist. Und auch MySQL sieht sehr vertrauenswuerdig aus:
Und das in einer Datenbank von angeblicher Produktionsqualitaet. *ts*

Fazit: drei strdup()-Implementierungen begutachtet, keine einzige macht es richtig.

Fefe schreibt in seinem Blog über die Fehlermeldung, die gcc bei "long long long" ausspuckt. Ich hab mir das noch etwas weiter angeschaut, und das mal mit 5 mal "long" ausprobiert:
$ cat t.c
long long long long long foo = 0;
$ gcc -c t.c
t.c:1: error: 'long long long' is too long for GCC
t.c:1: error: 'long long long' is too long for GCC
t.c:1: error: 'long long long' is too long for GCC
$
Und um ehrlich zu sein: wenn ich sowas sehe, möchte ich nicht wissen, was für ein Hack das Parsen von "long long int" bzw. "long long long" in gcc sein muss...

I just submitted my paper for 23C3. This year I wrote a paper about trapdoor2, which I wrote together with Clifford. I will focus on its implementation and use it as an example to show what attack vectors against a network server (and especially trapdoor2) exist, and what techniques can be employed to encounter potential attacks. Look forward to a pretty interesting lecture, showing some state of the art techniques in secure network server programming in C on Unix and Unix-like operating systems.

ndbm is library standardized by SuSv3 to store arbitrary key/value pairs into a file. Out of boredom, I wrote a small and simple implementation of it for dietlibc. The format it implements is incompatible with other ndbm implementations. I compared my implementation with BerkeleyDB and GDBM (which both feature ndbm compatibility modes), and while my implementation is a lot slower, the size of my data files is about 50 to 60 % of the ones produced by BDB and GDBM.

You can download the patch here. I submitted this patch to the dietlibc author, and he found it cool, but hasn't integrated it into dietlibc yet. Oh, and in case anybody asks what software I use to manage my dietlibc patches: I use StGIT on top of git. I have a local copy of the CVS repository, and with StGIT, I can manage the patches in a stack (similar to Andrew Morton's patch scripts and transvn) and keep everything up to date if any changes in the CVS repository or on any patch are done.

Once in a while, I'm googling for feedback on various projects that I implemented in the past. One of these projects is ContraPolice, which resulted in a brief paper and a prototype implemented as a patch for dietlibc. In fact, I'm really proud of what I produced here, because it is a straight-forward and simple solution to a big problem in IT security. While I don't claim that it's perfect (no solution is), it's supposed to be effective in (wild guess) 90 % of all incidents it tries to prevent.
Also, other security researchers came upon ContraPolice, most notably Yves Younan, who mentioned it in a number of papers, including a lecture at 22C3 on memory allocator security.
What I regret most about it is that I didn't put any further work into it. The concept of ContraPolice itself could be definitely improved in some points (Yves points out some weaknesses in his papers), and the prototype could be made more complete. I could also have tried to try to present it at some conference by myself, as it is definitely something that makes sense and is interesting to a number of people, if it only got out of prototype stage. Oh, actually it does already, e.g. the Annvix project mentions ContraPolice as one of their hardening technologies they employ.
And on a funny sidenote, I also found a call for help in a Linux forum where ContraPolice seems to have brought a bug to notice, with the consequence that the user is unable to install Mandriva 2006 onto his RAID. And according to the changelog found here this issue only seems to come up on x86_64...

I recently heard from nion and others that "assert() is crap". I would like to object this, and back that assertion (harhar!) with a few facts.

So, why is assert() not crap? Well, assert() is an early predecessor of a concept that is now known as Design by contract (DBC). The idea of DBC is that the caller of a function and the callee (i.e. the function) place a contract on what function arguments are allowed (the so-called "preconditions") and which return values are allowed (the so-called "postconditions"). In order to check whether both parties meet the contract, these preconditions and postconditions are formulated by the programmer of the callee, and the compiler (if supported by the language) adds code to check these conditions or some support library checks the conditions. If one of the conditions failed, the program fails hard - as one of the parties has violated the contract, - usually by aborting the program. As DBC has its roots in the OO area, a third condition has been added, the so-called "invariant", which checks the internal consistency of the object before leaving the function.

So why use DBC? Because, if implemented properly for all involved functions, it provides a specification on how the function may be called and what return results can be expected. During development, more attention is paid to the code and specification, and during testing, a lot of bugs (not all, such as incorrect specifications and logical errors) can be detected a lot easier than without DBC. Experience with languages like Eiffel has shown that this way of implementing and debugging code is very efficient, helping the programmer to get a program practically bug-free a lot faster. Of course, as with other techniques, DBC doesn't solve all problems, and one must not solely rely on DBC to find and fix bugs.

Now back to the actual topic, assert(). assert() is a simple mechanism that can help C and C++ programmers to implement simplified variants of DBC. Especially pre- and postconditions are easy to implement with them. So that's why assert() is "not crap", as nion stated. It is a useful tool, can help with debugging and testing and even be disabled when not required anymore.

Last, but not least, the humorous side of engaging this argument: