22 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO.

1, JANUARY 2014

A Probabilistic Misbehavior Detection Scheme

toward Efficient Trust Establishment
in Delay-Tolerant Networks
Haojin Zhu, Member, IEEE, Suguo Du, Zhaoyu Gao, Student Member, IEEE,
Mianxiong Dong, Member, IEEE, and Zhenfu Cao, Senior Member, IEEE

Abstract—Malicious and selfish behaviors represent a serious threat against routing in delay/disruption tolerant networks (DTNs). Due
to the unique network characteristics, designing a misbehavior detection scheme in DTN is regarded as a great challenge. In this
paper, we propose iTrust, a probabilistic misbehavior detection scheme, for secure DTN routing toward efficient trust establishment.
The basic idea of iTrust is introducing a periodically available Trusted Authority (TA) to judge the node’s behavior based on the
collected routing evidences and probabilistically checking. We model iTrust as the inspection game and use game theoretical analysis
to demonstrate that, by setting an appropriate investigation probability, TA could ensure the security of DTN routing at a reduced cost.
To further improve the efficiency of the proposed scheme, we correlate detection probability with a node’s reputation, which allows a
dynamic detection probability determined by the trust of the users. The extensive analysis and simulation results demonstrate the
effectiveness and efficiency of the proposed scheme.

Index Terms—Misbehavior detection, incentive scheme, delay tolerant networks, security

1 INTRODUCTION

D ELAY tolerant networks (DTNs), such as sensor net-

works with scheduled intermittent connectivity, vehi-
cular DTNs that disseminate location-dependent
packets or modifying the packets to launch attacks. The
recent researches show that routing misbehavior will
significantly reduce the packet delivery rate and, thus,
information (e.g., local ads, traffic reports, parking informa- pose a serious threat against the network performance of
tion) [1], and pocket-switched networks that allow humans DTN [4], [6]. Therefore, a misbehavior detection and
to communicate without network infrastructure, are highly mitigation protocol is highly desirable to assure the secure
partitioned networks that may suffer from frequent DTN routing as well as the establishment of the trust
disconnectivity. In DTNs, the in-transit messages, also among DTN nodes in DTNs.
named bundles, can be sent over an existing link and Mitigating routing misbehavior has been well studied in
buffered at the next hop until the next link in the path traditional mobile ad hoc networks. These works use
appears (e.g., a new node moves into the range or an neighborhood monitoring or destination acknowledgement
existing one wakes up). This message propagation process to detect packet dropping [7], and exploit credit-based and
is usually referred to as the “store-carry-and-forward” reputation-based incentive schemes to stimulate rational
strategy, and the routing is decided in an “opportunistic” nodes or revocation schemes to revoke malicious nodes [4],
fashion [2], [3], [4], [5]. [8]. Even though the existing misbehavior detection
In DTNs, a node could misbehave by dropping packets schemes work well for the traditional wireless networks,
intentionally even when it has the capability to forward the the unique network characteristics including lack of
data (e.g., sufficient buffers and meeting opportunities) [4]. contemporaneous path, high variation in network condi-
Routing misbehavior can be caused by selfish (or rational) tions, difficulty to predict mobility patterns, and long
nodes that try to maximize their own benefits by enjoying feedback delay have made the neighborhood monitoring-
the services provided by DTN while refusing to forward based misbehavior detection scheme unsuitable for DTNs
the bundles for others, or malicious nodes that drop [4]. This can be illustrated by Fig. 1, in which a selfish node
B receives the packets from node A but launches the black
hole attack by refusing to forward the packets to the next hop
. H. Zhu, Z. Gao, and Z. Cao are with the Department of Computer Science
& Engineering, Shanghai Jiao Tong University, 800 Dongchuan Rd., receiver C [9]. Since there may be no neighboring nodes at
Shanghai 200240, China. E-mail: {zhu-hj, zhaoyu, zfcao}@sjtu.edu.cn. the moment that B meets C, the misbehavior (e.g., dropping
. S. Du is with the Department of Management Science, Shanghai Jiao Tong messages) cannot be detected due to lack of witness, which
University, 535 Fahua Zhen Road, Shanghai, China 200052200. renders the monitoring-based misbehavior detection less
E-mail: [email protected].
. M. Dong is with the University of Aizu, Higashisengoku, Aizuwakamatsu, practical in a sparse DTN.
Fukushima 9650818 2-3-14, Japan. E-mail: [email protected]. Recently, there are quite a few proposals for misbeha-
Manuscript received 24 Jan. 2013; accepted 25 Jan. 2013; published online 14 viors detection in DTNs [4], [8], [9], [10], most of which are
Feb. 2013. based on forwarding history verification (e.g., multilayered
Recommended for acceptance by X. Li. credit [4], [8], three-hop feedback mechanism [10], or
For information on obtaining reprints of this article, please send e-mail to:
[email protected], and reference IEEECS Log Number TPDS-2013-01-0077. encounter ticket [6], [9]), which are costly in terms of
Digital Object Identifier no. 10.1109/TPDS.2013.36. transmission overhead and verification cost. The security
1045-9219/14/$31.00 ß 2014 IEEE Published by the IEEE Computer Society
Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
ZHU ET AL.: A PROBABILISTIC MISBEHAVIOR DETECTION SCHEME TOWARD EFFICIENT TRUST ESTABLISHMENT IN DELAY-TOLERANT... 23

. First, we propose a general misbehavior detection

