Answers CSG 379 Fall 2004 Karl Lieberherr 207 Max =========== 19 UNKNOWNs, 3 points each 57 Question 2: =========== 50 points Question 3: ----------- 40 points Question 4: ----------- 30 points Question 5: ----------- 30 points Question 1: ================================================== see directory cw-automaton-daj UNKNOWN1 = execAutomata UNKNOWN2 = from ChineseWallPolicyChecker to * but a more restrictive strategy is better. Must go to Transition. UNKNOWN3 = from Group_List to GroupName UNKNOWN4 = current = host UNKNOWN5 = cgl.contains(g1) UNKNOWN6 = current UNKNOWN7 = groups UNKNOWN8 = findCIType UNKNOWN9 = ctl.contains(cit) UNKNOWN10 = this UNKNOWN11 = groupName UNKNOWN12 = ident UNKNOWN13 = groupName UNKNOWN14 = ident UNKNOWN15 = this UNKNOWN16 = groupName UNKNOWN17 = ident UNKNOWN18 = groupName UNKNOWN19 = ident Question 2: =========== see directory rbac (generated with demeterj, not DAJ): RBACs = List(RBAC) EOF. RBAC = "users" List(User) "roles" List(Role) "subjects" List(Subject). Role = RoleName [ "transactions" List(Transaction)]. Subject = User "current" "role" Role ["authorized" List(Role)]. Transaction = TransactionName. User = UserName. TransactionName = Ident. RoleName = Ident. UserName = Ident. List(S) ~ "(" {S} ")". Question 3: ================================================= Advantages: ----------- Better separation of security concern. Encourages good compartmentalization. Can be used as weaver for policy languages. Security code is localized. Dynamic changes to security policies Easy run-time monitoring of programs. Can correct vulnerabilities using an aspect Disadvantages: -------------- Hard to follow the program control flow. Manual code inspection is harder but tool support (e.g., the AspectJ Eclipse plug-in are a big help) Have to mentally figure out where aspects will affect code behavior. When base code is changed, aspects may have to be updated. Performance may be reduced Introduces new security vulnerabilities through "rogue" aspects. Removing a security aspect is too easy? Can tempt to add security later rather than building it into the system from the design. Education needed to learn AspectJ Limited to Java Question 4: ======================================================== Many correct answers. Question 5: ========================================================= Non-Emptiness of Set Expressions We translate a boolean formula s into a set expression t(s) using the translation: or union and intersection negation complement The universe is the set of one element: {1}. The set of all subsets consists of the two sets: {} and {1}. Clearly, this is a polynomial time translation. The size of the boolean formula and the size of the set expression are the same. The translation takes linear time. We must show that s is satisfiable if and only if t(s) has a set assignment returning a non-empty set (IFF property). If t(s) has a set assignment returning a non-empty set then we can find a satisfying truth assignment to the boolean formula s as follows: If set variable x is assigned {1}, we set x to true in the formula. If set variable x is assigned {}, we set x to false in the formula. On the other hand, if the boolean formula s is satisfiable, then there is a set assignment that returns the non-empty set for the set expression t(s): If x is true, we set x to {1}. If x is false, we set x to {}. Now let's assume that we have a polynomial-time algorithm ORACLE for Non-Emptiness of Set Expressions. We translate s into t(s) in polynomial time and apply ORACLE to t(s). Then we have an assignment to the set of variables so that the expression returns the non-empty set or we know that such an assignment does not exist. By the IFF property we know whether s is satisfiable. We have also shown the following dual result: Emptiness of Set Expressions: If there is a polynomial algorithm for solving Emptiness of Set Expressions, then there is a polynomial algorithm for unsatisfiability of boolean formulas.