PC Infections Hypothesis and Examinations - PowerPoint PPT Presentation

computer viruses theory and experiments n.
Skip this Video
Loading SlideShow in 5 Seconds..
PC Infections Hypothesis and Examinations PowerPoint Presentation
PC Infections Hypothesis and Examinations

play fullscreen
1 / 19
Download Presentation

PC Infections Hypothesis and Examinations

Presentation Transcript

  1. Computer Viruses Theory and Experiments By Dr. Frederick B. Cohen Presented by Jose Andre Morales

  2. 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

  3. 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

  4. 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.

  5. 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

  6. 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

  7. Formal Definition of Language V M V (M,V) V  [V  I*] and [MM] and vV 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}]]

  8. 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’

  9. 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

  10. 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.

  11. 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

  12. 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

  13. 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)notV • (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

  14. 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.

  15. 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.

  16. 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

  17. 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

  18. Questions? sawaal soru 問題 ¿Preguntas?