framework based on a series of newly introduced data
forwarding evidences. The proposed evidence frame-
work could not only detect various misbehaviors but
also be compatible to various routing protocols.
. Second, we introduce a probabilistic misbehavior
detection scheme by adopting the inspection game.
A detailed game theoretical analysis will demon-
Fig. 1. An example of black hole attack in DTNs. strate that the cost of misbehavior detection could be
significantly reduced without compromising the
overhead incurred by forwarding history checking is critical detection performance. We also discuss how to
for a DTN because expensive security operations will be correlate a user’s reputation (or trust level) to the
translated into more energy consumptions, which repre- detection probability, which is expected to further
sents a fundamental challenge in resource-constrained reduce the detection probability.
DTN. Further, even from the Trusted Authority (TA) point . Third, we use extensive simulations as well as
of view, misbehavior detection in DTNs inevitably incurs a detailed analysis to demonstrate the effectiveness
high inspection overhead, which includes the cost of and the efficiency of the iTrust.
collecting the forwarding history evidence via deployed The remainder of this paper is organized as follows: In
judgenodes [10] and transmission cost to TA. Therefore, an Section 2, we present the system model, adversary model
efficient and adaptive misbehavior detection and reputation considered throughout the paper. In Section 3, we proposed
management scheme is highly desirable in DTN. the basic iTrust and the analysis from the perspective of
In this paper, we propose iTrust, a probabilistic game theory. The simulation results of iTrust are given in
misbehavior detection scheme to achieve efficient trust Section 4, followed by the conclusion in Section 5.
establishment in DTNs. Different from existing works that
only consider either of misbehavior detection or incentive 2 PRELIMINARY
scheme, we jointly consider the misbehavior detection and
This section describes our system model and design goals.
incentive scheme in the same framework. The proposed
iTrust scheme is inspired from the inspection game [11], a 2.1 System Model
game theory model in which an inspector verifies if In this paper, we adopt the system model similar to [4]. We
another party, called inspectee, adheres to certain legal consider a normal DTN consisted of mobile devices owned
rules. In this model, the inspectee has a potential interest by individual users. Each node i is assumed to have a
in violating the rules while the inspector may have to unique ID Ni and a corresponding public/private key pair.
perform the partial verification due to the limited We assume that each node must pay a deposit C before it
verification resources. Therefore, the inspector could take joins the network, and the deposit will be paid back after
advantage of partial verification and corresponding pun- the node leaves if there is no misbehavior activity of the
ishment to discourage the misbehaviors of inspectees. node. Similar to [13], we assume that a periodically
Furthermore, the inspector could check the inspectee with available TA exists so that it could take the responsibility
a higher probability than the Nash Equilibrium points to of misbehavior detection in DTN. For a specific detection
prevent the offences, as the inspectee must choose to target Ni , TA will request Ni ’s forwarding history in the
comply the rules due to its rationality. global network. Therefore, each node will submit its
Inspired by inspection game, to achieve the tradeoff collected Ni ’s forwarding history to TA via two possible
between the security and detection cost, iTrust introduces approaches. In a pure peer-to-peer DTN, the forwarding
a periodically available TA, which could launch the history could be sent to some special network components
probabilistic detection for the target node and judge it by (e.g., roadside unit (RSU) in vehicular DTNs or judgenodes
collecting the forwarding history evidence from its up- in [10]) via DTN transmission. In some hybrid DTN
stream and downstream nodes. Then, TA could punish or network environment, the transmission between TA and
compensate the node based on its behaviors. To further each node could be also performed in a direct transmission
improve the performance of the proposed probabilistic manner (e.g., WIMAX or cellular networks [14]). We argue
inspection scheme, we introduce a reputation system, in that because the misbehavior detection is performed
which the inspection probability could vary along with the periodically, the message transmission could be performed
target node’s reputation. Under the reputation system, a in a batch model, which could further reduce the transmis-
node with a good reputation will be checked with a lower sion overhead.
probability while a bad reputation node could be checked 2.2 Routing Model
with a higher probability. We model iTrust as the inspection
We adopt the single-copy routing mechanism such as First
game and use game theoretical analysis to demonstrate that
Contact routing protocol, and we assume the communica-
TA could ensure the security of DTN routing at a reduced tion range of a mobile node is finite. Thus, a data sender out
cost via choosing an appropriate investigation probability. of destination node’s communication range can only
The contributions of this paper can be summarized as transmit packetized data via a sequence of intermediate
follows: nodes in a multihop manner. Our misbehaving detection

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
24 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUARY 2014

scheme can be applied to delegation-based routing proto-

cols or multicopy-based routing ones, such as MaxProp [18]
and ProPHET [19]. We assume that the network is loosely
synchronized (i.e., any two nodes should be in the same
time slot at any time).

2.3 Threat Model

