Problem Set 2: Attack of the Robots

Due Wednesday, September 19, 2007, 11:00 pm.

• Sep 12: Part 2: An obvious typo has been fixed in the definition of IMPLIES. Also, the description of the input string for makeTree has been fixed: variables are in all lowercase, constructor names are in all uppercase. Changes are shown in red.

Instructions

TOP SECRET: RESNET OPERATION #42

And you thought a horde of Zombies attacking Ithaca was disturbing...

After many years of planning and plotting, the Department of Robotics at Cornell (DRAC) has decided now is the take to take over the rest of the Cornell campus. In a secret laboratory beneath Beebe lake, a group of students and faculty have designed and engineered countless autonomous robots whose sole goal is to completely block the access to the most precious energy resource on campus: Free Food (FF). The army of robots have formed barriers around all FF sources and will disrupt any unauthorized attempt to access the FF without any exception. Fortunately, spies from the underground Resistance Network (RESNET) have just uncovered blueprints of the underlying circuitry of all the robots. In the blueprints, the first thing you notice is that the robots have a built-in Emergency Shutoff (ES) feature that is triggered by opening a small panel on the torso of the robot, and entering the correct bit string. Unfortunately, the other engineering members of RESNET have concluded that each robot has distinct circuitry, and thus a distinct ES code. Also, there seems to be no way to invert the circuit to see what the code is, so it needs to be cracked by trying all possibilities. Even worse, if the panel on a robot is opened, and the correct code is not entered within 5 seconds, the robot will stun the person entering the code, and alert all other robots to ignore any Emergency Shutoff request for the next 48 hours!

The most recent development is that RESNET has just learned that each robot has a unique identifier on the panel that is only visible after the panel has been opened (an unnamed professor went through a lot of trouble to discover this the hard way when he attemped to secure a slice of pizza at a seminar). The great news is that the same identifier appears on the blueprints. Thus it should be possible to

1. Bravely walk up to a robot
2. Open the panel and read the ID
3. Find the blueprint of that particular robot
4. Crack the code of the ES circuit
5. Enter the code, cross fingers, and disable this robot.
6. Repeat for all other robots surrounding the FF source.

The problem is that until we open the panel, we have no idea which robot is which, and cracking the ES code certainly takes longer than 5 seconds.

As an invaluable CS expert in RESNET, you immediately see that the most direct approach is to reverse-engineer and crack all of the ES circuits before opening any panels. There are too many robots and blueprints to do this manually, so you decide to write a program to do the cracking. Given the situation, the natural choice for a programming language for this task is ML.

Time is running out. It is in your hands to regain control over the FF supplies, and save the whole campus!

Part 1: Evaluation using substitutions

As you sit down, you suddenly realize the severity of the situation. You get a little nervous since most of the ML code you've written ended up having occasional mistakes, and there is really no room for errors this time. You decide that it makes sense to start off by writing down things that you feel you need to fully understand before being able to undertake the RESNET Operation with full confidence. You grab a piece of paper and write down some non-trivial expressions, and start seeing how they evaluate, step by step. On the paper you write

(fn x => fn y => x * y * (fn y => y+x) 10) 3 8

let
   val x = 2 + 3
   val y = fn z => z+1
   val z = y x
in
   (fn x => x*z) (y z)
end

let
   val l = [ [7,8,9], nil ]
in
   case l of
      (x1 :: x2 :: xs) :: nil => x1 + x2
    | (x1 :: x2 :: xs) :: [nil] => x1 + x1 + x2
    | (x1 :: x2 :: xs) :: xt => x1 + x2 + x2
    | _ => 0
end

To do: Write the evaluation of these expressions using small-step substitutions in a file called written.txt

Part 2: Parsing postfix

A few experiments later, you again feel confident in your ML skills. It is time to start addressing the real problems at hand. You look at the blueprints again. It appears the DRAC engineers designed the ES circuits to use the following set of gates.

• AND:     x AND y = true iff both x and y are true.
• OR:      x OR y = true iff either x or y are true.
• NOT:     NOT changes true to false, and vice versa.
• XOR:     x XOR y = true iff exactly one of x and y are true
• NAND:    x AND y = true unless both x and y are true.
• IMPLIES: x IMPLIES y = true unless x = true and y = false.

