GEC12 - GENI "Hive Mind" Report

Period: August 1, 2011 - December 1, 2011

I. Major accomplishments this period

A. Milestones achieved this period

Hive: S3.e Paper on Security Experimentation with GENI (Due 09/01/11) -Completed and delivered to Vic Thomas.

Hive: S3.f Deliver software and documentation (Due 09/09/11) -Completed and delivered to Vic Thomas.

Hive: Year 3.a Demonstration and Outreach at GEC12 (Due 11/5/11) -Completed.

B. Deliverables made this period

Hive: S3.e Paper on Security Experimentation with GENI (Due 09/01/11)

Hive: S3.f Deliver software and documentation (Due 09/09/11)

II. Description of work performed during this period

A. Activities and findings


The Hive Mind project seeks to to define and prototype a security layer underlying GENI that will allow providers of the system to collaboratively defend against attacks and misuse of GENI resources.

Our initial hypothesis guided us to propose the use of concepts similar to swarm-intelligence for GENI. This idea was a response to two key qualities of GENI that make it different than many other scenarios: first, GENI is used for networking experiments. Such experiments need predictable and minimal performance impact from any security solutions. Second, GENI slices cross many administrative boundaries. Thus, a security solution must support a variety of different security policies, as policies between different organizations can vary widely and may sometimes even conflict (e.g., "all hosts must respond to ICMP requests" vs. "all hosts must use firewalls to 'blackhole' all incoming requests").

To these ends, we proposed The Hive Mind using a hierarchy of security layers with ultra-lightweight, mobile, digital ants as sensors/classifiers, host-level sentinels that protect and configure a single host, enclave-level sergeants responsible for the security state of an entire enclave (slice or aggregator), and humans supervisors that provide guidance to and receive feedback from one or more enclaves. The lightweight nature of the sensors was designed to minimize impact on experiments, and the split responsibilities of each sergeant allowed organizations to share common sensor libraries but configure sentinels and sergeants to react to sensors to enforce security policies in very different ways.


In this term, we developed a working prototype of the Hive Mind.

Our experimentation over this term, has shown that the ant-based is effective for system monitoring and can quickly find attacks regardless of the types of events and their distribution across the monitored system. Detection speed and resource usage is based on a number of configuration parameters. Several heuristics for these are apparent; optimal settings for them have not been studied. While effective, ant-based monitoring has a number of challenges to be overcome before it could be arguably superior to other methods. Many of these have been resolved in recent versions of the monitoring system, but more remain. We plan empirical comparison to other competing methods in the next term.

The philosophy behind traditional, "heavyweight" IDS methods is to run all detection rules, all the time, at all locations. Alternatively, ant-based monitoring strives to look for only what is of interest, only when and only where it is likely occurring. By design the ant-based method is expected to take longer to detect events than traditional network and host IDS approaches, but in contrast would use significantly less system resources, and have less impact on the monitored system. Our experimentation has shown that this is true of host resources (CPU, memory), but ant-based methods uses a significant ammount of network bandwidth to support information exchange between hosts, i.e., the "ants." The amount of bandwidth used and the speed of detection is directly related to ant-density, that is, the number of host monitored, the number of ants in the system, and how fast the are allowed to move. The actual impact of this depends on the communications medium used. The worst case is when all ant packets, for all hosts, pass over a common medium (e.g. a common wire). The result is that detections speed can be increased, but with increased consumpiton of network resources. Determining at what point resource use becomes excessive needs to be understood.

A related finding is that while detection speed increases with ant density, this is only true up to a point where the system becomes saturated with ants. The is because of resource contention. For wide spread attacks, too many ants will also degrade performance. The resulting explosion of digital pheromone trails seem to confuse ant movement and at times move the ants away from unexamined regions where attacks have occurred.

In the simplest sense, the our ant based method is a series of biased random trials to find needles in a haystack. The bigger the stack, the fewer the needles, and the longer the time between attempts, the longer the time to find a needle. Thus very low ant densities tend to result in long and decididly non-deterministic times to detect an event. Upper and lower bounds on effective ant-density needs to be determined.

Many other parameters that affect performance need to be studied. Some example are, the lenght of the pheromone trail; how long the trail persists; how birth/death parameters effect not just the average ant population, but its variability; the proportion of ants assigned to each task type, how ants change tasks, how linear (vs. random) an ant's trail is.

