Source code logic evaluation

Question

I was given a fragment of code (a function called bubbleSort(), written in Java, for example). How can I, or rather my program, tell if a given source code implements a particular sorting algorithm the correct way (using bubble method, for instance)?

I can enforce a user to give a legitimate function by analyzing function signature: making sure the the argument and return value is an array of integers. But I have no idea how to determine that algorithm logic is being done the right way. The input code could sort values correctly, but not in an aforementioned bubble method. How can my program discern that? I do realize a lot of code parsing would be involved, but maybe there's something else that I should know.

I hope I was somewhat clear.

I'd appreciate if someone could point me in the right direction or give suggestions on how to tackle such a problem. Perhaps there are tested ways that ease the evaluation of program logic.

Answer 1

In general, you can't do this because of the Halting problem. You can't even decide if the function will halt ("return").

As a practical matter, there's a bit more hope. If you are looking for a bubble sort, you can decide that it has number of parts:

• a to-be-sorted datatype S with a partial order,
• a container data type C with single instance variable A ("the array")
• that holds the to-be-sorted data
• a key type K ("array index") used to access the container that has a partial order such that container[K] is type S
• a comparison of two members of container, using key A and key B such that A < B according to the key partial order, that determines if container[B]>container of A
• a swap operation on container[A], container[B] and some variable T of type S, that is conditionaly dependent on the comparison
• a loop wrapped around the container that enumerates keys in according the partial order on K

You can build bits of code that find each of these bits of evidence in your source code, and if you find them all, claim you have evidence of a bubble sort.

To do this concretely, you need standard program analysis machinery:

• to parse the source code and build an abstract syntax tree
• build symbol tables (ST) that know the type of each identifier where it is used
• construct a control flow graph (CFG) so that you check that various recognized bits occur in appropriate ordering
• construct a data flow graph (DFG), so that you can determine that values recognized in one part of the algorithm flow properly to another part

[That's a lot of machinery just to get started]

From here, you can write ad hoc code procedural code to climb over the AST, ST, CFG, DFG, to "recognize" each of the individual parts. This is likely to be pretty messy as each recognizer will be checking these structures for evidence of its bit. But, you can do it.

This is messy enough, and interesting enough, so there are tools which can do much of this.

Our DMS Software Reengineering Toolkit is one. DMS already contains all the machinery to do standard program analysis for several languages. DMS also has a Dataflow pattern matching language, inspired by Rich and Water's 1980's "Programmer's Apprentice" ideas.

With DMS, you can express this particular problem roughly like this (untested):

 dataflow pattern domain C;

 dataflow pattern swap(in out v1:S, in out v2:S, T:S):statements =
    " \T = \v1;
      \v1 = \v2;
      \v2 = \T;";

 dataflow pattern conditional_swap(in out v1:S, in out v2:S,T:S):statements=
     " if (\v1 > \v2)
          \swap(\v1,\v2,\T);"

 dataflow pattern container_access(inout container C, in key: K):expression
     = " \container.body[\K] ";

 dataflow pattern size(in container:C, out: integer):expression
     = " \container . size "

 dataflow pattern bubble_sort(in out container:C, k1: K, k2: K):function
     "  \k1 = \smallestK\(\);
        while (\k1<\size\(container\)) {
           \k2 = \next\(k1);
           while (\k2 <= \size\(container\) {
               \conditionalswap\(\container_access\(\container\,\k1\),
                                 \container_access\(\container\,\k2\)  \)
           }
       }
    ";

Within each pattern, you can write what amounts to the concrete syntax of the chosen programming language ("pattern domain"), referencing dataflows named in the pattern signature line. A subpattern can be mentioned inside another; one has to pass the dataflows to and from the subpattern by naming them. Unlike "plain old C", you have to pass the container explicitly rather than by implicit reference; that's because we are interested in the actual values that flow from one place in the pattern to another. (Just because two places in the code use the same variable, doesn't mean they see the same value).

Given these definitions, and ask to "match bubble_sort", DMS will visit the DFG (tied to CFG/AST/ST) to try to match the pattern; where it matches, it will bind the pattern variables to the DFG entries. If it can't find a match for everything, the match fails.

To accomplish the match, each of patterns above is converted essentially into its own DFG, and then each pattern is matched against the DFG for the code using what is called a subgraph isomorphism test. Constructing the DFG for the patter takes a lot of machinery: parsing, name resolution, control and data flow analysis, applied to fragments of code in the original language, intermixed with various pattern meta-escapes. The subgraph isomorphism is "sort of easy" to code, but can be very expensive to run. What saves the DMS pattern matchers is that most patterns have many, many constraints [tech point: and they don't have knots] and each attempted match tends to fail pretty fast, or succeed completely.

Not shown, but by defining the various bits separately, one can provide alternative implementations, enabling the recognition of variations.

We have used this to implement quite complete factory control model extraction tools from real industrial plant controllers for Dow Chemical on their peculiar Dowtran language (meant building parsers, etc. as above for Dowtran). We have version of this prototyped for C; the data flow analysis is harder.