7 ms·

I'm wondering about a situation where forgetting a strictness annotation is the analogous Haskell situation of forgetting to bounds-check some input. There are

I'm wondering about a situation where forgetting a strictness annotation is the analogous Haskell situation of forgetting to bounds-check some input. There are lots of ways in Haskell for something not to be evaluated. (No, the simple fixes like 'use strict fields' do not cover all cases.) To put all of them behind a free monad seems like it would be giving up a lot. In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that.

AnthonyMouse 13y ago
> In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that. Exactly. struct buffer { void* data; size_t len; }; void smemcpy(buffer* dst, buffer* src, size_t n) { if(dst->len < n || src->len < n) abort(); memcpy(dst->data, src->data, n); } I mean how hard is that, honestly? Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. "I just checked that the buffer is big enough, I don't need memcpy to waste cycles checking it again. I don't need that length variable sucking up memory when I know how big the buffer is." Except when you do.
- sseveran 13y ago
  They come from the C language allowing it.
  - AnthonyMouse 13y ago
    All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.
    - lomnakkus 13y ago
      Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
      - unstabilo 13y ago
        "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.
        lmm 13y ago
        You're thinking of implementation-defined behaviour. Undefined behaviour is not well-defined; the compiler does not have to implement it consistently or sanely, and certainly gcc won't.
      - deleted 13y ago
        [deleted]
      - AnthonyMouse 13y ago
        > Do Turing machines have a concept of "undefined behavior" in the same way that C does? Sure they do. For example, nothing in the Turing machine specification tells you how fast they are. Whether a given program will run on a Turing machine in a given amount of wall clock time is undefined. Here's a real example with real machines. Suppose you have a program with two threads. The first thread computes data and puts it on a queue for the second thread, the second thread writes it to the filesystem. When the compute thread has computed all of the data, it sleeps for 10 seconds and then terminates the program without checking whether the write thread has actually completed writing all the data to the filesystem. That results in undefined behavior in every real language I've ever heard of. Whether the data is all written depends on how fast the CPU is, how fast the filesystem is, what other programs are scheduled on the machine that compete for CPU and filesystem access at what priority, etc. Languages don't define any of those things so you have undefined behavior.
  - humbledrone 13y ago
    The Python language allows constructs such as socket.write(my_private_key). Do you think that just because Python makes it possible to write your private key to a socket that it must necessarily happen?
- zvrba 13y ago
  It's hard to define semantics. Here, you have potentially copied less than dst->len bytes into dst->data. Is the remaining data (up to dst->len) still valid, is it garbage, should you have adjusted dst->len, etc? When does it even make sense to partially mix byte-level representations of some data? The buffer abstraction is necessary, but far from sufficient to build security-critical code. To do so, you also need to code in semantics somewhere, and buffers know zilch about the meaning of the data.
  - AnthonyMouse 13y ago
    Check again. Hint: "abort()" is not "return" -- that code doesn't prevent you from having to know how large the buffer is, it just shoots your program in the head if you don't. Which is basically the same semantics Java et al have by throwing an out of bounds exception when you don't catch it. Incidentally, this is another reason that the language can't save you from yourself. Program termination is sometimes totally unreasonable, e.g. in real-time settings. And it's unreasonable regardless of the language. When an airplane falls out of the sky, you don't get to declare victory just because the reason it did was an uncaught out of bounds exception rather than a buffer overrun. In that context the programmer must explicitly handle the condition that the buffer is too small, regardless of the language, because "abnormal program termination" is not an acceptable outcome.
    - andreasvc 13y ago
      Your code checks whether dst->len < n, but not whether dst->len > n; i.e., after copying 5 bytes to dst, there may be another 10 bytes of garbage in dst. This 'garbage' might as well be a password from a string that was just free'd. A fix would be to set dst->len to n after this operation.
      - AnthonyMouse 13y ago
        OK, I see what you're getting at. There is a difference between the end of the buffer and the end of the data. But copying some bytes into a buffer doesn't imply that you intend to discard the rest of the buffer. It's quite common to want to replace a header or some other subsection of a buffer and have the rest of the buffer remain unmodified. Moreover, the purpose of the above is to achieve the level of bounds checking that you get with the likes of Java. If you want to go beyond that then you need something more complicated -- maybe add separate variables to the buffer struct for buffer_len and data_len and then have different memcpy functions based on whether you want existing data in the buffer to be truncated. But there comes a point at which further complexity produces more confusion than safety.
