Standardized SafeInt?

[Ben Craig]

SafeInt information can be found here.  Basically, it is an open source library authored by security expert David LeBlanc of Microsoft.  It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur.  I believe that getting this added to the standard would be a boon to C++ and secure code.  It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.

[Jens Maurer]

On 11/08/2012 03:59 AM, Ben Craig wrote:
> SafeInt information can be found here <http://safeint.codeplex.com/>. Basically, it is an open source library authored by security expert David LeBlanc of Microsoft. It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur. I believe that getting this added to the standard would be a boon to C++ and secure code. It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.

Probably a good idea.

This would need a proposal, i.e. a paper essentially showing a bit of rationale
plus (eventually) the full text that would go into the standard. Unless someone
from the committee itself has enough interest to invest the substantial effort
to write that, it's not going to happen with a one-line post like this.

Or, you could write the proposal yourself and submit it (as a first start,
only show the motivation and rationale plus a rough outline; unless encouraged
by WG21 to do the full thing, don't write the full standard text just yet;
it might turn out to be a waste of time).

Jens

[Beman Dawes]

On Sat, Nov 10, 2012 at 2:55 PM, Jens Maurer <Jens....@gmx.net> wrote:
> On 11/08/2012 03:59 AM, Ben Craig wrote:
>> SafeInt information can be found here <http://safeint.codeplex.com/>. Basically, it is an open source library authored by security expert David LeBlanc of Microsoft. It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur. I believe that getting this added to the standard would be a boon to C++ and secure code. It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.
>
> Probably a good idea.

Yes, although with no docs at the above link, and no examples in your
query, it is not possible to give a very complete answer.

> This would need a proposal, i.e. a paper essentially showing a bit of rationale
> plus (eventually) the full text that would go into the standard. Unless someone
> from the committee itself has enough interest to invest the substantial effort
> to write that, it's not going to happen with a one-line post like this.
>
> Or, you could write the proposal yourself and submit it (as a first start,
> only show the motivation and rationale plus a rough outline; unless encouraged
> by WG21 to do the full thing, don't write the full standard text just yet;
> it might turn out to be a waste of time).

As Jens suggests, writing a query proposal is really the only way to
know how the LWG will react.

Since there are other "safe integer" libraries in use, a proposal
document should comment on the differences between the proposal and
other similar libraries. It always rattles me when a proposal appears
that doesn't seem to be aware of the work of others, and which
approaches were successful with users.

--Beman

[Marc]

On Thursday, November 8, 2012 3:59:50 AM UTC+1, Ben Craig wrote:

SafeInt information can be found here.  Basically, it is an open source library authored by security expert David LeBlanc of Microsoft.  It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur.  I believe that getting this added to the standard would be a boon to C++ and secure code.  It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.

I don't think adding an isolated checked int makes much sense (I haven't looked at SafeInt). I believe it would make more sense as part of a generic integer type for which you can specify many overflow (and division by 0) policies: undefined, wrap, saturate, set a flag, trap/throw, etc (we can start with few policies).

[Michał Dominiak]

Yay for that. Currently, if you want to check for overflow and other situations like that, you need to either write weird tests (result + b < a, for example, huh) or rely on assembly (like `jc` on x86). Creating some reasonable way to access such flag or throw something on carry, etc. would be great.

Now (following x86 example), throwing on carry is trivial; just add `jc` here and make it jump to throwing code. Accessing the flag would be different, harder. It would either require construct similar to assembly `jc` (if [[overflow]]? looks weird), or keeping additional flag for each variable, which would kill the point of doing it without library construct - for example, `std::safe<int>`.

Just throwing some thoughts.

[dvd_l...@yahoo.com]

Hi - I was notified of this thread on Sunday, and am happy to answer questions about my library.

 

A few comments I can make on some of what is here so far:

 

1) Rationale - integer checking is hard - much more difficult than it would seem at first. Many people can't get the math right to start with, and then get the checks wrong when they do try (e.g., if ( a * b < 0 ) for signed multiplication). There are also very subtle problems involving code that isn't quite standards-compliant (e.g., signed integer rollover). There's a need for a library that can just be dropped into existing code which does not change the current logic, and which will help solve this problem. The SafeInt library works nicely to solve these issues, as well as difficult things, like checking to see if a cast on entry into a function results in information loss.

 

2) I have not extensively reviewed other libraries. The one that I'm aware of which came before my work (first released in 2005) was the Microsoft IntSafe library. It is written in C, and is easy to use incorrectly. SafeInt takes a more robust C++ approach. I believe other libraries have been created after mine was released, and I'm largely aware of them because John Regehr of the University of Utah did some nice work to find a small number of flaws in SafeInt. His team looked at other libraries, and found much more substantial flaws. I can take a look at the other libraries, or it would really be better for an unbiased 3rd party to do the comparison. Other than IntSafe, I am not aware of any libraries that pre-dated SafeInt.

 

3) There are two versions of SafeInt that are public - one ships in Visual Studio, and is only expected to be correct with that compiler. The other is at www.codeplex.com/SafeInt, should be thoroughly standards-compliant (if not, let me know, I will consider it a bug and fix it), and is known to work correctly with a number of compilers.

 

4) Just checking the carry flag is insufficient. For example, adding 2 16-bit shorts into a 32-bit register will never trip the carry flag, but if the result is assigned to a short, it may represent an overflow - ironic that if sizeof(short) < sizeof(int), the signed short addition overflow is defined by the standard (due to operator casting), but signed int overflow is not - these are the sorts of oddities that make the problem so difficult for most programmers.

 

5) The library has had significant adoption within Microsoft, and has proven very useful in mitigating this class of problem, which often manifests as security bugs. It has been downloaded over 5000 times, but I'm not aware of what other products it may have ended up in.

 

I'll be happy to answer any questions and help with this process. If there's significant interest, I can work with the Microsoft standards team to do the full write-up needed. I've participated in other standards bodies, but not this one.

 

Thanks to all for the kind comments thus far -

[Beman Dawes]

Sounds like an excellent candidate for standardization. Please do
consider making a formal proposal. Stephan T. Lavavej (aka STL) is the
Microsoft person you probably want to talk to about getting together a
formal proposal.

--Beman

[robertmac...@gmail.com]

On Wednesday, November 7, 2012 6:59:50 PM UTC-8, Ben Craig wrote:

SafeInt information can be found here.  ...

I also found myself interested in this code.  When I got around to looking at it I felt it could be improved.  Being a "booster" I wanted to leverage on Boost stuff to make a simpler implementation.  The result of my efforts can be found at http://rrsd.com/blincubator.com/bi_library/safe-numerics/

Main differences are:
a) follows Boost/C++ library conventions as to naming, formating etc.
b) Is many many lines shorter due to the usage of more meta-programming technique in the implementation.
c) Includes an exhaustive set of tests including all combinations of corner cases - generated with boost pre-processor library.
d) defines concepts for "numeric" types and includes concept checking via the boost concept checking library.
e) includes documentation more in line with currently recommended "formal" style.

Robert Ramey

[Fernando Cacciola]

I would most definitely like to have a standardized interface to handle numerical overflow.

I do however have some reservations on doing it by means of an integer wrapper.

First, I think we need such "safe numeric operations" to handle floating point values just as well. While the mechanisms are different, the requirements are exactly the same (and floating-point does overflow no matter how big their range is). In fact, I think we need it for arbitrary numeric types, including rationals, complex, user-defined extended precision, interval, etc... (and consistently defined for even unlimited precision numeric types, even if the overflow test always yields false)

Second, I wonder if a wrapper is the best interface. Since this is a "security" utility, it needs to be consistently applied *all over* the relevant source code, otherwise it is not really effective
A lot, if not most, critical and complex numeric code (where this is mostly needed) depends on third-party libraries, and in the numerical community there is a huge base of reusable code that is (yet) not sufficiently generic to let you get away with simple using a wrapper type at the highest level.
In other words, you might use SafeInt in your own code but it is not easy to have third-party code use it as well.

Since the overflow is always a side effect of operations, and operations are expressed in C++ via operators (and functions), I wonder if the library shouldn't be in a form of "safe operators and functions" as opposed to "safe numeric type".

IIUC, the current operator overloading mechanism should allow something like the following:

#include <safe_numeric_operations>

// This "activates" the overflow detection on any supported type, including builtin types
using std::safe_numeric_operations ;

void test()
{
  try
  {
     int a = std::numeric_limits<int>::max();

     // std::safe_numeric_operations::operator + (int,int) being called here
     int r = a + a ;
  }
  catch ( std::bad_numeric_conversion ) { }
}

--
 
 
 

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com

[Nicol Bolas]

On Thursday, November 22, 2012 5:45:42 AM UTC-8, Fernando Cacciola wrote:

I would most definitely like to have a standardized interface to handle numerical overflow.

I do however have some reservations on doing it by means of an integer wrapper.

First, I think we need such "safe numeric operations" to handle floating point values just as well. While the mechanisms are different, the requirements are exactly the same (and floating-point does overflow no matter how big their range is). In fact, I think we need it for arbitrary numeric types, including rationals, complex, user-defined extended precision, interval, etc... (and consistently defined for even unlimited precision numeric types, even if the overflow test always yields false)

Second, I wonder if a wrapper is the best interface. Since this is a "security" utility, it needs to be consistently applied *all over* the relevant source code, otherwise it is not really effective

Don't forget the essential C++ maxim: pay only for what you use.

There is a lot of code that's just fine with non-secure integers. They no need to have overflow checks and such every time time they loop from 0 to 240. They aren't going to overflow their loop counter. There are many such occurrences in a code-base where the structure and nature of the code means that overflow is just not a realistic possibility.

This means that whatever we adopt has to be an opt-in mechanism, not an opt-out.
 

A lot, if not most, critical and complex numeric code (where this is mostly needed) depends on third-party libraries, and in the numerical community there is a huge base of reusable code that is (yet) not sufficiently generic to let you get away with simple using a wrapper type at the highest level.
In other words, you might use SafeInt in your own code but it is not easy to have third-party code use it as well.

Since the overflow is always a side effect of operations, and operations are expressed in C++ via operators (and functions), I wonder if the library shouldn't be in a form of "safe operators and functions" as opposed to "safe numeric type". 

IIUC, the current operator overloading mechanism should allow something like the following:

#include <safe_numeric_operations>

// This "activates" the overflow detection on any supported type, including builtin types
using std::safe_numeric_operations ;

void test()
{
  try
  {
     int a = std::numeric_limits<int>::max();

     // std::safe_numeric_operations::operator + (int,int) being called here
     int r = a + a ;
  }
  catch ( std::bad_numeric_conversion ) { }
}

Ignoring the fact that a recompile would suddenly cause massive amounts of code to potentially throw std::bad_numeric_conversion without the knowledge of that code's owners (ie: we can't do that), there's also the practical issue that this won't magically affect any C code that people often use.

But even more importantly, I'm pretty sure you can't overload operator+(int, int). Besides being practically infeasible by creating the possibility of exceptions in potentially exception-unsafe code, it's simply not possible.
 

[Marc Thibault]

I would like to have a standard that deals with overflows. I think the best way would be an arbitrary precision class used for internal linkage and the right cast functions to create object with external linkage. I think dynamic_cast could in theory be used to throw on overflow. I would also like a saturate_cast which would convert to the nearest valid value of the output type. The class definition could also look like this:

template<int64_t MIN, int64_t MAX> //minimum and maximum runtime value that can be stored
class integer
{
    /*Large enough storage type for MIN and MAX*/ value;
    public:
    template<int64_t OMIN, int64_t OMAX>
    integer<MIN+OMIN, MAX+OMAX> operator+(integer<OMIN,OMAX> i) const;
};

Now, there is a limit to how much precision the MIN and MAX could have. So it would still be interesting to have a safeintmax_t and safeuintmax_t.

Other options that could be interesting:

A third template parameter being a common divisor. If you make an integer from a long*, the alignment can guaranty a minimum common divisor among all results.

An arbitrary precision floating point class which knows its min and max to some extent.

A cast that lowers precision so all preceding operations could be replaced by less precise and faster operations.

[robertmac...@gmail.com]

On Thursday, November 22, 2012 5:45:42 AM UTC-8, Fernando Cacciola wrote:

I would most definitely like to have a standardized interface to handle numerical overflow.

I do however have some reservations on doing it by means of an integer wrapper.

First, I think we need such "safe numeric operations" to handle floating point values just as well. While the mechanisms are different, the requirements are exactly the same (and floating-point does overflow no matter how big their range is). In fact, I think we need it for arbitrary numeric types, including rationals, complex, user-defined extended precision, interval, etc... (and consistently defined for even unlimited precision numeric types, even if the overflow test always yields false)

Note that my proposed implementation defines a concept "Numeric" for all types which look like a number and are supported via std::limits. I've implemented this for safe<int>, safe<unsigned int>, etc..  All of the other types listed above would fit into this scheme.  (Though implementing this for floating point types would be an effort).

Second, I wonder if a wrapper is the best interface. Since this is a "security" utility, it needs to be consistently applied *all over* the relevant source code, otherwise it is not really effective

I totally disagree with this.  I must be optional on the part of the user.  we can't really know that the user really want's to do.  Maybe he's just fine with high order bits being lost. So if you applied this "everywhere" you'd have to supply an "escape hatch" which would complicate it's usage.  Further more, some users would want to use this only for debug build and perhaps define away the functionality for release builds.  Finally,  using it "everywhere" would mean mucking with C++ language - a language which is already to complex for anyone to write a correct compiler for.
 

A lot, if not most, critical and complex numeric code (where this is mostly needed) depends on third-party libraries, and in the numerical community there is a huge base of reusable code that is (yet) not sufficiently generic to let you get away with simple using a wrapper type at the highest level.
In other words, you might use SafeInt in your own code but it is not easy to have third-party code use it as well.

Which is as it must be.  We can't fix the whole world - only our own code. But this shouldn't prevent us from doing that.
 

IIUC, the current operator overloading mechanism should allow something like the following:

#include <safe_numeric_operations>

// This "activates" the overflow detection on any supported type, including builtin types
using std::safe_numeric_operations ;

void test()
{
  try
  {
     int a = std::numeric_limits<int>::max();

     // std::safe_numeric_operations::operator + (int,int) being called here
     int r = a + a ;
  }
  catch ( std::bad_numeric_conversion ) { }
}

This is pretty much exactly what my reference implementation does!

Robert Ramey

[robertmac...@gmail.com]

On Thursday, November 22, 2012 8:35:26 AM UTC-8, Marc Thibault wrote:

template<int64_t MIN, int64_t MAX> //minimum and maximum runtime value that can be stored

...

Note that my reference implementation includes safe_signed_range<min, max> and safe_unsigned_range<min, max>.  In fact, safe<int> .. are implemented in terms of these more general templates.  - something like

template<T>
struct safe_unsigned_int<T> : public safe_range<std::limits<T>::min ...
{};

So you get this functionality for free.


Robert Ramey

[Fernando Cacciola]

OK, I agree with your observations about silently overloading operators.

