'A few years ago [~1991] the Computer Science Department at
Carnegie-Mellon University regularly ran a small programming contest
for its incoming graduate students.
[...] in one particular year it was very simple. Contestants had to
read a file of numbers and print the average. There were only two
rules:
- The program had to run as fast as possible.
- The program had to be written in Pascal or C.
The rival programs were grouped together and submitted in batches by a
faculty member. Students could submit as many entries as they wished;
this encouraged the use of nondeterministic probabilistic algorithms
(algorithms that would guess at certain characteristics of the data
set and use the guess to obtain faster performance). The golden rule
was that the program which ran in the shortest amount of time won the
contest. [...]
The data file contained about 10,000 numbers, so assuming it took a
millisecond just to read and process each number (about par for the
systems at the time), the fastest possible program would take about 10
seconds.
The actual results were very surprising. The fastest program, as
reported by the operating system, took -3 seconds. That's right--the
winner ran in a negative amount of time! The next fastest apparently
took just a few milliseconds, while the entry in third place came in
just under the expected 10 seconds. Obviously, some devious
programming had taken place, but what and how? A detailed scrutiny of
the winning programs eventually supplied the answer.
The program that apparently ran backwards in time had taken advantage
of the operating system. The programmer knew where the process control
block was stored relative to the base of the stack. He crafted a
pointer to access the process control block and overwrote the
"CPU-time-used" field with a very high value. The operating system
wasn't expecting CPU times that large, and it misinterpreted the very
large positive number as a negative number under the two's complement
scheme.
The runner-up, whose program took just a few milliseconds, had been
equally cunning in a different way. He had used the rules of the
competition rather than exotic coding. He submitted 2 different
entries. One entry read the numbers, calculated the answer in the
normal way, and wrote the result to a file; the second entry spent
most of its time asleep, but woke up briefly every few seconds and
checked it the answer file existed. When it did, it printed it
out. The second process only took a few milliseconds of total CPU
time. Since contestants were allowed to submit multiple entries, the
smaller time counted and put him in second place,
The programmer whose entry came in third, taking slightly less than
the calculated minimum time, had the most elaborate scheme, He had
worked out the optimized machine code instructions to solve the
problem, and stored the instructions as an array of integers in his
program. It was easy to overwrite a return address on the stack (as
Bob Morris, Jr. later did with the Internet worm of 1988) and cause
the program to jump into and start executing this array. These
instructions solved the problem honestly in record time.
There was an uproar among the faculty when these stratagems were
uncovered. Some of the staff were in favor of severely reprimanding
the winners. A younger group of professors proposed instead awarding
them an extra prize in recognition of their ingenuity. In the end, a
compromise was reached. No prizes were awarded, no punishments were
handed down, and the results stuck. Sadly, the contest was a casualty
of the strong feelings, and this incident marked the final year it was
held.'