- iopq 13y ago
  if(obj != null) { obj.stuff = ... } I mean how hard is that exactly? yet Java applications have null pointer exceptions all time
  - RyanZAG 13y ago
    Nothing wrong with null pointer exceptions - they are specific checks to see if the pointer is valid and are a good thing. If you see one, it means the programmer made a mistake and the runtime caught it for him. There are also tools to help with it in the form of @NotNull, @Nullable, etc. It's a completely different issue compared to actually accessing memory in an undefined way as you can in C. The bounds check you are replying to is manually creating something like that exception through the use of abort() while in java it is done always at the cost of some performance in exchange for safety.
    - iopq 13y ago
      Consider the following: some languages don't have null. When you need nullable what you really want is an Option/Maybe type. No null pointer exceptions, ever! It just won't compile until you fix the bug.
      - TheLoneWolfling 13y ago
        Or, more generally, I think languages should have union and intersection types - "(IFoo && IBar) || (IBaz)", etc. (I also think languages should have arbitrary Boolean expressions as types, where the compiler emits a warning and a runtime check if the compiler cannot prove either if the condition will be always met or it won't be always met, but that is another matter.) Null is just a built-in final/sealed type(enum?) with a single value and no operations defined, like boolean is a type(enum?) with two values. That, combined with proper type inference, would alleviate a large chunk of the boilerplate associated with statically typed languages in general, and Java in particular. (For how much Java is pushed as moving errors to compile time, there are an awful lot of things that fail only at run time that could be checked at compile time...) Same thing with checked exceptions. A checked exception is really just an option - return foo or failure.
- lhgaghl 13y ago
  > Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. You have to use other people's code / language constructs which are underspecified and/or you don't have time to fully understand. Throw in versioning to the equation and now the problem is exponentially worse. This is why C code will always be full of memory vulns. Heartbleed is a very oversimplified example of the problems in C.
Theriac25 13y ago
>In C you could have made some 'safe buffer' No you couldn't've. C is fundamentally unsafe language and people like you should stop pretending it isn't.
- quchen 13y ago
  People (all people) are fundamentally unsafe, not languages. It may be harder to write safe code in some languages than others, but that arguably doesn't make the language unsafe. Most certainly though, it does not make it "fundamentally" unsafe.
  - iopq 13y ago
    You can imagine a language that's memory safe. In fact, these languages exist today.
  - nmrm 13y ago
    Browse through the National Vulnerability Database, and write down the language of each bug. Discounting bad PHP, a huge majority of bugs are in C/C++ code. And "past popularity" isn't a good explanation, because a lot of the software is fairly recent. So, the following isn't an opinion. It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't.
    - runeks 13y ago
      > It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't. And in the case of crypto code, one could argue that there is a very good reason to use C/C++: to prevent timing attacks.
      - stcredzero 13y ago
        How hard would it be to develop a fast memory safe language that eliminates timing attacks?
PeterisP 13y ago
The point is that in Haskell you could reasonably define a 'biggish-num' type where only strict and constant-time operations would be possible - you couldn't forget to make an annotation, you'd have to explicitly ask for the value to become a 'normal number' before being able to make any such operation. In C having such a 'safe buffer' struct would require discipline from you, in Haskell that'd be the natural order of things.
- runeks 13y ago
  From your comment, I can't understand why defining a special struct in C is different from defining a special type in Haskell. I understand that many C programmers don't do it, mind you, but how is that different from a Haskell programmer not using the proper type for a certain operation?
  - AaronFriel 13y ago
    In Haskell, there are types that you have probably heard of but not used. Functors, applicative functors, and monads. In Haskell, I could define a value and its type: > value :: ConstantTime Int But how do I obtain an "Int" from that, since I know it somehow relates to an integer type? The answer is: you must ask the implementation of ConstantTime for the value, and if it doesn't want to give it to you, it doesn't have to. Constructors can be one way. The library author could define a number of additional operations. These operations are privileged, being written as part of the library, they can actually inspect the inner data at any time. This is the "small core" that needs to be verified. > addInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > subInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > mulInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > divInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int Then to compute something like Euler's formula one could write a function in terms of those functions. > newtonsMethod :: ConstantTime Int -> ConstantTime Int > newtonsMethod = ... And one can be certain that the laws that apply to `addInt` apply to `newtonsMethod`. This composition has wonderful benefits because if there is no branching operation defined by the library, users cannot use branches inside ConstantTime. To serially apply addition, multiplication, etc, one can write in a sort of reverse polish notation: > square :: ConstantTime Int -> ConstantTime Int > square input = mulInt input input Using the multiplication operator, (*), would be illegal there. And that function, square, cannot inspect the value of input. Because it can't inspect the value, it can't make choices based on that value.

AnthonyMouse 13y ago

> In C you could have made some 'safe buffer' struct together with some safe set of functions. But people didn't do that. Exactly. struct buffer { void* data; size_t len; }; void smemcpy(buffer* dst, buffer* src, size_t n) { if(dst->len < n || src->len < n) abort(); memcpy(dst->data, src->data, n); } I mean how hard is that, honestly? Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. "I just checked that the buffer is big enough, I don't need memcpy to waste cycles checking it again. I don't need that length variable sucking up memory when I know how big the buffer is." Except when you do.

sseveran 13y ago
They come from the C language allowing it.
- AnthonyMouse 13y ago
  All Turing complete languages allow you to do anything all Turing complete languages allow you to do. You can allocate a huge block of memory in Java or C# and then write your own malloc to allocate buffers from subsets of it. In some cases that may have better performance. It also allows you to have buffer overruns. You can run right off the end of one buffer and into the next and the language won't stop you because it only knows that you haven't reached the end of the array it allocated.
  - lomnakkus 13y ago
    Do Turing machines have a concept of "undefined behavior" in the same way that C does? AFAICT all behavior of a Turing machine is defined -- sure you might not calculate what you want, but that doesn't admit arbitrary behvaior outside of the semantics of the machine as in the C language.
    - unstabilo 13y ago
      "Undefined behavior" means "undefined by the language specification", but it is well defined by the compiler implementation. In other words, you never use the C language, always an implementation.
      - lmm 13y ago
        You're thinking of implementation-defined behaviour. Undefined behaviour is not well-defined; the compiler does not have to implement it consistently or sanely, and certainly gcc won't.
    - deleted 13y ago
      [deleted]
    - AnthonyMouse 13y ago
      > Do Turing machines have a concept of "undefined behavior" in the same way that C does? Sure they do. For example, nothing in the Turing machine specification tells you how fast they are. Whether a given program will run on a Turing machine in a given amount of wall clock time is undefined. Here's a real example with real machines. Suppose you have a program with two threads. The first thread computes data and puts it on a queue for the second thread, the second thread writes it to the filesystem. When the compute thread has computed all of the data, it sleeps for 10 seconds and then terminates the program without checking whether the write thread has actually completed writing all the data to the filesystem. That results in undefined behavior in every real language I've ever heard of. Whether the data is all written depends on how fast the CPU is, how fast the filesystem is, what other programs are scheduled on the machine that compete for CPU and filesystem access at what priority, etc. Languages don't define any of those things so you have undefined behavior.
- humbledrone 13y ago
  The Python language allows constructs such as socket.write(my_private_key). Do you think that just because Python makes it possible to write your private key to a socket that it must necessarily happen?
zvrba 13y ago
It's hard to define semantics. Here, you have potentially copied less than dst->len bytes into dst->data. Is the remaining data (up to dst->len) still valid, is it garbage, should you have adjusted dst->len, etc? When does it even make sense to partially mix byte-level representations of some data? The buffer abstraction is necessary, but far from sufficient to build security-critical code. To do so, you also need to code in semantics somewhere, and buffers know zilch about the meaning of the data.
- AnthonyMouse 13y ago
  Check again. Hint: "abort()" is not "return" -- that code doesn't prevent you from having to know how large the buffer is, it just shoots your program in the head if you don't. Which is basically the same semantics Java et al have by throwing an out of bounds exception when you don't catch it. Incidentally, this is another reason that the language can't save you from yourself. Program termination is sometimes totally unreasonable, e.g. in real-time settings. And it's unreasonable regardless of the language. When an airplane falls out of the sky, you don't get to declare victory just because the reason it did was an uncaught out of bounds exception rather than a buffer overrun. In that context the programmer must explicitly handle the condition that the buffer is too small, regardless of the language, because "abnormal program termination" is not an acceptable outcome.
  - andreasvc 13y ago
    Your code checks whether dst->len < n, but not whether dst->len > n; i.e., after copying 5 bytes to dst, there may be another 10 bytes of garbage in dst. This 'garbage' might as well be a password from a string that was just free'd. A fix would be to set dst->len to n after this operation.
    - AnthonyMouse 13y ago
      OK, I see what you're getting at. There is a difference between the end of the buffer and the end of the data. But copying some bytes into a buffer doesn't imply that you intend to discard the rest of the buffer. It's quite common to want to replace a header or some other subsection of a buffer and have the rest of the buffer remain unmodified. Moreover, the purpose of the above is to achieve the level of bounds checking that you get with the likes of Java. If you want to go beyond that then you need something more complicated -- maybe add separate variables to the buffer struct for buffer_len and data_len and then have different memcpy functions based on whether you want existing data in the buffer to be truncated. But there comes a point at which further complexity produces more confusion than safety.
iopq 13y ago
if(obj != null) { obj.stuff = ... } I mean how hard is that exactly? yet Java applications have null pointer exceptions all time
- RyanZAG 13y ago
  Nothing wrong with null pointer exceptions - they are specific checks to see if the pointer is valid and are a good thing. If you see one, it means the programmer made a mistake and the runtime caught it for him. There are also tools to help with it in the form of @NotNull, @Nullable, etc. It's a completely different issue compared to actually accessing memory in an undefined way as you can in C. The bounds check you are replying to is manually creating something like that exception through the use of abort() while in java it is done always at the cost of some performance in exchange for safety.
  - iopq 13y ago
    Consider the following: some languages don't have null. When you need nullable what you really want is an Option/Maybe type. No null pointer exceptions, ever! It just won't compile until you fix the bug.
    - TheLoneWolfling 13y ago
      Or, more generally, I think languages should have union and intersection types - "(IFoo && IBar) || (IBaz)", etc. (I also think languages should have arbitrary Boolean expressions as types, where the compiler emits a warning and a runtime check if the compiler cannot prove either if the condition will be always met or it won't be always met, but that is another matter.) Null is just a built-in final/sealed type(enum?) with a single value and no operations defined, like boolean is a type(enum?) with two values. That, combined with proper type inference, would alleviate a large chunk of the boilerplate associated with statically typed languages in general, and Java in particular. (For how much Java is pushed as moving errors to compile time, there are an awful lot of things that fail only at run time that could be checked at compile time...) Same thing with checked exceptions. A checked exception is really just an option - return foo or failure.
lhgaghl 13y ago
> Buffer bugs in C don't come from the language, they come from the tendency of C programmers to value performance highly. You have to use other people's code / language constructs which are underspecified and/or you don't have time to fully understand. Throw in versioning to the equation and now the problem is exponentially worse. This is why C code will always be full of memory vulns. Heartbleed is a very oversimplified example of the problems in C.

Theriac25 13y ago

>In C you could have made some 'safe buffer' No you couldn't've. C is fundamentally unsafe language and people like you should stop pretending it isn't.

quchen 13y ago
People (all people) are fundamentally unsafe, not languages. It may be harder to write safe code in some languages than others, but that arguably doesn't make the language unsafe. Most certainly though, it does not make it "fundamentally" unsafe.
- iopq 13y ago
  You can imagine a language that's memory safe. In fact, these languages exist today.
- nmrm 13y ago
  Browse through the National Vulnerability Database, and write down the language of each bug. Discounting bad PHP, a huge majority of bugs are in C/C++ code. And "past popularity" isn't a good explanation, because a lot of the software is fairly recent. So, the following isn't an opinion. It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't.
  - runeks 13y ago
    > It's simply a matter of observable fact. If you write in C/C++, you are far more likely to introduce security vulnerabilities than in other languages; therefore, unless there's a pressing reason to use these languages, don't. And in the case of crypto code, one could argue that there is a very good reason to use C/C++: to prevent timing attacks.
    - stcredzero 13y ago
      How hard would it be to develop a fast memory safe language that eliminates timing attacks?

PeterisP 13y ago

The point is that in Haskell you could reasonably define a 'biggish-num' type where only strict and constant-time operations would be possible - you couldn't forget to make an annotation, you'd have to explicitly ask for the value to become a 'normal number' before being able to make any such operation. In C having such a 'safe buffer' struct would require discipline from you, in Haskell that'd be the natural order of things.

runeks 13y ago
From your comment, I can't understand why defining a special struct in C is different from defining a special type in Haskell. I understand that many C programmers don't do it, mind you, but how is that different from a Haskell programmer not using the proper type for a certain operation?
- AaronFriel 13y ago
  In Haskell, there are types that you have probably heard of but not used. Functors, applicative functors, and monads. In Haskell, I could define a value and its type: > value :: ConstantTime Int But how do I obtain an "Int" from that, since I know it somehow relates to an integer type? The answer is: you must ask the implementation of ConstantTime for the value, and if it doesn't want to give it to you, it doesn't have to. Constructors can be one way. The library author could define a number of additional operations. These operations are privileged, being written as part of the library, they can actually inspect the inner data at any time. This is the "small core" that needs to be verified. > addInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > subInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > mulInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int > divInt :: ConstantTime Int -> ConstantTime Int -> ConstantTime Int Then to compute something like Euler's formula one could write a function in terms of those functions. > newtonsMethod :: ConstantTime Int -> ConstantTime Int > newtonsMethod = ... And one can be certain that the laws that apply to `addInt` apply to `newtonsMethod`. This composition has wonderful benefits because if there is no branching operation defined by the library, users cannot use branches inside ConstantTime. To serially apply addition, multiplication, etc, one can write in a sort of reverse polish notation: > square :: ConstantTime Int -> ConstantTime Int > square input = mulInt input input Using the multiplication operator, (*), would be illegal there. And that function, square, cannot inspect the value of input. Because it can't inspect the value, it can't make choices based on that value.