OTOH, I still think there is something to be considered in the fact that it is the operations that overflow (and other unwanted side effects), not the numbers themselves, so I would propose a layer of overloaded functions, that can be applied on any type, including built-in types, and on top of that a higher-level wrapper (or wrappers like in Robert's library)

The advantage of doing so, following your own observations, is that in most numeric code, you don't really need to check for all operations, so a performance critical algorithm might not be able to just use the wrapper as a drop-in replacement for int, yet it could be made secure by adding checked operations where specifically necessary.

Having said all that, I would like to at least mention the fact that there is a largest picture to consider here, where integer overflow is just one case. I'm referring to the domain of numerical robustness in general, and while a comprehensive work on that is way out of the scope of a relatively simple proposal like this one, the big picture should still be constantly present and considered.

From the more general point of view of numerical robustness, throwing an exception when a numerical computation could not be performed (such as in the case of integer overflow) is the most basic building block, but it is still too low-level. There is a lot of work in the research community about how to truly handle numerical limitations, as opposed to not handling in order (which is what a safe-int does). Unfortunately, most of that work is specific to an application domain and a given numeric type or types, so it's hard to extrapolate general idioms and utilities. However, there are two basic elements that are usually found in most of them:

First there is the general mechanism of using a proper type to perform an operation. For intance, an int64 to operate two int32. This is the mechanism used by SafeInt and Robert's code, but it's actually used in a lot of places dealing with integer numerics. So, we should standardized that, such that it is generally available to any programmer to do something like:

auto r = (secure)a + b;

here (secure) would bootstrap an operator+ which selects the proper return type to guarantee the addition does not overflow (or you could just have secure_add(a,b) or whatever)

Second, there is the general requirement to test whether the result of operations are reliable, beyond just overflow.
One idiom that has emerged in recent years and which I found intuitive enough to be general is the concept of "certified arithmetic" (usually implemented with interval floating-point numbers). The idea is that, on the one hand, the result of operations carry a certificate (explicit or not) to indicate if it succeeded or not, and on the other hand, triboolean logic is used along, made general and easy.  In terms of safe_int this would mean that instead of throwing, the result is just flaged as overflow, much like a floating-point saturates to +- INF, but, when you try to compare, the answer is "maybe" (and if you want to convert it to plain int it throws)

The general form of the idiom would be something like this:

auto e = ( a  + b == c + d ) ;
if ( certainy(e) )
{
}
else if ( certainly_not(e ) )
{
}
else
{
  // can't tell. It not possible to compare the numbers
}

Here, if a,b,c,d are integers numbers, and either of the additions overflow, the code flows to the last else, and without even any exception being thrown.
The trick is that operator == returns a tribool (or it's generalization uncertain<bool>)


Best

[robertmac...@gmail.com]

On Thursday, November 22, 2012 9:02:42 AM UTC-8, Fernando Cacciola wrote:

OK, I agree with your observations about silently overloading operators.

OTOH, ....

Well one can make this very elaborate.  When I was doing this I experimented with keep track of number of bits a compile time so that operations which could never overthrow would generate no runtime overhead.  There are lots of things one could do along this line - especially now that we have something like auto.

But in the end, I decided to keep it as simple as I could. The whole library can be summarized in one sentence.

"any operation involving a safe numeric type will produce the expected mathematical result or throw an exception"

Making it do more or less than this would severely hamper it's utility.

Robert Ramey

 

[Fernando Cacciola]

I didn't intend to suggest that a library should do less or more than proposed here. I suggested that in order to prepare and evaluate such a proposal, the bigger picture should be taken into account.

For instance, both SafeInt's and your code *requires* a primitive operation that returns the result in a larger type such that it is known not to overflow. The overflow detection is just an extra step, and it's only required because (or rather IFF) the result is needed to be converted into the same type as the operands. That means that both libraries under consideration are really the composition of two layers: the bottom layer that performs the operation in a way that it's result is known to be correct, and the layer that performs the conversion to a given receiving type but doing a proper range check first.

Then I'm saying that, since the bottom layer is a requirement for these libraries, and it's also useful--and used--in several other numerical techniques, it should be standardized as such (and not hidden as an implementation detail as it proposed)

Furthermore, with such a decomposition in place, the top layer can be *totally* given by a general numeric_cast<> utility, such as the the one proposed in n1879
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1879.htm)

But that's not all.

I'm also saying that the bigger picture could critically affect design decision even within the scope proposed. I gave the example of certified arithmetic because that would suggest that a given safe_int should not necessarily just throw right up front, but it could instead flag the overflow and throw only when necessary, such as when casting to int. This is important because if you are going to compare the overflowed result, you can just return "maybe" from the comparison without throwing an exception. This not only allows the client code to be *elegantly* explicit about the way overflowed results affect the computation results, but it also allows the library to be used in contexts where exceptions are to be avoided when possible.


Best

[robertmac...@gmail.com]

On Thursday, November 22, 2012 1:33:38 PM UTC-8, Fernando Cacciola wrote:

On Thu, Nov 22, 2012 at 5:57 PM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 9:02:42 AM UTC-8, Fernando Cacciola wrote:

OK, I agree with your observations about silently overloading operators.

OTOH, ....

Well one can make this very elaborate.  When I was doing this I experimented with keep track of number of bits a compile time so that operations which could never overthrow would generate no runtime overhead.  There are lots of things one could do along this line - especially now that we have something like auto.

But in the end, I decided to keep it as simple as I could. The whole library can be summarized in one sentence.

"any operation involving a safe numeric type will produce the expected mathematical result or throw an exception"

Making it do more or less than this would severely hamper it's utility.

 

 

I didn't intend to suggest that a library should do less or more than proposed here. I suggested that in order to prepare and evaluate such a proposal, the bigger picture should be taken into account.

For instance, both SafeInt's and your code *requires* a primitive operation that returns the result in a larger type such that it is known not to overflow.

I don't think that's true.  That's not part of the interface or type requirements. It's merely an implementation feature of the library because it's the fastest way to do this.  It still checks for overflows on int64 operations even though there is not int 128 type - it has to use a much slower method.

 

The overflow detection is just an extra step, and it's only required because (or rather IFF) the result is needed to be converted into the same type as the operands.

The result is calculated to whatever precision is required to avoid overflow. When the result is assigned somewhere - then the overflow is caught.  So

safe<int16> a, b;
safe<int16> x = a + b; // could trap on overflow - but
safe<int32> x = a + b; // would never trap

An interesting side issue of this is that there is no run time overhead on the second
statement because template meta programming is used to determine that
there can never, ever be an overflow. Finally

auto x = a + b; will result in x being of type safe<int32> and will never, ever trap( actually I have to double check this).

So to my mind this is exactly what is desired.

That means that both libraries under consideration are really the composition of two layers: the bottom layer that performs the operation in a way that it's result is known to be correct, and the layer that performs the conversion to a given receiving type but doing a proper range check first.

In my implementation, the two layers are there - but can't be separated.  The "lower" layer happens on the + operator while the "upper" layer happens on the = operator.  There is only one library though.

 
Then I'm saying that, since the bottom layer is a requirement for these libraries, and it's also useful--and used--in several other numerical techniques, it should be standardized as such (and not hidden as an implementation detail as it proposed)

I'm guessing that anyone wanting to do this could just overload the = operator. or use safe<?> as a constructor argument to his own special type.

But that's not all.

I'm also saying that the bigger picture could critically affect design decision even within the scope proposed. I gave the example of certified arithmetic because that would suggest that a given safe_int should not necessarily just throw right up front, but it could instead flag the overflow and throw only when necessary, such as when casting to int. This is important because if you are going to compare the overflowed result, you can just return "maybe" from the comparison without throwing an exception. This not only allows the client code to be *elegantly* explicit about the way overflowed results affect the computation results, but it also allows the library to be used in contexts where exceptions are to be avoided when possible.

as a practical matter, I don't see how you can "throw upfront" until you actually do an assignment or explicit cast.  Take the following assignment.

safe<int16> a;
safe<int32> b;

auto x = a + b;  // what is the type of x?
auto x = b + a;  // is the type of y the same as the type of x?

Questions like these made me decide to divide the task as you suggested
a) do the calculation resulting in a type which can hold the true result
b) on assignment or cast (safe_cast ...) trap the attempt to save a value which loses information.

Robert Ramey

[Fernando Cacciola]

On Thu, Nov 22, 2012 at 7:25 PM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 1:33:38 PM UTC-8, Fernando Cacciola wrote:

On Thu, Nov 22, 2012 at 5:57 PM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 9:02:42 AM UTC-8, Fernando Cacciola wrote:

OK, I agree with your observations about silently overloading operators.

OTOH, ....

Well one can make this very elaborate.  When I was doing this I experimented with keep track of number of bits a compile time so that operations which could never overthrow would generate no runtime overhead.  There are lots of things one could do along this line - especially now that we have something like auto.

But in the end, I decided to keep it as simple as I could. The whole library can be summarized in one sentence.

"any operation involving a safe numeric type will produce the expected mathematical result or throw an exception"

Making it do more or less than this would severely hamper it's utility.

 

 

I didn't intend to suggest that a library should do less or more than proposed here. I suggested that in order to prepare and evaluate such a proposal, the bigger picture should be taken into account.

For instance, both SafeInt's and your code *requires* a primitive operation that returns the result in a larger type such that it is known not to overflow.

I don't think that's true.  That's not part of the interface or type requirements. It's merely an implementation feature of the library because it's the fastest way to do this.  It still checks for overflows on int64 operations even though there is not int 128 type - it has to use a much slower method.

I haven't checked your code in this corner case, but SafeInt uses a form of 128 bits type (when configured as such)

Since it is always true that the result of an integer operation between two N bits integer fits perfectly in a 2*N bits integer, it is entirely possible to generalize the pattern even for 64bits by providing a library-based 128bit integer.
In fact, we've been doing that for 64bits on 32bits hardwarde and OS for a long long time, so it wouldn't be anything new.

 

 

The overflow detection is just an extra step, and it's only required because (or rather IFF) the result is needed to be converted into the same type as the operands.

The result is calculated to whatever precision is required to avoid overflow. When the result is assigned somewhere - then the overflow is caught.  So

safe<int16> a, b;
safe<int16> x = a + b; // could trap on overflow - but
safe<int32> x = a + b; // would never trap

An interesting side issue of this is that there is no run time overhead on the second
statement because template meta programming is used to determine that
there can never, ever be an overflow. Finally

auto x = a + b; will result in x being of type safe<int32> and will never, ever trap( actually I have to double check this).

So what's the signature of operator+ ( safe<int64>, safe<int64> ) ?
 

So to my mind this is exactly what is desired.

So we are mostly agreeing on what is useful, only not on the interface.

I still prefer something more general that would allow me to do:

int16 a,b ;
int32 x = safe_add(a,b);

and entirely bypass the wrapper though, specially as a std utility (which is what we are discussing here)
 

That means that both libraries under consideration are really the composition of two layers: the bottom layer that performs the operation in a way that it's result is known to be correct, and the layer that performs the conversion to a given receiving type but doing a proper range check first.

In my implementation, the two layers are there - but can't be separated.  The "lower" layer happens on the + operator while the "upper" layer happens on the = operator.  There is only one library though.

Notice that this is not the case of the SafeInt (and SafeInt does not allow me to just get the correct, non-overflowed result as we did above)

 
Then I'm saying that, since the bottom layer is a requirement for these libraries, and it's also useful--and used--in several other numerical techniques, it should be standardized as such (and not hidden as an implementation detail as it proposed)

I'm guessing that anyone wanting to do this could just overload the = operator. or use safe<?> as a constructor argument to his own special type.

But that's not all.

I'm also saying that the bigger picture could critically affect design decision even within the scope proposed. I gave the example of certified arithmetic because that would suggest that a given safe_int should not necessarily just throw right up front, but it could instead flag the overflow and throw only when necessary, such as when casting to int. This is important because if you are going to compare the overflowed result, you can just return "maybe" from the comparison without throwing an exception. This not only allows the client code to be *elegantly* explicit about the way overflowed results affect the computation results, but it also allows the library to be used in contexts where exceptions are to be avoided when possible.

as a practical matter, I don't see how you can "throw upfront" until you actually do an assignment or explicit cast.  Take the following assignment.

Indeed my point was that you shouldn't, but you certainly could (and naturally would) in a design that does not separate the two layers.

The SafeInt code, for example, (and AFAICT), does just that, since it doesn't produce a 2N bits integer for an operation between two N bits integers. So it checks and throws right in the operators (actually the functions that produce the results, to be precise)


 

safe<int16> a;
safe<int32> b;

auto x = a + b;  // what is the type of x?

should be safe<int64>
 

auto x = b + a;  // is the type of y the same as the type of x?

yes
 

Questions like these made me decide to divide the task as you suggested
a) do the calculation resulting in a type which can hold the true result
b) on assignment or cast (safe_cast ...) trap the attempt to save a value which loses information.

So we are almost on the same page.

We differ in how to propose two two layers to the std

[Ben Craig]

On Thursday, November 22, 2012 2:57:26 PM UTC-6, robertmac...@gmail.com wrote:

Well one can make this very elaborate.  When I was doing this I experimented with keep track of number of bits a compile time so that operations which could never overthrow would generate no runtime overhead.  There are lots of things one could do along this line - especially now that we have something like auto.

 
That would likely turn into a fixed-point arithmetic library.

[robertmac...@gmail.com]

On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:

 
That would likely turn into a fixed-point arithmetic library.

I believe that a multi-precision library has recently been submitted to boost by john maddock.  It would be my hope that save<T> would work with any type which has std::limits<T> implemented and the member limits has the right definitions.  I haven't spent any time considering whether this is possible though.  I did define and implement a "Numeric" concept which includes all the intergers and the safe versions of the same in order to support such an idea.  But I don't know whether this will really pan out or not.  My main motivation was to make a "boostified" version of SafeInt.

Off topic - but related note.  In the course of doing this, I spent time investigating Boost conversion which I believe you wrote.  I really couldn't understand how to use it from the documentation  and filed a track issue to that effect.  To my knowledge it's still a pending issue.  I think some more effort in this area would be very helpful.

Robert Ramey
 

[Fernando Cacciola]

On Fri, Nov 23, 2012 at 3:45 AM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:

 
That would likely turn into a fixed-point arithmetic library.

I would rather say that a fixed-point library, as well as a rationals library, would be alongside (or maybe one level above) safe-int, as opposed to a generalization of it.
 

I believe that a multi-precision library has recently been submitted to boost by john maddock.  It would be my hope that save<T> would work with any type which has std::limits<T> implemented and the member limits has the right definitions.  I haven't spent any time considering whether this is possible though.  I did define and implement a "Numeric" concept which includes all the intergers and the safe versions of the same in order to support such an idea.  But I don't know whether this will really pan out or not.  My main motivation was to make a "boostified" version of SafeInt.

I still prefer a traits and functions only lower layer because it would be naturally used in the implementation of a fixed_point<T> and rational<T>, but I admit that they could just as well use safe_int<T>, as has been presented.

Here's one example off the top of my head about why I would prefer a lower layer independent of safe_int<>

Both fixed_point<T> and rational<T> are useful as long as the values do not overflow. However, and this is particularly true in the case of rationals, there are several application domains where computations can easily, and often, overflow. In these cases, one must use a big_int (unlimited precision integer) as T (whether for a fixed_point or rational)
But that is pessimistically inefficient, so one would consider a non-template "exact" numeric type which would have a dynamic internal representation of rational<T> but which would automatically switch from T to 2T (meaning a two times bigger integer), until it reaches big_int.

Now, if rational<T> uses internally safe<T>, how would we determine the next representation to use when overflow is detected? would it do something like

rational< typename decltype( safe<T> + safe<T> )::internal_type > ?

that'd work but it starts getting cumbersome.

If, OTOH, safe<T>, rational<T>, fixed_point<T> and exact, they all use the same general lower layer with elements such as :

exact_integer_result_type<T,T>::type  // given int32,int32 yields int64

safe_add(T,T) -> exact_integer_result_type<T,T>::type

etc...

then the promoted rational to use within exact would be

rational< typename exact_integer_result_type<T,T>::type >

which looks a lot clean to me.

That's all off the top of my head, but I hope it illustrates my point.


 

Off topic - but related note.  In the course of doing this, I spent time investigating Boost conversion which I believe you wrote.  I really couldn't understand how to use it from the documentation  and filed a track issue to that effect.  To my knowledge it's still a pending issue.  I think some more effort in this area would be very helpful.

Absolutely. Fixing that documentation is in my close-term TODO list

Best
 

[robertmac...@gmail.com]

On Friday, November 23, 2012 4:26:08 AM UTC-8, Fernando Cacciola wrote:

On Fri, Nov 23, 2012 at 3:45 AM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:

 
That would likely turn into a fixed-point arithmetic library.

I would rather say that a fixed-point library, as well as a rationals library, would be alongside (or maybe one level above) safe-int, as opposed to a generalization of it.

I'm not sure I followed your suggestion, but somehow I'm thinking I might be in agreement. My view would be the "safe" idea would be orthogonal to the "numeric" idea.  So

int, rational<T>, multiprecision<N>, .... would have std limits<T> defined. std::limits includes members to define min/max values and a lot of other features of numeric types.

This would make them fullfill the "Numeric" concept (type requirements).

safe<T> would be defined for any type T fullfilling the "Numeric" concept.

and safe<T> would also have std::limits implemented so it would fullfill the "Numeric" concept as well.

This would separate the "safe" idea from the "numeric" idea and permit users to use the "safe" version if and only if actually desired.  It would also clarify what "safe" does as opposed to what "numeric" does.  My proposal implements this idea for current integer types.  It hasn't really been investigated whether this extends well to all integer types for which std::limits is implemented.  Anyway, this is far into the future.

Robert Ramey

[Marc Thibault]

A few facts I wanted to share:

uint32 a= random<uint32>();
uint32 b= random<uint32>();
bool carry= random<bool>();
uint33 c= a + b + carry; //this cannot overflow

In this example, the integer type that stores automatic results must know the exact maximum, not the number of bits of the sub result. Also, a multiplication of two Nbits number cannot give the maximum of a 2*Nbits number.

It might be possible to define a 128bits integer as a pair of low bits and high bits. And then generalize for N*64bits number. All of those numbers could know their exact minimum and maximum at compile time. Multiplication algorithm of large numbers often add several results of the multiplication of 2 machine words. Many overflow check could be removed if the integer type knows its exact minimum and maximum.

[robertmac...@gmail.com]

On Sunday, November 25, 2012 8:59:27 AM UTC-8, Marc Thibault wrote:

A few facts I wanted to share:...

Many overflow check could be removed if the integer type knows its exact minimum and maximum.

The library I cited - http://rrsd.com/blincubator.com/bi_library/safe-numerics/ does exactly that.  That is using TMP techniques - it elides the overflow check if it can be determined that the result can never overflow.

Robert Ramey

[Marc Thibault]

I also believe that safe-numerics is very good. I think the problem of integers that grows at runtime has to be done in a different library. Also, there is the independent problem of creating efficient accumulators.

safe_int<int64_t> i;
i.accumulate(uint32_t* first, uint32_t* last);

The number of overflow check could be greatly reduced in the above equation.

[robertmac...@gmail.com]

On Sunday, November 25, 2012 10:31:18 AM UTC-8, Marc Thibault wrote:

I also believe that safe-numerics is very good. I think the problem of integers that grows at runtime has to be done in a different library. Also, there is the independent problem of creating efficient accumulators.

safe_int<int64_t> i;
i.accumulate(uint32_t* first, uint32_t* last);

The number of overflow check could be greatly reduced in the above equation.

The SafeInt as well as safe<int64> don't have an accumulate function.  They are meant to be drop-in replacements for the base type int64.  Adding a new interface would be a whole new kettle of fish.

Besides,  dont' think anything more is needed though.

safe<int64> total;

for(..
    int32 x.
   ....
    total += x;
}
would work just fine and throws if the total were to overflow.

Robert Ramey

[Vicente J. Botet Escriba]

Le 25/11/12 19:31, Marc Thibault a �crit :

