Pointers Gone Wild | Hacker News Reader

Pointers Gone Wild

goto.ucsd.edu

132 pointslelf65 comments

Shameless plug: I just implemented a simple refined type-checking algorithm. It can statically prevent division by 0 and Heartbleed (if functions are given the correct contracts) and is much simpler than I expected. It uses Z3 to prove that the code is correct.

https://github.com/tomprimozic/type-systems/tree/master/refi...

Edit: I submitted it as a separate story here: https://news.ycombinator.com/item?id=7826175

I have to admit, the more I look into Haskell the less enamored I am of its syntax. Sure, it's wonderful in the common case, but when it comes to things like vectors or (apparently) unsafe pointer manipulation, it's practically unreadable. Something like Lisp or Python— or even C++— syntax is rarely optimal, but at least it never degenerates this totally into symbol soup.

They don't degenerate when tryin to achieve type safety?

You won't see (#a,b#) in client code, that's hidden behind the facade of a library, unless you are very desperate. Nor will you use pointers.

So... this is somebody else's problem and smarter people will take care of it for me?

I've never found that answer very satisfying...

Do you assemble your own machine code as well or do you trust that someone else has taken care of the gritty details of the assembler so that you can work at a level of abstraction higher than that?

Assembling a program into machine language is simple enough that it's easy to trust someone else to get it right.

I imagine it depends on the difficulty of the problem being outsourced.

Have you seen what optimizing compilers do? I'd hardly call that simple!

Thought it was clear the OP was talking about assembly?

Which, thanks to pipeline stalls and out-of-order execution is no walk in the park these days, but it's not TOO bad.

> So... this is somebody else's problem and smarter people will take care of it for me?

Smarter is your opinion. Is a library writer smarter than an app developer? Is a compiler writer smarter than a library writer? Perhaps, though I don't see how that is a given. I look at it more like; compilers will be used by more people than a single library, so it pays off to spend more time on developing, testing, debugging, etc. it than a library. A library might be used by more clients than a single app, so it pays off to use more time on it and optimize it, which might include unsafe features.

If people that work "further down the stack" are necessarily smarter than those in the upper layers, we programmers must be pretty stupid... :)

Bjarne says in his book that he wanted to make C++ implementable with just nothing more complicated than a linear search.

Things didn't quite work out that way, but it's a good principle for language designers to live by.

If you don't know how to implement the languages you use, then either you or the language is at fault, IMO.

That's a pretty absolute rule to live by. I think there is merit in the idea - it's nice to be able to easily know what is going on. If I was making a language - and I could do as I wanted - I would make try to make the compilation step fully "debuggable", ie being able to step through the whole compilation, even stop and modify things, mess around, etc. Compilers seem awfully black-boxy, in general.

(Forth might be one of the ultimate expressions of the principle of a fully understandable compiler - Chuck Moore even hesitates to call it a compiler.)

On the other hand, you can get very far without really losing anything if you just know the semantics of the language, and leave the nitty-gritty to the compiler. C is supposed to be simple, but given how big of a deal optimizing compilers for C seems to be, it's not straightforward to make a proper, industrial standard compiler for the language (perhaps both with regards to competition and effort). And yet C is supposedly just a thinly-veiled abstraction over assembly ("supposedly" since I'm not a C programmer).

I for one welcome giant, too-big-to-understand-for-one-person compilers, as long as they are awesome at what they do. Simple programming language? Then you seem to get complicated design patterns. Simple semantics ala "everything is X" (immutable, object, ...)? Then you get complicated work-around in the places where you can't/don't want immutability/objects... . Simple compiler? Lot's of responsibility and mental overhead for each individual programmer, in a sense duplicating a lot of the effort that could be handled by a team of compiler writers, once.

Works for libc.

This code here isn't representative of any Haskell end-users would write, it has a whole other syntax (LiquidHaksell) layered on top of it that augments the type system and it imports the internals of GHC.* libraries to work with the base machine types. The strength of GHC's implementation is that a lot of the compiler internals are directly accessible in the frontend source language with certain language extensions enabled (GHC.Exts, GHC.Prim, ``-XMagicHash``).

That said the code here is more about the implementation of the vector library internals at a very low level that deals with machine types. If you're a Python user this is effectively equivalent to reading the NumPy internals which I can tell you first hand are an ungodly mess of preprocessor macros and code generation gone horribly wrong and far worse than this.

