This repository contains existing and new loop detection algorithms, which aim to answer the question: "What is contained within a loop?" All programs operate on control flow graphs (CFGs); however, the developed algorithms: 1, 2, 3A and 3B operate upon implementing CFGs as doubly linked lists, whereby each node within the CFG can reference at most two additional nodes, constrained to be a CFG.
Each algorithm conforms to a specific loop definition. Each algorithm is tested against a common set of tests to determine what nodes are detected by each algorithm. The outputs for each algorithm are located in: algorithms/ALGORITHM/ALGORITHM-results.
A UNIX derivative, preferably Debian/Ubuntu or MacOS, is required to compile each algorithm and generate similar results.
Bash v5.1.16(1)+ to run shell-scripts
GCC v13.1.1+ to use G++ as a C++ Compiler to compile algorithms 1 to 3. Please ensure the version installed is compatible with C++ 17.
CBMC v5.77.0+ to generate Lexical and Natural Loops results.
Graphviz v2.40.1+ to generate a CFG visualizing the (*c) program used by shell scripts.
GNU Time v1.9 | GNU Time Mac v1.9 to include measurement of program runtime, CPU and RAM resource usage.
Within each algorithms folder, there are two sub-folders for each generated algorithm. One folder contains the algorithm's source code, while the other contains the results generated.
CBMC algorithms deviate from this as the source code for their implementations is locatable on the hyperlinks below to the specific commit used for each algorithm, such that if the algorithms deviate after the project, the code visible is exact as to what the results within the project have generated.
Contains folders for each generated bug report containing the supporting evidence for each bug report. A text file contains the URL to the submitted bug report for each bug.
Contains a (*.c) program and its equivalent representation as a CFG. (*.goto) is an intermediary generated by CBMC to generate (*.dot) file Graphviz output. Each folder contains a single test case and the equivalent representation as a CFG viewable as a (*.pdf).
Contains shell scripts to generate results for all algorithms compared, invokable by running:
chmod +x ./{SCRIPTNAME}.sh
./{SCRIPTNAME}.sh
where SCRIPTNAME is either ./run-developed.sh to generate results for developed algorithms or ./run-cbmc.sh for CBMC's lexical and natural loops algorithms.