Newsgroups: comp.risks
X-issue: 4.94
From: decvax!utzoo!henry@ucbvax.Berkeley.EDU (Henry Spencer)
Date: Sun, 31 May 87 00:00:23 edt
To: ucbvax!CSL.SRI.COM!RISKS
Subject: Risk of Inappropriate Technology to Prevent Password Overwrite

>   The particular error cited by Bill Young could not have happened if the
> implementation had been in a language such as PL/I or Ada, where
> over-running the bounds of an array is a required run-time check...

I'm not an Ada aficionado, but my recollection is that every PL/I compiler
I've ever seen has a turn-checks-off option, and usually it's the default.
The reason is clear:  such checks are expensive, particularly with a naive
compiler that can't eliminate many of them at compile time, and the overrun
condition is rare.

> Such checks are clearly not new technology, since Multics (written in PL/I)
> has been doing such for over 20 years.  Nor is the technology new to
> hardware, since the Burroughs B5500-series and MCP (written in Algol) has
> also been checking for a similar period.

The distinguishing feature here is that both Multics and MCP are running on
special hardware.  The reason that these are relatively unpopular systems,
while Unix and C are everywhere, is that the latter will run efficiently on
almost anything.  As we all know, many people will trade off safety for
performance any day.  As is less widely appreciated, this is not necessarily
a foolish thing to do -- it depends on the application.  One negative aspect
of having hardware and languages that enforce checking is that you have no
control over the tradeoffs.

My personal conjecture, not yet verified by experiment, is that with a
cooperative language and a reasonable amount of intelligence in the
compiler -- more than most current compilers have, mind you -- something
like 90% of the run-time checks could be eliminated at compile time, and
about 90% of the remainder could be eliminated by reprogramming that would
make the program clearer to the compiler (and incidentally to humans) while
leaving efficiency unaffected.  The remaining 1% might require a way to tell
the compiler "believe me, it's right", but otherwise the need for a run-time
check could be made a fatal compile-time error.  Result:  safety with no
efficiency penalty.  Trouble is, verifying this conjecture would require
building such a smart compiler, a sizable project.  Maybe next year...

Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,decvax,pyramid}!utzoo!henry

Newsgroups: comp.risks
X-issue: 4.96
From: decvax!utzoo!henry@ucbvax.Berkeley.EDU
Date: Sat, 6 Jun 87 02:54:42 edt
To: ucbvax!CSL.SRI.COM!RISKS
Subject: Run-time checks

I should clarify a couple of points in my previous contribution.  Several
people have pointed out IBM's internal PL.8 compiler, which does generally
resemble what I was thinking of:  it works quite hard to determine whether
run-time checks are really needed, and succeeds in eliminating most of them.
It typically manages to bring the run-time-check overhead down to one or
two percent, sometimes to zero.  (PL.8 has not been publicized much, but
there are a couple of papers on it in the Sigplan 82 compiler symposium.)

My notion was a little different, though:  the compiler should *never*
generate a run-time check; if a run-time check is necessary anywhere, and
the programmer has not explicitly overridden that particular check in that
particular place, this should be considered a fatal error and code generation
should be abandoned.

The reasons behind this are two.  First, the occurrence of a run-time error
is almost certainly a symptom of a bug; programs should be more careful.
It seems better to flag such bugs at compile time, when it is convenient
to do something about them.  Second, since the actual error will generally
show up at some remove from the underlying bug that caused it, it is really
very difficult to do anything intelligent about it after the fact, barring
global recovery methods like recovery blocks.  (This is a major reason why
programs should avoid generating such errors.)  Dying with a core dump is
not acceptable for e.g. an air-traffic-control program.  It seems wise to
head off such errors in advance.

Clearly, it is not realistic to expect a compiler to eliminate all run-time
checks from arbitrarily complex programs.  That's more a job for a theorem
prover, which isn't practical as a routine programming tool for normal
applications just yet.  But:  programmers do not write arbitrary programs.
My conjecture -- which PL.8 strengthens but does not prove -- is that modest
intelligence in the compiler, plus some willingness to clean up code to make
it clearer, would reduce the "compiler can't be sure about this one" cases
to an occasional annoyance that could be handled by manual overrides.

				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,decvax,pyramid}!utzoo!henry