**Computer Viruses Theory and Experiments**By Dr. Frederick B. Cohen Presented by Jose Andre Morales**Background**• Originally written in 1984 • Published in Computers and Security, Vol. 6, pp. 22-35 • Appeared in DOD/NBS 7th Conference on Computer Security • Considered the foundation of computer virus research**Highlights**• Coined the phrase “Computer Virus” • Gave a definition for a computer virus • Showed multiple aspects of dealing with viruses are not decidable • Presented many fundamental properties of computer viruses**Computer Virus Defined**A computer virus is defined as: A program that can infect other programs by modifying them to include a possibly evolved copy of itself Key Property: the ability to infect other programs.**An Example**• We have a file sharing system • User A has program P1 that is infected by a virus • User B runs P1 from the file sharing system and P1 infects B’s program P2 • User C runs P2 from the same file sharing system and P2 infects C’s program P3 • Virus spreads from program to program and user to user**Deeper Description of a Virus**• A computer virus can be viewed as sequences of symbols in the memory of a machine in some form • Ex. main memory, registers, disk, tape, etc… • One of those sequences of symbols (v) is an element of a viral set (V) if • when interpreted by the machine it causes some other element of the viral set or itself (v’) to appear somewhere else in the system at a later point in time**Formal Definition of Language V**M V (M,V) V [V I*] and [MM] and vV H t, j N [[Pt = j] and [t = 0] and (t,j,…, t,j+|v|-1) = v] v’V, t’, t’’, j N and t’ > t [[j’ + |v’|) j] or [(j + |v|) j’]] and [((t’,j’,…, t’,j’+|v’|-1) = v’] and [t’’[t < t’’ < t’] and [Pt’’ {j’,…j’ + |v’| -1}]]**Description of Formal Definition**• For all M and V, the pair (M,V) Vif and only if • V is a set of TM sequences and M is a TM where • M’s tape head is at a cell j at time t and the tape cells starting at j hold the virus v • At a time t’ > t tape cells starting at cell j’, far enough away from v hold the virus v’ such that • At time t < t’’ < t’, v’ is written by M to tape cells starting at j’**Detection of a Virus**• P is a virus if it is determined that P infects other programs • This is not a decidable problem • P can infect if and only if a detection process D finds P to be non-viral • Thus finding a virus by appearance may be infeasible**Detection of a Virus 2**An example program contradictory-virus:= {... main-program:= {if ~D(contradictory-virus) then {infect-executable; if trigger-pulled then do-damage; } goto next; } } The virus CV will only infect if the detector D returns False, if D returns True no infection takes place.**Detection of a Virus 3**• If D returns true then the virus CV will not act like a virus • If D returns false then the virus CV will act as one. • Clearly detector D is self contradictory**Formal Proof 1**Can a Turing Machine be created that can determine in a finite amount of time If a set of sequences of symbols V for a given Turing Machine M is a virus. Cohen showed that it is not decidable whether or not (M,V) V This is done via a reduction from Atm**Formal Proof 2**• A Turing Machine M’ that decides if (M,V) V • On input <M,V> • Run M on V • If M accepts V then accept (M,V)V • If M rejects V then reject (M,V)notV • (M,V) Vif and only if • M accepts and halts on V • Thus we have Atm≤ V • Since Atm is not decidable then V is also not decidable. • QED**Removal of a Virus 1**• Removal of a virus depends on detection • Detection is not decidable • the removal of a virus is not absolutely guaranteed • Therefore not all viruses can be precisely detected and removed from a given computer system.**Removal of a Virus 2**• If a more liberal detection method is used then detection and removal is possible • But at the expense of producing false positives and false negatives. • Ex. Erase all files created after a specific date from the system.**Cohen’s Not Decidable Detection Problems**• Detection of a virus by its appearance and behavior • Detection of an evolution of a known virus • Detection of a triggering mechanism by its appearance and behavior • Detection of an evolution of a known triggering mechanism • Detection of a virus detector by its appearance and behavior • Detection of an evolution of a known viral detector**Cohen’s Conclusions**• Precise viral detection is not decidable • Multiple detection problems dealing with virus are not decidable • Viral removal is not always guaranteed because it is dependent on detection**Questions?**sawaal soru 問題 ¿Preguntas?