Beware the insiduous Penetrator, my son!

Excerpt from "MULTICS SECURITY EVALUATION VULNERABILITY ANALYSIS"

   Paul A. Karger, 2Lt, USAF
   Roger R. Schell, Major, USAF

   June 1974

   Approved for public release;
   distribution unlimited.

Pg 51.

[ ... ]

Two classes of trap doors, which are themselves source or object trap
doors are particularly insiduous and merit discussion here.  These are
the teletype string trigger trap door and the compiler trap door.

[... one paragraph describing the teletype trigger trap door omitted ...]

Pg. 52

It was noted above that while object code trap doors are invisible,
they are vulnerable to recompilations. The compiler (or assembler)
trap door is inserted to permit object code trap doors to survive even
a complete recompilation of the entire system. In Multics, most of the
ring 0 supervisor is written in PL/1. A penetrator could insert a trap
door in the PL/1 compiler to note when it is compiling a ring 0
module. Then the compiler would insert an object code trap door in the
ring 0 module without listing the code in the listing. Since the PL/1
compiler is itself written in PL/1, the trap door can maintain itself,
even when the compiler is recompiled. (38) Compiler trap
doors are significantly more complex than the other trap doors
described here, because they require a detailed knowledge of the
compiler design. However, they are quite practical to implement at a
cost of perhaps five times the level shown in section 3.5 [<$4,000,
See Pg. 57]. It should be noted that even costs several hundred times
larger than those shown here would be considered nominal to a foreign
agent.

There is also a variant on the compiler trap door called the
initialization trap door. Here, the system initialization code is
modified by the penetrator to insert other trap doors as the system is
brought up. Such trap doors can be relatively invulnerable to [page
break] detection and recompilation, because system initialization is
usually a very complex and poorly understood procedure.

------------------------------------------------------

(38) This type of trap door does not require a higher level
language. Entirely analogous trap doors could be placed in an
assembler.

====================================================

Downloaded from:
 
http://seclab.cs.ucdavis.edu/projects/history/papers/karg74.pdf

Accessed 25 August 2014.

PDF 558901 bytes,
SHA1 c/s: a77bb61b2a65a337506a72ec98fe8d546f830994

A Funny way to Earn a Living

There seem to be quite a few foreigners in La Paz, who earn a living of some sort by doing tricks in front of cars waiting for traffic lights to turn green. I saw a guy today, who had learned how to spin a ball balanced on the end of a wooden-spoon he held in his mouth whilst juggling three skittles. After 5 seconds of this, the ball fell off the end of a stick, and then he flipped his hat off the ground with a foot, and caught it, and bowed and smiled to his audience. "What a weird and pointless skill!" I thought.

Then I realised that I had been doing something weirder and even more pointless for the past few days. I had been learning how to use GNU autoconf/automake/autoheader etc. again. I call them the GNU auto4ck tools. Really, after fifteen years of this crap, we ought to admit defeat and try again. But we don't. Who said enough monkeys banging away on type-writers couldn't write the works of Shakespeare? If a few thousand monkeys banging away on typewriters for a just a couple or three decades can make the GNU software suite, why not the works of Shakespeare too?

Now if we all started thinking instead of just banging away on our typers, then we might be able to make better software. But we haven't time to think, because we're so occupied looking for obscure and stupid bugs introduced by using a 'language' which, for example, can't detect an 'error' caused by putting a space between the name of a function and the parentheses containing its arguments. Or by indenting the arguments to a nested if/then/else block, in an attempt to make it more readable. I despair!

But the upshot is, maybe Red October will build on Linux boxes other than my own. Maybe someone will try cloning the repository now, and typing

cd src  
autoreconf -vif

then

./configure --help

and following the instructions.

Writing Assembler using Standard ML Functors

Here is an example of something important which is seldom mentioned in Functional Programming circles. One can use Standard ML functors to produce type-checked, efficient assembler code. For example, here is a functor implementing assembler primitives for CAML byte-code machines. The same functor implements code for three different ABI representations of "machine words," which are instances of the Standard ML basis signature Word. The Functor AbstractMachineWord effectively composes the assembler code from JIT instruction-generating routines which are in turn composed by other functors. In this instance, for example, the parameter WordEnc (which is another structure with a defined interface like this one) is something like  that produced by the functor VectorSliceWordEnc.sml which uses other assembler code composed by the code-generating primitives defined in PrimEnc.sml which, you might be pleased to hear, is a first-class structure, also with a defined interface. This structure is fixed in terms of the primitives implemented by the 'foreign function interface' binding to the GNU lightning JIT code-generating library. , and it implements only the  CAML ABI. But VectorSliceWordEnc.sml is just one of the possible representations of machine words in memory, and another is ArraySliceWordEnc.sml. And this uses the same primitives, but results in a different set of assembler functions.

