Tag: graph mining

# Can an algorithm identify the perpetrators of a bomb attack

On 13th July, 2011, there were simultaneous bomb attacks at different locations in Mumbai.  One day, while I was thinking about it, I suddenly realized that there was an algorithm that could be used to bring the perpetrators to book.

It’s almost a year since the attacks took place, and we thought we’d finally write about our work on the problem (which we’ve shared with many government organizations, including CAIR, though we frankly don’t know if they plan to implement it).

Introduction:

When multiple coordinated attacks take place (like the three bombs that were triggered simultaneously in three locations in Mumbai in 2011), if the attackers had used cell phones to coordinate their attacks, the phone numbers involved can be extracted mathematically from the call records linked to the cell towers in the vicinity of the attacks.

Our calculations indicate that in a city the size of Mumbai and a population of around 20 million people, you would need a minimum of only 3 simultaneous attacks to be able to pinpoint the attackers to within 1 person. If there were only 2 attacks, you would have a much higher uncertainty. The greater the number of coordinated attacks, the easier it is to identify the attackers.

The identification will only be possible if the attackers used their cell phones to coordinate with a central handler, or with each other, or a group of handlers who in turn communicated with each other. It would be possible to support different possible patterns of communication and usage of cell phones and SMS to coordinate between the attackers and confirm the attacks.

History:

A similar method might have already been used in Europe after the Madrid bombings to identify those responsible for the same.
Two years after the attacks, the EU mandated that carriers store some details for 6 months. The information that the carriers need to preserve contains all the details required to triangulate attackers in multiple simultaneous attacks.

Here is some information on the directive from the Wikipedia:

On 15 March 2006 the EU formally adopted Directive 2006/24/EC, on “the retention of data generated or processed in connection with the provision of publicly available electronic communications services or of public communications networks and amending Directive 2002/58/EC.”

The Directive requires Member States to ensure that communications providers must retain, for a period of between 6 months and 2 years, necessary data as specified in the Directive.

 to trace and identify the source of a communication;
 to trace and identify the destination of a communication;
 to identify the date, time and duration of a communication;
 to identify the type of communication;
 to identify the communication device;
 to identify the location of mobile communication equipment.

The data is required to be available to competent national authorities in specific cases, “for the purpose of the investigation, detection and prosecution of serious crime, as defined by each Member State in its national law”.

Information:

The minimum information that would be needed to obtain an effective fix on an attacker is the following:
a) FROM_NUMBER
b) TO_NUMBER
c) TIME_STAMP
d) CELL_TOWER

Indian carriers tend to store the FROM, TO and TIME information in call logs (used by the carriers for billing and for customer service) for SMS messages for 2 days and for phone calls for 30 days. These can be obtained easily from them by a simple request from police.
The location of the cell tower is determined from signaling logs.

Technology:

Messages used to coordinate teams have certain patterns. For example, a possible pattern in an attack is a confirmation – success/failure – to the central handler after an attack.

Each message would have to originate from a cell tower near the site of a blast and in a short time window after the blast and have the same destination.

Out of all the hundreds of millions of messages sent in a city, only some would satisfy all these constraints.
Simple graph analysis can identify these messages, to very high accuracies in a city of 20 million of the size of Mumbai, provided there were 3 or more coordinated attacks.

The algorithm is so simple that an undergraduate student could build it in a few months.

Acknowledgements:

There are many people I have to thank for their help with this study, including old mentors from other research firms in the area who helped me with suggestions for handling temporal queries, and students/interns who helped speed up the study, and my colleague Sumukh who works on graph/tree search himself.