> I also believe that safe-numerics is very good. I think the problem of
> integers that grows at runtime has to be done in a different library.
> Also, there is the independent problem of creating efficient accumulators.
>
> safe_int<int64_t> i;
> i.accumulate(uint32_t* first, uint32_t* last);
>
> The number of overflow check could be greatly reduced in the above
> equation.

Well all this depends of the initial value of i. If it is 0, I agree
that a accumulate member function could avoid lost of the overloads checks.
I will suggest then that the accumulate function be a free function and
return just a int64_t, so the result initialization is mastered by the
algorithm.

-- Vicente

[Vicente J. Botet Escriba]

Le 08/11/12 03:59, Ben Craig a écrit :

SafeInt information can be found here.  Basically, it is an open source library authored by security expert David LeBlanc of Microsoft.  It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur.  I believe that getting this added to the standard would be a boon to C++ and secure code.  It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.

--
 
 
 

Hi,

have you take a look at "C++ Binary Fixed-Point Arithmetic" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?

It seems to respond to most of the problems (if not all) you try to solve.

Could you comment features you want  that this proposal doesn't covers?

-- Vicente

[robertmac...@gmail.com]

On Sunday, November 25, 2012 1:39:58 PM UTC-8, viboes wrote:

Le 08/11/12 03:59, Ben Craig a écrit :

Hi,

have you take a look at "C++ Binary Fixed-Point Arithmetic" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?

It seems to respond to most of the problems (if not all) you try to solve.

Could you comment features you want  that this proposal doesn't covers?

Very interesting.  i don't know whether or not I saw this when I made my version of safe<T>.

In general, I see it as very similar.  But there are some notable differences.

"The fixed-point library contains four class templates. They are cardinal and integral for integer arithmetic, and nonnegative and negatable for fractional arithmetic."

a) I use the integer traits defined by std::limits<T> to determined whether the type is signed/unsigned, the max/min, etc. So instead of having a variety of templates, there is only one using TMP to determine the traits.

b) I don't address fractions or rounding at all. 

c) I considered a policy parameter of some sort to indicate how to handle overflows - they use an enum to select.  But I rejected the idea for two reasons

i) more complexity with very little value.
ii)  I couldn't see how to do it with something like

safe<int32> x;
safe<int16> y;
safe<int32> z;
z = x + y;  // where would the policy parameter go?

In the end, I re-focused on a drop-in replacement for all integer types.  "all integer types" means all types - instrinsic and user defined types for which std::limit<T>::is_integer() return true.

To summarize,  SafeInt and safe<T> are different than the proposal in the paper above.  But I believe they are better.

Robert Ramey

-- Vicente

[Vicente J. Botet Escriba]

Le 25/11/12 23:07, robertmac...@gmail.com a écrit :

On Sunday, November 25, 2012 1:39:58 PM UTC-8, viboes wrote:

Le 08/11/12 03:59, Ben Craig a écrit :

Hi,

have you take a look at "C++ Binary Fixed-Point Arithmetic" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?

It seems to respond to most of the problems (if not all) you try to solve.

Could you comment features you want  that this proposal doesn't covers?

Very interesting.  i don't know whether or not I saw this when I made my version of safe<T>.

My question was addressed to the PO. Anyway ...

In general, I see it as very similar.  But there are some notable differences.

"The fixed-point library contains four class templates. They are cardinal and integral for integer arithmetic, and nonnegative and negatable for fractional arithmetic."

a) I use the integer traits defined by std::limits<T> to determined whether the type is signed/unsigned, the max/min, etc. So instead of having a variety of templates, there is only one using TMP to determine the traits.

I don't see an added value at the user level. I'm open to variations.

b) I don't address fractions or rounding at all. 

Well, this is out of the PO subject, so no matter. I could understand that we could want safe integers independently.

c) I considered a policy parameter of some sort to indicate how to handle overflows - they use an enum to select.  But I rejected the idea for two reasons

i) more complexity with very little value.
ii)  I couldn't see how to do it with something like

safe<int32> x;
safe<int16> y;
safe<int32> z;
z = x + y;  // where would the policy parameter go?

With the Lawrence proposal you don't have overflow as far as you don't loss range. So the natural place is to use it only with assignment.

integral<31,OV1> x;
integral<15,OV2> y;
integral<31,OV3> z;

z = x + y;

Check for overflow only when doing the assignment using the overflow OV3 policy.

The fact to add the overflow policy on the type makes the code less weight.

We can have also a base class for integral that has no overflow policy and forbids assignment that can loss information

basic_integral<31> x;
basic_integral<15> y;
basic_integral<31> z;
z = x + y; // compile file

The user will need to use a number_cast conversion like in

z = number_cast<OV3>(x + y);

In the end, I re-focused on a drop-in replacement for all integer types.  "all integer types" means all types - instrinsic and user defined types for which std::limit<T>::is_integer() return true.

To summarize,  SafeInt and safe<T> are different than the proposal in the paper above.  But I believe they are better.

Humm, I need then to read both ;-) But do the PO proposal or your Safe library allow to saturate on overflow, assert, ignore, ...?

Best,
Vicente

[Vicente J. Botet Escriba]

Le 26/11/12 08:17, Vicente J. Botet Escriba a écrit :

Where can I get the documentation of the PO proposal?

I wanted to add. safe<T> could be defined as a alias of the fixed point class.

-- Vicente

[Ben Craig]

Some large use cases for SafeInt are computing sizes for buffers and array indices.  In these situations, you probably want to throw an exception, or terminate the program.  Saturation, assertions in debug mode, and ignoring aren't very good options from a security standpoint.

Are the saturate, debug assert, and ignore cases useful in some other domain?  I can see some use for saturation in some cases where a (possibly implicit) range check was already present.  For instance, if I'm doing some calculations with the volume on my speakers, I may have an acceptable range of 0 - 65,535.  If my math comes up with a volume of 100,000, then setting the volume to 65,535 may be reasonable.  I don't know how often this kind of thing comes up though.

If you stick to "drop-in" replacements, then I'm not sure if there's any benefit to an "ignore" policy.  Ignore is equivalent to the raw type.  Fixed-point libraries could make use of it though.  Debug assertions aren't any better from a security standpoint, but they could help discover bugs in non-security critical code.

[robertmac...@gmail.com]

On Sunday, November 25, 2012 11:17:04 PM UTC-8, viboes wrote:

c) I considered a policy parameter of some sort to indicate how to handle overflows - they use an enum to select.  But I rejected the idea for two reasons

i) more complexity with very little value.
ii)  I couldn't see how to do it with something like

safe<int32> x;
safe<int16> y;
safe<int32> z;
z = x + y;  // where would the policy parameter go?

With the Lawrence proposal you don't have overflow as far as you don't loss range. So the natural place is to use it only with assignment.

It's exactly the same with safe<T>.  EXCEPT the case where safe<int64> + safe<int64> where there is not large type to hold the intermediate result. That is, the overflow can occur before the assignment.  In this case, it throws immediately.  I struggled on how to avoid this - but solutions seemed more and more heavy weight.

integral<31,OV1> x;
integral<15,OV2> y;
integral<31,OV3> z;
z = x + y;

Check for overflow only when doing the assignment using the overflow OV3 policy.

I suppose this could be made to work - except for the note above.

The fact to add the overflow policy on the type makes the code less weight.

We can have also a base class for integral that has no overflow policy and forbids assignment that can loss information

basic_integral<31> x;
basic_integral<15> y;
basic_integral<31> z;
z = x + y; // compile file

The user will need to use a number_cast conversion like in

z = number_cast<OV3>(x + y);

I wanted to avoid this so as to keep the "drop-in" replacement functionality. I want people take a program with bugs in it,  change all their "int" to safe<int>, etc. run the program and trap errors. This makes the library much, much more attractive to use.

 

But do the PO proposal or your Safe library allow to saturate on overflow, assert, ignore, ...?

The safe<T> throws an exception.  Users would have to trap the exception if they want to handle it in some specific way.  I considered alternatives, but I felt that if something traps it's almost always an unrecoverable error - ie a programming error - so making it any fancier than necessary would be counter productive - also refer to the note above regarding trying to specify a policy.

The thread started with the proposal to consider SafeInt for inclusion in the standard library.  safe<T> should be considered in this light.

Other proposals - modular arithmetic, decimal integers, etc should be considered separately.

Note that safe<T> uses the traits defined in std::limits so that it should be possible to apply safe<T> to any type which has std::limits<T> implemented.  (I doubt it's possible now - but I believe it can be made to work).  This would leave the concept of "safe" as orthogonal to the "number type" which is also where I believe we would want to be.

Robert Ramey.

Robert Ramey
 

Best,
Vicente

[robertmac...@gmail.com]

I wanted to add. safe<T> could be defined as a alias of the fixed point class.

I would like to keep the "save" concept/idea orthogonal to the "numeric" concept/idea.

Robert Ramey

-- Vicente

[robertmac...@gmail.com]

On Monday, November 26, 2012 8:59:59 AM UTC-8, Ben Craig wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.  In these situations, you probably want to throw an exception, or terminate the program.  Saturation, assertions in debug mode, and ignoring aren't very good options from a security standpoint.

agreed.  But note that SafeInt or safe<unsigned int> aren't that useful for things like buffer sizes or array indices unless they happen to be exactly max<unsigned int> long or something like that.

However, it turns out there is a very slick solution here.  When I started this effort what I really wanted to make was "save_range<min, max> for just this purpose.  I made this and since it depended upon std::limits, it could use the equivalent of

template<T>
safe : public safe_range<std::limits<T>:min, safe_range<std::limits<T>:max> {
};

to make safe<int> etc.

So to trap array and buffer overflows one would already have (for free)

char a[12345];
safe_unsigned_range<0, sizeof(a)> aindex;

and you're in business. It's actually a side effect of the way it's implemented.
 .

If you stick to "drop-in" replacements, then I'm not sure if there's any benefit to an "ignore" policy.  Ignore is equivalent to the raw type. 

+1
 

Fixed-point libraries could make use of it though.  Debug assertions aren't any better from a security standpoint, but they could help discover bugs in non-security critical code.

I would like to avoid "feature creep"

Robert Ramey
 

[Lawrence Crowl]

On 11/23/12, Fernando Cacciola <fernando...@gmail.com> wrote:

> On Nov 23, 2012 <robertmac...@gmail.com> wrote:
> > On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:
> > > That would likely turn into a fixed-point arithmetic

> > > <http://en.wikipedia.org/wiki/Fixed-point_arithmetic> library.

>
> I would rather say that a fixed-point library, as well as a
> rationals library, would be alongside (or maybe one level above)
> safe-int, as opposed to a generalization of it.

The committee has a Study Group 6 addressing issues of number
representation. One of the tasks is figuring out the logical
relationships and implementation relationships between various
number types.

We welcome contributions.

> Both fixed_point<T> and rational<T> are useful as long as the
> values do not overflow. However, and this is particularly true in
> the case of rationals, there are several application domains where
> computations can easily, and often, overflow. In these cases, one
> must use a big_int (unlimited precision integer) as T (whether for
> a fixed_point or rational) But that is pessimistically inefficient,
> so one would consider a non-template "exact" numeric type which
> would have a dynamic internal representation of rational<T>
> but which would automatically switch from T to 2T (meaning a two
> times bigger integer), until it reaches big_int.

The study group has reached a tentative conclusion that a rational
should be based either on a bigint, or do rounding when the
representation is not sufficient for the true result. The former
would be useful in computational geometry. The latter would be
useful in music.

Fixed point is useful even in the presence of overflow, but the
method for dealing with the overflow may vary depending on the
application. In these cases, I think it generally best to give
program the tools they need, rather than pick a single solution.
(Plain unsigned ints picked one solution, and it is inappropriate
in a number of cases.)

--
Lawrence Crowl

[Lawrence Crowl]

On 11/25/12, Vicente J. Botet Escriba <vicent...@wanadoo.fr> wrote:
> Le 25/11/12 23:07, robertmac...@gmail.com a écrit :
> > On Sunday, November 25, 2012 1:39:58 PM UTC-8, viboes wrote:
> > > Le 08/11/12 03:59, Ben Craig a écrit :

> > > > have you take a look at "C++ Binary Fixed-Point Arithmetic"
> > > > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html

> > > > <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html>?

> > > >
> > > > It seems to respond to most of the problems (if not all)
> > > > you try to solve.
> > > >
> > > > Could you comment features you want that this proposal
> > > > doesn't covers?
> >
> > Very interesting. i don't know whether or not I saw this when
> > I made my version of safe<T>.
>
> My question was addressed to the PO. Anyway ...
>
> > In general, I see it as very similar. But there are some
> > notable differences.
> >
> > "The fixed-point library contains four class templates. They
> > are |cardinal| and |integral| for integer arithmetic, and
> > |nonnegative| and |negatable| for fractional arithmetic."
> >
> > a) I use the integer traits defined by std::limits<T> to
> > determined whether the type is signed/unsigned, the max/min,
> > etc. So instead of having a variety of templates, there is only
> > one using TMP to determine the traits.
>
> I don't see an added value at the user level. I'm open to
> variations.

I am the author of that proposal. The difference is that my proposal
is parameterized by the number of bits, not by a representation type.
The implementation is responsible for picking a representation
suitable to the number of bits and the sign. So, in my proposal,
there is no type parameter available to extract that the information.

That was part of the feedback from the committee's first review
of the proposal.

> > In the end, I re-focused on a drop-in replacement for all integer
> > types. "all integer types" means all types - instrinsic and user
> > defined types for which std::limit<T>::is_integer() return true.
> >
> > To summarize, SafeInt and safe<T> are different than the proposal
> > in the paper above. But I believe they are better.
>
> Humm, I need then to read both ;-) But do the PO proposal or your
> Safe library allow to saturate on overflow, assert, ignore, ...?

A safe integer proposal and my fixed-point proposal do serve
different purposes. My proposal works best when the range and
precision is derivable from the data, e.g. pixel values. A safe
integer type works best when the range is derivable from the machine,
e.g. indexing.

So, I think there is room for a safe integer proposal. I would,
however, like to see in conceptually integrated with my proposal
so that we have one mechanism for specifying overflow behavior, etc.

--
Lawrence Crowl

[Lawrence Crowl]

On 11/26/12, Ben Craig <ben....@gmail.com> wrote:
> Some large use cases for SafeInt are computing sizes for buffers
> and array indices. In these situations, you probably want
> to throw an exception, or terminate the program. Saturation,
> assertions in debug mode, and ignoring aren't very good options
> from a security standpoint.

Not necessarily true. An exception could be vulnerable to a
denial-of-service attack, where as saturation may just deliver
fewer widgets than desired.

> Are the saturate, debug assert, and ignore cases useful in some
> other domain? I can see some use for saturation in some cases
> where a (possibly implicit) range check was already present.
> For instance, if I'm doing some calculations with the volume
> on my speakers, I may have an acceptable range of 0 - 65,535.
> If my math comes up with a volume of 100,000, then setting the
> volume to 65,535 may be reasonable. I don't know how often this
> kind of thing comes up though.

It comes up often in signal processing applications. The C standard
has an option for fixed-point arithmetic, and it allow saturated
arithmetic for exactly this reason.

> If you stick to "drop-in" replacements, then I'm not sure if
> there's any benefit to an "ignore" policy. Ignore is equivalent to
> the raw type. Fixed-point libraries could make use of it though.
> Debug assertions aren't any better from a security standpoint,
> but they could help discover bugs in non-security critical code.

Can we be clear on what "ignore" means? I have two policies in mind,
both of which allow the implementation to ignore overflow.

"I have done a mathematical proof that overflow cannot occur.
Code reviewers please check my proof."

"I have really low reliability constraints, and do not have the need
or time to make the code correct in all circumstances. Don't bother
me with overflow."

--
Lawrence Crowl

[Lawrence Crowl]

On 11/26/12, robertmac...@gmail.com

<robertmac...@gmail.com> wrote:
> On Sunday, November 25, 2012 11:17:04 PM UTC-8, viboes wrote:
> > > c) I considered a policy parameter of some sort to indicate
> > > how to handle overflows - they use an enum to select. But I
> > > rejected the idea for two reasons
> > >
> > > i) more complexity with very little value.
> > > ii) I couldn't see how to do it with something like
> > >
> > > safe<int32> x;
> > > safe<int16> y;
> > > safe<int32> z;
> > > z = x + y; // where would the policy parameter go?
> >
> > With the Lawrence proposal you don't have overflow as far as
> > you don't loss range. So the natural place is to use it only
> > with assignment.
>
> It's exactly the same with safe<T>. EXCEPT the case where
> safe<int64> + safe<int64> where there is not large type to
> hold the intermediate result. That is, the overflow can occur
> before the assignment. In this case, it throws immediately.
> I struggled on how to avoid this - but solutions seemed more and
> more heavy weight.

Given that expressions can have an arbitrary number of operators,
how do you handle other intermediate results that might overflow?

> > integral<31,OV1> x;
> > integral<15,OV2> y;
> > integral<31,OV3> z;
> > z = x + y;
> >
> > Check for overflow only when doing the assignment using the
> > overflow OV3 policy.
>
> I suppose this could be made to work - except for the note above.

The intent in the fixed-point library is that the intermediate type
would switch to a multi-precision implementation. An alternative
is cause a compilation error.

> > The fact to add the overflow policy on the type makes the code
> > less weight.
> >
> > We can have also a base class for integral that has no overflow
> > policy and forbids assignment that can loss information
> >
> > basic_integral<31> x;
> > basic_integral<15> y;
> > basic_integral<31> z;
> > z = x + y; // compile file
> >
> > The user will need to use a number_cast conversion like in
> >
> > z = number_cast<OV3>(x + y);
>
> I wanted to avoid this so as to keep the "drop-in" replacement
> functionality. I want people take a program with bugs in it,
> change all their "int" to safe<int>, etc. run the program and trap
> errors. This makes the library much, much more attractive to use.