There are also other possible representations of the ABI calling conventions, so we could use the same AbstractMachineWord functor to generate primitives for GNU guile, Python, or Ocaml, just by writing a different version of PrimEnc.sml. Provided this conforms to the interface signature defined in PrimEnc.sig, it will work.

The remarkable thing about these functors is their reliability. It is actually easier to write assembler this way than it is to write it ad-hoc. You don't have to take my word for it, you can try it yourself. The whole repository is available for download and/or forking.

Hindley-Milner Type Inference

A few years ago I lost access to my web site and the Proof-toys people very kindly offered to host this description of Hindley-Milner type inference, including the brilliantly written 1982 paper by Damas and Milner, Principal Type Schemes for Functional Programs, describing the soundness and completeness proofs. There is also a file of the purely functional (but nevertheless buggy! See below.) Standard ML implementation. I am posting this here just to increase the number of links to it.

There are a couple of errors. One is a serious misapprehension I was under. Despite having implemented the algorithm in (apparently working) code, I still thought that resolution happened under universal quantification. That is not so. All quantifiers are stripped before resolving the type-schemes. The mistake is in the last-but-two paragraph on page 12 where I state:

If the assumptions include a type-scheme for x, then the result is simply the generic instantiation of the type-scheme to new variables. Otherwise the algorithm fails.

The other error is in the implementation of capture-avoiding substitution in the function tssubs: it fails when there are free variables in the assumptions Gamma, because an over-enthusiastic optimisation means it doesn't rename below a binder of the variable being alpha-converted. Capture-avoiding substitution is a simple idea, but a bit tricky to implement efficiently, and you probably shouldn't try to implement it in just 22 lines of code!

Thanks for BZIP2

Here's a mail I just sent to the author of the Bzip2 tools.

"If you can be bothered, please email me to say you've got a copy. It's nice to know where this stuff gets to."

Everywhere, I think is the answer, except the default OpenBSD distribution ... which is why I'm fetching source.

Thanks for making bzip2. I have always appreciated it. I used to take tea with David Wheeler every day at Cambridge. I spent a decade at the Computer Laboratory, for some sins I must have committed in a past life, ... but tea with David Wheeler never seemed like punishment. He didn't have a lot to say, but what he did say was always pretty interesting.

He used to use bzip2 as his spam filter. Did you know that? He used it to measure the information content of his incoming messages M as the change in entropy between his "verified as spam" archive S and S+M. The change in entropy was just the difference in the size of the bzip2 compressed files. I was a sys-admin and had to help him once with some technical fiddling to get the mail message processing done automatically.

He used to think about physics in terms of information and entropy too. He had a Machian perspective. He told me once that a better physical theory was one which explained the data more concisely. In a sense he viewed physical theories as programs which reproduced the observed data from a compressed expression of the mechanical cause, i.e. the program. This was essentially Mach's view. I didn't ask David whether he took Mach to Mach's extreme of saying that there was no truth independent of our ability to concisely describe phenomena.

So there, I hope this amuses you, and I hope you feel good about all that effort you put into making bzip2 a supremely reliable workhorse of the Free Software revolution.

And do you know David carried on working right to the end. Despite failing eyesight and heart. He died in the bicycle shed seconds after arriving by bike for work at 8am on a cold winter's day.

Best wishes,
Ian

On Feminist Genealogy

The tradition of women adopting the surname of their husband is a strange one. In Spanish cultures the custom is far more symmetric. I don't exactly know what it is, but it is roughly that a girl takes the surnames of both her father and mother, and takes that of the mother first. And the boys take both too, but the other way around. So for example, El Che was named Ernesto Rafael Guevara de la Serna, Guevara was his father's surname, and de la Serna was from his mother. But it is recorded that his father's mother's name was Lynch. This is because Lynch, was an Irish grandmother of his. But her surname would have been passed down to all her female descendents, which means that in Spanish speaking countries women have the same 'genealogical continuity' as men.

The tradition of women adopting their husband's married name is a pernicious one. It basically means that in these cultures it is practically impossible for a woman to know her ancestry! Humanity is not a tree, going back to Adam and Eve, it is really one whole river, and within it we can trace two streams. There is a feminine stream and a masculine one. And the feminine stream is the more fundamental one. As I've said before, men and women are different: the mechanics of human Biology are such that women are all practically the same living organism, which exists in many different places at any one time. Men are different, they don't have this physical continuity from father to son because there is a fourteen-year discontinuity between the sperm which fertilises the ovum in the mother and the sperm which will fertilise the ovum in the mother of that woman's grand-daughter. Men are like the flowers on a tree, they serve just to equilibrate the genetic stream. So men are like a distributed data storage facility. They each store up a bit of genetic flexibility and can transmit it from one part of the whole Global Plant to another part.

The male genome has a tiny amount of information compared to the mitochondrial genome of the female. The mitochondrial genome is much more stable. It is through mitochondrial DNA that we can trace migration of human populations over centuries, such as those Jews who became black and wound up living in Masvingo and keeping the ark of the covenant in Zimbabwe!

