Subject: [manet] Questions regarding misbehavior detection

From: zhen <[email-masked]>
Date: Sat, 25 Jan 2003 16:29:16 -0400

Hello, there,

I am wondering how you think about following questions regarding the 
well-known paper "Mitigating Routing Misbehavior in Mobile Ad Hoc Networks". 
The idea of in the paper mentioned above is very interesting but I have 
following questions to ask.

Does the idea apply to the stage of data transmission or the one of finding 
routes? (In the paper, it does not specify the attacks that this approach can 
solve). I suppose it applies to the first one because only so you have the 
list of nodes needed by monitoring procedure.

How do you feel the limitation of it"does not work well in multi-rate wireless 
networks because nodes might not hear their neighbors forwarding 
communications due to different modulation"(An On-Demand Secure Routing 
Protocol Resilient to Byzantine Failures). But I suppose if nodes can 
communicate, they should be in same modulation model. Is this the right case?

Also I heard that this method(I mean, misbehavior detection) can not detect 
all misbehaviors. Any thought?

thanks for your help

new to this

Zhen Zhen

Graduate CS Dalhousie University

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "David Holmer" <[email-masked]>
Date: Mon, 27 Jan 2003 23:50:32 -0500

Zhen,

Obviously we took a close look at "Mitigating Routing Misbehavior in
Mobile Ad Hoc Networks", by Sergio Marti, T.J. Giuli, Kevin Lai, and
Mary Baker at Stanford, while we were writing "An On-Demand Secure
Routing 
Protocol Resilient to Byzantine Failures". So I figured I'd share my
opinions in an effort to answer your question.

> well-known paper "Mitigating Routing Misbehavior in Mobile Ad Hoc
> Networks". The idea of in the paper mentioned above is very
interesting
> but I have following questions to ask.

First, I agree that the central idea of this paper is very interesting,
and I applaud the clever exploitation of a unique property of wireless
networks to serve a useful function. Also, I agree with the fundamental
approach of misbehavior detection and avoidance (which was also used as
the basis of our protocol).

I believe this is the central issue related to your confusion:

> (In the paper, it does not specify the attacks that this 
> approach can solve).

While they don't provide a formal security model, in the introduction
the authors state that "a node may misbehave by agreeing to forward
packets and then failing to do so, because it is overloaded, selfish,
malicious, or broken." There is also another paragraph in the
introduction that talks about the down sides of "a priori trust-based
forwarding". This implies that the presented protocol does not require
such a trust relationship (and none is described in the protocol
sections).

My best guess at the security model is:
- All nodes may participate in the network (no keys or certificates are
required)
- All nodes participate correctly protocol, except that
- Some nodes may misbehave by dropping packets they have agreed to
forward

Notice that I've limited the misbehavior of the nodes to dropping
packets ONLY. This protocol does not protect against the myriad of
attacks possible if even a single malicious node is allowed to fabricate
and modify packets. The lack of authentication using a trust
relationship in this protocol means that a single malicious node has
even greater power than a single Byzantine node. This is because the
single malicious node can use an unlimited number of fictitious
identities, allowing it to perform many of the attacks that multiple
Byzantine adversaries can.

Just for example, a single malicious node can easily escape detection by
watchdog by appending a fictitious node id after its own on the route
request during the route discovery flood. Now the node can safely drop
any packets by "sending" them to the fictitious next hop. This is the
same attack that two collaborating nodes can mount, but executed by a
single malicious node.

Now if you think carefully about this particular example, you can
probably come up with ways to defend against this attack: by implicating
nodes that append two ids during the flood, by having the next real hop
notice that it has received a packet out of sequence from someone
further back on the source route, or by some other means. But any
solution requires modifications to the proposed protocol. In the end
this protocol is inherently flawed when dealing with unrestricted
malicious nodes, because even if they are successfully detected, they
can simply change identities and avoid the blame (not to mention the
near limitless abuse made possible by the ability to implicate other
nodes).

So given the above security model, the question is which types of nodes
still fit? Since malicious nodes aren't likely to restrict themselves to
only dropping packets and operating correctly otherwise, we are left
with overloaded, selfish, or broken nodes. Upon closer inspection, the
best option available for selfish nodes is to simply not forward route
requests. This is in their best interest because forwarding requests
takes CPU and battery, and as a side effect, no one will ever select a
route through them. 

