Objective

In this lab, you will implement cooperative bug isolation (CBI) to statistically localize error locations in a program. You need to implement an LLVM pass that instruments each branch and function call to report the values of their conditions and return values. You will then generate a number of sample inputs using a fuzzer. With these inputs, you will obtain the runtime data from the instrumentation and measure different types of scores that help isolate bugs and guide debugging effort. You will then use an LLM to localize the same bugs from source code and compare it with CBI.

Setup

The skeleton code for Lab 5 is located under cis547vm/lab5/. We will frequently refer to the top level directory for Lab 5 as lab5 when describing file locations for the lab. Open the lab5 directory in VSCode following the Instructions from Course VM document.

The lab is split into four parts:

1. In part 1, you will implement two instrumentations, one to instrument each conditional branch instruction reporting the condition. And another that instruments all function calls, to report their return values.
2. In part 2, you will run a fuzzer to generate a set of inputs that will be used to collect data for performing statistical analysis.
3. In part 3, you will run the target program with the inputs generated by the fuzzer to collect cbi logs and analyze the data to report various metrics.
4. In part 4, you will use an LLM for localization and compare using an LLM to using CBI.

To build the instrumentation, you can use the following commands:

lab5$ mkdir build && cd build
lab5/build$ cmake ..
lab5/build$ make

You should now see CBIInstrumentPass.so, libruntime.so, and InstrumentPass.so in the build directory.

The cbi tool performs statistical debugging for a program using a feedback profile (which you will generate) for successful and erroneous program runs.

To help generate program runs that pass or fail, you will use a fuzzer:

lab5$ cd test
lab5/test$ make
lab5/test$ rm -rf fuzz_output_sanity && mkdir fuzz_output_sanity
lab5/test$ timeout 1 ../fuzzer/build/fuzzer ./sanity fuzz_input fuzz_output_sanity 10

Or alternatively you can have the Makefile to do this for you using:

lab5/test$ make fuzz-sanity

To setup the cbi tool you can run:

lab5$ make install

This will install the cbi tool, just like what you had in lab4 for the delta-debugger tool.

You can then run cbi to generate a report of analyzing the runs of a program using:

lab5/test$ cbi ./sanity ./fuzz_output_sanity

Running cbi after completing CBIInstrument.cpp but before completing cbi.py should give you the following report:

== S(P) ==

== F(P) ==

== Failure(P) ==

== Context(P) ==

== Increase(P) ==

Lab Instructions

In short, the lab consists of the following tasks:

1. Implement the instrumentBranch function to insert a __cbi_branch__ call for a predicate (conditional).
2. Modify runOnFunction to instrument all conditional branching instructions using instrumentBranch.
3. Implement the instrumentReturn function to insert a __cbi_return__ call to log the return value of function calls.
4. Modify runOnFunction to instrument all call instructions that return an integer usinf instrumentReturn.
5. Using the feedback profile you construct via 1 through 4, modify cbi/data_format.py to implement formula for calculating: Failure(P), Context(P), and Increase(P) in the PredicateInfo class.
6. Modify the cbi/cbi.py file using the instruction provided in the file, and compute S(P), SObs(P), F(P), and FObs(P) which should be stored in the corresponding data structure (PredicateInfo).
7. Implement an LLM localization script.
8. Answer a list of short response questions.

Part 1: Instrumentation

In this part, you will edit the lab5/src/CBIInstrument.cpp file to instrument branches and return instructions with code to extract and monitor predicates.

lab5/lib/runtime.c contains functions that you will be instrumenting:

void __cbi_branch__(int line, int col, int cond);

void __cbi_return__(int line, int col, int rv);

These functions appends corresponding predicate information as the following json objects respectively:

{"kind": "branch", "line": line, "col": col, "value": true/false}
{"kind": "return", "line": line, "col": col, "value": rv}

to the running process’s cbi log file (target.cbi.jsonl).

Like you did in Lab 2, your LLVM pass should instrument the code with these functions. Your pass should instrument each conditional branch with code that records whether the branch conditional is true or false on execution. Likewise, instrument each call instruction that returns an integer to record its return value at runtime. The log file generated by these instrumentations will create a feedback profile for you to perform statistical debugging and generate a feedback report.

Revisiting Instrumentation.

By now you should feel comfortable working with the LLVM compiler infrastructure, but for a refresher, consult Lab 2 and see the paragraphs titled “Inserting Instruction into LLVM Code” and “Loading C functions into LLVM”.

Part 2: Fuzzer

