Tracing byzantine faults in ad hoc networks
Download 138.2 Kb.
|
| Tracing faults
If the source s receives a valid fault_report j, then either xi or xi+1 is a faulty node. If s receives no valid report within the allocated time , then x1 is the faulty node. Observe that must be significantly less than the expected lifetime of each hop. Furthermore, one must allow for some time for nodes to process/forward packets, so that the link between nodes xi and xi+1 does not break (because of the ad hoc nature of the network) before xi+1 forwards its packet. This Tracing algorithm will succeed in tracing a Byzantine fault because of our assumption that all the links on the route are not faulty, and because if both xi and xi+1 were both non faulty then xi would not authenticate a fault report. The fault will be attributed to both xi and xi+1 . Remarks Our Tracing algorithm will trace pairs of linked nodes, so that with each faulty node an innocent node may be implicated. Note that it is impossible to decide which of the two nodes xi and xi+1 is actually malicious from a single Byzantine attack. This is because there is no way of distinguishing which one of the two is the liar. Our Tracing algorithm is more efficient than the Awerbuch et al. tracing algorithm [1], for several reasons. One reason is that there is only one mode of operation and that tracing is only triggered if an actual fault occurs. So the adversary cannot employ a hide-and-seek strategy in which he/she is malicious only during the communication phase and not during the tracing phase. Another reason is that for each fault only one fault_report is needed, whereas in the Awerbuch et al. tracing algorithm [1] up to log n fault_reports may be needed (depending on the strategy of the adversary), where n is the length of the routing path. Our Tracing algorithm which is described for routes determined by an AODV routing algorithm can easily be extended to routes determines by any other routing algorithm. Download 138.2 Kb. Share with your friends:
|