K Framework Seeking Professional Developers

5104335The K Framework provides extensive support for writing and validating formal semantics of programming languages, and using these semantics to execute, analyze, and even verify programs. We are part of a new joint effort to advance the implementation of the K framework – and we are now hiring for this project. The organizations involved are

Positions for professional developers are available at RV, IOHK, and ADSC. The K website has full details on the projects and the available positions.

Undefined Behavior Review: tis-interpreter vs. RV-Match

John Regher’s blog is a great source for anyone concerned about undefined behavior in C programs. The latest installment Undefined Behavior in 2017, written jointly with Pascal Cuoq, reviews the state of popular tools for detecting important categories of undefined behavior, and describes a new tool tis-interpreter that they have been working with.

At Runtime Verification we are big proponents of dynamic program analysis and rigorous error detection, so we were excited to hear of another tool following a similar approach to our own undefined-behavior checker, RV-Match(which is the commercial continuation of the academic kcc tool). We tested the most recent available version of tis-interpreter against RV-Match. With roots in the Frama-C verification project, we would hope tis-interpreter is faithful to the C standard – or become concerned that Frama-C could “prove” wrong code correct. We found that tis-interpreter detects many fewer errors than RV-Match, and has missing or incorrect implementations of several language features and almost all library functions. On the positive side, their examples revealed a few errors in RV-Match, which we have now fixed. We will update this post for improvements in tis-interpreter.

Continue reading

Experienced C Developers Can Still Misunderstand Simple Language Concepts

Not long ago, one of our customers came to us confused about an analysis report on a simple program their company used internally to assess knowledge of C. Among the code they sent us was something like the following three lines:

int32_t var = 0xffeeddcc;
int32_t var2 = 0x7f000000;
var2 <<= 8;

They assumed that this code should be free from defects, and thought that possibly the two defects we reported were incorrect. Let’s take a look at the error reports that result when we insert these lines into a simple program and execute them:
Continue reading

14% of SV-COMP’s “Correct Programs” are Undefined!


Last April (2016), I gave a tutorial on K at ETAPS’16 in Eindhoven, Netherlands, where I also demonstrated RV-Match.  During the week that I spent there, I heard several friends and colleagues who were involved with the Competition on Software Verification, SV-COMP, that some of the benchmark’s correct programs appear to be undefined.  What?  So some of the assumed-correct C programs that are used to evaluate the best program verifiers in the world are actually wrong programs? Continue reading

Using RV-Predict to track down race conditions

We’ve all had it happen: you write some multithreaded code, but when you run it, it crashes with some kind of error every second or third or hundredth run. The traditional way of trying to debug this problem is very tedious and involves attempting to reproduce the error (difficult) and then tracing the inconsistent state backwards to find the source of the race condition (even more difficult).

Enter RV-Predict. Today I was developing code for RV-Match when I ran into an intermittently occurring NullPointerException in its parser. Instead of trying to reproduce the bug and tracking its behavior backwards, I assumed going in that it was caused by a race condition, and ran RV-Predict on the program. After it crashed, it spat out the following error report: Continue reading

“restrict” keyword in header files

It would appear that Mac OS X’s copy of string.h is invalid.

It declares strcpy as

char *strcpy(char *, const char *);

But the C standard declares it as

char *strcpy(char * restrict, const char * restrict);

These two types are actually incompatible with each other according to the C standard, and a function that is declared  more than once in different translation units with different declarations is considered undefined behavior. Thus, any correctly conforming C library will cause any code that includes string.h to be undefined.


Undefined C: Common mistakes

This blog post is the beginning of an intended series of blog posts detailing undefined and unspecified behavior in the ISO C standard, and its impact on development. To start with, we will summarize the domain and provide information about some of the undefined behaviors which we have found to be most widespread in production-deployed C code of the open source projects we have tested.

Continue reading