Skip to content

CSCE 467 Final

General Instructions:

  • You must do this exam by yourself. You cannot work with others (classmates or anyone else). You can use external materials online (e.g., Wikipedia), but if you do, you must (i) cite the source and (ii) write it in your own words (e.g., do not copy and paste).
  • You must type everything unless it involves drawing, which you can do by hand (but you still must draw it very clearly).
  • Submit through Canvas.
  • DUE Tuesday 11/24 at 11:59 PM

Genetic Algorithm (10 pts)

The MAXIMIZATION problem

def foo(x):
  return (-x^2 / 10) + 3*x
The function foo above returns different values depending on the input x, e.g., foo(x=30) = 0, foo(x=12) = 21.6, and then foo(x=14)=22.4. The MAXIMIZE problem aims to find a value of x such that foo(x) is maximized. Moreover, to narrow the search space (otherwise x can have an infinite number of possible values), we will restrict the values of x between 0 and 63.

Your task is to design a GA to solve this problem. Answer the following questions (and subquestions) with complete explanations (use concrete examples if they help illustrate).

  1. How do you represent an individual/chromosome for this problem? Note: for GA, all individuals/chromosomes must have the same size. Then, using this representation, show the chromosome representing
  2. x = 30
  3. x = 12
  4. x = 14
  5. Give a fitness function to evaluate the chromosomes you designed in the previous question. For this example, use a fitness function such that the higher the fitness, the better. Then, using the fitness function, give the fitness values for the chromesomes:
  6. x = 30
  7. x = 12
  8. x = 14
  9. Hint: Your fitness function should produce scores such that fitness(30) < fitness (12) < fitness (14)

Delta Debugging (10 pts)

  1. Consider the the list [a,b,c,d,e,f,g], create a test (an oracle) that makes Delta Debugging runs in its worst case complexity (i.e., it uses O(N^2) tests).
  2. You must use Python (or some language that is supported by the CSE machine) to create the oracle
  3. Clearly illustrate how DD works using the given list and the oracle. Show ALL work (you can write a program or reuse your PA3 if you want to, but you must show all of its work here)
  4. Consider the oracle 
     def test(s):
   return "interesting" if s == [a,b,c,d,e,f,g] else "not interesting"
    1. What is the runtime complexity of using this oracle on the given list [a,b,c,d,e,f,g]?
    2. Clearly illustrate how DD works using the given list and this oracle!
    3. How many variants did you create and test? (Hint: it should be quite many)

Symbolic Execution (10 pts)

void foo1(int a, int b, int c){
  int x = 0, y = 0, z = 0;
  if (a !=0 ){         
    x = -2;
  }                
  if (b < 5){
      if (a==0 && c!=0){
        y = 1;
      }
      z = 2;
  }
  //assert (x+y+z != 3)
  if (x + y + z == 3){
      printf("FAIL\n");
  }
}
  1. Draw the symbolic execution tree for foo to reach the FAIL statement
  2. Clearly label symbolic inputs (e.g., a=A, b=B, b=C or a=\(\alpha\), b = \(\beta\), c = \(\gamma\))
  3. Clearly show EVERY path (including the INFEASIBLE ones)
  4. Create a table as shown below and fill in the answers (examples are given).
    • The above program is written in C, in which the condition if(c) means if (c!=0) and if(!c) means if(c==0)
    • For every condition, there are two branches: then and else, so something like if(a){do something} means if(a){do something}else{pass}
    • After you get some inputs on the FAIL path, try to simulate the execution of foo on those inputs to see if the program actually hit FAIL
  5. Fuzzing: Assume that the inputs are positive and 5 bit (i.e., a,b,c each can take values between 0 and 32), compute and show how many possible inputs over a,b,c that can reach FAIL if you use pure fuzzing. In other words, if you just randomly generate values for a,b,c, then what are the probability you will hit FAIL?