Once you have implemented the instrumentation, you will run the fuzzer to generate a number of passing as well as failing inputs to a target program.

This is done identically as in lab 3 and lab 4 using:

lab5/test$ make fuzz-sanity

Depending on your machine, you may need to increase the timeout in the test/Makefile to allow for the fuzzer to run for a long enough time to generate a reasonable number of inputs.

Part 3: CBI

The cbi program will execute the target program on each of the input files from the fuzzer output directory. This includes both successful program runs as well as erroneous program runs. Each run will generate a corresponding feedback profile as a .cbi.jsonl file. The resulting directory tree will look like this:

fuzz_output_sanity1
├── success
│   ├── input0
│   ├── input0.cbi.jsonl
│   └──  ...
└── failure
    ├── input0
    ├── input0.cbi.jsonl
    ├── input1
    ├── input1.cbi.jsonl
    └──  ...

The cbi program then parses each of the .cbi.jsonl file into a list of CBILogEntry objects, and passes it to the cbi function in cbi/cbi.py where you will generate the report.

Generating the feedback report.

During the lesson, you saw how we use several metrics to help determine which predicates correlate with bugs. One such metric, Failure(P), calculates how often predicate P is true in a failing run. Another metric, Context(P), calculates the background chance of failure when predicate P is observed. Finally, Increase(P) calculates the likelihood that P influences the success or failure of the program.

You will first need to implement the formula for Failure(P), Context(P), and Increase(P) in the PredicateInfo class.

To help you get started, here’s what you will be filling in for Increase(P):

class PredicateInfo:
   ...
   @property
    def increase(self):
        """
        The Increase value of the predicate.

        :return: The increase value.
        """
        # TODO: Implement the calculation of the increase value.
        return self.failure - self.context
   ...

The PredicateInfo class is a simple data structure that holds the all the requires information for a predicate.

In the cbi.py file, you will go over all the CBILogs and for each predicate you will populate its corresponding PredicateInfo object with the information required for the report.

This includes:

• s: The number of successful runs where the predicate was true at least once.
• s_obs: The number of successful runs where the predicate was either true or false at least once. in a.
• f: The number of failing runs where the predicate was true at least once.
• f_obs: The number of failing runs where the predicate was either true or false at least once.

We have provided you with a few function declarations in cbi/cbi.py that may help you break down this task into more reasonable chunks.

It will also be helpful to look at the cbi/data_format.py file for the data format that you will be using and the available convenience functions.

In particular you have:

class CBILogEntry:
   """
   Data class for a single entry in a CBI log.

   :param kind: The kind of entry [branch/return].
   :param line: The line number specified in the log.
   :param column: The column number specified in the log.
   :param value: The value specified in the log.
   """
   ...

class ObservationStatus(Enum):
   """
   Enum for the Observation Status of a predicate.

   :param NEVER: The predicate was never observed.
   :param ONLY_TRUE: The predicate was observed and was always true.
   :param ONLY_FALSE: The predicate was observed and was always false.
   :param BOTH: The predicate was observed at least once as true and false.
   """
   ...

class Predicate:
   """
   Data class for a predicate.

   :param line: The line number of the predicate in the program.
   :param column: The column number of the predicate in the program.
   :param pred_type: The type of the predicate.
      One of the predicate types from PredicateType.
   """
   ...

class Report:
   """
   Data class for the CBI Report.

   :param predicates_info_list: A list of PredicateInfo objects of
      all predicates in the program.
   """
   ...

Note: Your instrumentation will record where a branch or return occurs and its result, but you need to encode that into a predicate. For example, if we encounter if (p == 10) { ... } in the code, we need to store two predicates, (p == 10) is true, and (p == 10) is false, which you would represent as BranchTrue and BranchFalse. You may find the PredicateType.alternatives function helpful for this.

Once you populate the predicate_infos dictionary in the cbi function, the skeleton code will go through it and print out the report as well as store a detailed report to target.report.json file.

Example Input and Output

Your statistical debugger should run on any C code that compiles to LLVM IR. As we demonstrated in the Setup section, we will compile code to LLVM and instrument the code with the fuzzer and cbi passes.

lab5$ cd test
lab5/test$ make test2

After this, we will run the fuzzer to generate a set of passing and failing inputs for use with the cbi tool, and finally run the cbi tool.

lab5/test$ make fuzz-test2
lab5/test$ cbi ./test2 fuzz_output_test2

You should expect to generate output similar to the following:

