Zeroconf Address Allocation
IPv4 Zeroconf lets devices choose local network addresses without manual configuration or a DHCP server [RFC 3927]. A device sends probes to check whether another device already uses its chosen address.
Lost probes or replies can leave a conflict unnoticed, while additional probes cost traffic and delay [PRISM Zeroconf].
For one address choice and a fixed probe limit, we verify an upper bound on the probability that the address is free or the collision is detected.
Both outcomes count as success.
The Programβ
The functions probCollision() and probMessageLost() give the collision probability and the probability that a probe fails to detect it.
This can happen if the probe or its reply is lost.
The function maxTries() gives the probe limit .
The helper exp(q, k) denotes .
The procedure zeroconf first samples whether the address is occupied.
For an occupied address, it calls arp(maxTries()) to try to detect the collision.
Verified@wp
coproc zeroconf() -> (success: Bool)
pre probCollision() * (1 - exp(probMessageLost(), maxTries())) + (1 - probCollision())
post [success]
{
var collision: Bool = flip(probCollision())
if collision {
// Try at most maxTries() probes to detect this collision.
success = arp(maxTries())
} else {
success = true
}
}
Choosing another address after detecting a collision is outside this model.
Verificationβ
Both coprocedures use the @wp annotation to verify upper bounds on the probability that success is true.
Upper Bound for the Address Choiceβ
Caesar verifies the upper bound
The term accounts for a free address, which immediately succeeds.
The term accounts for an occupied address, using the bound in arp's specification for probes.
Bounding Collision Detection Recursivelyβ
The helper arp(triesRemaining) probes an occupied address, stopping when a collision is detected or no probes remain.
Verified@wp
coproc arp(triesRemaining: UInt) -> (success: Bool)
pre 1 - exp(probMessageLost(), triesRemaining)
post [success]
{
if triesRemaining == 0 {
// With no probes remaining, the collision cannot be detected.
success = false
} else {
// A delivered probe detects the collision; a lost probe leaves one fewer attempt.
var messageLost: Bool = flip(probMessageLost())
if messageLost {
success = arp(triesRemaining - 1)
} else {
success = true
}
}
}
With independent probes left, the collision remains undetected if all fail, an event of probability .
With no probes remaining, arp returns false, matching the bound zero.
For , a probe detects the collision with probability ; otherwise, we use the recursive specification with one fewer probe:
Each recursive call decreases triesRemaining, so the procedure terminates after at most that many probes.
Caesar uses the recursive definition of exp for and the axiom exp_bounded for .
See Alsoβ
- Bounded Retransmission Protocol analyzes packet delivery with a retry limit.
- Geometric Loop compares several ways to bound the effect of repeated independent trials.
Referencesβ
-
Bohnenkamp et al. (2003). Cost-Optimization of the IPv4 Zeroconf Protocol.
Studies the tradeoff between reliable address allocation and expected cost.
(Section 3.1, Figure 1) -
Kwiatkowska et al. (2006). Performance Analysis of Probabilistic Timed Automata Using Digital Clocks.
The PRISM Zeroconf case study describes the model with timing, message buffers, and address reconfiguration used in that analysis.
(Section 6.1) -
SchrΓΆer et al. (2023). A Deductive Verification Infrastructure for Probabilistic Programs. OOPSLA.
Includes the recursive HeyVL case study used here.
(Table 2)