A key concept of our method is that of a "geography", that is, a space that provides host location and the notion of neighbors. Because ant pheromone trails direct detection resources into a region of this space, and it is presumed that there is a likelihood that if multiple attacks occur there will be some similarity between them (e.g. same targeted OS or application, same slice, same aggregator, etc.) it is necessary to place similar hosts near each other in the geography. Note if there is no correlation between attack, pheromone trail adds no value, and the search method is reduced to a random walk. It can be shown that for some cases, the pheromone trails delay detection by divering ants into unproductive areas of the geography, preventing the ants from searching others. Our current prototype uses a Hilbert space filing curve to map nodes to a 2-d geography. This is a reasonable method when there is a single similarity attribute (e.g. aggregator, VM host), but completely ineffective when trying to organize neighbor relations across multiple attributes. Unfortunately detection system performance requires it. This is a known hard problem, but heurestic and randomized algorithms for this need to be investigated.

In the ant based method, an ant-specified sensor function is checked when an ant arrives. Sensor functions query a particular aspect of the current state of the host. This sample-focused or shapshot method is very different from traditional IDS methods that are event-driven, including network based IDS that monitor all traffic flowing through gateways. This difference restricts the type of information that the ant method can readily obtain.

Because the ant method can be effective in a variety of differenty implentation environments, we are also exploring the use of digital ants to cope with considerably different varieties of attacks, such as use of computational resources for Bitcoin computation, or other cryptanalytic activities, because we have demonstrated in the HPC context how we are able to detect such activities:

Sean Peisert, "Fingerprinting Communication and Computation on HPC Machines," Technical Report LBNL-3483E, Lawrence Berkeley National Laboratory, June 2010.

Sean Whalen, Sean Peisert, and Matt Bishop, "Network-Theoretic Classification of Parallel Computation Patterns," Proceedings of the First International Workshop on Characterizing Applications for Heterogeneous Exascale Systems (CACHES), Tucson, AZ, June 4, 2011.

Sean Whalen, Sophie Engle, Sean Peisert, and Matt Bishop, "Network-Theoretic Classification of Parallel Computation Patterns" (expanded version of CACHES paper), to appear in the International Journal of High Performance Computing Applications (IJHPCA), 2011.

Alternative Approaches

As indicated above, we have informally compared the method used in the ant-based prototype to several others, and investigated other biological systems to ameliorate some of the shortcomings of the digital ant method. We have determined that different biologicial systems "solve" different problems, each related to the environment or other behavior of the creatures, for example if the creatures food occurs in locally dense regions or singaly. We have modifying the orignal ant model to handle many different situations, first by incorporating analogs of actual ant behaviors, then by looking at how non-ant species handle similar problems. Attempting to merge all behaviors into a single detection "species" will overly complicate what was as it strong point a truly simple system, and the result will not be as effective as simply building an "ecosystem" of different independent types of monitoring types. This way we can incorporate the benefits of traditional IDS designs and balance the effectiveness of each.

The purpose of the ants leaving digital pheromone is to direct ants toward the region where something was found. This biases the ants random foraging and increases detection on the host where the original problem was found. If instead, each node would simply periodically execute a random sensor function, then upon success, increase the rate of random sensor execution, and broadcast to its neighbors that a particular problem was found. The neighbors could in turn execute with higher probability the sensor function originally successful and increase their rate of executing sensor functions in general. This would increase local detection and appears to provide equivalent detection to the ant-method for many cases. It may be possible to create a system that has similar behavior to ant-based methods, without the overhead of the ants. The difference in effectiveness and resource use between these two methods should be studied.

Determining what the sensor functions should detect is a primary concern. This will be directly related to the types of attacks we wish to detect. A promising direction is to use sensor function to detect violations of broadly, "policy." This includes user specified limits on an experiments behavior to detecting unexpected changes in files.

Experimental Setup and GEC 12 Demo

In the current instance of the prototype, GENI experiment slices are swapped in with a management process running on each node. An extra node for security system oversight and reporting is added to the experiment. Experiments are being run to test a variety of performance criteria using Slices of up to 640 nodes. We are using ProtoGENI and DETER test beds and the Benito virtualization framework for our testing.

In our GEC 12 demo, we showed visually how the Hive Mind system can detect a wide variety of attacks, each having different challenges. These ranged from single isolated attacks, multiple attacks targetting a group of related hosts, to widely distributed attacks such as may be seen in a distributed denial of service attack launched from a GENI slice against an internet host.