== S(P) ==
Line 010, Col 007,    BranchFalse: 68.0
Line 010, Col 007,     BranchTrue: 0
Line 014, Col 007,    BranchFalse: 65.0
Line 014, Col 007,     BranchTrue: 3.0
== F(P) ==
Line 010, Col 007,    BranchFalse: 0
Line 010, Col 007,     BranchTrue: 145.0
Line 014, Col 007,    BranchFalse: 0
Line 014, Col 007,     BranchTrue: 0
== Failure(P) ==
Line 010, Col 007,    BranchFalse: 0
Line 010, Col 007,     BranchTrue: 1.0
Line 014, Col 007,    BranchFalse: 0
Line 014, Col 007,     BranchTrue: 0
== Context(P) ==
Line 010, Col 007,    BranchFalse: 0.6807511737089202
Line 010, Col 007,     BranchTrue: 0.6807511737089202
Line 014, Col 007,    BranchFalse: 0.0
Line 014, Col 007,     BranchTrue: 0.0
== Increase(P) ==
Line 010, Col 007,    BranchFalse: -0.6807511737089202
Line 010, Col 007,     BranchTrue: 0.31924882629107976
Line 014, Col 007,    BranchFalse: 0.0
Line 014, Col 007,     BranchTrue: 0.0

You can download the input files we used to generate the report above from here.

Part 4: LLM Fault Localization

In this part you will use an LLM to read the source code of the test programs and localize the divide-by-zero errors. You will also compare the LLM’s answers to the CBI reports from part 3.

Use the test programs in test/llm-localization/ (test2.c-test6.c). They behave the same as the programs in test/, but test6.c has been edited so that the bugs are not labeled.

You will write a script that prompts the LLM of your choice to find the exact lines in a program that divide by zero. Use the same prompt for every test program.

The script will sample the LLM ten times for a program and save each reply. It will then combine the ten replies into one final answer.

LLM Fault Localization Script

You will implement a script that programmatically prompts and samples an LLM to localize faults given program source code. You will sample ten times and decide how to combine the ten samples into one final answer. You will implement a version where the LLM can’t use tools, and a version where the LLM can use tools. Start with the version without tools: the prompt includes the program’s source code and the LLM may not use any tools. That is the default when you run the script. You will add the tool usage version in the Tool Usage Comparison section. Please execute your script in the docker container.

You will complete the functions in llm/llm_localize.py that have the comment # TODO in the function body.

For deciding on how to combine the samples into one answer for the combine function, your combining strategy is up to you.

When running the script, it saves the following for each program:

• The generated prompt: llm/samples/<program>/prompt.txt
• Each sample’s reply, exactly as the LLM returned it: llm/samples/<program>/sample01.json through sample10.json
• Each sample’s session transcript, which includes the entire output after invoking the coding agent: llm/samples/<program>/transcript01.log through transcript10.log
• The final answer, combined from the 10 samples: llm/<program>.localization.json

Save everything your tool records about the session. Most CLIs have a JSON or verbose output mode (for example, claude -p --output-format stream-json --verbose). The transcript format is up to you; it is not graded.

Write your prompt in llm/prompt.txt. The script reads it and uses it for every program. Run the script from the lab5 project root with the path to a test program:

lab5$ python3 llm/llm_localize.py test/llm-localization/test2.c

Output Format

Each reply and the final answer must be a JSON object with exactly these two keys, and nothing else in the file:

{ "file": "test2.c", "fault_lines": [11] }

• file is the program’s file name, for example "test2.c".
• fault_lines lists 1-5 distinct line numbers, most likely first. Line numbers refer to the program’s source file, counting the first line as 1.

A fault line is the line where the division by zero happens. A reply with Markdown code fences, explanations, or extra keys does not follow the format.

CBI Comparison

Extend your LLM localization script to include a CBI report in the prompt. Run the script with the corresponding CBI report for each program. Run the CBI comparison without tools, so the only difference from your main runs is the CBI report. You will observe the performance differences with and without the CBI report in the writeup questions.

Save these runs separately so they do not replace your graded answers: write their samples and transcripts to llm/samples/<program>-cbi/ and the final answer to llm/<program>.cbi.localization.json.

Tool Usage Comparison

Extend the llm localization script to include a tool usage option. In this mode, the LLM does not receive the program’s source in the prompt. Instead, your script copies the program into an otherwise empty working directory, and the LLM uses tools to read and search it there. Use the same llm/prompt.txt for both modes.

Run your script in tool usage mode on every test program (test2 through test6). The LLM may only read and search the program, for example with cat and grep. It may not compile or run code, edit files, access the web, or read anything outside its working directory. Configure your tool’s permissions so that any other action is denied rather than allowed (see the Tool Permissions hint). The agent also cannot use persisted memory between sessions.

