The purpose of PNTG (pronounced “painting”) is to provide an easy way to generate test functions for code with discontinuous control flow, such as a network protocol where sections of code are separated by waits for messages or an API in which users call multiple entry points in succession. The resulting test functions can then either be compiled and run as a standard unit test or subjected to static code analysis. Either way, the goal is to verify that the code follows certain rules such as locking or resource acquisition/release across all possible sequences — including those which are likely to be missed by manual test generation and almost certain to be missed by static analyzers on their own.

Note: this article and the ideas behind it are not really “fully baked” by my usual standards, but I’ve been falling behind on my writing here so I figured I’d just splat it up here anyway to see if anyone had any interesting comments. Maybe I’ll try to clean it up more later.

Petri Nets (PNs) are a well-established notation for describing complex systems, similar to the better known finite state machines (FSMs). In fact, it’s almost trivial to convert a description from one to the other. In a nutshell, a simple Petri Net consists of “places” which may contain tokens, connected to “transitions” which can “fire” when their input places contain a sufficient number of tokens. When a transition fires, it both consumes tokens from its input places (possibly disabling other previously enabled transitions including itself) and produces tokens at its output places (possible enabling other previously disabled transitions). Thus, any FSM can be represented as a PN in which each transition has exactly two input places representing a predecessor state and an event plus one output place representing a successor state. Conversely, any PN can be represented as an FSM by defining an FSM state for each possible PN “marking” (assignment of tokens to places) and an event for each choice of an enabled transition for that marking.

If the two are equivalent, and FSMs are more familiar to most programmers, why use PNs? Mostly it’s because PNs tend to describe real systems more concisely. While translating from an FSM to a PN yields a roughly equivalent number of places and transitions as states and events, translation in the other direction can cause a combinatorial explosion resulting in an obscene number of states. Computational equivalence does not imply equal expressiveness, and a more expressive notation is more likely to be used successfully to verify the behavior of complex real-world systems. That’s why the literature for such verification in PN-based systems is so much more extensive than that for FSM-based systems (although neither has exactly suffered from lack of attention), and the same concerns apply to PNTG.

OK, enough philosophy. How do we turn this into a real tool? The key is to map transitions to code, so that each path through the PN (from the initial marking to some terminal marking in which no transitions are able to fire) maps to a generated test function. To see how this works, consider a simple API in which a user opens a file and closes it again immediately or reads one block before closing. This is represented by the following diagram, with ovals representing places and rectangles representing transitions.

With a token initially in the “ready to open” state this yields the desired possibilities. Initially only the “open file” transition is enabled. After it fires, both “read” and “close file” are enabled. The only twist is the double arrow between “ready for close” and “read” which is a standard PN idiom for when a token is required for a transition to fire but is not consumed in the process. Now, consider the following fairly-intuitive mapping from transitions to code.

prefix {
    int  fd;
    char buf[512];
}
open_file {
    fd = open("/foo/bar",O_RDWR);
    if (fd < 0) {
        return;
    }
}
read_file {
    read(fd,buf,sizeof(buf));
}
close_file {
    close(fd);
}

Following the possible sequences and assembling a function from the code associated with each successive transition, this yields the following test functions.

void
test1 (void)
{
    int  fd;
    char buf[512];

    fd = open("/foo/bar",O_RDWR);
    if (fd < 0) {
        return;
    }
    close(fd);
}
void
test2 (void)
{
    int  fd;
    char buf[512];

    fd = open("/foo/bar",O_RDWR);
    if (fd < 0) {
        return;
    }
    read(fd,buf,sizeof(buf));
    close(fd);
}

The two differ only as to whether a read is done, as should be the case. The code associated with a transition can easily do error checking and such, as above for the open, to preclude code paths that would actually not execute. It could also check internal state. A "suffix" section (not shown) at the end of each function could do the same, or report status for automated testing. This could be useful, for example, to guarantee that a locking protocol actually does make forward progress instead of succumbing to deadlock or livelock. Obviously this is a trivial example, and a more realistic protocol could generate hundreds or thousands of test functions, but that's pretty much the whole point of the exercise; a more restrictive set of tests is highly likely to miss important sequences that lead to bugs.

PNTG should actually be pretty easy to implement and might actually not be all that interesting by itself. However, it's an important building block for a more comprehensive automated-testing approach. In my next article I'll go into more detail about unit tests vs. static analysis and what features each would need to make full use of the test functions that PNTG provides.