You should expect code that breaks out of the safe environment the language tries to build for you to be ugly. To be unworkable even. If it is not, then that means that the language has been optimized for unsafe usage, and whatever clean syntax was chosen could have been used better somewhere else.

Just curious what would you think has good syntax that you would enjoy?

I always thought Python to be one of the most approachable for example. Then maybe C. I also like Erlang.

More in depth:

Python is closest to pseudocode. As in, if I sat down and wrote an algorithm, in some pseudocode language, it would probably look a lot like Python.

I like C and Erlang because they are relatively small and self-consistent. Think of it as chess, there are not too many rules of the game, but the game can still be very interesting. Erlang is a good example of a practical functional language. I really like pattern matching in it.

I don't like C++ for example because the syntax is too complex. Too many exceptions, rules and corner cases.

I don't have an opinion on Lisp/Scheme/Clojure/Haskell just because I haven't tried using them in depth.

I'm not a Haskell programmer, but I'm having trouble understanding how this is applicable to Heartbleed type bugs. While it's nice to flag invalid constant indexes at compile time, the real problems occur with variable indexes that a potential attacker can control.

And the solution for those seems to be the equivalent of "Don't use 'array[i]', always 'if (i < len) ? array[i] : BOOM'". Or am I misinterpreting we have passed the burden of proof onto users of charAt? I guess the difference is that the check only needs to be done once for each 'i' at the time it is assigned/created? But then how does one guarantee that a given AValidI is used with array for which is intended, and not for a shorter one?

We only used the constant indexes for illustration. The system checks, at compile time, that values that are controlled by the attacker (e.g. inputs) are properly sanitized. See this:

http://goto.ucsd.edu:8090/index.html#?demo=permalink%2F14014...

that uses Lists instead of pointers, for a short example.

This shows me some surprising information -- Haskell is susceptible to heartbleed-like problems like C!

Of course, you can write your own safe wrapper which checks deference, but one could just as easily (in fact, I think more easily) write such a thing in C...

Compile time checks are quite a big step up from runtime (assert) checks.

The problem with 'silver bullets' is that they are relatively untested. Once you get mass deployments of Haskell in the hostile environment that is the web these days it will become apparent whether or not the safety argument is as strong in practice as it is in theory. That is assuming that it will see such mass deployment which is not a foregone conclusion.

That does not mean that it isn't good there are people trying to give us safer languages, but there is something disconcerting about the ease with which presumably bullet-proof Haskell can be made to do unsafe things like referring to out-of-bounds data, even if the reason is 'performance'. The whole idea was (or at least, that's what I thought it was) that you can get there at reasonable speed without giving up the safety net. Like this you might as well go the whole hog and program in C after all... It's a bit like making a vault that has the front door hinges and the lock screwed on from the outside.

Compare with like Linux on the desktop not having too many viruses and such. The viruses aren't there because nobody is motivated enough to write them given the small distribution footprint of the OS. The money isn't there for the virus writers. Not because Linux is somehow magically resistant to viruses (though it does a few things better than say Windows).

The number of people trying to bust down the barriers is roughly proportional to the size of the deployments, and I suspect that Haskell when put to the test will eventually turn out to have it's own (different) class of problems that have nothing to do with the class of problems that plagues the C like languages.

Just like interpreted languages have a unique set of problems and virtual machines have their own. Silver bullets are rare.

Viruses are harder on Linux because running random binaries is not a common usage pattern.

Linux is exploited via remote execution or by passing payload data to be processed by the user using known vulnerable programs. The latter is harder to pull off.

Getting access to Linux systems is not usually a problem of Linux itself. It happens a lot more than you think.

>running random binaries is not a common usage pattern.

Nor is checking the source code to whatever module or tool you need to compile and run.

That's what package maintainers are for, it would be a highly targeted attack if any of the code I compiled managed to be compromised. I would be impressed at being so important.

As a fellow relatively new to Haskell, I was surprised at all the unsafe constructs in the core. Almost everything you'd expect to find in C's standard library is exposed somewhere, with roughly the same level of safety. (Which is to say, almost none.)

