DIMACS Workshop on Applications of Order Theory to Homeland Defense and Computer Security

September 28 - 29, 2004
DIMACS Center, CoRE Building, Rutgers University

Jonathan Farley, Massachusetts Institute of Technology
Anthony A. Harkin, Harvard University, harkin@deas.harvard.edu
Mel Janowitz, DIMACS / Rutgers University, melj@dimacs.rutgers.edu
Stefan Schmidt, Physical Science Laboratory, schmidt@psl.nmsu.edu
DIMACS Working Group on Applications of Order Theory to Homeland Defense and Computer Security participation by invitation only.


Jafar Iman Adibi, Information Sciences Institute, University of Southern California

Title: Link Discovery via a Mutual Information Model: From Graphs to Ordered Lists (with an Illustration Concerning Russian Contract Killing)

Link discovery (LD) is a new challenge in data mining. Its primary concerns are to identify strong links and discover hidden relationships among entities and organizations based on low-level, incomplete and noisy evidence data. To address this challenge, we have developed a hybrid link discovery system called KOJAK that combines state-of-the-art knowledge representation and reasoning (KR&R) technology with statistical clustering and analysis techniques from the area of data mining. In this talk we report on the architecture and technology of its first fully completed module called the KOJAK Group Finder.

The Group Finder's statistical component employs a novel mutual information approach to find hidden groups and group members in large evidence databases. The mutual information model can identify entities strongly connected to a given entity or set of entities and provide an ordered list based on connection strength. Our group finding approach addresses a variety of important link discovery challenges, such as being able to exploit heterogeneous and structurally rich evidence, handling the connectivity curse, and dealing with noise and corruption.

In addition we have extended such approach to find most important nodes in a community-based graph. We will show how to transform a graph to an ordered list by exploiting the graph entropy. At the end I illustrate how to adapt the bootstrap resampling method to measure the uncertainty in LD hypotheses such as an ordered list.

In the second part of my talk I'll introduce and illustrate the application and results of such techniques in a series of synthetic and real world datasets. These datasets are:

  1. EDB developed by IET, Inc., synthetic datasets created by running a simulation of an artificial world. The main focus in designing the world was to produce datasets with many relationships between agents as opposed to complex domains with a large number of entity properties.
  2. HATS designed by the EKSL lab leaded by Paul Cohen. HATS is a lightweight proxy for many intelligence analysis problems. It is a virtual world in which millions of agents engage in individual and collective activities. Most agents are benign, but some intend harm.
  3. A small but interesting dataset about Russian Contract Killing (RCK), developed through research on Russian organized crime.
  4. The Enron email dataset which was made public by the Federal Energy Regulatory Commission during its investigation. It contains many types of personal and official emails.

Don Birx, Physical Science Laboratory

Title: Agent-based Modeling of Multi-resolutional Factors in Terrorist Recruitment

Over the past five years, we have sought to de-velop a new approach to modeling the evolu-tion of social events that builds on complex nonlinear dynamical systems, reflexive analysis and agent-based simulation. The modeling components are themselves not unique; many social science modelers over the past two dec-ades have moved from a reductionist analytic framework to using discrete, agent-based plat-forms that allow non-scripted behaviors to emerge from assemblages of local rules and interactions (e.g. [2]).

What is different in our approach is that we fo-cus on treating our simulations as unusually transparent virtual field experiments with tools and processes that model and analyze the com-plex interaction of agents (which employ re-flexive models) and the resultant system dy-namics - yielding the hoped-for ability to pre-dict and control future events. Results from these experiments can then be used to frame hypotheses that are tested against the real-world, with results being fed back to the virtual world to form a perpetual system identification loop.

Steven J. Brams, Michael A. Jones, and D. Marc Kilgour, NYU

Title: Detecting Terrorist Cells: The Hierarchical Formation of Networks

Terrorists are assumed to rank each other as associates, based on the volume or nature of the communication traffic they have with each other or other measures of association. For example, the more messages that person i sends to person j, the higher i ranks j as an associate. Two processes of network formation are defined and illustrated:

BU cells are stable in the sense that no member would prefer to be in another cell, whereas FB cells, whose members need not rank each other highest, may not be stable. BU cells, at each level of the hierarchy that forms, are mutually exclusive, whereas FB cells may have overlapping members. Because of the overlap, the detection of FB cells is more effective in disrupting networks, whereas the detection of BU cells is more effective in identifying all members of the cells.

Kathleen M. Carley, Carnegie Mellon University

Title: Dynamic Network Analysis for Homeland Defense: Destabilizing Terror Networks

