SECURITY INFORMATICS AND TERRORISM: PATROLLING THE WEB
NATO Science for Peace and Security Series This Series presents the results of scientific meetings supported under the NATO Programme: Science for Peace and Security (SPS). The NATO SPS Programme supports meetings in the following Key Priority areas: (1) Defence Against Terrorism; (2) Countering other Threats to Security and (3) NATO, Partner and Mediterranean Dialogue Country Priorities. The types of meeting supported are generally “Advanced Study Institutes” and “Advanced Research Workshops”. The NATO SPS 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 2006 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.springer.com http://www.iospress.nl
Sub-Series D: Information and Communication Security – Vol. 15
ISSN 1874-6268
Security Informatics and Terrorism: Patrolling the Web Social and Technical Problems of Detecting and Controlling Terrorists’ Use of the World Wide Web
Edited by
Cecilia S. Gal Rutgers University, USA
Paul B. Kantor Rutgers University, USA
and
Bracha Shapira Ben-Gurion University of the Negev, Israel
Amsterdam • Berlin • Oxford • Tokyo • Washington, DC Published in cooperation with NATO Public Diplomacy Division
Proceedings of the NATO Advanced Research Workshop on Security Informatics and Terrorism – Patrolling the Web Beer-Sheva, Israel 4–5 June 2007
© 2008 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 978-1-58603-848-9 Library of Congress Control Number: 2008922759 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
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
v
Editors’ Introduction 1
This book is based on presentations given at the NATO Advanced Research Workshop on “Security Informatics and Terrorism – Patrolling the Web” that was held in June 2007 in Israel. The two day workshop included presentations by scholars, researchers and practitioners from several related fields (computer science, information retrieval, data mining, and terror and intelligence experts). The speakers and participants were scientists from prestigious institutes, security consulting firms, and representatives of official government agencies and practitioners. The workshop’s primary aim was to initiate a discussion and sharing of ideas among experts in quite diverse disciplines, and especially between computer scientists and terrorism experts. Most speakers were recruited by the directors, based on their academic and professional experience and performance. All talks specifically included introductory and summary remarks that were clear to the full range of experts participating. During the closing panel discussion some conclusions about the problems of patrolling the Web, and desired action items were drawn up.
Audience This work is intended to be of interest to counter-terrorism experts and professionals, to academic researchers in information systems, computer science, political science, and public policy, and to graduate students in these areas. The goal of this book is to highlight several aspects of patrolling the Web that were raised and discussed during the workshop by experts from different disciplines. The book includes academic studies from related technical fields, namely, computer science, and information technology, the strategic point of view as presented by intelligence experts, and finally the practical point of view by experts from related industry describing lessons learned from practical efforts to tackle these problems. This volume is organized into four major parts: definition and analysis of the subject, data-mining techniques for terrorism informatics, other theoretical methods to detect terrorists on the Web, and practical relevant industrial experience on patrolling the Web. Part I addresses the current status of the relationship between terrorists and the Internet. The presenters are experienced intelligence experts and describe the causes and impacts of terrorists’ use of the Web, the current status, and the governmental responses, and provide an overview of methods for the detection of, and the prevention of terrorist use of the Web, in different parts of the world. Part II addresses data and Web mining techniques for identifying and detecting terrorists on the Web. The presenters are primarily computer scientists and they present 1
For a variety of reasons most, but not all, of the presentations could be included in this book. A complete list of the presenters and their contact information is given in Appendix 1. Readers can find slides of some of the presentations posted on: http://cmsprod.bgu.ac.il/Eng/conferences/Nato/Presentations.htm
vi
recent studies suggesting data-mining techniques that are applicable for detecting terrorists and their activities on the Web. Part III addresses theoretical techniques (other than data mining) applicable to terrorism informatics. The presenters are again computer and information scientists, but they propose computational methods that are not (presently) commonly used in terrorism informatics. These papers suggest new directions and promising techniques for the detection problem, such as visual recognition, information extraction and machine learning techniques. Part IV reports on “learning from experience” and the presenters are industry practitioners who describe their applications and their experiences with operations attempting to patrol the Web. Together, the participants worked to fashion a summary statement, drawing attention to the strengths and the limitations of our present efforts to patrol and limit the use of the World Wide Web by terrorist organizations. The summary statement may be regarded as representing a consensus, but the reader is cautioned that not every participant agrees with every element of the summary.
Summary Statement As the proceedings show, a wide range of topics were discussed, and several points of view were presented. In a final session reflecting upon the entire workshop, participants identified a number of key points which should be kept in mind for future studies and efforts to limit the effectiveness of the World Wide Web as an aid to terrorists. These key points can be divided into two areas: 1) Social/Policy Issues, and 2) more narrow Technical Issues.
1. Social and Policy Issues The Internet is used by terrorists for various activities such as recruitment, propaganda, operations, etc., without their physically meeting. But the Internet can be used to track the conspirators once they are identified. Some activities are open, others are hidden. The struggle against terrorism is the quintessential example of asymmetric warfare. In addition, terrorism stands on the ill-defined boundary where criminality, warfare, and non-governmental actors meet. It was agreed that, collectively, nations have the resources needed to counter terrorism, but that it is essential to share information in order to combat the geographically distributed nature of the terrorist organizations, which may have a very small footprint in any one nation. Therefore a key recommendation of the workshop is that: International cooperation is required among intelligence and law enforcement experts and computer scientists. Other policy issues concern the interplay between the called-for cooperation, and the rights of individual citizens. This may be formulated as a technical question: “Can data mining truly protect privacy when the data is held and mined by ‘distrusted’ custodians?”. This important question was not addressed at the present workshop, but should definitely be on the agenda for future research. At the interface between policy and technical matters, several participants stressed that some idea of a scheme, a model or a scenario is needed to interdict terrorists, be-
vii
cause simple searching cannot cover every possibility. Therefore, whatever technical means and alarms are developed will have to be triggered by considerations of likelihood or probability, and/or by existing intelligence from other sources.
2. Technical Issues As noted, technical means and alarms will have to be triggered by considerations of likelihood or probability, and/or by existing intelligence from other sources. In summary, a second key agreement is that: It is necessary to have people in the analytical loop, supplying human judgment. An important point to consider in patrolling the Web for terrorism is that rates of false positives are necessarily high for any automated method of identification or discovery. As noted, the search must be moderated by some understanding of plausible scenarios. There is a clear interface to policy and social issues when considering the consequences of “false positive” (that is, naming a person, an organization, or a website as terrorist when it is not) which must be weighed, and balanced, against the consequences of failing to identify terrorist activity on the Web. It was noted that computers work “from the bottom up”, digesting large masses of data and producing indications of when something is out of the ordinary. Human analysts, in contrast, work “from the top down”, guided by models or scenarios which may be drawn from previous experience, or may be suggested, for the very first time, by some configuration in the available data. In working to make the computer a more powerful ally, it would be of immense value to have some common “challenge tasks”. This is the final finding of the workshop: It is necessary to have some model tasks which are well defined, and which have a “gold standard” known correct resolution or answer. Ideally these model challenges should be driven by the real missions of the several NATO nations. It was noted that most of the presentations dealt with websites in English, and a few with sites in Arabic. All of the technical work needs also to be extended to other languages. Overall, there was an extremely effective exchange of ideas and of concerns between the experts in technical/computer issues and the experts in social/policy issues. It is highly recommended that this type of boundary spanning workshop be expanded and replicated in the future. Bracha Shapira Paul Kantor Cecilia Gal.
A note on the production of this volume The papers of this volume have been produced by a multi-step process. First, we recorded the talk given by each author at the conference in June (due to some technical difficulties a few presentations were not recorded). Next, we transcribed each recording. The authors then produced a draft of their paper from these transcriptions, refining each draft until the final version. Although the papers are not exactly like the talks given,
viii
some do retain the informal and conversational quality of the presentations. Other authors, however, preferred to include a more formal paper based on the material presented at the conference. A few notes about language and conventions used in the book. Since the authors in this volume come from different parts of the globe we have tried to preserve their native cadences in the English versions of their papers. We have also decided to use both British English and American English spelling and standards depending on the specific style the author preferred to use. Language conventions for naming entities – such as Al Qaeda, 9/11 or Hezbollah – which have more than one standard spelling, were taken from the New York Times editorial practices. The formatting and style of references, when used, are consistent within each paper but vary between papers. And finally, a number of papers have pictures from screen captures of illustrations or of proprietary software. Although every effort was made to include the highest quality pictures so they would reproduce well in print, in some instances these pictures may not reproduce as well as might be desired, and we beg the reader’s indulgence. Cecilia Gal, Rutgers.
Acknowledgements It is a pleasure to acknowledge the superb hospitality of Ben-Gurion University, which provided their magnificent faculty Senate Hall for the two days of the Conference, together with excellent audio-visual support. The Deutsche Telekom Laboratory at BGU, and Dr. Roman Englert provided additional hospitality for the participants. We want to thank Rivka Carmi the President of Ben-Gurion University for her gracious welcome, Yehudith Naftalovitz and Hava Oz for all their hard work with the conference arrangements and Professor Fernando Carvalho Rodrigues and Elizabeth Cowan at NATO for their generous support.
ix
Contents Editors’ Introduction Bracha Shapira, Paul Kantor and Cecilia Gal
v
Part One. The Social and Political Environment The Internet and Terrorism Yaakov Amidror
3
Understanding International “Cyberterrorism”: A Law Enforcement Perspective Marc Goodman
8
Global Threats – Local Challenges. Current Issues of Intelligence Tasking and Coordination in the Rapidly Changing Threat Environment Janusz Luks Cybercrime and Cyberterrorism as a New Security Threat Vladimir Golubev The Enemy Within: Where Are the Islamist/Jihadist Websites Hosted, and What Can Be Done About It? Yigal Carmon
17 20
26
Part Two. Discovering Hidden Patterns of Activity Mining Users’ Web Navigation Patterns and Predicting Their Next Step José Borges and Mark Levene
45
Data Mining for Security and Crime Detection Gerhard Paaß, Wolf Reinhardt, Stefan Rüping and Stefan Wrobel
56
Enhancement to the Advanced Terrorist Detection System (ATDS) Bracha Shapira,Yuval Elovici, Mark Last and Abraham Kandel
71
Discovering Hidden Groups in Communication Networks Jeff Baumes, Mark K. Goldberg, Malik Magdon-Ismail and William A. Wallace
82
Part Three. Knowledge Discovery in Texts and Images Authorship Attribution in Law Enforcement Scenarios Moshe Koppel, Jonathan Schler and Eran Messeri Bayesian Models, Prior Knowledge, and Data Fusion for Monitoring Messages and Identifying Actors Paul B. Kantor Entity and Relation Extraction in Texts with Semi-Supervised Extensions Gerhard Paaß and Jörg Kindermann
111
120 132
x
Data Compression Models for Prediction and Classification Gordon Cormack
142
Security Informatics in Complex Documents G. Agam, D. Grossman and O. Frieder
156
Visual Recognition: How Can We Learn Complex Models? Joachim M. Buhmann
166
Approaches for Learning Classifiers of Drifting Concepts Ivan Koychev
176
Part Four. Some Contemporary Technologies and Applications Techno-Intelligence Signatures Analysis Gadi Aviran
193
Web Harvesting Intelligent Anti-Terror System – Technology and Methodology Uri Hanani
202
How to Protect Critical Infrastructure from Cyber-Terrorist Attacks Yuval Elovici, Chanan Glezer and Roman Englert
224
Appendix 1: Conference Participants
233
Author Index
237
Part One The Social and Political Environment
This page intentionally left blank
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
3
The Internet and Terrorism Yaakov AMIDROR 1 Vice President of Lander Institute, Jerusalem, Israel Head of ICA Project, Jerusalem Center for Public Affairs, Israel
Abstract. Terrorism was part of our lives before the Internet and it will be a part of our lives even if we have all the means and all the possibilities to control the Internet some day. So when we look at the Internet as a tool for terrorists, we must remember that at the end of the day, the Internet is not the source of terrorism and the Internet is not the only way to implement terrorism. There are four major areas where the Internet has had a major impact on terrorist activities First, the Internet has become a substitute for the “open squares” in cities, the Internet as an anonymous meeting place for radicals of like minds. Second, non-governmental organizations can spread propaganda, stories, movies, pictures, about their successes and no one can stop them. Third, the Internet is used by terrorists as a source of information. Fourth, the Internet can be employed as a command and control vehicle; operational coordination via the Internet. Finally, a smaller point, the Internet can be used by terrorist organizations to raise money for their activities. Anti-terrorist organizations can also use the Internet to collect information on known terrorists and ultimately democratic governments can find the standards that are needed and share knowledge about the way that terrorists are using the Internet, and in the long run the governmental systems will prevail and not the terrorist organizations.
Keywords. Cyber terrorism, Internet, Terrorism
Good morning. Let me say that I am very glad to be with you here in Beer-Sheva. I welcome you here. I thought, during the long drive from my home in the center of Israel to Beer-Sheva, that in a way we are exaggerating. In a way, if we think that terrorism without the Internet cannot survive, or that terrorism is a result of the Internet, or the Internet is something that is critical for terrorism, that is not true. I can tell you from my own experience. I have been involved in fighting terrorism since 1969, when I was a young officer in the territories dealing with Arafat and his followers, and this was before the Internet. We fought Hezbollah before the Internet existed as an international communication system. Maybe in some exotic areas in the United States, back then, the Internet existed, but for the terrorists it was not a tool. At the end of the day, terrorism was part of our lives before the Internet and it will be a part of our lives even if we have all the means and all the possibilities to control the Internet some day. I think that some sense of proportion is needed in this discussion about the Internet and terrorism. At the same time that the Internet is flourishing all around the world, 1
Corresponding Author: Yaakov Amidror, Email:
[email protected]
4
Y. Amidror / The Internet and Terrorism
since 9/11 Al Qaeda hasn’t succeeded in carrying out any new operations in the United States. In all these years of very good Internet connections inside Israel, and outside Israel, Al Qaeda hasn’t succeed in carrying out any actions inside Israel. We can see that in some areas where Al Qaeda had some success, like the operation in London, the operation was not connected at all to the Internet. They could do it without using the Internet, they did do it with the Internet. So when we look at the Internet as a tool for terrorists, we must remember that at the end of the day, the Internet is not the source of terrorism and the Internet is not the only way to implement terrorism. Having said that, I want to go to four areas, actually four and a half areas, in which the terrorist organizations use the Internet as a very important machine or tool to enhance their capabilities.
1. Internet as a Meeting Place The first one, which I think is one of the most important, is the Internet as a substitute for the “open squares” in cities. In the past, when someone wanted to hear the preacher in order to get some information, or to get the ideology, he had to go to a club or to a meeting somewhere. And consequently it was very easy for us, the intelligence organization, to understand, to know, and if needed, to track these people from their homes to the venue where they heard the one who is preaching for terrorism. This is the case in Israel; it is the case all around the world. Today is the first time in history that all of these terrorist leaders, preachers, ideologists, can spread their ideas all around the world at the same time to millions of people. No one knows who is listening to these preachers, who will come to the meeting again, who is becoming more and more caught up in this process of becoming slowly, slowly more extremist, as they understand and begin to believe in these preachers. It is the first time in history that you can organize many, many people without bringing them together in a physical place. You can preach without directly seeing these people. You can bring them the ideology without being face-to-face with them, and no one around the world can know who is there and who is not. And I think that this is more important than all the other very interesting and esoteric uses of the Internet, the fact that the terrorist can preach around the world at the same time to millions, to convince people to go into the circles in which they will be not only affiliated with the ideas but also part of the system. It is a slow process; nobody is born to be a terrorist. It is a slow process that can take months or years. I do not believe that someone will become a terrorist in a few days. This is, I think, the most important development in this area because of the Internet and only because of the Internet. This is something new.
2. Non-Governmental Organizations Can Spread Propaganda Connected to the above and important enough to mention as a separate category, is that this is the first time that organizations which are non-governmental organizations can spread propaganda, stories, movies, pictures, about their successes and no one can stop it. There is nothing more important to the success of the terrorist organization than that they can show others that they are succeeding. The Internet gives them a way of spreading their operations all around the world, without any censorship, and nobody
Y. Amidror / The Internet and Terrorism
5
can stop it. One can watch the success of Hezbollah from Australia. Or one can look at the success in Iraq from inside Israel, and nobody can stop people from watching these transmissions, at least in democratic countries. The fact is, they can spread the message of their success all around the world immediately; almost at the same time that the event is taking place in Iraq, one can see the pictures in Israel -- it takes an hour or two and you have all the pictures. It is a realtime propaganda. These organizations gain life from their success, so they want to show around the world that they are doing a very good job fighting the Israelis, fighting the Americans, fighting the infidels, whoever. So for them it is a very important tool. So this is a new phenomenon and it exists only because of the Internet. Nobody can control the way that they are spreading their propaganda, mainly through pictures, all around the world.
3. The Internet as an Information Source The third area that the Internet is very helpful for these terrorist organizations is in collecting information. Of course, it is true that it is helping governments as well, but governments had this ability in the past because of the intelligence organizations that they had to collect information, even if it is a very complicated process. For nongovernmental organizations it was almost impossible, or at least very, very hard. Think about the picture of a target in Tel Aviv. In the past, they had to send someone to Tel Aviv to photograph it, to go in and out through some check points in Lod Airport. If it was someone whose name was on the watch list it was not so easy to do this. And then the issue of taking the photo, if the target is in a sensitive area, this is also not so easy. So they need a process to get the photo of this target if it is in Tel Aviv or in BeerSheva or elsewhere. Today all they have to do is go to the Web, to Google Earth™, and get the picture they need for their operation. The fact that information so necessary for their operations is on the Web is making the life of those people who are thinking about carrying out terrorist operations much easier. In the past non-governmental organizations didn’t have the resources to collect this type of information as easily as they can today. And for them, in this instance, the Internet is more important and more helpful than it is for governmental organizations, many elements of information that, in the past, we had to send our people around the world to collect, today can be easily found on the Internet. I remember as a young officer, a Captain, when we planned an operation against Fatah in Beirut, we had to send some of our guys into Beirut to learn the streets which lead to the target and back. Today, we can go to the map of the world on the Internet and get the information we need for such an operation. In the past, as a government it was very easy for us to send people into Beirut and collect the information. It was not that easy for non-governmental organizations in the past to do the same, but now they have access to it on the Web as easily as we have it.
4. Command and Control Via the Internet The fourth area, in which the Internet is very helpful, is the one most people like to think is the most important one. Personally, I don’t think this is the most important.
6
Y. Amidror / The Internet and Terrorism
This is communication between the headquarters and the operational people on the ground, and among the operational people. I usually tell a story about four people sitting in four different places all around the world. They don’t know each other; they are getting information through the Web. One is using a code of agricultural terms, another one is using retail terms to communicate in code. Technically they can hide the source of the information using servers all over the world and they are getting all the information they need to plan an operation, even pictures, which were taken by another guy who is using third generation cellular phones to make photos in and around the target. And slowly, slowly they gather all the information they need, all the details of the operation. Then someone that they don’t know invites them to a restaurant somewhere in London. They don’t know each other. When they come to the restaurant, waiting for each of them there is a table and chair and an envelope, and in the envelope there is some money. The boss of the restaurant says “sorry Mr. John Reed the person who invited you cannot come but he sent you the money and the information that you needed”. The restaurant boss does not know anything about it, they don’t know anything, but they have a key to a lock somewhere in the train station where the explosive is hidden. The explosive they cannot move via the Web. This is something in the real world that someone has to carry from somewhere, Iran or Iraq maybe. So each of them has a very clear understanding what he should do, where he is going now, what time he is opening the case, what time he is operating, everything he needs to know. And they don’t know each other. They did not meet each other. And they will not meet each other, they don’t know who sent them all these materials, and everything is done through the Web. And the chance of an intelligence organization being able to track and find these four people, who are not connected and never were connected, people who are using coded words of agriculture, retail and commodities in their communications, is almost zero. The only part, in which the real world is involved in the operation is when someone has to bring the explosive to the site of the operation; this cannot be done through the Internet. This is an example of how the Internet can be used for such operations.
5. Weaknesses of the Internet for Terrorists What are the weak points of the system from the point of view of the counter-terrorist organizations. I think that there is one, philosophically, one great weak point. To find the “goldfish” in such a huge sea is almost impossible. To identify the one who is the terrorist, the one that we are looking for is very, very difficult. However, once we identify him on the Web, the details that we can learn about him through the Web are enormous. So the first part, to identify the guy we are looking for is very complicated. After he is identified, however, we can know everything about him. And, in the future, we will know even more. In the future, he will have a smart house and we will know what he is eating, when he’s out of bread, when he’s coming home, when he opened the door and so on and so forth. As the system is becoming more sophisticated it will be more complicated to identify him but it will also enable us to have more details after he has been identified. This is philosophically the point.
Y. Amidror / The Internet and Terrorism
7
And in the end I am very optimistic. I am very optimistic because these systems that involve the Internet need a lot of money to make them untraceable, and you need to invest a lot of energy and know-how. At the end of the day, governments, and states, have more money and more know-how and more energy than non-governmental organizations. For the present, Al Qaeda can use it, Hezbollah is using it, Hamas is using it, all these organization are using the Internet. But it is only a question of time before the free world will organize itself and after investing money, time, people and sharing information with each other, states will be in a better position to deal with the terrorist websites and Internet networks than non-governmental organizations. So we are now in a very delicate situation in which we know that these organizations use the Internet as a tool for all the four purposes that I mentioned. The “half” purpose I mentioned earlier is to collect money. Although from our experience, most of the money being used is cash. But some of it is through the Web. But I think that if we will act, by “we” I mean the free world, those who want to fight the terrorists, if we will act together and find the standards that are needed and we share our knowledge about the way that they are using the Internet, at the end of the day, the governmental systems will prevail and not the terrorist organizations. Then we will find ourselves, as in the old days, fighting terrorists who maybe won’t use the Internet but, nonetheless, have a very strong will to implement terrorist actions.
8
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
Understanding International “Cyberterrorism”: A Law Enforcement Perspective Marc GOODMAN 1 Interpol Steering Committee on Information Technology Crime, INTERPOL, Lyon, France
Abstract. Cyber terrorism is a commonly heard expression but lacks definition and precision. Does it apply to terrorists’ use of the Internet or to computer attacks against critical infrastructures? There are many entities that play a role in this complex topic from governments, technology and telecommunication service providers to the terrorists themselves. This paper explores the role of law enforcement in the international fight against terrorists’ use of the Internet and provides an overview of the wide extent to which terrorists and their support structures have fully embraced cyber space. Keywords. Cyber crime, Cyber terrorism, Terrorist use of the Internet, Law enforcement in cyber space
Introduction Thank you, thank you very much. Good morning. We’ll make this an informal conversation. If you have any questions please let me know. Today, I would like to thank Ben-Gurion University, NATO, Bracha and Paul for having invited me here. It’s my great honor to be with you. Early on Paul said that he wanted differing perspectives on cyber terrorism and I hope to provide you with the law enforcement perspective on how police and security officials regard the topic of cyber crime and cyber terrorism.
1. Interpol I thought first, it would be useful for a moment to talk about Interpol itself. In some regards it is somewhat similar to the United Nations in that it is an organization of member states or member countries. After the United Nations, Interpol has more member states than any other international organization, with 186 members around the world, which is a good advantage for the organization. Interpol works with law enforcement entities around the world and works through the national law enforcement authorities in nearly 200 countries. So for example, Israel 1
Corresponding Author: Marc Goodman, Senior Advisor, Interpol Steering Committee on Information Technology Crime, INTERPOL, General Secretariat, 200, quai Charles de Gaulle, 69006 Lyon, France; Email:
[email protected]
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
9
is a member of Interpol, Ukraine is a member of Interpol, Germany is a member of Interpol, and the national police forces in each of these countries can reach out to Interpol for assistance in terms of sharing police communications and information across a global police information network. There are a number of criminal databases that Interpol can offer to police forces around the world -- everything from DNA to fingerprints, photographs, etc. Interpol also provides proactive support for police operations around the world. A very typical scenario under which Interpol would become involved in an international criminal investigation would be if somebody committed a murder in one country and fled to another country. Interpol would help coordinate the investigation between, for example, France and Germany or France and El Salvador, or among multiple jurisdictions. Let me give you a little bit of history. Interpol was officially created in 1923 in Vienna and in 1946 its headquarters was moved to Paris. As for the name Interpol itself, it is an abbreviation for the International Criminal Police Organization, and the shortened name was taken from the original telegraphic address used to communicate with the organization. Thus long before we had SMS, text messages, SKYPE and Virtual Worlds, in simpler times people used to send telegrams -- and the telegram address for the International Criminal Police Organization was Interpol. Over the years, I have had the pleasure of working with Interpol, in a variety of capacities, on the issues of cyber crime and cyber terrorism. In many regards, Interpol is the perfect organization to help address some of these issues because cyber crime, by its very nature, is a transnational crime. In the not too distant past, transnational crime was quite rare. For example, if somebody in Sofia, Bulgaria walked into a bank and robed the institution, the thief would usually travel back to his home somewhere in Bulgaria after the crime. The investigation of this matter was rather routine and, without dispute, it would be handled by Bulgarian police officials. The victim was in Sofia, the perpetrator was in Sofia, the evidence was in Sofia, it was very easy to investigate. With the advent of ocean liners, railroads, airplanes and now, of course, the Internet it is extremely easy to cross international borders. The Internet by its very nature is international. If one were to send an email from Eilat to Jerusalem, it could still pass through several international computer services, possibly hosted on a server in London or in Tokyo. Thus even if one were to communicate solely within a single country, there still could, quite possibly, be an international dimension to every Internet investigation. For law enforcement agencies around the world this represents a complete paradigm shift in their own modus operandi. Traditionally law enforcement organizations have derived their power from the state, and states are by their nature national level institutions. So, how do we, as representatives of states around the world, adapt to this new global transnational threat which is not clearly defined in any one single state? How can government authorities responsibly conduct investigations around the world in jurisdictions where they lack any actual authority to do so? The answer requires significant transnational cooperation among states and because Interpol is the world’s only true international organization established to deal with global crime issues, Interpol has a key role to play in global matters of cyber crime and terrorism. What has Interpol been doing to combat cyber crime and terrorism? Quite a bit actually. Dating back to 1989, Interpol assembled a group of cyber crime experts within the European Union to study and respond to the issue of trans-border cyber crime. Thus in 1990, Interpol formed its first Working Party on Information Technology Crime. In those early days Interpol brought together cyber crime experts from Scotland Yard, the French National Police and from the German Bundeskriminalamt to meet and
10
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
share experiences and training in the fight against cyber offenses. These officials had a traditional police background and training, but also brought deep technical knowledge to the table. Since 1990, Interpol has grown its regional working party efforts substantially and currently has working groups not just in Europe, but also in Asia, Africa, the Middle East and in the Americas. Each of these groups shares criminal information on the latest cyber tools and trends. In addition, the European Working Party has established a widely respected international computer crime investigation manual, which is available to investigators around the world to help build their capacity to respond to international cyber crime incidents. One of the ways that Interpol facilitates communication among high-tech crime investigators is via its National Central Reference Points (NCRP) program. This network of cyber crime experts augments the traditional Interpol I-24/7 network as a means of sharing emerging cyber threat and crime information in near real time. In effect, it is a closed list of global law enforcement experts working on cyber crime and security matters around the world who are available on a 24/7 basis to assist their colleagues in other countries on urgent cyber crime matters.
2. Cyber Crime As many of you know, cyber crimes differ greatly from traditional crimes, where the evidence may last much longer. For example, with a homicide there is a body on the ground, somebody has been killed, the body is not going anywhere: it will stay right there until moved by somebody else or until the police arrive. Evidence in the cyber world is much more transient. Server log data can disappear very quickly, assuming such data is even kept in the first place. Thus, police and law enforcement must investigate cyber offenses much more rapidly and across greater distances than they have done with traditional crimes in the past. For example, in the kidnapping of Daniel Pearl, the Wall Street Journal reporter, much of the original evidence in the case began to emerge first on the Internet, a non-traditional crime scene for law enforcement. The Interpol NCRP network is meant to help in the case of an emergent crime such as the pursuit of kidnappers across the globe in real-time. In fact we must ask the question: how ‘new’ is cyber crime really? Today we frequently hear police executives referring to cyber crime as a new phenomenon. But is it really? For at least twenty years now many police services have been dealing with a large number of traditional crimes that have migrated to the Internet. For example, frauds that previously existed in “real space” such as West African financial frauds (419 schemes) have merely migrated online. Sexual exploitation of minors sadly had existed in “real space” for a very very long time, but now predators have leveraged the Internet to take advantage of unsuspecting victims around the world. Interpol has responded through the establishment of several professional databases to deal with the severe problem of child pornography and exploitation. But just about any crime that occurs in “real space” can occur in cyber space, including prostitution, theft of intellectual property and even sales of narcotics. There are also some crimes that law enforcement has never seen before in “real space” and which can only exist due to the nature of the Internet itself. Distributed denial of service (DDOS) attacks for example, had no equivalent in the real world. DDOS attacks committed via BOTNET armies controlled by organized criminal groups represent a completely new phenomenon for law enforcement officials. Interpol has a
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
11
number of project groups underway studying these issues in depth, bringing together some of the best experts in the world from both the private and public sectors to tackle these problems.
3. Cyber Terrorism And now to the theme of this conference: cyber terrorism. What’s cyber terrorism? This is not such an easy question to answer. Before we can define cyber terrorism, we must have a firm understanding of what is terrorism itself. So what is terrorism? It depends on whom you ask. There are approximately 100 different definitions of what terrorism is, and while many of these definitions have elements in common, none is universal. The United Nations has a definition, Interpol has a definition, several national level police forces have their own definitions, political organizations, academic organizations, everyone has their own definition of terrorism and no single definition reigns supreme. Thus when one adds a widely misunderstood prefix to the mix (the word cyber), things become even more complicated. If there is no universal agreement on the definition of terrorism, then there certainly is no fundamental accord today that delineates “cyber terrorism.” Thus in defining cyber terrorism, we end up with a definition that draws upon confusion from both the cyber and terrorist worlds. For most people, cyber terrorism may refer to the activities of radical terrorist organizations on the Internet. The other common view of cyber terrorism relates to the use of computer networks to attack the critical information infrastructures of a nation state. 3.1. Use of the Internet by Radical Organizations I will focus on the general definition first: use of the Internet by radical organizations for the purposes of terror. The activities of these groups broadly break down into two categories: support activities and operational activities. 3.1.1. Support Activities Terrorist support activities on the Internet includes disseminating terrorist goals via propaganda in support of radicalization of thought, such as encouraging others to believe that violence is the answer for a particular political problem. Many recognized terrorist organizations have well-organized and funded propaganda machines, news services, video feeds and radio stations on the Internet. Another example of a “cyber terrorist” support activity is the emerging trend occurring in the gaming world vis-à-vis radicalization of thought. There is extensive evidence that cyber jihadists are using stolen computer source code and modifying it to create computer games whose aim is to kill an Israeli soldier, to kill George Bush, to kill Tony Blair or to kill King Abdullah II of Jordan. Those types of games certainly exist and are freely and widely circulated in cyber space as a means of spreading a particular violent and cyber jihadist point of view. There are also radical terrorist organizations that have crafted cyber jihadist messages geared specifically at children, the goal of which is radicalization at an early age to bring new members into the fold for the terrorist group. For example, were one to visit a number of terrorist websites, (and organizations such as MEMRI have carefully cataloged such sites), you will see
12
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
cartoon messages specially tailored for children. These cartoons look like other cartoon images well known to young people, such as Disney™ characters. The major difference is that the messages put forth by these characters is one of hate and violence rather than youthful diversion. Fundraising is another major terrorist support activity that takes place over the Internet. Many terrorist organizations try to raise money over the Internet either via traditional means, where people can send in cash or give money to a local terrorist organization or via virtual means, using new forms of money such as E-Gold, etc. One of our speakers the first day talked about the concept of a town common. It used to be very difficult in the past to find another terrorist depending on where you lived and what your neighborhood looked like. Now, it’s very easy for people with unique ideas and beliefs to “gather” and to find one another. Previously if two disturbed individuals lived on different sides of the city, it would have been difficult for them to find each other and to share a terrorist agenda. Now, with so many chat rooms, blogs, websites etc., it is very easy for individuals to find these groups. As a result, these would-be terrorists meet in the commons and share uncommon beliefs to reinforce each other’s radical mindset and agenda. We have seen a similar radicalization of thought on the criminal side with regard to child pornography and sexual exploitation of children on the Internet. The idea of sleeping with an 8 year old boy or girl is repugnant to most adults; most people find this very very offensive and would never consider it. Thus for obvious reasons, in the past child pornographers have had a hard time meeting each other. Now, via the Internet, and this new concept of a common, they can come together and convince each other that it’s perfectly normal to sleep with a child. The same modus operandi and mindset is also found in the radicalized common space inhabited by terrorist organizations. 3.1.2. Operational Activities The next category of terrorist activity that takes place on the Internet may be described as “operational activities.” There are vast resources online, such as training manuals that can help any person complete a self-paced study program to become a terrorist. There is a document called the Encyclopedia of Jihad which is widely available online. It has many thousands of pages and covers everything from how to build an IED, an improvised explosive device, to how to build weapons of mass destruction. Other chapters cover topics such as how to engage in secret communications and how to avoid detection by the police. Of course the Internet facilitates operational terrorist activities through its communications capabilities, allowing for command-and-control in cyber space, whether through peer-to-peer networks, SMS text messaging, or Voice Over Internet Protocol. When one thinks about it, intimidation is one of the major goals of terrorist organizations. The Internet is an outstanding operational venue for terrorists to intimidate and terrorize the public. We have seen examples of this, such as the beheading video of Nicholas Berg. What was the ultimate effect of that very graphic and violent portrayal? It was to intimidate and to cause terror. And so jihadists are carrying out their terrorist goals via an alternative method, via cyber space. Another major category of terrorist operational activity that can be carried out online is research and planning for an eventual terror attack. Terrorists can use the Internet to research their targets, whether it be using satellite imagery or just Google™ to obtain open-source information to identify, select and prepare to attack a particular
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
13
target. A current and highly publicized example of this was the recently broken-up terrorist plot to attack JFK Airport in New York City. In that case, the FBI in the United States uncovered a plot where a small homegrown terrorist cell, with links to Guyana, planned to attack a very large pipeline that provided jet fuel to JFK Airport. The pipeline was over 40 kilometers in length and terrorists planned to blow up the pipeline using homemade explosives. The group’s planning efforts were also enhanced by the participation in the plot of an insider who previously worked at the airport and became a convert to radical Islam. Law enforcement officials discovered, upon arresting the cell members, that the terrorists had extensively used Google Earth™ to help map out the entire airport as well as the pipeline. Thus, more and more, we are seeing commonly available computer tools serving the operational planning requirements for terrorist plots. 3.1.3. Attacks Against Critical Infrastructure Up until this point, we have focused on terrorists using the Internet to facilitate or support operations. Another common definition of “cyber terrorism” refers to attacks against critical information infrastructures. That is, using computers, computer networks, and the Internet to attack those systems that we rely upon in our daily lives. These systems include transportation, government communications and banking/financial institutions. If you think about it, almost all modern services in one way or another involve a computer. So when one visits the ATM (automatic teller machine), the reason one is able to take money from the machine is because there is a computer and a telephone network line behind the machine that decides it is OK to give you money. The reason police, fire and ambulance personnel can come to your house in the case of an emergency is because they have a dispatch system that knows how to get to where you are. The reason we can see each other in this windowless room is because there is electricity that is controlled via computer by a power grid. Each one of these systems represents a critical infrastructure upon which we depend in our daily lives. Some countries have much better access to these infrastructures than others, and in fact, for those reasons, the most developed countries are at greatest risk for attacks against their critical infrastructure. While many people often predict so-called “electronic Pearl Harbors,” there is disagreement as to whether such a threat is fact or fantasy. In order to better understand the potential threat of a critical infrastructure attack, I will provide three examples to give an overview of the problem. One of the earliest known critical infrastructure attacks occurred in Queensland Australia where a former employee of a water sewage treatment plant hacked into the system of his old company and, through his remote computer control, was able to release raw sewage into a neighborhood. Over 260,000 gallons of raw sewage poured into the streets of this particular town in Queensland. People had to be evacuated, the grounds of an internationally known chain-hotel was covered in raw sewage and lots of wildlife in this wetlands area died as a result. All of this damage was unleashed via a remote computer attack against the information infrastructure of a utility provider. Another famous example from the late 1990’s is Gazprom. Gazprom, as you know, is one of the largest oil/pipeline companies in the world. Hackers were able to access their control systems and at one point, Gazprom was no longer in control of their own pipes, valves and pressure gauges. Instead, each of these was now under remote control via computer hackers. A third example of this type of critical infrastructure attack comes from the United States and involved a disruption to the aviation system at a local
14
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
airport. A small airport in Worcester Massachusetts had its telephone and computer systems taken over by a hacker. By extension, the people in the FAA control tower, the air traffic controllers were no longer able to make outbound phone calls. If there would have been a plane crash officials could not have called an ambulance, nor fire or police services. Because this attack involved a small airport, the runway lights were also controlled via the same phone lines and also were affected by the attack. Each of the above scenarios are stark examples of how one could attack the critical infrastructure of a nation via a cyber attack. 3.2. Terrorist Organizations as Learning Organizations As we know, terrorist organizations are learning organizations. We see evidence of this all over the world. We see it very clearly now in Iraq. The people who are attacking the various coalition troops in Iraq are refining their methodology or modus operandi so that every day they are getting smarter and better. They observe the techniques used by coalition forces to protect themselves and adjust their attacks to counter security measures. One of the things we know that terrorist organizations have learned all too well is how to use our own systems and infrastructure against us. In the first attack against the World Trade Center in New York in 1993 terrorists smuggled a truck bomb into the basement parking lot of the building. The 1,500-lb (680 kg) urea nitrate-fuel oil device was intended to knock down the North Tower and kill thousands. Instead, only six people were murdered and over 1,000 injured—not quite the spectacular event the terrorists had hoped for. In the second attack against the towers in 2001, rather than trying to move a 10,000 kilo bomb into the building, the terrorists adapted and instead chose an airplane full of jet fuel as the bomb/projectile and achieved the desired effect. Thus terrorists took advantage of infrastructure that already existed (an airplane) and weaponized it. There are many other examples of terrorists attacking existing infrastructures, including the bombing of the Atocha train station in Madrid on March 11, 2004 and the London Tube bombings on July 7, 2005. Transportation systems are not the only infrastructures which can be subverted for terrorist use. Back in 2001, in the United States the mail system ground to a halt as the result of a series of Anthrax contaminated letters which were sent through the public mail creating widespread panic and fear. Given all the attacks against various other infrastructures, why is it not too farfetched to presume terrorists might attack critical information infrastructures next. While many downplay the significance of “cyber terrorism” (meaning terrorist attacks against computer networks), the threat is indeed real and one that has been discussed frequently in one Jihadist chat room in the past. Since we already know that terrorists can use the transportation system and the mail system, why would they not turn the computer systems against us next and use them? One of our previous speakers, an Israeli general noted that terrorist organizations had at least one Achilles heel: the need for somebody to actually move the explosives to the detonation site thus providing an opportunity to law enforcement for interception (such as observing a terrorist wearing a suicide belt). I am less optimistic about the Achilles heel theory than is the general. I think he had a very good point but it is no longer necessary to actually move explosives in a whole new genre of attack scenarios. We just saw in early 2007, the JFK Airport pipeline attack plot which was interrupted by authorities. In that attack a small amount of explosives could have been used to detonate the 40 kilometer jet fuel pipeline
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
15
causing extensive damage to JFK Airport and the surrounding neighborhoods. But, in fact, that entire pipeline was controlled by a variety of computer systems. Thus terrorists also could have theoretically compromised the safety features in the computer system and caused the explosion anyway as the pressure grew too high in the pipeline. Thus, I am not sure that it is as necessary today to move large amounts of explosives in order to do extensive damage. The explosives or the chemicals or the fertilizer—all of these things are around us everywhere, and on many occasions are controlled by computer. Thus I remain concerned about terrorist organizations compromising an information system to cause a spectacular infrastructure attack in the future—a form of “cyber terrorism,” if you will.
4. Relationship Between Crime and Terrorism Among law enforcement and justice officials around the world, there has been somewhat of a debate as to the relationship between crime and terrorism. There are some who feel quite strongly that terrorism is a form of crime that must be investigated and prosecuted like all other forms of criminality. There are others, however, who focus on the special nature of terrorism and define it as a problem for armies and intelligence agencies—for a “global war against terrorism.” In my mind, however, the distinction is not so clear and there is often overlap between the two. There have been many incidents of terrorist groups engaging in traditional criminal activities and other instances in which organized crime groups have committed terrorist acts. In South America, for example, the Fuerzas Armadas Revolucionarias de Colombia (FARC) have engaged in narcotics trafficking, and they pose a terrorist security threat to the people of Colombia. Evidence has now revealed that the Al Qaida affiliated terror cells in Spain responsible for the March 11th plot, were using stolen credit cards to help finance their operational expenses. And we know now that organized crime groups are selling their services to people all over the world, selling their expertise to the highest bidders—whether global pedophile rings or terrorists. Today organized crime groups sell so-called BOTNET armies which can be used to target computer networks around the world. While Interpol is actively engaged on the wide gamut of activities discussed previously, it is important to note that Interpol is not alone in this fight. Obviously, NATO through their sponsorship of this important forum is heavily engaged in some of these questions. So are other institutions such as the United Nations, the Council of Europe, the European Union, ASEAN, APEC and many many others. Many of these efforts are growing, however, there is always more to be done. Earlier Professor Golubev mentioned the Council of Europe Treaty on Cyber Crime. Forty-two countries have signed the treaty, though a much smaller number have actually ratified the document to date. It is good news, in the global fight against cyber crime, that so many countries have agreed to common standards and protocols on this important emerging criminal trend. Unfortunately with over 180 countries in the United Nations, there is still much work to be done. Until every country has some method of dealing with cyber crime and cyber terrorism, we are all in danger. Just as money laundering proliferated in so called financial havens, in the Caribbean and elsewhere, so too we may suffer because of so-called “cyber-havens” from which criminals and terrorist may launch their attacks. If a particular country does not protect its slice of cyber space from criminal activity, then all the criminals will frequent those jurisdictions.
16
M. Goodman / Understanding International “Cyberterrorism”: A Law Enforcement Perspective
5. Conclusion So, in conclusion, where are we today vis-à-vis cyber terrorism? It depends on whom you ask. Some activists and pundits argue that the cyber world is close to an eventual and inevitable destruction. These people often talk about an “electronic Pearl Harbor,” in reference to the 1940’s attack on the U.S. port in Hawaii. They believe that there will be an imminent electronic attack that will lead to the crashing of the entire Internet with modern man possibly returning to the Stone Age. Though I exaggerate for emphasis, some people do believe in that vision for the future. Others, including many traditionalists in law enforcement and counter-terrorism, remain unconvinced by the socalled cyber threat. They think it is “no big deal” to-date. In their point of view, “somebody has to move the explosives anyway and therefore why do we have to worry about computers.” Maybe we do and maybe we don’t. In my opinion, the truth lies somewhere in between, and elements of both sides of the camp are correct. I personally believe that while total cyber destruction may be science fiction at this point, some critical infrastructure attack involving cyber space is more than likely over the next ten years. Of course, that is in the realm of an infrastructure attack. As we already know from so much of our own experience and the many experienced speakers at this forum, on the perspective of terrorist use of the Internet—cyber-jihad has certainly arrived and is flourishing. I do believe strongly in cooperation and think that only through collaboration will we have any chance in gaining the upper-hand on either issue. Based upon my discussions with many of the attendees at this forum, I remain convinced that law enforcement cannot win this fight alone. It is evident to me that there is much that academia and industry have to contribute to this discussion. There is an overwhelmingly compelling argument for cooperation against these threats. There are so many interesting tools being developed by academia and the technology industry— law enforcement simply cannot do it alone. We need to work as a team and so for those of you that have interesting ideas that may help support our efforts, please introduce yourselves as I would enjoy the opportunity to share ideas with you. It has been my pleasure to address you today and I thank you all for your kind attention.
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
17
Global Threats – Local Challenges Current Issues of Intelligence Tasking and Coordination in the Rapidly Changing Threat Environment Janusz LUKS 1 Grupa GROM, Warsaw, Poland
Abstract. The nature of threats to international and national security is changing at a rapid pace, forcing a series of fundamental changes in intelligence management and tasking methods and processes. These are clearly visible in counterterrorism operations, particularly in the intelligence collection against terrorist targets in the Internet environment. The need for the development of new analytical capabilities and tools requires a new level of cooperation and dialogue between the intelligence community and research organizations, both at the national and international level. NATO can aid and foster international intelligence cooperation through the requirements definition by NC3A, which will help address some of the compatibility and tools availability issues the intelligence services currently face while developing joint response to the terrorist threat. Keywords. Intelligence management, intelligence tasking, terrorism, Internet
The intelligence cycle environment in the XXI century has changed quite significantly. Tasking, collection and analysis of any national intelligence organization, regardless of its size, must now face the challenges of globalization of national economies, policies and national security threats. Local conflicts, even in remote areas, often tend, nowadays, to have an impact on the national security of countries thousands of miles away. For many countries intelligence support to military operations for their forces has also gone global. In contemporary intelligence there is also a significant asymmetry of threats and targets. Threats, instead of being large, static and highly organized became smaller and less defined, highly mobile and often cloaked, as well as amorphous. Information technology has entered the arena, this time as a weapon, difficult to control and universally proliferated. We now witness electronic warfare, look for and identify cyber 1
Corresponding Author: Janusz Luks, Ul. Granitowa 3/6, 02-681 Warszawa, Tel: +48 606 802999; Email:
[email protected]
18
J. Luks / Intelligence Tasking and Coordination in the Rapidly Changing Threat Environment
threats, take up defense postures in cyberspace and police it very much as we would our physical environment. In the world of dual use technology development, with commercial-off-the-shelf (COTS) products and solutions and ambiguous delivery platforms it is getting harder to decide what is potentially a threat, or a possible weapon of today and what will be a weapon of tomorrow. Rapid development of the Internet and Web resources has brought about a steady erosion of governments’ monopoly on access to potentially sensitive information coupled with the proliferation of effective collection tools and techniques. In parallel, both industry and governments already suffer from information overload and “white noise” and are constantly trying to resolve emerging difficult privacy issues, so important in democratic societies. As the communication revolution continues at great speed, stretching the available collection and monitoring resources almost to their limits, versatile, easily accessible Internet services (data, P2P, IRC, VoIP, Webcam), mobile and satellite communication networks, the proliferation of high level encryption techniques (voice, data, digitally enhanced steganography), user ID cloaking, all present intelligence services with new functional and technological challenges. The changing nature of the threat has resulted in the introduction of new categories in national security priorities, such as: x x x
National critical infrastructure protection; Return to a homeland defense concept, with profound impacts on both the composition and functionality of the intelligence community; Forging global and regional alliances against terrorism and the proliferation of weapons of mass destruction and narcotrafficking, in order to benefit from the international cooperative environment for the exchange of intelligence.
Intelligence customers have also made significant changes in the way their requirements (tasking) are carried out. The speed of intelligence response to tasking has gone up and more often has to conform to the concept of the information reaching the decision maker “just in time”. Intelligence services are asked to collect against a very broad range of targets and to provide all-source-analysis (ASA) at the top level. It is important that the threat analysis be able to differentiate between a criminal and a terrorist threat. One should note a growing need for intelligence (or intelligence-type) information in industry, where vetting of major decisions (e.g., investment) has become a lasting component of the risk management process. Moreover, the private sector has growing intelligence resources, often directly related to national and/or transnational security issues. It is also in industry that a new understanding of the value of intelligence takes root, faster than in governments: information costs money and takes time; intelligence makes money and buys time. The implications of the above discussed changes for the intelligence cycle and process are multiple: x
On the functional side there is a growing need to expand the presence of a “new breed” of intelligence analysts in the intelligence community. They
J. Luks / Intelligence Tasking and Coordination in the Rapidly Changing Threat Environment
x
19
should posses the set of skills which seem to be of crucial importance in the contemporary intelligence environment: o good understanding of source balance and ASA processes; o ability to deliver value-added information from analysis; o understanding of the new tools and technologies, especially in the IT area; o ability to work, interact and communicate with science and technology experts in order to understand advantages and limitations of available collection techniques. On the management side there should be an understanding that processing of intelligence is becoming a core competency. Both global coverage and counterintelligence issues matter more nowadays, as do non-traditional threats. Decision support remains the raison d’être for the decision maker, but new value for him comes from a combination of content + context + speed.
One of the major problems that remains is the failure to share information. “Out there”, especially in the national governments’ world, it is still a stove-pipe environment. We all seem to understand the benefits of all-source analysis, but it is still a challenge for many governments to provide effective mechanisms to fuse, process and analyze information collected from multiple, non-traditional and diversified sources. Tracking terrorists on the Web, in the words of U.S. security expert Bruce Schneier, has all the qualities of a needle in a haystack dilemma. Schneier asks a pointed question: “Are we going to get better results by simply adding more hay to sift through?” The answer is obvious, so we had better start looking for a better pitch-fork and, preferably, X-ray vision. The issues and challenges discussed above call, among other things, for a more extensive R&D contribution to intelligence collection and analysis. One of the possible ways appears to be a focused R&D program under the auspices of NC3A (NATO Communications, Command and Control Agency). NC3A has a good record of supporting the research and development of new IT tools and systems, both for NATO and member countries’ use, through the BOA (Basic Ordering Agreement) mechanism, as well as promoting and certifying standardized solutions. The NC3A Agency is also well versed in coming up with excellent quality international tenders with clearly stated functional requirements for desired technical/technological solutions. Finally, it has the funds to do such jobs in the interest of and on behalf of member countries.
20
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
Cybercrime and Cyberterrorism as a New Security Threat Vladimir GOLUBEV 1 Computer Crime Research Center, Zaporozhye, Ukraine
Abstract. As with many other new technologies in the past, the World Wide Web presents us with great opportunities for progress as well as potentials for misuse. A list of only a few of such crimes committed on the Internet are: network attacks, credit card fraud, stealing money from bank accounts, corporate espionage, and child pornography distribution. These crimes represent a significant social danger to Ukraine and other CIS Confederation of Independent States countries. Below I discuss three different countries and the ways in which they have managed their technology infrastructure and dealt with Internet crime.
Keywords. Internet crime, Cyber crime, Cyber terrorism, CIS countries, Network, Attacks, Information, Security
Introduction As with many other new technologies in the past, the World Wide Web presents us with great opportunities for progress as well as potential for misuse. Here are only a few of the crimes committed on the Internet: network attacks, credit card fraud, stealing money from bank accounts, corporate espionage, child pornography distribution. These crimes represent a significant social danger to Ukraine and other CIS Confederation of Independent States countries. Below I discuss three different countries and the ways in which they have managed their technology infrastructure and dealt with Internet crime.
1
Corresponding Author: Vladimir Golubev, Computer Crime Research Center, Box 8010, Zaporozhye 95, Ukraine, 69095. Telephone: +38 (0612) 341470; Email:
[email protected]
V. Golubev / Cybercrime and Cyberterrorism as a New Security Threat
21
1. The Republic of Moldova In Moldova, the number of Internet users grows each day. Out of a total of 100,000 Internet users 20,000 are government officials. In 2006-2007 all attempted computer attacks and infringement of information systems were successfully neutralized and did not cause any significant problems with the normal operation of state information systems and websites. Maintaining the security of the telecommunication system entails a number of technical measures and methods. These methods are employed by the Center of Special Telecommunications. One of the main factors of reliable, stable and safe functioning of the state information structure is having a special, modern and protected environment. In 2005, the Center of Special Telecommunications began to develop a modern and protected telecommunication system for their government agencies. Today this system has more than 30 kilometers of information fiber-optic network systems that link more than 60 state agencies, including the Office of the President, the Parliament, the Ministries of Commerce and Economy, the Ministry of Finance, the Ministry of Internal Affairs, Ministry of Defense, the General Prosecutor’s Office, the Information and Security Service, Border and Customs Offices, the Center for Fighting Economic Crimes and Corruption and other state offices. State agencies can already exchange information through high-speed, wide-band, encrypted channels. The central information center of the telecommunication system of state agencies was upgraded. State agencies can use special services like high-speed and protected access to the Internet, protected data exchange, and e-mail services. There is a technical support office for all information services provided in all state agencies. One of the top-priority tasks at present is to develop protected communication systems between state offices in the capital and regional state offices. Taking into account the proliferation of computer criminals, the Center of Special Telecommunications is focused on implementing high-tech solutions in the sphere of information security, including technologies of digital signatures. The digital signature is one of the significant means for providing high level protection of e-documents. Introduction of digital signatures in the republic increased the use of e-documents in the communications of state authorities and public offices; this created a fair basis for implementing the electronic exchange of documents, and increased the efficiency of document flow and administrative work. In fact, only 12% of computer crimes in Moldova become the subject of criminal prosecution. Georgiy Suprunov, sales director of the largest telecommunications company in Moldova, said at the international seminar “Control of Internet Use” held in Chisinau, that computer crime is unfavorable for companies because computer crimes decrease their business rating.
2. Republic of Kazakhstan Representatives of Kazakhstan, at a Euro-Asian forum on information security, stated that about 500,000 hacker attacks each month are attempted on their state information networks. Hackers regularly try to break into the databases of banks and companies to try to steal large sums of money and to try to obtain confidential information. The struggle against cyber crime is hampered because the government and these companies
22
V. Golubev / Cybercrime and Cyberterrorism as a New Security Threat
do not want to reveal information about these attacks. In addition, most hackers attack from abroad. The global use of modern information technologies, by governments and financial institutions all over the world, makes the solution of information security problems a top priority. Besides the direct harm from possible intrusion into systems, information gained through cyber crime may become a serious means for human oppression. For this reason Kazakhstan adopted state programs to maintain information security, maintain state secrets and other necessary means including the highest level of cooperation with the Committee of National Security. It is important to note the need to balance maximum openness of access to information, as mandated by the Constitution of Kazakhstan, with the needs of national security. The sphere of information security also demands rational investment of state financial resources in building modern information system and maintenance of the system’s security. Under the Protocol on Cooperation in the area of fighting computer crimes of CIS countries, a computer crime unit was created within the Committee of National Security. The unit’s primary tasks are to find and prevent crimes related to information resources of state authorities. It is essential to cooperate with European and Western countries in this area. Authorized state agencies are interested in ratifying the EU Convention on Cyber Crime adopted in 2001. This will further cooperation in this area of fighting computer crime and will enable colleagues from all over the world to share their experiences in this arena.
3. Republic of Byelorussia As it is well-known, a favorable environment for any crimes in general, and computer crimes in particular, may be explained by the conjunction of three factors: motivation, opportunity and the absence of capable counteraction. When all three are present, there is impunity for criminals and the opportunity for repeated illegal actions in the area of computer information. Byelorussian law enforcement first encountered cases of computer crime in 1998. Subsequently, law enforcement agencies began to fight cyber criminals using traditional legal rules. However this approach was unsuccessful, as most computer crimes grew out of traditional ones but in new ways. The New Criminal Code of the Republic of Byelorussia enacted in 2001 contains a number of articles permitting prosecution for crimes against property (article 212 of the CC) and information security (articles 349-355 of the CC), committed using computer technologies. Among newly introduced crimes are the following six: Article 349, Unauthorized access to computer information; Article 350, Modification of computer information; Article 351, Computer sabotage; Article 352, Unauthorized capture of computer information; Article 353, Production or marketing of special means designed to obtain unauthorized access to computer systems or networks; Article 354, Development, use or spreading of detrimental computer programs; Article 355, Violation of computer system or network operating rules. Taking into account the reality of the potential threat of the misuse of information technologies, the Ministry of Internal Affairs gradually realized that a complex program of counteraction to these crimes was needed; this program was created in 2001.
V. Golubev / Cybercrime and Cyberterrorism as a New Security Threat
23
Special units were created in the ministry specifically to fight high-tech crimes. Today cyber crime problems are solved by the high-tech crime unit at the ministry and its regional departments. The state program for implementing information technology infrastructure of the Republic of Belarus for 2003-2005, (forecasted to 2010), "Electronic Belarus" was developed to carry out the instructions of the President of Belarus from May 27, 2002, ʋ 09/540-20 by a group of specialists from different organizations and organizations of the republic. This endeavor is under the control of the National Academy of Sciences of the Republic of Belarus and is mandated to remove registered negative moments and factors. The program has inter-agency collaboration and is based on the basic regulations of the state policy in the area of information technology. According to Vladislav Kaluqa, the Chief Executive of "Beltelekom" the number of Internet users in Byelorussia is over 2 million now. According to statistical information from 2003, the number of Internet users in the country was more than 1 million. Every day thousands of Byelorussians connect to global networks. Between 1998 and 2001 most cyber crimes were related to stealing goods in emarkets using stolen credit cards, and these crimes were committed by single criminals. Now, crimes are more often related to hacking, with the goal of stealing information; hacker attacks on the web resources of schools, universities, ISPs (Internet Service Providers), mass media, companies and citizens, in order to obtain restricted information or to disrupt an organization’s normal operations. Almost everywhere, repeated crimes committed with the use of computers and stolen credit card information, unauthorized access to computer information, alteration of computer information, computer sabotage, and the distribution of slander on public persons and officials, occurs on the Internet. Criminals actively use technologies to gain maximum profit from illegal financial operations. An increase in Internet use and higher levels of education contributed to a rise in cyber crime in Belarus last year. Belarusian computer criminals caused about $400,000 in damages to foreign institutions last year, mostly banks, cyber crime investigators reported. Hackers targeted only a few domestic banks. The country's High Technology Crimes Investigation Department started 429 legal proceedings against hackers and the FBI (U.S. Federal Bureau of Investigations) visited the country twice to get information for its own investigations. As the number of Belarusians attending university rises, so does the number of cyber criminals. Officials at the Ministry of Internal Affairs estimate 80% of the 189 hackers known in the country are students. In 2006 almost 2000 crimes involving computers, software and the Internet occurred in the country and 175 criminal cases were prosecuted involving illegal actions in the area of information security; in 2005 the number of cases prosecuted was 178. In August, last year, the Belarusian Internet community was stressed by a number of hacker attacks. Anonymous hackers altered hundreds of Belarusian websites. An analysis of the crimes committed in the “digital” sphere shows that the majority (55%) of illegal actions were related to computer crimes: criminal infringements in the sphere of computer information and thefts using computers. Most computer crimes in Belarus are committed by persons aged 18-29 years, (60,7%), while 30 years and older represents about one third, (33,3%). Under-aged persons make up 6%. Viewed from another perspective: 11,9% were committed by students, 21,4% by unemployed individuals, 9,5% by women and 3,6% by prisoners (with some overlap among these classes).
24
V. Golubev / Cybercrime and Cyberterrorism as a New Security Threat
According to the Belarusian Ministry of Internal Affairs’ Public Relations Department, illegal access to computer information, illegal modification of computer information, computer sabotage and credit card theft and fraud are the most typical computer crimes in Belarus. In 2005 cooperation of Russian and Belarusian Ministries of Internal Affairs resulted in the uncovering of an international criminal network specializing in computer crimes. In June of 2005 Belarusian police uncovered an international criminal group that stole USD 112,000 from Citibank USA’s clients’ accounts during August through November 2003. In 2003, a criminal group specializing in the online dissemination of child pornography was uncovered in Minsk. The total profit of that group totalled USD 3 million. Currently, the Belarusian Ministry of Internal Affairs participates in the international special operation Innocent Images Task Force. A Ministry of Internal Affairs spokesman stressed that 60% of computer crimes are committed by people from 18 to 29 years, and 8% committed by juvenile delinquents. According to the official data of the Interior Ministry of the Republic of Belarus, trends of computer crimes in Belarus are significant. High-tech crimes in 2002 showed a 80,5% growth as compared to 2001, 924 such crimes occurred in 2002 and 512 crimes occurred in 2001. The experience of counteracting computer crime in Belarus has raised a number of grave questions related to the investigation of computer crimes and the cooperation of law enforcement agencies of different countries. The high-tech crimes unit at the Interior Ministry of the Republic of Belarus, together with the National High-Tech Crimes Unit of Great Britain held a joint operation “Fire wall” in 2004. The operation resulted in finding and arresting international criminal group members. These criminals produced, sold and used forged credit cards. The Interior Ministry of the Republic of Belarus emphasized the significance of combating computer crimes. There was a meeting at the Ministry dedicated to these issues in 2004. Counteracting cyber crime was flagged as a high priority issue; a program of actions including cooperation of all agencies was adopted.
4. Conclusion The agreement on cooperation of CIS countries in fighting cyber crimes, adopted six years ago in Minsk, laid the basis for the strategy and tactics of law enforcement for these countries. This agreement also put in place a mechanism for cooperation to combat high-tech crimes. However, these countries didn’t fulfill their obligations related to joint investigation measures and the creation of special information systems and cooperation in the field of training skilled police officers. CIS countries are at a complicated and critical stage in solving those numerous problems related to the investigation of cyber crimes. Massive Distributed Denial of Service (DDOS) attacks, where hundreds of compromised BOTNET computers, and even networks from several countries, are used to attack websites in other countries; computer worms causing damage to two-thirds of the countries of the world raise for us the fundamental questions related to localization and jurisdiction of these crimes and criminals. Recently, a number of measures were taken in order to develop efficient methods of international collaboration in combating cyber crime at regional and international levels. These methods produced significant results. Cooperation is
V. Golubev / Cybercrime and Cyberterrorism as a New Security Threat
25
necessary in carrying out operations combating the wide range of problems related to computer crimes in order that these efforts will be successful. It is also necessary to develop partnerships between the CIS and all other interested parties. To reiterate, only by cooperation among nations will it be possible to stop the growth of Internet crime.
26
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
The Enemy Within: Where Are the Islamist/Jihadist Websites Hosted, and What Can Be Done About It? Yigal CARMON1 MEMRI, Washington, DC, USA
Abstract. Terrorist organizations and their supporters make extensive use of the Internet for a variety of purposes, including the recruitment, training and indoctrination of jihad fighters and supporters. The overwhelming majority of the Islamist/jihadist websites are hosted by Internet Service Providers (ISPs) based in the West, many of which are unaware of the content of the Islamist/jihadist sites they are hosting. Experience shows that, once informed, most of the ISPs remove these sites from their servers. Therefore, an effective way to fight the phenomenon is to expose the sites via the media. It would be advisable to establish an organization – governmental or non-governmental – which would maintain a database and publish information about Islamist/jihadist sites on a regular basis, and/or provide such information to ISPs upon their request. Keywords. Jihadist websites, ISPs in the U.S., online jihad, Internet jihad
Introduction Extremist Islam makes extensive use of the Internet. [1] One can hardly imagine the growth of radical Islam and its jihadist organizations in recent years without the immense reach, impact and capabilities of the Internet. The threat posed by Islamist websites has recently been demonstrated by three cases: the planned attack on Fort Dix by a group of young men from New Jersey; the planned terrorist attack on JFK Airport, and the attempted car bombings in the UK, all of them in 2007. According to media reports, the terrorists in all three cases were inspired by jihadist websites. There were also two recent court cases in Britain and in Switzerland in which terrorists were convicted of using Internet sites to promote terrorist activities. The National Intelligence Estimate recently published by the U.S. National Intelligence Council stressed the following: "We assess that the spread of radical especially Salafi - Internet sites, increasingly aggressive anti-US rhetoric and actions, and the growing number of radical, self-generating cells in Western countries indicate that the radical and violent segment of the West’s Muslim population is expanding, including in the United States. The arrest and prosecution by U.S. law enforcement of a small number of violent Islamic extremists inside the United States - who are becoming 1
Corresponding Author: Yigal Carmon, MEMRI, P.O. Box 27837, Washington, DC 20038-7837, Phone: (202) 955-9070; Email:
[email protected].
Y. Carmon / The Enemy Within
27
more connected ideologically, virtually, and/or in a physical sense to the global extremist movement - points to the possibility that others may become sufficiently radicalized that they will view the use of violence here as legitimate..." [2]
1. The Goals of the Jihadist Websites The jihadist terrorist organizations utilize the Internet for two main purposes: for operational needs, and for indoctrination and da'wa (propagation of Islam). 1.1. Operational Purposes The terrorists use the Internet in the military training of jihad fighters by circulating military guidebooks on weaponry, battle tactics, explosives manufacture, and other topics. An example is Al Qaeda's online military magazine Mu'askar Al-Battar (The Al-Battar Training Camp), published by the Military Committee of the Mujahideen in the Arabian Peninsula. [3]
Figure 1. Al Qaeda's online military magazine Mu'askar Al-Battar (www.qa3edoon.com). ISP: R & D Technologies LLC; Nevada, USA
Figure 2. Online course on manufacturing explosives (www.w-n-n.com). ISP: SiteGenie LLC; Minnesota, USA
28
Y. Carmon / The Enemy Within
Some websites also carry courses on manufacturing explosives and even guides for making homemade dirty bombs. [4] Another type of online operational activity is the use of hacking techniques to break into Internet sites - what the Islamists term "electronic jihad." As part of this activity, Islamist hackers attack the websites of those whom they consider their enemies with the aim of sabotaging the sites and damaging morale. They also attempt to hack into strategic economic and military networks with the aim of inflicting substantial damage on infrastructures in the West. Many Islamist websites and forums have special sections devoted to the topic of electronic jihad, such as the electronic jihad section in the Abu Al-Bukhari forum.
Figure 3. Electronic jihad section on the Al-Bukhari forum (www.abualbokhary.info). ISP: Everyones Internet; Texas, USA
1.2. Indoctrination and Da'wa Needs The main use of the Internet by Islamist/jihadist organizations is for purposes of indoctrination and da'wa (propagation of Islam). These organizations attach great significance to this Internet activity, as evident from the considerable effort they invest in it. Al Qaeda, for example, has an "information department" and a very active production company, Al-Sahab. Likewise, the Islamic State of Iraq (ISI) - which is an umbrella organization founded by Al Qaeda, incorporating several terrorist groups in Iraq - has an "information ministry" and two media companies, Al-Furqan and Al-Fajr. In addition, there are independent media companies serving the Islamist organizations, such as the Global Islamic Media Front (GIMF), which denies having ties with Al Qaeda but has posted Al Qaeda statements taking responsibility for terrorist acts. The GIMF has also established the Media Jihad Brigade (Katibat Al-Jihad Al-I'lami). [5] The online indoctrination and da'wa activities are regarded by these organizations as an integral part of jihad, and as another front of jihad in addition to its military, economic, and political fronts. In fact, they characterize online media or informational activity as a type of jihad that can be carried out by those who cannot participate in the
Y. Carmon / The Enemy Within
29
fighting on the battlefield. They call this activity "media jihad" (al-jihad al-i'lami) or "da'wa jihad" (al-jihad al-da'awi). [6] The following are some examples of websites that carry out indoctrination and da'wa activities by disseminating communiqués, religious tracts and videos that serve the terrorists' purposes. a) The "World News Network" forum, which posts communiqués by numerous terrorist organizations. The following is a page from the website that includes messages by Al Qaeda’s production company Al-Sahab, by the ISI media company Al-Furqan, and by the Iraqi terrorist organization Ansar Al-Sunna.
Figure 4. The "World News Network" forum (www.w-n-n.net). ISP: SiteGenie LLC; Minnesota, USA
b) The Al-Saha forum, which posts videos produced by Al-Sahab and speeches by Al Qaeda leaders like Ayman Al-Zawahiri.
Figure 5. The Al-Saha forum (www.alsaha.com). ISP: Liquid Web Inc.; Michigan, USA
30
Y. Carmon / The Enemy Within
c) Some Islamist websites have special sections devoted to messages by the jihadist media companies. For example, the Al-Nusra forum, which is affiliated with GIMF, has a special section devoted to GIMF messages.
Figure 6. Page devoted to GIMF messages on Al-Nusra forum (www.alnusra.net). ISP: Select Solutions LLC; Texas, USA
In practice, the two types of online activity conducted by terrorist organizations military activity and informational activity – cannot be separated, since prominent terrorists are actively involved in online media activities. For example, Fares AlZahrani, an Al Qaeda leader who was arrested in August 2004 by the Saudi authorities, used to post on Islamist forums and on Abu Muhammad Al-Maqdisi's website "Minbar Al-Tawhid Wal-Jihad" under the pseudonyms Abu Jandal Al-Azadi and Al-Athari. [7] Another senior Al Qaeda operative, Abd Al-Aziz Al-Anzi, who has likewise participated in clashes with Saudi security forces, was also very active on the Internet. Al-Anzi, known as the "the information minister of Al Qaeda in the Arabian Peninsula," headed the Al Qaeda Media Council, recruited Al Qaeda supporters on Internet forums, and was a supervisor on the Al-Salafiyoon website (www.alsalafyoon.com) under the pseudonym Abd Al-Aziz Al-Bakri. He also wrote regularly for Al Qaeda's online magazine Sawt Al-Jihad (The Voice of Jihad) under various pseudonyms, including Abdallah bin Nasser Al-Rashid, Abd Al-Aziz bin Musharraf Al-Bakri, Sheikh Nasser Al-Najdi, and Nasser Al-Din Al-Najdi. [8]
2. Most Islamist Websites Are Hosted on Servers Based in the West Some of the Arab countries in which Islamic extremists are most active employ highly restrictive supervision measures against individuals and groups involved in online terrorist activity. [9] As a result, Islamist organizations and their supporters prefer to use Internet Service Providers (ISPs) located in the West - and especially in the U.S., which is a key provider of Internet services - and thus exploit Western freedom of speech to spread their message. In many cases, Western ISPs even host websites of organizations that have been officially designated by these very countries as illegal terrorist organizations. It must be stressed, though, that the ISPs themselves are frequently unaware that they are providing services to extremist elements. The following are examples of jihadist websites hosted in the West (along with their URLs and the names of the ISPs that host them), in three main categories: [10]
Y. Carmon / The Enemy Within
• • •
31
Websites officially or unofficially associated with specific terrorist organizations Forums used by terrorist organizations Websites of sheikhs supporting terrorism
2.1. Websites of Terrorist Organizations a) The website of the Iraqi organization Asaeb Al-Iraq, hosted in Texas.
Figure 7. www.iraqiasaeb.org. ISP: Layered Technologies Inc.; Texas, USA
b) The website of the Jaysh Al-Mujahideen organization, hosted in Pennsylvania.
Figure 8. www.nasrunmiallah.net. ISP: Network Operations Center Inc.; Pennsylvania, USA
c) The website of the Palestinian Islamic Jihad organization, hosted in Texas.
32
Y. Carmon / The Enemy Within
Figure 9. www.sarayaalquds.org. ISP: ThePlanet.com Internet Services Inc.; Texas, USA
d) A Pro-Hezbollah website, hosted in Texas.
Figure 10. www.shiaweb.org/hizbulla/index.html. ISP: Everyones Internet; Texas, USA
e) A blog called "Supporters of Jihad in Iraq," hosted in Washington state. The caption at the top of the page says "Kill the Americans everywhere."
Figure 11. www.hussamaldin.jeeran.com. ISP: Electric Lightwave; Washington, USA
Y. Carmon / The Enemy Within
33
2.2. Islamist Forums Currently, forums are the primary platform used by Islamist organizations to spread their message. The importance the organizations attach to these forums is evident in the fact that their official statements, such as communiqués or videos, are usually posted on forums before being posted on their websites. For instance, Al Qaeda, which has no official websites, uses Islamist forums to convey its messages. The following are some examples of forums: a) The highly popular Al-Hesbah forum, hosted in Texas.
Figure 12. www.alhesbah.org. ISP: RealWebHost, Texas, USA
b) The Al-Tajdid forum, hosted in Britain.
Figure 13. www.tajdeed.org.uk. ISP: FASTHOSTS-UK-NETWORK, UK
c) The Al-Saha forum, hosted in the U.S.
34
Y. Carmon / The Enemy Within
Figure 14. www.alsaha.com. ISP: Liquid Web Inc.; Michigan, USA
2.3. Websites of Sheikhs Who Support Terrorism Known Islamist sheikhs play a pivotal role in setting up the terrorist organizations' ideological infrastructure and in granting religious-legal legitimacy to their activities. Many of these religious scholars are currently serving prison sentences for incitement to terrorism or even for active involvement in terrorist activity. However, this does not prevent them from spreading inciting messages and supporting terrorism via their websites, which remain active, and are often hosted in the very same counties that convicted and imprisoned them. For example: a) The website of Abu Qatada Al-Falastini (a.k.a., Omar Mahmoud Abu Omar), a Jordanian of Palestinian origin, who has been detained in Britain since 2005 on suspicion of having ties with Al Qaeda. His site is hosted in Britain.
Figure 15. www.almedad.com/tae. ISP: BT-Wholesale, UK.
Y. Carmon / The Enemy Within
35
b) The website of Sheikh Abu Muhammad Al-Maqdisi, who was the spiritual mentor of the late commander of Al Qaeda in Iraq, Abu Mus'ab Al-Zarqawi. AlMaqdisi's website includes numerous documents that provide ideological and religious legitimacy for Islamist terrorist organizations. [11]
Figure 16. www.tawhed.ws / www.alsunnah.info. ISP: Interserver Inc.; New Jersey, USA
c) The website of extremist Islamist sheikh Hamed Al-Ali, known for supporting jihad fighters.
Figure 17. www.h-alali.net. ISP: FortressITX; New Jersey, USA
2.4. Sites Hosted by the Large Internet Companies Google™, Yahoo!™ and MSN™ The Islamist/jihadist organizations also make use of the free Internet services offered by large Internet companies like Google™, Yahoo!™ and MSN™. The following are examples of jihadist blogs hosted by these companies:
36
Y. Carmon / The Enemy Within
a) The unofficial blog of Al-Furqan (the production company of the Al Qaedafounded ISI), hosted by Google™.
Figure 18. www.gldag.blogspot.com. ISP: Google Inc.; California, USA
b) A blog dedicated to the legacy of the late commander of Al Qaeda in Iraq, Abu Mus'ab Al-Zarqawi. The blog, hosted by Google™, features messages and videos by Al-Zarqawi.
Figure 19. www.kjawd.blogspot.com. ISP: Google Inc.; California, USA
Y. Carmon / The Enemy Within
37
c) A Yahoo!™ group called "Supporters of Jihad in Iraq."
Figure 20. http://groups.yahoo.com/group/ansaraljehad. ISP: Yahoo!; California, USA
d) A pro-Hezbollah group on Microsoft's portal MSN™ which posts speeches by Nasrallah, information on Hezbollah operations and links to other Hezbollah sites.
Figure 21. http://groups.msn.com/Hezbollahh/page16.msnw. ISP: Microsoft Corp.; Washington, USA
2.5. Websites in European Languages: Among the jihadist websites hosted in the West, most are in Arabic, but there are also websites in European languages such as English, French and German, as well as Arabic websites that have sections in other languages. For example:
38
Y. Carmon / The Enemy Within
a) The World News Network forum, hosted in the U.S., has a section in English.
Figure 22. www.w-n-n.net. ISP: SiteGenie LLC; Minnesota, USA
b) GIMF's website in German, hosted in Britain:
Figure 23. http://gimf1.wordpress.com. ISP: Akamai Technologies; London, UK.
c) A website in French called La Voix des Opprimés (The Voice of the Oppressed), hosted in the U.S.
Y. Carmon / The Enemy Within
39
Figure 24. http://news.stcom.net. ISP: DNS Services; Florida, USA
3. What Can Be Done? The prevalent view in the West, even among officials in charge of counterterrorism, is that the primary way to fight the jihadist websites is to spread an alternative message, or a "counter-narrative," which is opposed to that of the Islamists. [12] Though Islamist ideology can and should be countered by alternative messages, and is indeed being increasingly challenged by reformists in the Arab and Muslim world, such an ideological campaign is, by its very nature, a long-term effort that does not produce immediate results. A more effective and immediate way to fight the phenomenon is, firstly, to expose the extremist sites via the media, and thus to inform ISPs and the public at large of their content, and secondly, to bring legal measures against ISPs that continue to host extremist websites and forums. 3.1. Exposure Experience teaches us that exposure is, in itself an effective measure against extremist sites. In 2004, MEMRI published a comprehensive two-part review of Islamist websites and their hosts. [13] Within a week of the document's publication, most of the sites exposed in it were closed down by their ISPs. This suggests that an effective measure against the extremists' online activities would be to establish a database - governmental or non-governmental - which would regularly publish information about Islamist/jihadist sites, and/or provide such information to ISPs upon their request. This database would provide a service similar to that of government bodies which inform the public about various kinds of threats to its safety, such as agencies that provide weather alerts and travel advisories; the Better Business Bureau, which provides businessmen and individuals with information about companies convicted of fraud; or the U.S. Treasury's Office of Foreign Assets Control, which provide information to banks, thereby enabling them to comply with the regulation of "know your customer." [14] It should also be stressed that the ISPs themselves have a legal authority to remove sites that violate the law (e.g., the copyright laws) or sites that abuse their own
40
Y. Carmon / The Enemy Within
regulations or terms of use. Thus, with information on extremist sites at their disposal, the ISPs should have the ability – and the obligation – to remove such sites from their servers. 3.2. Legal Countermeasures The prevailing opinion among the American public - and even among government officials, including those in charge of counterterrorism - is that the First Amendment severely limits the scope of legal measures that can be brought against terrorist websites. But the fact is that American law contains clear and effective provisions against terrorist organizations and their online activities, including the following: 3.2.1. Designated Terrorists and Foreign Terrorist Organizations The U.S. officially designates certain organizations as “Foreign Terrorist Organizations” (FTOs) and certain individuals as "Specially Designated Terrorists" (SDTs) or "Specially Designated Global Terrorists" (SDGTs). The list of designated organizations and individuals is updated regularly and made available to the public. [15] These designations have legal consequences. For example, section 219 of the Immigration and Nationality Act states that it is unlawful to provide a designated FTO with "material support or resources," including "any property, tangible or intangible, or services," including "communication equipment and facilities." [16] Some of the organizations and individuals listed in this document - such as the Islamic Jihad organization, for example - are designated FTOs and SDGTs, which means that the ISPs hosting their sites are violating U.S. law. 3.2.2. 18 U.S.C. Section 842 Another pertinent law is Title 18, Section 842, of the U.S. Code, which states: "It shall be unlawful for any person to teach or demonstrate the making or use of an explosive, a destructive device, or a weapon of mass destruction, or to distribute by any means information pertaining to... the manufacture or use [thereof] with the intent that the teaching, demonstration, or information be used for, or in furtherance of, an activity that constitutes a Federal crime of violence” (see original document listed on http://www.atf.gov/explarson/fedexplolaw/explosiveslaw.pdf). Websites and forums that disseminate operational military information to terrorists, such as many of the sites and forums presented here, are illegal under this law, even if they are not formally associated with a designated FTO. A motion claiming this law to be incompatible with the First Amendment was denied by a U.S. court in the case of Rodney Adam Coronado, a radical animal-rights and environmental activist. Coronado was charged with violating Title 18, Section 842 of the U.S. Code after giving a lecture in California in which he showed how to build an incendiary bomb. After being indicted, Coronado filed a motion to dismiss the case against him on grounds that the law had violated his First Amendment rights. The motion, however, was denied by the District Court of San Diego. In explaining its ruling, the court stated that "the First Amendment does not provide a defense to a criminal charge simply because the actor uses words [rather than actions] to carry out his illegal purpose..."
Y. Carmon / The Enemy Within
41
References [1]
For a general overview of Islamist websites, see MEMRI Inquiry & Analysis No. 328, " Islamist Websites as an Integral Part of jihad: A General Overview," February 21, 2007, http://memri.org/bin/articles.cgi?Page=archives&Area=ia&ID=IA32807. [2] http://www.dni.gov/press_releases/20070717_release.pdf. [3] See MEMRI Special Dispatch No. 637, "The Al-Battar Training Camp: The First Issue of Al-Qa'ida's Online Military Magazine," January 6, 2004, http://memri.org/bin/articles.cgi?Page=archives&Area=sd &ID=SP63704. [4] See MEMRI Special Dispatch No. 1004, "On Islamic Websites: A Guide for Preparing Nuclear Weapons," October 12, 2005, http://memri.org/bin/articles.cgi?Page=archives&Area=sd&ID= SP100405. [5] Al-Sharq Al-Awsat (London), August 14, 2005. [6] See article by Nur Al-Din Al-Kurdi in the third issue of the magazine Dhurwat Sanam Al-Islam, published by the Al Qaeda in Iraq Information Department. [7] Al-Sharq Al-Awsat (London), July 31, 2007. [8] http://www.alarabiya.net/Articles/2005/10/17/17782.htm. [9] Saudi Arabia, for example, passed a bill in March 2007 that stipulates imprisonment of up to 10 years and/or a fine of up to 5 million riyals for anyone setting up a website for a terror organization or a site promoting terrorist goals (Al-Watan, Saudi Arabia, March 27, 2007). There have also been arrests. On June 5, 2007, the Saudi Security services detained three Al Qaeda members for using the Internet to spread extremist ideology and recruit young people to jihad. One of the detainees was Abu Asid AlFaluji, who attempted to recruit youths for terrorist operations and disseminated via the Internet speeches by bin Laden and Abu Mus'ab Al-Zarqawi; another was Abu Adullah Al-Najdi, who was involved in terrorist operations against Saudi Arabia and attempted to publish a new edition of the Al Qaeda in Saudi Arabia e-journal, Sawt Al-Jihad, which was closed down two years ago (Al-Watan, Saudi Arabia, June 6, 2007; Al-Riyadh, Saudi Arabia, June 7, 2007). [10] All data concerning the websites was verified July 15, 2007. [11] See MEMRI Inquiry and Analysis No. 239, "Dispute in Islamist Circles over the Legitimacy of Attacking Muslims, Shiites, and Non-Combatant Non-Muslims in Jihad Operations in Iraq: Al-Maqdisi vs. His Disciple Al-Zarqawi," September 11, 2005, http://memri.org/bin/articles.cgi?Page=archives &Area=ia&ID=IA23905. [12] Measures of this sort were the focus at a May 3, 2007 hearing of the Senate Homeland Security and Governmental Affairs Committee, chaired by Senator Joseph Lieberman, which dealt with "The Internet as a Portal for Islamist Extremists." Among the speakers at this hearing were Lieutenant Colonel Joseph Felter from the United States Army; Deputy Assistant Secretary of Defense Michael Doran; and Frank J. Cilluffo, Director of the Homeland Security Institute at George Washington University. Frank Cilluffo stated that, in order to counter the Islamist threat, the West must "win the battle for hearts and minds... and offer hope... to those who might otherwise be seduced by the jihadi ideology." As examples of activities that achieve this aim, Cilluffo mentioned, among other things, the Indonesian pop-star Ahmad Dhani who "uses his music... to counter calls to violence with a message of peace and tolerance," and an anti-terrorism fatwa issued in 2005 by the Fiqh Council of North America - a pro-Islamist body (Speech delivered at a hearing of the U.S. Senate Homeland Security and Governmental Affairs Committee, May 3, 2007). [13] See MEMRI Special Report No. 31, "Islamist Websites and Their Hosts Part I: Islamist Terror Organizations," July 16, 2004, http://memri.org/bin/articles.cgi?Page=archives&Area=sr&ID=SR3104; MEMRI Special Report No. 35: " Islamist Websites and their Hosts Part II: Clerics," November 11, 2004, http://memri.org/bin/articles.cgi?Page=archives&Area=sr&ID=SR3504. [14] Website of the Office of Foreign Assets Control: http://www.treas.gov/offices/enforcement/ofac/. [15]For an updated list of Specially Designated Nationals, see:http://www.treas.gov/offices/enforcement/ ofac/sdn/t11sdn.pdf. [16] http://www.state.gov/s/ct/rls/fs/37191.htm.
This page intentionally left blank
Part Two Discovering Hidden Patterns of Activity
This page intentionally left blank
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
45
Mining Users’ Web Navigation Patterns and Predicting Their Next Step José BORGES a and Mark LEVENE b,1 a School of Engineering, University of Porto, Portugal b School of Computer Science and Information Systems, Birkbeck, University of London Abstract. Web server logs can be used to build a variable length Markov model representing user’s navigation through a web site. With the aid of such a Markov model we can attempt to predict the user’s next navigation step on a trail that is being followed, using a maximum likelihood method that predicts that the highest probability link will be chosen. We investigate three different scoring metrics for evaluating this prediction method: the hit and miss score, the mean absolute error and the ignorance score. We present an extensive experimental evaluation on three data sets that are split into training and test sets. The results confirm that the quality of prediction increases with the order of the Markov model, and further increases after removing unexpected, i.e. low probability, clicks from the test set. Keywords. Web usage mining, variable length Markov chains, scoring rules
Introduction When users click on a link in a web page, submit a query to a search engine or access a wireless network they leave a trace behind them that is stored in a log file. The information stored in the log file for each user click will include items such as a time-stamp, identification of the user (for example, an IP address, a cookie or a tag), the user’s location, query terms entered and further clickstream data, where appropriate. (We use the term ‘click’ generically to mean a click on a link, a query submission or an access to a network.) The log file thus contains an entry for each click and can be pre-processed into timeordered sessions of sequential clicks. Each session includes a trail that the user followed through the space, which we take without loss of generality to be a web site. A trail can be defined in various ways, for example as a sequence of clicks that has taken no longer than a given time span, or one such that the time between clicks in the sequence is no longer than a given short time span, or as a sequence of link-connected clicks (i.e. clicks that are linked together). In [21] the authors present a study to evaluate heuristics to reconstruct sessions from server log data, known as sessionizing. They show that sessions can be accurately inferred for web sites with embedded session identification mechanisms, that time-based reconstruction heuristics are acceptable when cookie identifiers 1 Corresponding Author: Mark Levene, School of Computer Science and Information Systems, Birkbeck, University of London, Malet Street, London WC1E 7HX, U.K.; E-mail:
[email protected]
46
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
are available and that referrer-based heuristics should be used when cookie identifiers are not available. Logs are thus a valuable source of information for understanding what users are doing and how a site is being used. Here we focus on web usage mining, which concentrates on developing techniques that model and study users’ web navigation data obtained from server log files, with the aim to discover and evaluate “interesting” patterns of behaviour [17]. It is important to note that apart from studying log data recording a user’s clickstream, other information, for example related to the content being browsed, or to the context in which the user is browsing, will be very useful. Several methods have been proposed for modelling web usage data. Schechter et al. [20] utilised a tree-based data structure that represents the collection of paths inferred from the log data to predict the next page access. Dongshan and Junyi [11] proposed a hybrid-order tree-like Markov model, which provides good scalability and high coverage of the state-space, also used to predict the next page access. Chen and Zhang [9] utilised a Prediction by Partial Match forest that restricts the roots to popular nodes; assuming that most user sessions start at popular pages, the branches having a non-popular page as their root are pruned. Deshpande and Karypis [10] proposed a technique that builds k th −order Markov models and combines them to include the highest order model covering each state; a technique to reduce the model complexity is also proposed therein. Moreover, Eirinaki et al. [12] propose a method that incorporates link analysis, such as the PageRank measure, into a Markov model in order to provide web path recommendations. Applications of web usage mining include: creating adaptive web sites that automatically improve their organisation and presentation [18], prefetching web pages to improve latency [9], personalisation of users’ web experience [17], and web access prediction [11,10,6,7]. In [3,4] we have proposed a first-order Markov model for a collection of user navigation sessions, and more recently we have extended the method to represent higherorder conditional probabilities by making use of a cloning operation [7]. In particular, we make use of a Variable Length Markov Chain (VLMC), which is an extension of a Markov chain that allows variable length history to be captured [1]. Our method transforms a first-order model into a VLMC so that each transition probability between two states takes into account the path a user followed to reach the first state prior to choosing the outlink corresponding to the transition to the second state. In addition, we have previously proposed a method to evaluate the predictive power of a model that takes into account a variable length history when estimating the probability of the next link choice of a user, given the user’s navigation trail [6]. Here we concentrate on the prediction problem, i.e. given a trail, we ask how well can we predict the final link the user followed to complete the trail. The algorithm we use for prediction is to choose the highest probability link, given that the user has inspected n web pages before reaching the final link on the trail, where n ≥ 1. In particular, we are interested to know how the prediction is affected by n, the order of the model used for prediction. In addition, we investigate three different scoring metrics for evaluating the prediction algorithm: the hit and miss score (also known as the hit rate) [23], the mean absolute error [23] and the ignorance score (also known as the information score) [19]. We are also interested in assessing unexpected or surprising events [16,13], since such rare events are not predictable. Although not predictable, unexpected clicks can be
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
47
detected by the fact that their probability of occurrence is low. The approach we take is to label a click as unexpected if its probability is less or equal to some threshold. Equivalently we can say that an event is expected if its probability of occurrence is greater than the threshold. We observe that if the threshold is zero then unexpected events are the ones that have not yet occurred in the log data. A significant application for the detection of unexpected events is patrolling the Web for security purposes [8]. Web usage mining can be used in this context to capture and analyse navigation patterns within a web site being monitored. Once an unexpected event is identified then the focus can be directed to tracking the user initiating the unexpected event. We have carried out an extensive experimental evaluation of the prediction algorithm on three substantial data sets with respect to the three scoring metrics. For evaluation purposes we split the data into a training set on which the VLMC model is constructed and a test set on which the prediction algorithm is evaluated. Our results show that prediction improves as the order of the Markov model increases, i.e. when we have a longer user history predicting the user’s next step is more likely. Moreover, the results also suggest that prediction stabilises as the order of the model increases. We also found that when we remove unexpected clicks from the training set up to a threshold of 0.1, the prediction further improves. The rest of the paper is organised as follows: in Section 1 we introduce the variable length Markov chain model we use. In Section 2 we introduce the prediction problem and present three different methods of evaluating the prediction. In Section 3 we discuss the issue of unexpected accesses. In Section 4 we present an experimental evaluation of the prediction algorithm, and, finally, in Section 5 we give our concluding remarks.
1. Web Mining with Variable Length Markov Chains In previous work we have proposed the use of Markov models to represent a collection of user sessions. A first-order Markov model [14] provides a compact way of representing a collection of sessions but, in most cases, its accuracy is low. A VLMC is a Markov model extension that allows variable length navigation history to be captured. We have proposed in [5] a method that transforms a first-order model into a VLMC so that each transition probability between two states takes into account the path a user followed to reach the anchor state. We now briefly review our VLMC construction method. Consider the collection of sessions and the corresponding first-order model given in Figure 1. Each web page corresponds to a state in the model. In addition, there is an artificial start state (S) and an artificial final state (F) appended to every session. The first-order model is incrementally built by processing each sequence of page requests. A transition probability is estimated by the ratio of the number of times the transition was traversed to the number of times the anchor state was visited. Next to a link, the first number gives the number of times the link was traversed and the number in parentheses gives its estimated probability. The model accuracy can be assessed by comparing a transition probability with the corresponding higher-order probability estimated by the n-gram frequency counts. For example, according to the input data the conditional probability of going to state A3 after following link (A1 , A2 ) is given by the number of times users followed (A1 , A2 , A3 )
48
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
divided by the number of times users followed (A1 , A2 ), that is 3/6 = 0.5. The firstorder model is not accurate since p(A2 , A3 ) = 0.38. A1
Session
freq.
A1 , A2 , A3 A1 , A2 , A4 A5 , A2 , A3 A5 , A2 , A4 A6 , A2 , A3 A6 , A2 , A4
3 3 1 4 2 3
S
5 (0.31)
A3
6 (1)
6 (0.38)
A5
5 (1)
5 (0.31)
6 (0.38)
6 (1)
10 (0.62)
10 (1)
A2
F
5 (1)
A4
A6
Figure 1. A collection of user navigation sessions and the corresponding first-order model
Our model extension that incorporates higher-order probabilities is based on a cloning operation that duplicates states whose outlink transition probabilities are not accurate. In Figure 1, for example, state A2 is cloned in order to separate in-paths to it that induce distinct conditional probabilities. In order to identify in-paths inducing similar conditional probabilities a clustering method is used; there is also a parameter used to set the intended accuracy. Figure 2 shows the resulting second-order model when a 5% deviation is allowed between the conditional probability induced by the n-gram counts and the transition probability given by the model. Since paths from A1 and A6 induce closer conditional probabilities, they were assigned to the same clone. The transition counts of the updated model are computed in a way that reflects the number of times each path was followed. Although the example corresponds to a second-order evaluation, the method was generalised for higher-orders; see [5].
A1 6 (0.38)
S
5 (0.31)
5 (0.45)
6 (1)
A3
A2 A6
5 (1)
6 (1)
6 (0.55)
F 10 (1)
1 (0.20)
5 (0.31)
A5
5 (1)
A’2
4 (0.80)
A4
Figure 2. The second order model corresponding to the model given in Figure 1
Modeling a collection of sessions in a VLMC has the advantage of providing a platform to (i) identify the most popular trails, which are defined as the higher probability paths, and (ii) to predict the user’s next navigation step after following a given trail.
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
49
2. Prediction and Scoring Rules Given a trail, the prediction problem is the task of predicting the next link a user followed to complete the trail. That is, by observing the clicks that lead to the last link on the trail, i.e. the clickstream history, the last link is the one to be predicted. The prediction algorithm we use is simply to choose the highest probability link, given that the user has inspected n web pages (states) before reaching the final link on the trail, where n ≥ 1; this prediction method is known as maximum likelihood. In particular, we are interested to know how the prediction is affected by n, the order of the model used for prediction. We investigate three different scoring metrics (see [22]) for evaluating the prediction algorithm. The first method is the hit and miss scoring rule (HM) [23], which counts a correct prediction, i.e. a hit, as 1 and an incorrect prediction, i.e. a miss, as 0. HM can be interpreted as the probability of guessing that the link followed was the one with the maximum probability, and is thus equal to the expected maximum likelihood probability of the last link on the trail; we denote this expected probability by M T P . The second method is the mean absolute error (MAE) [23], which ranks the links from 1 to r, where the rth link was the one that was followed, and records the MAE as r − 1. MAE can be interpreted as the expected rank of the last link on the trail that was followed minus one. So, for example, if on average, the user clicks on the link that was ranked 3rd the MAE will be 2. The third method is the ignorance score (IS) [19], which records the score as − log2 (p), where p is the probability of the link that was, in fact, followed by the user. The ignorance has an information-theoretic interpretation as the entropy of an event [19], and two to the power of IS can be interpreted as the expected probability of the last link on the trail that was followed by the user; we denote this expected probability by AT P . As opposed to HM and MAE, IS is a non-linear scoring function, ranging from zero, when p = 1, to infinity, when p = 0 (when p = 0.5, the IS is equal to 1), i.e. the penalty is large when the user follows a link whose probability of occurrence is very low.
3. Unexpected Events If the user follows a link whose probability of occurrence is very low (or zero when it is followed for the first time), the event may be considered as being unexpected from the point of view of the Markov model. Such unexpected or surprising events [16,13] are not predictable, since they are unlikely to occur according to the constructed VLMC model. Thus, although not predictable, unexpected user clicks can be detected by the fact that their probability of occurrence is low. The approach we take here is to label a click as unexpected if its probability is less than or equal to some threshold, α. Equivalently we can say that an event is expected if its probability of occurrence is greater than the threshold, α. We observe that if the threshold is less than zero, then there are no unexpected events (in the following we use all to denote a value of α which is less than 0). We also observe that when α = 0 then the only unexpected events are the ones whose probability is zero, i.e. representing links that have not yet occurred in the Markov model. When α = all, i.e. α < 0 we apply a form of Laplace smoothing [24] to the model. In particular, for each state, we set the probability, pi , of the ith outlink from the state as
50
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
pi =
wi + d , W + md
(1)
where m is the number of links that can be followed from the state, wi is the number m of times the ith outlink was traversed, W = i=1 wi , and d is an initial small positive weight assigned to each outlink; we determined the value of d = 0.001 used in our experiments by trial and error. We note than when d = 0 Laplace smoothing is turned off.
4. Experimental Evaluation For the experimental evaluation we make use of three distinct data sets. The first data set (LTM) represents four months of usage from the London Transport Museum between November 2002 and February 2003. Erroneous requests, image requests and requests from IP addresses that requested the robots.txt file were eliminated. A session was defined as a sequence of requests from the same IP address with a time limit of 30 minutes between consecutive requests. After sessionizing, sessions with a single request were removed. For testing, we decided to use a temporal based natural split, thus, the training set is the first three months of data and the test set is the last month of data. The second data set (MSWEB) was obtained from the UCI KDD archive (http: //kdd.ics.uci.edu/databases/msweb/msweb.html) and records the areas within www.microsoft.com that users visited in a one-week time frame in February 1998. Two separate data sets are provided, a training set and a test set. The third data set (PKDD) corresponds to the ECML/PKDD 2005 challenge and contains server sessions from seven e-commerce vendors [2]. The data contains a session generated ID, and a session was thus defined as a sequence of requests with the same ID for a given vendor. For testing, we randomly split the data into a 70/30 training set and test set split. Table 1 summarises the characteristics of the data sets. For each data set we indicate the number of pages occurring in the log file, the total number of requests recorded and the total number of sessions derived from each data set. Table 1. Summary characteristics of the three real data sets used Pages LTM PKDD MSWEB
2438 316 285
Trainning set Requests Sessions 792886 456786 98654
31953 60288 32711
Pages
Test Set Requests
Sessions
1974 263 236
338322 188922 15191
13694 25837 5000
We let BF be the model branching factor. For a model having i = 1, 2, . . . , s states and each state i having ui outlinks we define BF as follows: s
BF =
1 ui . s i=1
(2)
Although BF is related to the model complexity it does not give a clear indication of the difficulty associated with predicting a user next navigation step when viewing a
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
51
given state. Thus, we define the weighted branching factor wBF to measure the average number of outlinks weighted by the number of times the anchor s state was visited. We let wi be the number of times state i was visited and W = i=1 wi and define wBF as follows: wBF =
s 1 wi ui . W i=1
(3)
25 weighted branching factor
20 branching factor
300
LTM MSWEB PKDD
15 10 5
LTM MSWEB PKDD
250 200 150 100 50
0 1
2 3 order of the model
4
1
2 3 order of the model
4
Figure 3. Branching factor (left) and Weighted branching factor (right)
In Figure 3 we show how BF and wBF vary with the order of the model. It can be seen that wBF is, on average, larger than BF by a factor of over 10. Although for higher order models BF is, on average, less than 5, states with a higher probability of being visited have a much larger number of outlinks and thus the choice of which link to predict is a non-trivial task.
percentage of trails in the test set
1
0.75
0.5
0.25
LTM MSWEB PKDD
0 all
0
0.01 α
0.05
0.1
Figure 4. Average percentage of expected events in the test data
Figure 4 shows an approximately linear decrease in the percentage of trails in the test sets as α is increased. (We note that although the α values on the x-axis in the figure are not proportionally spaced, when adjusting the data points appropriately linear
52
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
regression shows a good fit for the three data sets.) Overall, LTM and MSWEB have more unexpected events than PKDD, and for α > 0.01 the increase in the number of unexpected events is sharper for MSWEB than for LTM. This could account for the links of MSWEB being less predictable than the other two data sets, as discussed below. We note that increasing α by too much is not desirable, since as seen from the trend in Figure 4, this will have an adverse effect on the size of the test set.
0.75
0.75
HM
1
HM
1
0.5 all > 0.00 > 0.01 > 0.05 > 0.10
0.25
0.5 all > 0.00 > 0.01 > 0.05 > 0.10
0.25
0
0 1
2 3 order of the model
4
1
2 3 order of the model
4
Figure 5. Hit and miss score for LTM (left) and PKDD (right)
1
all > 0.00 > 0.01 > 0.05 > 0.10
0.75
15
all > 0.00 > 0.01 > 0.05 > 0.10
MAE
HM
10 0.5
5 0.25
0
0 1
2 3 order of the model
4
1
2 3 order of the model
4
Figure 6. Hit and miss score for MSWEB (left) and Mean absolute error for LTM (right)
In Figures 5, 6, 7, 8 and 9 (left) we show for the three data sets how the HM score, the MAE and the IS score vary, respectively, with the order of the model for varying values of α. The general pattern for all scoring metrics is that the scores improve as the order of the model increases and as α increases. By increasing the order of the model we are able to make use of the history to limit the choices of clicks that users have made, and by increasing α, until it reaches a predefined level, we are able to eliminate unexpected events which make the prediction more difficult. It can be seen that for HM and IS, the LTM data set performs best, then the PKDD data set and the worst performing data set is MSWEB. For MAE the same holds when α is all or 0, but when α is greater than 0 the
53
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
distinction, although present, is less evident. Thus assuming that α > 0, we can conclude that, on average, the link we are trying to predict is in the top 3 most probable links. For HM we see that when α is greater than 0 we can reach a prediction level above 0.75 for LTM, between 0.5 and 0.75 for PKDD, while for MSWEB only when α = 0.10 can we reach a level above 0.5. (We note that 0.5 is still much better than a uniform guess as, in general, there are more than two links to choose from.) The results for the IS scoring rule show that there are significant differences between the three data sets with respect to the expected probability of the link that we are trying to predict. As we can see for LTM the probability 2−IS is able to reach levels above 0.5 when α ≥ 0.05, for PKDD the probability levels are all below 0.5, while for MSWEB they barely reach 0.25. Thus, although, as seen in Figure 3, the branching factors for the data sets are comparable, the probabilities of the links we are trying to predict are generally lower in MSWEB than in PKDD and lower in PKDD than in LTM. This is reinforced in Figure 9 (right), where it can be seen that the difference between M T P and AT P is larger for MSWEB than for PKDD and larger for PKDD than for LTM.
15
15
all > 0.00 > 0.01 > 0.05 > 0.10
MAE
10
MAE
10
all > 0.00 > 0.01 > 0.05 > 0.10
5
5
0
0 1
2 3 order of the model
4
1
2 3 order of the model
4
Figure 7. Mean absolute error for PKDD (left) and MSWEB (right)
1
0.5
0.5
0.25
0.25
0
0 1
all > 0.00 > 0.01 > 0.05 > 0.10
0.75 1/2IS
0.75 1/2IS
1
all > 0.00 > 0.01 > 0.05 > 0.10
2 3 order of the model
4
1
2 3 order of the model
Figure 8. Ignorance score for LTM (left) and PKDD (right)
4
54
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
1
1 all > 0.00 > 0.01 > 0.05 > 0.10
0.75 trail probability
1/2IS
0.75
0.5
0.25
LTM-MTP LTM-ATP MSWEB-MTP MSWEB-ATP PKDD-MTP PKDD-ATP
0.5
0.25
0
0
1
2 3 order of the model
4
1
2
3
4
order of the model
Figure 9. Ignorance score for MSWEB (left) and Average (AT P ) and maximum (M T P ) test trail probability (right)
5. Concluding Remarks We have evaluated a maximum likelihood prediction algorithm using three metrics: the hit and miss score, the mean absolute error and the ignorance score. Our experiments show that, as expected, prediction accuracy increases with the order of the model, and also increases when unexpected events, controlled by the parameter α, are being detected rather than being predicted. Our experiments show that the accuracy of prediction varies for different data sets. We also discussed the different interpretations of the three scoring metrics: HM can be understood in terms of the expected maximum likelihood probability of the last link on a trail (M T P ), MAE can be understood in terms of the expected rank of the last link on the trail that was followed minus one, and IS can be understood in terms of the expected probability of the last link on a trail that was followed by the user (AT P ). Future work involves a better understanding of what makes the prediction algorithm perform better on different data sets. In addition, we would like to take into account concept drift [15] when building the Markov model, since we do not expect the probabilities to be stationary. Finally, we also wish to apply the prediction algorithms to data sets from applications areas such as patrolling the Web.
References [1] G. Bejerano. Algorithms for variable length Markov chain modelling. Bioinformatics, 20(5):788–789, March 2004. [2] P. Berka. Guide to the click-stream data. In Proceedings of the Discovery Challenge Workshop, in Conjunction with ECML/PKDD, 2005. [3] J. Borges and M. Levene. Data mining of user navigation patterns. In B. Masand and M. Spiliopoulou, editors, Web Usage Analysis and User Profiling, LNAI 1836, pages 92–111. Springer-Verlag, Berlin, 2000. [4] J. Borges and M. Levene. An average linear time algorithm for web usage mining. International Journal of Information Technology and Decision Making, 3(2):307–319, June 2004. [5] J. Borges and M. Levene. Generating dynamic higher-order Markov models in web usage mining. In Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), LNAI 3721, pages 34–45, Porto, Portugal, October 2005.
J. Borges and M. Levene / Mining Users’ Web Navigation Patterns and Predicting Their Next Step
55
[6] J. Borges and M. Levene. Testing the predictive power of variable history web usage. Soft Computing, 11(8):717–727, 2007. [7] J. Borges and M. Levene. Evaluating variable length Markov chain models for analysis of user web navigation sessions. IEEE Transactions on Knowledge and Data Engineering, 19(4):441–452, 2007. [8] H. Chen. Editorial, Intelligence and security informatics: information systems perspective. Decision Support Systems, 41:555–559, 2006. [9] X. Chen and X. Zhang. A popularity-based prediction model for web prefetching. IEEE Computer, 36(3), pages 63–70, 2003. [10] M. Deshpande and G. Karypis. Selective Markov models for predicting web page accesses. ACM Transactions on Internet Technology, 4(2):163–184, May 2004. [11] X. Dongshan and S. Juni. A new Markov model for web access prediction. IEEE Computing in Science & Engineering, 4(6):34–39, November 2002. [12] M. Eirinaki, M. Vazirgiannis, and D. Kapogiannis. Web path recommendations based on page ranking and Markov models. In Proceedings of the 7th ACM international workshop on Web Information and Data Management (WIDM), pages 2–9, New York, NY, USA, 2005. [13] L. Geng and H.J. Hamilton. Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3), 2006. [14] J.G. Kemeny and J.L. Snell. Finite Markov Chains. D. Van Nostrand, Princeton, NJ, 1960. [15] I. Koychev. Experiments with two approaches for tracking drifting concepts. Serdica Journal of Computing, 1:27–44, 2004. [16] K. McGarry. A survey of interestingness measures for knowledge discovery. The Knowledge Engineering Review, 20(1):39–61, 2005. [17] B. Mobasher. Web usage mining and personalization. In Munindar P. Singh, editor, Practical Handbook of Internet Computing. Chapman Hall & CRC Press, Baton Rouge, 2004. [18] M. Perkowitz and O. Etzioni. Towards adaptive web sites: Conceptual framework and case study. Artificial Intelligence, 118(2000):245–275, 2000. [19] M.S. Roulston and L.A. Smith. Evaluating probabilistic forecasts using information theory. Monthly Weather Review, 130:1653–1660, 2002. [20] S. Schechter, M. Krishnan, and M.D. Smith. Using path profiles to predict HTTP requests. Computer Networks and ISDN Systems, 30(1-7):457–467, 1998. [21] M. Spiliopoulou, B. Mobasher, B. Berendt, and M. Nakagawa. A framework for the evaluation of session reconstruction heuristics in web usage analysis. IN-FORMS Journal on Computing, 15(2):171–190, 2003. [22] R.L. Winkler. Scoring rules and the evaluation of probabilies (with discussion). Test, 5:1–60, 1996. [23] I.H. Witten and E. Frank. Data Mining, Practical Machine Learning Tools and Techniques. MorganKaufmann, San Francisco, Ca., 2nd edition, 2005. [24] C. Zhai and J. Lafferty. A study of smoothing methods for language models applied to information retrieval. ACM Transactions on Information Systems, 22(2):179–214, 2004.
56
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
Data Mining for Security and Crime Detection Gerhard PAAß 1 , Wolf REINHARDT, Stefan RÜPING, and Stefan WROBEL Fraunhofer Institute for Intelligent Analysis and Information Systems, Sankt Augustin, Germany
Abstract. As the Internet becomes more pervasive in all areas of human activity, attackers can use the anonymity of cyberspace to commit crimes and compromise the IT infrastructure. As currently there is no generally implemented authentification technology we have to monitor the content and relations of messages and Internet traffic to detect infringements. In this paper, we present recent research on Internet threats such as fraud or hampering critical information infrastructure. One approach concentrates on the rapid detection of phishing email, designed to make it next to impossible for attackers to obtain financial resources or commit identity theft in this way. Then we address how another type of Internet fraud, the violation of the rights of trademark owners by the selling of faked merchandise, can be semi-automatically solved with text mining methods. Thirdly, we report on two projects that are designed to prevent fraud in business processes in public administration, namely in the healthcare sector and in customs administration. Finally, we focus on the issue of critical infrastructures, and describe our approach towards protecting them using a specific middleware architecture.
Keywords. Internet security, email fraud, phishing, trademark infringement, counterfeit merchandise, Internet auctions, critical infrastructure
Introduction Classically, the most severe and dangerous security threats to countries, organizations and individuals are considered to be physical acts of violence, such as the ones we have sadly had to observe in recent years. Consequently, besides classical police work, efforts in the online realm have concentrated strongly on finding individuals and organizations who are offering material that incites towards such acts of violence, or who are using electronic means to arrange for committing them. At the same time, however, it has become clear that the nature of the threats, and the structure of organizations and individuals that deal with the threat has started to change.
1 Corresponding Author: Gerhard Paaß, Fraunhofer Institute for Intelligent Analysis and Information Systems,IAIS, Schloss Birlinghoven, 53757 Sankt Augustin, Germany, http://www.iais.fraunhofer.de; Email:
[email protected]
G. Paaß et al. / Data Mining for Security and Crime Detection
57
Firstly, the distinction between criminal activity carried out for purely financial gain and security threats motivated by political or ideological reasons is beginning to dissolve. More and more, we are seeing that the Internet is being used to provide financing for politically or ideologically motivated offences, and that techniques that up to now have been associated only with financial crime, such as phishing, are being used in this context. Drying up these sources of funds through measures designed to prevent phishing and other financial fraud on the Internet thus becomes an important contribution not only to fighting crime in general, but also to defend against larger scale security threats. Secondly, the nature of the threats is changing dramatically. While previously, explosives or other chemical, biological or nuclear weapons were needed to seriously threaten the general public or infrastructure of a country, recent examples such as the attacks against Estonia in the spring of 2007 [Landler, Markoff 07, Rhoads 07] show that nowadays, critical infrastructures can be destabilized by entirely nonphysical methods, simply by attacking a country’s infrastructure with suitable means. In this paper, we therefore present recent research that is not primarily directed at identifying individuals conspiring to threaten countries or organizations, but which is focused on the general Internet threats that provide the financial basis for such activities. In particular, in the following sections, we first present a research project centrally focused on the rapid detection of phishing email, designed to make it next to impossible for attackers to obtain financial resources or commit identity theft in this way. In the next section, we then show how another type of Internet fraud, the violation of the rights of trademark owners by offering faked merchandise, can be semiautomatically detected with text mining methods. Thirdly, we report on two projects that are designed to prevent fraud in business processes in public administration, namely in the healthcare sector and in customs administrations. Finally, we focus on the issue of critical infrastructures, and describe our approach towards protecting them using a specific middleware architecture.
1. Fighting Phishing: The Anti-Phish Project
Figure 1. Example of a phishing email (© wikipedia http://en.wikipedia.org/wiki/Image:PhishingTrustedBank.png)
58
G. Paaß et al. / Data Mining for Security and Crime Detection
One of the most harmful forms of email spam is phishing. Criminals are trying to convince unsuspecting online customers of various institutions to surrender passwords, account numbers, social security numbers or other personal information. To this end they use spoofed messages which masquerade as coming from reputable online businesses such as financial institutions (see Figure 1 for an example). It includes a web link or a form to collect passwords and other sensitive information. Subsequently this information is used to withdraw money, enter a restricted computer system, etc.
Number of Hijacked Brands by Month 180 160 140 120 100 80 60 40 20 0 April
June
August
October
December
February
April
Figure 2. Brands used in phishing emails April '06 – April'07 according to AntiPhishing Working Group (© Fraunhofer IAIS)
The AntiPhishing Working Group reports [APWG 07] that phishing has increased enormously over the last months and is a serious threat to global security and economy (see Figure 2). Most often banks and online payment services are targeted. Others phishers obtain sensitive data from U.S. taxpayers by fraudulent IRS-emails. Recently more non-financial brands were attacked including social networking (e.g. myspace.com), VoIP, and numerous large web-based email providers. (see Figure 3, source of graphics and information: APWG 07). There is an upward trend in the total number of different phishing emails sent over the whole Internet. They grew from 11121 in April 2006 to 55643 in April 2007. There has been a massive increase of phishing sites over the past year. In addition there is an increasing sophistication of phishing e-mails, e.g. by link manipulation, URL spelling using unicode letters, website address manipulation. Finally there is an evolution of phishing methods from shotgun-style email to phishing using embedded images and targeted attacks to specific organizations (“spear phishing”).
G. Paaß et al. / Data Mining for Security and Crime Detection
59
Figure 3. Phishing emails attacks by business sector of attack brand (© Fraunhofer IAIS)
Figure 4. Anti-Phish project logo (© AntiPhish Consortium)
AntiPhish (see Figure 4, http://www.antiphishresearch.org/press.html) is a specific targeted research project funded under Framework Program 6 by the European Union. It started in January 2006 and will run until December 2008. AntiPhish is an acronym for “Anticipatory Learning for Reliable Phishing Prevention”. The consortium consists of six partners. AntiPhish aims at developing spam and phishing filters with high accuracy for use both on traditional emails and mobile messaging services. The scientific focus of the project is on trainable and adaptive filters that are not only able to identify variations of previous phishing messages, but are capable of anticipating new forms of phishing attacks. Such technology does not exist yet, but
60
G. Paaß et al. / Data Mining for Security and Crime Detection
could greatly improve all existing methods used in spam and phishing filters. So the project does not pursue new legal regulations or the change of email protocols, but is concentrating on technical recognition approaches. Besides Fraunhofer IAIS the consortium comprises of a reputable university (K.U. Leuven), a world leading company (Symantec), a major Internet service provider (Tiscali) and a leading provider of mobile phone infrastructure (Nortel). The research will be driven by the hands-on expertise of our industrial participants, who have years of success fighting spam on a global scale. The AntiPhish project not only aims at developing the filter methodology in a test laboratory setting, but has the explicit goal to implement this technology in real world settings at our partners sites, to be used to filter all email traffic online in real time, as well as content filtering at the edge of wireless networks. Figure 5 shows the structure of the project [AntiPhish 06]. From the stream of emails appropriate features are extracted to train and estimate classifiers in a laboratory setting. Subsequently these filters are simulated in real-world conditions in the Symantec labs. Finally, they will be deployed into large-scale real world environments at an Internet provider and a mobile phone provider.
Figure 5. Anti-Phish project structure (© AntiPhish Consortium)
If successful all of this technology will be implemented in Symantec’s Global Intelligence Network where people are working in three shifts, 24 hours a day, around the globe to help fight spam and phishing. Success against these threats will always require a combination of human labor and intelligent algorithms. The main approach of this project is to obtain training data from the email stream, to extract features, to estimate and update classifiers and, at the end, to deploy them at the Internet service provider. A central challenge to this task is concept drift and the project will develop adaptive approaches to detect this concept drift and react on it.
G. Paaß et al. / Data Mining for Security and Crime Detection
61
2. Detecting Illegal Products: Text Mining to Identify Fake Auction Offers According to a current study by the University of Mainz [Huber et al. 06] the number of faked products seized by German customs between 1998 and 2004 rose by about 1000 percent. The real number of fake products is estimated to be significantly higher. Whereas previously mainly watch, clothing and perfume industries had to face this problem, now the pharmaceutical, automobile and aeronautical industries are affected as well. For a perfume web auction in a specific period 84.4 percent of products in the sample survey could be identified as fakes, and only 7 percent as the genuine article. Besides the financial losses for the original manufacturer the poor quality of fake products can adversely affect the original brand.
Figure 6. Counterfeited Luxury Watch (© wikipedia http://en.wikipedia.org/wiki/Image:Frolex.jpg)
Often the fake products are openly offered as replicas, remakes, etc., and the customer knows that he will get a fake product, but nevertheless with the prestige of the genuine product. For a well-known manufacturer of luxury watches Fraunhofer IAIS developed a filter to detect such fakes in Ebay™ watch offer auctions. First a training set of genuine and fake watch offers were compiled. Then a classifier was trained to detect the different classes using the text of the offer and format features as inputs. On a training set these classifiers showed very good performance and needed very little time for actual filtering.
62
G. Paaß et al. / Data Mining for Security and Crime Detection
Therefore it may be used in the workflow of an Internet auction platform. Whenever a new offer is entered the classifier checks the text and immediately bans a suspicious auction. The additional computational effort for the auction provider is minimal. Using the results of the project the highest German court, the Bundesgerichtshof, ruled that a brand product manufacturer can require an Internet auction provider to set up a filter to identify fake offers and exclude them from the auctions [Bundesgerichtshof 07].
3. Preventing Fraud: The iWebCare and RACWeB Projects The assessment of fraud risks associated with business processes is a very interesting field of application for data mining. With respect to security and crime detection, those risks can, for example, be the risk of customs offences, or the risk of fraudulent activities in public administration. This has a significant economical impact; for example according to the Counter Fraud Service of the UK’s National Health System, fraud accounts for almost 3% of public healthcare expenditures in the UK. The projects iWebCare and RACWeB (Risk Assessment in Customs in the Western Balkans), in which Fraunhofer IAIS takes part, are aimed at implementing anti-fraud measures in public administration based on data mining techniques in the domains of healthcare and customs, respectively, in order to improve the efficiency and transparency of risk assessment and fraud detection and prevention. The problem of fraud detection is characterized by the adversarial setting of a fraudster trying to hide from fraud detection in a large amount of data. This setting has important implications that distinguish fraud detection from standard data mining tasks: Skewed class distribution: there are many different estimates of how many cases of fraud exist in different domains. What they all have in common is that fraud is always the exception to the rule, that is, the percentage of fraud cases is usually quite low. This poses a problem for many supervised learning algorithms, which usually work best when there are equally many positive and negative examples. Skewed class distributions can be addressed in data mining by forms of sampling [Scholz, 2005]. Sparsely labeled data: fraud is a complex organizational problem, and it is usually not trivial to determine whether a given case actually constitutes fraud or not, as many other legal, organizational, and practical issues have to be considered. As a result, one cannot expect that fraud experts can produce large labeled data sets that would be necessary to train supervised methods. Instead, one has to take into account the fact that expert feedback is a scarce resource and one must make optimal use of the limited time that experts have by using methods like active learning and semi-supervised learning [Chapelle et al., 2006]. False negatives: a false negative is a case of fraud which the system has labeled as non-fraud. While a case the system labels as fraud will be investigated by a fraud operator, such that false positives will be corrected later in the fraud discovery process, false negatives will not be inspected any further and disappear in the large amount of cases which are seemingly correct. Hence, completely novel, unknown methods of committing fraud will not be detected by a supervised learning scheme and one must rely on unsupervised methods to detect new trends and developments in the data that may turn out to be fraud on further inspection. The general problem with this is that while it is possible to confirm a detected case of fraud with high confidence, it is much
G. Paaß et al. / Data Mining for Security and Crime Detection
63
more difficult to decide whether a given case is not fraudulent or whether the fraud is simply hidden too well. Trivial rules: a standard approach for fraud detection would be to collect an initial set of known fraud cases from fraud inspectors and then to use a supervised learner to generalize these fraud cases into rules to detect future cases of fraud. The problem with this approach is that fraud inspectors already use rules for finding fraud. These rules may either be given explicitly as a set of procedures to apply to new cases (an example of this would be to check that no two invoices have the same serial number), or implicitly by the way fraud inspectors work (an example being that when fraud inspectors come upon a novel case of fraud, they try to find similar cases, e.g., by checking all the invoices submitted by the same company). Consequently, the set of known fraud cases given to the system is not randomly selected, as would be assumed by standard statistical techniques, but are biased in the sense that only fraud cases that are detectable by the known fraud rules are included. When this happens, the best thing the data mining algorithm can do is to re-construct the old rules that have been used to construct the data set. Returning these rules to the fraud inspectors will be disappointing to them, because they will only get back what they already know. Concept drift: as a direct result of the adversarial nature of fraud and anti-fraud measures, whenever there is a good way to detect certain cases of fraud, fraudsters will sooner or later adapt to the detection strategy and will try to find novel ways to cheat the system. This means that fraud is evolving over time and hence one cannot expect fraud rules to remain constant over time. This scenario is called concept drift in the machine learning literature and must be treated by careful validation of the learning results [Widmer, Kubat, 1996]. Interpretability: data mining is only one step in the process of fighting fraud. Human fraud inspectors and automatic data mining have to interact closely to have the maximum effect. In order to achieve this interactivity, it is important that the rules returned by the system are interpretable to the user, such that he can decide whether the new pattern that the algorithm has discovered actually describes fraud or not [Rüping, 2006]. From this discussion it follows that one has to distinguish between two different goals of data mining fraud detection. 1) Detection of new fraud cases of a known fraud pattern. When a new case of fraud is detected, the goal of fraud detection is not only to stop and prosecute this particular instance of fraud, e.g., by dismissing an employee who was involved in procurement fraud, but also to prevent similar cases of fraud from occurring, e.g., by finding indicators that facilitate the identification of such cases earlier and with higher confidence. Supervised learning can be used to find these indicators by generalizing the single cases into high-quality rules, and prevent the same type of fraud from happening again. 2) Detection of new fraud patterns. It is safe to assume that new types of fraud are being developed all the time. Hence, fraud detection cannot only rely on tracing known types of fraud, but must also incorporate methods to find new fraud patterns. In order to do this, one cannot rely on known fraud labels, but must identify unusual patterns based on other properties of the data. Once a statistical significant deviation is found, the pattern can then be reported back to a fraud officer for investigation. An example might be that a certain type of doctor spends much more money per patient than the rest. While it can be statistically confirmed that such a deviation in the budget is indeed significant and not random, one can usually not decide from the given data
64
G. Paaß et al. / Data Mining for Security and Crime Detection
whether there is a valid reason for the higher spending (e.g., the doctor treating a special group of high-risk patients that require more expensive treatment) or whether this is a sign of fraud. This makes unsupervised fraud detection more challenging, because it needs to combine high statistical significance of the found patterns with interpretability, such that the experts can understand and judge the validity of the patterns.
4. Fighting Threats Against Critical Infrastructures: The IRRIIS Project The EU Integrated Project "Integrated Risk Reduction of Information-based Infrastructure Systems" (IRRIIS) is carried out under the motto: Enhance substantially the dependability of Large Complex Critical Infrastructures (LCCIs) by introducing appropriate Middleware Improved Technology (MIT) components. IRRIIS increases dependability, survivability and resilience of EU critical information infrastructures based on Information and Communication Technology (ICT) and has the objectives to: x x x x x
determine a sound set of public and private sector requirements based upon scenario and related data analysis; design, develop, integrate and test MIT components suitable for preventing and limiting cascading effects and supporting automated recovery and service continuity in critical situations; develop, integrate, and validate novel and advanced modeling and simulation tools integrated into a synthetic environment (SimCIP) for experiments and exercises; validate the functions of the MIT components using the SimCIP environment and the results of the scenario and data analysis; disseminate novel and innovative concepts, results, and products to other ICTbased critical sectors.
IRRIIS addresses the challenges of Complex Information Infrastructure Protection (CIIP) by a "diagnosis - therapy strategy" and "therapy implementation and validation approach" starting with the electrical power infrastructure and its supporting telecommunication infrastructure. After thoroughly analysing these infrastructures and their interdependencies, the synthetic simulation environment (SimCIP) is build. MIT components are developed, tested and validated inside SimCIP to demonstrate their capabilities before dissemination to potential stakeholders. The approach subsequently includes additional critical infrastructures. The interdisciplinary research is performed by a European consortium of fifteen partners, ranging from academia to key stakeholders from the fields of energy supply and telecommunication. The project is partly financed by the European Union’s Sixth Framework Programme for a term of three years. 4.1. Large Complex Critical Infrastructure Analysis and Requirements Up until now there is a lack of deep understanding of Large Complex Critical Infrastructures' (LCCIs) dependability and interdependency particularly with regard to the use of Information and Communication Technology (ICT). Although some models
G. Paaß et al. / Data Mining for Security and Crime Detection
65
and tools dealing with these issues exist, LCCI complexity cannot yet be tackled properly. Basic research is necessary to understand the phenomena of interdependency, dynamic behaviour and cascading effects in order to support the development of solutions for protecting and managing existing LCCIs in case of incidents. IRRIIS will perform in-depth research regarding the topological structure of LCCIs and the interdependencies between different LCCIs. Appropriate analytical approaches will be applied such as simulation models or analytical models suitable to investigate interdependency, network dynamics and cascading effects. Starting from a thorough analysis of LCCIs, incorporating the stakeholder’s views regarding ICT tools and models, a sound set of public and private sector requirements can be determined. These requirements will be the base for the development of the SimCIP simulation environment and the Middleware Improved Technology (MIT) components. In order to enhance the understanding of LCCIs and to gain a sound foundation for the development of the SimCIP simulation environment and the MIT components IRRIIS will: x x x x x x x
Survey LCCI stakeholder’s requirements on technology and tools needed for understanding and mitigating cascading effects Survey and analyse existing tools and models Analyse current research gaps to identify relevant research and development efforts Provide detailed scenario and risk analysis Perform in-depth topological analysis of LCCIs Analyse the interdependency between different LCCIs Analyse the upcoming Next Generation Networks (NGN), i.e., networks based on IP connectivity or wireless connections with mainly software based services
This work will not only help ensure that the SimCIP environment and the MIT components meet the stakeholder’s needs but also contribute to the ongoing worldwide research efforts concerning LCCIs. 4.2. Middleware Improved Technology Starting with the knowledge gained from the LCCI analysis and the survey of stakeholder’s requirements and existing tools, Middleware Improved Technology (MIT) components are developed. These MIT components facilitate the communication between different LCCIs and allow the identification and evaluation of incidents and malicious attacks and responding accordingly. Currently, one big problem for the dependability, security and resilience of LCCIs is the high interdependence between different LCCIs within the same sector and also between different sectors. The consequence is that problems within one LCCI can lead to severe problems in dependent LCCIs. The resulting cascading effects are not limited to one kind of infrastructure and do not stop at national borders. To make things worse there is often a lack of appropriate communication structures between the dependent LCCIs (see Figure 7). This results in a lack of awareness of problems occurring in other infrastructures and therefore mitigating actions cannot be performed in time.
66
G. Paaß et al. / Data Mining for Security and Crime Detection
Figure 7. Interdependent LCCIs of the same and different sectors. The arrows indicate interdependencies and the lines communication links using different standards. (© IRRIIS Consortium)
To facilitate the communication between different infrastructures, IRRIIS will develop appropriate middleware communication components. All communication between different LCCIs should run via this middleware. The advantage is that each LCCI only needs one communication link to the middleware and does not have to interface with several other LCCIs (see Figure 8).
Figure 8. Interdependent LCCIs with Middleware Communication Layer and Middleware Improved Technology components. (© IRRIIS Consortium)
The middleware will also be used by the optional MIT add-on components which have some kind of build-in “intelligence”. These add-on components will monitor data flowing within and between the infrastructures and raise an alarm in case of intrusions or emergencies and then take measures to avoid cascading effects. They will be able to detect anomalies, filter alarms according to their relevance and support recovery actions and will thus contribute to the security and dependability of LCCIs. MIT components will interface with existing systems and will not require major replacement
G. Paaß et al. / Data Mining for Security and Crime Detection
67
of existing hardware or software. The flexibility of the middleware allows the easy integration of new LCCIs or the exchange of new kinds of information.
4.3. SimCIP Simulator for Critical Infrastructure Protection Application The purpose of the SimCIP simulation environment is twofold: On the one hand, side simulation can be used to improve the understanding of interdependent LCCIs. On the other hand, the MIT components will be tested and validated in experiments using SimCIP. Furthermore, their applicability and usefulness will be demonstrated to stakeholders within the SimCIP environment before deployment to the “real world” systems (see Figure 9).
MI Development & Test in Simulation
MIT Deployment to the Real World
Figure 9. The role of the SimCIP simulation environment in the development of the MIT components. (© IRRIIS Consortium)
Building the SimCIP environment is a big challenge because the simulation will not only have to include physical simulations but also has to simulate the cyber layer and the management layer of a LCCI as well (see Figure 10). For this purpose SimCIP will use the principle of agent-based simulation. Each object will be modeled as an agent with clear interfaces to its environment and other agents. The SimCIP environment will include and interface with existing tools to keep the simulation meaningful with respect to existing technologies and to allow the use of the results gained in current systems. This also means that the SimCIP environment does not have to start from scratch but can rely on already existing and proven technology.
68
G. Paaß et al. / Data Mining for Security and Crime Detection
Figure 10. The different layers of a single LCCI and the according SimCIP simulation objects. (© IRRIIS Consortium)
To decide which tools and models should be included in SimCIP, an in-depth survey of existing tools and models will be performed. However, the main strength of SimCIP will be the simulation of interdependencies between different LCCIs. To that end, one will model some objects of the individual LCCIs on more abstract levels. This will ensure the high scalability and flexibility of the SimCIP environment. SimCIP should be as generic as possible to allow its application to various kinds of LCCIs and its adaptation to the specific needs of individual stakeholders. Knowledge Elicitation and Research will lead to a “diagnosis” of the current and the future status of interdependent LCCIs. The “therapy” will be implemented through the MIT components which can be tested and validated in the SimCIP environment. The main contributions of IRRIIS are an enhanced understanding of LCCIs, the SimCIP simulation environment and the MIT components. To disseminate the results broadly to stakeholders, technology and service providers and the research community, these interest groups will be included within the IRRIIS project right from the start. IRRIIS also relies on international cooperation and is open to joint efforts of all kinds to achieve its goals. To foster international cooperation IRRIIS will establish an international conference and will define scenarios and benchmarks to allow the comparison of different approaches.
5. Conclusion In this paper, we have given an overview of several projects currently carried out at our institute which are aimed at fighting Internet related crime. As these projects show, to
G. Paaß et al. / Data Mining for Security and Crime Detection
69
fully address the issue of Internet related security threats, especially when looking towards politically and ideologically motivated attacks, requires consideration not only of physical violence, but also of the criminal activities that provide the funds for such activities. As a primary example, phishing is used on the Internet in this way, and we have described how phishing activities can be suppressed using advanced text mining solutions. In related projects, we show how data mining and text mining techniques can be used to prevent fraud with fake auction goods, and in the medical administration system. Finally, we have described how specific software architectures and middlewares can be used to protect critical infrastructures consisting of technical, economic and social systems that are interrelated. All the above projects form part of what we call “Preventive Security” which is one of the major areas of activity for our institute. In addition to the projects described here, we provide services to military and non-military organizations in the area of organizational planning, simulation and process intelligence, as well as research and applied work on physical hardware and robots for security and inspection purposes.
Acknowledgements This work was funded in part by the EU FP6 projects AntiPhish (contract 027600), IRRIIS (contract 027568), iWebCare (contract 28055), and RACWeB (contract 045101).
References AntiPhish (2006): Website of the project. http://www.antiphishresearch.org/home.html. APWG (2007): Phishing Activity Trends. Report for the Month of April, 2007. http://www.antiphishing.org/reports/ apwg_report_april_2007.pdf. Bundesgerichtshof (2007): Bundesgerichtshof bestätigt Rechtsprechung zur Haftung von eBay bei Markenverletzungen. Press release 45/2007, April 19th 2007. Chapelle, O., and Schölkopf, B., and Zien, A. (2006): Semi-Supervised Learning, MIT Press, Cambridge, MA. Huber, F., Matthes, I., Vollhardt, K., Ulbrich, D. (2006): Marken- und Produktpiraterie aufdecken und bekämpfen – am Beispiel von Internetauktionen eines Markenparfums Arbeitspapiere Management P6 Center of Market-Oriented Product and Production Management Mainz ISBN: 3-938879-13-0. Landler, M., Markoff, J. (2007): Digital Fears Emerge After Data Siege in Estonia. Online edition of 2007. http://www.nytimes.com/2007/05/29/technology/ NewYork Times, May 24th, 29estonia.html?pagewanted=1&ei=5070&en=5858f0fda0af7087&ex=1184644800. Rhoads, C. (2007): Cyber Attack Vexes Estonia, Poses Debate. The Wall Street Journal Online. May 18, 2007. Page A6. Rüping, Stefan (2006): Learning Interpretable Models, Ph.D. Thesis, Universität Dortmund, URL: http://hdl.handle.net/2003/23008. Scholz, Martin (2005): Sampling-Based Sequential Subgroup Mining. In Grossman, R. L. and Bayardo, R. and Bennett, K. and Vaidya, J. (editors), Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '05), Seiten 265--274, Chicago, Illinois, USA, ACM Press. Widmer, G. and Kubat, M. (1996): Learning in the presence of concept drift and hidden contexts, Machine Learning 23, pp. 69-101.
70
G. Paaß et al. / Data Mining for Security and Crime Detection
Copyright of images: x x x x x x
Figure 1: Public domain image from http://en.wikipedia.org/wiki/Image:PhishingTrustedBank.png Figure 2 & 3: Own Graphs Figure 4: Logo of our own project AntiPhish, copyright AntiPhish consortium Figure 5: Graph of our own project AntiPhish, copyright AntiPhish consortium Figure 6: Public domain image from http://en.wikipedia.org/wiki/Image:Frolex.jpg Figures 7-10: Graphs of our own project IRRIIS, copyright IRRIIS consortium
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
71
Enhancement to the Advanced Terrorist Detection System (ATDS) Bracha SHAPIRAa1 ,Yuval ELOVICIb, Mark LASTa, Abraham KANDELc a Department of Information Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel b Deutsche Telekom Laboratories at Ben-Gurion University of the Negev Beer-Sheva, Israel c Department of Computer Science and Engineering, University of South Florida
Abstract. The ATDS system is aimed at detecting potential terrorists on the Web by tracking and analyzing the content of pages accessed by users in a known environment (e.g., university, organization). The system would alert and report on any user who is "too" interested in terrorist-related content. The system learns and represents the typical interests of the users in the environment. It then monitors the content of pages the users access and compares it to the typical interests of the users in the environment. The system issues an alarm if it discovers a user whose interests are significantly and consistently dissimilar to the other users' interests. This paper briefly reviews the main ideas of the system and suggests improving the detection accuracy by learning terrorists' typical behaviors from known terrorist related sites. An alarm would be issued only if a "non-typical" user is found to be similar to the typical interests of terrorists. Another enhancement suggested is the analysis of the visual content of the pages in addition to the textual content. Keywords. Cluster-Analysis, Content-based detection, Similarity measure
Introduction Terrorists increasingly take advantage of the Internet as a cheap and accessible infrastructure for intelligence and propaganda. The Internet enables anonymous communication with other terrorists, coordination of activities, promotion of new ideas recruiting new members into terror organizations. to a mass audience, and Governments and intelligence agencies are trying to track terrorists and their activities 1
Corresponding Author: Bracha Shapira, Department of Information Systems Engineering, Ben-Gurion University; Email:
[email protected]
72
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
on the Web in order to prevent future acts of terrorism [3,5]. Vast amounts of resources are invested in research aimed at developing new methods and technologies for the cyber intelligence effort. One fact is that terrorists and their supporters are accessing the Web for their activities and to browse terror-related sites. This is especially true for "newcomers" who are planning to form a new terrorist cell, and browse terror-related sites to obtain relevant information for terrorist activities. It is therefore desired to detect users who are continuously accessing terror-related sites and to further examine if they are indeed interested in committing terrorist acts. It is not feasible to monitor known terror-related sites in order to detect users who access them since terrorist sites tend to change their locations very often to prevent surveillance by intelligence agencies. The Advanced Terrorist Detection System (ATDS) is using a content-based approach for the detection of potential terrorists and their supporters while they access the Web by monitoring and analyzing the content of the web pages accessed. The assumption underlying ATDS is that it is possible to determine users' interests (referred to as profiles) from this analysis [1,2]. Using this approach, real time web traffic monitoring can be performed to identify terrorists and their supporters as they access terror-related information on the Internet. The current implemented version of ATDS is described in detail in [1,2,7]. In this paper we provide a brief overview of the current version of ATDS, and suggest an extension to the underlying model that is aimed at improving ATDS performance. We also point out the current version's limitations, and suggest improvements that are being implemented and evaluated now. The paper is structured as follows: Section 1 briefly reviews ATDS and reports the results of the experiments conducted to examine its feasibility and performance. Section 2 presents the model extension. Section 3 lists further suggestion to improve the system based on the current version's limitations and Section 4 concludes with future issues.
1. ATDS Review 1.1. ATDS Model ATDS uses the content of web pages accessed by a group of users in a specific environment as an input for detecting non-typical activities of individual users. ATDS analyzes the textual content of web pages. The underlying idea is to learn and model the typical interests of a group of users in a certain environment such as a company, a university campus, or a public organization and then identify users whose interests are atypical, i.e., users whose interests are consistently and significantly dissimilar to the typical interests in the environment. These users are referred to as "abnormal" or "nontypical" users. The model consists of two phases, the learning phase and the detection phase: During the learning phase - the web traffic of a group of users is recorded and an efficient representation is created for further analysis. We use the vector-space model [6] and cluster analysis to represent users' typical interests, i.e., each page is transformed to a vector of weighted terms. The set of users' vectors are clustered to represent the users' areas of interests. The learning phase is applied in the same environment where the detection would later be applied in order to learn the typical content of users in the environment.
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
73
The detection phase is aimed at detecting non-typical users, i.e., users whose interests are consistently and significantly dissimilar to the typical interests of the group. The detection is performed on-line while the users browse the Internet. Each accessed page is represented as a vector and compared to the known typical interests of the reference group. The level of consistency and significance of the dissimilarity can be configured by the dissimilarity threshold and the number and frequency in a time frame of non-typical accesses that would cause an alert. The learning and detection phases are described briefly in the following sections. The reader is referred to [1,2,7] for further details. 1.1.1. Learning Phase During the learning phase, a database representing the interests of the monitored group is generated. During the detection phase the content of the pages users access is compared to this database. The learning module includes the Filter, Vectors-generator and the Clustersgenerator components. The functionality of these components are: each page of the training data is sent to the Filter for exclusion of non-appropriate pages, e.g., nontextual pages, or pages in languages not supported by the system, and for omitting images and tags related to the content format. The filtered pages are then sent to the Vectors-generator component that generates a weighted terms vector for each page. The vector entries represent terms, and their values represent the discriminate value of the term to the page defined by the normalized frequency of the term on the page, and by other properties of the term, such as if it is part of the title, or its position on the page. The vectors are recorded for the clustering process that follows. The Clusters-generator module (Figure 1) receives the vectors from the Vectorsgenerator and performs cluster-analysis on it. Cluster-analysis methods group objects of similar kinds to respective categories. A clustering process receives as input a set of objects and their attributes and generates clusters (groups) of similar objects based on their attribute, so that objects within a cluster have high similarity in their attribute values, and objects between groups are dissimilar. The objects in ATDS are the pages, and the attributes are the weighted terms. The n clusters generated by the Clustergenerator represent the n areas of interest of the users in the monitored environment. The optimal n is defined by the clustering algorithm. For each cluster, the Grouprepresentor component computes the central vector (centroid), denoted by Cvi for cluster i. In the ATDS context, each centroid represents an area of interest for the users in the environment. The learning phase is a batch process and should be activated recurrently to assure up-to-date representation of the users’ interest. 1.1.2. The Detection Phase During the detection phase, a group of computers in a particular environment is monitored to detect non-typical users. The content of web-accesses of the group members is collected on-line and compared to the set of pre-defined cluster centroids
74
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
Training Data
Filter
Vectors Generator
Vectors of Group’s Transactions
Clusters-Generator
Cluster 1 (Vectors)
Cluster n (Vectors)
Group-Representors
Group Interests represented
Figure 1. The learning phase of the model
(generated during the learning phase). The detection phase consists of the Sniffer, Filter, the Vector–generator and the Detector which are the main components of this phase. The Sniffer captures the pages that users, (identified by their Internet Protocol Addresses (IPs)), access at the network layer, and sends each page to the Filter for further processing. The Filter and the Vector-generator have the same functionality as in the learning phase. The Detector receives the vectors (and their respective IPs) and decides whether to issue an alarm. The Detector measures the distance between each vector and each of the centroids representing an area of interest to the user. Each incoming vector is compared to every cluster centroid, and classified as non-typical if its similarity to all clusters is below a pre-defined threshold. The similarity between the vectors accessed by users and the centroids is measured by the cosine of the angle between them as defined in Equation 1. A vector representing a user access is considered non-typical if the similarity between the access vector and the nearest centroid is lower than the threshold denoted by tr.
§ ¨ ¨ Max ¨ ¨ ¨ ©
· tAvi ¸ ¸ i 1 ,.., i 1 ¸ tr m m m m 2 2 2 2 ¸ tCv tAv tCv tAv ¦ ¦ i1 ¦ i in ¦ i ¸ i 1 i 1 i 1 i 1 ¹ m
¦ tCv
i1
tAvi
m
¦ tCv
in
(1)
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
75
where Cvi is the i-th centroid vector, Av - the access vector, tCvi1 - the i-th term in the vector Cvi , tAvi - the i-th term in the vector Av , and m – the number of unique terms in each vector. The system holds a data-structure to maintain the history of users' accesses. For each known IP address in the environment, a queue is maintained with the most recent vectors accessed by the user/users at their respective IPs. The vector and its classification (typical or not-typical) and the time stamp of the access are recorded into the queue of the specific IP address in the sub-queue data structure. The next step is performed by the Anomaly finder which scans the queue of the IP address of the page accessed and analyzes the set of recorded vectors within the queue, which represent the history of accesses for the specific IP. If the percent of the non-typical vectors in a queue is above a pre-defined threshold, an alarm is generated flagging that the user at the specific IP is consistently accessing non-typical information. The detection algorithm can be calibrated with certain parameters to fine-tune the detection. Some of the parameters are: 1) the dissimilarity threshold, 2) the minimum number of nontypical accesses by the IP that issues an alarm and, 3) the time frame of suspicious accesses by the IP that issues an alarm. These thresholds are set to prevent alerts caused by random accesses, and to prevent alerts caused by the aggregation of accesses from different sessions/users on the same IP. Web Pa es accessed and IP address
Sniffer
Filter
Vectors Generator
Users Queues Access history
Detector
DB of User interests
Anomaly Finder Threshold Parameters Alarm
Figure 2. The Detection Phase
1.2. ATDS Evaluations and Results A very brief overview of ATDS evaluations and the results is presented below, to illustrate the suggested extensions. The reader is referred to [1,2,7] for further details. ATDS evaluation was performed at the Information Systems Engineering Department of Ben-Gurion University in Beer-Sheva, Israel. The evaluation took place in a student teaching lab with 38 PCs. The typical interests of the users were learned from 170,000 accesses to the Web collected during the students' regular activities (with their permission). After the exclusion of non-English pages which ATDS cannot handle, we obtained a collection of 13,300 pages as inputs for the learning phase of the activated Filtering and Vector-generator modules.
76
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
To simulate atypical accesses during the detection phase we collected 582 terrorrelated pages to which we applied the Filtering and Vector-generation modules. We also randomly selected 582 vectors from the data set of typical users so as to simulate typical accesses, in order to examine the system's ability to distinguish between typical and non-typical content. ATDS performance was measured by the fraction of True Positive (TP) alerts which indicate the detection rate, vs. the fraction of False Positive (FP) alerts which indicate the detection completeness. This fraction is described in ROC (Receiver Operator Characteristic) curves. A True Positive (TP) is the percentage of alarms in the case of non-typical activity, a False Positive (FP) is the percentage of false alarms when typical activity is taking place. The ATDS evaluation had two goals; the first was to prove its feasibility; and the second to examine the effect of the following parameters on ATDS performance: the size of the sub-queue for each IP, i.e., the length of the history list of accessed pages kept for each IP, and the percentage of abnormal pages to issue an alert, similarity threshold values for issuing an alert, and the number of clusters representing the normal profile of the monitored users. Three simulations were run; the first examined ATDS monitoring capability where all 38 computers submitted 13 iterations of 100 URL access requests while controlling the time-gap between requests. In this simulation the loss of data was recorded, which turned out to be very minimal. The second and the third simulations manipulated the above mentioned parameters in order to examine their effects. To sum the results briefly (please see [1,2,7] for further details), the experiments showed that all the parameters did have a significant effect on results. For example, the ideal detection was observed for a queue size of 32 and the percentage of atypical vectors required in the queue for issuing an alarm was 100%. However, we do not think that these results should be generalized before further study. The evaluation did prove, besides the feasibility of ATDS, that the system is sensitive to these parameters and that a sensitivity analysis might be required before the application of ATDS to a new data set. ROC Queue Size 32 1 0.9 0.8 0.7 0.6 TP
Alarm Threshold 100% 0.5 Alarm Threshold 50% 0.4 0.3 0.2 0.1 0 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
FP
Figure 3. Results of simulation for queue size= 32 and %accesses in a queue = 50,100
1
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
77
2. Extensions to the Model In the current version of ATDS users who consistently browse content significantly dissimilar compared to the typical interests of their environment will be suspected as potential "terrorists" and will be further investigated. The underlying assumption is that potential terrorists, using the infrastructure of some non-terrorist environment, would be detected due to their non-typical interests. While this assumption is reasonable with respect to real terrorists, it is too general and might cause the detection of users who are not typical to the group, but who are not terrorists. Examples of such users are workers in an organization who are using the organizational infrastructure for private activities or interests during their work, students in a specific department who are interested in topics that have nothing to do with their studies, etc. If the system is aiming at detecting terrorists and not just non-typical users, it might be beneficial to narrow the suspect list in order to prevent further investigation of non-typical users who are not involved in any illegal activities. We suggest the use of a similar but reverse method and test whether a user who is detected as non-typical, has similar interests to known terrorists' interests. This requires the following additions to the ATDS model: The enhanced learning phase would include a process for “learning typical terrorists’ interests" in addition to learning the typical interests of the users in the environment. The typical terrorists’ interests would be derived from many sites known to include terror-related content. Such sites are being monitored by many organizations that track terror activities on the Web. Examples of such organizations are the SITE Institute (www.siteinstitute.org) and MEMRI (www.memri.org). The learning phase components, i.e., the Filter, the Vector-generator, and the Cluster-generator are activated on terror-related sites as an input and the output would be a set of clusters that represent terrorists’ typical interests. Thus, the system holds two sets of clusters, the first represents the typical users' interests in the environment being monitored, and the second represents terrorists' typical interests. The enhanced detection phase (presented in Figure 4) would include an additional component: the "Terrorist Detector" that would receive as an input every user (IP) detected as non-typical to the environment by the Detector component. As described above, a user is flagged as non-typical if a pre-defined percent of the pages she accessed within a pre-defined time-frame are not similar to any of the typical known interests of the environment. The set of vectors viewed by the suspected user (as not similar to the typical known interests) is then compared to the centroids of the clusters representing terrorists' interests (using cosine similarity). An alarm would be issued if the similarity between the user interests and the terrorists’ typical interests is above a pre-defined threshold. Thus, only if a non-typical user is consistently interested specifically in terror-related content, is he then suspected as a potential terrorist and is further investigated. The detection algorithm should be calibrated to set the similarity threshold that would cause an alarm to be issued. The system is flexible to the type of "abnormal" users that it is able to detect. It can actually be tuned to detect any type of dissimilar users. Thus, if law enforcement authorities are interested in detecting child abusers, they can collect web pages with child abuse related content and activate the learning phase on the relevant data.
78
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
Web Page of User Access and User IP
Sniffer
Filter
Vector Generator
Detector User QueuesAccess history
DB of Group User interests
Annomaly finder Detection Parameters
Terrorist Detector
DB of terror related interests
Alarm
Figure 4. Enhanced Detection Algorithm
3. Visual Content Handling ATDS currently handles valid HTML web pages, and extracts only the textual information on the page. Extension of ATDS to support additional formats (e.g., XML) is rather technical, and can be easily solved by adding other interpreters to the model.
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
79
However, many terrorist related pages include typical visual elements rather than text. The visual elements are very strong identifiers of their sources. These elements include typical colors, images (of terrorist leaders or holy places), logos (of organizations), and known phrases. Terror-related visual elements, in addition to the terror-related textual content, may improve the accuracy of ATDS by providing stronger evidence for a terror related page. Ollari & Glotin [8] showed that even simple linear fusion of textual and visual analysis of web pages for image search engines significantly improve retrieval results. They claim that the "textualness" and the "visualness" of web pages are dependent. We believe that the same idea might apply to the representation of a group profile, and that both types of evidence, might improve classification results. We thus intend to add a visual analysis component that will examine the existence of typical terrorist visual elements on a website. The visual analysis is to be integrated into ATDS in its two phases: The learning phase, in the context of visual elements, would apply learning to the typical visual elements on terror-related sites. The detection phase would use the knowledge about typical elements as inputs for the classification of a page to terror-related or non-terror related groups in order to improve classification accuracy. During the first stage we will concentrate on improving detection, thus, we intend to use human experts to define a set of typical visual elements known to appear on terror-related sites. Such elements include background colors, terror-organization logos, and images. We will represent these visual elements efficiently to enable fast comparison during the detection phase[10]. We will then focus on integrating the detection of terror-related content using visual elements on a page in addition to textual content. We will conduct empirical experiments to examine the optimal method of fusion of textual and visual analysis. Several options exist: 1.
2.
Check the existence of terror-related visual elements after textual analysis is applied, regardless of the classification result of the textual analysis. Fuse the results according to a relative weighting scheme. This method is similar to the method presented in [8]. Check the existence of terror-related elements after the textual analysis was applied, only for documents classified to the terror-related group. Use the visual elements as an additional verification for the classification results.
As for visual analysis implementation, (as shown in Figure 5), the Vectorgenerator component of the detection phase will also extract images of every incoming document. The comparison between the visual elements of a user-accessed web page and the known terror-related visual elements would be activated only for the pages classified as non-typical to the environment and according to the fusion policy. A crucial consideration for the selection of methods for the non-textual representation of visual elements is their efficiency since the visual analysis is performed on-line during the detection process. Thus, efficient algorithms for extracting, representing and the comparison of visual elements should be used [10].
80
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
Web Page of User Access and User IP
Sniffer
Filter
Vector Generator & Image Extractor User queues Access History
Detector
DB of Group User interests
Anomaly finder Detection Parameters Page images
Terrorist Detector
DB of terror related interests
Visual Analysis DB of terror related visual elements
Alarm
Figure 5. ATDS including visual analysis
4. Future Issues and Limitations For ATDS to become practical, i.e., to enable its use in real environments to monitor web users and detect potential terrorists, the following additional enhancements should be applied: Language - ATDS should support other languages in addition to English which is the only language currently supported. ATDS should support Arabic which is the common language of many Islamist terror organizations. The Arabic language is very challenging for text analysis due to its many special characteristics. For example, a given word in Arabic can be found in many different forms which could be conflated in information retrieval. Many definite articles, particles and other prefixes can be attached to the beginnings of words, and a large number of suffixes can be attached to their ends. Most related forms (such as plural) are irregular, and cannot be formed just by adding prefixes or suffixes [4]. Additionally, most noun, adjective, and verb stems are derived from a few thousand roots by infixing, for example, creating words like
B. Shapira et al. / Enhancement to the Advanced Terrorist Detection System (ATDS)
81
maktab (office), kitaab (book), Kutub (books), kataba (he wrote), and naktubu (we write), from the root ktb [9]. Thus, in the ATDS context, stemming is required to prevent mismatches between a term representing a cluster and a similar term on a web page. There exist some stemmers for Arabic, mainly statistically based stemmers [4], but their performance is far worse than the performance of stemmers in English. ATDS should include the most advanced existing Arabic-based retrieval tools to support Arabic as the inclusion of Arabic is a pre-condition for its practicality. Scalability – The current version of ATDS was evaluated on a network with 38 computers, which of course is not the scale of the environment it is designed for. ATDS would have to be scaled up, optimized, and calibrated for large scale environments and would have to be evaluated in such a large scale environment. We are planning to conduct experiments applying and manipulating the enhancements described above, so we can examine their effect on ATDS performance. The experiments will be conducted with a new set of pages in a different environment to test consistency with former results.
References [1]
Elovici,Y., Shapira, B., Last, M., Kandel, A., and Zaafrany, O. Using Data Mining Techniques for Detecting Terror-Related Activities on the Web, J of Information Warfare, 3 (1) (2004) 17-28. [2] Elovici, Y., Shapira, B., Last, M., Zaafrany, O., Freidman, M., Schneider, M., Kandel, A. ContentBased Detection of Terrorists Browsing the Web Using an Advanced Terror Detection System (ATDS). ISI 2005 (2005), 244-255. [3] Ingram, M.: Internet privacy threatened following terrorist attacks on US, http://www.wsws.org/articles/2001/sep2001/isps24.shtml (2001) [4] Larkey, L., Ballesteros, L., and Connell, M. Improving Stemming for Arabic Information Retrieval: Light Stemming and Co-occurrence Analysis. In Proceedings of ACM SIGIR, (2002), 269-274. [5] Lemos, R. What are the real risks of cyberterrorism?, ZDNet, http://zdnet.com.com/2100-1105955293.html (2002). [6] Salton, G., Wong, A., Yang, C.S., "A Vector Space Model for Automatic Indexing," Communications of the ACM, Vol. 18, 11, (1975) 613–620. [7] Shapira B. Content Based Model for Web Monitoring, Fighting Terror in Cyberspace, Series in Machine Perception and Artificial Intelligence, Vol. 65, (2005), 63-69.. [8] Tollari , S., Glotin, H., Web Image Retrieval on ImagEVAL: Evidences on Visualness and Textualness Concept Dependency in Fusion Models, Conference On Image And Video Retrieval Archive, Proceedings of the 6th ACM International Conference on Image and Video Retrieval (2007), 65-72. [9] Wightwick, J.,Gaafar,M. Arabic Verbs and Essentials of Grammar. Chicago: Passport Books, 1998. [10] Yoo, H-W., Jang, D-S., NA Y-K. An Efficient Indexing Structure and Image Representation for Content-Based Image Retrieval. IEICE Trans Inf Syst (Inst Electron Inf Commun Eng) (2002), 13901398.
82
Security Informatics and Terrorism: Patrolling the Web C.S. Gal et al. (Eds.) IOS Press, 2008 © 2008 IOS Press. All rights reserved.
Discovering Hidden Groups in Communication Networks1 Jeff BAUMES a , Mark K. GOLDBERG a,2 , Malik MAGDON-ISMAIL a , William A. WALLACE b a CS Department, Rensselaer Polytechnic Institute, Troy, NY 12180. b DSES Department, Rensselaer Polytechnic Institute, Troy, NY 12180. Abstract. This chapter presents statistical and algorithmic approaches to discovering groups of actors that hide their communications within the myriad of background communications in a large communication network. Our approach to discovering hidden groups is based on the observation that a pattern of communications exhibited by actors in a social group pursuing a common objective is different from that of a randomly selected set of actors. We distinguish two types of hidden groups: temporal, which exhibits repeated communication patterns; and spatial which exhibits correlations within a snapshot of communications aggregated over some time interval. We present models and algorithms, together with experiments showing the performance of our algorithms on simulated and real data inputs. Keywords. statistical communication analysis, terrorist networks, graph clustering, temporal correlation
1. Introduction 1.1. Motivation Modern communication networks (telephone, email, Internet chatroom, etc.) facilitate rapid information exchange among millions of users around the world. This vast communication activity provides the ideal environment for groups to plan their activity undetected: the related communications are embedded (hidden) within the myriad of random background communications, making them difficult to discover. When a number of individuals in a network exchange communications related to a common goal, or a common activity, they form a group; usually, the presence of the coherent communication activity imposes a certain structure of the communications on the set of actors, as a group. A group of actors may communicate in a structured way while not being forthright in exposing its existence and membership. This chapter develops statistical and algorithmic approaches to discovering such hidden groups. 1 This article is a reproduction of the article “Identification of Hidden Groups in Communications,” by J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace, Handbook in Information Systems, Volume 2, pp. c Elsevier B. V. 209 - 242; 2007, 2 Corresponding Author: Rensselaer Polytechnic Institute; 110 8th street, Troy, N.Y., 12180; USA; Email:
[email protected].
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
83
Finding hidden groups on the Internet has become especially important since the September 11, 2001 attacks. The tragic event underlines the need for a tool (a software system) which facilitates the discovery of hidden (malicious) groups during their planning stage, before they move to implement their plans. A generic way of discovering such groups is based on discovering correlations among the communications of the actors of the communication network. The communication graph of the network is defined by the set of its actors, as the vertices of the graph, and the set of communications, as the graph’s edges. Note that the content of the communications is not used in the definition of the graph. Although the content of the messages can be informative and natural language processing may be brought to bear in its analysis, such an analysis is generally time consuming and intractable for large data-sets. The research presented in this chapter makes use of only three properties of a message: its time, the name of the sender and the name of the recipient of the message. Our approach to discovering hidden groups is based on the observation that a pattern of communications exhibited by actors in a social group pursuing a common objective is different from that of a randomly selected set of actors. Thus, we focus on the discovery of such groups of actors whose communications during the observation time period exhibit statistical correlations. We will differentiate between spatial and temporal correlations, which as we shall see, lead to two different notions of hidden groups. 1.2. Temporal Correlation One possible instance of temporal correlation is an occurrence of a repeated communication pattern. Temporal correlation may emerge as a group of actors are planning some future activity. This planning stage may last for a number of time cycles, and, during each of them, the members of the group need to exchange messages related to the future activity. These message exchanges imply that, with high probability, the subgraph of the communication graph formed by the vertices corresponding to the active members of the group is connected. If this connectivity property of the subgraph is repeated during a sufficiently long sequence of cycles, longer than is expected for a randomly formed subgraph of the same size, then one can discovers this higher-than-average temporal correlation, and hence identify the hidden group. Thus, in order to detect hidden groups exhibiting temporal correlations, we exploit the non-random nature of their communications as contrasted with the general background communications. We describe efficient algorithms, first appearing in [4,5], which, under certain conditions on the density of the background communications, can efficiently detect such hidden groups. We differentiate between two types of temporally correlated hidden groups: a trusting, or non-secretive hidden group, whose members are willing to convey their messages to other hidden group members via actors that are not hidden group members, using these non-hidden group members as “messengers”; and, a non-trusting, or secretive hidden group, where all the “sensitive” information that needs to be conveyed among hidden group members uses only other hidden group members as messengers. Our results reveal those properties of the background network activity and hidden group communication dynamics that make detection of the hidden group easy, as well as those that make it difficult. We find that if the background communications are dense or more structured, then the hidden group is harder to detect. Surprisingly, we also find that
84
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
when the hidden group is non-trusting (secretive), it is easier to detect than if it is trusting (non-secretive). Thus, a hidden group which tries to prevent the content of its messages from reaching third parties undermines its operations by becoming easier to detect! 1.3. Spatial Correlation We use spatial correlation to refer to correlations in the communications of a single communication graph, which represents a snapshot of the communications aggregated over some time interval (in contrast to temporal correlation which refers correlation in the communications over multiple communication graphs which represent successive snapshots of the communications). Spatial correlation of messages initiated by a group of actors in a social network can be identified by a higher-than-average total communication level within this group. This property does not rely on the content of the messages and is adequately described by the communication graph: the edge density of the corresponding set of vertices of the graph is higher than that of the average set. To be able to address a wide variety of applications, we consider a general notion of edge density, which compares the intensity of communications between the actors within a particular set and that between the set and the “outside world.” The edge density may be defined in numerous ways depending on the desired characteristics of the discovered groups; our algorithms for discovering groups of higher density (potential hidden groups) are generic with respect to the definition of density. Furthermore, we find only groups which are more dense than any group sufficiently close, which reflects the principle of locality in a social network. For our numerical experiments, we use two main ideas in defining density: one is the proportion of the number of actual communications to the total number of possible communications; and the other is the ratio of the number of communications within the group to the total number of group communications, including messages to individuals outside the group. In graph-theoretical terminology, the problem we study is clustering. An important implication of our approach is that our algorithms construct clusters that may overlap, i.e., some actors may be assigned to more than one group. While there is much literature in the area of graph clustering, up until very recent work it has mainly focused on a specific sub-case of the problem: graph-partitioning. As opposed to partitioning algorithms, which decompose the network into disjoint groups of actors, general clustering allows groups to extend to their natural boundaries by allowing overlap. We discuss prior work in the area of partitioning, and present three general clustering heuristics, originally described in [2,3]. We refer to these procedures by the names Iterative Scan (IS), Rank Removal (RaRe) and Link Aggregate (LA). We present experimental data that illustrate the efficiency, flexibility, and accuracy of these heuristics. Searching for both spatial and temporal correlation may be combined to produce a more effective algorithm for the identification of hidden groups. The temporal algorithms may indicate that a large group of individuals are involved in planning some activity. The spatially-correlated algorithm may then be used to cluster this large group into overlapping subgroups, which would correspond to smaller working groups within the larger group. We present results from the testing of our spatial-hidden group algorithms on a number of real-world graphs, such as newsgroups and email. We analyze the quality of the
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
85
groups produced by the clustering algorithms. We also test the algorithms on random graph models in order to determine trends in both runtime and accuracy. One of the interesting experimental discoveries that different implementations of the Iterative Scan algorithm are optimized for different domains of application based on the sparseness (density) of the communication network. 2. Discovering Temporal Correlation 2.1. Literature Review Identifying temporally correlated hidden groups was initiated in [30] using Hidden Markov models. Here, our underlying methodology is based upon the theory of random graphs [7,22]. We also incorporate some of the prevailing social science theories, such as homophily [32], by incorporating group structure into our model. A more comprehensive model of societal evolution can be found in [20,37]. Other simulation work in the field of computational analysis of social and organizational systems [9,10,36] primarily deals with dynamic models for social network infrastructure, rather than the dynamics of the actual communication behavior, which is the focus of this chapter. One of the first works analyzing hidden groups is found in [14]. Here, the author studies a number of secret societies, such as a resistance that was formed among prisoners at Auschwitz during the Second World War. The focus, as it is in this paper, was on the structure of such societies, and not on the content of communications. An understanding of a hidden network comes through determining its general pattern and not the details of its specific ties. The September 11, 2001 terrorist plot spurred much research in the area of discovering hidden groups. Specifically, the research was aimed at understanding the terrorist cells that organized the hijacking. Work has been done to recreate the structure of that network and to analyze it to provide insights on general properties that terrorist groups have. Analyzing their communication structure provides evidence that Mohammed Atta was central to the planning, but that a large percent of the individuals would have needed to be removed in order to render the network inoperable [39]. In “Uncloaking Terrorist Networks” [29], Krebs uses social network measures such as betweenness to identify which individuals were most central to the planning and coordination of the attacks. Krebs has also observed that the network that planned September 11 attempted to hide by making their communications sparse. While these articles provide interesting information on the history of a hidden group, our research uses properties of hidden groups to discover their structure before a planned attack can occur. There is also work being done in analyzing the theory of networked groups, and how technology is enabling them to become more flexible and challenging to deal with. The hierarchical structure of terrorist groups in the past is giving way to more effective and less organized network structure [35]. Of course, the first step to understanding decentralized groups is to discover them. What follows are some strategies to solve this problem. 2.2. Methodology A temporally hidden group is a different kind of group from the normally functioning social groups in the society that engage in “random” communications. We define a tempo-
86
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
Figure 1. Cyclic representation of the communication.
rally hidden group, or in this section labeled a hidden group, as some subset of the actors who are planning or coordinating some activity over time; the hidden group members may also be engaging in other non-planning related communications. The hidden group may be malicious (for example some kind of terrorist group planning a terror attack) or benign (for example a foursome planning their Sunday afternoon golf game). So in this sense, a hidden group is not assumed to be intentionally hiding, but the group activity is initially unknown and masked by the background communications. The hidden group is attempting to coordinate some activity, using the communication network to facilitate the communications between its members. Our task now is to (1) discover specific properties that can be used to find hidden groups; and (2) construct efficient algorithms that utilize those properties. The next steps such as formulation of empirically precise models and further investigation of the properties of hidden groups is beyond the scope of this methodology. Whether intentional or not, in a normal society, communications will, in general, camouflage the planning related activity of the hidden group. This could occur in any public forum such as a newsgroup or chatrooms, or in private communications such as email messages or phone conversations. However, the planning related activity is exactly the Achilles heel that we will exploit to discover the hidden group: on account of the planning activity, the hidden group members need to stay “connected” with each other during each “communication cycle.” To illustrate the general idea, consider the following time evolution of a communication graph for a hypothetical society; here, communications among the hidden group are in bold, and each communication cycle graph represents the communications that took place during an entire time interval. We assume that information must be communicated among all hidden group members during one communication cycle (see Figure 1). Note that the hidden group is connected in each of the communication cycle figures above. We interpret this requirement that the communication subgraph for the hidden group be connected as the requirement that during a single communication cycle, information must have passed (directly or indirectly) from some hidden group member to all the others. If the hidden group subgraph is disconnected, then there is no way that information could have been passed from a member in one of the components to a member in the other, which makes the planning impossible during that cycle. The information need not pass from one hidden group member to every other directly: A message could be passed from A to C via B, where A, B, C are all hidden group members. Strictly speaking, A and C are hidden group members, however B need not be one. We will address this issue more formally in the next section. A hidden group may try to hide its existence by changing its connectivity pattern, or by throwing in “random” communications to non-hidden group members. For example, at some times the hidden group may
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
87
Figure 2. Types of connectivity.
be connected by a tree, and at other times by a cycle. None of these disguises changes the fact that the hidden group is connected, a property we will exploit in our algorithms. We make the assumption here that the hidden group remains static over the time period when communications are collected. The algorithms described here would still be useful, however, as long as a significant subset of the group remains the same. The algorithms would likely not detect members that joined or left the group, but would discover a “core” group of members. 2.2.1. Trusting vs. Non-Trusting Hidden Groups Hidden group members may have to pass information to each other indirectly. Suppose that A needs to communicate with B. They may use a number of third parties to do this: A → C1 → · · · → Ck → B. Trusting hidden groups are distinguished from nontrusting ones by who the third parties Ci may be. In a trusting (or non-secretive) hidden group, the third parties used in a communication may be any actor in the society; thus, the hidden group members ( A, B) trust some third-party couriers to deliver a message for them. In doing so, the hidden group is taking the risk that the non-hidden group members Ci have access to the information. For a malicious hidden group, such as a terrorist group, this could be too large a risk, and so we expect that malicious hidden groups will tend to be non-trusting (or secretive). In a non-trusting (secretive) hidden group, all the third parties used to deliver a communication must themselves be members of the hidden group, i.e., no one else is trusted. The more malicious a hidden group is, the more likely it is to be non-trusting. Hidden groups that are non-trusting (vs. trusting) need to maintain a higher level of connectivity. We define three notions of connectivity as illustrated by the shaded groups in Figure 2. A group is internally connected if a message may be passed between any two group members without the use of outside third parties. In the terminology of Graph Theory, this means that the subgraph induced by the group is connected. A group is externally connected if a message may be passed between any two group members, perhaps with the use of outside third parties. In Graph Theory terminology, this means that the group is a subset of a connected set of vertices in the communication graph. For example, in Figure 2 (2) above, a message from A to B would have to use the outside third party C. A group is disconnected if it is not externally connected. The following observations are the basis for our algorithms for detecting hidden groups. (i) Trusting hidden groups are externally connected in every communication cycle.
88
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
Figure 3. Internally persistent, externally persistent and non-persistent groups. The communication graph during 4 communication cycles is shown. Three groups are highlighted, I P, E P, D. One can easily verify that I P is internally persistent during these 4 communication cycles, and so is a candidate non-trusting hidden group. E P is only internally persistent only for time periods 1 and 2. If we only observed data during this time period, then E P would also be a candidate non-trusting hidden group. However, E P is only externally persistent for all the communication cycles, and hence can only be a candidate for a trusting hidden group. D becomes disconnected during communication cycle 4, and hence is not a candidate hidden group.
(ii) Non-trusting hidden groups are internally connected in every communication cycle. We can now state the idea behind our algorithm for detecting a hidden group: a group of actors is persistent over communication cycles 1, . . . , T if it is connected in each of the communication graphs corresponding to each cycle. The two variations of the connectivity notion, internal or external, depend on whether we are looking for a nontrusting or trusting hidden group. Our algorithm is intended to discover potential hidden groups by detecting groups that are persistent over a long time period. An example is illustrated in Figure 3. A hidden group can be hidden from view if, by chance, there are many other persistent subgroups in the society. In fact, it is likely that there will be many persistent subgroups in the society during any given short time period. However, these groups will be short-lived on account of the randomness of the society communication graph. Thus we expect our algorithm performance to improve as the observation period increases. 2.2.2. Detecting The Hidden Group Our ability to detect the hidden group hinges on two things. First, we need an efficient algorithm for identifying maximally persistent components over a time period . Second, we need to ensure, with high probability, that over this time period there are no persistent components that arise, by chance, due to the background societal communications. We will construct algorithms to efficiently identify maximal components that are persistent over a time period . Given a model for the random background communications, we can determine (through simulation) how long a time period a group of a particular size must be persistent in order to ensure that, with high probability, this persistent component did not arise by chance, due to background communications.
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
(a) Externally persistent components 1: Ext_Persistent({G t }tT=1 , V )
2: //Input: Graphs {G t = (E t , V )}tT=1 . 3: //Output: A partition P = {V j } of V . 4: Use DFS to get the connected components Ct of every G t ; 5: Set P1 = C1 and Pt = {} for t > 1; 6: for t = 2 to T do 7: for Every set A ∈ Pt −1 do 8: Obtain a partition P of A by intersecting
A with every set in Ct ;
89
(b) Internally persistent components 1: Int_Persistent({G t }tT=1 , V ) 2: //Input: Graphs {G t = (E t , V )}tT=1 . 3: //Output: A partition P = {V j } of V . K = Ext_Persistent({G }T , V ) 4: {Vi }i=1 t t =1 5: if K = 1, then 6: P = {V1 }; 7: else K Int_Persistent({G (U )}T , V );| 8: P = ∪k=1 t k t =1 k 9: end if 10: return P;
9: Place P into Pt ; 10: end for 11: end for 12: return PT ;
Figure 4. Algorithms for detecting persistent components.
2.3. Algorithms Select to be the smallest time-interval during which it is expected that information is passed among all group members. Index the communication cycles (which are consecutive time periods of duration ) by t = 1, 2, . . . , T . Thus, the duration over which data is collected is = · T . The communication data is represented by a series of communication graphs, G t for t = 1, 2, . . . , T . The vertex set for each communication graph is the set V of all actors. The input to the algorithm is the collection of communication graphs {G t } with a common set of actors V . The algorithm splits V into persistent components, i.e., components that are connected in every G t . The notion of connected could be either external or internal, and so we develop two algorithms, Ext_Persistent and Int_Persistent. Each algorithm develops the partition in an iterative way. If we have only one communication graph G 1 , then both the externally and internally persistent components are simply the connected components of G 1 . Suppose now that we have one more graph, G 2 . The key observation is that two vertices, i, j are in the same external component if and only if they are connected in both G 1 and G 2 , i.e., they are in the same component in both G 1 and G 2 . Thus, the externally persistent components for the pair G 1 , G 2 are exactly the intersections of the connected components in G 1 with those in G 2 . This argument clearly generalizes to more than two graphs, and relies on the fundamental property that any subset of an externally connected set is also externally connected. Unfortunately, the same property does not hold for internal connectivity, i.e, a subset of an internally connected set is not guaranteed to be internally connected. However, a minor modification of the externally connected algorithm where one goes back and checks any sets that get decomposed leads to the algorithm for detecting internally persistent components. (Figure 4(b)). The formal details of the algorithms are given in [5].
90
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
2.3.1. Analysis The correctness and computational complexity results of the algorithms given in Figure 4 are stated here. For full detail see [5]. We say that a set A is a maximal persistent set (internal or external) if it is persistent, and any other persistent set that contains at least one element of A is a subset of A. Clearly, any two maximal persistent sets must be disjoint, which also follows from the following lemma. Lemma 1 If A and B are non-disjoint externally (resp. internally) persistent sets then A ∪ B is also externally (resp. internally) persistent. Theorem 1 (Correctness of Ext_Persistent) Algorithm Ext_Persistent correctly partitions the vertex set V into maximal externally connected components for the input graphs {G t }tT=1 . the number of edges in G t , and let E denote the total number of edges Let E t denote in the input, E = tT=1 E t . The size of the input is then given by E + V · T . Theorem 2 (Complexity of Ext_Persistent) The computational complexity of Algorithm Ext_Persistent is in O(E + V T ) (linear in the input size). Theorem 3 (Correctness of Int_Persistent) Algorithm Int_Persistent correctly partitions the vertex set V into maximal internally connected components. Theorem 4 (Complexity of Int_Persistent) The computational complexity of Algorithm Int_Persistent is in O(V · E + V 2 · T ). 2.3.2. Statistical Significance of Persistent Components Let h be the size of the hidden group we wish to detect. Suppose that we find a persistent component of size ≥ h over T communication cycles. A natural question is to ask how sure we can be that this is really a hidden group versus a persistent component that happened to arise by chance due to the random background communications. Let X (t) denote the size of the largest persistent component over the communication cycles 1, . . . , t that arises due to normal societal communications. X (t) is a random variable with some probability distribution, since the communication graph of the society follows a random process. Given a confidence threshold, , we define the detection time τ (h) as the time at which, with probability 1−, the largest persistent component arising by chance in the background is smaller than h, i.e., τ (h) = min{t P X (t) < h ≥ 1 − }.
(1)
Then, if after τ (h) cycles we observe a persistent component of size ≥ h, we can claim, with a confidence 1 − , that this did not arise due to the normal functioning of the society, and hence must contain a hidden group. τ (h) indicates how long we have to wait in order to detect hidden groups of size h. Another useful function is h (t), which is an upper bound for X (t), with high probability (1 − ), i.e., h (t) = min{h P X (t) < h ≥ 1 − }.
(2)
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
91
If, after a given time t, we observe a persistent component with size ≥ h (t), then with confidence at least 1 − , we can claim it to contain a hidden group. h (t) indicates what sizes hidden group we can detect with only t cycles of observation. The previous approaches to detecting a hidden group assume that we know h or fix a time t at which to make a determination. By slightly modifying the definition of h (t), we can get an even stronger hypothesis test for a hidden group. For any fixed δ > 0, define H (t) = min{h P X (t) < h ≥ 1 −
δ }. t 1+δ
(3)
Then one can show that if X (t) ≥ H (t) at any time, we have a hidden group with confidence 1 − . Note that the computation of τ (h) and h (t) constitute a pre-processing of the society’s communication dynamics. This can be done either from a model (such as the random graph models we have described) or from the true, observed communications over some time period. More importantly, this can be done off-line. For a given realization of the society dynamics, let T (h) = min{t X (t) < h}. Some useful heuristics that aid in the computation of τ (h) and h (t) by simulation can be obtained by assuming that T (h) and X (t) are approximately normally distributed, in which case, Confidence level τ (h) h (t) 50% E T√(h) E X√(t) 84.13% E T (h) + √V ar T (h) E X (t) + √V ar X (t) 97.72% E T (h) + 2 V ar T (h) E X (t) + 2 V ar X (t)
(4)
2.4. Random Graphs as Communication Models Social and information communication networks, e.g., the Internet and WWW, are usually modeled by graphs [33] [9] [10] [36], where the actors of the networks (people, IP-addresses, etc.) are represented by the vertices of the graph, and the connections between the actors are represented by the graph edges. Since we have no a priori knowledge regarding who communicates with whom, i.e., how the edges are distributed, it is appropriate to model the communications using a random graph. In this paper, we study hidden group detection in the context of two random graph models for the communication network: uniform random graphs and random graphs with embedded groups. In describing these models, we will use standard graph theory terminology [40], and its extension to hypergraphs [6]. In a hypergraph, the concept of an edge is generalized to a hyperedge which may join more than two vertices. In addition to these two models, there are other models of random networks, such as the small world model and the preferential attachment model [1]. However, in this work we limited our experiments to the following models, which are also illustrated in Figure 5. Random Model A simple communication model is one where communications happen at random uniformly among all pairs of actors. Such a communication model can be represented by the random graph model developed and extensively studied by Erd˝os and Rényi, [11,12,13,7]. In this model, the graph is generated by a random process in which an edge between every pair of vertices is generated independently with a given probability p. The probability space of graphs generated by such a random process is denoted G(n, p), or sometimes are called the Bernoulli Graphs. We will use the G(n, p) notation throughout this paper.
92
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
Random Model
Group Model
Figure 5. Two random graph models.
Group Model The G(n, p) random graph model may not be a suitable model for large communication networks. Actors tend to communicate more often with certain actors and less frequently with others. In a more realistic model, actors will belong to one or more social groups where communication among group members is more frequent than communication among actors that do not belong to the same group. This leads us to the hypergraph model of the communication network, in which the actors associate themselves into groups. In this paper, we assume that each group is static and contains m actors. While this is a simplification, it serves to illustrate all the essential ideas and results without undue complication. A group of actors is represented by a hyperedge in the graph, and an actor may belong to zero or more hyperedges. The set of all hyperedges represents the structure of the communication network. Since groups tend to be small, it is appropriate to model the communications within a group as a G(m, pg ), where pg is the probability within the group. We also allow communication between two actors that do not share a group in common; we denote such communications as external. The probability of an external communication is pe ; we further assume that pe pg because intra-group communications are much more likely than extra-group communications. Connectivity of Random Graphs The key idea of our algorithms is based on the following observation. For any subset of actors in a random model network, it is very unlikely that this subset is connected during a “long” consecutive period of time cycles, while a hidden group must stay connected (for its operations) as long as it functions as a group. Thus, we summarize here some results from random graph theory regarding how the connectivity of a G(n, p) depends on n and p, [11,12,13,7]. These results are mostly asymptotic in nature (with respect to n), however, we use them as a guide that remains accurate even for moderately sized n. Given a graph G = {V, E}, a subset S ⊆ V of the vertices is connected if there exists a path in G between every pair of vertices in S. G can be partitioned into disjoint connected components such that every pair of vertices from the same connected component is connected and every pair of vertices in different connected components is not connected. The size of a component is the number of its vertices; the size of the largest connected component is denoted by L(G). The remarkable discovery by Erd˝os and Rényi, usually termed The Double Jump, deals with the size of the largest component, and essentially states that L(G) goes through two phase transitions as p increases beyond a critical threshold value. All the results hold asymptotically, with high probability, i.e., with probability tending to 1 when n → ∞:
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
p = nc p = lnnn + nx , x > 0 ⎧ ⎪ ⎨ O(ln n) 0 < c < 1 −x L(G(n, p)) = O(n 2/3 ) c = 1 L(G(n, p)) = n with prob. e−e ⎪ ⎩ β(c)n c > 1, β(c) < 1
93
(5)
Note that when x → ∞, the graph is connected with probability 1. Since our approach is based on the tenet that a hidden group will display a higher level of connectivity than the background communications, we will only be able to detect the hidden group if the background is not maximally connected, i.e., if L(G) = n. Thus we expect our ability to detect the hidden group to undergo a phase transition exactly when the background connectivity undergoes a phase transition. For p = constant or p = d ln n/n with d > 1, the graph is asymptotically connected which will make it hard to detect the hidden group. However, when p = constant, connectivity is exponentially more probable than when p = d ln n/n, which will have implications on our algorithms. 2.5. Experiments and Results In these tests, we simulate societies of sizes n = 1000 and 2000. The results for both the random background communication model and the group background communication model are presented in parallel. For each model, multiple time series of graphs are generated for communication cycles t = 1, 2, . . . , T , where T = 200. Experiments were run on multiple time series (between five and thirty), and averaged in order to obtain more statistically reliable results. In order to estimate h (t), we estimate E X (t) by taking the sample average of the largest persistent component over communication cycles 1, . . . , t. Given h, the time at which the plot of E X (t) drops below h indicates the time at which we can identify a hidden group of size ≥ h. We first describe the experiments with the random model G(n, p). The presence of persistently connected components depends on the connectivity of the communication graphs over periods 1, 2, . . . , T . When the societal communication graph is connected for almost all cycles, we expect the society to generate many large persistent components. By the results of Erd˝os and Rényi described in Section 2.4, a phase transition from short-lived to long-lived persistent components will occur at p = 1/n and p = ln n/n. Accordingly, we present the results of the simulations with p = 1/n, p = c ln n/n for c = 0.9, 1.0, 1.1, and p = 1/10 for n = 1000. The rate of decrease of E X (t) is shown in Figure 6. For p = 1/n, we expect exponential or super-exponential decay in E X (t) (Figure 6, thin dashed line). This is expected because L(G) is at most a fraction of n. An abrupt phase transition occurs at p = ln n/n (Figure 6 dot-dashed line). At this point the detection time begins to become large. For constant p (where p does not depend on n, in this case 1/10), the graph is connected with probability tending to 1, and it becomes essentially impossible to detect a hidden group using our approach without any additional information (Figure 6 thick dashed line). This will occur for any choice of a constant as n becomes large. That is, for any constant p > 0, there is an integer N such that if n > N then G(n, p) is connected with high probability, tending to 1. The parameters of the experiments with the group model are similar to that of the G(n, p)-model. We pick the group size m to be equal to 20. Each group is selected independently and uniformly from the entire set of actors; the groups may overlap; and each actor may be a member of zero or more groups. If two members are in the same
94
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
Largest Persistent Internally Connected Component, G(1000,p)
Largest Component Size as Fraction of n
1 0.9 0.8 0.7 0.6 0.5 0.4
p=1/n p = 0.9 ln n / n p = 1.0 ln n / n p = 1.1 ln n / n p = 0.1
0.3 0.2 0.1 0 0
50
100
150
200
Time
Largest Persistent Internally Connected Component, G(2000,p)
Largest Component Size as Fraction of n
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3
p=1/n p = 0.9 ln n / n p = 1.0 ln n / n p = 1.1 ln n / n p = 0.1
0.2 0.1 0 0
50
100
150
200
Time
Figure 6. The largest internally persistent component E X (t) for the G(n, p) model with
n = 1000, 2000. The five lines represent p = 1/n, p = c ln n/n for c = 0.9, 1.0, 1.1, and p = 1/10. Note the transition at p = ln n/n. This transition becomes more apparent at n = 2000. When p is a constant (i.e. does not depend on n; here we used 1/10), the graph is almost always connected. The results were averaged over a number of runs. The sharp jumps indicate where the largest component quickly jumped from about 0.9n to zero in different runs.
group together, the probability that they communicate during a cycle is pg , otherwise the probability equals pe . It is intuitive that pg is significantly bigger than pe ; we picked pe = 1/n, so each actor has about one external communication per time cycle. The values of pg that we use for the experiments are chosen to achieve a certain average number of communications per actor, thus the effect of a change in the structure of the communication graph may be investigated while keeping the average density of communications constant. The average number of communications per actor (the degree of the actor in the communication graph) is set to six in the experiments. The results do change qualitatively for different choices of average degree. The number of groups g is chosen from {50, 100, 200}. These cases are compared to the G(n, p) structure with an average of six communications per actor. For the selected values of g, each actor is, on average, in 1, 2 and 4 groups, respectively. When g is 50, an actor is, on average, in approximately one group, and the overlaps of groups are small. However, when g is 200, each actor,
J. Baumes et al. / Discovering Hidden Groups in Communication Networks Largest Persistent Internally Connected Component, deg
av
=6
Uniform G(n,p) 50 Groups Size 20 100 Groups Size 20 200 Groups Size 20
1
Largest Component Size as Fraction of n
95
0.8
0.6
0.4
0.2
0 10
20
30
40
50
60
70
80
90
100
Time
g (# of groups) T (1)
Group Model 50 100 200 > 100 63 36
Random Model G(n, n6 ) 32
Figure 7. Times of hidden group discovery for various amounts of group structure; each group is independently generated at random and has 20 actors. In all cases, n = 1000, degav = 6, and the group size m = 20. Note how, as the number of groups becomes large, the behavior tends toward the G(n, p) case.
on average, is in about 4 groups, so there is a significant amount of overlap between the groups. The goal of our experiments is to see the impact of g on finding hidden groups. Note that as g increases, any given pair of actors tends to belong to at least one group together, so the communication graph tends toward a G(n, pg ) graph. We give a detailed comparison between the society with structure (group model) and the one without (random model) in Figure 7. The table shows T (1), which is the time after which the size of the largest internally persistent component has dropped to 1. This is the time at which any hidden group would be noticed, since the group would persist beyond the time expected in our model. We have also run similar experiments for detecting trusting groups. The results are shown in Figure 8. As the table shows, for the corresponding non-trusting communication model, the trusting group is much harder to detect. 3. Discovering Spatial Correlation 3.1. Literature Review While an informal definition of the goal of clustering algorithms is straightforward, difficulty arises when formalizing this goal. There are two main approaches to clustering: partitioning and general clustering.
96
J. Baumes et al. / Discovering Hidden Groups in Communication Networks Largest Persistent Connected Component, deg
av
Largest Persistent Connected Component, degav = 6
0.8
0.6
0.4
0.2
0
Internally Connected Externally Connected
1
Largest Component Size as Fraction of n
Largest Component Size as Fraction of n
=2
Internally Connected Externally Connected
1
0.8
0.6
0.4
0.2
0
5
10
15
20
25
30
Time
degav T (1) for trusting groups 2 28 6 > 100
10
20
30
40
50
60
70
80
90
100
Time
T (1) for non-trusting groups 2 32
Figure 8. Times of hidden group discovery for non-trusting (internally connected) hidden groups and trusting (externally connected) hidden groups. In all cases the communication graphs are G(n, p) with n = 1000.
Partitioning, or hierarchical clustering, is the traditional method of performing clustering. In some circles, clustering and partitioning are synonymous. For example, Kannan, Vempala, and Vetta define clustering as “partitioning into dissimilar groups of similar items” [23]. However, the partitioning approach forces every cluster to be either entirely contained within or entirely disjoint from every other cluster. Partitioning algorithms are useful when the set of objects needs to be broken down into disjoint categories. These categories simplify the network and may be treated as separate entities. Partitioning is used in the fields of VLSI design, finite element methods, and transportation [24]. Many partitioning algorithms attempt to minimize the number of connections between clusters, also called the cut size of the partition [27] [26] [21] [24] [25]. The ρseparator metric attempts to balance the sizes of the clusters, while also minimizing the cut size [15]. The betweenness metric is used to find a small cut by removing edges that are likely to split the network into components [17,19]. In addition to trying to minimize the cut size, some algorithms attempt to maximize the quality of each cluster. Two metrics used in partitioning which define cluster quality are expansion and conductance [16,23]. A final metric relates to how well the members of the same cluster are related to the values in eigenvectors of the adjacency matrix of the network [8]. Groups in social networks do not conform to this partitioning approach. For example, in a social network, an individual may belong to numerous groups (e.g., occupational, religious, political, activity). A general clustering algorithm may put the individual into all these clusters, while a partitioning algorithm will only place the individual into one cluster. Classifying an individual as belonging to a single cluster or social group will often miss the full picture of the societal structure. As opposed to partitioning, general clustering allows individuals to belong to many groups at once. General clustering algorithms determine the zero, one or more groups that each actor belongs to, without enforcing a partition structure on the clusters. This complex structure may more directly correspond to real-world clusters. However, permitting overlapping groups is a more complex problem, since each cluster may not be treated as a separate entity. See Figure 9 for a comparison of partitioning and general clustering.
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
(a)
97
(b)
Figure 9. A comparison of a partitioning (a) and a general clustering (b) of the same network.
When clustering a network, there needs to be a definition of what constitutes a “good” cluster. In some sense, members of a cluster need to be “close” to each other, and “far” from the other objects in the network. There are many ways to define the criterion for a valid cluster. The general clustering problem has been less widely studied than the partitioning problem, however there are some algorithms that exist for discovering a general clustering of a network. Some algorithms of this type are well suited for web networks [28,18,31]. These algorithms all attempt to find clusters by optimizing a metric referred to as bicliqueness. Though often used for partitioning, eigenvector correlation may also be used to discover overlapping clusters [38]. Local optimality is a generic technique which can optimize many of the previously mentioned metrics, even metrics originally developed for partitioning. These algorithms have been applied to social networks [2,3]. We present these algorithms in more detail in the following sections. 3.2. Methodology Let G = (V, E) be a graph whose nodes represent individuals, web pages, etc., and whose edges represent communications, links, etc. The graph may be directed or undirected. We present the definitions for directed graphs, the undirected case being similar. A graph cluster C is a set of vertices which can be viewed as a binary vector of length |V | that indicates which nodes are members of C. The set of all graph clusters, C, is the power set of V . A weight function, or metric is a function W C → R that assigns a weight to a graph cluster. Associated to cluster C, we define three edge sets: E(C), the edges induced by C; E(C, C), the edges in E from C to its complement; E(C, C), the edges in E to C from its complement. Let E out (C) = E(C, C) + E(C, C). We define the internal and external edge intensities, pin (C) =
E(C) , |C| · (|C| − 1)
pex (C) =
E out (C) 2|C| · (n − |C|)
(6)
( pex = 1 when |C| = |V |). We will consider three weight functions: the internal edgeprobability W p ; the edge ratio We ; and, the intensity ratio Wi , W p (C) = pin (C),
We (C) =
E(C) , E(C) + E out (C)
Wi (C) =
pin (C) . pin (C) + pex (C)
(7)
98
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
These metrics are measures of how intense the communication within the cluster is, relative to that outside the cluster; they can be efficiently updated locally, i.e. the metric may be updated by knowing only the connectivity of the one node that is added or removed (which improves the efficiency of the algorithms). A set-difference function δ is a metric that measures the difference between two clusters C1 , C2 . Two useful set-difference functions are the Hamming or edit distance δh , and the percentage non-overlap δ p : δh (C1 , C2 ) = |(C1 ∩ C2 ) ∪ (C1 ∩ C2 )|,
δ p (C1 , C2 ) = 1 −
|C1 ∩ C2 | . |C1 ∪ C2 |
(8)
The -neighborhood of a cluster Bδ (C) is the set of clusters that are within of C with respect to δ, i.e., Bδ (C) = {C |δ(C, C ) ≤ }. For weight function W , we say that a cluster C ∗ is -locally optimal if W (C ∗ ) ≥ W (C) for all C ∈ Bδ (C ∗ ). We are now ready to formally state our abstraction of the problem of finding overlapping communities in a communication network. The input is a graph G, the communication graph, along with the functions W , δ and . The output is a set of clusters O ⊆ C such that C ∈ O iff C is -locally optimal. While our heuristic approaches are easily adapted to different weight and set-difference functions, we will focus on the choices W = We , δ = δh and = 1, referring to the output clusters as locally optimal. As stated, the problem is NP-hard. In fact, the restriction to δ = δh and = |V | asks to find all the globally optimal clusters according to an arbitrary weight function W , which is well known to be NP-hard. Thus, we present heuristic, efficient (low-order polynomial time) algorithms that output candidate (overlapping) clusters, and then evaluate the quality of the output.
3.3. Algorithms 3.3.1. k-Neighborhood (k − N) k − N is a trivial algorithm that yields overlapping clusters. The clusters are simply the kneighborhoods of a randomly selected set S of cluster centers. The inputs to this algorithm are k and |S|.
3.3.2. Rank Removal (RaRe) Algorithm RaRe is based on the assumption that within a communication network, there is a subset of “important” or high-ranking nodes, which do a significant amount of communication. RaRe attempts to identify these nodes and remove them from the graph, in order to disconnect the graph into smaller connected components. The removed node(s) are added to a set R. This process is repeated, until the sizes of the resulting connected components are within a specified range. These connected components can be considered the core of each cluster. Next, the vertices in R are considered for addition into one or more of these cores. If a vertex from R is added to more than one cluster, then these clusters now overlap. Note, however, that the cores of each cluster are disjoint, and only communicate with each other through vertices in R. “Important” or high-ranking nodes are determined by a ranking function φ. These are the nodes which are removed at each iteration. We wish to remove nodes that will result in disconnecting the graph as much as possible. One choice is to remove vertices with high degree, corresponding to the choice φd (v) = deg(v). Another approach that we have found to be experimentally better is to rank nodes according to their Page RankTM , φ p (v) [34]. The Page RankTM of a node is defined implicitly as the solution to the following equation, φ p (v) = c
φ p (u) (1 − c) + − (v) deg n u,v
(9)
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
99
Table 1. User specified inputs for Algorithm RaRe. Input
Description
W
Weight function.
φ min, max
Ranking function. Minimum and maximum core sizes.
t
Number of high-ranking vertices to remove.
where n is the number of nodes in the graph, deg − (v) is the out degree of vertex v, and c is a decay factor between 0 and 1. An iterative algorithm to compute φ p (v) for all the nodes converges rapidly to the correct value. Once we have obtained the cores, we must add the vertices in R back into the cores to build up the clusters. Intuitively, a vertex v ∈ R should be part of any cluster to which it is immediately adjacent, as it would have been part of the core if it were not removed at some step. Also, if we do not take this approach, we run the risk of v not being added to any cluster, which seems counterintuitive, as v was deemed “important” by the fact that it was at one time added to R. This is therefore the approach which we take. We also add vertices in R to any cluster for which doing so increases the metric W . The algorithm is summarized in Figure 10, and all the user specified inputs are summarized in Table 1. It is important to note that the initial procedure of removing vertices, though not explicitly attempting to optimize any single metric, does produce somewhat intuitive clusters. The cores that result are mutually disjoint and non-adjacent. Consider a connected component C at iteration i. If C has more vertices than our maximum desired core size max, we remove a set Ri of vertices, where |Ri | = t. If the removal of Ri results in disconnecting C into two or more connected components C1 , C2 ...Ck , we have decreased the diameter of C1 , C2 ...Ck with respect to C, resulting in more compact connected components. If the removal of Ri does not disconnect the graph, we simply repeat the procedure on the remaining graph until it either becomes disconnected or its size is less than max. As an added performance boost, the ranks may be computed initially, but not recomputed after each iteration. The idea is that if the set R is being removed, the rank of a vertex v in G will be close to the rank of v in G − R .
3.3.3. The Link Aggregate Algorithm (LA) The IS algorithm performs well at discovering communities given a good initial guess, for example when its initial “guesses” are the outputs of another clustering algorithm such as RaRe as opposed to random edges in the communication network. We discuss a different, efficient initialization algorithm here. RaRe begins by ranking all nodes according to some criterion, such as Page RankTM [34]. Highly ranked nodes are then removed in groups until small connected components are formed (called the cluster cores). These cores are then expanded by adding each removed node to any cluster whose density is improved by adding it. While this approach was successful in discovering clusters, its main disadvantage was its inefficiency. This was due in part to the fact that the ranks and connected components need to be recomputed each time a portion of the nodes are removed. The runtime of RaRe is significantly improved when the ranks are computed only once. For the remainder of this paper, RaRe refers to the Rank Removal algorithm with this improvement, unless otherwise stated. Since the clusters are to be refined by IS, the seed algorithm needs only to find approximate clusters. The IS algorithm will “clean up” the clusters. With this in mind, the new seed algorithm Link Aggregate LA focuses on efficiency, while still capturing good initial clusters. The pseudocode is given in Figure 10. The nodes are ordered according to some criterion, for example
100
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
decreasing Page RankTM , and then processed sequentially according to this ordering. A node is added to any cluster if adding it improves the cluster density. If the node is not added to any cluster, it creates a new cluster. Note, every node is in at least one cluster. Clusters that are too small to be relevant to the particular application can now be dropped. The runtime may be bounded in terms of the number of output clusters C as follows Theorem 5 The runtime of LA is O(|C||E| + |V |). Proof: Let Ci be the set of clusters just before the ith iteration of the loop. The time it takes for the ith iteration is O(|Ci |deg(v i )), where deg(v i ) is the number of edges adjacent to v i . Each edge adjacent to v i must be put into two classes for every cluster in Ci : either the other endpoint of the edge is in the cluster or outside it. With this information, the density of the cluster with v i added may be computed quickly (O(1)) and compared to the current density. If deg(v i ) = 0, the iteration takes O(1) time. Therefore the total runtime is asymptotically on the order of
|Ci |deg(v i ) +
|V |
1≤
|V |
|Ci |deg(v i ) +
|V |
1
(10)
|C|deg(v i ) + |V | = 2|C||E| + |V | = O(|C||E| + |V |).
(11)
deg(v i )>0
≤
deg(v i )=0
i=1
i=1
i=1
Q.E.D
3.3.4. Iterative Scan (IS) Algorithm IS explicitly constructs a clusters that is a local maximum w.r.t. a density metric by starting at a “seed” candidate cluster and updating it by adding or deleting one vertex at a time as long as the metric strictly improves. The algorithm stops when no further improvement can be obtained with a single change. This algorithm is given in pseudo-code format in Figure 10. Different local maxima can be obtained by restarting the algorithm at a different seed, or changing the order in which vertices are examined for cluster updating. The algorithm terminates if the addition to C or deletion from C of a single vertex does not increase the weight. During the course of the algorithm, the cluster C follows some sequence, C1 , C2 , . . ., with the property that W (C1 ) < W (C2 ) < · · · , where all the inequalities are strict. Since the number of possible clusters is finite, the algorithm must terminate when started on any seed, and the cluster output will a locally optimal cluster. The cluster size may be enforced heuristically by incorporating this criterion into the weight function. This is done by adding a penalty for clusters with size outside the desired range. Such an approach will not impose hard boundaries on the cluster size. If the desired range is Cmin , Cmax , then a simple penalty function Pen(C), that linearly penalizes deviations from this range is Cmin − |C| |C| − Cmax Pen(C) = max 0, h 1 · , (12) , h2 · Cmin − 1 |V | − Cmax where Cmin , Cmax , h 1 , h 2 are user specified parameters. All the user specified inputs are summarized in Table 2. We emphasize that algorithm IS can be used to improve any seed cluster to a locally optimal one. Instead of building clusters from random edges as a starting point, we can refine clusters, that are output by some other algorithm – these input clusters might be good “starting points”, but they may not be locally optimal. IS then refines them to a set of locally optimal clusters. The original process for IS consisted of iterating through the entire list of nodes over and over until the cluster density cannot be improved. In order to decrease the runtime of IS, we
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
101
Table 2. User specified inputs to Algorithm IS. Parameter
Description
W
Weight function.
δ
Set-difference function (δ = δh in our implementation). Size of set neighborhood ( = 1 in our implementation).
max_ f ail
Number of unsuccessful restarts to satisfy stopping condition.
Cmin , Cmax h1, h2
Desired range for cluster size. Penalty for a cluster of size 1 and |V |.
Table 3. Algorithm performance on real-world graphs. The first entry in each cell is the average value of Wad . The two entries in parentheses are the average number of clusters found and the average number of nodes per cluster. The fourth entry is the runtime of the algorithm in seconds. The e-mail graph represents emails among the RPI community on a single day (16,355 nodes). The web graph is a network representing the domain www.cs.rpi.edu/∼magdon (701 nodes). In the newsgroup graph, edges represent responses to posts on the alt.conspiracy newsgroup (4,526 nodes). The Fortune 500 graph is the network connecting companies to members of their board of directors (4,262 nodes). Algorithm
E-mail
Web
RaRe → IS LA → IS2
1.96 (234,9); 148 2.94 (19,25); 305
6.10 (5,8); 0.14 5.41 (6,19); 0.24
Algorithm
Newsgroup
Fortune 500
RaRe → IS
12.39 (5,33); 213
2.30 (104,23); 4.8
LA → IS2
17.94 (6,40); 28
2.37 (288,27); 4.4
make the following observation. The only nodes capable of increasing the cluster’s density are the members of the cluster itself (which could be removed) or members of the cluster’s immediate neighborhood, defined by those nodes connected to a node inside the cluster. Thus, rather than visiting each node on every iteration, we may skip over all nodes except for those belonging to one of these two groups. If the neighborhood of a cluster is much smaller than the entire graph, this could significantly improve the runtime of the algorithm. This algorithm provides both a potential decrease and increase in runtime. A decrease occurs when the cluster and its neighborhood are small compared to the number of nodes in the graph. This is the likely case in a sparse graph. In this case, building the neighborhood set N takes a relatively short time compared to the time savings of skipping nodes outside the neighborhood. An increase in runtime may occur when the cluster neighborhood is large. Here, finding the neighborhood is expensive, plus the time savings could be small since few nodes are absent from N. A large cluster in a dense graph could have this property. In this case, placing all nodes in N is preferable. Taking into account the density of the graph, we may construct N in either of the two methods described here, in order to maximize efficiency in all cases. If the graph is dense, all nodes are placed in N, but if the graph is sparse, the algorithm computes N as the neighborhood of the cluster. In the experiments that follow, the behavior of IS for sparse graphs is denoted IS, and the behavior for dense graphs is denoted IS2 .
3.4. Experiments and Results A series of experiments were run in order to compare both the runtime and performance of the new algorithm with its predecessor. In all cases, a seed algorithm was run to obtain initial clusters, then a refinement algorithm was run to obtain the final clusters. The baseline was the seed algorithm
102
J. Baumes et al. / Discovering Hidden Groups in Communication Networks procedure RaRe(G, W ) global R ← ∅; {Hi } are connected components in G; for all Hi do ClusterComponent(Hi ); end for Initial clusters {Ci } are cluster cores; for all v ∈ R do for all Clusters Ci do Add v to cluster Ci if v is adjacent to Ci or W (v ∪ Ci ) > W (Ci ); end for end for
procedure ClusterComponent(H ) if |V (H )| > max then {v i } are t highest rank nodes in H ; R ← R ∪ {v i }; H ← H \ {v i }; {Fi } are connected components in H ; for all Fi do ClusterComponent(Fi ); end for else if min ≤ |V (H )| ≤ max then mark H as a cluster core; end if
procedure LA(G, W ) C ← ∅; Order the vertices v 1 , v 2 , . . . , v |V | ; for i = 1 to |V | do added ← false; for all D j ∈ C do if W (D j ∪ v i ) > W (D j ) then D j ← D j ∪ v i ; added ← true; end if end for if added = false then C ← C ∪ {{v i }}; end if end for return C;
procedure IS(seed,G, W ) C ← seed; w ← W (C); increased ← true; while increased do if G is dense then N ← All nodes adjacent to C; else N ← All nodes in G; end if for all v ∈ N do if v ∈ C then C ← C \ {v}; else C ← C ∪ {v}; end if if W (C ) > W (C) then C ← C; end if end for if W (C) = w then increased ← false; else w ← W (C); end if end while return C;
Figure 10. Algorithms Rank Removal (RaRe), Link Aggregate (LA), and Iterative Scan (IS).
RaRe followed by IS. The proposed improvement consists of the seed algorithm LA followed by IS2 . The algorithms were first run on a series of random graphs with average degrees 5, 10, and 15, where the number of nodes range from 1,000 to 45,000. In this simple model, all pairs of communication are equally likely. All the algorithms take as input a density metric W , and attempt to optimize that metric. In these experiments, the density metric was chosen as Wad , called the average degree, which is
103
J. Baumes et al. / Discovering Hidden Groups in Communication Networks Runtime (s) (5 Edges Per Node)
Runtime (s) (5 Edges Per Node)
500
800 Original RaRe RaRe LA
400
IS IS2
700 600 500
300
400 200
300 200
100
100 0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
Runtime (s) (10 Edges Per Node)
Runtime (s) (10 Edges Per Node)
600
1000 RaRe LA 800
IS IS2
500 400
600
300 400
200 200
0 0
100
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
0 0
0.5
Runtime (s) (15 Edges Per Node)
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
Runtime (s) (15 Edges Per Node)
1500
2500 RaRe LA
IS IS2 2000
1000 1500
1000 500 500
0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
Figure 11. Runtime of the previous algorithm procedures (RaRe and IS) compared to the current procedures (LA and IS2 ) with increasing edge density. On the left is a comparison of the initialization procedures RaRe and LA, where LA improves as the edge density increases. On the right is a comparison of the refinement procedures IS and IS2 . As expected, IS2 results in a decreased runtime for sparse graphs, but its benefits decrease as the number of edges becomes large.
defined for a set of nodes C as Wad (C) =
2|E(C)| , |C|
(13)
where E(C) is the set of edges with both endpoints in C. The runtime for the algorithms is presented in Figure 11. The new algorithm remains quadratic, but both the seed algorithm and the refinement algorithm run-times are improved significantly for sparse graphs. In the upper left plot in Figure 11, the original version of RaRe is also plotted, which recalculates the node ranks a number of times, instead of precomputing the ranks a single time. LA is 35 times faster than the original RaRe algorithm and IS2 is about twice as fast as IS for graphs with five edges per node. The plots on the right demonstrate the tradeoff in
104
J. Baumes et al. / Discovering Hidden Groups in Communication Networks Runtime Per Cluster (s) (5 Edges Per Node)
Runtime Per Cluster (s) (5 Edges Per Node)
0.8
0.1 RaRe LA 0.08
IS IS2
0.7 0.6 0.5
0.06
0.4 0.04
0.3 0.2
0.02
0.1 0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
Figure 12. Runtime per cluster of the previous algorithm (RaRe followed by IS) and the current algorithms (LA followed by IS2 ). These plots show the algorithms are linear for each cluster found.
Mean Density (5 Edges Per Node) 2.5
Mean Density (10 Edges Per Node) 4
RaRe → IS LA → IS2
3.5
2
RaRe → IS LA → IS2
3
1.5
2.5
1
1.5
2
1
0.5
0.5 0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
0 0
0.5
1
1.5 2 2.5 3 Number of Nodes
3.5
4
4.5 4 x 10
Figure 13. Performance (average density) of the algorithm compared to the previous algorithm.
IS2 between the time spent computing the cluster neighborhood and the time saved by not needing to examine every node. It appears that the tradeoff is balanced at about 10 edges per node. For graphs that are more dense, the original IS algorithm runs faster, but for less dense graphs, IS2 is preferable. Figure 12 shows that the quadratic nature of the algorithm is based on the number of clusters found. When the runtime per cluster found is plotted, the resulting curves are linear. Runtime is not the only consideration when examining this new algorithm. It is also important that the quality of the clustering is not hindered by these runtime improvements. Figure 13 compares the average density of the clusters found for both the old and improved algorithms. A higher average density indicates a clustering of higher quality. Especially for sparse graphs, the average density is approximately equal in the old and new algorithms, although the older algorithms do show a slightly higher quality in these random graph cases. Another graph model more relevant to communication networks is the preferential attachment model. This model simulates a network growing in a natural way. Nodes are added one at a time, linking to other nodes in proportion to the degree of the nodes. Therefore, popular nodes get more attention (edges), which is a common phenomenon on the Web and in other real world networks. The resulting graph has many edges concentrated on a few nodes. The algorithms were run on graphs using this model with five links per node, and the number of nodes ranging from 2,000 to 16,000. Figure 14 demonstrates a surprising change in the algorithm RaRe when run on this type of graph. RaRe removes high-ranking nodes, which correspond to the few nodes with very
J. Baumes et al. / Discovering Hidden Groups in Communication Networks Mean Density (5 Edges Per Node)
Runtime (s) (5 Edges Per Node)
4
4
x 10
RaRe → IS 2 LA → IS
3.5
105
RaRe → IS LA → IS2 8
3 2.5
6
2
4
1.5 1
2
0.5 0 0
2000
4000
6000 8000 10000 12000 14000 16000 Number of Nodes
0 0
2000
4000
6000 8000 10000 12000 14000 16000 Number of Nodes
Figure 14. Runtime and performance of the previous algorithm (RaRe followed by IS) and the current algorithm (LA followed by IS2 ) for preferential attachment graphs.
Mean Density (5 Edges Per Node)
Runtime (s) (5 Edges Per Node) 250 LA with PageRank LA with Random Order
2
200
1.5
LA with PageRank LA with Random Order
150
1 100
0.5
50
0 0
2000 4000 6000 8000 10000 12000 14000 16000 18000 Number of Nodes
0 0
2000 4000 6000 8000 10000 12000 14000 16000 18000 Number of Nodes
Figure 15. Runtime and performance of LA with two different ordering types.
large degree. When these nodes are added back into clusters, they tend to be adjacent to most all clusters, and it takes a considerable amount of time to iterate through all edges to determine which connect to a given cluster. The algorithm LA, on the other hand, starts by considering high-ranking nodes before many clusters have formed, saving a large amount of time. The plot on the right of Figure 14 shows that the quality of the clusters are not compromised by using the significantly faster new algorithm LA → IS2 . Figure 15 confirms that constructing the clusters in order of a ranking such as Page RankTM yields better results than a random ordering. LA performs better in terms of both runtime and quality. This is a surprising result since the random ordering is obtained much more quickly than the ranking process. However, the first nodes in a random ordering are not likely to be well connected. This will cause many single-node clusters to be formed in the early stages of LA. When high degree nodes are examined, there are many clusters to check whether adding the node will increase the cluster density. This is time consuming. If the nodes are ranked, the high degree nodes will be examined first, when few clusters have been created. These few clusters are likely to attract many nodes without starting a number of new clusters, resulting in the algorithm completing more quickly. The algorithms were also tested on real-world data. The results are shown in Table 3. For all cases other than the web graph, the new algorithm produced a clustering of higher quality.
106
J. Baumes et al. / Discovering Hidden Groups in Communication Networks
4. Conclusion In this article, we described methods for discovering hidden groups based only on communication data, without the use of communication contents. The algorithms rely on the fact that such groups display correlations in their communication patterns (temporal or spatial). We refer to such groups as hidden because they have not declared themselves as a social entity. Because our algorithms detect hidden groups without analyzing the contents of the messages, they can be viewed as an additional, separate toolkit, different from approaches that are based on interpreting the meaning of the messages. Our algorithms extract structure in the communication network formed by the log of messages; the output groups can further be studied in more detail by an analyst who might take into account the particular form and content of each communication, to get a better overall result. The main advantage is that our algorithms greatly reduce the search space of groups that the analyst will have to look at. The spatial and temporal correlation algorithms target different types of hidden groups. The temporal hidden group algorithms identify those groups which communicate periodically and are engaged in planning an activity. Our algorithms have been shown to be effective at correctly identifying hidden groups artificially embedded into the background of random communications. Experiments show that as the background communications become more dense, it takes longer to discover the hidden group. A phase transition occurs if the background gets too dense, and the hidden group becomes impossible to discover. However, as the hidden group becomes more structured, the group is easier to detect. In particular, if a hidden group is secretive (non-trusting), and communicates key information only among its members, then the group is actually more readily detectable. Our approach to the discovery of spatial correlation in communications data is based on the observation that social groups often overlap. This fact rules out the traditional techniques of partitioning and calls for novel procedures for clustering actors into overlapping groups. The families of clustering algorithms described here are able to discover a wide variety of group types based on the clustering metric provided. The algorithms have been shown to be both efficient and accurate at discovering clusters and retaining meaningful overlap between clusters.
Acknowledgments The research presented here was partially supported by NSF grants 0324947 and 0346341.
References [1] [2]
[3] [4] [5]
[6] [7] [8]
R. Albert and A. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74, 2002. J. Baumes, M. Goldberg, M. Krishnamoorthy, M. Magdon-Ismail, and N. Preston. Finding comminities by clustering a graph into overlapping subgraphs. Proceedings of IADIS Applied Computing, pages 97–104, 2005. J. Baumes, M. Goldberg, and M. Magdon-Ismail. Efficient identification of overlapping communities. Intelligence and Security Informatics (ISI), pages 27–36, 2005. J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace. Discovering hidden groups in communication networks. Intelligence and Security Informatics (ISI), pages 378–389, 2004. J. Baumes, M. Goldberg, M. Magdon-Ismail, and W. Wallace. On hidden groups in communication networks. Technical report, TR 05-15, Computer Science Department, Rensselaer Polytechnic Institute, 2005. C. Berge. Hypergraphs. North-Holland, New York, 1978. Béla Bollobás. Random Graphs, Second Edition. Cambridge University Press, new york edition, 2001. A. Capocci, V. D. P. Servedio, G. Caldarelli, and F. Colaiori. Detecting communities in large networks. Workshop on Algorithms and Models for the Web-Graph (WAW), pages 181–188, 2004.
J. Baumes et al. / Discovering Hidden Groups in Communication Networks [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]
107
K. Carley and M. Prietula, editors. Computational Organization Theory. Lawrence Erlbaum associates, Hillsdale, NJ, 2001. K. Carley and A. Wallace. Computational organization theory: A new perspective. In S. Gass and C. Harris, editors, Encyclopedia of Operations Research and Management Science. Kluwer Academic Publishers, Norwell, MA, 2001. P. Erd˝os and A. Rényi. On random graphs. Publ. Math. Debrecen, 6:290–297, 1959. P. Erd˝os and A. Rényi. On the evolution of random graphs. Maguar Tud. Acad. Mat. Kutató Int. Kozël, 5:17–61, 1960. P. Erd˝os and A. Rényi. On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar., 12:261–267, 1961. Bonnie H. Erickson. Secret societies and social structure. Social Forces, 60:188–211, 1981. G. Even, J. Naor, S. Rao, and B. Schieber. Fast approximate graph partitioning algorithms. Siam J. Computing, 28(6):2187–2214, 1999. G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Clustering methods basen on minimum-cut trees. Technical Report 2002-06, NEC, Princeton, NJ, 2002. L. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40:35–41, 1977. D. Gibson, J. Kleinberg, and P. Raghavan. Inferring web communities from link topology. Proceedings of the 9th ACM Conference on Hypertext and Hypermedia, 1998. M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proc. Natl. Acad. Sci., 99:7821–7826, 2002. Mark Goldberg, Paul Horn, Malik Magdon-Ismail, Jessie Riposo, David Siebecker, William Wallace, and Bulent Yener. Statistical model