I agree that this approach will produce a valuable tool.

> > But do the PO proposal or your Safe library allow to saturate
> > on overflow, assert, ignore, ...?
>
> The safe<T> throws an exception. Users would have to trap
> the exception if they want to handle it in some specific way.
> I considered alternatives, but I felt that if something traps it's
> almost always an unrecoverable error - ie a programming error - so
> making it any fancier than necessary would be counter productive -
> also refer to the note above regarding trying to specify a policy.
>
> The thread started with the proposal to consider SafeInt for
> inclusion in the standard library. safe<T> should be considered
> in this light.
>
> Other proposals - modular arithmetic, decimal integers, etc should
> be considered separately.

I agree that a safe-int proposal make sense, but we want the proposal
to integrate with the language and library as a whole. We have a
study group to avoid unintended incompatibilities within the C++
library. So, all these proposals should be considered together.

> Note that safe<T> uses the traits defined in std::limits so that
> it should be possible to apply safe<T> to any type which has
> std::limits<T> implemented. (I doubt it's possible now - but I
> believe it can be made to work). This would leave the concept of
> "safe" as orthogonal to the "number type" which is also where I
> believe we would want to be.

I have less confidence that we can have one definition of "safe",
let alone apply it uniformly to all numbers.

--
Lawrence Crowl

[Vicente J. Botet Escriba]

Le 23/11/12 18:10, robertmac...@gmail.com a écrit :

On Friday, November 23, 2012 4:26:08 AM UTC-8, Fernando Cacciola wrote:

On Fri, Nov 23, 2012 at 3:45 AM, <robertmac...@gmail.com> wrote:

On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:

 
That would likely turn into a fixed-point arithmetic library.

I would rather say that a fixed-point library, as well as a rationals library, would be alongside (or maybe one level above) safe-int, as opposed to a generalization of it.

I'm not sure I followed your suggestion, but somehow I'm thinking I might be in agreement. My view would be the "safe" idea would be orthogonal to the "numeric" idea.  So

int, rational<T>, multiprecision<N>, .... would have std limits<T> defined. std::limits includes members to define min/max values and a lot of other features of numeric types.

This would make them fullfill the "Numeric" concept (type requirements).

safe<T> would be defined for any type T fullfilling the "Numeric" concept.

safe and integers could be orthogonal, but I don't see how a safe<T> class could provide safety to rational as overflow is avoided by using gcd while doing the addition of two rationals and many other tricks.

and safe<T> would also have std::limits implemented so it would fullfill the "Numeric" concept as well.

This would separate the "safe" idea from the "numeric" idea and permit users to use the "safe" version if and only if actually desired.  It would also clarify what "safe" does as opposed to what "numeric" does.  My proposal implements this idea for current integer types. 

So maybe your class should be renamed as safe_int ;-)

It hasn't really been investigated whether this extends well to all integer types for which std::limits is implemented.  Anyway, this is far into the future.

I guess you meant any number type.

-- Vicente

[robertmac...@gmail.com]

On Monday, November 26, 2012 3:32:09 PM UTC-8, viboes wrote:

Le 23/11/12 18:10, robertmac...@gmail.com a écrit :safe and integers could be orthogonal, but I don't see how a safe<T> class could provide safety to rational as overflow is avoided by using gcd while doing the addition of two rationals and many other tricks.

then safe<rational> wouldn't throw on overflow - because it can't happen.  Same with save<multi-precision>.  But currently safe<T> throws on at attempt to divide by zero.  So the concept is easily extended to other numeric types.  I can easily imagine a safe<float> and safe<double> which could overflow, underflow and device by zero.  Basically safe<T> would throw anytime and operation on T doesn't yield the expected mathematical result.

Note that I'm getting ahead of myself here.  safe<T> is only implemented for types which are integers according to std::limits<T>.  For other types it will trip a compile time assert.
 

Robert Ramey

[Fernando Cacciola]

On Sun, Nov 25, 2012 at 6:39 PM, Vicente J. Botet Escriba <vicent...@wanadoo.fr> wrote:

Le 08/11/12 03:59, Ben Craig a écrit :

SafeInt information can be found here.  Basically, it is an open source library authored by security expert David LeBlanc of Microsoft.  It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur.  I believe that getting this added to the standard would be a boon to C++ and secure code.  It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.
--
 
 
 

Hi,

have you take a look at "C++ Binary Fixed-Point Arithmetic" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3352.html?

I've been wanting to read that proposal, but never did before.

It looks to me that it is a very good proposal BTW 

[Fernando Cacciola]

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

Hmmm.
Can you elaborate how is SafeInt safe when it comes to an array index in the case of an array of runtime size? Which I believe is, by far, the most common type of array (buffer, container, etc)

For *that* purpose I think the proper tool is an integer with runtime boundaries (a number of these have been implemented and proposed to, for instance, Boost)

 

  In these situations, you probably want to throw an exception, or terminate the program. 

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

 

Saturation, assertions in debug mode, and ignoring aren't very good options from a security standpoint.

Maybe. It depends on how you define security.
But for sure those are good options in several application domains, and a standard C++ library facility should consider them all (as much as possible)
 

[Fernando Cacciola]

On Mon, Nov 26, 2012 at 2:45 PM, <robertmac...@gmail.com> wrote:

On Sunday, November 25, 2012 11:17:04 PM UTC-8, viboes wrote:

c) I considered a policy parameter of some sort to indicate how to handle overflows - they use an enum to select.  But I rejected the idea for two reasons

i) more complexity with very little value.
ii)  I couldn't see how to do it with something like

safe<int32> x;
safe<int16> y;
safe<int32> z;
z = x + y;  // where would the policy parameter go?

With the Lawrence proposal you don't have overflow as far as you don't loss range. So the natural place is to use it only with assignment.

It's exactly the same with safe<T>.  EXCEPT the case where safe<int64> + safe<int64> where there is not large type to hold the intermediate result. That is, the overflow can occur before the assignment.  In this case, it throws immediately.  I struggled on how to avoid this - but solutions seemed more and more heavy weight.

Hmm, how isn't is as simple as using a software-based int128 number type?
 

integral<31,OV1> x;
integral<15,OV2> y;
integral<31,OV3> z;
z = x + y;

Check for overflow only when doing the assignment using the overflow OV3 policy.

I suppose this could be made to work - except for the note above.

The fact to add the overflow policy on the type makes the code less weight.

We can have also a base class for integral that has no overflow policy and forbids assignment that can loss information

basic_integral<31> x;
basic_integral<15> y;
basic_integral<31> z;
z = x + y; // compile file

The user will need to use a number_cast conversion like in

z = number_cast<OV3>(x + y);

I wanted to avoid this so as to keep the "drop-in" replacement functionality. I want people take a program with bugs in it,  change all their "int" to safe<int>, etc. run the program and trap errors.

Imagine you have a program and you get a division by zero exception . What do you do
You change the program so that, instead of attempting a computation that cannot be performed, it determines the case and handle the "exceptional case" manually in a different way.
You could just let the exception abort the current execution block but that's NOT the way division by zero is handled.

Now suppose you change all the 'int' for safe<int> and you discover a point where overflow is occurring?  What do you do?
By analogy to the div-by-zero case, and IME (and I do have experience writing algorithms that need handle overflow, both integer and floating-point), you also want to detect the case before-hand so you can do something else.
Simply changing a program so that instead of UB it throws is a step ahead, but it's a too general solution that surely works for general application code. But if you are writing a numerical algorithm OTOH you need, for example, to have a clean and simple way to handle the overflow and do something else *without* aborting the computation.

 

 

But do the PO proposal or your Safe library allow to saturate on overflow, assert, ignore, ...?

The safe<T> throws an exception.  Users would have to trap the exception if they want to handle it in some specific way.  I considered alternatives, but I felt that if something traps it's almost always an unrecoverable error - ie a programming error

Wait.
Numerical overflow is *rarely* a programming error. It's the consequence of finite precision when crunching numbers.

[Fernando Cacciola]

On Mon, Nov 26, 2012 at 7:59 PM, Lawrence Crowl <cr...@googlers.com> wrote:

On 11/23/12, Fernando Cacciola <fernando...@gmail.com> wrote:

> On Nov 23, 2012 <robertmac...@gmail.com> wrote:
> > On Thursday, November 22, 2012 6:10:24 PM UTC-8, Ben Craig wrote:
> > > That would likely turn into a fixed-point arithmetic

> > > <http://en.wikipedia.org/wiki/Fixed-point_arithmetic> library.

>
> I would rather say that a fixed-point library, as well as a
> rationals library, would be alongside (or maybe one level above)
> safe-int, as opposed to a generalization of it.

The committee has a Study Group 6 addressing issues of number
representation.  One of the tasks is figuring out the logical
relationships and implementation relationships between various
number types.

We welcome contributions.

How do I join Study Group 6 ?

I would very much like to contribute.
 

> Both fixed_point<T> and rational<T> are useful as long as the
> values do not overflow. However, and this is particularly true in
> the case of rationals, there are several application domains where
> computations can easily, and often, overflow. In these cases, one
> must use a big_int (unlimited precision integer) as T (whether for
> a fixed_point or rational) But that is pessimistically inefficient,
> so one would consider a non-template "exact" numeric type which
> would have a dynamic internal representation of rational<T>
> but which would automatically switch from T to 2T (meaning a two
> times bigger integer), until it reaches big_int.

The study group has reached a tentative conclusion that a rational
should be based either on a bigint, or do rounding when the
representation is not sufficient for the true result.  The former
would be useful in computational geometry.  The latter would be
useful in music.

I agree. Well almost.
There are significant efficiency concerns when using bigint, and I think that in C++  it's possible to overcome that by means of a mechanism that promotes to "the next most efficient integer type needed" as computations are performed.
Something of this form has been done, sort of manually, over the past decade or more, in different unrelated projects, and it would be fantastic to capture some of that within standard C++

Fixed point is useful even in the presence of overflow, but the
method for dealing with the overflow may vary depending on the
application.  In these cases, I think it generally best to give
program the tools they need, rather than pick a single solution.
(Plain unsigned ints picked one solution, and it is inappropriate
in a number of cases.)

Agreed.

[Ben Craig]

On Tue, Nov 27, 2012 at 7:32 AM, Fernando Cacciola <fernando...@gmail.com> wrote:

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

Hmmm.
Can you elaborate how is SafeInt safe when it comes to an array index in the case of an array of runtime size? Which I believe is, by far, the most common type of array (buffer, container, etc)

For *that* purpose I think the proper tool is an integer with runtime boundaries (a number of these have been implemented and proposed to, for instance, Boost)

Without a facility like SafeInt, a developer would likely write (buggy) code like this:
size_t index = user_controlled_x+user_controlled_y;
if(index > array_size)
   throw std::range_error("");

With SafeInt, you get something like this:
SafeInt<size_t> index = SafeInt<uint32_t>(user_controlled_x)+SafeInt<uint32_t>(user_controlled_y);
if(index > array_size)
   throw std::range_error("");

SafeInt doesn't do everything for you, but it gets the difficult checks out of the way, and lets the programmer handle the easy, program specific checks.  A more fully range checked class might be appropriate, but there isn't as much field experience with that.

 

  In these situations, you probably want to throw an exception, or terminate the program. 

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

If you hit undefined behavior, you should probably terminate the program as quickly as possible.  This is the approach that "stack canary" implementations take.  However, since we are talking about C++ spec work here, we should probably only talk about things with defined behavior.  For those, I agree with you that exceptions are the better approach.
 

Saturation, assertions in debug mode, and ignoring aren't very good options from a security standpoint.

Maybe. It depends on how you define security.
But for sure those are good options in several application domains, and a standard C++ library facility should consider them all (as much as possible)

 

Let's take it from a code review standpoint.  If SafeInt (or some alternative) is used, then any place where C++ "a+b" is not the same as arithmetic "a+b", you should get an exception, or there should be something explicit in the code indicating that a different policy is required at that point.  Maybe the "drop-in" stuff only allows exceptions, but saturation and modulo arithmetic get free functions?  "short myVal = saturation_cast<short>(x, 0, 100);"

[Olaf van der Spek]

On Tuesday, November 27, 2012 3:54:38 PM UTC+1, Ben Craig wrote:

Without a facility like SafeInt, a developer would likely write (buggy) code like this:

size_t index = user_controlled_x+user_controlled_y;
if(index > array_size)
   throw std::range_error("");

With SafeInt, you get something like this:
SafeInt<size_t> index = SafeInt<uint32_t>(user_controlled_x)+SafeInt<uint32_t>(user_controlled_y);
if(index > array_size)
   throw std::range_error("");

I assume you meant index >= array_size? :p 

[Fernando Cacciola]

On Mon, Nov 26, 2012 at 11:16 PM, <robertmac...@gmail.com> wrote:

On Monday, November 26, 2012 3:32:09 PM UTC-8, viboes wrote:

Le 23/11/12 18:10, robertmac...@gmail.com a écrit :safe and integers could be orthogonal, but I don't see how a safe<T> class could provide safety to rational as overflow is avoided by using gcd while doing the addition of two rationals and many other tricks.

then safe<rational> wouldn't throw on overflow - because it can't happen. 

Strictly speaking, you can end up with an irreductible fraction. In that case, operating with such a fraction can overflow.

OTOH, gcd is time consuming, so it is sometimes more efficient to just use big enough integers as long as you can, for which you need to have a form of overflow management.

[Olaf van der Spek]

On Tuesday, November 27, 2012 2:33:03 PM UTC+1, Fernando Cacciola wrote:

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

Why not? The difference between aborting and throwing is basically whether you can catch and continue (safely). 

For the majority of apps aborting is fine for certain errors and exceptions aren't without cost and can't be used everywhere.

[Fernando Cacciola]

On Tue, Nov 27, 2012 at 11:54 AM, Ben Craig <ben....@gmail.com> wrote:

On Tue, Nov 27, 2012 at 7:32 AM, Fernando Cacciola <fernando...@gmail.com> wrote:

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

Hmmm.
Can you elaborate how is SafeInt safe when it comes to an array index in the case of an array of runtime size? Which I believe is, by far, the most common type of array (buffer, container, etc)

For *that* purpose I think the proper tool is an integer with runtime boundaries (a number of these have been implemented and proposed to, for instance, Boost)

Without a facility like SafeInt, a developer would likely write (buggy) code like this:
size_t index = user_controlled_x+user_controlled_y;
if(index > array_size)
   throw std::range_error("");

With SafeInt, you get something like this:
SafeInt<size_t> index = SafeInt<uint32_t>(user_controlled_x)+SafeInt<uint32_t>(user_controlled_y);
if(index > array_size)
   throw std::range_error("");

SafeInt doesn't do everything for you, but it gets the difficult checks out of the way, and lets the programmer handle the easy, program specific checks.  A more fully range checked class might be appropriate, but there isn't as much field experience with that.

OK, I see the motivation to make sure you don't compute an index value the wrong way, accidentally because of the current limitations with integer types.
 

 

  In these situations, you probably want to throw an exception, or terminate the program. 

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

If you hit undefined behavior, you should probably terminate the program as quickly as possible.  This is the approach that "stack canary" implementations take.  However, since we are talking about C++ spec work here, we should probably only talk about things with defined behavior.  For those, I agree with you that exceptions are the better approach.
 

Saturation, assertions in debug mode, and ignoring aren't very good options from a security standpoint.

Maybe. It depends on how you define security.
But for sure those are good options in several application domains, and a standard C++ library facility should consider them all (as much as possible)

 

Let's take it from a code review standpoint.  If SafeInt (or some alternative) is used, then any place where C++ "a+b" is not the same as arithmetic "a+b", you should get an exception, or there should be something explicit in the code indicating that a different policy is required at that point.  Maybe the "drop-in" stuff only allows exceptions, but saturation and modulo arithmetic get free functions?  "short myVal = saturation_cast<short>(x, 0, 100);"

I agree that, for an utility intended to be a drop-in replacement for 'int', should simply throw in the case of overflow (when it is assigned, or in corner cases).
I also agree that such an utility might be useful.

Having said that, I still think we need a lower layer, used by such an utility, that would also be used by other similar utilities (like fixed_int<>). That lower layer would provide general building blocks, with your saturation_cast<short> being a possible one.

[Fernando Cacciola]

I'm tempted to respond, but I think this thread is not the correct place. (and I'm not sure where would be)

Anyway, let me just rephrase that: IMO, the *end user* never ever wants you the programmer to structure the program in such a way that the *entire application* must abort as opposed to the current "task" (task from the end user POV )

 

[Vicente J. Botet Escriba]

Le 27/11/12 00:28, Lawrence Crowl a �crit :

> On 11/26/12, robertmac...@gmail.com
> <robertmac...@gmail.com> wrote:
>> I wanted to avoid this so as to keep the "drop-in" replacement
>> functionality. I want people take a program with bugs in it,
>> change all their "int" to safe<int>, etc. run the program and trap
>> errors. This makes the library much, much more attractive to use.
> I agree that this approach will produce a valuable tool.
>
>

I don't know if I understand your use case, you want to use safe as a
debug tool, then IMHO the best should be to terminate the program, isn't
it?

I don't know if your SafeInt/safe<T> prevents from assignments from
signed values to unsigned types, but this could also be useful.

-- Vicente

[Vicente J. Botet Escriba]