First of all, we assume that each node in the networks is
rational and a rational node’s goal is to maximize its own
profit. In this work, we mainly consider two kinds of DTN
nodes: selfish nodes and malicious nodes. Due to the selfish
nature and energy consuming, selfish nodes are not willing
to forward bundles for others without sufficient reward. As
an adversary, the malicious nodes arbitrarily drop others’
bundles (black hole or gray hole attack), which often take
Fig. 2. In the routing evidence generation phase, A forwards packets to
place beyond others’ observation in a sparse DTN, leading B, then gets the delegation history back. B holds the packet and then
to serious performance degradation. Note that any of the encounters C. C gets the contact history about B. In the auditing phase,
selfish actions above can be further complicated by the when TA decides to check B, TA will broadcast a message to ask other
collusion of two or more nodes. nodes to submit all the evidences about B, then A submits the delegation
history from B, B submits the forwarding history (delegation history from
C), C submits the contact history about B.
2.4 Design Requirements
The design requirements include:
node N i , which will follow a specific routing
. Distributed. We require that a network authority protocol to forward M to the next hop. When N j
responsible for the administration of the network is arrives at the transmission range of N i , N i will
only required to be periodically available and determine if N j is the suitable next hop, which is
consequently incapable of monitoring the opera- indicated by flag bit flag. If N j is the chosen next
tional minutiae of the network. hop (or flag ¼ 1), a delegation task evidence IEi!j task
. Robust. We require a misbehavior detection scheme needs to be generated to demonstrate that a new task
that could tolerate various forwarding failures has been delegated from N i to N j . Given that Tts
caused by various network environments. and TExp refer to the time stamp and the packets
. Scalability. We require a scheme that works inde- expiration time of the packets, we set IMi!j M ¼
pendent of the size and density of the network. fM; N src ; flag; N i ; N j ; N dst ; Tts ; TExp ; Sigsrc g, where
Sigsrc ¼ Sigsrc ðHðM; N src ; N dst ; TExp ÞÞ refers to the
3 THE PROPOSED BASIC iTRUST SCHEME FOR signature generated by the source nodes on message
MISBEHAVIOR DETECTION IN DTNs M. Node N i generates the signature Sigi ¼
SIGi fIMi!j
M g to indicate that this forwarding task
In this section, we will present a novel basic iTrust scheme
for misbehavior detection scheme in DTNs. As shown in has been delegated to node N j while node N j
Fig. 2, the basic iTrust has two phases, including routing generates the signature Sigj ¼ SIGj fIMi!j M g to show
evidence generation phase and routing evidence auditing that N j has accepted this task. Therefore, we obtain
phase. In the evidence generation phase, the nodes will the delegation task evidence as follows:
generate contact and data forwarding evidence for each  i!j 
IEi!j
task ¼ IMM ; Sigi ; Sigj : ð1Þ
contact or data forwarding. In the subsequent auditing
phase, TA will distinguish the normal nodes from the Note that delegation task evidences are used to
misbehaving nodes. record the number of routing tasks assigned from
the upstream nodes to the target node N j . In the
3.1 Routing Evidence Generation Phase
audit phase, the upstream nodes will submit the
For the simplicity of presentation, we take a three-step data delegation task evidences to TA for verification.
forwarding process as an example. Suppose that node A has Forwarding history evidence IEj!k
. forward . When N j meets
packets, which will be delivered to node C. Now, if node A the next intermediate node N k , N j will check if N k
meets another node B that could help to forward the
is the desirable next intermediate node in terms of a
packets to C, A will replicate and forward the packets to B.
specific routing protocol. If yes (or flag ¼ 1), N j will
Thereafter, B will forward the packets to C when C arrives
forward the packets to N k , who will generate a
at the transmission range of B. In this process, we define
forwarding history evidence to demonstrate that N j
three kinds of data forwarding evidences that could be used
has successfully finished the forwarding task.
to judge if a node is a malicious one or not:
Suppose that IMj!k i!j 0
M ¼ fIMM ; flag; N k ; Tts g. N k will
. Delegation task evidence IEi!j
task . Suppose that source generate a signature Sigk ¼ SIGk fHðIMj!k M Þg to
node N src is going to send a message M to demonstrate the authenticity of forwarding history
the destination N dst . Without loss of generality, we evidence. Therefore, the complete forwarding his-
assume the message is stored at an intermediate tory evidence is generated by N k as follows:

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
ZHU ET AL.: A PROBABILISTIC MISBEHAVIOR DETECTION SCHEME TOWARD EFFICIENT TRUST ESTABLISHMENT IN DELAY-TOLERANT... 25
 
IEj!k j!k
forward ¼ IMM ; Sigk ; ð2Þ m 2 SSforward and N k ðmÞ  R and jN k ðmÞj ¼¼ D;
ð4Þ
which will be sent to N j for future auditing. In the
audit phase, the investigation target node will which shows that the requested message has been
submit his forwarding history evidence to TA to forwarded to the next hop, the chosen next hop
demonstrate that he has tried his best to fulfill nodes are desirable nodes according to a specific
the routing tasks, which are defined by delegation DTN routing protocol, and the number of forward-
task evidences. ing copies satisfy the requirement defined by a
Contact history evidence IEj$k multicopy forwarding routing protocol.
. contact . Whenever two
nodes N j and N k meet, a new contact history . Class II (An honest data forwarding with insufficient
j$k
evidence IEcontact will be generated as the evidence contacts). In this class, users will also honestly
of the presence of N j and N k . Suppose that perform the routing protocol but fail to achieve the
IMj$k ¼ fN j ; N k ; Tts g, where Tts is the time stamp. desirable results due to lack of sufficient contacts.
N j and N k will generate their corresponding Therefore, given the message m 2 SStask , an honest
signatures Sigj ¼ SIGj fHðIMj$k Þg and Sigk ¼ data forwarding in the presence of sufficient contacts
SIGk fHðIMj$k Þg. Therefore, the contact history could be determined if
evidence could be obtained as follows: m 62 SSforward and jRj ¼¼ 0 ð5Þ
 j$k 
IEj$k
contact ¼ IM ; Sigj ; Sigk : ð3Þ or
Note that IEj$kwill be stored at both of meeting
contact m 2 SSforward and N k ðmÞ ¼¼ R
nodes.
In the audit phase, for an investigation target N j , both of and jN k ðmÞj ¼¼ jRj < D: ð6Þ
N j and other nodes will submit their contact history
evidence to TA for verification. Note that contact history Equation (5) refers to the extreme case that there is
no contact during period ½Tts ðmÞ; t2 , while (6) shows
could prevent the black hole or gray hole attack because the
the general case that only a limited number of
nodes with sufficient contact with other users fail to
contacts are available in this period and the number
forward the data will be regarded as a malicious or selfish
of contacts is less than the number of copies required
one. In the next section, we will show how to exploit three
by the routing protocols. In both cases, even though
kinds of evidences to launch the misbehavior detection. the DTN node honestly performs the routing
3.2 Auditing Phase protocol, it cannot fulfill the routing task due to lack
of sufficient contact chances. We still regard this
In the auditing phase, TA will launch an investigation
kind of users as honest users.
request toward node N j in the global network during a
. Class III (A misbehaving data forwarding with/without
certain period ½t1 ; t2 . Then, given N as the set of total nodes
sufficient contacts). A misbehaving node will drop the
in the network, each node in the network will submit its packets or refuse to forward the data even when
collected fIEi!j j!k j$k
task ; IEforward ; IEcontact j 8i; k 2 N g to TA. By there are sufficient contacts, which could be deter-
collecting all of the evidences related to N j , TA obtains mined by examining the following rules:
the set of messages forwarding requests SStask , the set of
messages forwarded SSforward , and the set of contacted users 9m 2 SStask ; m 62 SSforward and R! ¼ 0 ð7Þ
SScontact , all of which could be verified by checking the or
corresponding evidences.
To check if a suspected node N j is malicious or not, TA 9m 2 SStask ; m 2 SSforward and N k ðmÞ 6 R ð8Þ
should check if any message forwarding request has been or
honestly fulfilled by N j . We assume that m 2 SStask is a
message sent to N j for future forwarding and Tts ðmÞ is its 9m 2 SStask ; m 2 SSforward and N k ðmÞ  R
expiration time. We further define N k ðmÞ as the set of next-
hop nodes chosen for message forwarding, R as the set of and jN k ðmÞj < D: ð9Þ
contacted nodes satisfying the requirements of DTN routing
Note that (7) refers to the case that the forwarder
protocols during ½Tts ðmÞ; t2  and D as the number of copies
refuses to forward the data even when the forward-
required by DTN routing. The misbehavior detection
ing opportunity is available. The second case is that
procedure has the following three cases: the forwarder has forwarded the data but failed to
. Class I (An honest data forwarding with sufficient follow the routing protocol, which is referred to (8).
contacts). A normal user will honestly follow the The last case is that the forwarder agrees to forward
routing protocol by forwarding the messages as the data but fails to propagate the enough number of
long as there are enough contacts. Therefore, given copies predefined by a multicopy routing protocol,
the message m 2 SStask , an honest data forwarding which is shown in (9).
in the presence of sufficient contacts could be Next, we give the details of the proposed scheme as
determined if follows: In particular, TA judges if node N j is a

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
26 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUARY 2014

