Viruses: The Four Phases, the Structure and the Types

NIST's own division is by what executes the virus: compiled viruses, run by the operating system, which is where file infector, boot sector and multipartite belong, and interpreted viruses, run by an application, which is where macro and scripting viruses belong.

Why macro viruses mattered so much. A macro virus infects documents, not programs. Documents are exchanged far more freely than programs, are not thought of as executable, and are the same on every platform the application runs on. The answer was not cleverer scanning but a change in the application: macros do not run unless the person allows them.

The structure, and what it is arranged to defeat

A virus that attaches to a program has to do four things when the infected program is run: check whether a chosen target is already infected, so it does not attach twice; attach a copy of itself to the target; do whatever its payload requires if the trigger condition holds; and finally hand control to the original program, so that everything appears normal.

Every one of those steps exists to keep some check from noticing.

• The infection marker exists so that the virus does not attach twice and make the file grow twice. A marker is also the first thing a defender can look for: it is a fixed pattern that the virus itself must recognise.
• Handing control back exists so that the user sees the program behave as expected. If the program failed or paused, someone would investigate.
• Compression, the classic trick, exists to defeat a check on the file's length. If the virus first squeezes the host program by more than the space it needs, it can restore the file to exactly its old length. The run below does that arithmetic.

Hiding from the scanner: the kinds by concealment

Cohen proved that this arms race has no end. To decide that a program is a virus, one must decide that it infects other programs. Cohen assumed a decision procedure D that answers correctly, and then described a program that calls D and infects other programs if and only if D says it is not a virus. The procedure is then "self contradictory", so "precise determination of a virus by its appearance is undecidable". His conclusions list the undecidable problems: detecting a virus by its appearance, by its behaviour, and detecting "an evolution of a known virus". This is why no scanner can be complete, and why defence also relies on checks that do not try to recognise the attacker at all.

The run: four checks, and what each one misses

The listing walks the four phases, then tries three defences: a check on a file's length, a scan for a known sequence of bytes, and a comparison against a stored hash. Nothing in it replicates: the "infected" files are ordinary byte strings, and each step only asks whether a check would notice.

# A virus from the DEFENDER'S side: the four phases as a state machine, then three detectors
# tried against three kinds of concealment. Nothing here infects anything: the "infected" files
# are ordinary byte strings, and every step asks only whether a check would notice.
import hashlib, random, zlib

# ---- 1. the four phases, walked through in order ---------------------------------------------
PHASES = [('dormant', 'installed but idle, waiting for whatever activates it'),
          ('propagation', 'placing a copy of itself where it can'),
          ('triggering', 'the condition it was waiting for has been met'),
          ('execution', 'the payload runs: a message, or damage')]
print('1. THE FOUR PHASES')
for name, meaning in PHASES:
    print('   %-12s %s' % (name, meaning))

def phase_of(run, trigger_day):
    """Where the four phases fall as the infected program is run day after day."""
    if run == 0:
        return 'dormant'
    if run == trigger_day:
        return 'triggering'
    if run == trigger_day + 1:
        return 'execution'
    return 'propagation'

print()
print('   run of the host program   phase        copies placed so far')
copies = 0
for run in range(6):
    here = phase_of(run, 4)
    copies += here == 'propagation'
    print('   %-25s %-12s %d' % (run if run else 'not yet run', here, copies))

# ---- 2. what a size check sees ---------------------------------------------------------------
# A stand-in for a compiled program: short opcode-like groups with varying operands, so that it
# compresses about as far as real machine code does. It is a stand-in, and the run prints how far
# it actually compressed rather than assuming a figure.
rng = random.Random(1984)
GROUPS = [b'\x8b\x45\xfc', b'\x83\xc0\x01', b'\x89\x45', b'\xe8', b'\xc3',
          b'\x55\x89\xe5', b'\x83\xec', b'\x8d\x55', b'\xff\x75', b'\x50']
buf = bytearray()
while len(buf) < 12_400:
    buf += rng.choice(GROUPS) + bytes([rng.randrange(256)])