The main difference I find between the two is that I have never needed to reach for an unsafe construct in Haskell myself - including some networking / parsing code that lives at roughly the same level of the stack as you'd find the heartbleed bug. The 'unsafe' functionality I use is encapsulated in libraries which expose a safer, higher-level interface. (Which is roughly the situation in Ruby with C bindings or Rust / Go with `unsafe` blocks.) I do feel there's a significant difference between a language where you need to be more-or-less constantly vigilant and one where you can isolate the memory management to a small, well-vetted library, but it's true that the situation still isn't ideal. (I think Haskell's story is much better as you move up the stack, but that's another story...)

But if you're interested in a stronger level of safety in Haskell, you may be interested in Safe Haskell[0] -- it disables many of the unsafe features (or requires uses of them to be explicitly 'trusted') and thus provides much stronger safety guarantees.

[0] http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/safe-...

Does Go have unsafe blocks? I was under the impression that it was similar to Haskell, with the really bad functions just in an `unsafe` module (or something like that?).

Sorry, editing error... meant to refer to unsafe blocks in Rust, and the unsafe package in Go.

It shows that, if you need to, you can drop to direct memory access in Haskell. Also note the "unsafe" in the names of the functions. Of course, the majority of Haskell code uses algebraic data types and garbage collection.

And you can even segfault it with unsafePerformIO!

… Now go read rest of the post

> Of course, you can write your own safe wrapper which checks deference

You don't generally. unsafe* functions practically are only used in libraries where you really need C-level speed. The next level of abstraction is their public API.

The openSSL programmers were terrible C programmers, who seemed to make an active effort to disable any safety feature C implementations provided if it could gain them the tiniest speed improvement. I have no double they would have called 'unsafe' functions everywhere in Haskell.

Certainly Haskell does have advantages over C (better type system, garbage collection), but I feel this article does a bad job explaining them an introduces a sausage to fortune by talking about Heartbleed.

Maybe I'm naieve, but I think perhaps the problems with OpenSSL had come to light a little bit sooner if all dangerous code had clearly been marked 'unsafe'.

I would not expect any unsafe calls in a crypto library. It would defeat almost the whole purpose of implementing a crypto library in Haskell. It would be like implementing a web application in Ruby, and then using static type annotations everywhere using some eDSL.

BTW, I don't think this article is meant to argue the advantages of Haskell, it is meant to describe a solution to a problem in Haskell.

Now wandering further off-topic I realise!

I think everyone who had ever looked at the code for OpenSSL (including myself) knew it was an unsafe time bomb waiting to go off, it's just no-one could be bothered to replace it, or do the basic complete re-engineer the BSD folks are now doing.

It's easy to point fingers, but I think any library which handles strong crypto over network sockets is going to be pretty hairy. I bet that if I showed you a random 100 lines from the "LibreSSL" code and a random 100 lines from the "OpenSSL" code, stripping out all identifiers, that you wouldn't be able to tell which library is which by judging quality alone.

That sounds like a fun experiment, actually. Someone should go and make that.

> I bet that if I showed you a random 100 lines from the "LibreSSL" code and a random 100 lines from the "OpenSSL" code, stripping out all identifiers, that you wouldn't be able to tell which library is which by judging quality alone.

That's quite easy. In 100 lines of OpenSSL you have 6 nested #ifdefs and the code is unreadable formatted.

You definitely need to use unsafe Haskell code in order to implement most cryptographic primitives in a way making them resistant to timing attacks. You simply have to be able to write constant-time primitives, and this is not possible in Haskell without unsafe.

The point of this blog post is how to enforce memory safety at compile time even when using unsafe.

Why isn't it possible? The safe versions just do bounds checking, which still seems constant time to me. If you mean that somewhere in the stack something must do pointer math you're right, but that's a given whatever you do crypto or not.

My response was to tinco in respect to the use of unsafe in general when writing crypto code, it wasn't about the particular use of unsafe in this article... (which isn't about crypto anyway, so how could it be?).

I'm disagreeing with this statement: "You definitely need to use unsafe Haskell code in order to implement most cryptographic primitives in a way making them resistant to timing attacks."

Safe indexing is constant time too, unless you're out of bounds and you have to process the exception, in which case your program is wrong anyway.

I think you're right, you could even write a monad/language extension in which it's only possible to perform constant time operations effectively ruling out a class of vulnerabilities.