misbehavior or not by triggering the Algorithm 1. In this 5: ask all the nodes (including node i) to provide
algorithm, we introduce BasicDetection, which takes evidence about node i
j; SStask ; SSforward , ½t1 ; t2 ; R; D as well as the routing require- 6: if BasicDetection(i; SStask ; SSforward ; ½t1 ; t2 ; R; D)
ments of a specific routing protocol R; D as the input, and then
output the detection result “1” to indicate that the target 7: give a punishment C to node i
node is a misbehavior or “0” to indicate that it is an 8: else
honest node. 9: pay node i the compensation w
Algorithm 1. The Basic Misbehavior Detection algorithm. 10: end if
1: procedure BASICDETECTION 11: else
((j; SStask ; SSforward ; ½t1 ; t2 ; R; D)) 12: pay node i the compensation w
2: for Each m 2 SStask do 13: end if
3: if m 62 SSforward and R! ¼ 0 then 14: end for
4: return 1
5: else if m 2 SSforward and N k ðmÞ 6 R then In the next section, we will model the above described
6: return 1 algorithm as an inspection game. And we will demonstrate
7: else if m 2 SSforward and N k ðmÞ  R and that, by setting an appropriate detection probability thresh-
jN k ðmÞj < D then old, we could achieve a lower detection overhead and still
8: return 1 stimulate the nodes to forward the packets for other nodes.
9: end if
4.1 Game Theory Analysis
10: end for
Before presenting the detailed inspection game, we assume
11: return 0
that the forwarding transmission costs of each node g to
12: end procedure
make a packet forwarding. It is also assumed that each node
The proposed algorithm itself incurs a low checking will receive a compensation w from TA, if successfully
overhead. However, to prevent malicious users from passing TA’s investigation; otherwise, it will receive a
providing fake delegation/forwarding/contact evidences, punishment C from TA. The compensation could be the
TA should check the authenticity of each evidence by virtual currency or credits issued by TA; on the other hand,
verifying the corresponding signatures, which introduce a the punishment could be the deposit previously given by
high transmission and signature verification overhead. We users to TA. TA will also benefit from each successful data
will give a detailed cost analysis in Section 4.2. In the forwarding by gaining v, which could be charged from
following section, inspired by the inspection game, we will source node similar to [4]. In the auditing phase, TA checks
propose a probabilistic misbehavior detection scheme to the node Ni with the probability pib . Since checking will
reduce the detection overhead without compromising the incur a cost h, TA has two strategies, inspecting (I) or not
detection performance. inspecting (N). Each node also has two strategies, forward-
ing (F) and offending (O). Therefore, we could have the
probabilistic inspection game as follows:
4 THE ADVANCED iTRUST: A PROBABILISTIC
MISBEHAVIOR DETECTION SCHEME IN DTNs Definition. According to iTrust, the probabilistic inspection
game is
To reduce the high verification cost incurred by routing
evidence auditing, in this section, we introduce a probabil- G ¼ <N; fsi g; fi g; fpi g>:
istic misbehavior detection scheme, which allows the TA to
launch the misbehavior detection at a certain probability. . N ¼ fN0 ; N1 ; . . . ; Nn g is the set of the players, N0
The advanced iTrust is motivated by the inspection game, a donates TA.
game theoretical model, in which an authority chooses to . si ¼ fsi0 ; si1 ; si2 ; . . . ; sin g is the strategy set of the
inspect or not, and an individual chooses to comply or not, player Ni , s0 ¼ fI; Ng, si ¼ fF ; Og.
and the unique Nash equilibrium is a mixed strategy, with . i is the payoff of the ith player Ni , and it is measured
positive probabilities of inspection and noncompliance. by credit earnings.
We start from Algorithm 2, which shows the details of . pi is a mixed strategy for player i, especially, p0 ¼
the proposed probabilistic misbehavior detection scheme. fðp1b ; 1  p1b Þ; . . . ; ðpnb ; 1  pnb Þg; pi ¼ fpif ; 1  pif g, pb
For a particular node i, TA will launch an investigation at denotes inspection probability, pf denotes offending
the probability of pb . If i could pass the investigation by probability.
providing the corresponding evidences, TA will pay node i
Then, we could get the payoff matrix between TA and an
a compensation w; otherwise, i will receive a punishment C
individual node as shown in Table 1, and we could use
(lose its deposit).
Theorem 1 to demonstrate that TA could ensure the security
Algorithm 2. The Proposed Probabilistic Misbehavior level with a low inspection cost by the proposed probabil-
Detection algorithm. istic checking approach.
1: initialize the number of nodes n gþ"
Theorem 1. If TA inspects at the probability of pb ¼ wþC in
2: for i 1 to n do iTrust, a rational node must choose forwarding strategy, and
3: generate a random number mi from 0 to 10n  1 the TA will get a higher profit than it checks all the nodes in
4: if mi =10n < pb then the same round.

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
ZHU ET AL.: A PROBABILISTIC MISBEHAVIOR DETECTION SCHEME TOWARD EFFICIENT TRUST ESTABLISHMENT IN DELAY-TOLERANT... 27