Covert organizations, such as terrorist groups, have network structures that are distinct from those in typical hierarchical organizations; e.g., they are cellular and distributed. Reasoning about how to attack dynamic networked organizations, let alone figuring out how they are likely to evolve, change, and adapt is terribly difficult. In this paper, an approach to estimating vulnerabilities and the impact of eliminating those vulnerabilities in covert networks is presented. This approach involves the combination of social network analysis (graph theoretical measures) and multi-agent systems. Uncertainty is handled by using two types of data to reduce uncertainty, running the model in a Monte-Carlo fashion to determine the robustness of the results, and examining the robustness of the results under adding and dropping nodes and edges in the underlying networks. This is illustrated by contrasting the differential predictions for al-Qa'ida and Hamas as the top leaders are removed.

Jason Crampton, University of London

Title: Using Cryptographic Techniques to Enforce an Information Flow Policy

Information flow policies can be used to articulate confidentiality requirements in highly sensitive commercial and military computer systems. An information flow policy assumes the existence of a partially ordered set of (security) labels and a function that assigns a label to users and data items. The policy requires that all information flow should respect the ordering on the labels: in particular, if a user reads a data object (causing information to flow from the object to the user), then the user's label should be greater than or equal to the object's label. A variety of cryptographic methods have been proposed for implementing this "no read down" aspect of an information flow policy. We will describe and compare some these methods and examine some applications of these techniques.

Paul Dreyer, RAND Corporation

Title: Mathematicians at RAND: Then and Now

It may not be very well known that Edward Tutte's 1971 book "Introduction to the Theory of Matroids" is based upon a series of lectures given at the RAND Corporation in 1965, and a set of papers in the later 1960s written at RAND discussed applications of matroids in more detail. This talk will give a brief summary of the work done by mathematicians at RAND then and now, with the discussion of recent work at RAND concentrating on command and control structures for both military and emergency response teams.

Jonathan Farley, MIT

Winning the Shadow War: A Mathematical Method for Analyzing the Effectiveness of Counterterrorism Operations (A Guide for Risk Assessment and Decision Making)

How can we tell if an Al-Qaeda cell has been broken? That enough members have been captured or killed so that there is a high likelihood they will be unable to carry out a new attack, and military resources can be redirected away from them and toward more immediate threats?

This paper uses order theory to quantify the degree to which a terrorist network is still able to function. This tool will help law enforcement know when a battle against Al-Qaeda has been won, thus saving the public's money without unduly risking the public's safety.

Vladimir A. Lefebvre, University of California, Irvine

Title: Boolean Model of Metachoice: An Analysis of Terrorists' Decision Making

In the framework of reflexive theory, a subject can be represented as a Boolean equation, the roots of which are Boolean functions. Each function is interpreted as a possible program of future behavior. A partial order relation is defined on a set of a Boolean equation roots, which is interpreted as a relation of moral superiority. The subject's selection of one of the programs is called metachoice. A case in which the equation does not have roots is interpreted as a moral dilemma facing the subject. Both the general model, and its application to the simulation of strategic decision-making processes will be discussed in this presentation. Special attention will be given to the application of this theory to the analysis of terrorists' decision making.

Cliff Joslyn, Los Alamos National Laboratory

Title: Order Theoretical Knowledge Discovery

We describe our recent experience in the use of order theoretical approaches to assist investigators in terrorist tracking and computational biology, specifically: the use of concept lattices to represent open-source relational information about terrorist networks; order-theoretical multi-dimensional link analytical techniques for tracking organized fraud in tax databases; and categorization techniques in large poset-based bio-ontologies. This past work has motivated a more general perspective on user-guided knowledge discovery techniques in large data spaces based on combinatorial algorithms rooted in order theory. In general, we propose pursuing a class of methods based on casting databases as ordered combinatorial data objects equipped both with inherent semantics and appropriate combinatorial and statistical measures to support user-guided discovery tasks such as search, retrieval, anomaly detection, and especially interoperable linkage. Central technical challenges include combinatorial measures of distance and interval rank in posets, calculation of poset intersection, and induction of order-preserving maps between ontologies.

Xenia Kramer, New Mexico State University

Title: From Prediction to Reflexive Control: Simulating the Penetration of Our Borders by Terrorists

We describe two algorithms for generating disinformation schemes intended to influence an adversary to make a predetermined decision. Such influence is termed reflexive control. The first algorithm's disinformation tricks the adversary into a given scenario, while the second algorithm finds a scenario to capitalize on a given trick. These algorithms are implemented in a computer program which simulates a situation in which an adversary is attempting to penetrate an international border guarded by the controlling party. Details of this implementation and possible extensions are discussed.

Michael Mislove, Tulane University

Title: Order Theory and Security

Order theory plays an important role in many areas of security. To a large extent, this is a consequence of Denning's seminal model for information flow that is based on a lattice order. This approach led Bell and LaPadula to propose a secure system as one where there is "no read up, no write down." There have been a number of approaches that use order theory to model security, ranging from security policies to multilevel systems. In this talk I'll comment on results in these two areas, pointing out how order-theoretic results arise at the heart of each, in the first instance providing clear insights into what is at work, while in the second, showing how a solution manages to solve a problem by avoiding it altogether. In this latter case, it remains an interesting open question whether there is a "right" order to capture the desired notion of security.

