Paul Karger: Mr. High Assurance

Abstract

Paul A. Karger (d. 2010) spent almost forty years building computer systems intended to survive professional attackers, and proving that everything else would not. As a young Air Force lieutenant, fresh out of MIT, he co-wrote the 1974 Multics vulnerability analysis that predicted the self-replicating compiler backdoor Ken Thompson later made famous in “Reflections on Trusting Trust”. At Digital Equipment he led the VAX security kernel, one of the few systems ever engineered to the Orange Book’s highest class, A1. DEC canceled it on 1 March 1990 with the finish line in sight. Colleagues called him “Mr. High Assurance”. The market never bought what he built, and the malware epidemic of the following decades unfolded roughly as his 1974 report said it would.

The Multics Penetration

Karger earned SB, SM, and EE degrees from MIT, where he worked on the Multics team as an undergraduate. In 1972 he joined the US Air Force’s computer security branch at the Electronic Systems Division, Hanscom Field, Massachusetts, as a newly commissioned second lieutenant. Steve Lipner, then at MITRE, remembered him as “a very eager freshly minted second lieutenant”.

The assignment that defined his career started as a procurement dispute. The Air Force wanted security enhancements to Multics before running it at the Air Force Data Services Center in the Pentagon. Honeywell, the vendor, declined: Multics was already sufficiently secure. So Karger and Roger Schell set out to prove otherwise with a sanctioned penetration test of the most secure commercial operating system of its day.

They broke it thoroughly. Working under strict ground rules (no real harm, exploit code kept encrypted and locked in a safe rated for TOP SECRET material, publication delayed until every hole was repaired), they demonstrated that the flaws mattered less than what a professional attacker could do with them: install malicious software that survives. As a proof, they planted a trap door in a routine of the MIT development system. Honeywell’s own distribution process then shipped it, unnoticed, to the Multics processor at the Pentagon. The trap door was deliberately neutered (it needed a one-instruction change to become active) and was found only about a year after the report appeared, during a security audit at a General Motors site.

The work had its slapstick moment. Copying working exploit code from the Multics system at Rome Air Development Center to MIT’s machine, Karger made a typo. When he ran it, MIT’s Multics crashed outright. The operations staff never found a smoking gun, and the test continued.

The findings were published in June 1974 as Multics Security Evaluation: Vulnerability Analysis (ESD-TR-74-193). Its bottom line: penetrate-and-patch cannot work, because testing can only show the presence of vulnerabilities, never their absence. A system exposed to motivated professional attackers must be restructured around a small, verifiable security kernel. The report became the founding document of what the field later called high assurance.

The Footnote Thompson Was Looking For

Buried in the report was a countermeasure analysis that aged better than almost anything else written that decade. Recompiling the operating system from source, the authors noted, would not remove a well-placed trap door, because the trap door could live in the PL/I compiler itself: it could insert malicious code whenever it compiled the operating system, and preserve itself by recognizing when it was compiling the compiler.

Ten years later, Ken Thompson built exactly this and described it in his 1984 Turing Award lecture Reflections on Trusting Trust. Thompson attributed the idea to “an unknown Air Force document” and asked for a better citation. The document was Karger and Schell’s report; they sent him a copy after the lecture was published. The Orange Book’s A1 class later required that new system versions be generated from source with a compiler kept under strict configuration control, a requirement that traces straight back to that paragraph (see Secure by Design).

The report’s constructive side also bore fruit. Karger was, in Schell’s words, the “undisputed technical authority” for Project Guardian, the ARPA/Honeywell effort to harden Multics that followed. Its results fed two evaluated products: Multics with mandatory access controls, rated Class B2 in 1985 and installed at the Pentagon and at NSA’s Computer Security Center, and Honeywell’s SCOMP, the first system rated A1. The purer research goal, a full security-kernel Multics, died by decree: in August 1976 Air Force Systems Command ordered the work stopped.

The VAX Security Kernel