TABLE 1 Theorem 2. Given that pb is the detection probability,  is the

The Payoff Matrix of TA and an Individual Node mean value of all the ij , T is the inspection period, N is
the number of nodes, Costtransmission and Costverification are
the evidence transmission cost and evidence signature
verification cost for a contact, the misbehavior detection cost
in the whole network could be estimated as
1 
pb T jNj2 ðCosttransmission þ Costverification Þ: ð11Þ
Proof. This is a static game of complete information, 2
though no dominating strategy exists in this game,
there is a mixed Nash Equilibrium point according to Proof. Given the above mentioned parameters, we could
the Table 1 as obtain the number of contacts jHj as

  1XX 1 1
g h jHj ¼ T T jNj2 : ð12Þ
ðpb ; pw Þ ¼ ; : 2 i j6¼i ij 2
wþC wþC
If the detection probability is pb , the expectation of the
If the node chooses offending strategy, its payoff is transmission and verification cost for these contact
  evidences will be
gþ" gþ"
w ðSÞ ¼ C  þw ¼ w  g  ":
wþC wþC
1 
If the node chooses forwarding strategy, its payoff is E ¼ pb jHj ¼ pb T jNj2  ðCosttransmission þ Costverification Þ:
2
w ðW Þ ¼ pb  ðw  gÞ þ ð1  pb Þ  ðw  gÞ ¼ w  g: ð13Þ
The latter one is obviously larger than the previous one. u
t
gþ"
Therefore, if TA chooses the checking probability wþC ,a
rational node must choose the forwarding strategy. Equation (12) shows that between two time slots, the
Furthermore, if TA announces it will inspect at the number of the contacts among jNj nodes is in line with
gþ"
probability pb ¼ wþC to every node, then its profit will be the time T and the square of the number of the nodes. Then,
higher than it checks all the nodes, for the cost of misbehavior detection (including evidence
  transmission and verification cost) is linear to the detection
gþ" probability pb . From Theorem 2, it is observed that the
vw  h > v  w  h: ð10Þ
wþC misbehavior detection cost could be significantly reduced if
choosing an appropriate detection probability without
Here, the latter part in the inequality is the profit of TA
compromising the security level. In the experiment section,
when it checks all the nodes. u
t
we will show that a detection probability of 10 percent is
Note that the probability that a malicious node cannot be efficient enough for misbehavior detection, which means the
gþ" k
detected after k rounds is ð1  wþC Þ ! 0, if k ! 1. Thus, it cost of misbehavior detection will be reduced to 10 percent,
is almost impossible that a malicious node cannot be which will save a lot of resource of the TA and the network.
detected after a certain number of rounds. In the simulation
section, we will show that the detected rate of malicious 4.3 Exploiting Reputation System to Further
users is close to 100 percent with a proper detection rate, at Improve the Performance of iTrust
the same time, the transmission cost is much lower than In the previous section, we have shown that the basic iTrust
inspection without iTrust. could assure the security of DTN routings at the reduced
detection cost. However, the basic scheme assumes the
4.2 The Reduction of Misbehavior Detection Cost same detection probability for each node, which may not
by Probabilistic Verification be desirable in practice. Intuitively, an honest node could be
In this section, we give a formal analysis on the misbehavior detected with a lower detection probability to further
detection cost incurred by evidence transmission and reduce the cost while a misbehaving node should be
verification. We model the movements and contacts as a detected with a higher detection probability to prevent its
stochastic process in DTNs, and the time interval t between future misbehavior. Therefore, in this section, we could
two successive contacts of nodes Ni and Nj follows the combine iTrust with a reputation system that correlates the
exponential distribution [20]: detection probability with nodes’ reputation.
The reputation system of iTrust could update node’s
P ft  xg ¼ 1  eij x ; x 2 ½0; 1Þ; reputation r based on the previous round of detection
result, and, thereafter, the reputation of this node could be
where ij is the contact rate between Ni and Nj , the used to determine its inspection probability p. We define the
expected contact interval between Ni and Nj is E½t ¼ 1ij . inspection probability p to be the inverse function of
We further denote Costtransmission as the evidences transmis- reputation r. Note that p must not be higher than the
sion cost and Costverification as the evidence signature g
bound wþC to assure the network security level, which has
verification cost for any contact. The below Theorem 2 been discussed before. Further, it is obvious that p cannot be
gives a detailed analysis on the cost incurred by iTrust. larger than 1, which is the upper bound of detection

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
28 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUARY 2014

probability. If a node’s p is 1, it means this node has been

labeled as a malicious one and, thus, should be detected for
all the time. What is more important, a node with a lower
reputation will lead to a higher inspection probability as
well as a decrease of its expected payoff w .

