diff options
Diffstat (limited to 'doc/rfc/rfc963.txt')
| -rw-r--r-- | doc/rfc/rfc963.txt | 1083 |
1 files changed, 1083 insertions, 0 deletions
diff --git a/doc/rfc/rfc963.txt b/doc/rfc/rfc963.txt new file mode 100644 index 0000000..d4316fa --- /dev/null +++ b/doc/rfc/rfc963.txt @@ -0,0 +1,1083 @@ + + +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 + is the last fragment, since the routine reassembly, which actually + sets these bits, has not yet been called for this fragment. This + statement must therefore skip the bits corresponding to the + incoming fragment. In specifying the range to be tested, + allowance must be made for whether these bits fall at the + beginning of the bit map or in the middle (the case where they + fall at the end has already been tested). The statement must + therefore be changed to read + + if from_SNP.dtgm.fragment_offset = 0 then + if (all reassembly map from + from_SNP.dtgm.fragment_offset + + ((from_SNP.dtgm.total_length - + from_SNP.dtgm.header_length * 4) + 7) / 8 + to ((state_vector.total_data_length + 7) / 8 - 1) is set) + then return YES; + else return NO; + end if; + + else + if (all reassembly map from 0 to + (from_SNP.dtgm.fragment_offset - 1) is set) + and (all reassembly map from + from_SNP.dtgm.fragment_offset + + ((from_SNP.dtgm.total_length - + from_SNP.dtgm.header_length * 4) + 7) / 8 + to ((state_vector.total_data_length + 7) / 8 - 1) is set) + then return YES; + else return NO; + end if; + end if; + + + + +Sidhu [Page 7] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + Note that here again it is necessary to subtract 1 from the upper + bound. + + Problem 4: Errors in fragment_and_send + + The action procedure fragment_and_send [MILS83a, sec 9.4.6.3.7] is + used to break up datagrams that are too large to be sent through + the subnetwork as a single packet. The specification requires + [MILS83a sec 9.2.2, sec 9.4.6.3.7] each fragment, except possibly + the "tail" fragment, to contain a whole number of 8-octet groups + (called "blocks"); moreover, each fragment must begin at a block + boundary. + + In the algorithm set forth in fragment_and_send, all fragments + except the tail fragment are set to the same size; the procedure + begins by calculating this size. This is done by the following + statement: + + data_per_fragment := maximum subnet transmission unit + - (20 + number of bytes of option data); + + Besides the failure to allow for header padding, which is + discussed in the next section, this statement makes the serious + error of not assuring that the result is an integral multiple of + the block size, i.e., a multiple of eight octets. The consequence + of this would be that as many as seven octets per fragment would + never be sent at all. To correct this problem, and to allow for + header padding, this statement must be changed to + + data_per_fragment := (maximum subnet transmission unit + - (((20 + number of bytes of option data)+3)/4*4)/8*8; + + Another problem in this procedure is the failure to provide for + the case in which the length of the data is an exact multiple of + eight. The procedure contains the statements + + number_of fragments := (from_ULP.length + + (data_per_fragment - 1)) / data_per_fragment; + + data_in_last_frag := from_ULP.length modulo data_per_fragment; + + (Note that in our terminology we would rename data_in_last_frag as + data_in_tail_frag; notice, also, that the proper spelling of the + Ada operator is mod [ADA83, sec 4.5.5].) + + If data_in_last_frag is zero, some serious difficulties arise. + One result might be that the datagram will be broken into one more + + +Sidhu [Page 8] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + fragment than necessary, with the tail fragment containing no data + bytes. The assignment of data into the tail fragment will succeed + even though it will now take the form + + output_data [i..i-1] := input_data [j..j-1]; + + because Ada makes provision for so-called "null slices" [ADA83, + sec 4.1.2] and will treat this assignment as a no-op [ADA83, sec + 5.2.1]. + + This does, however, cause the transmission of an unnecessary + packet, and also creates difficulties for the reassembly + procedure, which must now be prepared to handle empty packets, for + which not even one bit of the reassembly map should be set. + Moreover, as the procedure is now written, even this will not + occur. This is because the calculation of the number of fragments + is incorrect. + + A numerical example will clarify this point. Suppose that the + total datagram length is 16 bytes and that the number of bytes per + fragment is to be 8. Then the above statements will compute + number_of_fragments = (16 + 7)/8 = 2 and data_in_last_frag = 16 + mod 8 = 0. The result of the inconsistency between + number_of_fragments and data_in_last_frag will be that instead of + sending three fragments, of lengths 8, 8, and 0, the procedure + will send only two fragments, of lengths 8 and 0; the last eight + octets will never be sent. + + To avoid these difficulties, the specification should add the + following statement, immediately after computing + data_in_last_frag: + + if data_in_last_frag = 0 then + data_in_last_frag := data_per_fragment; + end if; + + This procedure also contains several minor errors. In addition to + failures to account for packet header padding, which are + enumerated in the next section, there is a failure to convert the + header length from words (four octets) to octets in one statement. + This statement, which calculates the total length of the non-tail + fragments, is + + to_SNP.dtgm.total_length := to_SNP.dtgm.header_length + + data_per_fragment; + + + + +Sidhu [Page 9] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + Since header length is expressed in units of words, this + statement should read + + to_SNP.dtgm.total_length := to_SNP.dtgm.header_length * 4 + + data_per_fragment; + + This is apparently no more than a misprint, since the + corresponding calculation for the tail fragment is done correctly. + + Problem 5: Errors in reassembly + + The action procedure reassembly [MILS83a, sec 9.4.6.3.9], which is + referred to as reassemble elsewhere in the specification [MILS83a, + sec 9.4.6.1.2, sec 9.4.6.1.3], inserts an incoming fragment into a + datagram being reassembled. This procedure contains several + relatively minor errors. + + In two places in this procedure, a range is written to contain one + more member than it ought to have. In the first, data from the + fragment is to be inserted into the datagram being reassembled: + + state_vector.data [from_SNP.dtgm.fragment_offset*8 .. + from_SNP.dtgm.fragment_offset*8 + data_in_frag] := + from_SNP.dtgm.data [0..data_in_frag-1]; + + In this statement, the slice on the left contains one more byte + than the slice on the right. This will cause a run-time exception + to be raised [ADA83, sec 5.2.1]. The statement should read + + state_vector.data [from_SNP.dtgm.fragment_offset*8 .. + from_SNP.dtgm.fragment_offset*8 + data_in_frag - 1] := + from_SNP.dtgm.data [0..data_in_frag-1]; + + A similar problem occurs in the computation of the range of bits + in the reassembly map that corresponds to the incoming fragment. + This statement begins + + for j in (from_SNP.dtgm.fragment_offset) .. + ((from_SNP.dtgm.fragment_offset + + data_in_frag + 7)/8) loop + + Not only are the parentheses in this statement located incorrectly + (because the function f(x) = (x + 7) / 8 should be executed only + on the argument data_in_frag), but also this range contains one + extra member. The statement should read + + + + +Sidhu [Page 10] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + for j in (from_SNP.dtgm.fragment_offset) .. + (from_SNP.dtgm.fragment_offset + + (data_in_frag + 7)/8) - 1 loop + + Note that if the statement is corrected in this manner it will + also handle the case of a zero-length fragment, mentioned above, + since the loop will not be executed even once [ADA83, sS 5.5]. + + Another minor problem occurs when this procedure attempts to save + the header of the leading fragment. The relevant statement is + + state_vector.header := from_SNP.dtgm; + + This statement attempts to transfer the entire incoming fragment + into a record that is big enough to contain only the header. The + result, in Ada, is not truncation, but a run-time exception + [ADA83, sec 5.2]. The correction should be something like + + state_vector.header := from_SNP.dtgm.header; + + This correction cannot be made without also defining the header + portion of the datagram as a subrecord in [MILS83a, sec 9.4.4.6]; + such a definition would also necessitate changing many other + statements. For example, from_SNP.dtgm.fragment_offset would now + have to be written as from_SNP.dtgm.header.fragment_offset. + Another possible solution is to write the above statement as a + series of assignments for each field in the header, in the + following fashion: + + state_vector.header.version := + from_SNP.dtgm.version; + state_vector.header.header_length := + from_SNP.dtgm.header_length; + state_vector.header.type_of_service := + from_SNP.dtgm.type_of_service; + + -- etc. + + Note also that this procedure will fail if an incoming fragment, + other than the tail fragment, does not contain a multiple of eight + characters. Implementors must be careful to check for this in the + decision function SNP_params_valid [MILS83a, sec 9.4.6.2.7]. + + + + + + + +Sidhu [Page 11] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + Problem 6: Incorrect Data Length for Fragmented Datagrams + + The procedure reassembled_delivery [MILS83a, sec 9.4.6.3.10] does + not deliver the proper data length to the upper-level protocol. + This is because the assignment is + + to_ULP.length := state_vector.header.total_length + - state_vector.header.header_length * 4; + + The fields in state_vector.header have been filled in by the + reassembly procedure, discussed above, by copying the header of + the leading fragment. The field total_length in this fragment, + however, refers only to this particular fragment, and not to the + entire datagram (this is not entirely clear from it definition in + [MILS83a, sec 9.3.4], but the fragment_and_send procedure + [MILS83a, sec 9.4.6.3.7] insures that this is the case). + + The length of the entire datagram can only be computed from the + length and offset of the tail fragment. This computation is + actually done in the reassembly procedure [MILS83a, sec + 9.4.6.3.9], and the result saved in state_vector.total_data_length + (see above). It is impossible, however, for reassembly to fill in + state_vector.header.total_length at this time, because + state_vector.header.header_length is filled in from the lead + fragment, which may not yet have been received. + + Therefore, reassembled_delivery must replace the above statement + with + + to_ULP.length := state_vector.total_data_length; + + The consequence of leaving this error uncorrected is that the + upper-level protocol will be informed only of the delivery of as + many octets as there are in the lead fragment. + +5. Implementation Difficulties of MIL Standard IP + + In addition to the problems discussed above, there are several + features of the MIL standard IP specification [MILS83a] which lead to + difficulties for the implementor. These difficulties, while not + actually errors in the specification, take the form of assumptions + which are not explicitly stated, but of which implementors must be + aware. + + + + + + +Sidhu [Page 12] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + 5.1 Header Padding + + In several places, the specification makes a computation of the + length of a packet header without explicitly allowing for padding. + The padding is needed because the specification requires [MILS83a, + sec 9.3.14] that each header end on a 32-bit boundary. + + One place this problem arises is in the need_to_frag decision + function [MILS83a, sec 9.4.6.2.5]. This function is used to + determine whether fragmentation is required for an outgoing + datagram. It consists of the single statement + + if ((from_ULP.length + (number of bytes of option data) + + 20) > maximum transmission unit of the local subnetwork + then return YES + else return NO; + end if; + + (A minor syntax error results from not terminating the first + return statement with a semicolon [ADA83, sec 5.1, sec 5.3, sec + 5.9].) In order to allow for padding, the expression for the + length of the outgoing datagram should be + + (((from_ULP.length + (number of bytes of option data) + 20) + + 3)/4 * 4) + + Another place that this problem arises is in the action procedure + build_and_send [MILS83a, sec 9.4.6.3.2], which prepares + unfragmented datagrams for transmission. To compute the header + field header_length, which is expressed in words, i.e., units of + four octets [MILS83a, sec 9.3.2], this procedure contains the + statement + + to_SNP.dtgm.header_length := 5 + + (number of bytes of option data)/4; + + In order to allow for padding, this statement should read + + to_SNP.dtgm.header_length := + 5 + ((number of bytes of option data)+3)/4; + + The identical statement appears in the action procedure + fragment_and_send [MILS83a, sec 9.4.6.3.7], which prepares + datagram fragments for transmission, and requires the same + correction. + + + + +Sidhu [Page 13] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + The procedure fragment_and_send also has this problem in two other + places. In the first, the number of octets in each fragment is + computed by + + data_per_fragment := maximum subnet transmission unit + - (20 + number of bytes of option data); + + In order to allow for padding, this statement should read + + data_per_fragment := maximum subnet transmission unit + - (((20 + number of bytes of option data)+3)/4*4); + + (Actually, this statement must be changed to + + data_per_fragment := (maximum subnet transmission unit + - (((20 + number of bytes of option data)+3)/4*4)/8*8; + + in order to accomplish its intended purpose, for reasons which + have been discussed above.) + + A similar problem occurs in the statement which computes the + header length for individual fragments: + + to_SNP.dtgm.header_length := 5 + + (number of copy options octets/4); + + To allow for padding, this should be changed to + + to_SNP.dtgm.header_length := 5 + + (number of copy options octets+3/4); + + Notice that all of these errors can also be corrected if the + English phrase "number of bytes of option data", and similar + phrases, are always understood to include any necessary padding. + + 5.2 Subnetworks with Small Transmission Sizes + + When an outgoing datagram is too large to be transmitted as a + single packet, it must be fragmented. On certain subnetworks, the + possibility exists that the maximum number of bytes that may be + transmitted at a time is less than the size of an IP packet header + for a given datagram. In this case, the datagram cannot be sent, + even in fragmented form. Note that this does not necessarily mean + that the subnetwork cannot send any datagrams at all, since the + size of the header may be highly variable. When this problem + arises, it should be detected by IP. The proper place to detect + this situation is in the function can_frag. + + +Sidhu [Page 14] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + The can_frag decision function [MILS83a, sec 9.4.6.2.2] is used to + determine whether a particular outgoing datagram, which is too + long to be transmitted as a single fragment, is allowed to be + fragmented. In the current specification, this function consists + of the single statement + + if (from_ULP.dont_fragment = TRUE) + then return NO + else return YES + end if; + + (A minor syntax error is that the return statements should be + terminated by semicolons; see [ADA83, sec 5.1, sec 5.3, sec 5.9].) + + If the above problem occurs, the procedure fragment_and_send will + obtain negative numbers for fragment sizes, with unpredictable + results. This should be prevented by assuring that the subnetwork + can send the datagram header and at least one block (eight octets) + of data. The can_frag function should be recoded as + + if ((8 + ((number of bytes of option data)+3)/4*4 + 20) + > maximum transmission unit of the local subnetwork) + then return NO; + elsif (from_ULP.dont_fragment = TRUE) + then return NO + else return YES + end if; + + This is similar to the logic of the function need_to_frag, + discussed above. + + 5.3 Subnetwork Interface + + Provision is made for the subnetwork to report errors to IP + [MILS83a, sec 6.3.6.2], but no provision is made for the IP entity + to take any action when such errors occur. + + In addition, the specification [MILS83a, sec 8.2.1.1] calls for + the subnetwork to accept type-of-service indicators (precedence, + reliability, delay, and throughput), which may be difficult to + implement on many local networks. + + + + + + + + +Sidhu [Page 15] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + 5.4 ULP Errors + + The IP specification [MILS83a, sec 9.4.6.3.6] states + + The format of error reports to a ULP is implementation + dependent. However, included in the report should be a value + indicating the type of error, and some information to identify + the associated data or datagram. + + The most natural way to provide the latter information would be to + return the datagram identifier to the upper-level protocol, since + this identifier is normally supplied by the sending ULP [MILS83a, + sec 9.3.5]. However, the to_ULP data structure makes no provision + for this information [MILS83a, sec 9.4.4.3], probably because this + information is irrelevant for datagrams received from the + subnetwork. Implementors may feel a need to add this field to the + to_ULP data structure. + + 5.5 Initialization of Data Structures + + The decision function reass_done [MILS83a, sec 9.4.6.2.6] makes + the implicit assumption that data structures within each finite + state machine are initialized to zero when the machine is created. + In particular, this routine will not function properly unless + state_vector.reassembly_map and state_vector.total_data_length are + so initialized. Since this assumption is not stated explicitly, + implementors should be aware of it. There may be other + initialization assumptions that we have not discovered. + + 5.6 Locally Defined Types + + The procedures error_to_source [MILS83a, sec 9.4.6.3.5] and + error_to_ULP [MILS83a, sec 9.4.6.3.6] define enumeration types in + comments. The former contains the comment + + error_param : (PARAM_PROBLEM, EXPIRED_TTL, PROTOCOL_UNREACH); + + and the latter + + error_param : (PARAM_PROBLEM, CAN'T_FRAGMENT, NET_UNREACH, + PROTOCOL_UNREACH, PORT_UNREACH); + + These enumerated values are used before they are encountered + [MILS83a, sec 9.4.6.1.1, sec 9.4.6.1.2, sec 9.4.6.1.3, et al.]; + implementors will probably wish to define some error type + globally. + + + +Sidhu [Page 16] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + 5.7 Miscellaneous Difficulties + + The specification contains many Ada syntax errors, some of which + have been shown above. We have only mentioned syntax errors + above, however, when they occurred in conjunction with other + problems. One of the main syntactic difficulties that we have not + mentioned is that the specification frequently creates unnamed + types, by declaring records within records; such declarations are + legal in Pascal, but not in Ada [ADA83, sec 3.7]. + + Another problem is that slice assignments frequently do not + contain the same number of elements on the left and right sides, + which will raise a run-time exception [ADA83, sec 5.2.1]. While + we have mentioned some of these, there are others which are not + enumerated above. + + In particular, the procedure error_to_source [MILS83a, sec + 9.4.6.3.5] contains the statement + + to_SNP.dtgm.data [8..N+3] := from_SNP.dtgm.data [0..N-1]; + + We believe that N+3 is a misprint for N+8, but even so the left + side contains one more byte than the right. Implementors should + carefully check every slice assignment. + +6. An Implementation of MIL Standard IP + + In our discussion above, we have pointed out several serious problems + with the Military Standard IP [MILS83a] specification which must be + corrected to produce a running implementation conforming to this + standard. We have produced a running C implementation for the MIL + Standard IP, after problems discussed above were fixed in the IP + specification. An important feature of this implementation is that + it was generated semi-automatically from the IP specification with + the help of a protocol development system [BLUT82] [BLUT83] [SIDD83]. + Since this implementation was derived directly from the IP + specification with the help of tools, it conforms to the IP standard + better that any handed-coded IP implementation can do. + + The problems pointed out in this paper with the current specification + of the MIL Standard IP [MILS83a] are based on an initial + investigation of the protocol. + + + + + + + +Sidhu [Page 17] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + +NOTES + + [1] Ada is a registered trademark of the U.S. Government - Ada Joint + Program Office. + + [2] d indicates a "don't care" condition. + +ACKNOWLEDGEMENTS + + The author extends his gratitude to Tom Blumer Michael Breslin, Bob + Pollack and Mark J. Vincenzes, for many helpful discussions. Thanks + are also due to B. Simon and M. Bernstein for bringing to author's + attention a specification of the DoD Internet Protocol during 1981-82 + when a detailed study of this protocol began. The author is also + grateful to Jon Postel and Carl Sunshine for several informative + discussions about DoD IP/TCP during the last few years. + +REFERENCES + + [ADA83] Military Standard Ada(R) Programming Language, United + States Department of Defense, ANSI/MIL-STD-1815A-1983, 22 + January 1983 + + [BLUT83] Blumer, T. P., and Sidhu, D. P., "Mechanical Verification + and Automatic Implementation of Communication Protocols," + to appear in IEEE Trans. Softw. Eng. + + [BLUT82] Blumer, T. P., and Tenney, R. L., "A Formal Specification + Technique and Implementation Method for Protocols," + Computer Networks, Vol. 6, No. 3, July 1982, pp. 201-217. + + [MILS83a] "Military Standard Internet Protocol," United States + Department of Defense, MIL-STD-1777, 12 August 1983. + + [MILS83b] "Military Standard Transmission Control Protocol," United + States Department of Defense, MIL-STD-1778, 12 August 1983. + + [POSJ81] Postel, J. (ed.), "DoD Standard Internet Protocol," Defense + Advanced Research Projects Agency, Information Processing + Techniques Office, RFC-791, September 1981. + + [SDC82] DCEC Protocol Standardization Program: Protocol + Specification Report, System Development Corporation, + TM-7172/301/00, 29 March 1982 + + [SIDD83] Sidhu, D. P., and Blumer, T. P., "Verification of NBS Class + 4 Transport Protocol," to appear in IEEE Trans. Comm. + + +Sidhu [Page 18] + + + +RFC 963 November 1985 +Some Problems with MIL-STD IP + + + [SIDD84] Sidhu, D. P., and Blumer, T. P., "Some Problems with the + Specification of the Military Standard Transmission Control + Protocol," in Protocol Specification, Testing and + Verification IV, (ed.) Y. Yemini et al (1984). + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Sidhu [Page 19] + |