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