вход по аккаунту


Jose Morales

код для вставкиСкачать
Computer Viruses
Theory and Experiments
Dr. Frederick B. Cohen
Presented by
Jose Andre Morales
• Originally written in 1984
• Published in Computers and Security, Vol. 6,
pp. 22-35
• Appeared in DOD/NBS 7th Conference on Computer
• Considered the foundation of computer virus
• 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
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
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
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
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}]]
Description of Formal Definition
• For all M and V, the pair (M,V)  V if and
only if
• V is a set of TM sequences and M is a TM
• 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:=
{if ~D(contradictory-virus) then
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>
1. Run M on V
2. If M accepts V then accept пѓ (M,V) пѓЋV
3. If M rejects V then reject пѓ (M,V) not пѓЋV
(M,V) пѓЋV if 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.
Removal of a Virus 1
• Removal of a virus depends on detection
• Detection is not decidable
• the removal of a virus is not absolutely
• 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.
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
• Detection of a virus detector by its appearance and
• 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
Размер файла
73 Кб
Пожаловаться на содержимое документа