I'm not sure you could do that with a monad. They still let you use whatever pure function you want, which can have arbitrary complexity.

You could wrap your operands in a type with a bind function that takes a function argument that has to be marked constant time. I guess it wouldnt strictly be a monad. You would then have to trust the implementor that he does not mark any non-constant time functions as being that, but I think that is reasonable.

> Maybe I'm naieve, but I think perhaps the problems with OpenSSL had come to light a little bit sooner if all dangerous code had clearly been marked 'unsafe'.

After listening to Bob Beck's talk[1], I think people did know how unsafe that code was but no one wanted to take a shot at fixing it until it all went bad. At 2:12 into the video (the Jon Snow slide), he explains why nobody looked (or admitted they looked)[2]. Code can be so bad in any language to discourage people from even attempting to figure out how it works.

1) https://www.youtube.com/watch?v=GnBbhXBDmwU

2) quotes "Why did WE not look" & "It is your parents talking about how you got made horrible"

You can deeplink YouTube videos thusly: https://www.youtube.com/watch?v=GnBbhXBDmwU#t=130

At least you can `grep unsafe` to get an (approximate) list of the places that are the most dangerous... the equivalent command for C is `cat`.

I don't think that C has any safety features; there are tools to help you find where you are being unsafe (e.g. static and dynamic analysis) and tools to mitigate the effects of the unsafe code (e.g. memory randomization, canaries, etc.).

> You don't generally. unsafe* functions practically are only used in libraries where you really need C-level speed. The next level of abstraction is their public API.

I agree. Who could ever think in using unsafe* functions?

Any language that has C FFI is susceptible to heartbleed-like problems.

completely off topic, but very nice nonetheless: when you hover above a code fragment, you see the type of the expression as a tooltip. Indispensable for reading Haskell on the web

Personally, I think all the talk of "language safety" is overhyped. Bugs like heartbleed occur because of programmers not reasoning correctly about their code. In particular, is it really that hard to know how large some block of memory is, and not access beyond it? It's such a ridiculously simple concept, but I feel like all the high-level languages with their automatically expanding data structures have only made this problem worse, by trying to hide this behind many layers of complexity (as evidenced by this article.)

In my opinion, if you are writing code that is performing array indexing, and are even the slightest bit uncertain about the size of the array, then you should not keep going, but stop and think a bit more about what it's doing. Language safety is not a replacement for true understanding.

Yeah, Real Programmers don't need safety.

http://en.wikipedia.org/wiki/Real_Programmer

Spare us the hyperbole and the misrepresentation, please.

userbinator makes a very valid and legitimate point: regardless of what safety features a programming language may or may not offer, it's still critical for the programmer to understand exactly what's actually happening.

You can't have true safety through tools alone. Operator knowledge is just as critical as whatever safety features the tool may offer.

Given layers upon layers of abstraction, it's often impractical for the programmer to understand exactly what's actually happening. Indeed, that's the entire premise for the existence of more safe languages, which (hope to) eliminate entire classes of bugs.

"true safety" like "true Scotsman"?

Realistically, you get "better safety". Operator knowledge gets you better safety. Better languages get you better safety. Better libraries get you better safety. Better testing gets you better safety. Often, each of these has diminishing returns, but that just means that the best outcome is one where don't over-focus one at the expense of others.

