Hacker News new | comments | show | ask | jobs | submit login
Tis-interpreter – find subtle bugs in programs written in standard C (github.com)
71 points by osivertsson on Apr 9, 2016 | hide | past | web | favorite | 37 comments



Many of these bugs exist only because compiler writers take unjustified liberties with the C++ standard. That the standard permits compilers to interpret memset(0, 0, 0) as __builtin_unreachable() does not justify compilers actually doing so and violating programmer expectations.

I'm sick of victim-blaming here. Packages like tis-interpreter are very clever ways to solve problems that shouldn't exist in the first place. The C standard needs to be changed to redefine a bunch of currently undefined behavior as unspecified or completely defined.


I'm gonna rant for a bit. I see posts like this from time-to-time, and while they're certainly well-meaning there's a good reason why you're not writing the C standard. :-)

> compiler writers take unjustified liberties

How are implementations wrt undefined behaviors unjustified? It's spec'd that way, it's documented that way, there's a good reason why it is that way.

> That the standard permits compilers to interpret memset(0, 0, 0) as __builtin_unreachable() does not justify compilers actually doing so

__builtin_unreachable() is a compile-time hint to the compiler, so for (say) GCC to interpret it that way you'd have to literally write memset(0,0,0) with all constants. Weird example.

Oh by the way, C11 has memset_s, where you can be explicit about what you want. C is good for being explicit. memset() should not try to guess what you mean in an error condition.

> violating programmer expectations.

It's hard to violate expectations that a programmer doesn't have.

While we're talking about “expectations,” let's redefine floating point so that 0.1+0.2==0.3.

> The C standard needs to be changed to redefine a bunch of currently undefined behavior as unspecified or completely defined.

I'd be interested to know how you define, say, signed integer overflow (keep in mind, most DSP architectures don't use two's complement) and invalid pointer dereferences (many embedded CPUs don't have MMUs, please remember them). How about shifting a uint32_t by 32 bits? (x86 and POWER differ on what this does, and I imagine others do too)

C runs on a lot of stuff. Undefined behavior is undefined explicitly _because_ there's not a good solution for every architecture. C gives the programmer the freedom to do what makes the most sense on their architecture and for their use case. Build different higher-level abstractions for desktops and the little signal processor in your phone's modem. There isn't gonna be a solution that works for both. C is for writing fast code in a moderately high-level language. It's not here to make your assumptions for you.

> I'm sick of victim-blaming here.

Alright, I'm sick of this shit on Hacker News. Say something intelligent or don't say anything. Don't use loaded terms like “victim blaming” to cover for your ill-informed opinions on how C should be. If anything, that only downplays real victim-blaming. I don't give a shit what you think C should be. _You're not a victim, you're ignorant_.


Examples you listed would be better made "implementation defined." ie use RFC language with "Programmers should avoid shifting by more than the bitwidth, compilers should produce an implementation defined result, but may specify a trap in this circumstance"

What's your opinion of What every compiler writer should know about programmers? http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201...


My opinion is that we need a What every programmer should know about compilers essay.

I could take that document more seriously if it didn't make compiler writers out to be evil.


I don't understand why the entire operation has to be undefined behaviour. Why not just say that the bitwidth may be truncated to an undefined number of bits?


On x86 the shift only looks at the leftmost 5 bits, so 1<<33 is 2. Whereas elsewhere 1<<33 may be 0. It wouldn't be strange if a platform decided to have 1<<33 throw an overflow fault. The key is that this choice should really be up to the platform, not the compiler


> How are implementations wrt undefined behaviors unjustified? It's spec'd that way, it's documented that way, there's a good reason why it is that way.

Many of these things are spec'd and documented that way because there happened to be some really obscure systems that fell out of use decades ago where the sensible, obvious behaviour wasn't possible - not because the standard-writers expected compiler developers to get a speed boost out of it. C didn't even have the restrict keyword until relatively late in its life, and I'm not sure C++ does even now; enabling aggressive compiler optimizations was not high in the priority list.

> I'd be interested to know how you define, say, signed integer overflow (keep in mind, most DSP architectures don't use two's complement)

Most DSP architectures can't run C code written for general-purpose computers because they don't support byte addressing. As far as I know most or all of them are two's complement though. The main other difference is that they support saturating arithmetic because some code needs it, though since you can't access that from C because signed integer overflow is undefined...