5 EXPERIMENT RESULTS
We set up the experiment environment with the opportu-
nistic networking environment (The ONE) simulator [21],
which is designed for evaluating DTN routing and
application protocols. In our experiment, we adopt the
First Contact routing protocol, which is a single-copy
routing mechanism, and we use our campus (Shanghai Jiao
Tong University Minhang Campus) map as the experiment
environment. The size of this area is 2:88 km2 . We set the
time interval T to be about 3 hours (10;800 s) as the default
value, and we deploy 50, 80, 100 nodes on the map,
respectively. With each parameter setting, we conduct the
experiment for 100 rounds.
We use the packet loss rate (PLR) to indicate the
misbehavior level of a malicious node. In DTNs, when a
node’s buffer is full, a new received bundle will be dropped
by the node, and PLR denotes the rate between the dropped
bundles out of the received bundles. But, a malicious node
could pretend no available buffer and, thus, drop the
bundles received. Thus, PLR actually represents the mis-
behavior level of a node. For example, if a node’s PLR is 1, it
is totally a malicious node who launches a black hole attack.
If a node’s PLR is 0, we take it as a normal node. Further, if
0 < P LR < 1, the node could launch a gray hole attack by
selectively dropping the packets. In our experiment, we use
the detected rate of the malicious nodes to measure the Fig. 3. Experiment results with user number of 100, 80, 50.
effectiveness of iTrust, and we take all the nodes whose PLR
larger than 0 as the malicious ones. On the other hand, since 5.2 The Impact of Percentage of Malicious Nodes on
a normal node may also be identified as the malicious one iTrust
due to the depletion of its buffer, we need to measure the We use malicious node rate (MNR) to denote the percentage
false alert of iTrust and show that iTrust has little impact on of the malicious nodes of all the nodes. In this experiment,
the normal users who adhere to the security protocols. we consider the scenarios of varying MNR from 10 to
Thus, we use the misidentified rate to measure the false 50 percent. In this experiment, PLR is set to be 1, and the
negative rate. Moreover, we evaluate the transmission velocity of 80 nodes varies from 10:5 to 11:5 m=s. The
overhead Costtransmission and verification overhead
message generation time interval varies from 25 to 35 s, and
Costverification in terms of the number of evidence transmis-
the TTL of each message is 300 s.
sion and verification for misbehavior detection. In the next
section, we will evaluate the effectiveness of iTrust under The experiment result is shown in Fig. 4. Fig. 4a shows
different parameter settings. that three curves have the similar trends, which indicate that
iTrust could achieve a stable performance with different
5.1 The Evaluation of the Scalability of iTrust MNRs. Even though the performance of iTrust under high
First, we evaluate the scalability of iTrust, which is shown MNR is lower than that with low MNR, the detected rate is
in Fig. 3. As we predict in (12), the number of nodes will still higher than 70 percent. Furthermore, the performance
affect the number of generated contact histories in a of iTrust will not increase a lot when the detection
particular time interval. So we just measure the detected probability exceeds 20 percent, but it is good enough when
rate (or successful rate) and misidentified rate (or false the detection probability is more than 10 percent. Thus, the
positive rate) in Fig. 3. Fig. 3a shows that when detection malicious node rate has little effect on the detected rate of
probability p is larger than 40 percent, iTrust could detect all malicious nodes. That means iTrust will be effective,
the malicious nodes, where the successful detection rate of no matter how many malicious nodes there are. Further, a
malicious nodes is pretty high. It implies that iTrust could high malicious node rate will help reduce the misidentified
assure the security of the DTN in our experiment. rate as shown in Fig. 4b because the increase of the malicious
Furthermore, the misidentified rate of normal users is nodes will reduce the proportion of the normal nodes who
lower than 10 percent when user number is large enough, as will be misidentified. However, all the misidentified rates in
shown in Fig. 3b, which means that iTrust has little impact Fig. 4b will be no more than 20 percent, which means iTrust
on the performance of DTN users. Therefore, iTrust has little effect on the normal nodes. Since the cost is linear
achieves a good scalability. to the detection probability, iTrust will save a lot of

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
ZHU ET AL.: A PROBABILISTIC MISBEHAVIOR DETECTION SCHEME TOWARD EFFICIENT TRUST ESTABLISHMENT IN DELAY-TOLERANT... 29

Fig. 4. Experiment results with different MNRs.

resources on the inspection if choosing a small but different MNRs and PLRs. It is obvious that iTrust will
appropriate detection probability. significantly reduce the misbehavior detection cost.
The above experiment results demonstrate that iTrust
5.3 The Impact of Various Packet Loss Rate on could achieve a good performance gain due to the following
iTrust two reasons. First, the detection performance of iTrust will
In the previous section, we have shown that iTrust could not increase significantly as the increase of detection
also thwart the gray hole attack. In this section, we evaluate probability. Second, the inspection cost will increase along
the performance of iTrust with different PLRs. In this with the increase of the detection probability. Thus, we
experiment, we measure the scenarios of varying PLR from suggest a lower detection probability such as 10 or 20 percent.
100 to 80 percent. We set MNR as 10 percent, and the speed And given the analysis of the inspection game, TA could set a
of 80 nodes varying from 10:5 to 11:5 m=s. The message proper punishment to ensure the detection probability. In
generation interval varies from 25 to 35 s, and the TTL of this way, TA could thwart the misbehavior of the malicious
each message is 300 s. The experiment result is shown in nodes and stimulate the rational nodes.
Fig. 5. Also, PLRs have little effect on the performance of
iTrust, as shown in Fig. 5a. 5.5 The Impact of Nodes’ Mobility
This implies iTrust will be effective for both black hole Besides the number of nodes and the length of inspection
attack and gray hole attack. The misidentified rate is not period, there are some other potential factors that will
affected by PLRs either. It is under 8 percent when the contribute to the cost of contact history authentication, one
detection probability is under 10 percent. Thus, the of which is the node’s speed. In the previous experiment,
variation of PLR will not affect the performance of iTrust. we set the node’s speed in the range of 10:5 to 11:5 m=s. In
this experiment, we will change the velocity of the node,
5.4 The Impact of Choosing Different Detection and the experiment result is shown in Fig. 7. The variation
Probabilities of the speed will not affect the effectiveness of iTrust on
In this section, we discuss the impact of choosing different both of the detected rate and misidentified rate, which has
detection probabilities on the performance of iTrust. In been shown in Figs. 7a and 7b. Fig. 7a implies in a high-
Fig. 6a, it is shown that iTrust will reduce the authentication speed network, iTrust will be more efficient in misbehavior
cost of the thousands of contact histories, which is in line detection when the detection probability is small. Fig. 7b
with the detection probability. And Fig. 6b implies that iTrust indicates that the misidentified rate is irrelevant with the
will significantly reduce transmission overhead compared speed. It is because that a lower speed will lead to a smaller
with the DTN without iTrust. This means iTrust will improve chance of packet forwarding, but a higher speed will lead to
the detection performance of TA and save the transmission a quicker depletion of the nodes’ buffer. So they will drop
cost. Figs. 6c and 6d show the cost of the inspection under some packets before they forward the data at the speed

