PaperlayerView exact revision on arXiv

Source-linked AI summary

Universe Detectors for Sybil Defense in Ad Hoc Wireless Networks

Adnan Vora, Mikhail Nesterenko, Sébastien Tixeuil, Sylvie Delaët

arXiv:0805.0087v2cs.DCcs.CRcs.NI

TL;DR

Wireless nodes cannot independently distinguish real neighbors from attacker-created fictitious identities, leaving neighborhood discovery under Sybil attack unresolved. The paper introduces universe detectors and SAND, with density and communication-range conditions for solvability. It reports that SAND solves the neighborhood-discovery problems under those conditions using the weakest necessary detectors.

Abstract

from arXiv · show

The Sybil attack in unknown port networks such as wireless is not considered tractable. A wireless node is not capable of independently differentiating the universe of real nodes from the universe of arbitrary non-existent fictitious nodes created by the attacker. Similar to failure detectors, we propose to use universe detectors to help nodes determine which universe is real. In this paper, we (i) define several variants of the neighborhood discovery problem under Sybil attack (ii) propose a set of matching universe detectors (iii) demonstrate the necessity of additional topological constraints for the problems to be solvable: node density and communication range; (iv) present SAND -- an algorithm that solves these problems with the help of appropriate universe detectors, this solution demonstrates that the proposed universe detectors are the weakest detectors possible for each problem.

D´etecteurs d’Univers pour la D´efense contre les Attaques Sybilles dans les R´eseaux Ad Hoc Sans Fil

The paper frames Sybil defense in wireless networks as an unsolved problem because nodes cannot distinguish real neighbors from attacker-created fictitious nodes. It proposes universe detectors to select the real universe, defines neighborhood-discovery variants and matching detectors, identifies necessary topological constraints, and presents SAND with weakest-detector guarantees.

1 Introduction

The introduction frames wireless neighborhood discovery as a Sybil-defense problem in which broadcast messages and limited sender identification leave nodes vulnerable to fictitious identities and impersonation. It motivates universe detectors and SAND, while emphasizing that solvability depends on density and communication-range conditions.

1 Introduction

  • Wireless nodes cannot reliably match broadcast messages to senders, allowing attackers to create fictitious identities or impersonate real nodes.Cryptographic defenses require maintained key infrastructure and may exceed resource-constrained sensor nodes’ capabilities.Source: §1 · p. 5
  • Wireless broadcast and received signal strength offer possible evidence about message senders, although attackers can change transmission strength.Source: §1 · p. 6
  • Prior synchronous approaches bound how many identities an attacker can use before correct nodes respond, limiting the attack’s strength.Dela¨et et al and Hwang et al consider synchronous operation.Source: §1 · p. 6
  • The paper studies a faulty node that can act arbitrarily in an asynchronous model, with coordinates as nodes’ only unique identities.The model excludes denial-of-service and jamming attacks and assumes adequate bandwidth, memory, and computing resources.Source: §1 · p. 7
  • Universe detectors help nodes select the real universe, but detectors alone cannot solve neighborhood discovery when network density is too sparse.The introduction identifies necessary conditions involving correct-node locations and minimum transmission range.Source: §1 · p. 7
  • SAND uses appropriate universe detectors to solve neighborhood discovery when necessary conditions hold, and the employed detectors are weakest for the problem.Source: §1 · p. 8

2 Computation Model Description, Assumptions, Notation and Definitions

The model represents nodes by their locations in a geometric plane and studies asynchronous communication among correct and Byzantine nodes. It defines RSS-based conflicts and universes, then distinguishes strong, weak, and eventual neighborhood-discovery guarantees.

2 Computation Model Description, Assumptions, Notation and Definitions

  • A layout is a set of nodes and their plane locations; coordinates uniquely identify nodes, and neighborhood membership is defined by a fixed distance.Source: §2 · p. 8
  • Computations are weakly fair and asynchronous, while node layout remains fixed during each computation.Nodes may be correct or Byzantine, and faulty nodes can behave arbitrarily.Source: §2 · p. 9
  • RSS follows the free-space model; correct nodes use fixed transmission strength, while faulty nodes may choose arbitrary strength.The model assumes no message loss from interference or hidden terminals, and receivers measure RSS accurately when a message arrives.Source: §2 · p. 9
  • Nodes broadcast announcements, confirmations, and conflicts; RSS inconsistent with the expected signal from a claimed location can indicate a conflict.Source: §2 · pp. 9–10
  • A universe is a set of neighbors whose announcements do not conflict; it is real if all its nodes exist and complete if it includes all correct neighbors.Completeness does not require silent faulty nodes to be included.Source: §2 · p. 10
  • SNDP requires safe, complete neighborhood output; WNDP permits incomplete output, while ⋄NDP permits incorrect output before an eventual safe suffix.The variants retain the prohibition on fictitious nodes in their required safe outputs.Source: §2 · pp. 10–11

