The Automaton Modeling of Typical Network Attacks
Shi Zhicai Electronic&Electrical Engineering Institute
Shanghai University of Engineering Science
Shanghai, P.R. China szc1964@163.com
Abstract—Network security is one of the most important research fields among information
security
techniques.
Most
problems of network security are often caused by network attacks. In order to ensure network secure running it is very necessary to analyze and research the procedure of network attacks. In this paper, the formal method is researched and automaton theory is used to describe the procedure of network attacks. The state transform diagrams of some typical network attacks are given. Different state transform diagrams are used to describe models for various network attacks and these models can be combined flexibly so as to describe complicated attack behaviors.
This
formal
method
for describing network attacks provides an effective approach for researching the mechanism of network attacks. Keywords-network attack;
automata;
information security; network intrusion
I. INTRODUCTION
Network Intrusions are defined as some behaviors which destroy the confidentiality, integrity, availability and controllability of the network system [1]. With the rapid development and widespread application of network techniques network attacks become more complicated. It is becoming very important how to abstract the features of network attacks and describe attack procedures so that they can be detected effectively. Natural language can be used to describe attack procedures. Although the
摘要——在信息安全技术领域中，网络的安全性是最重要的研究之一。大多数网络安全问题往往是网络攻击引起的。为了保证网络安全可靠的运行，分析和研究网络攻击的步骤是非常有必要的。在本文中，被研究的正式的方法和自动机理论是用来描述网络攻击的步骤。本文给出了一些状态变换的典型的网络攻击图。不同的状态转换图是用来描述各种网络攻击模型，这些模型可以灵活组合，来描述复杂的攻击行为。这种正式的用来描述网络攻击的方法对网络攻击的机制的研究提供了一种有效的途经。
Ⅰ．引言
网络入侵被定义为破坏了网络系统的保密性，完整性，可用性和可控性[ 1 ]的一定的行为。随着网络技术的迅速发展和广泛应用，网络攻击变得越来越复杂。如何概括网络攻击的特征和描述攻击步骤使他们能有效地检测变得非常重要。
method is direct it is very difficult to process natural language with a computer. Tidwell used attack tree to model the procedure of network intrusions [2]. But his method cannot describe the change of the system
states effectively. As we know, when the
system is running it changes from one state
to another state. These states represent different meanings. They may be some
normal states or abnormal states. But the
system is corresponding to only a state at any moment whether it is normal or abnormal.
The system runs to the ultimate state finally.
This will confirm the state of a system is limited. So the transition procedure of the
system states can be described with
deterministic finite automata. The automata can be described by means of state transition
diagram. When the system is attacked its
state will change and this procedure can be described directly by state transition diagram.
This makes attack procedures understood
easily. The remainder of this paper is
organized as follows. In Sect. II, we review
the theory of a deterministic finite automaton. In Sect， III, we investigate several typical network attacks and use deterministic
finite automata to describe their attack procedures. The state transform diagrams
of these network attacks are given. The paper
is concluded in Sect. IV with a summary and an outlook for future work.
II. DETERMINISTIC FINITE AUTOMATA
A deterministic finite automaton M is an automatic recognition device [3]. It consists
of:
1. A finite set of states, often denoted Q. 2. A finite set of input symbols, often
denoted. It is usually called a condition set.
3. A transition function that takes a state and an input symbol as arguments and returns
another state (or itself). The transition
自然语言可以用来描述攻击过程。但是该方法是直接的，用计算机处理自然语言非常困难。蒂德韦尔利用攻击树来建造网络入侵的过程[ 2 ]的模
型。但是他的方法不能有效的描述系
统状态的改变。我们知道，在系统运行时，它的变化是 从一个状态到另一个状态。这些状态代表不同的含义。
他们可能是一些正常状态或异常状态。
在任何时候，无论是正常或异常，系统仅仅对应于一个状态。最后，系统运行到极限状态。这将确定一个系统
的状态是有限的。因此系统状态的过
渡过程可以用确定性有限自动机描述。自动机可以通过状态过度图的方法描述。当系统受到攻击，它的状态会发
生变化，本程序可以通过状态转换图
直接描述。这使得攻击步骤易于理解。 本文的其余部分安排如下。第二，我们回顾一个确定性有限自动机理论。
第三，我们研究了几种典型的网络攻
击和使用确定性有限自动机来描述他们的攻击步骤，给出了这些网络攻击的状态转换图，本文的结论，总结和
对未来工作的展望在第五部分。
II。确定性有限自动机
一个确定性有限自动机M是一种自动识别装置[ 3 ]。它由： 1。一组有限的状态，往往表示为Q。
2。一个有限的输入符号集合，经常表
示为Σ。它通常被称为一个条件组。
function is commonly denoted F. In the diagram representation of automata, F is represented by arcs between states and labels on the arcs. If q ∈Q is a state, and s is an input symbol, then F (q,s)=p(p∈Q)and there is an arc labeled s from q to p. 4. A start state q0, q0 Q.
5. A set of final or accepted states Z, Z∈ Q.
A deterministic finite automaton M is abbreviated as DFA. It is often defined as a five-tuple:
M=(Q, Σ，F, q0, Z)
Where Q is a finite state set and it is not empty. One element of set Q presents a state of the system. Consists of all conditions occurred in the system and it may represent the running of a program, the happening of an attack or another event. F: Q Q?it is a function with a single value, For q Q and s?there exists a state p Q, p is equal to F (q,s). Q0 is only one start state of the system. Z ∈ Q, it is a set of final or accepted states.
As described above, the state of a computer system can be described with deterministic finite automata. It is supposed that there are m states in set Q and there are n transition conditions in set. Then there are m state nodes at most in the corresponding DFA. Each state node can be transferred to n neighbor nodes at most. The whole state transition procedure of a computer system can be described directly with the state transition diagram.
III. THE FORMAL DESCRIPTION OF SOME TYPICAL NETWORK ATTACKS Network attacks are complicated generally. Their feature and mechanism may be very different. So it is difficult to use a uniform model to describe various different attacks. In order to find the common features of different network attacks deterministic finite automata are used to
3。一个转换函数以一个状态和一个输入符号作为参数并返回另一个状态（或自己）。转换函数通常用F表示，用自动机图表示，F代表基于状态和标签之间的弧。如果一个状态是q＜Q，且S∈Σ，是一个输入符号，则F（Q，S）= P（P∈Q）并且有一条标记为从q到p的弧s。
4。一开始状态q0， q0∈Q
5。一组最终或公认的状态Z，Z∈Q。 一个确定性有限自动机M简称DFA。它通常被定义为一五元组：
M=(Q, Σ，F, q0, Z)
其中Q是一个有限状态集，它不是空的。一个元素的集合Q提出了一个系统的状态。Σ包括所有的发生在系统中的所有条件，它可能代表一个程序的运行，一个攻击或其他事件的发生。F：Q*Σ->Q，它是一个单值函数，q∈Q，s∈Σ，存在一个状态p∈Q，p= F(q,s)。 q0是唯一一个系统启动状态，Z∈Q，这是一套最终或可接受状态。
如上所述，一个计算机系统的状态可以用确定性有限自动机描述。认为在集合Q有m个状态和在集合∑有N个转换条件，然后有m个状态节点的相应的DFA。每个状态的节点最多可以转移到N的邻居节点。一个计算机系统的整个状态转换步骤可以用状态转换图直接描述。
III、一些典型的网络攻击的形式化描述
网络攻击比较复杂。他们的特征和机制可能会很不一样。所以很难用一个统一的模型来描述各种不同的攻击。为了找到不同网络攻击的确定性的共同特点，有限自动机被用来描述一些典型的攻击步骤。
describe
some
typical
attack
procedures.
For a DFA model M=（Q,Σ, F, q0, Z） which is corresponding to a different attack
procedure, the system state Q may represent
different meanings. It can be used to describe the states of hosts which are monitored, the
states of processes, and so on. The condition
set is called as the transition function. It is the cluster of functions and it consists of attack functions, communication functions, feature judgement functions, and so on. During the happening of attacks some
functions are activated, the system transfers
from one state to another state. For different attack procedures each component of DFA
model may be different.
When the DFA model is used the caught data packet and log file are analyzed
and audited, some feature parameters are got and they are used to judge whether the system is abnormal or there exist intrusion
behaviors. With system running a state
transition diagram is generated from the start state to the end state. What has
happened to the system can be got by
analyzing its end state. Some automaton models about typical network attacks (e.g.
SYN-Flooding attack) are given as follows.
A. SYN-Flooding Attack
TCP is an oriented connection protocol in Internet architecture. When two nodes want to communicate each other, they set up their connection at first by three handshake procedure. It is supposed that host A want to access the resource of server B, then host A must set up the connection with server B before their exchanging information. The detail procedure is shown as Fig. 1. At first, host A send a connection
request packet with SYN mark to server B. This packet consists of the initial
一个DFA模型（Q,Σ, F, q0, Z）是对应于一个不同的攻击步骤，系统
状态Q可能代表不同的含义。它可以
用来描述所监控主机的状态，进程的
状态，等等。设定的条件被称为转移函数。它是功能群并且它由攻击功能，
通信功能，特征判断功能组成，等等。
在攻击的一些功能被激活的时候，该系统从一个状态转移到另一种状态。
针对不同的攻击步骤的DFA模型的每
个组件可能是不同的。 当DFA模型采用了数据包的日志
文件分析和审计的一些特征参数，得到他们用来判断系统是否存在异常或
入侵行为。系统的运行状态转换图产
生自从开始状态到最终状态。对系统
所发生的一切都可以通过分析结束状态获得。对典型的网络攻击的一些自
动机模型（例如SYN泛洪攻击）如下。
在网络体系结构中A. SYN泛洪攻击TCP是一种面
向连接得协议。当两个节点要互相交流，他们在第一三次握手过程建立连接。假设，主机A要访问服务器B的资源，在他们的信息交换信息之前，主机A必须与服务器B建立连接。具体过程如图1所示。首先，首先主机A发送一个连接请求包到服务器B。该包包括主机A 的初始序列号x。
serial number x of host A. After server B receives this request packet its state is transferred to SYN.RCVD and it allocates the corresponding resource for this connection.
Then Server B sends the ACK packet with SYN/ACK mark to host A and this data packet consists of the initial serial number y of server B. It is obvious that the ACK serial number is x+1. At this moment the state of the system is called as the semi-connection state. After host A receives the SYN/ACK packet it sends the ACK packet to server B again. The ACK serial number in this packet is y+1. Server B receives the ACK packet and its state is transferred to “established”. The connection is set up at this moment and host A can exchange information with server B[4-5].
Figure 1. Setting up the connection between host A and server
The procedure of setting up connection mentioned above is the normal situation for TCP protocol. But after server B sends SYN/ACK packet to host a, it maybe not receive the responsive packet from host A for a long time. Then server B has to wait for a moment. If such semi-connection exceeds a certain amount it is possible to use up all system resources(e.g. buffers) of server B which is used to set up the connection between server B and other nodes. Once the resource of server B is exhausted other normal connection requests for server B cannot be responded. Denial of Service (DoS) attack happens. This is the basic theorem of SYN-Flooding attack.
在服务器B接收到该请求包之后它的状态转移到SYN.RCVD并且为该连接分配相应的资源。
然后服务器B发送标记SYN/ACK的ACK包给主机A，这个数据包包括服务器B的初始序列号Y。很明显，确认序号是x + 1。此时，系统的状态被称为半连接状态。然后主机A收到SYN/ACK包再次发送ACK包给主机B。这个包里的ACK序列号是y+1。B服务器接收ACK包及其状态转移到“建立”。 在这一刻连接被建立，主机A可以与服务器B [4-5]交换信息。
图1。建立了主机A和B服务器之间的连接
上述建立连接锁提到的步骤就是TCP协议正常的情况。但在服务器B发送SYN / ACK包到主机A，它也许在一个相当长的时间内没有从主机A收到响应数据包。然后服务器B等待一段时间。如果这些半连接超过一定量时可以使用服务器B的所有用于设置服务器B和其他节点之间的连接的系统资源（例如，缓存）。一旦服务器B的资源枯竭，其他正常的连接请求服务器B就不能回应。拒绝服务（DoS）攻击发生。这是SYN泛洪攻击的基本定理。