program = bytes(buf[:12_400])
ADDED = 1_800                                    # how much bigger something added would make it
plain = program + bytes(ADDED)
squeezed = zlib.compress(program, 9)
disguised = squeezed + bytes(ADDED)
print()
print('2. A SIZE CHECK, AND THE TRICK THAT WAS BUILT TO DEFEAT IT')
print('   the program as shipped            %6d bytes' % len(program))
print('   with %d bytes added              %6d bytes  size check: %s'
      % (ADDED, len(plain), 'NOTICES' if len(plain) != len(program) else 'passes'))
print('   the program compressed            %6d bytes, %.0f%% of the original'
      % (len(squeezed), 100 * len(squeezed) / len(program)))
print('   compressed, plus the same %d    %6d bytes  size check: %s'
      % (ADDED, len(disguised), 'NOTICES' if len(disguised) > len(program) else 'passes'))
print('   compressing saved %d bytes, more than the %d added, leaving %d spare'
      % (len(program) - len(squeezed), ADDED, len(program) - len(disguised)))
print('   padding those out, the file is exactly its old length again: %s'
      % (len(disguised + bytes(len(program) - len(disguised))) == len(program)))

# ---- 3. a fixed signature against three levels of concealment --------------------------------
BODY = b'\x8b\x45\xfc\x83\xc0\x01\x89\x45\xfc\xeb\xe2'      # the bytes a scanner knows
STUB = b'\x31\xc9\xb1\x0b\x80\x34\x0e'          # a fixed loop that undoes the masking

def masked(body, key):
    return bytes(b ^ key for b in body)

samples = {
    'plain': BODY,
    'masked with key 0x11': STUB + masked(BODY, 0x11),
    'masked with key 0x7d': STUB + masked(BODY, 0x7d),
    'masked, and the stub rewritten': b'\x33\xc9\xb9\x0b\x00\x30\x24\x0e' + masked(BODY, 0x42),
}
print()
print('3. ONE SIGNATURE, THREE LEVELS OF CONCEALMENT')
print('   %-32s %-14s %s' % ('sample', 'body found?', 'stub found?'))
for name, blob in samples.items():
    print('   %-32s %-14s %s' % (name, 'yes' if BODY in blob else 'no',
                                 'yes' if STUB in blob else 'no'))
print('   a scanner that looks for the body alone finds %d of %d'
      % (sum(BODY in b for b in samples.values()), len(samples)))
print('   a scanner that looks for the constant stub finds %d of %d'
      % (sum(STUB in b for b in samples.values()), len(samples)))

# ---- 4. the check that does not care how it was hidden ----------------------------------------
baseline = {'a.bin': program, 'b.bin': program, 'c.bin': program, 'd.bin': program}
stored = {name: hashlib.sha256(data).hexdigest() for name, data in baseline.items()}
padded = disguised + bytes(len(program) - len(disguised))
now = {'a.bin': program, 'b.bin': plain, 'c.bin': padded,
       'd.bin': program[:-len(BODY)] + BODY}        # same length, contents changed
print()
print('4. AN INTEGRITY CHECK AGAINST A STORED HASH')
for name in sorted(now):
    same_size = len(now[name]) == len(baseline[name])
    changed = hashlib.sha256(now[name]).hexdigest() != stored[name]
    print('   %-7s size unchanged: %-5s  hash changed: %-5s  %s'
          % (name, same_size, changed, 'ALARM' if changed else 'no change'))
print('   caught by size alone: %d of %d; caught by the hash: %d of %d'
      % (sum(len(now[n]) != len(baseline[n]) for n in now), len(now),
         sum(hashlib.sha256(now[n]).hexdigest() != stored[n] for n in now), len(now)))

What the run establishes, in order.

The phases are a sequence, not a list. The virus is dormant until the program is run, spends most runs propagating, and only once reaches triggering and then execution. A defender who watches only for damage sees nothing during the runs that matter most.

A length check is worth having and easy to defeat. Adding 1,800 bytes to the program makes the file longer, and the check notices. Compressing the program first saved 3,907 bytes of the 12,400, more than the 1,800 needed, leaving enough spare to pad the file back to exactly its old length. The check then passes. The stand-in program compressed to 68 per cent of its length, about what compiled code does; the trick works whenever compression saves more than the addition costs.

A signature finds what it was given and nothing else. The scanner's eleven bytes match the unconcealed sample and none of the masked ones. Looking instead for the constant unmasking routine catches both masked versions, which is exactly what scanners do with encrypted viruses; and the variant that rewrites that routine too, the polymorphic case, is found by neither.