3 Impossibility of Standalone Solution to Neighborhood Discovery

A correct node cannot solve neighborhood discovery alone in an asynchronous system with a Byzantine fault. The attacker can make fictitious nodes’ messages indistinguishable from real-neighbor messages, violating safety if the node eventually includes its correct neighbors.

3 Impossibility of Standalone Solution to Neighborhood Discovery

  • A faulty node can introduce arbitrarily many fictitious nodes and imitate internally consistent traffic, which a correct node cannot distinguish from real neighbors.Source: §3 · p. 11
  • None of the three neighborhood-discovery variants is deterministically solvable in an asynchronous system with one Byzantine fault.Source: §3 · p. 11
  • The proof constructs two layouts with identical messages and RSS at a correct node but different neighborhoods, forcing an output that includes a fictitious node in one layout.Source: §3 · pp. 11–12

4 Abstract Universe Detectors

Universe detectors help nodes choose which collected neighborhood universe is real, addressing a choice that nodes cannot make from conflicts alone. The paper distinguishes detectors by whether the selected universe must be complete and when the detector must select it.

4 Abstract Universe Detectors

  • A universe detector takes a node’s collected universes as input and points to one that contains only real nodes.The algorithm must still collect neighborhood information and form at least one real universe.Source: §4 · pp. 12–13
  • SPU eventually selects a real, complete universe and never selects one that is not both real and complete.Its completeness property requires eventual selection when the node outputs a real and complete universe continuously.Source: §4 · p. 13
  • WPU relaxes accuracy to permit selecting a real but incomplete universe, while retaining completeness; ⋄PU relaxes both properties in a suffix of every computation.The detector classes satisfy SPU ⊂ WPU ⊂ ⋄PU.Source: §4 · p. 13
  • Conflict-aware algorithms do not separate non-conflicting neighbors across universes, limiting how much universe construction is delegated to the detector.The paper focuses on conflict-aware solutions rather than composing a universe for every possible node combination.Source: §4 · p. 13

5 Necessary Node Density

Universe detectors alone cannot guarantee neighborhood discovery in every layout: density and communication geometry constrain whether fictitious nodes can be introduced without conflicts. The section defines snares to characterize this vulnerability and gives grid examples and an impossibility result for layouts containing a perfect snare.

5 Necessary Node Density

  • Faulty nodes can exploit a layout to announce fictitious nodes without conflicts, which a conflict-aware algorithm cannot remove from the real universe.A universe detector then cannot point to a universe that excludes those fictitious nodes.Source: §5 · p. 14

5.1 Fictitious Nodes Placement Examples

  • A deception field contains locations where a faulty node can match the retinue’s received signal strengths; a snare lies in intersecting fields and can avoid explicit conflicts locally.A perfect snare additionally places all nodes within transmission range of the relevant node and location in the faulty nodes’ retinues, avoiding implicit conflicts too.Source: §5.1 · p. 18
  • For s ≤ dn < s√2 with rt = dn, a single node failure creates a wedge-shaped deception field, making the grid layout not fault tolerant.In this range, each node has exactly four neighbors.Source: §5.1 · pp. 18, 20
  • For 2 ≤ dn < 2s with rt = dn, the neighborhood withstands exactly one node failure because a received signal reaches three non-collinear correct neighbors.Their pairwise deception circles intersect only at the sender, so the neighborhood contains no snare.Source: §5.1 · p. 20
  • With dn = rt = 1.5s, two failed grid nodes can use intersecting deception fields to form a perfect snare, so the layout cannot withstand their simultaneous failure.The retinues are u2 for u1 and u5 for u4; their deception-field intersection provides the snare location.Source: §5.1 · p. 20