Save these runs separately so they do not replace your other answers: write each program’s samples and transcripts to llm/samples/<program>-tool-use/ and its final answer to llm/<program>.tool-use.localization.json. These runs are graded the same way as your runs without tools. You will compare the two modes in the writeup questions.

Rules

• Using an LLM is required. Save every reply exactly as the LLM returned it. Do not edit replies by hand.
• The LLM can not use persisted memory between samples and test programs.
• For tool usage mode - the LLM can only read and search the given test program in its working directory. Do not have the agent read/write other directories and files.
• Use one prompt, llm/prompt.txt, for all test programs and for all script modes (no tools, tools, cbi).
• Every line in your final answer must appear in at least one LLM response that follows the format. You choose how to combine the replies, but the final answer must come from them.
• The LLM may access only the program it is localizing and in the CBI comparison, the program’s corresponding CBI report. Run it in a directory that contains only those files.

Below is a table describing the required LLM runs to provide in your submission. Run each mode on every test program (test2 through test6), for 15 runs in total.

Mode	How it runs	Samples and transcripts	Final answer
No tools	Program source in the prompt, no tools	llm/samples/<program>/	llm/<program>.localization.json
Tool usage	LLM reads the program with read-only tools	llm/samples/<program>-tool-use/	llm/<program>.tool-use.localization.json
CBI	No tools, with the program’s CBI report in the prompt	llm/samples/<program>-cbi/	llm/<program>.cbi.localization.json

Hints

Programmatically Prompting

See these official guides on how to write generalized LLM prompts programmatically:

• Anthropic: Prompting best practices
• OpenAI: Prompt engineering
• Google: Gemini prompt design strategies

Read the replies in your samples, not only the final answer. They show how your prompt fails, and how often.

Tool Permissions

In the tool run, the agent should be able to read and search the program and nothing else. Most agents decide what to run through a permission system: some actions run automatically, and the rest need approval. Because your script runs the agent non-interactively, nobody is there to approve anything, so you need to choose a setting that denies those actions instead of waiting or allowing them.

• Claude Code Permissions
• Codex Permissions
• Agy Permissions

Memory

Each sample should depend only on your prompt and the program. Many LLM tools remember things between sessions or load extra instructions automatically, which can make your ten samples less independent and give the LLM information that is not in your prompt. Before sampling, check what your tool loads and saves:

• Instruction files: tools load files such as CLAUDE.md (Claude Code), GEMINI.md (Gemini CLI), or AGENTS.md (Codex) from your home directory and from the directory they run in. Running each sample in a fresh, empty directory avoids project files; check your home directory for a global one.
• Saved sessions and memory: some tools save each session or write memories that later sessions read.

Your transcripts show what each session loaded, so you can confirm the memory usage.

Adding CBI Input

See parse_args().

Short Answer Questions

We have the following questions. Please fill out lab5_writeup.md.

1. What LLM model and coding agent did you use?
2. Why did we ask you to sample the LLM ten times? Should you increase the number of samples or decrease? Should you sample at all?
3. How did you decide on combining the multiple samples to one answer for the combine function implementation? Please explain your thought process.
4. Compare the transcripts between the no tool usage and tool usage runs. What tools were most frequently used? Did the LLM get stuck on the task due to tool usage, and if so why/how/which tool? Compare the token usage and explain which approach is more efficient to use. When would you use tools, when would you not use tools, and why?
5. Given your experience of using CBI with/without an LLM to find faults, which of the approaches do you prefer to use for fault localization? Do you prefer CBI over LLM, LLM over CBI, or using both? What are the trade-offs? Support your answer with concrete examples from your runs with and without the CBI report, for example whether the report changed the LLM’s answers, turns, or token usage.
6. Extra Credit/Optional (+20 points) - Create a program where the LLM incorrectly detected a fault line. The bug must still be a divide by zero bug. Include the model and coding agent used. You can take an existing test program and modify it yourself, or create your own. Why do you think the LLM failed to detect the fault line, and what else did you try? Save your program in llm/extra_credit/ and run your script on it, so its samples, transcripts, and final answer are included in your submission.
7. Extra Credit/Optional (+1 point) - What did you think of the LLM portion? How long did it take? Did you find this useful? Were you already familiar with working with LLMs this way? We appreciate any feedback.

Submission

Once you are done with the lab, you can create a submission.zip file by using the following command:

lab5$ make submit
...
submission.zip created successfully.

Then upload the submission file to Gradescope.