Jordi Wippert
← All writing
· · 2 min · #cs #paper

Wlp testing

“wlp-based Automated Testing”

Abstract - In this paper we describe our process and solution for creating a wlp-based automated testing tool for the GCL language given in (“Project: wlp-based Automated Testing” 2018). First, we describe how we can represent the GCL programs as instances of our internal datatypes. Afterwards, the generation of paths is discussed, along with a solution to the infinite-while paths problem. After this, generating a WLP based on these found paths is discussed. This WLP will then be translated to a DNF in order to function as the input for our solve function that tries to find counter examples for the given propositions. Finally, the addition of program calls is discussed, along with how to inline these calls and deal with the problem of shadowing variables.

Two fellow students and I built this tool in Haskell for the course Program Semantics and Verification. It tests programs written in GCL, the small Guarded Command Language used in the course, by searching for counterexamples: input values that make an assertion in the program fail.

From program to paths

A GCL program is represented by two Haskell datatypes, one for statements (skip, assert, assume, assignment, if-then-else and while) and one for expressions, including arrays and quantifiers. Before anything else, program calls are inlined and local variables are renamed, so a variable inside a called program can’t shadow one with the same name outside it.

The tool then generates the paths through the program. An if-then-else splits into two paths, one that assumes the condition and one that assumes its negation. A while loop could in theory go on forever, so it is unrolled a limited number of times, and paths longer than 200 statements are dropped.

From path to counterexample

For each path the tool computes the weakest liberal precondition, the wlp, and rewrites it to disjunctive normal form, a set of alternatives of which only one has to hold. The solver is our own: it narrows every variable down to a range of possible values by fixpoint iteration, picks a value from each range and checks whether that assignment, which satisfies what the path assumes, also satisfies what it asserts. If it doesn’t, the tool prints it as a counterexample. The test programs came from the course assignment, such as swapping two elements of an array and finding the index of the smallest element.

GitHub repository (access on request)
CS Course: Program Semantics and Verification

Disclaimer: The above content and related documentation, papers, essays, code and other references, were created during a course of the MSc Computing Science. No rights can be derived from the content. Much work has been done in collaboration with other students. If there is any reference to your person in any way that you would like to see removed or to be named (more) explicitly, at any time, please let me know.

Tags

← A Haskell DSL for expressing music: CoLa (Compose Language) Estimating the Uithoflijn’s operational performance with simulation →