This paper establishes a fundamental theory of secure clock synchronization. Accurate clock synchronization is the backbone of systems managing power distribution, financial transactions, telecommunication operations, database services, etc. Some clock synchronization (time transfer) systems, such as the global navigation satellite systems, are based on one-way communication from a master to a slave clock. Others, such as the network transport protocol, and the IEEE 1588 precision time protocol (PTP), involve two-way communication between the master and slave. This paper shows that all one-way time transfer protocols are vulnerable to replay attacks that can potentially compromise timing information. A set of conditions for secure two-way clock synchronization is proposed and proved to be necessary and sufficient. It is shown that IEEE 1588 PTP, although a two-way synchronization protocol, is not compliant with these conditions, and is therefore insecure. Requirements for secure IEEE 1588 PTP are proposed, and a second example protocol is offered to illustrate the range of compliant systems.
The work presented in @cite_11 is perhaps in closest relation to the current paper. upper bound the clock drift between subsequent synchronization signals using a drift model, and perform two-way exchange of timestamps such that the master clock is able to verify the time at the slave. Furthermore, given the maximum clock drift rate and the maximum and minimum propagation delay of the timing signal, they derive an upper bound on the adversarial delay that can go unnoticed. However, with conservative bounds on the maximum clock drift rate and the variation in path delays, the accuracy guarantees derived in @cite_11 may be insufficient for certain applications. Moreover, as will be shown in this paper, they fail to take account of one the necessary conditions for secure synchronization.
@cite_11
1970745521 2143229717 1994441984 2114925953
We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors never fail is too optimistic. To cope with this reality, we suggest self-stabilizing protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol. Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale networks of small, wireless, low-power sensors and actuators. Time synchronization is critical in sensor networks for diverse purposes including sensor data fusion, coordinated actuation, and power-efficient duty cycling. Though the clock accuracy and precision requirements are often stricter than in traditional distributed systems, strict energy constraints limit the resources available to meet these goals.We present Reference-Broadcast Synchronization, a scheme in which nodes send reference beacons to their neighbors using physical-layer broadcasts. A reference broadcast does not contain an explicit timestamp; instead, receivers use its arrival time as a point of reference for comparing their clocks. In this paper, we use measurements from two wireless implementations to show that removing the sender's nondeterminism from the critical path in this way produces high-precision clock agreement (1.85 ± 1.28μsec, using off-the-shelf 802.11 wireless Ethernet), while using minimal energy. We also describe a novel algorithm that uses this same broadcast property to federate clocks across broadcast domains with a slow decay in precision (3.68 ± 2.57μsec after 4 hops). RBS can be used without external references, forming a precise relative timescale, or can maintain microsecond-level synchronization to an external timescale such as UTC. We show a significant improvement over the Network Time Protocol (NTP) under similar conditions. Abstract We describe a new fault-tolerant algorithm for solving a variant of Lamport's clock synchronization problem. The algorithm is designed for a system of distributed processes that communicate by sending messages. Each process has its own read-only physical clock whose drift rate from real time is very small. By adding a value to its physical clock time, the process obtaines its local time. The algorithm solves the problem of maintaining closely synchronized local times, assuming that processes' local times are closely synchronized initially. The algorithm is able to tolerate the failure of just under one-third of the participating processes. It maintains synchronization to within a small constant, whose magnitude depends upon the rate of clock drift, the message delivery time and its uncertainty, and the initial closeness of synchronization. We also give a characterization of how far the clocks drift from real time. Reintegration of a repaired process can be accomplished using a slight modification of the basic alborithm. A similar style algorithm can also be used to achieve synchronization initially. The power of two well-known consistency conditions for shared-memory multiprocessors, sequential consistency and linearizability , is compared. The cost measure studied is the worst-case response time in distributed implementations of virtual shared memory supporting one of the two conditions. Three types of shared-memory objects are considered: read write objects, FIFO queues, and stacks. If clocks are only approximately synchronized (or do not exist), then for all three object types it is shown that linearizability is more expensive than sequential consistency. We show that, for all three data types, the worst-case response time is very sensitive to the assumptions that are made about the timing information available to the system. Under the strong assumption that processes have perfectly synchronized clocks, it is shown that sequential consistency and linearizability are equally costly. We present upper bounds for linearizability and matching lower bounds for sequential consistency. The upper bounds are shown by presenting algorithms that use atomic broadcast in a modular fashion. The lower-bound proofs for the approximate case use the technique of “shifting,” first introduced for studying the clock synchronization problem.