Saturday, August 1, 2015

Software Security - Week 5

1. A static analysis
  • analyzes a program's code without running it
 2. Advantages of static analysis over testing?
  • A static analysis can reason about all program paths, not just some of them
    • This is the key benefit of abstraction, as used by static analysis. The abstraction makes it possible to consider an approximation of all runs.
3. Which of the following are not the advantages of static analysis over testing?
  •  A static analysis is usually more scalable than testing
    • This is not true in general. Arbitrarily large programs can be tested (i.e., executed), but many static analyses are limited in the size of the programs they can consider. OTOH, very simple static analyses can run very fast.
  • A static analysis is more precise than testing
    • This is not true: Static analysis abstracts an execution, ignoring some details to focus on a property of interest, and to scale. Testing is perfectly precise, because it's actually running the program.
4. The halting problem is the problem of determining, for an arbitrary program and input, whether the program will finish running or continue to run forever. Which of the following statements about the halting problem are true?
  • Many other program analysis problems can be converted to the halting problem.
    • This is true. We showed how the question of whether an array indexing expression is in bounds can be reduced to the halting problem (by converting the program we are interested in into a different program such that an answer by a termination analysis implies an answer about the original program).
5. Suppose we have a static analysis that aims to find buffer overflows in C programs. If the analysis is sound, then which of the following is true about it?
  • It may have false alarms, but will not fail to report actual bugs
6. Consider the program below, using the qualified types annotations for tainted flows given in the lecture (shown in comments). In particular, notice that the variable fmt and the argument to printf are untainted, while the result of fgets is tainted. Suppose we analyze this with a tainted flow analysis. This program has no bugs, but which kinds of analysis report a false alarm?
/* int printf(untainted char *fstr, ...); */
/* tainted char *fgets(...); */

char *chomp(char *s) {
  int i, len = strlen(s);
  for (i = 0; i<len; i++)
    if (s[i] == '\n') {
      s[i] = '\0';
      break;
    }
  return s;
}

void foo(FILE *networkFP, untainted char *fmt) {
  char buf[100];
  char *str = fgets(buf, sizeof(buf), networkFP);
  char *str1 = chomp(str);
  char *fmt1 = chomp(fmt);
  printf(fmt1,str1);
}
  • flow-sensitive, context-INsensitive
    • A context insensitive analysis will report an alarm because all calls to chomp are conflated. Since we are passing both str1 and fmt to chomp, where the former is tainted, the output of chomp will always be considered tainted in a context-insensitive analysis, regardless of whether or not it is flow- or path-sensitive.
  • path-sensitive, context-INsensitive
    • A context insensitive analysis will report an alarm because all calls to chomp are conflated. Since we are passing both str1 and fmt to chomp, where the former is tainted, the output of chomp will always be considered tainted in a context-insensitive analysis, regardless of whether or not it is flow- or path-sensitive.
NOTE: 
  • flow-sensitive, context-sensitive
A context-sensitive analysis will treat the two calls to chomp distinctly, so fmt1 will remain untainted, and thus be considered a legal argument to printf (regardless of the flow- or path-sensitivity of the analysis)
  • path-sensitive, context-sensitive
A context-sensitive analysis will treat the two calls to chomp distinctly, so fmt1 will remain untainted, and thus be considered a legal argument to printf (regardless of the flow- or path-sensitivity of the analysis)
7. Consider the following code, where the referenced chomp function is the same as in the previous question. Suppose we analyze this with a a tainted flow analysis. Once again, this program has no bugs, but which kinds of analysis report a false alarm?
void bar(FILE *networkFP, char *fmt, int testing) {
  char buf[100];
  char *str = fgets(buf, sizeof(buf), networkFP);
  char *str1 = chomp(str);
  if (testing)
    str1 = chomp("test format");
  printf(fmt,str1);
  if (testing)
    printf(fmt,"how did the test string look?\n");
}

NONE: 
Even the least precise analysis will not throw a false alarm for this program. This is because fmt is always treated as untainted, no matter whether the calls to chomp are sensitive, or whether the order (or path) of statements is considered.

8. Which of the following are true of implicit flows?
  • One can occur when assigning an untainted value to an untainted variable, but conditioned on a tainted value
  • Implicit flows are rarely detected by tainted flow analyses, because detecting them can increase false alarms
9 What is a key advantage of symbolic execution over static analysis?
  • As a generalized form of testing, when a symbolic executor finds a bug, we are sure it is not a false alarm
    • Moreover, one can often produce a test case from the alarm that reproduces the bug, making it easier to fix
10. Symbolic execution, viewed as a kind of static analysis, has which of the following "sensitivities?"
  • Flow-sensitivity
  • Context-sensitivity
  • Path-sensitivity
11. Why is concolic execution problematic for non-terminating programs?
  • Its search strategy is to choose new test cases based on constraints generated by terminating runs
    • As such, a non-terminating program may not produce a terminating test, and thus will never produce constraints to produce the next test.
