Tracing faults
If the source s receives a valid fault_report_{ }_{j}, then either x_{i} or x_{i+1} is a faulty node. If s receives no valid report within the allocated time , then x_{1} 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 x_{i} and x_{i+}_{1} does not break (because of the ad hoc nature of the network) before x_{i+}_{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 x_{i} and x_{i+1} were both non faulty then x_{i} would not authenticate a fault report. The fault will be attributed to both x_{i} and x_{i+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 x_{i} and x_{i+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 hideandseek 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.

Share with your friends: 