Hi there! This page presents a couple of my side projects in software and research as well as some older students projects, published here in the hope of being useful or interesting to other persons on the web. If you are curious about myself or my academic works, or would like to get in contact with me, follow this link.
Lightweight and Efficient Link-Layer Security for First- and Second-Generation DVB Networks
Digital Video Broadcasting (DVB) systems are implemented in a variety of network architectures and application scenarios, and are predominantly used for the broadcasting of multimedia data to large-scale receiver populations and for Internet and intranet access by fixed and mobile devices via interactive satellite systems on a global scale.
The convergence towards IP networks requires migration from traditional DVB-centric transport mechanisms to solutions optimized for IP packet delivery and end-to-end connectivity over heterogeneous networks.
The openness of Internet protocols as well as of DVB networks entails a significant risk in communications security, however.
DVB broadcast links are particularly vulnerable due to their typically large coverage areas and the direct accessibility of a wireless communications channel.
This is of relevance not only for corporate, governmental, or military customers but also for ordinary end-consumers, who are increasingly concerned about privacy issues.
Often, end-to-end security mechanisms are not available, and common solutions for securing intermediate network links are suboptimal.
My MSc thesis, entitled "Lightweight and Efficient Link-Layer Security for First- and Second-Generation DVB Networks" and completed in July 2011, motivates the implementation of a link-layer security extension for DVB networks, and, based on an analysis of security requirements, proposes a specific solution that is designed to be lightweight in terms of implementation in resource-scarce, mobile receiver devices and to be efficient in the sense of being conservative in bandwidth usage while targeting a broad spectrum of application scenarios. The extension is further based on an extensive and in-depth theoretical analysis of traditional and state-of-the-art cryptographic solutions and security protocols, and implements novel techniques for improved protection against traffic flow analysis. By specifying protocol design, processing procedures, and a set of default security algorithms it can be readily implemented into terminal devices. While the extension focuses on current first- and second-generation broadcast and interactive DVB systems it further considers usage for future networks including a next generation of regenerative DVB satellite systems.
This thesis arose out of the work I have been carrying out over the course of several years at the multimedia communications group, department of computer science, University of Salzburg, under the supervision of Ass.-Prof. Mag. Dr. Bernhard Collini-Nocker, who I am grateful to for having directed my interest to the fascinating subject of cryptography and for giving me the chance to work on cryptographic aspects in satellite communication networks within this group while compiling this thesis. I am also grateful for his stimulating input during discussions and for the leeway I was given in completing this work.
» Download my thesis on Lightweight and Efficient Link-Layer Security for First- and Second-Generation DVB Networks (July 2011).
Tornado Codes
Tornado Codes are a rather new class of erasure-correcting codes based on randomly-connected irregular bipartite graphs with an almost optimal reception efficiency while being encodable and decodable in time linear to the block length, making them ideal for the encoding of large data and as an alternative to the classic ARQ concept as it is used on the Internet.
In a university project carried out in 2005, I have studied and implemented these codes. The codes have since been superseded by more efficient rateless codes such as LT and Raptor codes. Nonetheless, as I hope to have presented the concepts of a modern class of graph-based codes in an accessible way and there is little other introductory information about Tornado codes available on the web, I have put both the presentation and the paper of my project online.
» Read the paper online in German or in English...
» Download the paper (in German!) and the presentation (PowerPoint, in German!).
A Faster-than-Bresenham "Error-Compensating" Digital Differential Analyzer (EC-DDA)
Bresenham's line drawing algorithm is the de-facto standard for efficient line drawing on rasterized output devices such as computer screens or plotters. The algorithm offers a number of benefits: it is solely based on simple integer operations, which are fast and cheap to implement, it minimizes the error that arises due to the discretization, and it is order-invariant. In contrast, a naive digital differential analyzer (DDA) requires complex floating-point arithmetic, accumulates rounding errors due to the finite representation of possibly infinite rational numbers, and is not order-invariant. However, on a modern desktop processor floating-point arithmetic is queued into the processor pipeline just as fast as integer operations, and a DDA requires a fewer number of instructions than Bresenham's algorithm.
An idea I publically described in 2003 and implemented shortly afterwards allows one to upper-bound the cumulative numeric error that may arise in the DDA and by that calculation adapt the differential such that the result is an "error-compensating" DDA (EC-DDA) with the property that all pixels along the line attain correct rounding provided that their cooridinate values are smaller than some predetermined maximum (e.g., 221 for IEEE 64-bit floating point numbers). The new algorithm has been shown to be significantly faster than traditional Bresenham line drawing on modern desktop processors.
» Read the paper online... (under construction)
An Optimal, Linear-Time Axis-Aligned Rectangle Merging Algorithm
The problem of computing Boolean operations (such as union, intersection, and difference) of an axis-aligned two-dimensional rectangle (or bounding box) with a set of non-overlapping rectangles constrained by the additional requirement that horizontal lines within the cover of the set always extend to the maximum possible (so as to improve memory access patterns) arises in the development of an efficient window managener for a graphical user interface (see below) and other applications. I have devised and implemented a fast, thoroughly tested and optimal algorithm which achieves this goal in O(n), where n is the number of rectangles currently in the set.
» Interested in the algorithm? Contact me and convince me to release the sources.
Operating System Programming
One thing I wished I still had time for was working on an operating system that is based on concepts such as modularity, micro-kernel design implementing efficient message passing (at last!), real-time scheduling while considering additional parameters such as latency and quality of experience, efficient and strictly bounded algorithms, and a strong program trust seperation together with a strict security model from ground up. Back then, I enjoyed hacking and extending NewOS,
a modular kernel primarily written by former Be Inc. employee Travis Geiselbrecht, a code base to which I have contributed some of my initial changes. NewOS has got its appeal mostly
from its clear design with high portability in mind and its cleanly written source code.
Here is a list of some of the many improvements and additions to the NewOS sources (most of which are not submitted to the public code repository):
- a proof-of-concept very fast TCP-based client-server window manager with some very refined algorithms (shame on the X window system for being so slow)
- ...with two simple GUI programs (terminal and lines)
- a completely new network memory managment algorithm (cbuf code) that is more than 800% faster than the original code
- an asynchronous network timer implemention, further speeding up the network module considerably
- kernel slab allocator
- centralized kernel object handling
- a VESA VBE 3.0 video card driver that even resolves the most frequent vendor specific VBE 3.0 flaws and plain errors
- a NE2000 and compatible ISA and PCI network card driver
- support for outgoing ICMP messages and the ping utility
- the PCI module re-written
- improved timer code
- vastly improved POSIX support
- C++ exception support
- port of various GNU utilities, including the BASH shell
Terrender
Terrender is a software voxel landscape engine based on the concept of height-tracking to achieve a real-time rendering rate (30 fps) even on a decade old hardware. It supports 5 degrees of freedom in full perspective correctness, and simulates the 6th degree to some extent. Fully implemented in assembler, its visual outcome was remarkable back then when 3D graphics hardware was still in its infancy.
Freeform Deformation
A students computer graphics project carried out jointly with two of my colleguese for the course "Computergrafik II" in summer semester 2002. The project presents a simple and fast way to deform a 3D object (either polygonally or parametrically defined) by a technique called "Freeform Deformation".
» Download the paper (in German!) or the source code (in C).
Communication in Multi-Agent Systems
A nice introductory project on the concepts of artificial neural networks (ANNs) and multi-agent systems (MASs), carried out together with a friend of mine in summer semester 1999 for the course "Bioinformatik" (Natural Computation) at the University of Salzburg. The project tries to propose the characteristics of agents and describes what multi-agent systems are, how communication therein can work and finally how artificial neural networks can be applied to agents so that they "learn" autonomically how to communicate and act in multi-agent systems. As for the practical part of the project we wrote a program wherein agents whose goal is to survive by "eating food" get commands for finding that by their "master". Unfortunately for them, they have to find out the meaning of the commands by themselves.
» For the paper (in German) and the source code (in Objective C) look at the home page of this course.