Description
Software Testing, Quality Assurance, and Maintenance Project, Version 1.1[1]
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 supportsupport({(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.
(b) Finding and Explaining False Positives (10 points)
Examine the output of your code for (a) on the Apache httpd server (test3 from part (a)) by running verify.sh. Do you think you found any real bugs? There are some false positives. A false positive is where a line says “bug …” in your output, but there is nothing wrong with the corresponding code. Write down two different fundamental reasons for as to why false positives occur in general.
Identify 2 pairs of functions that are false positives for httpd. Explain why you think each of the two pairs that you selected are false positives. The two pairs should have a combined total of at least 10 “bug …” line locations (e.g., first pair can have 4 and second pair can have 6). For example, the following sample output contains 4 locations regarding 3 pairs: (A, B) (A, D) and (B, D). You do not have to provide explanations for all 10 locations, but you will want to use at least one location to discuss each pair. Briefly explain why the pair is a false positive with reference to the source code.
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%
The source code of httpd has been provided on ecelinux for your convenience. It is located at: /opt/testing/apache src.
This directory contains the source code, the bitcode file (.bc), the call graph file in plain text format (.txt), and the sample output (.out) for a run of httpd. At the end of the call graph, you’ll find the file path where each function is defined, which will help you find the actual function bodies.
If you find new bugs (bugs that have not been found by other people yet), you may receive bonus points. Check the corresponding bug databases of Apache[2] to make sure that the bug you found has not been reported there already. Clearly explain why you think it is a bug and provide evidence that it is a new bug.
(c) Inter-Procedural Analysis. (10 points)
One solution to reduce false positives is inter-procedural analysis. For example, one might expand the function scope1 in the function scope4 to the four functions A, B, C, and D. Implement this solution by adding an optional fourth command line parameter to pipair. We leave the algorithm’s implementation details up to you.
Write a report (up to 2 pages) to describe your algorithm and what you found. Run an experiment on your algorithm and report the details. For example, you can vary the numbers of levels that you expand as an experiment. Provide a concrete example to illustrate that your solution can do better than the default algorithm used in (a). We will read your report and code. If you only submit a report, you will receive at most 50% of the points for this part (c). Make sure your code is well documented and your report is understandable. Follow the submission protocol in part (a) and place the code inside the pi/partC directory.
Test 3 from part (a) utilizes the same program (httpd) as part (b). Therefore, you might find it convenient to use test 3 to verify your inter-procedural experiment.
Resources for students who would like to generate a call graph with function arguments (optional):
- Check out the following post: http://stackoverflow.com/questions/5373714/generate-calling-graph-for-ccode
- Once you generated the call graph, use c++filt to demangle the function names (takes care of function overloading). After that use sed to transform the text and you will get the call graph.
- It is important that you disable C/C++ optimizations during the call graph generation. Add the following flags in “opt” to ensure there is no inlining and ensure “opt” would not optimize the function arguments: -disable-inlining -disable-opt
- You have to use clang++ to generate the bitcode.
Part (II) — Using a Static Bug Detection Tool
For this part of the project you will be using the static code analysis tool Coverity to find defects in source code.
We have acquired a Coverity license for student use. Occasionally, we will collect groups, generate Coverity credentials, and mail you a link which allows you choose a password for your credentials.
(a) Resolving Bugs in Apache Commons (10 points)
In this task, you are to triage warning messages resulting from running Coverity static analysis on Apache Commons (a library of useful Java tools). We have already compiled and analyzed a version of Apache Commons for you. The pre-analyzed code is available on Coverity’s web interface at http://ecetesla0.uwaterloo.ca: 8080 behind the firewall. Log in using username “student” and password “%Ccb2wXQ”. To view and triage warnings from the analysis, select the “Outstanding Defects” item in the navigation tree on the left hand side of the page. Click on warnings to view details of the warning and the source code that triggered the warning.
The analysis results contain warnings from both Coverity and FindBugs static analysis tools.
Your task is to triage and repair these warnings. There are 20 warnings for you to triage and repair. Triage each warning by classifying it as one of the following: False Positive, Intentional or Bug. Do not use the built-in Triage tool. Write your classification and explanations directly in your report. Below are descriptions of each triage classification:
- False Positive: The warning does not indicate a fault or deficiency.
- Intentional: You believe the warning points to code that the developer intentionally created that is incorrect (contains a fault) or considered bad practice.
- Bug: The warning points to a defect (a fault or bad practice) in the code.
If you classify the warning as False Positive, provide an explanation as to why you believe this is the case. If you classify the warning as Intentional, explain how the code can be re-factored to remove the warning, or explain why it should be left as-is. If you classify the warning as bug, provide the faulty lines (1–2 lines is often enough, including the file name and line numbers) and a description of a proposed bug fix.
The difference between False Positive/Intentional and Intentional/Bug is not always clear, so there is not necessary one unique good classification. Make sure you explain clearly your choice!
For details on each Coverity checker, read the checker documentation (see https://patricklam.ca/stqam/ coverity/#reference_material). Information on FindBugs checkers can be found at http://findbugs. sourceforge.net/bugDescriptions.html.
The report for this part should be no more than 4 pages. Be concise.
(b) Analyzing Your Own Code (10 points)
Run Coverity on your own code from part (I) (a). See instructions on https://patricklam.ca/stqam/ coverity/ to analyze your code with Coverity Connect interface. Once your project is uploaded on the web interface, you must make it inaccessible to other students: connect on http://ecetesla0.uwaterloo.ca: 8080 with your credentials. Click on “Configuration” , “Projects & Streams” and Select your project. In the “Roles” tab, click on “add” and check “No Access” for the group “Students”.
You learn more from having the tool find defects in code that you wrote, fixing the problem and seeing the defect go away. Discuss two of the bugs detected by Coverity using up to 1 page. If Coverity finds no bugs, what are the possible reasons?
Include the results from your analysis with your submission. Put them in directory pii.
You can find instructions on how to use Coverity to build and analyze your code at https://patricklam.ca/ stqam/coverity/.
[1] updated URLs
