SE465 - project1 - Solved

Part (I) Building an Automated Bug Detection Tool
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 (also seen in lecture):

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 support({(A,B{A})}), which is  . 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 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%    , 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, 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 the ECE machines (ecetesla0.uwaterloo.ca) as well as the CS machines. If you want to work on your own computer, you need to use 64-bit LLVM 3.0 to avoid compatibility issues. LLVM 3.0 is available as a package in many popular Linux distributions.

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 <<null function>><<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.

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 two minutes. A timed-out test case will receive zero points. We do not recommand using multi-threading because it only provides a linear gain in performance.

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 helpful 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 a directory named as pi/partA. Your .gitignore should ensure that you don’t push 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 ecelinux. 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.