Le 27/11/12 03:16, robertmac...@gmail.com a écrit :

On Monday, November 26, 2012 3:32:09 PM UTC-8, viboes wrote:

Le 23/11/12 18:10, robertmac...@gmail.com a écrit :safe and integers could be orthogonal, but I don't see how a safe<T> class could provide safety to rational as overflow is avoided by using gcd while doing the addition of two rationals and many other tricks.

then safe<rational> wouldn't throw on overflow - because it can't happen. 

Sorry, I wanted to say "to avoid intermediary overflows (before normalization)". To compute  {n1/d1}+{n2/d2} the rational library makes some intermediate operation on the rational value type as products, additions and divisions that can overflow. But nothing ensures you that the template parameter T of rational is safe.

Same with save<multi-precision>.  But currently safe<T> throws on at attempt to divide by zero.  So the concept is easily extended to other numeric types.  I can easily imagine a safe<float> and safe<double> which could overflow, underflow and device by zero.  Basically safe<T> would throw anytime and operation on T doesn't yield the expected mathematical result.

Maybe you are right. We need a concrete proposal (only for integral types or for numbers in general) to continue the discussion.

--Vicente

[Marshall Clow]

The key is "for the majority of apps" is the key.

This is a decision that needs to be made by the app developer, not the library developer.

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow...@gmail.com>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki

[Marshall Clow]

On Nov 27, 2012, at 11:44 AM, Marshall Clow <mclow...@gmail.com> wrote:

On Nov 27, 2012, at 9:33 AM, Olaf van der Spek <olafv...@gmail.com> wrote:

On Tuesday, November 27, 2012 2:33:03 PM UTC+1, Fernando Cacciola wrote:

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

Why not? The difference between aborting and throwing is basically whether you can catch and continue (safely). 

For the majority of apps aborting is fine for certain errors and exceptions aren't without cost and can't be used everywhere.

The key is "for the majority of apps" is the key.

Sigh. Bad editing strikes again.

"For the majority of apps" is the key phrase.

[Fernando Cacciola]

Olaf moved this into std-discussions.

This is a decision that needs to be made by the app developer, not the library developer.

And that totally summarizes my point, but since it seems that is not at all obvious what that implies in terms of library design, I will try to elaborate on that in the other thread.

[robertmac...@gmail.com]

On Tuesday, November 27, 2012 5:44:44 AM UTC-8, Fernando Cacciola wrote:

On Mon, Nov 26, 2012 at 2:45 PM, <robertmac...@gmail.com> wrote:

On Sunday, November 25, 2012 11:17:04 PM UTC-8, viboes wrote:

c) I considered a policy parameter of some sort to indicate how to handle overflows - they use an enum to select.  But I rejected the idea for two reasons

i) more complexity with very little value.
ii)  I couldn't see how to do it with something like

safe<int32> x;
safe<int16> y;
safe<int32> z;
z = x + y;  // where would the policy parameter go?

With the Lawrence proposal you don't have overflow as far as you don't loss range. So the natural place is to use it only with assignment.

It's exactly the same with safe<T>.  EXCEPT the case where safe<int64> + safe<int64> where there is not large type to hold the intermediate result. That is, the overflow can occur before the assignment.  In this case, it throws immediately.  I struggled on how to avoid this - but solutions seemed more and more heavy weight.

Hmm, how isn't is as simple as using a software-based int128 number type?

a software based int128 type doesn't handle the problem.  what about

int64 x, y;
y = x * x * x;

Only an arbitray length multi-precision intermediate type could defer all checking until the next assigment.

 

Imagine you have a program and you get a division by zero exception . What do you do
You change the program so that, instead of attempting a computation that cannot be performed, it determines the case and handle the "exceptional case" manually in a different way.
You could just let the exception abort the current execution block but that's NOT the way division by zero is handled.

 
Now suppose you change all the 'int' for safe<int> and you discover a point where overflow is occurring?  What do you do?

you fix the program.
 

By analogy to the div-by-zero case, and IME (and I do have experience writing algorithms that need handle overflow, both integer and floating-point), you also want to detect the case before-hand so you can do something else.

of course
 

Simply changing a program so that instead of UB it throws is a step ahead, but it's a too general solution that surely works for general application code.

this is the intent of SafeInt and safe<int>.
 

But if you are writing a numerical algorithm OTOH you need, for example, to have a clean and simple way to handle the overflow and do something else *without* aborting the computation.

That's a whole other problem.  The solution is application dependent.  One way would be to use arbitrary multi-precision numbers - but that's a different library.

 

 

But do the PO proposal or your Safe library allow to saturate on overflow, assert, ignore, ...?

The safe<T> throws an exception.  Users would have to trap the exception if they want to handle it in some specific way.  I considered alternatives, but I felt that if something traps it's almost always an unrecoverable error - ie a programming error

Wait.

 

Numerical overflow is *rarely* a programming error. It's the consequence of finite precision when crunching numbers.

that depends on the application.  usually if i just use int or unsigned int I'm expecting the result to match the expected mathmetical result.  If overflow or divide by zero occurs it's a bug. If one wanted to use safe<int> for cases where an overflow is expected, one could trap the exception like

safe<int> x, y;

try{
    x = 256 * 256 * 256 * 256 * 256;
 }
catch(boost:numeric_exception e){
  .... // do your own thing.
}

generally, I'm not crazy about this code - but it has its uses.

Robert Ramey

[robertmac...@gmail.com]

On Tuesday, November 27, 2012 6:54:38 AM UTC-8, Ben Craig wrote:

On Tue, Nov 27, 2012 at 7:32 AM, Fernando Cacciola <fernando...@gmail.com> wrote:

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

 

Let's take it from a code review standpoint.  If SafeInt (or some alternative) is used, then any place where C++ "a+b" is not the same as arithmetic "a+b", you should get an exception,

+1

It's really about producing demonstrably correct code. That is - code which does what one would expect it to do. That's the whole intent - nothing more nothing less.

Robert Ramey

[robertmac...@gmail.com]

On Tuesday, November 27, 2012 10:05:27 AM UTC-8, viboes wrote:

Le 27/11/12 00:28, Lawrence Crowl a �crit :
> On 11/26/12, robertmac...@gmail.com

I don't know if your SafeInt/safe<T> prevents from assignments from
signed values to unsigned types, but this could also be useful.

I can't speak for SafeInt but safe<T> will throw if a negative value is assigned to an unsigned int. 

-- Vicente

[dvd_l...@yahoo.com]

Floating point is in some ways more complex. An issue that would be hard to deal with would be the classic large number + small number, where the result ends up either not changing, or losing a lot of the significant bits of the small number. This could range from by design to disaster, completely depending on the application.

 

I've thought about it, but believe it would take a different class.

 

Having it be a class does make it apply all over the place - here's how - for almost all operations, the return type is a SafeInt or reference to SafeInt. It is thus 'sticky'. For example, say you had:

 

int x, y, z;

unsigned int ret;

// assign x, y, z

 

ret = SafeInt<int>(x) * y + z;

 

The multiplication is performed, checked, result is a temporary SafeInt of type int, addition is performed and checked, result is another temporary. Finally, assignment is performed and checked.

 

It is true that it would be hard to get 3rd party code to use it, though this depends on how the maintainers feel, whether you'd like to fork it. Really the same sort of issue as replacing strcpy with strcpy_s, or any other update.

 

 

Alternately, you could change the declaration of one or more of x, y, z to SafeInt<int>, and then everywhere x is used in the subsequent code is then checked.

 

The idea about the operations is interesting, but I would bet that it would cause the following to blow up and not compile:

 

std::string s = "Hello";

s += " World";

On Thursday, November 22, 2012 5:45:42 AM UTC-8, Fernando Cacciola wrote:

I would most definitely like to have a standardized interface to handle numerical overflow.

I do however have some reservations on doing it by means of an integer wrapper.

First, I think we need such "safe numeric operations" to handle floating point values just as well. While the mechanisms are different, the requirements are exactly the same (and floating-point does overflow no matter how big their range is). In fact, I think we need it for arbitrary numeric types, including rationals, complex, user-defined extended precision, interval, etc... (and consistently defined for even unlimited precision numeric types, even if the overflow test always yields false)

Second, I wonder if a wrapper is the best interface. Since this is a "security" utility, it needs to be consistently applied *all over* the relevant source code, otherwise it is not really effective
A lot, if not most, critical and complex numeric code (where this is mostly needed) depends on third-party libraries, and in the numerical community there is a huge base of reusable code that is (yet) not sufficiently generic to let you get away with simple using a wrapper type at the highest level.
In other words, you might use SafeInt in your own code but it is not easy to have third-party code use it as well.

Since the overflow is always a side effect of operations, and operations are expressed in C++ via operators (and functions), I wonder if the library shouldn't be in a form of "safe operators and functions" as opposed to "safe numeric type".

IIUC, the current operator overloading mechanism should allow something like the following:

#include <safe_numeric_operations>

// This "activates" the overflow detection on any supported type, including builtin types
using std::safe_numeric_operations ;

void test()
{
  try
  {
     int a = std::numeric_limits<int>::max();

     // std::safe_numeric_operations::operator + (int,int) being called here
     int r = a + a ;
  }
  catch ( std::bad_numeric_conversion ) { }
}

On Wed, Nov 21, 2012 at 11:25 PM, <robertmac...@gmail.com> wrote:

On Wednesday, November 7, 2012 6:59:50 PM UTC-8, Ben Craig wrote:

SafeInt information can be found here.  ...

I also found myself interested in this code.  When I got around to looking at it I felt it could be improved.  Being a "booster" I wanted to leverage on Boost stuff to make a simpler implementation.  The result of my efforts can be found at http://rrsd.com/blincubator.com/bi_library/safe-numerics/

Main differences are:
a) follows Boost/C++ library conventions as to naming, formating etc.
b) Is many many lines shorter due to the usage of more meta-programming technique in the implementation.
c) Includes an exhaustive set of tests including all combinations of corner cases - generated with boost pre-processor library.
d) defines concepts for "numeric" types and includes concept checking via the boost concept checking library.
e) includes documentation more in line with currently recommended "formal" style.

Robert Ramey

--
 
 
 

[dvd_l...@yahoo.com]

If you are going to derive something from my work, please follow the license. It doesn't ask much, just that you keep attribution and the license. If you are going to completely rewrite something based on my work, then you may not need a license (I Am Not A Lawyer, one should be asked), but attribution would be nice.

 

Other than that, I don't have time to review an entirely new library. I do believe portions of Boost and/or the standard library could be leveraged to reduce some of the code in SafeInt. I'd assume that if we made it part of the standard that would be a work item.

[dvd_l...@yahoo.com]

Yes - += 2 on this comment -

 

The overhead of this class is quite small, often to the point of being no more overhead than what would happen if you put the correct checks into the code. But it does have overhead, and we don't need it injected into:

 

for (unsigned int j = 0; j < 10; ++j)

 

Don't forget the essential C++ maxim: pay only for what you use.

There is a lot of code that's just fine with non-secure integers. They no need to have overflow checks and such every time time they loop from 0 to 240. They aren't going to overflow their loop counter. There are many such occurrences in a code-base where the structure and nature of the code means that overflow is just not a realistic possibility.

This means that whatever we adopt has to be an opt-in mechanism, not an opt-out.

[dvd_l...@yahoo.com]

The problem is actually a bit worse than one would assume from a quick look. There's a number of wrinkles to the standard, and a couple of difficult corner cases - here's some examples:

 

unsigned int x;

signed char y;

 

Now consider the result of (x & y) - if the high bit is set, then it will sign extend. You may then end up with some of the upper 24 bits of x set, which the programmer may have not expected. Another issue is to consider a shift of more bits than are available - if I'm not mistaken, this is implementation dependent, possibly undefined. There is more than one way to perform modulus of two mixed sign numbers. The class deals with some of this by use of asserts.

 

As an aside, some of the thinking about this parallels what we went through while working on this. At one time, we had an implementation that would have an internal bool to see if it was valid or not, you'd just let it go, then check later to see if it was valid or not - much the same for testing a float to see if it was not a number. Turned out to be unusable, since a simple check like if (SafeCheckedInt<int>(x) < 0) might throw.

A problem with many of these suggestions that SafeInt does deal with is the following:

 

int foo(unsigned short s);

 

SafeInt<int> x = init();

 

foo(x);

 

The casting operator overloading will ensure that x is within range of a short, or throw. This is an extremely common mistake, and this is the only approach I'm aware of that solves it.

 

BTW, thanks to all of you for the extremely interesting ideas and questions - I will likely have several more replies before I am caught up...

On Thursday, November 22, 2012 9:02:42 AM UTC-8, Fernando Cacciola wrote:

OK, I agree with your observations about silently overloading operators.

OTOH, I still think there is something to be considered in the fact that it is the operations that overflow (and other unwanted side effects), not the numbers themselves, so I would propose a layer of overloaded functions, that can be applied on any type, including built-in types, and on top of that a higher-level wrapper (or wrappers like in Robert's library)

The advantage of doing so, following your own observations, is that in most numeric code, you don't really need to check for all operations, so a performance critical algorithm might not be able to just use the wrapper as a drop-in replacement for int, yet it could be made secure by adding checked operations where specifically necessary.

Having said all that, I would like to at least mention the fact that there is a largest picture to consider here, where integer overflow is just one case. I'm referring to the domain of numerical robustness in general, and while a comprehensive work on that is way out of the scope of a relatively simple proposal like this one, the big picture should still be constantly present and considered.

From the more general point of view of numerical robustness, throwing an exception when a numerical computation could not be performed (such as in the case of integer overflow) is the most basic building block, but it is still too low-level. There is a lot of work in the research community about how to truly handle numerical limitations, as opposed to not handling in order (which is what a safe-int does). Unfortunately, most of that work is specific to an application domain and a given numeric type or types, so it's hard to extrapolate general idioms and utilities. However, there are two basic elements that are usually found in most of them:

First there is the general mechanism of using a proper type to perform an operation. For intance, an int64 to operate two int32. This is the mechanism used by SafeInt and Robert's code, but it's actually used in a lot of places dealing with integer numerics. So, we should standardized that, such that it is generally available to any programmer to do something like:

auto r = (secure)a + b;

here (secure) would bootstrap an operator+ which selects the proper return type to guarantee the addition does not overflow (or you could just have secure_add(a,b) or whatever)

Second, there is the general requirement to test whether the result of operations are reliable, beyond just overflow.
One idiom that has emerged in recent years and which I found intuitive enough to be general is the concept of "certified arithmetic" (usually implemented with interval floating-point numbers). The idea is that, on the one hand, the result of operations carry a certificate (explicit or not) to indicate if it succeeded or not, and on the other hand, triboolean logic is used along, made general and easy.  In terms of safe_int this would mean that instead of throwing, the result is just flaged as overflow, much like a floating-point saturates to +- INF, but, when you try to compare, the answer is "maybe" (and if you want to convert it to plain int it throws)

The general form of the idiom would be something like this:

auto e = ( a  + b == c + d ) ;
if ( certainy(e) )
{
}
else if ( certainly_not(e ) )
{
}
else
{
  // can't tell. It not possible to compare the numbers
}

Here, if a,b,c,d are integers numbers, and either of the additions overflow, the code flows to the last else, and without even any exception being thrown.
The trick is that operator == returns a tribool (or it's generalization uncertain<bool>)


Best

On Thu, Nov 22, 2012 at 1:58 PM, Nicol Bolas <jmck...@gmail.com> wrote:

On Thursday, November 22, 2012 5:45:42 AM UTC-8, Fernando Cacciola wrote:

I would most definitely like to have a standardized interface to handle numerical overflow.

I do however have some reservations on doing it by means of an integer wrapper.

First, I think we need such "safe numeric operations" to handle floating point values just as well. While the mechanisms are different, the requirements are exactly the same (and floating-point does overflow no matter how big their range is). In fact, I think we need it for arbitrary numeric types, including rationals, complex, user-defined extended precision, interval, etc... (and consistently defined for even unlimited precision numeric types, even if the overflow test always yields false)

Second, I wonder if a wrapper is the best interface. Since this is a "security" utility, it needs to be consistently applied *all over* the relevant source code, otherwise it is not really effective

Don't forget the essential C++ maxim: pay only for what you use.

There is a lot of code that's just fine with non-secure integers. They no need to have overflow checks and such every time time they loop from 0 to 240. They aren't going to overflow their loop counter. There are many such occurrences in a code-base where the structure and nature of the code means that overflow is just not a realistic possibility.

This means that whatever we adopt has to be an opt-in mechanism, not an opt-out.
 

A lot, if not most, critical and complex numeric code (where this is mostly needed) depends on third-party libraries, and in the numerical community there is a huge base of reusable code that is (yet) not sufficiently generic to let you get away with simple using a wrapper type at the highest level.

In other words, you might use SafeInt in your own code but it is not easy to have third-party code use it as well.

Since the overflow is always a side effect of operations, and operations are expressed in C++ via operators (and functions), I wonder if the library shouldn't be in a form of "safe operators and functions" as opposed to "safe numeric type". 

IIUC, the current operator overloading mechanism should allow something like the following:

#include <safe_numeric_operations>

// This "activates" the overflow detection on any supported type, including builtin types
using std::safe_numeric_operations ;

void test()
{
  try
  {
     int a = std::numeric_limits<int>::max();

     // std::safe_numeric_operations::operator + (int,int) being called here
     int r = a + a ;
  }
  catch ( std::bad_numeric_conversion ) { }
}

Ignoring the fact that a recompile would suddenly cause massive amounts of code to potentially throw std::bad_numeric_conversion without the knowledge of that code's owners (ie: we can't do that), there's also the practical issue that this won't magically affect any C code that people often use.

But even more importantly, I'm pretty sure you can't overload operator+(int, int). Besides being practically infeasible by creating the possibility of exceptions in potentially exception-unsafe code, it's simply not possible.
 

On Wed, Nov 21, 2012 at 11:25 PM, <robertmac...@gmail.com> wrote:

On Wednesday, November 7, 2012 6:59:50 PM UTC-8, Ben Craig wrote:

SafeInt information can be found here.  ...

I also found myself interested in this code.  When I got around to looking at it I felt it could be improved.  Being a "booster" I wanted to leverage on Boost stuff to make a simpler implementation.  The result of my efforts can be found at http://rrsd.com/blincubator.com/bi_library/safe-numerics/

Main differences are:
a) follows Boost/C++ library conventions as to naming, formating etc.
b) Is many many lines shorter due to the usage of more meta-programming technique in the implementation.
c) Includes an exhaustive set of tests including all combinations of corner cases - generated with boost pre-processor library.
d) defines concepts for "numeric" types and includes concept checking via the boost concept checking library.
e) includes documentation more in line with currently recommended "formal" style.