The newest one's complement or sign-magnitude systems anyone seems to be able to find are ancient Sperry-Burroughs mainframes.


You got so worked up about specific examples that you missed the point somewhat.

Consider this mini example:

    void myfunc (int * p)  {
     int t = *p;
     if(p == NULL) { return;}
     *p = t + 1;
   } 
Accessing p before null check is undefined, and causes compilers to deduce that the null check isn't required. It can therefore be stripped, which most programmers would find very surprising.

Edit: yes, the replies are right, I meant to dereference *p rather than just copy the pointer. Fixed and somewhat simplified.

I was trying (badly) to remember this example: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...


One that often gets people is this:

    struct foo {
        int bar;
    }

    void myfunc(struct foo *p) {
        int *t = &p->bar;
        if(p == NULL) return;
        *t = 5;
    }
Is this undefined? Probably. Absent compiler optimizations, it won't cause a crash on any system you're ever likely to encounter because it's not actually dereferencing the pointer, but some versions of gcc have caused security issues in Linux by optimising away NULL checks like this.


I'm not sure that's undefined though. It's equivalent to

  ...
  
  void myfunc(struct foo *p) {
    int *t = (int *)((char *)p + offsetof(p->bar));
    ...
  }
right? In the C abstract machine taking the address of an offset of a pointer is always defined, I think.


It is not always defined. It's defined to take an address to a pointer with an offset within the object's space plus one. Subtracting two pointers to distinct objects is undefined. This is to allow for segmented memory architectures. It's also to allow implementation of garbage collectors by the compiler


FWIW, the tis-interpreter doesn't flag that code (aside from the missing semicolon). I think you're right, though, that it has UB.


I'm not sure this is correct. I think you are referring to the fact that if p was dereferenced before the NULL-check, then the compiler could optimize out the entire conditional statement.

This is true as dereferencing a NULL pointer is undefined behaviour, so is fair game for optimizations. The compiler may assume that NULL pointer dereferencing results in a trap/segfault and that the conditional can never be executed.

If I am wrong, and your example actually exhibits undefined behaviour, I would certainly love to learn why.


Nope, you're right - I meant to dereference the pointer, rather than just access it. D'oh!


That code is well defined.


Doesn't *t = 1 invoke UB if t is null?

Edit: I'm a moron, thanks for pointing out the obvious to me :)


Yes, but note that the assignment occurs after the NULL check. If the grandparent did mean to put it before, then the code snippet would be undefined, but it wouldn't be surprising either.


I guess one could still be evil and pass a pointer to a non-int type to the function. That example is really bad, you don't need a void pointer to show this ub 'optimization'.


That'd still be defined though. It'd just be defined to set the first sizeof(int) bytes of `* p` to 1. ;) void * and (char * ) can alias to anything and the compiler has to make it work.

Of course if you pass a pointer to a type smaller than sizeof(int)-1 bytes then it accesses uninitialized memory which is UB, but that's a different issue.

EDIT: Aaaand I wasn't thinking.

̶E̶D̶I̶T̶ ̶E̶D̶I̶T̶:̶ ̶N̶o̶t̶ ̶o̶n̶l̶y̶ ̶d̶i̶d̶ ̶I̶ ̶m̶i̶s̶-̶r̶e̶a̶d̶,̶ ̶b̶u̶t̶ ̶v̶o̶i̶d̶ ̶p̶o̶i̶n̶t̶e̶r̶ ̶c̶a̶n̶'̶t̶ ̶a̶l̶i̶a̶s̶ ̶a̶n̶y̶t̶h̶i̶n̶g̶ ̶i̶n̶ ̶s̶t̶a̶n̶d̶a̶r̶d̶ ̶C̶ ̶a̶n̶y̶w̶a̶y̶ ̶(̶t̶h̶o̶u̶g̶h̶ ̶I̶I̶R̶C̶ ̶G̶C̶C̶ ̶t̶r̶e̶a̶t̶s̶ ̶i̶t̶ ̶l̶i̶k̶e̶ ̶c̶h̶a̶r̶ ̶p̶o̶i̶n̶t̶e̶r̶ ̶w̶r̶t̶ ̶a̶l̶i̶a̶s̶i̶n̶g̶)̶.