A stored hash does not care how the change was hidden. All three changed files fail the comparison, including the one padded back to its original length and the one whose contents changed without any change in length. This is integrity checking, and it is the answer to concealment: it recognises the file, not the attacker. Its cost is that it must be told what "correct" is, and be kept where the attacker cannot rewrite it.

Distinctions that carry marks

What beginners get wrong here

Saying the payload is what makes it a virus. Copying itself into other programs is what makes it a virus; the payload may be nothing at all.

Treating the four phases as universal. They are the textbook's description of a typical virus, and not every virus has a dormant phase or a trigger.

Thinking a longer signature list makes a scanner complete. Cohen's result is that detection by appearance is undecidable in general; a list of known patterns can only ever find what is already known.

Confusing encrypted with polymorphic. In both, the body is masked; only in a polymorphic virus is the unmasking routine itself rewritten each time, which is what defeats a signature taken from that routine.

Believing a stealth virus fools every check. It hides from reads made through the infected system; a check made from a clean system, or against a stored hash kept elsewhere, still sees the change.

Quick revision

• Cohen, 1984: a virus is "a program that can 'infect' other programs by modifying them to include a possibly evolved copy of itself". Detection by appearance is undecidable.
• Four phases: dormant (idle), propagation (copies itself), triggering (condition met), execution (the payload).
• Structure when the host runs: check the target is not already infected (a marker), attach a copy, act if triggered, hand control back so nothing looks wrong.
• Compression defeats a length check: squeeze the host by more than the addition needs.
• NIST's kinds: compiled (file infector, boot sector, multipartite) and interpreted (macro, scripting).
• Concealment: encrypted (masked body, fixed routine), stealth (lies to reads), polymorphic (routine rewritten too), metamorphic (whole body rewritten).
• Run: length catches 1 of 4, a body signature 1 of 4, a routine signature 2 of 4, a stored hash all 3 changed files.

Test yourself

1. Define a virus and describe its four phases. A virus is a program that infects other programs by modifying them to include a possibly evolved copy of itself, so that the copy runs and infects further programs when the modified program is run. In the dormant phase it is idle, waiting for an event such as a date or the presence of a file to activate it. In the propagation phase it places copies of itself into other programs or into system areas of a disk. In the triggering phase the condition it waits for is met and it prepares to act. In the execution phase its payload is performed, which may be a harmless message or the destruction of data.

2. Describe what a virus attached to a program does when that program is run, and why each step is there. It first checks whether the program it has chosen is already infected, usually by looking for a marker it left before, so that it does not attach twice and make the file grow twice. It then attaches a copy of itself to that program. If its trigger condition is met, it performs its payload. Finally it transfers control to the original program so that the program behaves exactly as the user expects and nothing appears wrong. Each step is arranged so that some check, on file size, on behaviour, or by the user, fails to notice.

3. How does a compression virus conceal itself, and what does that tell you about detection? It compresses the host program before attaching itself, by more than the space its own copy requires, and pads the result so that the infected file has exactly the same length as before; when the program is run, the original is expanded and executed normally. It tells you that a check on file length alone is not enough, and more generally that each concealment technique is aimed at one particular check, so defences must be layered.

4. Distinguish encrypted, polymorphic and metamorphic viruses. In an encrypted virus most of the body is stored masked under a key that differs between copies, with a small constant routine that unmasks it before it runs; a signature taken from the body fails, but one taken from the constant routine succeeds. A polymorphic virus masks the body and also rewrites the unmasking routine for every copy, so no fixed sequence of bytes survives and signature scanning fails entirely. A metamorphic virus rewrites its whole body on each copy, so two copies may share no bytes and may even behave differently while achieving the same effect.

5. Why can no scanner detect every virus? Because, as Cohen showed, deciding whether an arbitrary program is a virus is undecidable: given any decision procedure, one can describe a program that consults it and infects others precisely when the procedure says it is not a virus, which makes the procedure self contradictory. Detection by appearance, by behaviour, and detection of an evolution of a known virus are all undecidable, so scanners can only recognise what is already known, and defence must also use checks that do not depend on recognising the attacker, such as integrity checking against stored hashes.