Robert Ramey

--
 
 
 

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com

--
 
 
 

[dvd_l...@yahoo.com]

On Thursday, November 22, 2012 1:33:38 PM UTC-8, Fernando Cacciola wrote:

On Thu, Nov 22, 2012 at 5:57 PM, <robertmac...@gmail.com> wrote:

For instance, both SafeInt's and your code *requires* a primitive operation that returns the result in a larger type such that it is known not to overflow.

No, not true - for type A, B, operator op:

 

SafeInt<A> op B returns a SafeInt<A>

 

So it is still the same size. Which has a difficulty associated with it, namely:

 

unsigned short a = 2;

unsigned short b = 3;

int c = -3;

 

(a + b + c) using standard behavior emits an int with a value of 2 as will:

(a + (b + SafeInt<int>(c)))

 

But:

(a + (SafeInt<unsigned short>(b) + c))

 

Will throw. But this is actually an unusual case, so in practice you will not see it much, and you can just document the behavior. I have explored just increasing the size of the type, but it got to be a very horrible problem and threatened to destroy perf.

 

 

Then I'm saying that, since the bottom layer is a requirement for these libraries, and it's also useful--and used--in several other numerical techniques, it should be standardized as such (and not hidden as an implementation detail as it proposed)

 

To some extent, I agree. Though there is support for this in SafeInt - there are templatized functions that will answer the general question of whether an addition (for example) between two arbitrary types is going to have a numerically valid result.

 

I'm also saying that the bigger picture could critically affect design decision even within the scope proposed. I gave the example of certified arithmetic because that would suggest that a given safe_int should not necessarily just throw right up front, but it could instead flag the overflow and throw only when necessary, such as when casting to int. This is important because if you are going to compare the overflowed result, you can just return "maybe" from the comparison without throwing an exception. This not only allows the client code to be *elegantly* explicit about the way overflowed results affect the computation results, but it also allows the library to be used in contexts where exceptions are to be avoided when possible.

 

We tried this, and it did not go well. Great idea, and we even implemented it and put it into a fair bit of code, but we've since abandoned the approach and removed uses of it. The best solution we've found so far is the templatized, non-throwing functions. 

[dvd_l...@yahoo.com]

 

I haven't checked your code in this corner case, but SafeInt uses a form of 128 bits type (when configured as such)

 

No, it does not support 128-bit integers. Once there is a compiler that will give you those, then it could be extended. But the template programming accounts for all 64 possible combination of signed and size that we currently have. If you introduce a fifth, then we have a 100 node table, and some of the current edge cases get easier, to be replaced by edge cases because now we don't have a 256 bit type.

 

So what's the signature of operator+ ( safe<int64>, safe<int64> ) ?

 

SafeInt<int64> operator+( SafeInt<int64>, SafeInt<64>)

 

I still prefer something more general that would allow me to do:

int16 a,b ;
int32 x = safe_add(a,b);

and entirely bypass the wrapper though, specially as a std utility (which is what we are discussing here)

 

Yes, that's included in the class, because there are times you want to test things and not have to deal with exceptions at all. Though it has to be done (in general) as:

 

int16 tmp;

if(SafeAdd(a, b, tmp) && SafeCast(tmp, x))

 

Because you have two operations that can possibly make trouble, though in this case, the second will compile away, because it is always safe.

 

  

safe<int16> a;
safe<int32> b;

auto x = a + b;  // what is the type of x?

should be safe<int64>

 

No, it is defined, and depends on operator precedence. This would invoke:

SafeInt<int16>::operator+(SafeInt<int32>)

which returns a SafeInt<int16>

 

If you wanted a SafeInt<int64> out of it, then you would write:

 

auto x = SafeInt<int64>(a) + b;

 

Else, we quickly get to all operations working on the largest possible type, and perf would suffer badly.

 

 

auto x = b + a;  // is the type of y the same as the type of x?

yes

Actually, no.

 

 

Questions like these made me decide to divide the task as you suggested
a) do the calculation resulting in a type which can hold the true result
b) on assignment or cast (safe_cast ...) trap the attempt to save a value which loses information.

So we are almost on the same page.

We differ in how to propose two two layers to the std

 

That approach will end up being infeasible due to perf issues.

 

[dvd_l...@yahoo.com]

Yes, strong agreement.

On Sunday, November 25, 2012 10:31:18 AM UTC-8, Marc Thibault wrote:

I also believe that safe-numerics is very good. I think the problem of integers that grows at runtime has to be done in a different library. Also, there is the independent problem of creating efficient accumulators.

[Fernando Cacciola]

On Tue, Nov 27, 2012 at 10:37 PM, <dvd_l...@yahoo.com> wrote:

On Thursday, November 22, 2012 1:33:38 PM UTC-8, Fernando Cacciola wrote:

On Thu, Nov 22, 2012 at 5:57 PM, <robertmac...@gmail.com> wrote:

For instance, both SafeInt's and your code *requires* a primitive operation that returns the result in a larger type such that it is known not to overflow.

No, not true - for type A, B, operator op:

 

SafeInt<A> op B returns a SafeInt<A>

 

I was referring to the implementation.
In the code (I did actually look), you do perform "the primitive operation in a type that has twice the precision" of the operands.

 

So it is still the same size. Which has a difficulty associated with it, namely:

 

unsigned short a = 2;

unsigned short b = 3;

int c = -3;

 

(a + b + c) using standard behavior emits an int with a value of 2 as will:

(a + (b + SafeInt<int>(c)))

 

But:

(a + (SafeInt<unsigned short>(b) + c))

 

Will throw. But this is actually an unusual case, so in practice you will not see it much, and you can just document the behavior. I have explored just increasing the size of the type, but it got to be a very horrible problem and threatened to destroy perf.

 

 

Then I'm saying that, since the bottom layer is a requirement for these libraries, and it's also useful--and used--in several other numerical techniques, it should be standardized as such (and not hidden as an implementation detail as it proposed)

 

To some extent, I agree. Though there is support for this in SafeInt - there are templatized functions that will answer the general question of whether an addition (for example) between two arbitrary types is going to have a numerically valid result.

I know. I saw them in the code.
And I'm saying that such functions (or whatever, it doesn't really matter what it is exactly, to the effect of my point) are a bottom layer of SafeInt but they would be equally useful as a bottom layer for several other integer related utility classes.
Then, I propose to standarize *them* as well.
 

 

I'm also saying that the bigger picture could critically affect design decision even within the scope proposed. I gave the example of certified arithmetic because that would suggest that a given safe_int should not necessarily just throw right up front, but it could instead flag the overflow and throw only when necessary, such as when casting to int. This is important because if you are going to compare the overflowed result, you can just return "maybe" from the comparison without throwing an exception. This not only allows the client code to be *elegantly* explicit about the way overflowed results affect the computation results, but it also allows the library to be used in contexts where exceptions are to be avoided when possible.

 

We tried this, and it did not go well. Great idea, and we even implemented it and put it into a fair bit of code, but we've since abandoned the approach and removed uses of it. The best solution we've found so far is the templatized, non-throwing functions. 

Fair enough.
OTOH, I believe it is reasonable to ask for a rationale on why it did not work, and to allow us to have some discussion about it, which would not ignore your experience but simply try to consider different contexts which might have not been taken into account when you first consider it.

For example, you said "Turned out to be unusable, since a simple check like if (SafeCheckedInt<int>(x) < 0) might throw"

Why would that throw? I don't get it

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 5:33:03 AM UTC-8, Fernando Cacciola wrote:

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

Hmmm.
Can you elaborate how is SafeInt safe when it comes to an array index in the case of an array of runtime size? Which I believe is, by far, the most common type of array (buffer, container, etc)

 

We can ensure that the array index is not the result of a wrapping operation. If you want to ensure that the index is within the bounds of the array, then I would construct the array from std::vector, and then rely on either at() or [] to know what is a suitable range. Works better if someone comes along and resizes the array while your other variable is not updated.

 

For *that* purpose I think the proper tool is an integer with runtime boundaries (a number of these have been implemented and proposed to, for instance, Boost)

Disagree - then you have to keep the boundaries in sync with the buffer size, which could grow or shrink, and the code may not think to notify the bounds. Especially given that the most efficient way to implement the bounds would be at compile time, and then you are stuck.

 
 

  In these situations, you probably want to throw an exception, or terminate the program. 

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

 

Also disagree. You may be in a state where you cannot cleanly unwind. Clearly, if you have ideal C++ code, then you can, but I have not seen much ideal code in the wild. You may want to just consider it the same sort of problem as a bad pointer dereference where you just take the app down. This is why the exception policy for SafeInt is user-defined, and you could have your own custom exceptions, standard exceptions, fail fast to exit, or OS-specific error handlers.

 

 

[Fernando Cacciola]

On Tue, Nov 27, 2012 at 11:05 PM, <dvd_l...@yahoo.com> wrote:

 

I haven't checked your code in this corner case, but SafeInt uses a form of 128 bits type (when configured as such)

 

No, it does not support 128-bit integers.

Not on the interface.
But the code uses _imul128 (or some such) for a certain operation over certain argument and given certain configuration options.

So the implementation is using an operation on 128 integers.

 

Once there is a compiler that will give you those, then it could be extended. But the template programming accounts for all 64 possible combination of signed and size that we currently have. If you introduce a fifth, then we have a 100 node table, and some of the current edge cases get easier, to be replaced by edge cases because now we don't have a 256 bit type.

 

So what's the signature of operator+ ( safe<int64>, safe<int64> ) ?

 

SafeInt<int64> operator+( SafeInt<int64>, SafeInt<64>)

 

That's in you library, I know.
But that question was addressed to Robert. His library *sifnificantly* differs from yours in this regard:


In Robert's library, safe<T> * safe<T> -> safe<2T>

And I believe *that* is the correct choice (SafeInt<> does the opposite so I believe that's not the correct choice)

Given that pattern, I ask what's the case when you already reached int64.

I still prefer something more general that would allow me to do:

int16 a,b ;
int32 x = safe_add(a,b);

and entirely bypass the wrapper though, specially as a std utility (which is what we are discussing here)

 

Yes, that's included in the class, because there are times you want to test things and not have to deal with exceptions at all. Though it has to be done (in general) as:

 

int16 tmp;

if(SafeAdd(a, b, tmp) && SafeCast(tmp, x))

 

I know.
And I would use a totally different *interface* but that's minor. What matters IMO is the existence of these utilities, which I believe should not be left hidden in the implementation.

 

Because you have two operations that can possibly make trouble, though in this case, the second will compile away, because it is always safe.

 

  

safe<int16> a;
safe<int32> b;

auto x = a + b;  // what is the type of x?

should be safe<int64>

 

No, it is defined, and depends on operator precedence. This would invoke:

SafeInt<int16>::operator+(SafeInt<int32>)

which returns a SafeInt<int16>

 

In your library, yes.

In Robert's, it does not need to return a safe-int of the same type. Hence, it *shoukld* return a safe of the next bigger type, int64 in this case.
 

If you wanted a SafeInt<int64> out of it, then you would write:

 

auto x = SafeInt<int64>(a) + b;

 

Else, we quickly get to all operations working on the largest possible type, and perf would suffer badly.

 

OK.
Then that would be your argument for NOT automatically promoting to the next bigger type to avoid overflow.

Right off the top of my head I disagree with your conclusion (I agree with the perf observation but not the conclusion you drew from that), but this is one thing that should be discussed as its own topic.

 

 

auto x = b + a;  // is the type of y the same as the type of x?

yes

Actually, no.

 

Maybe one of us is misreading the question.

I read the question as: Should ( a + b ) and ( b + a) return the same type?

I say yes.

 

 

Questions like these made me decide to divide the task as you suggested
a) do the calculation resulting in a type which can hold the true result
b) on assignment or cast (safe_cast ...) trap the attempt to save a value which loses information.

So we are almost on the same page.

We differ in how to propose two two layers to the std

 

That approach will end up being infeasible due to perf issues.

 

I would need you to elaborate on that.

 

[Fernando Cacciola]

On Tue, Nov 27, 2012 at 11:25 PM, <dvd_l...@yahoo.com> wrote:

On Tuesday, November 27, 2012 5:33:03 AM UTC-8, Fernando Cacciola wrote:

On Mon, Nov 26, 2012 at 1:59 PM, Ben Craig <ben....@gmail.com> wrote:

Some large use cases for SafeInt are computing sizes for buffers and array indices.

Hmmm.
Can you elaborate how is SafeInt safe when it comes to an array index in the case of an array of runtime size? Which I believe is, by far, the most common type of array (buffer, container, etc)

 

We can ensure that the array index is not the result of a wrapping operation. If you want to ensure that the index is within the bounds of the array, then I would construct the array from std::vector, and then rely on either at() or [] to know what is a suitable range. Works better if someone comes along and resizes the array while your other variable is not updated.

 

Right, I totally misunderstood the index example.
That was clarified and I then agreed that a safe-int is very useful for that.

For *that* purpose I think the proper tool is an integer with runtime boundaries (a number of these have been implemented and proposed to, for instance, Boost)

Disagree - then you have to keep the boundaries in sync with the buffer size, which could grow or shrink, and the code may not think to notify the bounds. Especially given that the most efficient way to implement the bounds would be at compile time, and then you are stuck.

 

I agree with your disagreement. I propose that to a problem I thought you where solving based on my (mis)interpretation of the example. But of course I don't think you should do that (just that if you do that, do it with the right type of wrapper)

 

 

  In these situations, you probably want to throw an exception, or terminate the program. 

This s off-topic but IMO you never ever want to terminate a program when you use a language that supports exceptions, like C++

 

Also disagree. You may be in a state where you cannot cleanly unwind. Clearly, if you have ideal C++ code, then you can, but I have not seen much ideal code in the wild. You may want to just consider it the same sort of problem as a bad pointer dereference where you just take the app down.

FWIW I don't take the app down in the presence of a bad-pointer.
Neither do the most popular application frameworks, like .Net for instance.

 

This is why the exception policy for SafeInt is user-defined, and you could have your own custom exceptions, standard exceptions, fail fast to exit, or OS-specific error handlers.

 

Then you actually agree. In my sentence, "you" is the library implementation. A policy is in the hand of the application (assuming a well engineered one),  and of course "it" can terminate  the program or do whatever. It is the *library* which cannot do that.

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 5:44:44 AM UTC-8, Fernando Cacciola wrote:

 

Hmm, how isn't is as simple as using a software-based int128 number type?
 

 

Depends on the operation, and I was not aware of a software-based 128-bit type at the time. You might not need it - for example, unsigned addition is well defined, and we can check the result more cheaply. Where this would come in handy is 64-bit multiplication, which is a sticky problem.

>> Now suppose you change all the 'int' for safe<int> and you discover a point where overflow is occurring?  What do you do?

By analogy to the div-by-zero case, and IME (and I do have experience writing algorithms that need handle overflow, both integer and floating-point), you also want to detect the case before-hand so you can do something else.

 

You can still do this.

>> Wait.
Numerical overflow is *rarely* a programming error. It's the consequence of finite precision when crunching numbers.

 

OK, so a light just came on - you are thinking of this in terms of numerical analysis, which has very different needs than ordinary production software where we're only calculating offsets and the argument to malloc for the most part. I would in general not suggest using SafeInt for that sort of application. It would probably ruin your perf. It might be a great tool for debugging to see just why you're coming up with odd results.

 

When we're dealing with the types of patterns seen from within general use software, numerical overflow is almost always unintended, and often results in disaster. Here's an example of how you can get real mayhem (and no true overflow involved)

 

char* p1 = Init1();

char* p2 = Init2();

unsigned int max = some_const;

 

if (p2 - p1 < max)

  DoThis();

else

  DoThat();

 

Now consider the case of p1 > p2, yielding a negative result. The type of (p2 -p1) is ptrdiff_t. When we compile this on a 32-bit system, the ptrdiff_t will cast to unsigned long, and we will call DoThat(). If we have a 64-bit system, and int is 32-bit, then max is cast to ptrdiff_t, and we will call DoThis(), which is almost certainly not intended.

 

It may be the consequence of finite precision, but it leads to a lot of security exploits.

 

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 9:43:28 AM UTC-8, Fernando Cacciola wrote:

I'm tempted to respond, but I think this thread is not the correct place. (and I'm not sure where would be)

Anyway, let me just rephrase that: IMO, the *end user* never ever wants you the programmer to structure the program in such a way that the *entire application* must abort as opposed to the current "task" (task from the end user POV )