EDIT EDIT EDIT: Actually maybe it can and I shouldn't be reading technical docs at 2am.


That is not correct. The type used to write to the memory is int, not void or char. If the object, whose address is passed to the function is not compatible with int, the behavior is undefined.

You should read about strict aliasing, you will be surprised.


You're right, I misread and misinterpreted that! Thanks.

Somehow I wasn't thinking and didn't realize that `t` aliases whatever was passed as `p`, and dereferencing a non int or char pointer would be undefined there.


On Firefox your edit strikethrough makes the page very very wide.


Maybe you should familiarize yourself with the standard before preaching about how easy it is to comply with it.


No compiler will optimize away the NULL check here.

Your example is plain wrong.


> I'd be interested to know how you define, say, signed integer overflow (keep in mind, most DSP architectures don't use two's complement)

Basically every DSP uses two's complement, and pretty much everything else besides, and has for decades. Most things that give different results based on the representation of negative numbers are merely implementation-defined, anyway. Signed overflow is undefined for a different reason.

  for (i = 0; i < n; i++) {
    foo();
  }
Does that loop execute n times, or (4,294,967,296 + n) times? If signed overflow is undefined, the compiler can assume n is non-negative. If it's even just implementation-defined, the compiler has to check. That in turn may eliminate a whole host of potential optimizations the compiler might have been done.

In general I agree with your point, though. If those kinds of optimizations don't matter to you, you shouldn't be using C. If you want the option for your loops to run (4,294,967,296 + n) times in C, use unsigned arithmetic. Its overflow behavior is well-defined.


> C11 has memset_s

Annex K, so unfortunately that isn't widely available and unlikely to ever be. Also, there is a performance hit for where it is available [0].

[0] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1967.htm


Besides making it optional for C11, from security point of view they don't improve anything in C.

Programmers still need to track pointer and length parameters separately, leading to the usual set of memory corruption.


I'm going to rant right back. You're the one who's misinformed. (And I'm going to attach a disingenuous smiley.)

There's a good reason that I and many other people continue to complain about compilers' adventurous interpretation of the standards. You persist in blaming programmers who clearly indicate the intent of their programs for compiler writers ignoring that intent in search of faster benchmarks, using bits undefined behavior intended to account for platform differences to actually distort programs.

> It's spec'd that way

Yes. So what? The spec is harmful. It is a bad spec. It doesn't reflect C as actually written.

> it's documented that way

Yes. So what? Not every documented behavior is good.

> there's a good reason why it is that way

Absolutely not. memset, memcpy, look and act like normal functions and only have this weird undefined behavior by special dint of the relevant standards. That's very surprising and leads to real bugs.

Other undefined behavior is similar. There's no reason on modern systems to make arbitrary pointer arithmetic undefined. There is no reason to make signed integer overflow undefined either --- unspecified, maybe, but certainly not undefined.