5.2 Necessary Node Density Condition

  • A perfect snare makes any conflict-aware, well-formed deterministic solution impossible, even when universe detectors are available.The result applies if one considered layout contains a perfect snare.Source: §5.2 · p. 20
  • The perfect-snare proof compares layouts with and without a correct node at the snare location: the same conflict-free messages force the same universes, leaving the fictitious node included.That contradicts detector safety and prevents eventual neighborhood discovery.Source: §5.2 · pp. 21–22

6 Necessary Transmission Range

Without snares, neighborhood discovery is unsolvable when transmission range is less than twice the neighborhood distance, even with universe detectors. The proof hinges on executions that a correct node cannot distinguish, although one contains a correct neighbor.

6 Necessary Transmission Range

  • When transmission range rt is less than 2dn, no conflict-aware deterministic solution exists for any neighborhood discovery variant, despite universe detectors and the absence of snares.The theorem states the necessary range condition; it does not assert that meeting the bound alone guarantees solvability.Source: §6 · p. 22
  • In the proof, a faulty node can impersonate a fictitious node at k, prompting a conflict that removes k from the real universe.With transmission strength matching the supposed location, the faulty node is in range of v while k is not, so v detects the conflict.Source: §6 · pp. 22–23
  • A second layout makes k a correct node while preserving the messages seen by the nodes, so deterministic behavior still excludes a correct neighbor and violates liveness.The proof compares layouts L1 and L2; in L2, k is correct and should eventually appear in u’s output.Source: §6 · pp. 23–24

7 The Sybil Attack Resilient Neighborhood Discovery Algorithm SAN D

SAND uses conflict information and universe detectors to solve neighborhood discovery under no-snare and transmission-range conditions. Its concrete detectors are weakest for their respective discovery variants.

7 The Sybil Attack Resilient Neighborhood Discovery Algorithm SAN D

  • SAND encodes candidate universes through conflicts passed to detectors, avoiding a naive enumeration that can grow to 2^floor(N/2) universes.The naive count arises from considering combinations of conflicting pairs among N neighborhood nodes.Source: §7 · p. 24
  • Nodes announce coordinates, confirm announcements, and send conflicts when coordinates disagree with the received signal strength.Nodes ignore messages from outside neighborhood distance dn.Source: §7 · p. 25
  • Each node builds DEP by matching confirms to announcements and conflicts to their triggering messages, then removes unmatched messages, cycles, and non-announcement sinks.Matches may be non-unique, and DEP may grow indefinitely as faulty nodes send arbitrary messages.Source: §7 · p. 25
  • cSPU outputs only complete, real universes; cWPU may output incomplete real universes, and ⋄cPU may output arbitrary values for finitely many states, but all eventually output a complete, real universe.The specifications must hold even though DEP may grow infinitely large.Source: §7 · p. 26
  • With no snares and transmission range at least twice the neighborhood distance, SAND solves SNDP with cSPU, WNDP with cWPU, and ⋄NDP with ⋄cPU.The theorem characterizes SAND as conflict-aware and deterministic.Source: §7 · pp. 25–26
  • The concrete detectors cSPU, cWPU, and ⋄cPU are weakest for SNDP, WNDP, and ⋄NDP, respectively.The paper defines weakest as both sufficient for a solution and implementable from the input of any solution.Source: §7 · p. 26

8 Detector Implementation and Future Research

The paper outlines possible detector implementations and identifies unresolved questions about their inputs and relationship to fault detectors. It also leaves adaptation to irregular wireless propagation open.

8 Detector Implementation and Future Research

  • Detectors could use bounds on faulty-node speed, known network topology such as a grid, or secure communication with trusted neighbors.The paper says actual implementation may depend on application properties.Source: §8 · p. 27
  • Whether SAND provides the maximum possible information to detectors remains unproven and is identified as future research.The authors suspect it does, but want a rigorous proof.Source: §8 · p. 27
  • The model assumes completely reliable communication within radius Rmin, while real low-power wireless propagation is irregular; adapting the model is left open.The paper contrasts its assumption with propagation patterns in sensor and ad hoc networks.Source: §8 · p. 27
  • Universe detectors require additional layout properties for neighborhood discovery, and their relationship to fault detectors remains an open research question.The paper asks whether a complete analogue to fault detectors exists for this problem.Source: §8 · p. 27
Loading 0805.0087v2…