And the male genetic heritage is often doubtful. Men cannot easily know who are their children, but no woman is likely to give birth without knowing about it! If you want to do a little interesting research project, then look up the life of Frederick, Lord North, and George III, and look up Thackeray's Lectures on the Georges which Dodgson mentions in his "Life and Letters," and read about Sir Isaac Brock, and George IIIs support of Charles Stuart in exile in France.

I personally think the probability that George III was really the son of Frederick Prince of Wales is far less than fifty percent. And so I think that the probability that the English Royal Family are in fact bona fide is far less than fifty percent. That doesn't mean I think they shouldn't be the Royal Family, but I wish people had the courage to discuss this openly. You won't find anyone asking this question on any public forum. Goodness knows why though, because if you actually read around any bit of history a bit you find a lot more questions than you find answers. And note how beautifully polished and well-researched is the Wikipedia page on George III. It couldn't have been done better by an equerry to the Prince of Wales!

Now back to the main point of this e-mail: this uncertainty of the male genetic line, coupled with the fact that in English tradition (or is it wider than that?) the more evident feminine genetic stream is rendered practically untraceable in historical records, means that in reality none of us really knows our true cultural heritage. For example, we imagine we know that the Grants mostly originated from Scotland. But we don't really know that. All we know is that the male line can be traced back to Scotland. What do we know about the mothers of all those men though? Absolutely nothing, they aren't 'real Grants'. Some of them could have been Greek, or Finnish, and some very probably were. That all these different women from different parts of the world all happened to marry male descendents of one old man Grant who lived in Scotland is just a long series of accidents. Or could it be the other way around?

If you want to test this, then try to find the statistics. Who in the English speaking world, has a greater interest in Genealogy, men or women? Do a survey amongst your friends. How many women can trace their feminine ancestry? I recall trying to find out about the Clarkson family. I was interested to know if there was any connection with the anti-slavery campaigner who has lent his name to Clarkson Rd in Cambridge, which is the address of the Cambridge Centre for Mathematical Sciences. I found it almost impossible to make connections amongst the publicly available data. Because I was trying to connect the surname of a male stream with the practically non-existent female stream. I realised later that the coincidence of the surnames is totally irrelevant. "Clarkson," being an English surname, is an essentially masculine phenomenon: it is solely the male genetic line, and has nothing whatsoever to do with the women. I am told the Church of Mormon has one of the biggest genealogical databases in the world. I don't suppose that it is run entirely by Mormon women, but go on, someone surprise me!

Now, by using the Internet, we could reconnect this one river. But it will only work if we all share all our family heritage data. And I mean everyone in the world. This is why no-one should use these proprietary genealogy databases. There is technically no necessity for that: we just need a well designed meta-data catalogue describing the different concrete representations of genealogical data. The basis for this is all laid out in the single most impressive example of systems engineering I have ever come across, which is the OSI's standard called ASN.1 which stands for Abstract Syntax Notation. This is just one example of one application of ASN.1, but there are many, many others covering all types of communication and computation. And the work I have been doing recently is towards a generic system for editing abstract syntax notation.

This cannot be done by any one private company for profit, because it is something that will never be profitable for any particular organization: it will only be profitable for the whole of humanity. That is the unfortunate situational logic we constantly have to fight against: what is good for the whole Earth is never going to be financially profitable for any particular person or group of people. So while capitalism is the fundamental basis of the Global Economy, the future of the Earth, and the whole of humanity, is more than a little doubtful.

Of course, if everyone in the world did share their genealogical data then we would all know with near certainty, who really was the father of George III, and no doubt there would be some other potentially embarrassing paternity conclusions. So I don't think it is entirely an accident that the word Genealogical has ancient Greek roots of Genus and a-logical, which is a privative alpha: it means illogical or incomprehensible, or without reason.

Google, Going, Gone to Pot?

Well, I heard that in the USA it is a domestic industry worth almost as much as Microsoft. Pot, I mean. All that money must be coming from somewhere, ... ad clicks, or the CIA, funding projects to discourage Americans from thinking about anything at all.

I wanted to upload my Red October patch for Moscow ML, but Google project hosting has moved the downloads function to Google Drive, and the latter doesn't work for me. I suppose because my ancient FireFox has bit-rotted. The more fancy Google's web user interfaces get, the less well they work. I suppose I am expected to get a Windows licence and download Google Chrome to read e-mail.

But how hard is it to implement an HTTP file-upload page, ... I am sure I did it, about ten times, ... It's half an hour's work, at the most. But that wouldn't work for the cloud, ...

Maybe it's because they are pissed-off at my insinuating that they, together with Microsoft, Skype and FaceBook are wide-open to the biggest class-action lawsuit in legal history, for abusing public resources.  What keywords do I need to put in here to get a greedy lawyer interested? Is "greedy lawyer" and "biggest class-action lawsuit in legal history" appearing twice enough? Where are the ambulance-chasers when you need one ...