Security and Privacy in Communication Networks. 5th International ICST Conference, SecureComm 2009, Athens, Greece, September 14-18, 2009, Revised Selected Papers

Research Article

Dealing with Liars: Misbehavior Identification via Rényi-Ulam Games

Download157 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-05284-2_12,
        author={William Kozma and Loukas Lazos},
        title={Dealing with Liars: Misbehavior Identification via R\^{e}nyi-Ulam Games},
        proceedings={Security and Privacy in Communication Networks. 5th International ICST Conference, SecureComm 2009, Athens, Greece, September 14-18, 2009, Revised Selected Papers},
        proceedings_a={SECURECOMM},
        year={2012},
        month={5},
        keywords={},
        doi={10.1007/978-3-642-05284-2_12}
    }
    
  • William Kozma
    Loukas Lazos
    Year: 2012
    Dealing with Liars: Misbehavior Identification via Rényi-Ulam Games
    SECURECOMM
    Springer
    DOI: 10.1007/978-3-642-05284-2_12
William Kozma1,*, Loukas Lazos1,*
  • 1: The University of Arizona
*Contact email: wkozma@ece.arizona.edu, llazos@ece.arizona.edu

Abstract

We address the problem of identifying misbehaving nodes that refuse to forward packets in wireless multi-hop networks. We map the process of locating the misbehaving nodes to the classic Rényi-Ulam game of 20 questions. Compared to previous methods, our mapping allows the evaluation of node behavior on a per-packet basis, without the need for energy-expensive overhearing techniques or intensive acknowledgment schemes. Furthermore, it copes with colluding adversaries that coordinate their behavioral patterns to avoid identification and frame honest nodes. We show via simulations that our algorithms reduce the communication overhead for identifying misbehaving nodes by at least one order of magnitude compared to other methods, while increasing the identification delay logarithmically with the path size.