The problem is programmers are humans and humans make errors (lot's of them.) Any model that relies on humans being perfect is fundamentally flawed. It's why all software has bugs. And sometimes those bugs endanger the whole internet or crash your car. The higher quality your team is, the higher quality their tools and automated tests the fewer bugs you will have. The more complex your code the harder for humans to understand and the more bugs you will have. It's a tradeoff, and I'm personally not certain on which sidebof the tradeoff this code is. Since most of the nastiness is on the library side, probably it's a good thing.

I don't like this spin on humans as imperfect compared to the perfect computers.

Of course humans will make more mistakes, when the immense complexity of the business logic models they deal with surpasses what even the most advanced computer can process today.

Plus, computers also make mistakes. They fail in arbitrary ways, and may produce an arbitrarily wrong result when you least expect it (say, if they overheat).

I think a distinction between "perfect" and "imperfect" can easily be made, in this case.

Computers are great at executing algorithms, and never learning from their experiences. Humans are great at learning from their experiences, but pretty hit-or-miss when it comes to following algorithms. It is probably exactly that learn-ability that trips us humans up: we can learn new and beneficial things, but the flip side is that we can learn the wrong things. Clearly, we need both of these traits (predictability, learn-ability), and should probably delegate the tasks according to each others strengths.

Of course, there is nothing fundamentally different between computers and humans (modulo some philosophical assumptions); in principle, we could implement very complex artificial neural networks, to the point that computers being deterministic might be as much of a useless distinction as considering sociological phenomena as deterministic - fine in a deterministic universe, but a pretty useless perspective for all practical purposes given the immense set of variables. We then gain learn-ability, or AI, but we also lose predictability. So we would probably still delegate the task of compiling programs to a very deterministic program over an incredibly advanced AI that, while sometimes having some good and creative insights when it comes to generating output code, sometimes also learns the wrong stuff and gives us just flat-out wrong output.

Sure there are hardware errors too. But in the context of this discussion getting the compiler to check for bugs at compile time vs having runtime failures leads to less buggy software. The more you can push that burden onto your tools, which are far more perfect than human beings, the better.

Humans are humorously bad at reasoning about large software systems written by a large number of people. Even if all the code you personally write is locally safe, it's very very difficult to guarantee that the interaction of it with all other components written by other people is itself safe.

That's why formal methods ( type systems, model checkers, ... ) are extremely important, the only to reason about programs in the large is to prove properties of the system that are machine-checkable and remove the need for manual proofs that admit error.

If people are humorously bad at reasoning about large software systems, why would they be any better at reasoning about large type systems?

Because type systems, at least in the ML tradition, reduce down to systems of logic that we already know how to prove properties about. We can prove progress and preservation of a type system, and we even have systems to mechanically check those proofs.

> is it really that hard to know how large some block of memory is, and not access beyond it

Considering that developers have been making this error pretty much every single day for the past 40 years, I'm gonna go with 'yes'.

> is it really that hard to know how large some block of memory is, and not access beyond it?

For one given block, maybe not. The problem is that in a language like C, the fallible human must get every single one correct, otherwise it's a bug waiting to promote to a security flaw. Not only must you get array indexing right, but also pointer dereferencing right, avoid dangling pointers, be mindful of the interaction of aliasing and mutation, etc. This is a lot for a person to never mess up. This is also the reason why projects like Rust exist: they start with the premise that humans will fail and provide tools that prevent the common mistakes.

> In my opinion, if you are writing code that is performing array indexing, and are even the slightest bit uncertain about the size of the array, then you should not keep going, but stop and think a bit more about what it's doing. Language safety is not a replacement for true understanding.

What if you are very sure that your code is correct, but five months later someone modifies code elsewhere in the program that aliases to this array and reallocs() it?

Not only must you get array indexing right, but also pointer dereferencing right, avoid dangling pointers, be mindful of the interaction of aliasing and mutation, etc.

All those things are just part of the logic of the program, which must be correct in any case. Even in safer languages, you still have to write correct code, and if you believe that humans can't reliably get simple things like array sizes correct, how would they do any better with the more subtle kinds of logic errors?

What if you are very sure that your code is correct, but five months later someone modifies code elsewhere in the program that aliases to this array and reallocs() it?

It depends on the specific case but I would tend to believe that someone is not modifying the code correctly (e.g. failing to update the associated size), because they have not understood it.

The mentality of "bugs are normal, and we should restrict languages as much as possible because people might do the wrong things otherwise" is what irks me the most, because proliferating the assumption that perfect code can never be written leads to a self-fulfilling prophecy.

All those things don't need to be correct in any case. The fact that Heartbleed existed for so long shows that the program worked just fine with the broken code.

Heck, bugs in general are usually code that works in some cases, but not every case. Having a type system to catch all that throws out a ton of classes of bugs.

Here's how I think of it: there are things humans are better at and things computers are better at, and whenever possible we should let the computers do things they are better at. One thing computers are better at is keeping precise track of a bunch of minutia threaded through a bunch of different contexts. Array indices are precisely that sort of minutia, and we should let compilers (or interpreters) take care of it for us to the extent possible.

Reply on news.ycombinator.com