12. Suppose that x and y in the following program are symbolic. When the symbolic executor reaches the line that prints"everywhere" what will the path condition be?
/* assume x and y are both symbolic */
void foo(int x, int y) {
  if (x > 5) {
    if (y > 7) {
      printf("here\n");
    } else {
      if (x < 20)
	printf("everywhere\n");
      else 
	printf("nowhere\n");
    }
  }
}
  • x > 5 ∧ ¬(y > 7) ∧ x < 20
13. Suppose that x in the following program is symbolic. When the symbolic executor reaches the line that prints "here" what will the path condition be?
void bar(int x) {
  int z;
  if (x > 5)
    z = 5;
  else
    z = 1;
  if (z > 3)
    printf("here\n");
}
14. Which of the following are heuristics that symbolic executors use to cover more of the search space?
  • Randomly restart the search from the main function
    • This avoids the problem of being stuck in a "local minimum", i.e., a portion of the program that has many paths, at the expense of exploring other parts of the program 
  • Choose between two paths based on whether one reaches program statements not previously executed
    • This approach intends to maximize "coverage" under the theory that executing all lines of code is more important than executing arbitrary groups of paths in the same code area
  • Choose between two paths based on a notion of priority
    • Coverage is one kind of priority; another kind might be based on whether some other static analysis tool finds part of the path suspicious 
15. Suppose that x in the following program is symbolic. When the symbolic executor reaches the line that prints "here" what will the path condition be?
void bar(int x) {
  int z;
  if (x > 5)
    z = 5;
  else
    z = 1;
  if (z > 3)
    printf("here\n");
}
  • x > 5
16. A tainted flow is
  • A flow from an untrusted source to both trusted and untrusted sinks
  • A flow from an untrusted source to a trusted sink
    • This is true, but not completely true. Really, a tainted flow is still tainted even if it ends up at an untrusted sink   

13 comments:

  1. Thank you for this. By any chance do you have Project 3 Quiz? I can't understand it. And it's the last quiz I need to pass. I appreciate it. Thanks very much.

    ReplyDelete
  2. anyone have info on project 3? I was doing fine until this project and it is really kicking my butt

    ReplyDelete
  3. any one with answers of coursera project2 (badstore)? stuck on first n 8th qustion!!!

    ReplyDelete
  4. Such an informative blog... thanks for sharing... please visit once at http://www.qosnetworking.com/ 

    ReplyDelete
  5. can someone help in solving project 2 & 3 of this course

    ReplyDelete
  6. Can anyone help me on the project 3 please?

    Thanks,

    ReplyDelete
  7. I finished Badstore. I was over thinking it. I am, however, stuck in Project three. I think that the method to go the directory is enigmatic?

    ReplyDelete
  8. Hi I need help in badstore week 3 project and quiz . Please anyone help me :( much appreciated

    ReplyDelete
  9. here is the solution to the quiz on the week 5 for project 3. If you need more help please feel free to ask.

    1. Does fuzz.py identify a crash in wisdom-alt? In how many iterations?

    Identifies a crash, 103 iterations

    Identifies a crash, 44 iterations

    Does not identify a crash

    Identifies a crash, one iteration

    2. Does fuzz.py identify a crash in wisdom-alt2? In how many iterations?

    Does not identify a crash

    Identifies a crash, 1 iteration

    Identifies a crash, 133 iterations

    Identifies a crash, 800 iterations

    3. Name one symbolic variable that was set in the path condition identified by KLEE that crashes wisdom-alt2.

    —-> buf

    4. Name another symbolic variable set in the path condition identified by KLEE that crashes wisdom-alt2.

    —-> r

    5. What was the data content of the buf object?

    ‘\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00’

    ‘\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xFF\x00\x00\x00\x00\x00\x00\x00\x00\xAA’

    ‘\x00\x00\x00\xFF\x00\x00\x00\x00\x00\x00\xBB\x00\x00\x00\x00\x00\x00\x00\x00\xEE’

    ‘\xFF\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00’

    6. After executing the symbolic maze, what was the data value of the ‘program’ object? (Hint: it will be a string of the lowercase letters s, d, w, and a.)

    —-> sddwddddsddw

    7. If you run the symbolic maze program so that it finds all solutions, not just one, how many are there?

    —-> 309 (But I think you have to work it yourself)

    8. There was a bug in the maze program that allows the player to walk through walls. What line in maze-sym.cis the bug on? (If there are multiple lines, pick one of them.)

    —–> 113

    Thank you.

    ReplyDelete
  10. https://nepalisupport.wordpress.com/2017/07/14/software-security-quiz-project-3-week-5/



    refer this

    ReplyDelete
  11. can someone post software security quiz-2 solutions

    ReplyDelete
  12. Software security week-1 quiz 2 solutions please!!!!!!

    ReplyDelete