Property-Based Testing

Note:

Learning outcomes

This is a language-agnostic programming assignment.

Programming language; machine

Programming language

You may use any programming language to complete this assignment, with instructor permission. Permission is granted by default for two programming languages: Python and Rust, for the following reasons:

• Python: Everyone registered for this class has some experience with Python, so this is likely simplest way for many students to complete this assignment.
• Rust: Rust is a (relatively) new, modern language for safer systems programming. The implementation assignments in this class, with the associated Workshop session, provide a chance for you to pick up a new programming language if you would like a bit more of a challenge.

Whatever language you choose, your submission must conform the input-output specification (described in the next section).

The January 31 Workshop session is dedicated to launching this assignment.

Machine

You can complete this assignment on any machine with a UNIX-based file system (your own Mac OS or Linux machine or the department's CS Linux server). If you have a Windows machine, you can still develop locally, but should test your code on the CS Linux server (e.g., using the VSCode remote server extension; post on Zulip if you need help with this).

Assignment description

The problem

You are a software engineer at an organization that produces many related software packages. Your team wants you to take a look at implementing an automated dependency management system.

Each software package your team produces has some number of dependencies. If package X has dependency Y, that means your system should install package Y before it can install package Y. For example, package Y could be the numpy package for manipulating data, and package X could be a scientific computing script.

Your task is to determine, given a list of dependencies, what order to install packages in. ( This is a problem encountered by real package management software, such a pip for Python, npm for JavaScript, and Cargo for Rust).

For example, you might be given the following list. You should read each line P Q as meaning "P is a dependency of Q".

B A 
B C 
A C 
D A 

For this example, a correct output would be:

B
D
A
C

Meaning: install package B first, then D, then A, then C.

D
B
A
C

The algorithm: topological sort

The problem from the previous section resolves to a classic graph theory problem. A valid list of dependencies should form a simple, directed acyclic graph, where packages are vertices and dependencies are directed edges (going from the package that must be installed first to the package that must be installed after). Let our graph be $G=(V,E)$. Finding a valid order of installation is equivalent to finding a linear ordering of vertices such that for all edges $(u,v)$ in $E$, $u$ precedes $v$ in the ordering. This is known as a topological sort, or topsort for short.

Another example of topological sort is determining the order of spreadsheets formula cell evaluation. You have almost certainly done your own informal topological sort to determine what order to take your Wellesley Computer Science classes, given the list of prerequisites!

Depending on the graph, many valid topological sorts may exist for each of these problems.

Your tasks: topsort, oracle, and README

You will write two programs for this assignment:

In addition, good software engineering practice is to document your software. I expect your code to be well-commented, and part of your grade will be based on design and style.

Most public software engineering projects have a top-level file called README.txt or README.md. The latter filetype is Markdown, a very useful formatting style used by many open-source software projects (e.g., most projects on Github) as well as the CS340 lecture notes and assignments (the pretty colored boxes are from a particular variant of Markdown popularized by Github).

I encourage you to use a private Github repository for this assignment, (1) to practice using Git, which is a useful systems-engineering skill, and (2) to make it easier to recover from mistakes. Refer to the CS240 resources if you need a refresher. Using Git is not required (and be sure to not use a public repository, since everyone in the class is completing the same assignment).

Part 1: Algorithm implementation, topsort

I suggest that you implement the topological sorting program using the following pseudocode:

	function topsort(g): // g = directed acyclic graph
	    L = empty list to store ordering
	    S = set of vertices with no incoming edges
	    while S is not empty:
	        u = vertex removed from S
	        append u to L
	        for each vertex v where edge e = (u,v) in g:
	            remove e from g
	            if v has no other incoming edges in g:
	                insert v in S
	    return L

Since your program will ultimately just read and write number from standard in and out, much of your implementation is up to you. You use any appropriate data structures in your chosen language to represent the graph and the queue (for example, just Python list or dict may suffice, depending on your design).

Your implementation of topsort should be a standalone executable. More on that in the Input-output specification section.

Part 2: Property-based testing, oracle

For the second part of this assignment, you will build an automated testing oracle for topological sorting programs based on the concepts of property-based testing that we covered.

Your oracle program will consume the file system path to a topological sorting program and the number of inputs to generate, n.

Your oracle should generate n valid input graphs and write each of them to the provided program's standard input. Your oracle will check that the output provided by the topsort executable is in fact a topological sort of the corresponding input. Note that your oracle should call the topsort implementation n times.

If the provided topsort produces a valid topological sort for all n graphs that you have generated, then your program should exit with status 0. Otherwise, your program should exit with status 1. The oracle should not write anything to standard output or standard error.

You may be worried about what your oracle would do about a deviously-slow topsort implementation. For this assignment, I will not test against any very long-running topsort implementations.

In general, it would be impossible to write an oracle to get around the "long running" problem.

Input-output specification

System topological sort implementations model graphs in a simple text format, where each line has two space-delimitated values that represent a single directed edge.

For example, consider the following directed acyclic graph:

The expected text format of this graph is:

  7 11
  7 8
  3 10
  5 11
  3 8
  8 9
  11 10
  11 2
  11 9

where each line represents a directed edge with each vertex name, an alphanumeric, case-sensitive string of any length, separated by a space (in the example of 7 11, vertex 7 comes before 11). Note that the order of lines does not matter.

The expected output of a topological sort in this text-based representation is in this form:

  3
  5
  7
  11
  8
  9
  10
  2

where each line contains a vertex name in topological order from top to bottom.

Testing your testing

You'll want to perform multiple checks of both of your executables.

Testing your oracle against the system tsort

First, you can test your oracle by using a known-correct (although not formally proven correct!) implementation of topological sort.

Most UNIX-based systems also come with a command-line topological sorting utility installed (and this assignment matches the utility's input-outport format). To check if your system has this installed, run which tsort (note the different spelling). On CS Linux, this is installed at /usr/bin/tsort.

./oracle /usr/bin/tsort n

Your oracle should exit with status 0 on the system tsort.

echo $?

Testing your topsort with your oracle

You also (hopefully!) have your own correct topsort implementation from part 1.

./oracle ./topsort n

Testing your own BROKEN topsorts with your oracle

To ensure your oracle detects incorrect topological sorting programs, try running it on deliberately broken implementations of your creation! You can do this by copying your implementation to a different files with different names, and passing those paths instead.

./oracle ./bad-topsort-1 n

Your oracle should exit with status 1 on these broken programs. Detecting incorrect implementations is arguably more important than detecting correct implementations!

Grading

I'll assess your topsort and oracle programs by running them against different implementations. I'll also assess your code and documentation.

This assignment is worth 100 points, broken down by:

Submission

Submit your code and README file via Gradescope.

Extra fun

If you're hungry for more, try out these ideas (which could get up to +5 extra credit). If you do either of these, please (1) implement them in a different copy of your file, and (2) document this in your README.

1. Adapt your topsort implementation to detect cyclic input.
2. Adapt your oracle implementation to terminate topsort processes that run for longer than 2 minutes.

Real-world context

Out in the wild, many software engineering projects use some form of fuzzing or property-based testing. On Thursday February 1, we'll continue our discussion of this in class.

In particular, there are many libraries that make it easier to generate randomized tests, such as QuickCheck for Haskell (one of the projects that popularized this approach!), Hypothesis for Python, and PropTest or Bolero for Rust.

Software engineers on existing projects often use these libraries rather than implementing their own oracle from scratch like we did here. Implementing from scratch is useful for understanding how the concepts work, but I encourage you to consider these libraries for future implementation projects both inside and outside of CS340.

Attribution

This assignment is based on a previous version of the Oracle assignment from Tim Nelson's Logic for Systems at Brown University.