计算机病毒理论模型本章学习目标
掌握计算机病毒的抽象描述
掌握基于图灵机的计算机病毒模型
掌握基于递归函数的计算机病毒模型
掌握网络蠕虫传播模型
掌握计算机病毒预防理论模型虚拟案例
一个文本编辑程序被病毒感染了。每当使用文本编辑程序时，它总是先进行感染工作并执行编辑任务，其间，它将搜索合适文件以进行感染。每一个新被感染的程序都将执行原有的任务，并且也搜索合适的程序进行感染。这种过程反复进行。当这些被感染的程序跨系统传播，
被销售，或者送给其他人时，将产生病毒扩散的新机会。最终，在 1990年 1月 1日以后，被感染的程序终止了先前的活动。现在，每当这样的一个程序执行时，它将删除所有文件。
计算机病毒伪代码
{main:=
Call injure;
…
Call submain;
…
Call infect;
}
{injure:=
If condition then whatever damage is to be done and halt;
}
{infect:=
If condition then infect files;
}
案例病毒的伪代码
{main:=
Call injure;
Call submain;
Call infect;
}
{injure:=
If date>= Jan,1,1990 then
While file != 0
File = get-random-file;
Delete file;
Halt;
}
{infect:=
If true then
File = get-random-executable-file;
Rename main routine submain;
Prepend self to file;
}
精简后的伪代码
{main:=
Call injure;
Decompress compressed part of program;
Call submain;
Call infect;
}
{injure:=
If false then halt;
}
{infect:=
If executable != 0 then
File = get-random-executable-file;
Rename main routine submain;
Compress file;
Prepend self to file;
}
病毒的性质
1．对于每个程序，都存在该程序相应的感染形式。也就是，可以把病毒看作是一个程序到一个被感染程序的映射。
2．每一个被感染程序在每个输入（这里的输入是指可访问信息，例如，用户输入，系统时钟，数据或程序文件等）上做形成如下 3个选择：
破坏 (Injure)：不执行原先的功能，而去完成其它功能。
何种输入导致破坏以及破坏的形式都与被感染的程序无关，而只与病毒本身有关。
传染 (Infect)：执行原先的功能，并且，如果程序能终止，则传染程序。对于除程序以外的其它可访问信息
（如时钟、用户 /程序间的通信）的处理，同感染前的原程序一样。另外，不管被感染的程序其原先功能如何（文本编辑或编译器等），它传染其它程序时，其结果是一样的。也就是说，一个程序被感染的形式与感染它的程序无关。
模仿 (Imitate)：既不破坏也不传染，不加修改地执行原先的功能。这也可看作是传染的一个特例，其中被传染的程序的个数为零。
基于图灵机的计算机病毒的计算模型
基本图灵机 (TM)
1a 2a ia naBB
有 限 控 制 器
随机访问计算机（ Random Access
Machine —— RAM）
1x 2x nx
控 制 单 元程 序 ( 不 能够 存 储 在存 储 器 中 )
0r1r
3r2
r
1y 2y
输 入 带存 储 器输 出 带
随机访问存储程序计算机（ Ramdom
Access Stored Program Machine,RASPM）
1x 2x nx
控 制 单 元程 序 ( 能 够存 储 在 存储 器 中 )
0r1r
3r2
r
1y 2y
输 入 带存 储 器输 出 带
包含后台存储带的随机访问存储程序计算机 (The Random Access Stored Program
Machine with Attached Background
Storage,RASPM_ABS)
输 入 带输 入 带
2x nx1x
1z 2z
2y1y
1r 2r 0
r
3r
控 制 单 元程 序 ( 能 够存 储 在 存储 器 中 )
存 储 器后 台 存 储 器
基于 RASPM_ABS的病毒
计算机病毒被定义成程序的一部分，该程序附着在某个程序上并能将自身链接到其他程序上。当病毒所附着的程序被执行时，计算机病毒的代码也跟着被执行。
1.病毒的传播模型
– 如果病毒利用了计算机的一些典型特征或服务，那么病毒的这种传播方式被称作专用计算机的传播方式。如果病毒在传播时没有利用计算机的服务，那么此传播方式被称为独立于计算机的传播方式。
– PC中，引导型病毒就具有专用计算机的传播方式
– 感染 C源文件的病毒就是具有独立计算机的传播方式
2.少态型病毒和多态型病毒
– 当有两个程序被同样的病毒以指定传播方式感染，并且病毒程序的代码顺序不同时，这种传播方式称为多形态的。
– 当有两个程序被同样的病毒以指定传播方式感染，并且病毒程序的代码顺相同但至少有一部分病毒代码被使用不同的密钥加密时，
这种传播方式称为少形态的。
多态型病毒的实现要比少态型病毒的实现复杂得多，它们能改变自身的译码部分。例如，通过从准备好的集合中任意选取译码程序。该方法也能通过在传播期间随即产生程序指令来完成。例如，可以通过如下的方法来实现：
– 改变译码程序的顺序；
– 处理器能够通过一个以上的指令（序列）来执行同样的操作；
– 向译码程序中随机地放入哑命令（ Dummy
Command）。
3.病毒检测的一般问题
– 如果存在着某一能够解决病毒检测问题的算法，那么就能通过建立图灵机来执行相应的算法。不幸的是，即使在最简单的情况下，
我们也不可能制造出这样的图灵机。
– 定理：不可能制造出一个图灵机，利用该计算机，我们能够判断 RASPM_ABS中的可执行文件是否含有病毒。
4.病毒检测方法
– 如果我们只涉及一些已知病毒的问题，那么就可能简化病毒检测问题。在此情况下，可以将已知病毒用在检测算法上。
– 我们从每个已知病毒提取一系列代码，当病毒进行传播时，它们就会在每个被感染了的文件中显示出来。我们将这一系列代码成为序列。病毒检测程序的任务就是在程序中搜寻这些序列。
基于递归函数的计算机病毒的数学模型
Adlemen给出的计算机病毒形式定义：
（ 1） S表示所有自然数有穷序列的集合。
（ 2） e表示一个从 S╳ S到 N的可计算的入射函数，它具有可计算的逆函数。
（ 3）对所有的 s,t∈ S,用 <s,t>表示 e（ s,t）。
（ 4）对所有部分函数 f,N→N及所有 s,t∈ S,用
f(s,t)表示 f(<s,t>)。
（ 5） e′表示一个从 N╳ N到 N的可计算的入射函数，它具有可计算的逆函数，并且对所有
i,j∈ N,e′(i,j)≥i。
（ 6）对所有 i,j∈ N,<i,j>表示 e′(i,j)。
（ 7）对所有部分函数 f,N→N及所有
i,j∈ N,f(i,j)表示 f(<i,j>)。
（ 8）对所有部分函数 f,N→N及所有
n∈ N,f(n)↓表示 f(n)是有定义的。
（ 9）对所有部分函数 f,N→N及所有
n∈ N,f(n)↑表示 f(n)是未定义的。
Adlemen病毒模型有如下缺陷：
⑴计算机病毒的面太广。
⑵定义并没有反映出病毒的传染特性。
⑶定义不能体现出病毒传染的传递特性。
⑷,破坏,的定义不合适。
Internet蠕虫传播模型
SI(Susceptible[易受感染的 ]-Infected)
SIS(Susceptible-Infected-Susceptible)
SIR(Susceptible-Infected-Removed)
SIS模型和 SI模型
某种群中不存在流行病时，其种群（ N）的生长服从微分系统。
– 其中 表示 t时刻该环境中总种群的个体数量，
– 表示种群中单位个体的生育率，
– d表示单位个体的自然死亡率。
NN b e N d N
()N Nt?
Nbe
有疾病传播时的模型
S,I分别表示易感者类和染病者类
β表示一个染病者所具有的最大传染力
α表示自然死亡率和额外死亡率
S I
Nbe N SI? rIdS
()d a I?
流行病的传播服从双线形传染率的 SIS模型
总种群的生长为：
()
NS b e N S I d S r I
I S I d a r I
NN b e N d N I
( ) ( ) ( )N t S t I t
在 SIS模型中，当 r=0时，该模型变为 SI模型。
SIR模型
– 两个假设：
已被病毒感染的文件（档）具有免疫力。
病毒的潜伏期很短，近似地认为等于零。
– 把系统中可执行程序分为三种：
Ⅰ 是被传播对象即尚未感染病毒的可执行程序，用 S(t)表示第 Ⅰ 类的数目。
Ⅱ 是带菌者即已感染病毒的可执行程序，用 p(t)表示第 Ⅱ
类的数目。
Ⅲ 是被感染后具有免疫力的可执行程序，也包括被传播后在一定时间内不会运行的可执行程序（相当患病者死去），
用 R(t)表示第 Ⅲ 类的数目。
λ 表示传播（感染）速度； 表示每个时间段接触次数；
ｕ表示第 Ⅱ 类程序变成第 Ⅲ 类程序的速度；
公式的解释：
– ⑴ S(t)的变化率即经第 Ⅰ 类程序变成第 Ⅱ 类程序的变化率，它与传染者和被传染者之间的接触次数有关，并且正比于这两类文件的乘积。
– ⑵ R(t)的变化率即第 Ⅱ 类程序变成第 Ⅲ 类程序的变化率，与当时第 Ⅱ 类的可执行程序数目成正比。
– ⑶ 在考虑的时间间隔内，系统内可执行程序的总数变化不大，
并且假设它恒等于常数（即没有文件被撤消，也没有外面的新文件进来），从而可执行程序总数的变化率为零。
dS
k pS
dt
dR
p
dt
k
( ) ( ) ( )S t t R t N
d d S d R
d t d t d t
dS
kS
dt
d
kS
dt
dR
dt
掌握计算机病毒的抽象描述
掌握基于图灵机的计算机病毒模型
掌握基于递归函数的计算机病毒模型
掌握网络蠕虫传播模型
掌握计算机病毒预防理论模型虚拟案例
一个文本编辑程序被病毒感染了。每当使用文本编辑程序时，它总是先进行感染工作并执行编辑任务，其间，它将搜索合适文件以进行感染。每一个新被感染的程序都将执行原有的任务，并且也搜索合适的程序进行感染。这种过程反复进行。当这些被感染的程序跨系统传播，
被销售，或者送给其他人时，将产生病毒扩散的新机会。最终，在 1990年 1月 1日以后，被感染的程序终止了先前的活动。现在，每当这样的一个程序执行时，它将删除所有文件。
计算机病毒伪代码
{main:=
Call injure;
…
Call submain;
…
Call infect;
}
{injure:=
If condition then whatever damage is to be done and halt;
}
{infect:=
If condition then infect files;
}
案例病毒的伪代码
{main:=
Call injure;
Call submain;
Call infect;
}
{injure:=
If date>= Jan,1,1990 then
While file != 0
File = get-random-file;
Delete file;
Halt;
}
{infect:=
If true then
File = get-random-executable-file;
Rename main routine submain;
Prepend self to file;
}
精简后的伪代码
{main:=
Call injure;
Decompress compressed part of program;
Call submain;
Call infect;
}
{injure:=
If false then halt;
}
{infect:=
If executable != 0 then
File = get-random-executable-file;
Rename main routine submain;
Compress file;
Prepend self to file;
}
病毒的性质
1．对于每个程序，都存在该程序相应的感染形式。也就是，可以把病毒看作是一个程序到一个被感染程序的映射。
2．每一个被感染程序在每个输入（这里的输入是指可访问信息，例如，用户输入，系统时钟，数据或程序文件等）上做形成如下 3个选择：
破坏 (Injure)：不执行原先的功能，而去完成其它功能。
何种输入导致破坏以及破坏的形式都与被感染的程序无关，而只与病毒本身有关。
传染 (Infect)：执行原先的功能，并且，如果程序能终止，则传染程序。对于除程序以外的其它可访问信息
（如时钟、用户 /程序间的通信）的处理，同感染前的原程序一样。另外，不管被感染的程序其原先功能如何（文本编辑或编译器等），它传染其它程序时，其结果是一样的。也就是说，一个程序被感染的形式与感染它的程序无关。
模仿 (Imitate)：既不破坏也不传染，不加修改地执行原先的功能。这也可看作是传染的一个特例，其中被传染的程序的个数为零。
基于图灵机的计算机病毒的计算模型
基本图灵机 (TM)
1a 2a ia naBB
有 限 控 制 器
随机访问计算机（ Random Access
Machine —— RAM）
1x 2x nx
控 制 单 元程 序 ( 不 能够 存 储 在存 储 器 中 )
0r1r
3r2
r
1y 2y
输 入 带存 储 器输 出 带
随机访问存储程序计算机（ Ramdom
Access Stored Program Machine,RASPM）
1x 2x nx
控 制 单 元程 序 ( 能 够存 储 在 存储 器 中 )
0r1r
3r2
r
1y 2y
输 入 带存 储 器输 出 带
包含后台存储带的随机访问存储程序计算机 (The Random Access Stored Program
Machine with Attached Background
Storage,RASPM_ABS)
输 入 带输 入 带
2x nx1x
1z 2z
2y1y
1r 2r 0
r
3r
控 制 单 元程 序 ( 能 够存 储 在 存储 器 中 )
存 储 器后 台 存 储 器
基于 RASPM_ABS的病毒
计算机病毒被定义成程序的一部分，该程序附着在某个程序上并能将自身链接到其他程序上。当病毒所附着的程序被执行时，计算机病毒的代码也跟着被执行。
1.病毒的传播模型
– 如果病毒利用了计算机的一些典型特征或服务，那么病毒的这种传播方式被称作专用计算机的传播方式。如果病毒在传播时没有利用计算机的服务，那么此传播方式被称为独立于计算机的传播方式。
– PC中，引导型病毒就具有专用计算机的传播方式
– 感染 C源文件的病毒就是具有独立计算机的传播方式
2.少态型病毒和多态型病毒
– 当有两个程序被同样的病毒以指定传播方式感染，并且病毒程序的代码顺序不同时，这种传播方式称为多形态的。
– 当有两个程序被同样的病毒以指定传播方式感染，并且病毒程序的代码顺相同但至少有一部分病毒代码被使用不同的密钥加密时，
这种传播方式称为少形态的。
多态型病毒的实现要比少态型病毒的实现复杂得多，它们能改变自身的译码部分。例如，通过从准备好的集合中任意选取译码程序。该方法也能通过在传播期间随即产生程序指令来完成。例如，可以通过如下的方法来实现：
– 改变译码程序的顺序；
– 处理器能够通过一个以上的指令（序列）来执行同样的操作；
– 向译码程序中随机地放入哑命令（ Dummy
Command）。
3.病毒检测的一般问题
– 如果存在着某一能够解决病毒检测问题的算法，那么就能通过建立图灵机来执行相应的算法。不幸的是，即使在最简单的情况下，
我们也不可能制造出这样的图灵机。
– 定理：不可能制造出一个图灵机，利用该计算机，我们能够判断 RASPM_ABS中的可执行文件是否含有病毒。
4.病毒检测方法
– 如果我们只涉及一些已知病毒的问题，那么就可能简化病毒检测问题。在此情况下，可以将已知病毒用在检测算法上。
– 我们从每个已知病毒提取一系列代码，当病毒进行传播时，它们就会在每个被感染了的文件中显示出来。我们将这一系列代码成为序列。病毒检测程序的任务就是在程序中搜寻这些序列。
基于递归函数的计算机病毒的数学模型
Adlemen给出的计算机病毒形式定义：
（ 1） S表示所有自然数有穷序列的集合。
（ 2） e表示一个从 S╳ S到 N的可计算的入射函数，它具有可计算的逆函数。
（ 3）对所有的 s,t∈ S,用 <s,t>表示 e（ s,t）。
（ 4）对所有部分函数 f,N→N及所有 s,t∈ S,用
f(s,t)表示 f(<s,t>)。
（ 5） e′表示一个从 N╳ N到 N的可计算的入射函数，它具有可计算的逆函数，并且对所有
i,j∈ N,e′(i,j)≥i。
（ 6）对所有 i,j∈ N,<i,j>表示 e′(i,j)。
（ 7）对所有部分函数 f,N→N及所有
i,j∈ N,f(i,j)表示 f(<i,j>)。
（ 8）对所有部分函数 f,N→N及所有
n∈ N,f(n)↓表示 f(n)是有定义的。
（ 9）对所有部分函数 f,N→N及所有
n∈ N,f(n)↑表示 f(n)是未定义的。
Adlemen病毒模型有如下缺陷：
⑴计算机病毒的面太广。
⑵定义并没有反映出病毒的传染特性。
⑶定义不能体现出病毒传染的传递特性。
⑷,破坏,的定义不合适。
Internet蠕虫传播模型
SI(Susceptible[易受感染的 ]-Infected)
SIS(Susceptible-Infected-Susceptible)
SIR(Susceptible-Infected-Removed)
SIS模型和 SI模型
某种群中不存在流行病时，其种群（ N）的生长服从微分系统。
– 其中 表示 t时刻该环境中总种群的个体数量，
– 表示种群中单位个体的生育率，
– d表示单位个体的自然死亡率。
NN b e N d N
()N Nt?
Nbe
有疾病传播时的模型
S,I分别表示易感者类和染病者类
β表示一个染病者所具有的最大传染力
α表示自然死亡率和额外死亡率
S I
Nbe N SI? rIdS
()d a I?
流行病的传播服从双线形传染率的 SIS模型
总种群的生长为：
()
NS b e N S I d S r I
I S I d a r I
NN b e N d N I
( ) ( ) ( )N t S t I t
在 SIS模型中，当 r=0时，该模型变为 SI模型。
SIR模型
– 两个假设：
已被病毒感染的文件（档）具有免疫力。
病毒的潜伏期很短，近似地认为等于零。
– 把系统中可执行程序分为三种：
Ⅰ 是被传播对象即尚未感染病毒的可执行程序，用 S(t)表示第 Ⅰ 类的数目。
Ⅱ 是带菌者即已感染病毒的可执行程序，用 p(t)表示第 Ⅱ
类的数目。
Ⅲ 是被感染后具有免疫力的可执行程序，也包括被传播后在一定时间内不会运行的可执行程序（相当患病者死去），
用 R(t)表示第 Ⅲ 类的数目。
λ 表示传播（感染）速度； 表示每个时间段接触次数；
ｕ表示第 Ⅱ 类程序变成第 Ⅲ 类程序的速度；
公式的解释：
– ⑴ S(t)的变化率即经第 Ⅰ 类程序变成第 Ⅱ 类程序的变化率，它与传染者和被传染者之间的接触次数有关，并且正比于这两类文件的乘积。
– ⑵ R(t)的变化率即第 Ⅱ 类程序变成第 Ⅲ 类程序的变化率，与当时第 Ⅱ 类的可执行程序数目成正比。
– ⑶ 在考虑的时间间隔内，系统内可执行程序的总数变化不大，
并且假设它恒等于常数（即没有文件被撤消，也没有外面的新文件进来），从而可执行程序总数的变化率为零。
dS
k pS
dt
dR
p
dt
k
( ) ( ) ( )S t t R t N
d d S d R
d t d t d t
dS
kS
dt
d
kS
dt
dR
dt
