It's taken me some time to draft a reply, for which I must apologize, but since Jeremy Epstein mentioned me by name, I must respond. This is actually responding to four messages from Jeremy Epstein, Larry Kilgallen, and Jerry Leichter.
>From: "Epstein, Jeremy" <[EMAIL PROTECTED]> >Subject: Re: [SC-L] GCC and pointer overflows [LWN.net] > >Ken, a good example. For those of you who want to reach much further >back, Paul Karger told me of a similar problem in the compiler (I don't >remember the language) used for compiling the A1 VAX VMM kernel, that >optimized out a check in the Mandatory Access Control enforcement, which >separates information of different classifications (*). [For those not >familiar with it, this was a provably secure kernel on which you could >host multiple untrusted operating systems. Despite what some young-uns >seem to think, VMs are not a new concept - they go back at least three >decades that I know of, and possibly longer. The A1 VAX effort ended >roughly 20-25 years ago, to give a timeframe for this particular >compiler issue.] I've discussed this anecdote with Jeremy, and unfortunately, I don't remember that particular optimization problem having happened on the A1 VAX VMM. It might have been on another system and confused with the VAX VMM. We did have a compiler optimization problem in zeroing shadow page tables when switching VMs. One line of PL/I code compiled into a horrendously slow loop. I had to re-write one line of code into about 10 lines of very cryptic code (plus a full page of comments, explaining it) to trick the compiler into generating the right block move instructions to do the job. I was trying to avoid an assembler subroutine, because the call/return overhead would have also been a problem here. Virtual machines do indeed go more than 30 years back. The earliest papers on virtual machines are these. The first paper is about CP/40, the direct ancestor of CP/67 which was the first commercially available VMM. CP/40 was done at the IBM Cambridge Scientific Center on a 360/40 with a custom virtual memory box. The second paper is about an even earlier virtual machine monitor done on a heavily modified IBM 7044X here at Watson Research. The 7044x was a 7044 with an added custom virtual memory box. The term "virtual machine" was coined by the 7044X people. 1. Lindquist, A.B., R.R. Seeber, and L.W. Comeau, A Time-Sharing System Using an Associative Memory. Proceedings of the IEEE, December 1966. 54(12): p. 1774-1779. 2. O'Neill, R.W. Experience using a time-shared multi-programming system with dynamic address relocation hardware. in Proceedings of the 1967 Spring Joint Computer Conference. 18-20 April 1967, Atlantic City, NJ: Vol. 30. Thompson Books. p. 611-621. >From: ljknews <[EMAIL PROTECTED]> > >At 1:00 PM -0400 5/1/08, Epstein, Jeremy wrote: > >> Ken, a good example. For those of you who want to reach much further >> back, Paul Karger told me of a similar problem in the compiler (I don't >> remember the language) > >VAX Pascal, before VMS was on Alpha (and long before Itanium). > >-- >Larry Kilgallen > Actually, the language choice for the VAX VMM was more complex than that. When the project started the VAX PASCAL compiler version 1 was not suitable for systems programming use. As a result, we wrote the VMM prototype entirely in VAX PL/I. About the time that the project moved from a research prototype to a full product development, the VAX Pascal version 2 compiler became available, and that compiler produced much better code and had extensions needed for systems programming (such as conformant arrays). Since PASCAL had stronger typing than PL/I, we switched to PASCAL for all new code, planning to re-write the PL/I into PASCAL eventually. In retrospect, we should have just stayed with PL/I, because the re-write never happened. We briefly considered using C, but rejected it for two reasons. The first reason was all the well-known lack of safety issues, but the second reason was that the lack of compiler known lengths not only led to security issues, but ALSO led to performance problems. Although the VAX PL/I and C compilers used the same common code generator, the PL/I compiler generated better code, because the compiler knew more about the size of data structures and could do better optimization. >From: "Leichter, Jerry" <[EMAIL PROTECTED]> >The VAX VMM effort died with the announcement of the Alpha, in late 1992 >- though obviously the death was decided internally once the move to >Alpha was decided, which would have been somewhat earlier. The origins >of the VAX VMM effort date back to the early 80's. These dates are not correct. The A1 VAX VMM effort started just after the 1981 Oakland conference, as a back of the napkin design in a Mexican restaurant in Palo Alto. The prototype was running on a VAX-11/730 in 1984. (That included changing the VAX instruction set to be virtualizable.) The product version went into highly successeful external field test in 1989. The product announcement was supposed to happen at the 1990 Oakland conference. The paper at the conference was disguised as a report of research results to avoid prematurely revealing the product. The product was cancelled, primarily due to internal corporate politics, on Feb 14th, 1990, which the development team promptly labeled the 2nd St. Valentine's Day massacre. As a result, the Oakland paper remained just a report of research results. The Alpha was not the cause of cancellation. Quite the contrary, we had specifically designed the Alpha to better support secure virtual machine monitors than could be possible on the VAX. Details are finally published here: 3. Karger, P.A., Performance and Security Lessons Learned from Virtualizing the Alpha Processor, in The 34th Annual International Symposium on Computer Architecture 9-13 June 2007, Association for Computing Machinery: San Diego, CA. p. 392-401. > >As best I can recall, the VAX VMM kernel was written almost entirely in >PL/I. (Why? Because the main alternatives available at the time were >assembler and C - way too open-ended for you to be able to make useful >correctness assertions - and Pascal, which even in VMS's much extended >version was too inflexible. There were almost certainly a few small >assembler helper programs. Before you defend C, keep in mind that this >is well pre-Standard, when the semantics was more or less defined by "do >what pcc does" and type punning and various such tricks were accepted >practice.) > As I discussed above, the VMM kernel was about 1/2 in PL/I and 1/2 in PASCAL V2. C was explicitly rejected for both security AND performance reasons. >I know from other discussions with Paul that it was understood in the >high assurance community at the time that, no matter what you knew about >the compiler and no matter what proofs you had about the source code, >you still needed to manually check the generated machine code. >Expensive, but there was no safe alternative. So any such optimizations >would have been caught. > > -- Jerry > >From: ljknews <[EMAIL PROTECTED]> > >My understanding is that DEC pulled the plug on the VMM project >(called SVS) during a successful field test when they discovered >that while the NSA division that handled trusted computing was >really gung ho about the project, none of the government units >which might actually make purchases were interested in multilevel >secure machines. Remember that the MicroVAX II was available at >the time and from many perspectives (including that of taxpayers) >it was a lot nicer to use separate machines for various security >classifications. This is a secure coding mailing list, and not the place to discuss how to market security. I will just say that this was the excuse used for cancelling a product that actually had a very profitable market niche. The root causes of the cancellation were neither technical nor profitability. Lots of DoD organizations had (and still have) needs for sharing multiple levels of classified information, and separate MicroVAXes would not solve those problems. For that matter, neither would pure isolation kernels, such as MILS. See this paper for details: 4. Karger, P.A. Multi-Level Security Requirements for Hypervisors. in 21st Annual Computer Security Applications Conference. 2005, Tucson, AZ: IEEE Computer Society. p. 240-248. URL: http://www.acsa-admin.org/2005/papers/154.pdf Getting back to the original question of compilers missing security checks in the code, there was a case on Multics where the argument validation code didn't anticipate the possibility of the argument list containing pointers with the increment and tally option turned on. What that accomplished was that every time the pointer was used, it pointed to a different place. Knowing that the argument validator touched the pointer N times, I carefully set up the increment and tally such that N references were to locations that the user had proper write permission to (therefore passing validation) and the N+1st reference done by the actual code of the program (as opposed to the validator) pointed to something the user did NOT have write permission to, and the operating system thus implemented a function to patch any location of memory - more than enough to take over the whole system. This was on the GE-645 processor, where argument validation was done by software. The follow-on Honewell 6180 processor had hardware argument validation which would defeat this trick. - Paul _______________________________________________ Secure Coding mailing list (SC-L) SC-L@securecoding.org List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l List charter available at - http://www.securecoding.org/list/charter.php SC-L is hosted and moderated by KRvW Associates, LLC (http://www.KRvW.com) as a free, non-commercial service to the software security community. _______________________________________________