(Except, that is, for loop optimization, but that's a bullshit and lame excuse that compiler writers use to avoid having to do real bounds inference.)

> memset() should not try to guess what you mean in an error condition.

That's not a fucking error condition, and you know it. memset(0,0,0) to any honest person means "do nothing to zero bytes", not "make my program do whatever compiler authors want". memset and memcpy of NULLs can occur in normal program logic, sometimes surprisingly, and there is absolutely no legitimate reason for treating these occurrences as undefined behavior.

> let's redefine floating point so that 0.1+0.2==0.3.

You know damn well that there's a good reason IEEE754 floating point is inexact when expressed in decimal. That's not the case with the undefined behavior that compiler writers currently exploit.

> How about shifting a uint32_t by 32 bits?

Specify that it returns zero or the original value, but don't allow the compiler to consider it unreachable, trap, or do other random shit.

> Alright, I'm sick of this shit on Hacker News.

The tone of your post and others like it is intolerable. It is precisely victim blaming. Compiler writers aren't taking advantage of undefined behavior to account for DSPs: they're doing it to win benchmarks that don't matter in the real world. (The memset issue is particularly egregious.) This process harms users and developers by introducing bugs.

You're the one who's badly-informed, not me. Practically every program, even extremely well-tested ones like SQLite, contain undefined behavior. See http://blog.regehr.org/archives/1292. (Read the whole blog, actually.)

Now, what good does it do say that almost every C program on earth is actually at fault? That's just giving compiler writers license to do whatever they'd like. When even very careful programmers trip over obscure parts of the standard, it's the standard that must change.


Alright, I'll bite, because you make some good points. Having reconsidered, I'm not entirely sure I'm in the right here anyway.

> using bits undefined behavior intended to account for platform differences to actually distort programs.

You can't really distort a program that doesn't have a valid interpretation to begin with.

> Yes. So what? The spec is harmful. It is a bad spec. It doesn't reflect C as actually written.

The spec is written to be cross-platform, and C as it is actually written typically is not cross-platform. Which is fine, actually, since generally programs don't need to run on both bare metal on a microcontroller and on a supercomputer. Portable between similar-purpose processors is enough.

The spec probably shouldn't reflect C as it is written anyway, rather C should be written to reflect the spec....

> memset, memcpy, look and act like normal functions and only have this weird undefined behavior by special dint of the relevant standards.

Can't any function do anything if that's part of its contract? We can write a div(x,y) function that deletes System32 if you divide by 0, and just say that division by zero is undefined.

> There's no reason on modern systems to make arbitrary pointer arithmetic undefined.

Fair enough.

> There is no reason to make signed integer overflow undefined either

That one is actually rather important for performance though.

> (Except, that is, for loop optimization, but that's a bullshit and lame excuse that compiler writers use to avoid having to do real bounds inference.)

https://gcc.gnu.org/contribute.html

> memset(0,0,0) to any honest person means "do nothing to zero bytes"

Yes, we really need more honest people to write compilers.

I think appealing to “honest person” or “what most people would expect” etc is a weak argument. Sometimes the correct behavior isn't what people expect, and sometimes there is no correct behavior.

> memset and memcpy of NULLs can occur in normal program logic, sometimes surprisingly

I believe that'd be an error condition. Check for NULL before you memcpy to NULL. Frankly though the circumstances where you memcpy or memset something that even could be NULL is pretty rare. Usually it's something recently allocated (stack or heap).

> Specify that it returns zero or the original value, but don't allow the compiler to consider it unreachable, trap, or do other random shit.

That would be reasonable. Perhaps some things, such as shifting, could be implementation-defined. I did, I think, ignore the idea that some undefined things could just be unspecified in my original rant.

> That's not the case with the undefined behavior that compiler writers currently exploit.

Perhaps not in all cases, but in many cases there is a good reason for undefined behavior being undefined: it doesn't make sense in the context of the C abstract machine. Derefencing a NULL pointer, for example, may be perfectly valid on an embedded CPU with no memory protection. C isn't defined to “how this should work on my x86_64 Macbook Pro,” it's defined to “how this should work—or not work—on the C abstract machine.” If on some particular implementation of the C machine that means “delete this basic block at compile time” then so be it. You're not entitled to tell compiler writers how to interpret undefined behavior.

> The tone of your post and others like it is intolerable. It is precisely victim blaming.

Yes, the evil evil compiler writers are conspiring to look good in benchmarks and poor programmers are the victims. Victims!

You are so damn ungrateful it hurts. You're not a fucking victim.

> Practically every program, even extremely well-tested ones like SQLite, contain undefined behavior.

I keep pondering whether this is a problem or not. If the compiler can't prove that it's undefined at compile time, then it just depends on the processor and the only problem is that your program is not portable to obscure special-purpose architectures. On the other hand, the fact that any non-trivial program needs to invoke undefined behavior is pretty damning evidence that the spec is insufficient.

I think, ultimately, I concede that the C standard is flawed. But please get over your fucking entitlement complex about how compiler writers take more liberties with UB than you would.


memset with 0 length becomes more likely due to the mess of NULL and malloc/realloc/free


Victim blaming does not apply here. You're using software written by other people - you dont get to decide what it does insofar as to actually modify the source code yourself.


I'm confused. Who uses what and decides what and modifies what???


By using a program you do not write or udjust, you are completely at the whim of whoever wrote the program.


You mean the C compiler?


It's about the standard, not any program


So, is this about the C standard or the C++ standard?


Both standards have many of the same problems.




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: