-
How Many C Programs Are There?
If I choose a size S, can you tell me how many valid C programs exist that are no larger than that size? I’m actually interested in the answer — it’ll help me make a point in a paper I’m writing. Shockingly, the Internet (or at least, the part of it that I looked at…
-
C Puzzle: Double Trouble
I ran into an interesting C program that both of my C oracles (KCC and Frama-C) consider to be well-defined, but that are inconsistently compiled by the current development versions of GCC and Clang on x86-64. The results: [regehr@gamow 1]$ current-gcc -O1 small.c ; ./a.out 1 [regehr@gamow 1]$ current-gcc -O2 small.c ; ./a.out 0 [regehr@gamow…
-
Randomly Testing a Static Analyzer
Static analyzers are intended to find bugs in code, and to show that certain kinds of bugs don’t exist. However, static analyzers are themselves large, complicated programs, leading to a “who watches the watchmen” problem. Pascal Cuoq, one of the people behind the excellent Frama-C analyzer, took it upon himself to run the fuzz-fix cycle…
-
Avoidable Failures of Peer Review
This piece is about a specific kind of peer review failure where a paper is rejected despite there being sufficient evidence to warrant acceptance. In other words, all the facts are available but the wrong decision gets made anyway. In my experience this is extremely common at selective computer science conferences. The idea here is…
-
Tricking a Whitebox Testcase Generator
The awesome but apparently discontinued Underhanded C Contest invited us to write C code that looks innocent but acts malicious. Today’s post is an alternate take on the same idea: we don’t really care what the malicious code looks like, but it needs to escape detection by an automated whitebox testcase generator. In some respects…
-
Discovering New Instructions
Sometimes I wonder what instruction sets are supposed to look like. That is, what instructions would there be if computers were redesigned by smart people who understood our fabrication capabilities and who knew what we wanted to accomplish using computers, but who didn’t care about backwards compatibility and who haven’t seen our architectures? We can…
-
Wanted: Epitaphs for Hot Topics
Any given research community always has a few hot topics that attract an inordinate number of paper submissions. Sometimes these are flashes in the pan, other times they mature into full-fledged areas having their own workshops and such — but most often they endure for a few years, result in a pile of PhDs, and…
-
It’s All About Interfaces
The Frank system — see also this recent post — is intended to reduce the amount of code needed to create a usable desktop software stack by about 1000x. I’m pretty sure that this goal is sufficient but not necessary. In other words, if we can reduce software size to 0.1% of its current size then that’s…
-
Can Simplicity Scale?
Software has gotten really big, with many systems — even, apparently, cars — running into the hundreds of millions of lines of code. The drawbacks of code bases this large are numerous: they are hard to understand, hard to modify, hard to test, and virtually guaranteed to contain huge numbers of bugs. My understanding is…
-
NSF Data Management Plans
As of a year ago, all grant proposals submitted to NSF must be accompanied by a data management plan. Basically, the PIs must explain: how sensitive data (for example, data that contains personal information about experimental subjects) will be managed how data resulting from the research will be archived and how access to it will…