Gordon T. Woo, Risk Management Solutions

Title: Rounding up the Usual Suspects: Insights from Order Theory

Terrorism is waged across one of the most complex of terrains: the human brain. Al Qaeda's chief strategist, Dr. Ayman Al Zawahiri, is renowned for his brilliance. The size and structure of Al Qaeda cells will adaptively evolve so as to minimize the operational impact of the arrest of cell members. On the opposing side, law enforcement officers will endeavor to render the cells operationally ineffective. In a democracy, counter-terrorism actions have to be commensurate with the threat. It is possible to put known Al Qaeda sympathizers under surveillance, but the arrest and detention of suspects is a restricted option for the security services. What terrorist network structures are optimal in respect of resilience against disruption? What powers of detention may be needed to keep would-be terrorists off the streets? Order theory can address these questions for the benefit of Homeland Security.

Ronald Young, University of the West Indies

Title: An Institute for Mathematical Methods in Counter-Terrorism: A new model for North-South cooperation

The world in the 21st century is more interconnected and the states in it more interdependent than at any other time in history. Decisions in one country have direct implications and immediate consequences for others. Vulnerability to cyber-attack and the spectre of narcoterrorism cut across national barriers exploiting our intricately interlinked communications networks. Policies formulated in developed, industrial states must take into account the ways in which their implementation will resonate through developing states where poverty and insecurity offer fertile breeding-ground for the genesis of discontent and for terror of one sort or another.

A North-South collaborative approach to issues of terrorism and related criminal activity, is therefore essential for optimal efficiency in planning for security on both sides of the divide. Jamaica, for example, is a well-known recipient of deportees - nationals who, seeking a better life in developed countries, have merely honed criminal skills; and who, having been convicted, are returned, free, to a society, ill-prepared to cope. They often quickly re-enter the USA/ Canadian/ British system with new identities and new connections. These linkages often help to foster the drug trade and the swap of guns for drugs, leading to extreme destabilization especially of small states with small economies. The Caribbean Task Force on Crime, in its July 2002 report to the 23rd Caribbean Heads of Governments meeting in Guyana, noted that the region had no research capacity for addressing these matters.

Accordingly, the UWI has established a "Centre for Studies of Issues in Criminal Justice, Peace & Security" as an initial step toward cultivating a more profound understanding of some of the problems relating to security and crime. The additional step of establishing at the UWI, an "Institute for Mathematical Methods in Counter-Terrorism," focusing upon formal strategic approaches to the issues of terrorism and State Security, could expand this concept-developing a new model for a deep, cooperative approach to issues of national security, between developed and developing nations. The elaboration, for example, of formal, games theory or other models of optimal strategic action, potential responses and counter-responses, may provide less emotional, more defensible bases for action which would be all the more powerful if they emerged out of a collaborative effort between a developed country and a credible developing state.

I therefore urge you to recognize that developing countries are not simply irresponsible, feckless greenhorns, but can be sophisticated partners with a useful perspective. And I further urge you to demonstrate that recognition by your strong support for setting up the proposed Institute for Mathematical Methods in Counter-Terrorism.

GQ Zhang, Case Western Reserve University

Title: Understanding Meadow's Safe Flow Policy as the Bridging Entailment Relation between Formal Concept Analysis and Scott Information Systems

This talk has two parts. In the first part we establish a systematic link between Formal concept analyais (FCA [1]), a lattice-based tool for symbolic data analysis and ontological engineering and Domain Theory (DT [2]), a mathematical theory for the denotational semantics of programming languages. This link is expressed formally as a categorical equivalence, using a new notion called approximating concepts [3].

In the second part we show how the key idea behind the work of first part, i.e. the closure operator in FCA induces the entailment relation in Scott information systems, shed light on Meadow's safe flow policy for aggregated datasets in computer security [4, 5]. By a concrete instantiation of Meadow's dataset aggregate system, we show that the maximal safe flow policy is precisely the induced entailment relation from a formal security context. Hence the existence and uniqueness of such policy are guaranteed from general principles.

[1] B. Ganter and R. Wille. Formal Concept Analysis. Springer-Verlag, 1999.

[2] D. S. Scott. Domains for denotational semantics, Lecture Notes in
	Computer Science, Vol.  140,  pp. 577-613, 1982.

[3] P. Hitzler and GQ Zhang. A cartesian closed category of approximating concepts. 
        12th International Conference on Conceptual Structures (ICCS04),
	July 19 - 23, 2004, Huntsville, Alabama, USA, in press.

[4] C. Meadows. Extending the Brewer-Nash model to a multi-level context. Proceedings 
        of the 1990 IEEE Symposium on Research in Security and Privacy, IEEE 
        Computer Society Press, pp. 95 - 102, 1990.

[5] J. Millen. Local configuration policies. Proceedings of the 1999 IEEE Symposium 
        on Research in Security and Privacy, IEEE Computer Society 
        Press, pp. 48 -56, 1999.

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 27, 2004.