Fig. 5. Experiment results with different PLRs.

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
30 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUARY 2014

Fig. 6. Experiment results with different detection probabilities.

11 m=s. But a higher speed will make the packet more easily necessary any more, and the cost thus will be reduced. This
reach the destination node, which will reduce the mis- result further demonstrates the efficiency of iTrust again.
identified rate again. The cost of inspection is almost the
5.6 The Impact of Message Generation Interval on
same as shown in Fig. 7c. But the higher speed will iTrust
inevitably help to generate more contact chances, which
We also measure the effect of the message generating rate
will increase the cost of contact history authentication. on iTrust. The message generation interval is the time
Fig. 7d shows that iTrust will reduce the authentication cost between two message generating events, which describes
much more when the speed of nodes is very high. Because, the demand of the users in the network. In a high-density
at the high speed, a large detection probability is not network, the message generation interval is short because

Fig. 7. Experiment results with different velocities of the nodes.

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
ZHU ET AL.: A PROBABILISTIC MISBEHAVIOR DETECTION SCHEME TOWARD EFFICIENT TRUST ESTABLISHMENT IN DELAY-TOLERANT... 31

Fig. 8. Experiment results with different message generation interval.

of the large demand of users. The experiment result is [2] T. Hossmann, T. Spyropoulos, and F. Legendre, “Know the
Neighbor: Towards Optimal Mapping of Contacts to Social
shown in Fig. 8. Fig. 8a shows that the performance of
Graphs for DTN Routing,” Proc. IEEE INFOCOM ’10, 2010.
iTrust at long message generation interval (85-95 s) is not as [3] Q. Li, S. Zhu, and G. Cao, “Routing in Socially Selfish Delay-
good as that at a short message generation interval. This is Tolerant Networks,” Proc. IEEE INFOCOM ’10, 2010.
because the messages propagation in the network does not [4] H. Zhu, X. Lin, R. Lu, Y. Fan, and X. Shen, “SMART: A Secure
involve all the malicious nodes in the network due to the Multilayer Credit-Based Incentive Scheme for Delay-Tolerant
Networks,” IEEE Trans. Vehicular Technology, vol. 58, no. 8,
shortage of the messages. But if the messages are enough, pp. 828-836, 2009.
the detected rate of malicious nodes will be more than [5] H. Zhu, X. Lin, R. Lu, P.-H. Ho, and X. Shen, “SLAB: Secure
90 percent at a small detection probability (e.g., 10 percent). Localized Authentication and Billing Scheme for Wireless Mesh
So, if the network is not busy, TA could extend the Networks,” IEEE Trans. Wireless Comm., vol. 17, no. 10, pp. 3858-
inspection interval, for example, from 3 to 6 hours, the low 3868, Oct. 2008.
[6] Q. Li and G. Cao, “Mitigating Routing Misbehavior in Disruption
inspection frequency will reduce more inspection cost Tolerant Networks,” IEEE Trans. Information Forensics and Security,
because the malicious ones are all involved. But the low vol. 7, no. 2, pp. 664-675, Apr. 2012.
message generation frequency also has some advantages [7] S. Marti, T.J. Giuli, K. Lai, and M. Baker, “Mitigating Routing
for TA. As shown in Fig. 8b. The misidentified rate will Misbehavior in Mobile Ad Hoc Networks,” Proc. ACM
MobiCom ’00, 2000.
decrease when the message generation interval is long.
[8] R. Lu, X. Lin, H. Zhu, and X. Shen, “Pi: A Practical Incentive
Another advantage of low message generation interval is Protocol for Delay Tolerant Networks,” IEEE Trans. Wireless
cost saving as shown in Fig. 8c. So there is a tradeoff Comm., vol. 9, no. 4, pp. 1483-1493, Apr. 2010.
between the detected rate and misidentified rate when the [9] F. Li, A. Srinivasan, and J. Wu, “Thwarting Blackhole Attacks in
message generation interval varies. Disruption-Tolerant Networks Using Encounter Tickets,” Proc.
IEEE INFOCOM ’09, 2009.
[10] E. Ayday, H. Lee, and F. Fekri, “Trust Management and
6 CONCLUSION Adversary Detection for Delay-Tolerant Networks,” Proc. Military
Comm. Conf. (Milcom ’10), 2010.
In this paper, we propose a probabilistic misbehavior [11] D. Fudenberg and J. Tirole, Game Theory. MIT Press, 1991.
detection scheme (iTrust), which could reduce the detection [12] M. Rayay, M.H. Manshaeiy, M. Flegyhziz, and J. Hubauxy,
“Revocation Games in Ephemeral Networks,” Proc. 15th ACM
overhead effectively. We model it as the inspection game Conf. Computer and Comm. Security (CCS ’08), 2008.
and show that an appropriate probability setting could [13] S. Reidt, M. Srivatsa, and S. Balfe, “The Fable of the Bees:
assure the security of the DTNs at a reduced detection Incentivizing Robust Revocation Decision Making in Ad Hoc
overhead. Our simulation results confirm that iTrust will Networks,” Proc. 16th ACM Conf. Computer and Comm. Security
(CCS ’09), 2009.
reduce transmission overhead incurred by misbehavior [14] B.B. Chen and M.C. Chan, “Mobicent: A Credit-Based
detection and detect the malicious nodes effectively. Our Incentive System for Disruption-Tolerant Network,” Proc. IEEE
future work will focus on the extension of iTrust to other INFOCOM ’10, 2010.
kinds of networks. [15] S. Zhong, J. Chen, and Y.R. Yang, “Sprite: A Simple Cheat-Proof,
Credit-Based System for Mobile Ad-Hoc Networks,” Proc. IEEE
INFOCOM ’03, 2003.
[16] J. Douceur, “The Sybil Attack,” Proc. Revised Papers from the First
ACKNOWLEDGMENTS Int’l Workshop Peer-to-Peer Systems (IPTPS ’01), 2001.
This research was supported by National Natural Science [17] R. Pradiptyo, “Does Punishment Matter? A Refinement of the
Inspection Game,” Rev. Law and Economics, vol. 3, no. 2, pp. 197-
Foundation of China (Grant No. 61003218, 70971086, 219, 2007.
61272444, 61161140320, 61033014), Doctoral Fund of Minis- [18] J. Burgess, B. Gallagher, D. Jensen, and B. Levine, “Maxprop:
try of Education of China (Grant No. 20100073120065), JSPS Routing for Vehicle-Based Disruption-Tolerant Networks,” Proc.
A3 Foresight Program, and NEC C&C Foundation. Profes- IEEE INFOCOM ’06, 2006.
[19] A. Lindgren and A. Doria, “Probabilistic Routing Protocol for
sor Suguo Du is the corresponding author of this paper. Intermittently Connected Networks,” draft-lindgren-dtnrg-pro-
phet-03, 2007.
[20] W. Gao and G. Cao, “User-Centric Data Dissemination in
REFERENCES Disruption-Tolerant Networks,” Proc. IEEE INFOCOM ’11, 2011.
[1] R. Lu, X. Lin, H. Zhu, and X. Shen, “SPARK: A New VANET- [21] A. Keranen, J. Ott, and T. Karkkainen, “The ONE Simulator for
Based Smart Parking Scheme for Large Parking Lots,” Proc. IEEE DTN Protocol Evaluation,” Proc. Second Int’l Conf. Simulation Tools
INFOCOM ’09, Apr. 2009. and Techniques (SIMUTools ’09), 2009.

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.
32 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUARY 2014

