Copyright © 2018-2023 by Jeffrey Sarnoff. This work is made available under The MIT License.
Using the default Int or UInt types allows overflow and underflow errors to occur silently, without notice. These incorrect values propagate and such errors are difficult to recognize after the fact.
This package exports safer versions. These types check for overflow and underflow in each of the basic arithmetic functions. The processing will stop with a message in the event of overflow or underflow. On one machine, the overhead relative to the built-in integer types is <= 1.2x.
Integer overflow occurs when an integer type is increased beyond its maximum value. Integer underflow occurs when an integer type is decreased below its minimum value. Signed and Unsigned values are subject to overflow and underflow. With Julia, you can see the rollover using Int or UInt types:
typemax(Int) + one(Int) < 0
typemin(Int) - one(Int) > 0
typemax(UInt) + one(UInt) == typemin(UInt)
typemin(UInt) - one(UInt) == typemax(UInt)
There are security implications for integer overflow in certain situations.
for i in 1:a
secure(biohazard[i])
end
a = Int16(456) * Int16(567)
a == -3592
# the for loop does not execute
-
Your work may require that integer calculations be secure, well-behaved or unsurprising.
-
Your clients may expect your package/app/product calculates with care and correctness.
-
Your software may become part of a system on which the health or assets of others depends.
-
Your prefer to publish research results that are free of error, and you work with integers.
-
SaferIntegers let you work more cleanly and always alerts otherwise silent problems.
-
This package is designed for easy use and written to be performant in many sorts of use.
-
All exported types are stable (e.g.
typeof(SafeInt32(1) + 1) == SafeInt32
) -
Using SaferIntegers can preclude some known ways that insecure systems are breached.
@saferintegers include(joinpath("PackageTestDirectory", "PackageTests.jl"))
- includes a type modified
PackageTests.jl
in the current environment - all
Integer
types inPackageTests.jl
are becomeSafeInteger
types - run it and see if there are any problems!
- includes a type modified
To use safer integers within your computations, where you have been using
explict digit sequences put them inside the safe integer constructors,
SafeInt(11)
or SafeUInt(0x015A)
and similarly for the bitsize-named versions
SafeInt8
, SafeInt16
.. SafeInt128
and SafeUInt8
.. SafeUInt128
Where you had usedInt
or UInt
now use SafeInt
or SafeUInt
and similarly
with the bitsize-named versions.
SafeInt and SafeUInt give you these arithmetic operators:
+
, -
, *
, div
, rem
, fld
, mod
, fld1
, mod1
, ^
which have become overflow and underflow aware.
The Int and UInt types can fail at simple arithmetic
and will continue carrying the incorrectness forward.
The validity of values obtained is difficult to ascertain.
Most calculations proceed without incident, and when used SafeInts operate as Ints should a calculation encouter an overflow or underflow, we are alerted and the calculation does not proceed.
Get the package:
Pkg.add("SaferIntegers")
Use the package:using SaferIntegers
- These functions check for overflow/underflow automatically:
abs
,neg
,div
,fld
,fld1
,cld
,rem
,mod
,mod1
divrem
,fldmod
,fldmod1
-
,+
,*
,^
SafeInt8
,SafeInt16
,SafeInt32
,SafeInt64
,SafeInt128
SafeUInt8
,SafeUInt16
,SafeUInt32
,SafeUInt64
,SafeUInt128
SafeSigned
,SafeUnsigned
,SafeInteger
SafeRational
They check for overflow, even when multiplied by the usual Int and UInt types.
Otherwise, they should be unsurprising.
abstract type SafeUnsigned <: Unsigned end
abstract type SafeSigned <: Signed end
const SafeInteger = Union{SafeUnsigned, SafeSigned}
(thanks to Mark Kittisopikul's PR and TimHoly's design of Ratios.jl)
Signed(x::SafeSigned)
returns an signed built-in integer of the same bitwidth as x
Unsigned(x::SafeUnsigned)
returns an unsigned built-in integer of the same bitwidth as x
Integer(x::SafeInteger)
returns a built-in integer of the same bitwidth and either Signed or Unsigned as is x
SafeSigned(x::Signed)
returns a safe signed integer of the same bitwidth as x
SafeUnsigned(x::Unsigned)
returns a safe unsigned integer of the same bitwidth as x
SafeInteger(x::Integer)
returns a safe Integer of the same bitwidth and is either Signed or Unsigned as matches x
signbit
,sign
,abs
,abs2
count_ones
,count_zeros
leading_zeros
,trailing_zeros
,leading_ones
,trailing_ones
ndigits0z
isless
,isequal
,<=
,<
,==
,!=
,>=
,>
>>>
,>>
,<<
,+
,-
,*
,\
,^
div
,fld
,fld1
,cld
,rem
,mod
,mod1
divrem
,fldmod
,fldmod1
zero
,one
typemin
,typemax
,widen
julia> @saferintegers begin
x = 64
y = Int16(16)
z = x + y + SafeInt128(x)
x, y, z
end
(64, 16, 144)
julia> typeof.(ans)
(SafeInt64, SafeInt16, SafeInt128)
julia> cd(<source file directory>)
julia> @saferintegers include(<filename.jl>)
julia v1.1-dev
using SaferIntegers
using BenchmarkTools
BenchmarkTools.DEFAULT_PARAMETERS.time_tolerance=0.005
@noinline function test(n, f, a,b,c,d)
result = a;
i = 0
while true
i += 1
i > n && break
result += f(d,c)+f(b,a)+f(d,b)+f(c,a)
end
return result
end
hundredths(x) = round(x, digits=2)
a = 17; b = 721; c = 75; d = 567;
sa, sb, sc, sd = SafeInt.((a, b, c, d));
n = 10_000;
hundredths( (@belapsed test(n, +, $sa, $sb, $sc, $sd)) /
(@belapsed test(n, +, $a, $b, $c, $d)) )
1.25
hundredths( (@belapsed test(n, *, $sa, $sb, $sc, $sd)) /
(@belapsed test(n, *, $a, $b, $c, $d)) )
1.25
hundredths( (@belapsed test(n, div, $sa, $sb, $sc, $sd)) /
(@belapsed test(n, div, $a, $b, $c, $d)) )
1.14
The exported abstract types SafeInteger, SafeSigned, SafeUnsigned are now defined as originally intended. Julia’s advancement, the active pursuit of consistant type abstractions, made it easy.
SafeUnsigned <: Unsigned
SafeSigned <: Signed
SafeInteger <: Integer
This clean approach holds through the exported concrete types.
SafeUInt <: SafeUnsigned <: Unsigned <: Integer <: Real
SafeInt <: SafeSigned <: Signed <: Integer <: Real
A good deal of benchmarking was done to evaluate the appropriateness of using SaferIntegers with Ratios.jl.to protect calculations within Interpolations.jl from Integer overflow in innocent looking linear interpolation without warning. The results are compelling, encouraging their wider application.
Using SafeInt64s with Ratios requires 1.025 the time used with Int64 Ratios. This is merely an extra 1.5 seconds per minute.
see Ratios/pull/23 for details.
The formal distinction is in the creation of the abstract types, and so the inheritance hierarchy that pervades the concrete types.
The new way is much cleaner and makes reasoning about the shallow extension to the abstract inheritance paths much simpler. This is given in the announcement above. The old way was a result of earlier internal limitations that Julia’s type patterning had embedded in the way Unsigned and Signed integer types had been developed (well, implemented). This forced defining these abstract types:
abstract type SafeInteger <: Integer end
abstract type SafeSigned <: SafeInteger end
So it precluded the natural pattern of type abstraction and well-formed instantiation logic we have now.
- it had been the case that
!(SafeUnsigned <: Unsigned)
.
There are some additional changes.
- Several bugs (limited to small yet substantive subdomains) were found by careful users and are fixed.
float(x::SafeInteger)
now works to mirrorfloat(x::Integer)
, for cross-package support.- There are other implementation improvements that just work.
This work derives from RoundingIntegers.jl.
The @saferintegers macro machinery is heavily informed by ChangePrecision.jl.