Somewhat off-topic, and very much platform-centric, but actually we do want that under a number of conditions. On Windows, if the app aborts unexpectedly, and you have opted in to the crash reporting feature, we then get a bug with a stack trace and possibly a dump. If we see many of them, we'll fix it. If you just catch the exception, then maybe we find out, maybe we don't, and the bug is more likely to stay there. Also some applications, Excel being one example, feel like the worst thing we can ever do is to corrupt the user's data. Crashing is bad, but not the worst thing we can possibly do. So if Excel gets off in the weeds, it would rather fall over than corrupt your data.

 

I did once have the X Window library do that to me (call exit()), and it was seriously annoying. So what you want is for the developer to decide what happens, which is what SafeInt does. 

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 6:19:32 PM UTC-8, Fernando Cacciola wrote:

I was referring to the implementation.
In the code (I did actually look), you do perform "the primitive operation in a type that has twice the precision" of the operands.

Oh - OK. This is not always true, though. Addition can be checked without larger types, and sometimes I just leverage normal operator casting behavior - char op char does not go to short, but instead int. For multiplication, this is the case for 32-bit types. 

 

 

To some extent, I agree. Though there is support for this in SafeInt - there are templatized functions that will answer the general question of whether an addition (for example) between two arbitrary types is going to have a numerically valid result.

I know. I saw them in the code.
And I'm saying that such functions (or whatever, it doesn't really matter what it is exactly, to the effect of my point) are a bottom layer of SafeInt but they would be equally useful as a bottom layer for several other integer related utility classes.
Then, I propose to standarize *them* as well.

Thanks, then yes, we agree on that. However, you would need both throwing and non-throwing semantics, as you see in the code. The throwing semantics can sometimes have a cleaner failure path.

 

 

We tried this, and it did not go well. Great idea, and we even implemented it and put it into a fair bit of code, but we've since abandoned the approach and removed uses of it. The best solution we've found so far is the templatized, non-throwing functions. 

Fair enough.
OTOH, I believe it is reasonable to ask for a rationale on why it did not work, and to allow us to have some discussion about it, which would not ignore your experience but simply try to consider different contexts which might have not been taken into account when you first consider it.

For example, you said "Turned out to be unusable, since a simple check like if (SafeCheckedInt<int>(x) < 0) might throw"
 

Why would that throw? I don't get it

 

If the checked int had overflowed, then we cannot answer the question of whether it is < 0, because it is undefined. Only thing we can do is throw at that point. This tends to cause serious problems when trying to use it in existing code.

 

I'm certainly willing to discuss the idea - one possibility is that our implementation or design was bad. Some other approach might work. We originally liked the idea because a float can tell us if it has become an undefined value, seemed like this concept should transfer. Part of it was confusion because a SafeInt can never become invalid, and a comparison operation can never throw. So introducing something that acts somewhat the same, but throws in places the other cannot was a mess.

 

 

[Fernando Cacciola]

On Tue, Nov 27, 2012 at 11:50 PM, <dvd_l...@yahoo.com> wrote:

On Tuesday, November 27, 2012 9:43:28 AM UTC-8, Fernando Cacciola wrote:

I'm tempted to respond, but I think this thread is not the correct place. (and I'm not sure where would be)

Anyway, let me just rephrase that: IMO, the *end user* never ever wants you the programmer to structure the program in such a way that the *entire application* must abort as opposed to the current "task" (task from the end user POV )

Somewhat off-topic, and very much platform-centric, but actually we do want that under a number of conditions. On Windows, if the app aborts unexpectedly, and you have opted in to the crash reporting feature, we then get a bug with a stack trace and possibly a dump. If we see many of them, we'll fix it. If you just catch the exception, then maybe we find out, maybe we don't, and the bug is more likely to stay there. Also some applications, Excel being one example, feel like the worst thing we can ever do is to corrupt the user's data. Crashing is bad, but not the worst thing we can possibly do. So if Excel gets off in the weeds, it would rather fall over than corrupt your data.

 

And this is quite reasonable error behavior. So is the opposite, like I've implemented on several applications, which is to abort the executing task (*NO* need for a separate thread or process like it has been said in some of the related posts), give the user some information and let him continue using the application.
There isn't one correct *application* behavior because it depends on the application.
Just to consider some opposing examples, Excel is basically about data management so there is a big chance that an application bug would corrupt the data. Maple OTOH, although similarly about "numbers", is about algebraic computations, so is a lot more likely that a bug would simply produce the wrong result. A Maple user would very much like to keep Maple going so he can just workaround the bug by twiking the computations.

I did once have the X Window library do that to me (call exit()), and it was seriously annoying. So what you want is for the developer to decide what happens, which is what SafeInt does. 

Exactly. It is the application (and not just any part of it) who must decide how to respond to errors (even programming errors). Never the library.
 

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 6:32:27 PM UTC-8, Fernando Cacciola wrote:

Not on the interface.
But the code uses _imul128 (or some such) for a certain operation over certain argument and given certain configuration options.

So the implementation is using an operation on 128 integers.

 

That's a Microsoft-specific intrinsic (AFAIK). If it turns out to be portable, I'd use it for other compilers, too. FWIW, it is not available on 32-bit Microsoft compilers.

 

But that question was addressed to Robert. His library *sifnificantly* differs from yours in this regard:


In Robert's library, safe<T> * safe<T> -> safe<2T>

And I believe *that* is the correct choice (SafeInt<> does the opposite so I believe that's not the correct choice)

Given that pattern, I ask what's the case when you already reached int64.

 

Ah - from the standpoint of keeping things from overflowing, I would tend to agree. From the standpoint of being able to use it in production code because I have not caused a perf problem, I disagree.

 

I would note that there could be a middle ground, though it may be tricky to get to compile. You could say that for SafeInt of types smaller than int, then the return would be SafeInt<int>

 

 >> And I would use a totally different *interface* but that's minor. What matters IMO is the existence of these utilities, which I believe should not be left hidden in the implementation.

 

Sure, complete agreement, and there are aspects of the existing interface I am not completely happy with.

 

 

Else, we quickly get to all operations working on the largest possible type, and perf would suffer badly.

 

OK.
Then that would be your argument for NOT automatically promoting to the next bigger type to avoid overflow.

Right off the top of my head I disagree with your conclusion (I agree with the perf observation but not the conclusion you drew from that), but this is one thing that should be discussed as its own topic.

OK.

 

 

Maybe one of us is misreading the question.

I read the question as: Should ( a + b ) and ( b + a) return the same type?

I say yes.

This gets into some level of implementation detail in terms of simplifying assumptions. The class was significantly hard to develop, and evolved over some years. The bulk of it was done in about 6 months. A simplifying assumption is that some_int op SafeInt<other_int> always returns the SafeInt<other_int>. This is true no matter what the order - we can do a + safe_b or safe_b + a. All works and meets your requirement.

 

What is undefined is the case of SafeInt<T> op SafeInt<U>. I don't know what type you want back, and compilers tend to just throw up their hands and refuse to compile. You could have a large table of all the types, but that's ugly. So I then ask you to make up your mind and do for example (U)SafeInt<T> op SafeInt<U>.

  

That approach will end up being infeasible due to perf issues.

 

I would need you to elaborate on that.

The worst thing you can ever ask this library to do is check 64-bit multiplication. If you have the intrinsics, it is not too bad, but it is still going to be expensive. I believe division gets significantly more expensive as the types get larger, especially 64-bit division on a 32-bit system. 64-bit addition is not quite as bad, and I don't have to do tricky things in the code, but it will use more registers, and on 32-bit Intel systems, we do not have many of those. As soon as you start using more registers, you're going to cause some side-effects in terms of optimizations.

 

So if you upcast a bunch of say 16-bit operations to 32-bit on a 32-bit system, then that's not going to hurt you in general. But if you then have two of those 32-bit values collide and want to go to 64-bit, now we have problems. If you start looking through the code that really does the work, the specializations for the smaller types tend to be very small and clean. The specializations that deal with mixed-sign operations on 64-bit types tend to be much more complex.

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 10:05:27 AM UTC-8, viboes wrote:

I don't know if your SafeInt/safe<T> prevents from assignments from
signed values to unsigned types, but this could also be useful.

No, it does not prevent it, but it does check that the assignment is within range. It does the same thing on a cast, which can result in some interesting bugs, for example:

 

SafeInt<unsigned int> x;

 

// code happens

 

if ((int)x < 0)

  complain();

 

Never calls complain, it just throws. 

[robertmac...@gmail.com]

On Tuesday, November 27, 2012 5:02:37 PM UTC-8, dvd_l...@yahoo.com wrote:

If you are going to derive something from my work, please follow the license. It doesn't ask much, just that you keep attribution and the license. If you are going to completely rewrite something based on my work, then you may not need a license (I Am Not A Lawyer, one should be asked), but attribution would be nice.

I'm sure that a simple inspection of my code will convince anyone that it's not a derivation.  The documentation has an Acknowledgements page in which you and your work are prominently mentioned. I was really looking for something like safe_range<min, max>.  I new about your library and had used it before to good effect. When I looked into your code I found it hard to follow and felt that a TMP approach would result in a more regular and smaller code base.  Also I had trouble actually finding the package and when I did, I couldn't find the documentation or tests. I knew tests were around since I had remembered seeing them.  Also it seemed there were a couple of versions - some portable to gcc and others only for vc.  I also felt the notion of "safe" type could be generalized to all types supported by std::limits.  For all these reasons I felt it need a fresh cut.  There is not question I was inspired by your library - and I still am.  One could well consider safe<T> a successor to SafeInt but I don't think derivation is a fair characterization.  The code is available for inspection by anyone who is actually interested in this point.

Robert Ramey
 

[robertmac...@gmail.com]

On Tuesday, November 27, 2012 7:22:20 PM UTC-8, dvd_l...@yahoo.com wrote:

On Tuesday, November 27, 2012 6:32:27 PM UTC-8, Fernando Cacciola wrote:

 

But that question was addressed to Robert. His library *sifnificantly* differs from yours in this regard:


In Robert's library, safe<T> * safe<T> -> safe<2T>

And I believe *that* is the correct choice (SafeInt<> does the opposite so I believe that's not the correct choice)

Given that pattern, I ask what's the case when you already reached int64.

 

Ah - from the standpoint of keeping things from overflowing, I would tend to agree. From the standpoint of being able to use it in production code because I have not caused a perf problem, I disagree.

I'm not convinced that promoting the types to 64 bits is more expensive timewise than the alternatives. I'd have to see some real data on that.

 

I would note that there could be a middle ground, though it may be tricky to get to compile. You could say that for SafeInt of types smaller than int, then the return would be SafeInt<int>

This is very interesting.  When I started on this, I started with "save_range<min, max>" from which safe<int> is derived.  This left open the possibility of using safe_range<0, 4> * safe_range<0,8>  to return a safe_range<0, 12> which was very cool to me.  But the TMP got just to complex and I scaled back my so that safe_range<0,4> is implemented as a safe<unsigned char> etc.

What is undefined is the case of SafeInt<T> op SafeInt<U>. I don't know what type you want back, and compilers tend to just throw up their hands and refuse to compile. You could have a large table of all the types, but that's ugly. So I then ask you to make up your mind and do for example (U)SafeInt<T> op SafeInt<U>.

FWIW safe<int32> * safe<int16> will return safe<int64.  safe<int8> + safe<int16> will return safe<int32> ...


Robert Ramey

[Fernando Cacciola]

On Wed, Nov 28, 2012 at 12:22 AM, <dvd_l...@yahoo.com> wrote:

On Tuesday, November 27, 2012 6:32:27 PM UTC-8, Fernando Cacciola wrote:

Not on the interface.
But the code uses _imul128 (or some such) for a certain operation over certain argument and given certain configuration options.

So the implementation is using an operation on 128 integers.

 

That's a Microsoft-specific intrinsic (AFAIK). If it turns out to be portable, I'd use it for other compilers, too. FWIW, it is not available on 32-bit Microsoft compilers.

 

But that question was addressed to Robert. His library *sifnificantly* differs from yours in this regard:


In Robert's library, safe<T> * safe<T> -> safe<2T>

And I believe *that* is the correct choice (SafeInt<> does the opposite so I believe that's not the correct choice)

Given that pattern, I ask what's the case when you already reached int64.

 

Ah - from the standpoint of keeping things from overflowing, I would tend to agree. From the standpoint of being able to use it in production code because I have not caused a perf problem, I disagree.

 

I would note that there could be a middle ground, though it may be tricky to get to compile. You could say that for SafeInt of types smaller than int, then the return would be SafeInt<int>

 

OK.

I agree that there are two separate goals. One is to avoid overflow by promoting to the next integer This would reach bigint in the end. The other is to turn overflow into well defined and *useful* behavior, but without any need to avoid it, just to deal with it.

From your use cases I can see that SafeInt is aimed at the later. The uses I have in mind are closer to the former.

So, IMO a proposal should contemplate both, and possibly, provide utilities to both problems.
 

 >> And I would use a totally different *interface* but that's minor. What matters IMO is the existence of these utilities, which I believe should not be left hidden in the implementation.

 

Sure, complete agreement, and there are aspects of the existing interface I am not completely happy with.

 

 

Else, we quickly get to all operations working on the largest possible type, and perf would suffer badly.

 

OK.
Then that would be your argument for NOT automatically promoting to the next bigger type to avoid overflow.

Right off the top of my head I disagree with your conclusion (I agree with the perf observation but not the conclusion you drew from that), but this is one thing that should be discussed as its own topic.

OK.

 

 

Maybe one of us is misreading the question.

I read the question as: Should ( a + b ) and ( b + a) return the same type?

I say yes.

This gets into some level of implementation detail in terms of simplifying assumptions. The class was significantly hard to develop, and evolved over some years. The bulk of it was done in about 6 months. A simplifying assumption is that some_int op SafeInt<other_int> always returns the SafeInt<other_int>. This is true no matter what the order - we can do a + safe_b or safe_b + a. All works and meets your requirement.

 

What is undefined is the case of SafeInt<T> op SafeInt<U>. I don't know what type you want back, and compilers tend to just throw up their hands and refuse to compile. You could have a large table of all the types, but that's ugly. So I then ask you to make up your mind and do for example (U)SafeInt<T> op SafeInt<U>.

  

Integer types are ranked based on their ranges. That's used in integer promotion. IMO, it's perfectly valid and I would say simple to define similar promotion rules for SafeInt<T> op SafeInt<U> based on the operation.

[Fernando Cacciola]

On Wed, Nov 28, 2012 at 4:37 AM, <robertmac...@gmail.com> wrote:

This is very interesting.  When I started on this, I started with "save_range<min, max>" from which safe<int> is derived.  This left open the possibility of using safe_range<0, 4> * safe_range<0,8>  to return a safe_range<0, 12> which was very cool to me.  But the TMP got just to complex and I scaled back my so that safe_range<0,4> is implemented as a safe<unsigned char> etc.

OTOH, in our context: a std proposal, we can just leave that to the implementations (knowing that it could be complex, but *can* be done). There are far more difficult things in the new language definition, so much that haven't even been implemented yet.

[Fernando Cacciola]

On Wed, Nov 28, 2012 at 12:01 AM, <dvd_l...@yahoo.com> wrote:

On Tuesday, November 27, 2012 6:19:32 PM UTC-8, Fernando Cacciola wrote:

I was referring to the implementation.
In the code (I did actually look), you do perform "the primitive operation in a type that has twice the precision" of the operands.

Oh - OK. This is not always true, though. Addition can be checked without larger types, and sometimes I just leverage normal operator casting behavior - char op char does not go to short, but instead int. For multiplication, this is the case for 32-bit types. 

 

 

To some extent, I agree. Though there is support for this in SafeInt - there are templatized functions that will answer the general question of whether an addition (for example) between two arbitrary types is going to have a numerically valid result.

I know. I saw them in the code.
And I'm saying that such functions (or whatever, it doesn't really matter what it is exactly, to the effect of my point) are a bottom layer of SafeInt but they would be equally useful as a bottom layer for several other integer related utility classes.
Then, I propose to standarize *them* as well.

Thanks, then yes, we agree on that. However, you would need both throwing and non-throwing semantics, as you see in the code. The throwing semantics can sometimes have a cleaner failure path.

IIUC, this is because you have failure policies.
If, OTOH, the library just consistently throw as the sole overflow handling mechanism, you won't need both.

I would (and probably will) argue that, a *standard library utility* should just consistently throw. Or else, something at a wider lever, across libraries, should be proposed.
 

 

 

We tried this, and it did not go well. Great idea, and we even implemented it and put it into a fair bit of code, but we've since abandoned the approach and removed uses of it. The best solution we've found so far is the templatized, non-throwing functions. 

Fair enough.
OTOH, I believe it is reasonable to ask for a rationale on why it did not work, and to allow us to have some discussion about it, which would not ignore your experience but simply try to consider different contexts which might have not been taken into account when you first consider it.

For example, you said "Turned out to be unusable, since a simple check like if (SafeCheckedInt<int>(x) < 0) might throw"
 

Why would that throw? I don't get it

 

If the checked int had overflowed

OK, so you actually meant to write:

SafeCheckedInt<int> x ;
...
if ( x < 0 )

because in your example, the checked int is a temporary constructed in the expression so I know it hadn't overflowed.

 

, then we cannot answer the question of whether it is < 0, because it is undefined.

Right, we can't.

 

Only thing we can do is throw at that point.

Correct
 

This tends to cause serious problems when trying to use it in existing code.

 

How so?

The very purpose of this utility is to make sure the user never ever deals with "an apparent" value that is not really so because it's actually undefined.
That should cover all cases where the value is being accessed, which would include comparisons, not just assignment and conversions.

UNLESS, it is decided by design that you *can* compare overflowed (that is undefined) values.  This is valid design, and there are conceptually similar libraries that follow it.
This, however, can *only* be implemented if the overflowed state is stored inside SafeInt (as opposed to throw right up front when the overflow is detected)

I'm certainly willing to discuss the idea - one possibility is that our implementation or design was bad.

IME, most thoughtful implementations and designs are not bad, but can be improved as new use cases or updated requirements are discovered.

 

Some other approach might work. We originally liked the idea because a float can tell us if it has become an undefined value, seemed like this concept should transfer. Part of it was confusion because a SafeInt can never become invalid, and a comparison operation can never throw.

It was specifically designed so it never becomes invalid and comparisons never throw.

A float can be "invalid" (NAN), and NANs *can* be compared for example without a trap (of course I'm referring to non signaling NANs, which are the most common)

 

So introducing something that acts somewhat the same, but throws in places the other cannot was a mess.

 

If SafeInt is compared to builtin int, then it indeed can throw in places the builtin won't. But that is *precisely* the idea of SafeInt.

[robertmac...@gmail.com]

On Wednesday, November 28, 2012 4:13:22 AM UTC-8, Fernando Cacciola wrote:

On Wed, Nov 28, 2012 at 4:37 AM, <robertmac...@gmail.com> wrote:

This is very interesting.  When I started on this, I started with "save_range<min, max>" from which safe<int> is derived.  This left open the possibility of using safe_range<0, 4> * safe_range<0,8>  to return a safe_range<0, 12> which was very cool to me.  But the TMP got just to complex and I scaled back my so that safe_range<0,4> is implemented as a safe<unsigned char> etc.

OTOH, in our context: a std proposal, we can just leave that to the implementations (knowing that it could be complex, but *can* be done). There are far more difficult things in the new language definition, so much that haven't even been implemented yet.

After I wrote this post I went back the check the code.  What I said above is not correct.  The safe<T> library functions like the following:

a) safe<int<number of bits>> is just a thin wrapper around safe_int_range<min int<number_of bits, max int<number of bits>.

b) so if one makes

safe_unsigned_range<0, 3> x;    // two bit integer
safe_unsigned_range<0, 15> y;  // four bit integer

x + y will be of type safe_unsigned_int<0, 63> // 7 bit integer
x + y + z will be of type safe_unsigned_int<0, 1023> // 10 bit integer

etc for other types (signed) and sizes.

This has the potential to speed up calculations on some machines considerably.

I had toyed with implementing a compile time range arithmetic so that rather than
using the nearest integer size one would use the actual ranges themselves so htat
safe_int_range<m, n> + safe_int_range<p, q> would result in type safe_int<m+p, n+q>.
This I could to for addition, but getting to into multiplication and division got
complicated too fast.  So I settled on the above as an expedient compromise.

Robert Ramey

[Chris Jefferson]

I use my own safeint extensively, and find it to be very useful in protecting from various kinds of overflow.

There is (in my opinion) one major design flaw in safeint, namely the operators like:

'operator int() const', which allow the safeint to be turned back into an int, for function calls. I prefer having a member function 'x.raw()', or new function 'checked_cast<int>(x)'. This does make code using safeint much more verbose, but means you cannot accidentally invoke unsafe behaviour, by turning back into non-safe types.

I feel if someone is going to the effort of using safeint, then they should care both when values are turned into safeint, and turned back. However, this goes get particularly annoying when doing things like indexing vectors, where you must keep writing 'v[x.raw()]' all the time.

Chris


On 08/11/12 02:59, Ben Craig wrote:

SafeInt information can be found here.  Basically, it is an open source library authored by security expert David LeBlanc of Microsoft.  It is basically a "drop-in" replacement for integer types, and will throw an exception whenever integer overflows occur.  I believe that getting this added to the standard would be a boon to C++ and secure code.  It should be a relatively low effort addition considering the "proof-of-concept" is already widely used within Microsoft.
--
 
 
 

[dvd_l...@yahoo.com]

On Tuesday, November 27, 2012 11:37:34 PM UTC-8, robertmac...@gmail.com wrote:

 

Ah - from the standpoint of keeping things from overflowing, I would tend to agree. From the standpoint of being able to use it in production code because I have not caused a perf problem, I disagree.

I'm not convinced that promoting the types to 64 bits is more expensive timewise than the alternatives. I'd have to see some real data on that.

OK, so looking at the case of multiplication on a 32-bit system, to do a 32-bit multiplication, we take 2 registers, and run imul, which then places the result in one of the source registers. Pretty lean. Now go look at what happens with a worst-case 64-bit multiplication - we pack our data into 4 registers (which is half of our general purpose registers), and then (at least when doing this with Visual Studio - I expect other compilers will be similar) enters a function which will call another 16 assembly instructions, at least two of which (possibly 4 - (a + b) * (c + d ) expands to ac+ ad + bc + bd) are multiplications.

 

Without considering the side-effects of chewing up half the available registers, we're looking at twice the multiplication instructions, and a total of about 20 assembly instructions vs. three. Some of that's common code, but for every multiplication we've doubled the number of instructions at each point, which expands the size of the code, which hurts perf.

 

If we look at an addition, you have a similar issue where instead of 2 registers you now have four, and you will have 2 adds. If I wanted to be careful about it, we could go count cycles per instruction and add them up, but the raw instruction count is so much different that it is obvious what the result will be.

 

Division will do the same thing, and you will find that a 64-bit division is a very expensive thing to do. 32-bit division is not cheap, but 64-bit is worse.

 

Expanding the size like this violates one of the constraints I had, which was that you should be able to change a declaration from int to SafeInt<int>, and not have a substantial perf loss.

 

If what you want to do is just lose data as little as possible, and perf isn't a problem for you, then some sort of big int variable length integer class would do the job.

 

 

I would note that there could be a middle ground, though it may be tricky to get to compile. You could say that for SafeInt of types smaller than int, then the return would be SafeInt<int>

This is very interesting.  When I started on this, I started with "save_range<min, max>" from which safe<int> is derived.  This left open the possibility of using safe_range<0, 4> * safe_range<0,8>  to return a safe_range<0, 12> which was very cool to me.  But the TMP got just to complex and I scaled back my so that safe_range<0,4> is implemented as a safe<unsigned char> etc.

 

This could be done, but you'd have to do a partial template specialization over the entire class, and you'd end up with multiple versions of all the members. While it is enticing from an academic standpoint, from a work needed to implement standpoint, it is tough to justify. And in practice, we're most often working with 32-bit instances, second most frequent case is mixed 32 and 64-bit.

 

[dvd_l...@yahoo.com]

On Wednesday, November 28, 2012 4:08:38 AM UTC-8, Fernando Cacciola wrote:

On Wed, Nov 28, 2012 at 12:22 AM, <dvd_l...@yahoo.com> wrote:

I agree that there are two separate goals. One is to avoid overflow by promoting to the next integer This would reach bigint in the end. The other is to turn overflow into well defined and *useful* behavior, but without any need to avoid it, just to deal with it.

From your use cases I can see that SafeInt is aimed at the later. The uses I have in mind are closer to the former.

So, IMO a proposal should contemplate both, and possibly, provide utilities to both problems.

 

Yes, agreed. I have done numerical analysis in the past, which is where I first became sensitive to this problem. Once I realized that was your frame of reference, many of your comments became more clear.

 

 

What is undefined is the case of SafeInt<T> op SafeInt<U>. I don't know what type you want back, and compilers tend to just throw up their hands and refuse to compile. You could have a large table of all the types, but that's ugly. So I then ask you to make up your mind and do for example (U)SafeInt<T> op SafeInt<U>.

  

Integer types are ranked based on their ranges. That's used in integer promotion. IMO, it's perfectly valid and I would say simple to define similar promotion rules for SafeInt<T> op SafeInt<U> based on the operation.

 

If you don't specialize them out, then you cannot get this to compile. I could theoretically have 64 specializations per binary operator (possibly omitting things like shift). You would also run into problems with things like:

 

- (SafeInt<int>(x) * SafeInt<unsigned int>(y))

 

If we followed standard casting rules, the multiplication would yield a SafeInt<unsigned int>, and then when we went to negate it, it will a) throw, and b) be doing something undefined by the standard and subject to having some compilers just toss your expression out completely.

 

