April 21, 1999
3085 ENG II

In attendance:
Matt Bishop (MB), Tuomas Aura (TA), John Hughes (JH) and David O'Brien (DOB)
  1. 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
    1. TA: On G2, cutting one link doesn't help (or hurt).
      1. Cutting 2 links can cut off one node
      2. Cutting 3 links - cut C-7, 1-8, 5-6
      3. Cutting 4 links - cut C-7, 1-8, 5-6, 3-4
      4. Cutting 5 links - cut Center off from rest of the nodes
  2. To determine damage automatically.
    1. Must associate costs of cutting each edge;
    2. Weight on nodes
    3. Try to minimize the weight of the cut while minimizing the cost of the attack.
    4. Optimization - network draws picture - gives values from 1 server to client
  3. Example G3 - 11 links - cut around center
    1. Communications network looks more like a tree
    2. Easier to solve large problems - parts are not so connected as example
  4. Encoding integer linear program problem
    1. Variable - integer values 0 (lower bound) to 1 (upper bound)
    2. Sum of all variables = Cost
    3. Inequality
    4. Target Function - want to optimize
      1. Spits out inequalities - maple does solve the problem, but is very slow.
      2. 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.
    5. More efficient
    6. Logic problems G1.handout page 2
      1. Basic Link Rule - gives values to all the predicates
      2. Links Breaking
      3. Program into 5 models - stable models for logic problems.
      4. Corporation dependent on one link to the internet
      5. Discussed with Scott Miller - minimum cuts to place in Intrusion Detection Systems - monitor certain connections
  5. Future directions - Probabilistic Algorithms, local changes to solutions
    1. MB: Flip back to covert channels - figure out bandwidth - minimize channels (max flow want to reduce it)
    2. TA: Writing it down to formalize the process
      1. MB: Consider for RAID conference
    3. MB and JH put something together for WATCHERS at meeting today.