Monday, April 29, 2024

How I ended up writing a garbage collector - how passion is the end goal for self-healing code.

How I ended up writing a garbage collector - how passion is the end goal for self-healing code.


The story of how I wrote a garbage collector for C is interesting.

It all started in 2001 when I got my first job as a software engineer, and I was working on a project which enables video footage to be recorded, with telemetry, sent over GPRS (2.5G) cellular modems.

The code was complicated. It had threads. It used dynamic memory allocation. I wasn't even done in my first year of uni and I realised that this is a major thing.

So I was worried that there might be some memory leaks that could prevent the code from running in a long time scenario.

I knew how to hack then, using stack overflow exploits etc. So I knew how to stack walk. I realised that if I walked the stack (a term used by hackers to look through a stack, without popping things off), I could retrieve pointers which I allocated using malloc().

This then leads to scanning the malloc'ed areas for more pointers, and recursively going from there.

This was the mark-and-sweep algorithm in play. A garbage collector, if you will.

This was a year before Valgrind (a memory leak detector) was made -- they released their first version in 2002.

Passion turned into a new company


It turns out my passion for side projects is the end goal. It's the things I find that I need to write for projects I do for work, that I find the most pleasing to do.

These "side projects" can turn out to be very valuable. Learning how the stack works, and writing a garbage collector offered me valuable insights in knowing how I can create code that "self-heals" -- a garbage collector "heals" broken code in the sense that any memory mismanagement is fixed up by the garbage collector.

Hence, drudget.com.au -- even though this company was made 20-odd years later, I kept making side projects for the last two decades, which culminated in me realising I could profit off these so-called side projects I've been making.

The deadlock detector


Another side project that I did whilst working at a company making performance monitoring software. I noticed I had to use threads again, this time however, I was maintaining code that wasn't written by me that had deadlocks in them. It's very hard and frustrating to debug deadlocks, because they don't occur all the time, so running and testing a program can be futile if you want to find a deadlock -- as it doesn't always occur.

So I wrote a graph analyser -- one which detects cyclic graphs of mutex locks -- as that's how deadlocks occur, when the cyclic graph hits both threads at the same time, it's deadlocked.

Again, this was before Helgrind was made.

Electric fence, or rather, Drudget's Flak Jacket...


In another episode of side projects, I wrote a clone of "Electric Fence" (written by Bruce Perens) which detects writes to memory areas that shouldn't occur, like those that happen in buffer overflow exploits, or when you write bad code that references out of bounds regions.

This was made when I was maintaining an IRCD (internet relay chat daemon), back in 1999.

I had forgotten about it then, but I came to realise it was useful for this startup I worked at -- making wireless speakers.

I was worried that someone would create a out-of-bounds code... the problem was the team lead at the time encouraged such practices.

The practise of half-allocating a struct, in order to save space, whilst still passing the struct completely on the stack was a bad thing, as the function being called doesn't know how much of the struct was allocated (since it wasn't a whole object), and thus could overwrite regions outside the allocated area.

This caused a world of pain, and inflicted random crashes, as well as weird problems due to it overwriting valid memory regions.

So ElectricFence/Flak Jacket was written into the memory allocator to detect such things.

I've since re-written Flak Jacket for Drudget, and it's far better performing than what I wrote for the company.

Again, this was years before libasan (address sanitizer) was made. From 1999, it would be two decades before libasan became the favourite tool for debugging broken code.

Improving deadlock detector -- making it fix deadlocks on the fly


Obviously one of the improvements that you could do if you had a deadlock detector, is fixing them on the fly before it happens.

If you recall, hooking mutex locks is necessary to create a graph for analysis. By doing so, you could just make the cyclic graph call a "big lock" which locks for the entire cyclic graph, thus preventing cycles, as it relies on the singular "big lock" instead, which wraps all the smaller locks inside the cyclic graph.

So that's what I made after finishing the deadlock detector. Another self-healing code.

Looking at snort (IDS - intrusion detection system), and making self-healing code from it


I looked at the various ways IDS's were used to log intrusions into systems. They would often log program crashes, with no way to counter them, whilst watching the process restart itself.

This probably allows a hacker to obtain information from the crash, such as pointer leaks, that they can use in subsequent attacks to exploit or override mitigations.

Or they could just brute force their way through mitigations, with some stack canaries only being 16-bits in effective length.

So I decided to write a ptrace() piece of code which debugs tracks the application, and picks up SIGSEGV (segmentation faults) and writes out the logs of what caused it to crash -- just like a typical IDS would do, except it filters it out based off patterns from previous inputs that also caused it to crash -- recognising patterns such as shellcode with only minor changes at the end (return instruction pointers being changed perhaps?), and creating filters which block/ban the shellcode from going through the next time.

I realise that subsequently, it could be strengthened with Generative-AI, to fix the problematic code at its source. Perhaps the source code had a buffer overflow, which would cause it to crash?

Given that the process could be run with Flak Jacket and the Garbage Collector and deadlock detector all built-in, it could mitigate almost all exploits, whilst still notifying the ptrace() monitor code AND still blocking/banning the inputs.

That is triple security: mitigate, log, and self-heal.

And with the added help of GenAI, self-mutating such that it looks like a living cell.


The future of Drudget


The future of Drudget is uncertain. I tried to get VC funding for it for the past year, and whilst I haven't been pushing for VC funding all that hard (I've only contacted 4 funds), I think the fact that I don't have any customers is really hitting me hard.

It feels like I need to shut it down before it's even ventured out on it's tiny footsteps.

I can imagine a world where Drudget's used everywhere -- from mobile phones to desktop PC apps, to servers (and cloud). All used to guard their software from broken/bad code written by human beings, which inevitably will be flawed, as we're imperfect beings, creating imperfect solutions.

Not sure that AI will generate the perfect solution either, as it's obvious that bad code needs to be reviewed, even if it has been fixed by GenAI.

So I'm not sure where this leads Drudget -- whether the software industry prefers fixing things manually, or whether cloud providers see value in saving money from support.

In the meantime...


In the meantime, I will be working on a computer game for ZZimps.

I've always wanted to publish a computer game. The problem is I have so many ideas for computer games that I can't do them all.

One of them is a stock market simulator -- for those interested in writing code that mimics a high frequency trader... it will be a pluggable simulator, which means the plug-ins allow other languages to be used -- as contesting the best high frequency trading code, we need to be language agnostic.

Another is a real-time strategy that is like rocks, paper, scissors, except it's with units that have obvious advantages and disadvantages. Currently I thought of using infantry, tanks, helicopters, but in reality, helicopters will be OP and own the entire game. So that's thrown out the window.

Another is a MOBA like game.

Another is a 2D-platformer/RPG similar to Maple Story.

I also have several maths (game theory) papers I want to publish. One involves Prisoner's dilemma, another is about Chess. I need to learn LaTeX, but I wish I could just write it in ASCII. LOL.

Using gdb

Using gdb I figured I'll write a mini-tutorial on how to use gdb, because there's not that many places where they teach you how to...