So, in conclusion, according to the given security model, the proposed
protocol is only useful for protecting against nodes that are either
overloaded or broken.

Even though the proposed protocol does not provide much useful
protection, it is possible that an alternate protocol could use the same
technique of promiscuous listening to provide greater security
guarantees, which brings us to your other question:

> How do you feel the limitation of it"does not work well in multi-rate 
> wireless networks because nodes might not hear their neighbors
forwarding 
> communicate, they should be in same modulation model. Is this the
right 
> case?

Since the protocol we propose in that paper is quite complex and space
was limited, some details got squeezed to the point of being cryptic.
The authors of the mitigating paper already point out a few "normal"
situations where a correctly forwarded packet may not be overheard
(various types of collisions and transmission power control). Since we
use 802.11b devices as a test platform, we used that as our standard of
evaluation. The power control issue doesn't affect current 802.11b
network as the transmission power is fixed. We also decided that the RTS
CTS virtual carrier sense mechanism of 802.11 should help mitigate the
number of these collisions (at least for a single stream of packets
traveling along a path). But we also noticed another reason why the
forwarded packet might not be overheard. If node A is far away from node
B and node C is relatively close to node B, then A will likely not be
able to overhear the transmission from B to C when a multi-rate protocol
like 802.11b is used. If the transmission from A to B must take place at
1 Mbps because of the high path loss, it will not be able to decode an
11 Mpbs transmission from B to C because the BER will be extremely high.
This is very similar to the power control case the authors already
mentioned. However, unlike the other two cases the authors mentioned,
this case is much more likely to cause problems then the other two,
because it actually happens in real world networks. A simulation would
be necessary to get an approximate number for the overall impact.

Well, this response got much longer than I originally intended, but I
hope it help you out. I'd be happy to hear other people's opinions on
the subject as well.

David Holmer,
Johns Hopkins University

For those that are interested:
An On-Demand Secure Routing Protocol Resilient to Byzantine Failures
Baruch Awerbuch, David Holmer, Cristina Nita-Rotaru, Herbert Rubens
ACM Workshop on Wireless Security (WiSe) 2002
http://citeseer.nj.nec.com/awerbuch02demand.html

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
zhen
Sent: Saturday, January 25, 2003 3:29 PM
To: [email-masked]
Subject: [manet] Questions regarding misbehavior detection

Hello, there,

I am wondering how you think about following questions regarding the 
well-known paper "Mitigating Routing Misbehavior in Mobile Ad Hoc
Networks". 
The idea of in the paper mentioned above is very interesting but I have 
following questions to ask.

Does the idea apply to the stage of data transmission or the one of
finding 
routes? (In the paper, it does not specify the attacks that this
approach can 
solve). I suppose it applies to the first one because only so you have
the 
list of nodes needed by monitoring procedure.

How do you feel the limitation of it"does not work well in multi-rate
wireless 
networks because nodes might not hear their neighbors forwarding 
communications due to different modulation"(An On-Demand Secure Routing 
Protocol Resilient to Byzantine Failures). But I suppose if nodes can 
communicate, they should be in same modulation model. Is this the right
case?

Also I heard that this method(I mean, misbehavior detection) can not
detect 
all misbehaviors. Any thought?

thanks for your help

new to this

Zhen Zhen

---

From: [email-masked]
Date: Mon, 27 Jan 2003 18:12:56 -0800

Zhen,

There's been a lot more work on really securing ad hoc routing
protocols since this paper.  This paper isn't a security paper,
since there are so many attacks it is not intended for.  It is more
a sort of "robustness improvement" approach. 

> communicate, they should be in same modulation model. Is this the right case?

I'm not quite sure I understand your question here -- my apologies.

> all misbehaviors. Any thought?

Certainly it cannot detect all misbehaviors!  It does nothing to secure
the routing protocol, for instance.  It was more a first attempt to see what
we can do for throughput with a little bit of machinery that doesn't much
interfere with the routing protocol itself.  

Best wishes,
Mary