rfc963.txt
来自「RFC 的详细文档！」· 文本 代码 · 共 1,084 行 · 第 1/3 页
TXT
1,084 行
Network Working Group Deepinder P. Sidhu
Request for Comments: 963 Iowa State University
November 1985
SOME PROBLEMS WITH THE SPECIFICATION OF THE
MILITARY STANDARD INTERNET PROTOCOL
STATUS OF THIS MEMO
The purpose of this RFC is to provide helpful information on the
Military Standard Internet Protocol (MIL-STD-1777) so that one can
obtain a reliable implementation of this protocol standard.
Distribution of this note is unlimited.
ABSTRACT
This paper points out several significant problems in the
specification of the Military Standard Internet Protocol
(MIL-STD-1777, dated August 1983 [MILS83a]). These results are based
on an initial investigation of this protocol standard. The problems
are: (1) a failure to reassemble fragmented messages completely; (2)
a missing state transition; (3) errors in testing for reassembly
completion; (4) errors in computing fragment sizes; (5) minor errors
in message reassembly; (6) incorrectly computed length for certain
datagrams. This note also proposes solutions to these problems.
1. Introduction
In recent years, much progress has been made in creating an
integrated set of tools for developing reliable communication
protocols. These tools provide assistance in the specification,
verification, implementation and testing of protocols. Several
protocols have been analyzed and developed using such tools.
Examples of automated verification and implementation of several real
world protocols are discussed in [BLUT82] [BLUT83] [SIDD83] [SIDD84].
We are currently working on the automatic implementation of the
Military Standard Internet Protocol (IP). This analysis will be
based on the published specification [MILS83a] of IP dated 12 August
1983.
While studying the MIL Standard IP specification, we have noticed
numerous errors in the specification of this protocol. One
consequence of these errors is that the protocol will never deliver
fragmented incoming datagrams; if this error is corrected, such
datagrams will be missing some data and their lengths will be
incorrectly reported. In addition, outgoing datagrams that are
divided into fragments will be missing some data. The proof of these
statements follows from the specification of IP [MILS83a] as
discussed below.
Sidhu [Page 1]
RFC 963 November 1985
Some Problems with MIL-STD IP
2. Internet Protocol
The Internet Protocol (IP) is a network layer protocol in the DoD
protocol hierarchy which provides communication across interconnected
packet-switched networks in an internetwork environment. IP provides
a pure datagram service with no mechanism for reliability, flow
control, sequencing, etc. Instead, these features are provided by a
connection-oriented protocol, DoD Transmission Control Protocol (TCP)
[MILS83b], which is implemented in the layer above IP. TCP is
designed to operate successfully over channels that are inherently
unreliable, i.e., which can lose, damage, duplicate, and reorder
packets.
Over the years, DARPA has supported specifications of several
versions of IP; the last one appeared in [POSJ81]. A few years ago,
the Defense Communications Agency decided to standardize IP for use
in DoD networks. For this purpose, the DCA supported formal
specification of this protocol, following the design discussed in
[POSJ81] and the technique and organization defined in [SDC82]. A
detailed specification of this protocol, given in [MILS83a], has been
adopted as the DoD standard for the Internet Protocol.
The specification of IP state transitions is organized into decision
tables; the decision functions and action procedures are specified in
a subset of Ada[1], and may employ a set of machine-specific data
structures. Decision tables are supplied for the pairs <state name,
interface event> as follows: <inactive, send from upper layer>,
<inactive, receive from lower layer>, and <reassembling, receive from
lower layer>. To provide an error indication in the case that some
fragments of a datagram are received but some are missing, a decision
table is also supplied for the pair <reassembling, reassembly time
limit elapsed>. (The event names are English descriptions and not
the names employed by [MILS83a].)
3. Problems with MIL Standard IP
One of the major functions of IP is the fragmentation of datagrams
that cannot be transmitted over a subnetwork in one piece, and their
subsequent reassembly. The specification has several problems in
this area. One of the most significant is the failure to insert the
last fragment of an incoming datagram; this would cause datagrams to
be delivered to the upper-level protocol (ULP) with some data
missing. Another error in this area is that an incorrect value of the
data length for reassembled datagrams is passed to the ULP, with
unpredictable consequences.
As the specification [MILS83a] is now written, these errors are of
Sidhu [Page 2]
RFC 963 November 1985
Some Problems with MIL-STD IP
little consequence, since the test for reassembly completion will
always fail, with the result that reassembled datagrams would never
be delivered at all.
In addition, a missing row in one of the decision tables creates the
problem that network control (ICMP) messages that arrive in fragments
will never be processed. Among the other errors are the possibility
that a few bytes will be discarded from each fragment transmitted and
certain statements that will create run-time exceptions instead of
performing their intended functions.
A general problem with this specification is that the program
language and action table portions of the specification were clearly
not checked by any automatic syntax checking process. Variable and
procedure names are occasionally misspelled, and the syntax of the
action statements is often incorrect. We have enumerated some of
these problems below as a set of cautionary notes to implementors,
but we do not claim to have listed them all. In particular, syntax
errors are only discussed when they occur in conjunction with other
problems.
The following section discusses some of the serious errors that we
have discovered with the MIL standard IP [MIL83a] during our initial
study of this protocol. We also propose corrections to each of these
problems.
4. Detailed Discussion of the Problems
Problem 1: Failure to Insert Last Fragment
This problem occurs in the decision table corresponding to the
state reassembling and the input "receive from lower layer"
[MILS83a, sec 9.4.6.1.3]. The problem occurs in the following row
of this table:[2]
________________________________________________________
check- SNP TTL where a reass ICMP
sum params valid to frag done check-
valid? valid? ? ? ? ? sum?
__________________________________________________________________
YES YES YES ULP YES YES d reass_
delivery;
state :=
INACTIVE
__________________________________________________________________
The reass_done function, as will be seen below, returns YES if the
Sidhu [Page 3]
RFC 963 November 1985
Some Problems with MIL-STD IP
fragment just received is the last fragment needed to assemble a
complete datagram and NO otherwise. The action procedure
reass_delivery simply delivers a completely reassembled datagram
to the upper-level protocol. It is the action procedure
reassemble that inserts an incoming fragment into the datagram
being assembled. Since this row does not call reassemble, the
result will be that every incoming fragmented datagram will be
delivered to the upper layer with one fragment missing. The
solution is to rewrite this row of the table as follows:
________________________________________________________
check- SNP TTL where a reass ICMP
sum params valid to frag done check-
valid? valid? ? ? ? ? sum?
__________________________________________________________________
YES YES YES ULP YES YES d reassemble;
reass_
delivery;
state :=
INACTIVE
__________________________________________________________________
Incidentally, the mnemonic value of the name of the reass_done
function is questionable, since at the moment this function is
called datagram reassembly cannot possibly have been completed. A
better name for this function might be last_fragment.
Problem 2: Missing State Transition
This problem is the omission of a row of the same decision table
[MILS83a, sec 9.4.6.1.3]. Incoming packets may be directed to an
upper-level protocol (ULP), or they may be network control
messages, which are marked ICMP (Internet Control Message
Protocol). When control messages have been completely assembled,
they are processed by an IP procedure called analyze. The
decision table contains the row
________________________________________________________
check- SNP TTL where a reass ICMP
sum params valid to frag done check-
valid? valid? ? ? ? ? sum?
__________________________________________________________________
YES YES YES ICMP YES NO d reassemble;
__________________________________________________________________
Sidhu [Page 4]
RFC 963 November 1985
Some Problems with MIL-STD IP
but makes no provision for the case in which where_to returns
ICMP, a_frag returns YES, and reass_done returns YES. An
additional row should be inserted, which reads as follows:
________________________________________________________
check- SNP TTL where a reass ICMP
sum params valid to frag done check-
valid? valid? ? ? ? ? sum?
__________________________________________________________________
YES YES YES ICMP YES YES d reassemble;
analyze;
state :=
INACTIVE
__________________________________________________________________
Omitting this row means that incoming fragmented ICMP messages
will never be analyzed, since the state machine does not have any
action specified when the last fragment is received.
Problem 3: Errors in reass_done
The function reass_done, as can be seen from the above, determines
whether the incoming subnetwork packet contains the last fragment
needed to complete the reassembly of an IP datagram. In order to
understand the errors in this function, we must first understand
how it employs its data structures.
The reassembly of incoming fragments is accomplished by means of a
bit map maintained separately for each state machine. Since all
fragments are not necessarily the same length, each bit in the map
represents not a fragment, but a block, that is, a unit of eight
octets. Each fragment, with the possible exception of the "tail"
fragment (we shall define this term below), is an integral number
of consecutive blocks. Each fragment's offset from the beginning
of the datagram is given, in units of blocks, by a field in the
packet header of each incoming packet. The total length of each
fragment, including the fragment's header, is specified in the
header field total_length; this length is given in octets. The
length of the header is specified in the field header_length; this
length is given in words, that is, units of four octets.
In analyzing this subroutine, we must distinguish between the
"tail" fragment and the "last" fragment. We define the last
fragment as the one which is received last in time, that is, the
fragment that permits reassembly to be completed. The tail
fragment is the fragment that is spatially last, that is, the
fragment that is spatially located after any other fragment. The
Sidhu [Page 5]
RFC 963 November 1985
Some Problems with MIL-STD IP
length and offset of the tail fragment make it possible to compute
the length of the entire datagram. This computation is actually
done in the action procedure reassembly, and the result is saved
in the state vector field total_data_length; if the tail fragment
has not been received, this value is assumed to be zero.
It is the task of the reass_done function [MILS83a, sec 9.4.6.2.6]
to determine whether the incoming fragment is the last fragment.
This determination is made as follows:
1) If the tail fragment has not been received previously and
the incoming fragment is not the tail fragment, then return NO.
2) Otherwise, if the tail fragment has not been received, but
the incoming fragment is the tail fragment, determine whether
all fragments spatially preceding the tail fragment have also
been received.
3) Otherwise, if the tail fragment has been received earlier,
determine whether the incoming fragment is the last one needed
to complete reassembly.
The evaluation of case (2) is accomplished by the following
statment:
if (state_vector.reassembly_map from 0 to
(((from_SNP.dtgm.total_length -
(from_SNP.dtgm.header_length * 4) + 7) / 8)
+ 7) / 8 is set)
then return YES;
The double occurrence of the subexpression " + 7 ) / 8" is
apparently a misprint. The function f(x) = (x + 7) / 8 will
convert x from octets to blocks, rounding any remainder upward.
There is no need for this function to be performed twice. The
second problem is that the fragment_offset field of the incoming
packet is ignored. The tail fragment specifies only its own
length, not the length of the entire datagram; to determine the
latter, the tail fragment's offset must be added to the tail
fragment's own length. The third problem hinges on the meaning of
the English "... from ... to ..." phrase. If this phrase has the
same meaning as the ".." range indication in Ada [ADA83, sec 3.6],
that is, includes both the upper and lower bounds, then it is
necessary to subtract 1 from the final expression.
The expression following the word to, above, should thus be
changed to read
Sidhu [Page 6]
RFC 963 November 1985
Some Problems with MIL-STD IP
from_SNP.dtgm.fragment_offset +
((from_SNP.dtgm.total_length -
(from_SNP.dtgm.header_length * 4) + 7) / 8) - 1
Another serious problem with this routine occurs when evaluating
case (3). In this case, the relevant statement is
if (all reassembly map from 0 to
(state_vector.total_data_length + 7)/8 is set
then return YES
If the tail fragment was received earlier, the code asks, in
effect, whether all the bits in the reassembly map have been set.
This, however, will not be the case even if the incoming fragment
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?