| RFC : | rfc789 |
| Title: | |
| Date: | July 1981 |
| Status: | UNKNOWN |
RFC 789
Vulnerabilities of Network Control Protocols: An Example
Eric C. Rosen
Bolt Beranek and Newman Inc.
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
This paper has appeared in the January 1981 edition of the
SIGSOFT Software Engineering Notes, and will soon appear in the
SIGCOMM Computer Communications Review. It is being circulated
as an RFC because it is thought that it may be of interest to a
wider audience, particularly to the internet community. It is a
case study of a particular kind of problem that can arise in
large distributed systems, and of the approach used in the
ARPANET to deal with one such problem.
On October 27, 1980, there was an unusual occurrence on the
ARPANET. For a period of several hours, the network appeared to
be unusable, due to what was later diagnosed as a high priority
software process running out of control. Network-wide
disturbances are extremely unusual in the ARPANET (none has
occurred in several years), and as a result, many people have
expressed interest in learning more about the etiology of this
particular incident. The purpose of this note is to explain what
the symptoms of the problem were, what the underlying causes
were, and what lessons can be drawn. As we shall see, the
immediate cause of the problem was a rather freakish hardware
malfunction (which is not likely to recur) which caused a faulty
sequence of network control packets to be generated. This faulty
sequence of control packets in turn affected the apportionment of
software resources in the IMPs, causing one of the IMP processes
to use an excessive amount of resources, to the detriment of
other IMP processes. Restoring the network to operational
- 1 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
condition was a relatively straightforward task. There was no
damage other than the outage itself, and no residual problems
once the network was restored. Nevertheless, it is quite
interesting to see the way in which unusual (indeed, unique)
circumstances can bring out vulnerabilities in network control
protocols, and that shall be the focus of this paper.
The problem began suddenly when we discovered that, with
very few exceptions, no IMP was able to communicate reliably with
any other IMP. Attempts to go from a TIP to a host on some other
IMP only brought forth the "net trouble" error message,
indicating that no physical path existed between the pair of
IMPs. Connections which already existed were summarily broken.
A flood of phone calls to the Network Control Center (NCC) from
all around the country indicated that the problem was not
localized, but rather seemed to be affecting virtually every IMP.
As a first step towards trying to find out what the state of
the network actually was, we dialed up a number of TIPs around
the country. What we generally found was that the TIPs were up,
but that their lines were down. That is, the TIPs were
communicating properly with the user over the dial-up line, but
no connections to other IMPs were possible.
We tried manually restarting a number of IMPs which are in
our own building (after taking dumps, of course). This procedure
initializes all of the IMPs' dynamic data structures, and will
- 2 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
often clear up problems which arise when, as sometimes happens in
most complex software systems, the IMPs' software gets into a
"funny" state. The IMPs which were restarted worked well until
they were connected to the rest of the net, after which they
exhibited the same complex of symptoms as the IMPs which had not
been restarted.
From the facts so far presented, we were able to draw a
number of conclusions. Any problem which affects all IMPs
throughout the network is usually a routing problem. Restarting
an IMP re-initializes the routing data structures, so the fact
that restarting an IMP did not alleviate the problem in that IMP
suggested that the problem was due to one or more "bad" routing
updates circulating in the network. IMPs which were restarted
would just receive the bad updates from those of their neighbors
which were not restarted. The fact that IMPs seemed unable to
keep their lines up was also a significant clue as to the nature
of the problem. Each pair of neighboring IMPs runs a line
up/down protocol to determine whether the line connecting them is
of sufficient quality to be put into operation. This protocol
involves the sending of HELLO and I-HEARD-YOU messages. We have
noted in the past that under conditions of extremely heavy CPU
utilization, so many buffers can pile up waiting to be served by
the bottleneck CPU process, that the IMPs are unable to acquire
the buffers needed for receiving the HELLO or I-HEARD-YOU
messages. If a condition like this lasts for any length of time,
- 3 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
the IMPs may not be able to run the line up/down protocol, and
lines will be declared down by the IMPs' software. On the basis
of all these facts, our tentative conclusion was that some
malformed update was causing the routing process in the IMPs to
use an excessive amount of CPU time, possibly even to be running
in an infinite loop. (This would be quite a surprise though,
since we tried very hard to protect ourselves against malformed
updates when we designed the routing process.) As we shall see,
this tentative conclusion, although on the right track, was not
quite correct, and the actual situation turned out to be much
more complex.
When we examined core dumps from several IMPs, we noted that
most, in some cases all, of the IMPs' buffers contained routing
updates waiting to be processed. Before describing this
situation further, it is necessary to explain some of the details
of the routing algorithm's updating scheme. (The following
explanation will of course be very brief and incomplete. Readers
with a greater level of interest are urged to consult the
references.) Every so often, each IMP generates a routing update
indicating which other IMPs are its immediate neighbors over
operational lines, and the average per-packet delay (in
milliseconds) over that line. Every IMP is required to generate
such an update at least once per minute, and no IMP is permitted
to generate more than a dozen such updates over the course of a
minute. Each update has a 6-bit sequence number which is
- 4 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
advanced by 1 (modulo 64) for each successive update generated by
a particular IMP. If two updates generated by the same IMP have
sequence numbers n and m, update n is considered to be LATER
(i.e., more recently generated) than update m if and only if one
of the following two conditions hold:
(a) n > m, and n - m <= 32
(b) n < m, and m - n > 32
(where the comparisons and subtractions treat n and m as unsigned
6-bit numbers, with no modulus). When an IMP generates an
update, it sends a copy of the update to each neighbor. When an
IMP A receives an update u1 which was generated by a different
IMP B, it first compares the sequence number of u1 with the
sequence number of the last update, u2, that it accepted from B.
If this comparison indicates that u2 is LATER than u1, u1 is
simply discarded. If, on the other hand, u1 appears to be the
LATER update, IMP A will send u1 to all its neighbors (including
the one from which it was received). The sequence number of u1
will be retained in A's tables as the LATEST received update from
B. Of course, u1 is always accepted if A has seen no previous
update from B. Note that this procedure is designed to ensure
that an update generated by a particular IMP is received,
unchanged, by all other IMPs in the network, IN THE PROPER
SEQUENCE. Each routing update is broadcast (or flooded) to all
IMPs, not just to immediate neighbors of the IMP which generated
- 5 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
the update (as in some other routing algorithms). The purpose of
the sequence numbers is to ensure that all IMPs will agree as to
which update from a given IMP is the most recently generated
update from that IMP.
For reliability, there is a protocol for retransmitting
updates over individual links. Let X and Y be neighboring IMPs,
and let A be a third IMP. Suppose X receives an update which was
generated by A, and transmits it to Y. Now if in the next 100 ms
or so, X does not receive from Y an update which originated at A
and whose sequence number is at least as recent as that of the
update X sent to Y, X concludes that its transmission of the
update did not get through to Y, and that a retransmission is
required. (This conclusion is warranted, since an update which
is received and adjudged to be the most recent from its
originating IMP is sent to all neighbors, including the one from
which it was received.) The IMPs do not keep the original update
packets buffered pending retransmission. Rather, all the
information in the update packet is kept in tables, and the
packet is re-created from the tables if necessary for a
retransmission.
This transmission protocol ("flooding") distributes the
routing updates in a very rapid and reliable manner. Once
generated by an IMP, an update will almost always reach all other
IMPs in a time period on the order of 100 ms. Since an IMP can
generate no more than a dozen updates per minute, and there are
- 6 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
64 possible sequence numbers, sequence number wrap-around is not
a problem. There is only one exception to this. Suppose two
IMPs A and B are out of communication for a period of time
because there is no physical path between them. (This may be due
either to a network partition, or to a more mundane occurrence,
such as one of the IMPs being down.) When communication is
re-established, A and B have no way of knowing how long they have
been out of communication, or how many times the other's sequence
numbers may have wrapped around. Comparing the sequence number
of a newly received update with the sequence number of an update
received before the outage may give an incorrect result. To deal
with this problem, the following scheme is adopted. Let t0 be
the time at which IMP A receives update number n generated by IMP
B. Let t1 be t0 plus 1 minute. If by t1, A receives no update
generated by B with a LATER sequence number than n, A will accept
any update from B as being more recent than n. So if two IMPs
are out of communication for a period of time which is long
enough for the sequence numbers to have wrapped around, this
procedure ensures that proper resynchronization of sequence
numbers is effected when communication is re-established.
There is just one more facet of the updating process which
needs to be discussed. Because of the way the line up/down
protocol works, a line cannot be brought up until 60 seconds
after its performance becomes good enough to warrant operational
use. (Roughly speaking, this is the time it takes to determine
- 7 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
that the line's performance is good enough.) During this
60-second period, no data is sent over the line, but routing
updates are transmitted. Remember that every node is required to
generate a routing update at least once per minute. Therefore,
this procedure ensures that if two IMPs are out of communication
because of the failure of some line, each has the most recent
update from the other by the time communication is
re-established.
This very short introduction to the routing algorithm's
updating protocol should provide enough background to enable the
reader to understand the particular problem under discussion;
further justification and detail can be found in the references.
Let us return now to the discussion of the network outage.
I have already mentioned that the core dumps showed almost all
buffers holding routing updates which were waiting to be
processed. Close inspection showed that all the updates were
from a single IMP, IMP 50. By a strange "coincidence," IMP 50
had been malfunctioning just before the network-wide outage
occurred, and was off the net during the period of the outage.
Hence it was not generating any updates during the period of the
outage. In addition, IMP 29, an immediate neighbor of IMP 50,
was also suffering hardware malfunctions (in particular, dropping
bits), but was up (though somewhat flakey) while the network was
in bad shape. Furthermore, the malfunction in IMP 50 had to do
with its ability to communicate properly with the neighboring IMP
- 8 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
29. Although we did not yet understand how it was possible for
so many updates from one IMP to be extant simultaneously, we did
understand enough to be able to get the network to recover. All
that was necessary was to patch the IMPs to disregard any updates
from IMP 50, which after all was down anyway. When the network
is operating normally, broadcasting a patch to all IMPs can be
done in a matter of minutes. With the network operating as it
was during the period of the outage, this can take as much as 3
or 4 hours. (Remember that the IMPs are generally unmanned, and
that the only way of controlling them from the NCC is via the
network itself. This is perfectly satisfactory when an outage
affects only a small group of IMPs, but is an obvious problem
when the outage has network-wide effects.) This procedure was
fully successful in bringing the network back up.
When we looked closely at the dumps, we saw that not only
were all the updates on the queue from IMP 50, but they all had
one of three sequence numbers (either 8, 40, or 44), and were
ordered in the queue as follows:
8, 40, 44, 8, 40, 44, 8, 40, 44, ... Note that by the definition
of LATER, 44 is LATER than 40 (44 > 40 and 44 - 40 <= 32), 40 is
LATER than 8 (40 > 8 and 40 - 8 <= 32), and 8 is LATER than 44
(8 < 44 and 44 - 8 > 32). Given the presence of three updates
from the same IMP with these three sequence numbers, this is what
would be expected. Since each update is LATER than one of the
others, a cycle is formed which keeps the three updates floating
- 9 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
around the network indefinitely. Thus the IMPs spend most of
their CPU time and buffer space in processing these updates. The
problem was to figure out how these three updates could possibly
have existed at the same time. After all, getting from update 8
to update 40 should require 2 or 3 full minutes, plus 31
intervening sequence numbers. So how could 8 still be around
when 40 was generated, especially since no updates with
intervening sequence numbers were present?
Our first thought was that maybe the real-time clock in IMP
50 was running one or two orders of magnitude faster than normal,
invalidating our assumptions about the maximum number of updates
which could be generated in a given time. An alternative
hypothesis suggested itself however when we looked at the binary
representations of the three sequence numbers:
8 - 001000
40 - 101000
44 - 101100
Note that 44 has only one more bit than 40, which has only one
more bit than 8. Furthermore, the three different updates were
completely identical, except for their sequence numbers. This
suggests that there was really only one update, 44, whose
sequence number was twice corrupted by dropped bits. (Of course,
it's also possible that the "real" update was 8, and was
corrupted by added bits. However, bit-dropping has proven itself
- 10 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
to be a much more common sort of hardware malfunction than
bit-adding, although spontaneously dropped bits may sometimes
come back on spontaneously.)
Surely, the reader will object, there must be protection
against dropped bits. Yes there is protection, but apparently
not enough. The update packets themselves are checksummed, so a
dropped bit in an update packet is readily detected. Remember
though that if an update needs to be retransmitted, it is
recreated from tabled information. For maximal reliability, the
tables must be checksummed also, and the checksum must be
recomputed every time the table is accessed. However, this would
require either a large number of CPU cycles (for frequent
checksumming of a large area of memory) or a large amount of
memory (to store the checksums for a lot of small areas). Since
CPU cycles and memory are both potentially scarce resources, this
did not seem to us to be a cost-effective way to deal with
problems that arise, say, once per year (this is the first such
problem encountered in a year and a half of running this routing
algorithm). Time and space can be saved by recomputing the
checksum at a somewhat slower frequency, but this is less
reliable, in that it allows a certain number of dropped bits to
"fall between the cracks." It seems likely then that one of the
malfunctioning IMPs had to retransmit update 44 at least twice,
(recreating it each time from tabled information), retransmitting
it at least once with the corrupted sequence number 40, and at
- 11 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
least once with the corrupted sequence number 8. This would
cause those three sequence numbers to be extant in the network
simultaneously, even though protocol is supposed to ensure that
this is impossible.
Actually, the detection of dropped bits is most properly a
hardware function. The next generation of IMP hardware (the "C30
IMP") will be able to detect and correct all single-bit errors,
and will detect all other bit errors. Uncorrectable bit errors
will cause the IMP to go into its "loader/dumper." (An IMP in
its loader/dumper is not usable for transferring data, and is
officially in the "down" state. However, an IMP in its
loader/dumper is easily controllable from the NCC, and can be
restarted or reloaded without on-site intervention.) Current
hardware does have parity checking (which should detect single
dropped bits), but this feature has had to be turned off since
(a) there are too many spurious parity "errors," i.e., most of
the time when the machines complain of parity errors there don't
really seem to be any, and (b) parity errors cause the machines
to simply halt, rather than go into their loader/dumpers, which
means that on-site intervention is required to restart them.
Pending the introduction of improved hardware, what can be
done to prevent problems like this from recurring in the future?
It is easy to think of many ways of avoiding this particular
problem, especially if one does not consider the problems that
may arise from the "fixes." For example, we might be able to
- 12 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
avoid this sort of problem by spending a lot more CPU cycles on
checksumming, but this may be too expensive because of the side
effects it would introduce. (Also, it is not clear that any
memory checksumming strategy can be totally free of "cracks.") A
very simple and conservative fix to prevent this particular
problem from recurring is to modify clause (a) of the definition
of LATER so that the "<=" is replaced by "<" (strictly less
than). We will implement this fix, but it cannot be guaranteed
that no related problems will ever arise.
What is really needed is not some particular fix to the
routing algorithm, but a more general fix. In some sense, the
problem we saw was not really a routing problem. The routing
code was working correctly, and the routes that were generated
were correct and consistent. The real problem is that a freakish
hardware malfunction caused a high priority process to run wild,
devouring resources needed by other processes, thereby making the
network unusable. The fact that the wild process was the routing
process is incidental. In designing the routing process, we
carefully considered the amount of resource utilization it would
require. By strictly controlling and limiting the rate at which
updates can be generated, we tried to prevent any situation in
which the routing process would make excessive demands on the
system. As we have seen though, even our carefully designed
mechanisms were unable to protect against every possible sort of
hardware failure. We need a better means of detecting that some
- 13 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
high priority process in the IMP, despite all the safeguards we
have built in, is still consuming too many resources. Once this
is detected, the IMP can be automatically placed in its
loader/dumper. In the case under discussion, we would have liked
to have all the IMPs go into their loader/dumpers when the
problem arose. This would have enabled us to re-initialize and
restart all the IMPs much more quickly. (Although restarting
individual IMPs did little good, restarting all the IMPs
simultaneously would have cleared up the problem instantly, since
all routing tables in all IMPs would have been initialized
simultaneously.) It took us no more than an hour to figure out
how to restore the network; several additional hours were
required because it took so long for us to gain control of the
misbehaving IMPs and get them back to normal. A built-in
software alarm system (assuming, of course, that it was not
subject to false alarms) might have enabled us to restore the
network more quickly, significantly reducing the duration of the
outage. This is not to say that a better alarm and control
system could ever be a replacement for careful study and design
which attempts to properly distribute the utilization of
important resources, but only that it is a necessary adjunct, to
handle the cases that will inevitably fall between the cracks of
even the most careful design.
- 14 -
RFC 789 Bolt Beranek and Newman Inc.
Eric C. Rosen
REFERENCES
"The New Routing Algorithm for the ARPANET," IEEE TRANSACTIONS ON
COMMUNICATIONS, May 1980, J.M. McQuillan, I. Richer, E.C. Rosen.
"The Updating Protocol of ARPANET's New Routing Algorithm,"
COMPUTER NETWORKS, February 1980, E.C. Rosen.
- 15 -