Path Condition Feasible Inputs Local Variables
1 A !=0 && B < 5 && (A == 0 && C != 0 ) NO NA NA
2 A !=0 && B < 5 && !(A == 0 && C != 0 ) YES a=1,b=4,c=1 x=-2,y=0,z=2
...

Hoare Logic

Consider the program

void foo2(){
  // {n >= 0 and p == 0 and x == 0} precondition P
  // note: m has no precondition so it can be value  
  //n,p,x,m are all integers

  while (1){
    // loop invariant I
    if (!(x < n))
      break;
    x = x + 1;
    p = p + m;
  }
  // {p == n*m}  post condition Q
}
  1. Informally argue that this post condition holds, i.e., foo2 computes p as the product n*m.

  2. This means look at the code and convince yourself that it is true, and informally explain why (the next 2 questions we will formally prove it).

  3. Show that each of the given loop invariants below is indeed an invariant (i.e., show that they holds when you enter the loop and are preserved through the loop body)

  4. p == x*m
  5. x <= n

  6. p == x*m && x <= n

  7. For each of the loop invariant above, show whether or not it is sufficiently strong to prove that foo2 is correct with respect to the given pre and postconditions. More specifically, for each loop invariant I above,

  8. Find the wp for the program using I and Q
  9. Prove the program is correct (by showing the verification condition P => wp(S, Q) is true)

Note that if you're not comfortable with the while (1) if ... break syntax above, you can change the program to

void foo2a(){
  // {n >= 0 and p == 0 and x == 0} precondition P

  // note: m has no precondition so it can be value  
  //n,p,x,m are all integers

  while (x < n){
    x = x + 1;
      p = p + m;
  }
  // {p == n*m} post condition Q
}

Abstract Interpretation (10 pts)

def foo3(A, B):
  # P = {A >= 0 and B >= 0}
  x = A
  y = B
  z = 0
  # L1
  while 
    # L2
    if not(x > 0):   # enter loop when x > 0  , exit when x <= 0
      break

    if x % 2 == 1:  #x is odd
        z = z + y 
    x = x // 2
    y = y * 2
    # L3

  # L4 : find abstract values of x,y,z
  return z

For the above program, apply abstract interpretation using the following domains (use the TABULAR FORMAT we did in class and in ia4, i.e., shows what happen at L1,L2,L3,L4, etc)

  1. Odd/Even/Zero: only do these following cases
  2. A = Zero, B = Odd

  3. A = Odd, B = Even

  4. Pos/Neg/Zero: only do these following cases

  5. A = Pos, B = Neg
  6. A = Pos, B = Zero

Note: if you find some of these cases are really trivial, then perhaps they really are. The purpose of this assignment is to see whether you know how to abstract interpretation in various domains.

Project Presentation (10 pts)

For each of the the presented tools below, fill out the table and answer the given question (you DO NOT have to do the tool you presented). See examples below

Tool Static, Symbolic, or Dynamic Tool Inputs Tool Outputs
Z3 (constraint solver) static a formula sat (counterexample)/unsat/ unknown
SPF (symbolic execution tool) symbolic a Java or Java Bytecote program concrete inputs leading to errors
PMD
NNV
FLOW
ANGR
MYPY
INFER
PYRE/PYSA

Extra Credits (5 pts)

  1. (3 pts) For the above program foo3, apply abstract interpretation using the Interval domain we talked in class.

  2. Note: you cannot apply case analysis for Interval domain as other domains because Interval domain does not have finite values (e.g., it does not have things like Odd, Even, but instead a range of values [min,max].)

  3. (2 pts) For the below questions, there are no right or wrong answer (unless you do not answer then you get zero points). I might present your text verbatim (but anonymously) to next year’s students when they are considering taking the course (e.g., in the first week of class).

  4. What were your favorite and least aspects of this class? Favorite topics? Favorite things the professor did or didn’t do? What would you change?
  5. Write an "advertisement" (e.g., "you should take this class because ...") and git bit of "advice" for students taking this class next year (e.g., "you should start PA4 early because ... ").