April 21, 1999

10-11am

3085 ENG II

In attendance:

Matt Bishop (MB), Tuomas Aura (TA), John Hughes (JH) and David O'Brien (DOB)

- Looking at networks of various sizes, Tuomas has created a system of linear programming which can determine which edges to cuts depending on number of cuts, cost of each edge ($ damage) and weight of each node (how important each node is to the network) -- See handouts

- TA: On G2, cutting one link doesn't help (or hurt).

- Cutting 2 links can cut off one node
- Cutting 3 links - cut C-7, 1-8, 5-6
- Cutting 4 links - cut C-7, 1-8, 5-6, 3-4
- Cutting 5 links - cut Center off from rest of the nodes
- To determine damage automatically.

- Must associate costs of cutting each edge;
- Weight on nodes
- Try to minimize the weight of the cut while minimizing the cost of the attack.
- Optimization - network draws picture - gives values from 1 server to client
- Example G3 - 11 links - cut around center

- Communications network looks more like a tree
- Easier to solve large problems - parts are not so connected as example
- Encoding integer linear program problem

- Variable - integer values 0 (lower bound) to 1 (upper bound)
- Sum of all variables = Cost
- Inequality
- Target Function - want to optimize

- Spits out inequalities - maple does solve the problem, but is very slow.
- Maple better than Matlab (uses floating-point number and matrices) or Mathematica (similar to Maple but don't know what algorithms it's using). Syntax worse in Mathematica.
- More efficient
- Logic problems G1.handout page 2

- Basic Link Rule - gives values to all the predicates
- Links Breaking
- Program into 5 models - stable models for logic problems.
- Corporation dependent on one link to the internet
- Discussed with Scott Miller - minimum cuts to place in Intrusion Detection Systems - monitor certain connections
- Future directions - Probabilistic Algorithms, local changes to solutions

- MB: Flip back to covert channels - figure out bandwidth - minimize channels (max flow want to reduce it)
- TA: Writing it down to formalize the process

- MB: Consider for RAID conference
- MB and JH put something together for WATCHERS at meeting today.