Around 1980 Karger left the Air Force for Digital Equipment Corporation, where he founded the Secure Systems Department and prototyped a security-enhanced VMS with mandatory access controls, which reached customers years later as the SEVMS product. The bigger project was conceived, by his own account and Lipner’s, in a Mexican restaurant in Palo Alto the night after the 1981 IEEE Symposium on Security and Privacy: a virtual machine monitor for the VAX architecture built as an A1 security kernel.

The VAX Security Kernel was a hypervisor a decade before the word was common. It ran on stock VAX 8530 to 8810 processors (with modified microcode to make the architecture virtualizable) and created isolated virtual VAXes, each running an unmodified VMS or ULTRIX-32 operating system, each labeled under Bell-LaPadula secrecy and Biba integrity models. The kernel team ate its own cooking: on a typical day about 40 engineers did all their development inside virtual machines on a single VAX 8800. In external field test at customer sites the system stayed up for nearly three weeks at a stretch under production load, unheard of for a new operating system. Karger worked through the A1 assurance machinery, formal top-level specification, proofs, covert channel analysis (his 1991 paper on timing channels hidden in disk arm optimization is a small classic of paranoia), configuration management, trusted distribution.

Mid-project, after the kernel first booted VMS in a virtual machine on a VAX-11/730, Karger married Carol Lynn and left for the University of Cambridge to write a PhD (Wolfson College, dissertation submitted March 1988: Improving Security and Performance for Capability Systems, proposing hardware-supported capability architectures that could enforce lattice security policies and resist Trojan horses). He was one of the few people to publish serious work in both the kernel and capability schools of secure system design.

On 1 March 1990, Digital formally canceled the VAX Security Kernel. The retrospective paper Karger and his co-authors published in 1991 records the epitaph: the project was “considered a technical success”, there was “significant customer demand”, and the exact reasons for cancellation remained confidential. It was never submitted for the A1 evaluation it was built for.

After Digital

Karger moved on as security architect of the Open Software Foundation and later researched wireline and wireless telephone security at GTE Laboratories. He spent his last years as a Research Staff Member at IBM’s Thomas J. Watson Research Center, holding 13 patents in computer security. There he led Caernarvon, a high-assurance smart card operating system aimed at Common Criteria EAL7, the highest defined evaluation level, and the first smart card OS to use hardware protection to separate the operating system from applications. He also worked on automated test generation for Common Criteria evaluations and, in a 2007 paper, on “fuzzy MLS”, a model that replaced binary allow/deny decisions with quantified risk.

In 2002 he and Schell revisited their Air Force work in the ACSAC classic paper Thirty Years Later: Lessons from the Multics Security Evaluation. The verdict was unsparing: security had gotten worse, not better. Few fundamentally new vulnerability classes had appeared since 1974; the difference was that commercial systems of 2002 did not even include the protections Multics had in 1972, let alone the security kernel the report had called essential. The buffer overflows plaguing the internet were largely impossible in Multics, whose PL/I string handling and hardware permission bits blocked the standard attack.

Karger died in September 2010. That December the ACSAC conference, home of his most-cited paper, gathered to remember him, and Hilarie Orman’s obituary in the IEEE Cipher newsletter predicted that future generations would keep drawing on his work. In 2016 he was inducted posthumously into the National Cyber Security Hall of Fame.

Dead End: High Assurance as a Product

The school of security Karger personified, formally specified kernels evaluated at A1 or EAL7, failed in the market, and he lived every stage of the failure. The Multics kernel was stopped by the Air Force in 1976. SCOMP earned its A1 rating in 1985 and sold in the dozens. The VAX Security Kernel was canceled in 1990 despite working. The pattern had a simple economics: an A1 evaluation took years, the rating applied to one frozen version on one hardware generation, and customers outside a narrow defense niche bought features and speed instead. The 1990s went to networked commodity systems with security retrofitted afterward, and the resulting malware wave kept Karger’s 1974 report current for fifty years.

The ideas survived the products. Virtual machine isolation, the core of the VAX kernel, returned as the foundation of cloud computing. Common Criteria evaluation, which Karger helped automate, still gates the smart cards in payment and identity systems. And the report’s central demand, a kernel small enough to verify, was finally met in 2009 when the seL4 microkernel received a machine-checked proof of functional correctness.