From: Laurent Malvert
Date: Sat, 1 Oct 2016 00:03:20 +0200
Subject: The Knuth's Challenge

Hello,

This is regarding your blog post on:
  https://www.gaxun.net/commentary/knuth-challenge/

I just wanted to tell you that, while we haven't tried to solve this
challenge (of which, to my shame, I was actually unaware), we did do a
Master's thesis on a similar subject with a friend in 2008, which meant to
design a way to perform a syscall-level recording of a system's activity
(in part or in full).
And to give credit where credit is due, most of the coding was Mickael's
(in CC).

The idea was to build a forensic analysis system allowing to record another
system's activity, which would then allow to:

 - perform a post-mortem analysis (e.g. troubleshooting or attack pattern
identification),
 - rebuild a physically damaged system by replaying it's archived history
(if all calls were captured).


Unfortunately the exported PDF for the presentations and thesis appear to
have been lost when the project was auto-migrated from the now defunct
Google Code Project Hosting to GitHub.

I've attached a copy of the thesis which I had saved on a drive, and that I
think was the one we released. The presentations, however, are not on the
archives I can put my hands on right this minute.
I found at least one of them that's been crawled and copied by one of these
online-viewers:
http://www.slideserve.com/ryo/lemona-linux-enhanced-monitoring-architecture
Not sure it was the latest version though.

You can also find the source and some additional details on this repo
(master and wiki branches imported from Google Code PH):
  https://github.com/laurent-malvert/lemona


Unfortunately we never pushed that experiment further, because, well...
life.


Anyways, not that I think our little endeavor was or is of that much
scientific significance, but I just found it may answer your specific
requests of:

> I've tried searching the web a few different times in the last couple
years to see if anyone has responded to the challenge. So far, I've come up
with basically nothing. If you know of any published results from this type
of study, please share!
>
> There are definitely people who profile their applications, generate
flame graphs, and step through line-by-line with a debugger. What about the
entire system, though? Is there a utility I can use to log every
instruction performed in one second for an operating system running on bare
metal? Can it be done with an emulator like QEMU?

and:

> I'd love to hear about a successful test. Or we could work on doing one
together. If you have ideas, related experience, or just want to say hello,
you can email me at [...]


Additionally, you may want to read the literature review part of the
thesis, as we were not the only ones working on similar systems, with
varying levels of success or granularity in the recordings. As you
mentioned, many do application level profiling or probing, but a few do
system-level probing as well. I don't know (but haven't looked for) other
projects that would go or have gone "lower" or closer to the metal. We
stopped as syscall which seemed satisfying enough for us, but I I think
that'd still be a step closer above Knuth's objective. Though from there
you could maybe (theoretically and if you know your arch well) map to the
sequences of machine code and down to hardware activity.


Hope this is of interest for you or can help you.


Cheers,

-- 
Laurent Malvert

==========

From: Gaxun
Date: Fri, 30 Sep 2016 23:26:19 -0500
Subject: Re: The Knuth's Challenge

Laurent,

This is great!

I read the introduction and a few pages throughout the document you
attached, but I won't be reading the whole thing, at least not tonight.
Right now I'm actually focusing on producing more posts for my site rather
than stopping to work on each idea.  I'm not sure if I will actually
attempt this in any way myself.  I know it would be a big project.

I'm planning on producing an addendum to accompany the original post,
containing a summary of the comments it generated, prior work shared, and
new questions raised.  Your message was very thorough and I plan to include
a summary of it in that upcoming post.

I'm wondering if you would prefer to be credited by name, or just as
"someone' who shared their Master's work with me.  I don't want to offend
if I include personal details against your wishes, especially since email
is seen by some as a private transaction.

Thanks,
Gaxun