CS295 FinalSpring 2010• Don’t forget to put your name and SID on this cover sheet.• Solutions will be graded on correctness and clarity. Each problem has a relatively simple and straight-forward solution. You may get as few as 0 points for a question if your solution is far more c omplicatedthan necessary. Partial solutions will be graded for partial credit.• This exam is due at no on on Tuesday, June 9. You may return the exam either by email to the coursestaff account or physically in 411 Gates (just put the exam under the door if it is closed).• If wish to ask questions during the period of the exam, please send email to the course staff [email protected]. Do not use the class newsgroup to discuss or ask questionsabout the exam.• In accordance with both the letter and spirit of the Honor Code, you will neither give nor receive assistanceon this examination.Problem Max points Points1 302 303 304 305 20TOTALNAME:SID:11. Eraser vs. Chord (30 points)Eraser, a dynamic tool, and Chord, a static tool, both detect data races. Please give concise answers to thefollowing questions that ask you to compare the two approaches. Eraser here refers to an implementationof Eraser for Java.• Give an example of a race that Eraser catches but Chord cannot. Give Java code (a pseudo-codesketch is fine) as well as a written description that explains your example and why Eraser finds therace and Chord does not.• Give an example of a race that Chord catches but Eraser cannot. Again, give Java code (a pseudo-code sketch is fine) as well as a written description that explains your example.• Give an example of a false positive that would be reported by Chord but that would not be reportedby Eraser. Here you do not need to give code, but you need to describe the conditions under whichthis situation could occur clearly.• Argue that any false positive produced by Eraser would also be produced by Chord.22. Annotation-Based Systems (30 points)Consider the following code:void bubble_sort(char * p, int len) (1){int i, j; (2)char temp; (3)char *end = p + len; (4)char *ptr = p; (5)for(i = 1; ptr + i < end; ++i) { (6)for(j = len - 1; j >= i; --j) { (7)if(ptr[j-1] >= ptr[j]) { (8)temp = ptr[j-1]; (9)ptr[j-1] = ptr[j]; (10)ptr[j] = temp; (11)}}}}• What annotations do you need to add to compile this code with De puty without any warnings?Show the annotation and the line number. You may, if you wish, use Deputy to answer this question(but it is not required that you do so).• How could you use DAIKON to infer Deputy annotations? Sketch an algorithm for automaticallyproducing the Deputy annotations from one or more runs of DAIKON and Deputy.33. Static Analysis Comparison (30 points)Consider the following program:mylock(x) { lock(x); }myunlock(x) {unlock(x); }main(boolean b) {if (b) { mylock(x) }y += 1;if (b) { myunlock(x) }}Using the standard specification for safe single-thread locking (i.e., treating any double-lock or double-unlock as an error), answer the following questions. Assume that the lock x is initially unlocked.• Show the function summaries inferred by Saturn.• Show how ESP would analyze this program. Show the information inferred for each line of code.4• Show how BLAST would analyze this program. Show the information inferred at each line of code,and show any predicates that are added as the result of refinement steps. In any refinement step youneed, pick any predicate you like (but only one).54. Static Analysis Expressiveness (30 points)You are designing test cases for a static analysis that detects division by zero. For each of the followingsituations, give the simplest code fragment (in any reasonable C or Java-like notation) that answers thequestion. You should also explain why your code examples answer the questions.• An example of a division-by-zero bug that can be found by a flow-insensitive analysis.• A division-by-zero bug that can be found by a flow-sensitive but not flow-insensitive analysis.• A division-by-zero bug that can be found by a path-sensitive but not path-insensitive analysis.65. Miscellaneous Short Answer (20 points)• What is one advantage and one disadvantage of a flow-insensitive static analysis? What is oneadvantage and one disadvantage of a path-insensitive analysis?• Java includes a language mechanism for detecting certain uncaught exceptions at compile-time.In particular, the Java compiler do es a static analysis to figure out whether checked exceptionsare guaranteed to be caught, and any checked exception that is not handled by the program is acompile-time error. If you are not familiar with Java’s language features for checked exceptions youshould read about them; only a basic knowledge is required to answer this question. One referenceis http://java.sun.com/docs/books/tutorial/essential/exceptions/catchOrDeclare.html.Do you think Java’s analysis for uncaught checked exceptions is inter- or intra-pro c edural? Justifyyour answer.7• What is a context-sensitive vs. context-insensitive analysis? Give one example of a static analysiswhere context sensitivity is important. You should also explain why context sensitivity is importantin that static analysis.• As discussed in class, a standard heuristic used in many bug-finding algorithms is to analyze onlythe first few iterations of a loop. Given an example of an analysis problem discussed in the courseother than buffer overflows for which this strategy will not work well. Justify your