While I do like the overall approach, and have spent a good bit of time attempting to sort out how it might work, things like this give me headaches and I decided shipping was a cool feature. In practice, you do not see this happen often.

[dvd_l...@yahoo.com]

On Wednesday, November 28, 2012 5:23:56 AM UTC-8, Fernando Cacciola wrote:

On Wed, Nov 28, 2012 at 12:01 AM, <dvd_l...@yahoo.com> wrote:

Thanks, then yes, we agree on that. However, you would need both throwing and non-throwing semantics, as you see in the code. The throwing semantics can sometimes have a cleaner failure path.

IIUC, this is because you have failure policies.
If, OTOH, the library just consistently throw as the sole overflow handling mechanism, you won't need both.

I would (and probably will) argue that, a *standard library utility* should just consistently throw. Or else, something at a wider lever, across libraries, should be proposed.
 

There are two counter-points - first is that while it is nice to throw, is it nicer to allow the caller to decide what to throw. It makes it a lot easier to use this class where either there are existing exception classes you'd like to integrate with, and it makes it easier if you'd prefer to just take the app down. In the Windows-specific case, we sometimes have code which isn't set up with exception handlers, and you might choose to use Windows exceptions. On UNIX, you could do similar things with signals.

 

The other is that throwing and catching an exception is very expensive. If we think that failure cases could be common, then we are a lot better off with a function that performs the addition and returns a status. We also would like to have tools to solve the problem where we may not be allowed to use exceptions - for example, in the kernel.

 

I'm certainly willing to discuss the idea - one possibility is that our implementation or design was bad.

IME, most thoughtful implementations and designs are not bad, but can be improved as new use cases or updated requirements are discovered.

 

Fair enough.

 

[dvd_l...@yahoo.com]

On Wednesday, November 28, 2012 9:03:02 AM UTC-8, Chris Jefferson wrote:

I use my own safeint extensively, and find it to be very useful in protecting from various kinds of overflow.

There is (in my opinion) one major design flaw in safeint, namely the operators like:

'operator int() const', which allow the safeint to be turned back into an int, for function calls. I prefer having a member function 'x.raw()', or new function 'checked_cast<int>(x)'. This does make code using safeint much more verbose, but means you cannot accidentally invoke unsafe behaviour, by turning back into non-safe types.

 

Yes, this is a trade-off. The problem is that it then prevents you from using temporaries in a lot of common cases. For example:

 

Foo(SafeInt<int>(x) * 2);

 

This was a debated design decision, and is not by accident. Another much more serious problem is that the raw approach lends itself to abuse, like so:

 

template <typename T>

T SafeInt<T>::raw() const { return m_int; }

 

People then call this, and any further casts, say on entry into the function now become unsafe. Or perhaps the signature of the function changes, it is nice if the SafeInt parameter will then check casting to match. This is a problem we have seen with some of the C-style integer libraries - people check one operation when they should have checked three.

 

I agree that overloaded casting operators are in general treacherous, but in this case it results in safe code more often, which is the primary goal.

 

 

 

I feel if someone is going to the effort of using safeint, then they should care both when values are turned into safeint, and turned back. However, this goes get particularly annoying when doing things like indexing vectors, where you must keep writing 'v[x.raw()]' all the time.
     

Actually, that case is annoying either way. I cannot figure out why (perhaps a compiler bug?) the compiler does not just attempt a cast to ptrdiff_t when used as an index, but I do have to extract the underlying int to use it as an index.

 

[Fernando Cacciola]

On Wed, Nov 28, 2012 at 5:45 PM, <dvd_l...@yahoo.com> wrote:

On Tuesday, November 27, 2012 11:37:34 PM UTC-8, robertmac...@gmail.com wrote:

 

Ah - from the standpoint of keeping things from overflowing, I would tend to agree. From the standpoint of being able to use it in production code because I have not caused a perf problem, I disagree.

I'm not convinced that promoting the types to 64 bits is more expensive timewise than the alternatives. I'd have to see some real data on that.

OK, so looking at the case of

While all the facts in your analysis are correct, I think the conclusion is not that clear.

The issue is this:

Consider a type T which is the largest natural integer in a given platform. Now consider integer types U1, U2, U3 etc all of which are smaller than T.

Further, let's assume that the most efficient and clean way to implement *the test for overflow* for a given operation between SafeInt<Un> is to promote both operands to Un+1 (restricting this implementation technique to types smaller than T). AFAICT this is exactly what SafeInt as well as Rober's safe<> do, so it's sensible assumption.

Since the implementation is *already* performing the promotion to the next integer type in order to efficiently test for overflow, it is IMO a total waste to don't just return that perfectly exact and in-range value, and instead sort-of *cause* the overflow by unnecessarily downcasting to the operands type.

OTOH, if we are operating on T then an implementation might very well not use an expensive 2T to test for overflow, in which case your analysis applies and it would more efficient to test for the overflow in a different way.

So, it seems to me that automatically promoting up to a certain implementation-defined type is both useful and efficient. Beyond that type, different application domains would benefit from one or other solution, thus like I said I would like a proposal to provide both, or at least leave a sensible path for a separate proposal to complete the offering.

[Fernando Cacciola]

OK.

Now following up on my latest response, I would still say that a certain "logical path" of automatic promotions are reasonable. The proposal could only contemplete those which are evidently reasonable, and leave all other cases in the wat SafeInt<> is now.

This seems like a balance between your's and Robert's approaches.

[dvd_l...@yahoo.com]

On Wednesday, November 28, 2012 1:36:50 PM UTC-8, Fernando Cacciola wrote:

OTOH, if we are operating on T then an implementation might very well not use an expensive 2T to test for overflow, in which case your analysis applies and it would more efficient to test for the overflow in a different way.

So, it seems to me that automatically promoting up to a certain implementation-defined type is both useful and efficient. Beyond that type, different application domains would benefit from one or other solution, thus like I said I would like a proposal to provide both, or at least leave a sensible path for a separate proposal to complete the offering.

In practice, there are two things to observe - first is that operations on int16 are some of the most risky. It may be hard to get 4 billion of something, but not that hard to exceed 64k. The second is that the typical case is most often 32 and 64-bit integers.

 

I see benefits and drawbacks to both approaches. So for example, consider a chain of unsigned int16 additions and subtractions. The current implementation has the drawback of not dealing with ( 4 - 5 + 6 ). Promoting to an int would solve this, and be consistent with operator casting. The drawback of this is that it is very cheap to check whether an unsigned addition worked as expected, and not cheap at all to determine if (int + int) worked. From a perf standpoint, we prefer to avoid signed numbers - these are always more difficult to check.

 

From a programming standpoint, it is relatively straightforward to specialize for the five types which are smaller than int in normal modern use. But if we are talking about the standard, now nothing is guaranteed - we know that sizeof(char) is 1, but can infer nothing about short, int, long, and long long. So it would be tricky to make the specializations work correctly if we cannot make assumptions about relative sizes - can likely overcome some of this by making yet another set of cases where we determine register size with sizeof(size_t), and can then go from there.

Even so, following the standard promotion rules can still get us into trouble, since short + unsigned short yields and int, but int + unsigned int yields an unsigned int, and not a long long (as C# does, and IMHO, the standard ought to have promotion rules that don't have exceptions in the middle).

 

I'm tempted by the benefits of special casing for sizeof(type) < sizeof(int), but I am wary of the perf implications.

[Lawrence Crowl]

On 11/27/12, Fernando Cacciola <fernando...@gmail.com> wrote:
> On Nov 26, 2012 Lawrence Crowl <cr...@googlers.com> wrote:
> > On 11/23/12, Fernando Cacciola <fernando...@gmail.com> wrote:
> > > Both fixed_point<T> and rational<T> are useful as long
> > > as the values do not overflow. However, and this is
> > > particularly true in the case of rationals, there are
> > > several application domains where computations can easily,
> > > and often, overflow. In these cases, one must use a big_int
> > > (unlimited precision integer) as T (whether for a fixed_point
> > > or rational) But that is pessimistically inefficient, so
> > > one would consider a non-template "exact" numeric type which
> > > would have a dynamic internal representation of rational<T>
> > > but which would automatically switch from T to 2T (meaning
> > > a two times bigger integer), until it reaches big_int.
> >
> > The study group has reached a tentative conclusion that a
> > rational should be based either on a bigint, or do rounding
> > when the representation is not sufficient for the true result.
> > The former would be useful in computational geometry. The latter
> > would be useful in music.
>
> I agree. Well almost. There are significant efficiency concerns
> when using bigint, and I think that in C++ it's possible to
> overcome that by means of a mechanism that promotes to "the next
> most efficient integer type needed" as computations are performed.
> Something of this form has been done, sort of manually, over
> the past decade or more, in different unrelated projects, and it
> would be fantastic to capture some of that within standard C++

The committee was leaning towards a tagged representation for bigint,
enabling fast single-word storage for the bulk of actual values.
Of course, the standard itself rarely defines representations.
We just need to make sure the standard permits good ones, and the
market will do the rest.

--
Lawrence Crowl

[Fernando Cacciola]

Fantastic.

Don't know the details but I'm pleased to see that we won't just take the simplistic route and merely standardize some of the big integers that have been around for more than a decade. They get the job done, some with an incredible amount of crafted optimization (take GMP's mpz_t  for example), yet they are still not as good as C++ ought to offer (IMO).