datatype CircuitTree =  AND of CircuitTree*CircuitTree | OR of CircuitTree*CircuitTree |
                        XOR of CircuitTree*CircuitTree | NAND of CircuitTree*CircuitTree |
                        IMPLIES of CircuitTree*CircuitTree | NOT of CircuitTree |
                        Var of string

First step is to manually read off the circuit from the blueprint and input it into your program. To make this easier, the fellow RESNET engineers have spent hours deciphering and writing up each circuit in postfix form. (They picked postfix notation because infix is ambiguous without loads and loads of brackets). Thus, the postfix form of the expression tree in the right is:

"x y AND NOT x y IMPLIES y x XOR NAND NOT OR"

You need to build the ML data structure that represents the actual expression tree, that is:

NOT (Var "x" AND Var "y") OR NOT ((Var "x" IMPLIES Var "y") NAND (Var "y" XOR Var "x"))

You write a function

fun makeTree(circuit : string) : CircuitTree

To do: Implement makeTree in part2.sml

Part 3: Evaluating circuit trees

Like a professional cryptanalyst, you want to get a feel for the circuits to look for possible weaknesses before you start cracking the ES codes. To do that, you want to be able to provide input codes to the circuits. More specifically, given a map from variables to their values represented as an association list (i.e., a list of variable names and input value pairs), evaluate the output of the circuit. The function you write is

fun evaluate(circuit : CircuitTree, values : BitValue list) : bool

type BitValue = string * bool

To make this easier, you decide to write another function to help look up variable names from the list of assignments. You call it

fun findValue(name : string, values : BitValue list) : bool

To do: Implement evaluate and findValue in part3.sml.

Part 4: Tree reduction

Now that you have a better feel for how the circuits operate, the next step is to write the cracker. To simplify things before starting the cracking, you decide to reduce the number of gate types in the circuit. For instance, (ignoring the ML datatype for clarity)

• x NAND y is equivalent to NOT (x AND y). Similarly,
• x XOR y becomes (x AND NOT y) OR ((NOT x) AND y), and
• x IMPLIES y is really (NOT x) OR y.

fun simplifyGates(circuit : CircuitTree) : CircuitTree

A friend of yours points out that it would be extremely helpful to implement a "fold" routine for the tree structure you defined that works similar to foldl and foldr. Following her suggestion, you write:

fun foldTree (f : (CircuitTree * 'a) -> 'a) (a : 'a) (t : CircuitTree) : 'a

[Looking back at your ML code so far, you wonder how on earth you would have pulled this off in say Java.]

To do: Implement simplifyGates and foldTree in part4.sml. Make use of foldTree in simplifyGates.

Part 5: Cracking!

You continue playing around with the simplification of the ES circuits, and actually putting them on a normal form, similar to the one you saw in complexity that was used for 3-SAT expressions. It turns out that the DRAC engineers are no weenies - to crack the circuits you are actually required to solve an instance of an NP-complete problem! The only algorithms that are known for solving 3-SAT are exponential in the input length. In other words, it would probably have been impossible to do the cracking in the 5 second grace period given by a robot, so the DRAC people must have some sort of book with robot IDs and the ES code for each robot. With luck, you will be able to replicate those codes!

Your first observation is that the circuits are not impossibly big, so that even exponential algorithms will terminate before our sun contracts into itself. After all, the DRAC engineers probably had to something similar to come up with those codes. The second observation is that there is nothing in the way for there being multiple codes that work for a given robot. No distinction appears to be made in the ES circuits, so any solution will do.

Up to this point, it has been your hope that it would be possible to narrow down the set of potential ES codes for each circuit to something that would be straightforward to crack. Something like "bits 2 and 4 need to be set, and the last 3 bits need to be the same value" would have been great. But this does not seem feasible anymore, so we're going to have to resort to trying all possible inputs for the circuit. You're going to use the simplified CircuitTrees from the last part. This is it. Your heartbeat is up. Your pupils are dilated, Your fingers are itching. It's time to start cracking. You grab the keyboard and type

(* VIVA RESNET!!! *)
fun crack(circuit : CircuitTree, variables : string list) : BitValue list

crack (simplifyGates (circuit2718), ["b1", "b2", "b3", "b4"])

[("b1", true), ("b2", false), ("b3", false), ("b4", true)]

To do: Implement crack in part5.sml