Part (I) Building an Automated Bug Detection Tool (60 points)
You will learn likely-invariants from call graphs in a way reminiscent to that in SOSP’01 paper discussed in class (Coverity). In particular, you will learn what pairs of functions are called together. You will then use these likely-invariants to automatically detect software bugs. (a) Inferring Likely Invariants for Bug Detection (40 points) Take a look at the following contrived code segment. void scope1() { A(); B(); C(); D(); } void scope2() { A(); C(); D(); } void scope3() { A(); B(); B(); } void scope4() { B(); D(); scope1(); } void scope5() { B(); D(); A(); } void scope6() { B(); D(); } We can learn that function A and function B are called together three times in function scope1, scope3, and scope5. Function A is called four times in function scope1, scope2, scope3, and scope5.
We infer that the one time that function A is called without B in scope2 is a bug, as function A and B are called together 3 times. We only count B once in scope3 although scope3 calls B two times. We define support as the number of times a pair of functions appears together. Therefore, support({A, B}) is 3. We define confidence({A, B}, {A}) as support({A,B}) support({A}) , which is 3 4 . We set the threshold for support and confidence to be T SUPPORT and T CONFIDENCE, whose default values are 3 and 65%. You only print bugs 2 with confidence T CONFIDENCE or more and with pair support T SUPPORT times or more. For example, function B is called five times in function scope1, scope3, scope4, scope5, and scope6.
The two times that function B is called alone are not printed as a bug as the confidence is only 60% support(A,B) support(B) = 3 5 , lower than the T THRESHOLD, which is 65%. Please note that support(A, B) and support(B, A) are equal, and both 3. Perform intra-procedural analysis. For example, do not expand scope1 in scope4 to the four functions A, B, C, and D.
Match function names only. The sample output with the default support and confidence thresholds should be: bug: A in scope2, pair: (A, B), support: 3, confidence: 75.00% bug: A in scope3, pair: (A, D), support: 3, confidence: 75.00% bug: B in scope3, pair: (B, D), support: 4, confidence: 80.00% bug: D in scope2, pair: (B, D), support: 4, confidence: 80.00% Generate call graphs using LLVM. Given a bitcode file, you use LLVM opt to generate call graphs in plain text format, and then analyze the textual call graphs to generate function pairs and detect bugs.
The opt tool is installed on CS Linux machines (mc*.cs.purdue.edu) If you want to work on your own computer, you need to use 64-bit LLVM 6.0 to avoid compatibility issues. A sample call graph in text format is shown as follows: Call graph node for function: ‘ap_get_mime_headers_core’<<0x42ff770>> #uses=4 CS<0x4574458> calls function ‘ap_rgetline_core’ CS<0x4575958> calls external node CS<0x4575a50> calls external node CS<0x4575b20> calls function ‘apr_table_setn’ CS<0x45775a8> calls external node CS<0x45776a0> calls external node CS<0x4577770> calls function ‘apr_table_setn’ CS<0x45783b8> calls external node CS<0x4579dc0> calls function ‘apr_table_setn’ CS<0x4579f78> calls function ‘strchr’ CS<0x457a948> calls external node CS<0x457aa40> calls external node CS<0x457ab10> calls function ‘apr_table_setn’ CS<0x457d9d0> calls function ‘apr_table_addn’ CS<0x457e4e8> calls function ‘apr_table_compress’ and Call graph node <><<0x2411e40>> #uses=0
The following explanation should help you understand the call graph: • The above call graph represents the function ap get mine headers core calls functions ap rgetline core, apr table setn, etc. • #uses= gives the number of times the caller is called by other functions. For example, ap get mine headers core is called 4 times. • CS denotes call site. • 0x????? indicates the memory address of the data structure, i.e., call graph nodes and call sites. • An external node denotes a function that is not implemented in this object file. Ignore external node functions.
• A call graph node of null function represents all external callers. Ignore null function nodes entirely. 3 Performance. We will evaluate the performance and scalability of your program on a pass/fail basis. The largest program that we test will contain up to 20k nodes and 60k edges. Each test case will be given a timeout of three minutes. A timed-out test case will receive zero points. We do not recommend using multi-threading because it only provides a linear gain in performance. 4 Hints: • (Very Important!) Do not use string comparisons because it will greatly impact the performance.
Use a hashing method to store and retrieve your mappings. • Minimize the number of nested loops. Pruning an iteration in the outer loop is more beneficial than in the inner loop. • None of the provided test cases should take more than 5 seconds to run. Submission protocol. Please follow this protocol and read it carefully: • You only have to submit three items inside the directory named pi/partA. You should ensure that you don’t include compiled binaries or test subdirectories. – A file called Makefile to compile your source code; it must include ‘all’ and ‘clean’ targets. – A file called pipair as an executable script. You don’t need to submit this if your pipair is an executable binary, which will be generated automatically when our script executes ‘make’ on your Makefile. – Source code for your program.
Please document/comment your code properly so that it is understandable. Third party libraries are allowed. Make sure all your code runs on CS mc machines (mc01.cs.purdue.edu – mc18.cs.purdue.edu). We will not edit any environment variables when we run your code on our account, so make sure your program is self-contained. We will be testing the code under the bash shell. Place all of the above items at the root of your repository. Do not submit any of the files from the skeleton folder. • We provide the marking script (verify.sh) that we’ll use to test your pipair. Please write your code and Makefile to fit the script. • Make sure your code works on CS mc machines. We will use the provided scripts to grade your project on CS mc machines. If your code doesn’t run on CS mc machines, you will receive 0 points. You must use C/C++ or Java for part (I). • Marking will be done with strict line comparisons.
We will count how many pairs are missing (false negatives) and how many pairs are false positives. • You should print one pair per line to stdout in this format: bug: %s in %s, pair: (%s, %s), support: %d, confidence: %.2f%%\n • The order of the pairs in your output does not matter. As you can see from the script verify.sh, we will run sort before diff . • The order of the two functions in a pair does not matter in the calculations. Both (foo, bar) and (bar, foo) contribute to the count of pair (bar, foo). However, to have consistent output (for easier grading), you must sort the pair alphabetically while printing. For example, print (bar, foo) instead of (foo, bar). The golden output uses natural sorting (lexicographical comparison) with the following API: http://docs.oracle.com/javase/tutorial/collections/interfaces/order.html In lexicographical comparison, digits will precede letters and uppercase precedes lowercase. • Ignore duplicate calls to the same function. For example, if we have the code segment scope() { A(); B(); A(); B(); A(); }, the support for the pair (A, B), support(A, B), is 1. 5 • Name your program pipair. We must be able to run it with the following command, where the support and confidence value will always be an integer: ./pipair , e.g. ./pipair hello.bc 10 80, to specify support of 10 and confidence of 80%, or ./pipair , e.g. ./pipair hello.bc, to use the default support of 3 and default confidence of 65%. • If running your program requires a special command line format such as java YourProgram arguments, your pipair should be a wrapper bash script, e.g.: #!/bin/bash java YourProgram $@ $@ represents all command line arguments. • If you are using Java, you must configure the -Xms128m and -Xmx128m flag to ensure Java Virtual Machine allocates enough memory during the startup (do not allocate more than 128MB). It is recommended that configure this in your pipair script while launching your Java program. The reason is that the VM will not dynamically increase the heap size for the larger test cases. Make sure your program is memory efficient to ensure it scales to larger test cases. Skeleton files and marking. • We recommend developing on CS mc machines so that you don’t have to deal with porting and compatibility issues later. We have confirmed that the UNIX “sort” command behave differently on Mac than on Linux. • To test a specific test case, run “make clean” and then “make” in the test’s directory. Your output should be identical to the “gold” file. Your output should be passed through sort before diffing with the gold file. For example: sort testX Y Z.out | diff gold Y Z – • To run all tests together, execute verify.sh. Logs of all output can be found in /tmp. • clean.sh runs “make clean” in all test directories. • Our marking procedure: 1. We will extract your submitted tar file on the server. 2. We will copy the required files from your pi/partA directory into the root of a clean skeleton folder that contains the full test suite with seven tests. 3. We will run “verify.sh” to test your program, which will automatically: (a) Run “make” to compile your program. (b) Execute each test with a two minute limit. • Since the skeleton files and tests are copied over during marking, do not modify any files given in the project skeleton, since they will be over-written. 6 Common issues. • It says “error”. This error indicates verify.sh encountered a problem when it tried to run make inside the test directories. This is likely due to a failure in pipair. Here are a few things that you can do to help troubleshoot this issue: – The error message is usually in the testx x xx.out file. This file contains what got written to stdout by your pipair executable. – The log output of verify.sh is dumped to a file at /tmp/testing–pi-
The Codes Hive believes in helping students to write clean codes that are simple to read and easy to execute.Based in New York, United States, we provide assignment help, homework help, online tutoring and project help in programming to the students and professionals across the globe.
Disclaimer: The reference papers/tutorials provided are to be considered as model papers only and are not to submitted as it is. These papers are intended to be used for research and reference purposes only.
