Outline for November 17, 2005

Reading: K. Thompson, "Reflections on Trusting Trust," Communications of the ACM 27 (8) pp. 761-763 (Aug. 1984).

1. Malicious logic
   1. Trojan horses, including replicatiing Trojan horses
   2. Computer viruses
      1. Boot sector infectors
      2. Executable infectors
      3. Multipartite viruses
      4. TSR viruses
      5. Stealth viruses
      6. Encrypted viruses
      7. Polymorphic viruses
      8. Macro viruses
   3. Computer worms
   4. Rabbits, bacteria
   5. Logic bombs
2. Defenses
   1. Cannot write a program to detect computer viruses without error
   2. Can detect all such programs if willing to accept false positives
   3. Can constrain case enough to locate specific malicious logic, using:
      1. Type checking (data vs. instructions)
      2. Limiting rights (sandboxing)
      3. Limiting sharing
      4. Preventing or detecting changes to files
      5. Prevent code from acting beyond specification (proof carrying code)
      6. Check statistical characteristics of programs (more authors than known, constructs in object files not corresponding to anything in the source)

Puzzle of the Day

Dr. Solomon, one of the earliest anti-virus software developers, wrote the following:

.... Fanfare of trumpets ...

.... Roll of the drums ...

.... Very loud noise from 76 trombones ....

THE PERFECT ANTIVIRUS

Definition. I shall now give you, free of charge, an antivirus that if used correctly, detects all past, present and future viruses, never gives a false alarm, and has a zero cost. Sceptical? Then watch carefully ...

P1.BAT
Echo %1 is infected by a virus!!!

You'll agree, I think, that P1.BAT will detect all past present and future viruses. That alone meets the "mathematically impossible" task! But, I hear you thinking, aren't there rather a lot of false alarms? Well, you didn't say you wanted a low false alarm rate....

OK, OK. I'm used to projects where the user specification changes in the midle. Never mind. I can deal with the false alarms ...

P2.BAT
Echo %1 is NOT infected by a virus!!!

You'll agree, I think, that P2 will never, ever, tell you that you have a virus when you don't. Of course, it has a pretty poor detection rate. I admit that. But I can fix it. See here ...

PERFECT.BAT
Echo Is %1 a virus? (Y/N)

If the user types Y, you run P1. If the user types N, you run P2. Remember what I promised you? An antivirus that *if used correctly*, detects all past, present and future viruses, never gives a false alarm, and has a zero cost. All very amusing, but what can we learn from this?

What lessons can you draw from this exercise?