Haojin Zhu (M’09) received the BSc degree in Mianxiong Dong received the BS and MS
2002 from Wuhan University, China, the MSc degrees in computer science and engineering
degree in 2005 from Shanghai Jiao Tong from the University of Aizu, Japan in 2006 and
University, China, both in computer science, 2008, respectively. He is a JSPS research fellow
and the PhD degree in electrical and computer with the School of Computer Science and
engineering from the University of Waterloo, Engineering, the University of Aizu. He was
Canada, in 2009. He is currently an associate selected by JSPS Excellent Young Researcher
professor with the Department of Computer Overseas Visit Program from April 2010 to
Science and Engineering, Shanghai Jiao Tong March 2011. From January 2007 to March
University, China. His current research interests 2007, he was a visiting scholar of West Virginia
include wireless network security and distributed system security. He is University. From August 2007 to September 2007, he was a research
a corecipient of best paper awards of IEEE ICC 2007 - Computer and associate at Tsukiden Software Philippines, Philippines. He was also a
Communications Security Symposium and Chinacom 2008- Wireless foreigner research fellow of NEC C&C Foundation, Japan and a
Communication Symposium. He served as a guest editor for IEEE research fellow of Circle for the Promotion of Science and Engineering,
Networks and an associate editor for KSII Transactions on Internet and Japan. He received the Best Paper Award of IEEE HPCC 2008 and
Information Systems, and Ad Hoc & Sensor Wireless Networks. He IEEE ICESS 2008. He is currently a research scientist with A3 Foresight
currently serves as the Technical Program Committee for international Program (2011-2014) funded by JSPS, NSFC of China, and NRF of
conferences such as INFOCOM, GLOBECOM, ICC, WCNC, and so on. Korea. His research interests include wireless sensor networks,
He is a member of the IEEE. vehicular ad hoc networks, wireless security, and pervasive computing.
He is a member of the IEEE.

Suguo Du received the BSc degree in Zhenfu Cao (SM’10) received the BSc degree in
applied mathematics from Ocean University computer science and technology and the PhD
of Qingdao, China, in 1993, the MSc degree degree in mathematics from Harbin Institute of
in mathematics from Nanyang Technological Technology, Harbin, China, in 1983 and 1999,
University, Singapore, in 1998, and the PhD respectively. He was exceptionally promoted to
degree in control theory and applications an associate professor in 1987 and became a
centre from Coventry University, United King- professor in 1991. He is currently a distinguished
dom, in 2002. She is currently an associate professor and the director of the Trusted Digital
professor at Management Science Department Technology Laboratory, Shanghai Jiao Tong
in Antai College of Economics & Manage- University, Shanghai, China. He also serves as
ment, Shanghai Jiao Tong University, China. Her current research a member of the expert panel of the National Nature Science Fund of
interests include risk and reliability assessment, fault tree analysis China. He is actively involved in the academic community, serving as a
using binary decision diagrams, fault detection for nonlinear system, committee/session chair and a program committee member for several
and wireless network security management. international conference committees, as follows: the IEEE Global
Communications Conference (since 2008), the IEEE International
Zhaoyu Gao (S’12) received the BSc degree in Conference on Communications (since 2008), the International Con-
applied mathematics in 2009 from Wuhan ference on Communications and Networking in China (since 2007), and
University, China, and is currently working so on. He is the associate editor of Computers and Security (Elsevier),
toward the MSc degree in the Department of an editorial board member of Fundamenta Informaticae (IOS) and Peer-
Computer Science and Engineering, Shanghai to-Peer Networking and Applications (Springer- Verlag), and the guest
Jiao Tong University, China. His research editor of the Special Issue on Wireless Network Security, Wireless
interests include cognitive radio network, secur- Communications and Mobile Computing (Wiley), and so on. He has
ity and privacy of wireless network. He is a received a number of awards, including the Youth Research Fund
student member of the IEEE. Award of the Chinese Academy of Science in 1986, the Ying-Tung Fok
Young Teacher Award in 1989, the National Outstanding Youth Fund of
China in 2002, the Special Allowance by the State Council in 2005, and
a corecipient of the 2007 IEEE International Conference on Commu-
nications Computer and Communications Security Symposium Best
Paper Award in 2007. He also received seven awards granted by the
National Ministry and governments of provinces such as the first prize of
the Natural Science Award from the Ministry of Education. He is a senior
member of the IEEE.

. For more information on this or any other computing topic,

please visit our Digital Library at www.computer.org/publications/dlib.

Authorized licensed use limited to: University of Pittsburgh. Downloaded on February 09,2021 at 19:53:02 UTC from IEEE Xplore. Restrictions apply.