New Directions

Although the digital ant method is effective at detecting particular classes of events, it is not clear that this is sufficient to meet the security monitoring needs of GENI. Our direction is now shifting back to traditional intrusion detection systems. However, we are still conscious of the specific requirements of GENI security systems. Therefore, our current approach still seeks to minimize the impact on the GENI and in particular resource contention (e.g. network bandwidth) of the experiments, but not at the cost of allowing an attack to be missed. Our current approach also still allows a variety of varying security policies, as one would expect when a slice crosses many aggregators.

To enable this, we employ a hybrid model that uses the ant approach for a limited number of attacks, and combines this with a "heavyweight" IDS that monitors using specification-based intrusion detection. In a specification-based intrusion detection system, good things are predefined and attacks are implicitly anything outside of the pre-defined, good specification. This is in contrast to misuse-based intrusion detection in which all bad things are pre-defined.

Calvin Ko, Manfred Ruschitzka, and Karl Levitt, "Execution Monitoring of Security-Critical Programs in Distributed Systems: a Specification-Based Approach," Proceedings of the IEEE Symposium on Security and Privacy, pp. 175-187, Oakland, CA, 1997.

In our system, a specification of an experiment is defined across multiple axes, including network bandwidth usage, host processor load, DNS requests, IP addresses sent to or received from, and length of experiment.

A specification is made by the experimenter, as well as the other stakeholders in the GENI environment. In order of priority, with the GENI Project Office being highest:

  1. GENI Project Office (GPO)
  2. Aggregator
  3. Other Experimenters
  4. Current Experimenter

In this hierarchy of policies, the "strictness" of each policy with higher priority trumps each policy with lower priority. That is, another experiment (priority = 3) can specify that no other experiments should use more than 50% of the network bandwidth. The proposed experiment (priority = 4) can say that it wants to use 60% of the network bandwidth. The "other" experiment is more strict, so it trumps. If the proposed experiment says it only wants 10% of the network bandwidth, then it can run. The GPO (priority = 1) can specify that no experiment can request more than 20% of the bandwidth however. In this case, the "other" experiment is rendered void and the proposed experiment can still run. In this way, all stakeholders are satisfied, and even unusual network experiments can be run because the burden of specifying security parameters is placed on experimenters and owners of the network, which may permit such activities, even if only for a short period of time.

Note that this model is inspired by the model used in supercomputing environments in which specifications of computational jobs are submitted to a batch scheduler. In such an environment, the scheduler analyzes the resources requested and then determines if a job should run on a particular machine, and if so, when. At this point, our project does not contain a scheduler, but such a concept may be a useful future addition.

We do intend to add a web-based policy composer for experimenters and stakeholders to input policies, and a system to evaluate those policies at runtime.

Also note that though the prioritization scheme avoids the need for resolving conflicts between policies, there may still be a more rich policy calculus that our scheme should permit in the future. For example, perhaps 100 Gigabits of bandwidth is permitted to be saturated for 1 minute, but 10 Gigabits of bandwidth is permitted to be saturated for up to 10 minutes.


Our experimental results, demonstrated at GEC12, have shown that the digital ant concept is effective at detecting a wide variety of attacks provided that ant-based sensors can obtain the required information. In order to meet the security monitoring requirements of GENI this will have to be augmented with some traditional IDS concepts at both the host and network layer. Ultimately, we believe that our new scheme provides significantly greater security and policy flexibility at lower resource cost.We look forward to showing this experimentally in a demonstration at GEC13.

B. Current project participants

PI: Sean Peisert (UC Davis)

Senior Personnel: Matt Bishop (UC Davis) Steven Templeton (UC Davis)

C. Publications (individual and organizational) this period


D. Outreach activities this period

Prof. Peisert is again serving as program co-chair of the 5th Workshop on Cyber Security Experimentation and Test (CSET '12) in August, 2012:

This workshop will have considerable discussion of and focus on testbeds, including ProtoGENI.

E. Collaborations this period

Our project is now collaborating closely with the "Attribution for GENI" project (PI: M. Bishop, UC Davis). Together, we are working toward shared goals, using shared project resources.

We also are working with staff at the DETER project, who are facilitating our implementation and experimental work on DETER, and with Rob Ricci, who is facilitating our implementation and experimental work on ProtoGENI. We are grateful to the staff at both projects for their valuable help.

F. Other Contributions