Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #71105

Re: What's the best hashing function?

Show all headers | View raw

On Tuesday, September 22, 2015 at 3:23:23 AM UTC-5, David Brown wrote:
> On 21/09/15 20:29, supercat wrote:
> > The problem is that if the program's requirements specify that maliciously-
> > crafted inputs may yield essentially-arbitrary outputs, but are required
> > not to allow the creator of those inputs to take over the machine, the only
> > way for the programmer to ensure that the compiler's generated code will
> > meet those requirements is for the SOURCE CODE to demand that the compiler
> > perform additional operations which will have no effect the programmer cares
> > about beyond preventing the compiler from making unwanted inferences about
> > the program's input.
> 
> You are changing the specifications yet again.  Now the functions
> response to inputs with out-of-range differences should be something
> specific and very definitely /not/ arbitrary - it must somehow be
> something that does not allow the user to take over the machine.  That
> is an impossible specification as it stands - there is not enough
> information for a programmer to write such code, let alone for a
> compiler to guess what you mean.

Appendix L of the C11 Standard is not particularly well-written, but it
expresses the basic concept that programs which are "analyzable" should
separate Undefined Behavior into "critical" and "non-critical" forms, with
the intention that the occurrence of actions which trigger non-critical
forms of undefined behaviors (such as integer overflow or accessing a
scalar variable with indeterminate value) should not entitle the compiler to
invoke critical forms.  Appendix L fails to sufficiently delineate what
range of actions should or should not be allowable to allow a programmer
to know whether a piece of code could trigger critical UB given invalid
input [e.g. given:

    unsigned char foo[5000];

    void blah(uint16_t x, uint16_t y)
    {
      int32_t z = x*y;
      if (z >= 0 && z < 5000) foo[z] = 6;
    }

it's unclear whether blah(42950,50000) would entitle a compiler to write to
foo[-131071], which would be Critical Undefined Behavior, or how the code
would need to be written to ensure that couldn't happen.  Note that even if
overflow is required to have no effect beyond yielding Indeterminate Value,
and every rvalue conversion of an Indeterminate Value is required to have no
effect beyond yielding another Indeterminate Value, and comparisons with
Indeterminate Values yield an Unspecified result, the above code could
generate a write to foo[-131071]; for Appendix-L Analyzability to be useful,
there needs to be some defined process for converting an Indeterminate Value
to an Unspecified Value, such that it would not be possible for the compiler
to simultaneously regard "z" as holding 4294836225 (which is greater than
zero) and -131071 (which is less than 5000).

> You might
> say it should an int, but don't care what int - in which case the
> simple, naive program with no checking will give you appropriate code on
> any sane compiler (just because the behaviour is undefined, does not
> mean that the compiler /must/ generate nasal daemons).  

If like me you do not believe that any SANE compiler would trigger arbitrary
and unpredictable behaviors, would that imply that you would consider some
of the trends in hyper-modern compiler philosophy to be INSANE?

>                                                         Whether you are
> happy to accept such a reasonable implementation of the undefined
> behaviour, or whether you insist on avoiding any undefined behaviour, is
> up to you.

I suspect I would be happy to accept the behaviors you would consider to be
sane.  I think our point of disagreement is that current compiler philosophy
believes that in those cases where the Standard imposes no requirements,
compilers should seek out any behavior that would be more "efficient" without
regard for whether it would satisfy application requirements which might have
been met by more commonplace behaviors.
 
> The /real/ problem here, is that you apparently do not understand the
> basics of software design.  If you want a function that will do
> something, then step one is to decide what it will do - give it a
> complete specification covering all inputs that you want to handle in a
> given way.  Regardless of what language you are using, and what the
> standards might say about behaviours, the function's behaviour will be
> undefined for all other inputs - that's what writing a specification
> means.  Then once you have the specification, step two is to write code
> that tells the compiler how to generate that function - on the
> assumption that the inputs match those given in the specification.

In the design of logic circuitry, if one specifies a list of cases when an
output must be high, and a list of cases when it must be low, the expected
normal behavior of a logic compiler is to yield the simplest circuitry
which, for any other combination of inputs, will make the output high or
make it low, without causing the circuit to catch fire, draw substantial
extra current, or doing anything else bizarre.  In some cases, the amount
of circuitry required to ensure that the circuit will produce a high or low
output without drawing excessive requirement will be greater than if
drawing excessive current was a valid behavior when given unspecified
inputs, but I don't think many designers would suggest that a good tool
shouldn't waste circuitry handling such cases.

> Your specification at the time when I wrote it allowed for the
> possibility of launching missiles given unreasonable input values.  It
> is extremely difficult to discuss a problem when you change
> specifications several times in every post.

A requirement that a program must not perform some specific behavior even
when given even maliciously-crafted invalid input, and a requirement that
a program must not grant the authors of maliciously-crafted input the
ability to have a program execute arbitrary code on their behalf, are pretty
much equivalent; any program which fails the latter requirement would, if
given input which was crafted to execute code to perform the forbidden
action, would perform the forbidden action.

> It is a /debugging/ option, to help figure out why your code is not
> doing what you think it should.  It is not an option to use in released
> code.  You should write correct code, according to the specifications
> you have, then there will be no problem.

You suggested that semantics suitable for programs that must not produce
seemingly-valid-but-wrong output in case of overflow (but would be allowed
to abnormally terminate) exist in the form of -fsanitize.  If it is
necessary that release code offer such semantics, how would you suggest
that could be done without bloating the main-line of the code with logic
to detect all possible overflows?

Given a requirement that overflows must be reported if they would cause a
numerically-incorrect result, but may arbitrarily be reported or not in
cases where the result would end up being numerically correct anyhow, the
optimal code to meet that requirement may be dependent upon CPU register
spillage, which is something a compiler will know about and a programmer
won't.  In many cases, performing computations using oversized values may
be cheaper than checking for overflow after every step, but only when
registers are sufficiently plentiful to allow such usage.  If it becomes
necessary to save/restore registers, checking whether a register is within
range of int32, trapping if not, and otherwise just storing the bottom
half and later reloading with sign extension may be faster than having to
save/restore all 64 bits.  Compilers will know a lot more about what
such optimizations would be useful than programmers could ever hope to, but
only if there exist a behavioral specification which provides that allows
compilers to freely select whether computations that exceed the range of
their integer type should yield arithmetically-correct results anyway, or
whether they should trap.

> This is finally getting to the point where something might be
> controversial.  The compiler could reasonably omit the bounds check -
> but I would hope it was able to issue a diagnostic message if it did so
> (assuming the appropriate warning flags).  Quick tests with gcc 4.9 show
> that while that compiler will omit unnecessary tests that come after
> undefined behaviour, it does not omit such tests that come before
> undefined behaviour.

I'm not sure how I see how it's useful to have the compiler omit the code
automatically and also emit warnings.  Either:

1. The code is correct, but the number of substitutions is small enough
   that once a programmer has read the warnings they won't pose too much
   of a distraction on future builds, in which case there probably won't
   have been enough optimizations to have much value.

2. The code is correct, and to avoid having massive numbers of warnings
   the programmer will immediately adds a directive to indicate that
   the apparent behavior is desired, in which case the value of having the
   compiler apply its inferences to code generation before the programmer
   adds the directive will be limited.

3. The code is incorrect, in which case having the compiler apply its
   inferences to code generation will be counter-productive.

In what situation is there significant value in having a compiler both warn
about what it perceives as dead code and eliminate it?

> Note, however, that the reason for all this is the bug in your code.  If
> the compiler omitted the test on reg_size, it is guilty of being
> unhelpful in aiding your debugging, not of generating incorrect code.  I
> believe compilers should be as helpful as possible in helping the
> programmer track bugs - /that/ is why I would be unhappy if it silently
> removed the test.

The purpose of code is to *meet requirements*.  A good language should allow
programmers to formulate a program meeting their requirements in a way which
is concise, readable, and *focused on those requirements that are unique to
their application*.  If more than 10% of the programs in a language will
need to meet some requirement, and if meeting the requirement "manually"
would be expensive, those factors should be taken as a strong indication
that the language should strive to minimize the amount of user-written code
necessary to meet those requirements.

> > Many programs are required to not let the creators of maliciously-crafted
> > inputs take over the machine.  That is hardly an obscure requirement.
> 
> If you don't make that requirement in the specification of the function,
> then it is obscure.  And since most functions are internal, rather than
> directly facing external input, then for most functions it is not a
> sensible requirement.

In cases where the amount of machine code required to make a function safe
against unsanitized data would be significant, it's often good to have
separate functions for sanitized and unsanitized inputs.  Absent a compelling
performance difference, however, I'd suggest that it's better to have a
policy that code should be made "safe" by default.

> > If compilers are allowed to use arithmetic overflow as an excuse to bypass
> > code that would otherwise prevent maliciously-crafted inputs from taking
> > over the machine, then there will never be any situations where a non-broken
> > program which is bound by the above requirement could receive input that
> > would cause overflow.  I'm not quite sure what value there is in having an
> > optimizer which is only effective on broken programs.
> 
> If your code is correct, there is no problem.  The optimiser works best
> on correct code.

If in a correct program, no combination of inputs will produce UB, then what
inferences could an UB-based optimizer ever manage to draw about the inputs
to a correct program?

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 09:35 -0700
  Re: What's the best hashing function? "D. Aaron Sawyer" <aaron@110.net> - 2015-09-16 14:22 -0300
    Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 10:59 -0700
      Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 19:44 +0100
        Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 12:32 -0700
          Re: What's the best hashing function? Bartc <bc@freeuk.com> - 2015-09-16 20:40 +0100
            Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 13:11 -0700
            Re: What's the best hashing function? "James Harris" <james.harris.1@gmail.com> - 2015-09-16 21:16 +0100
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 13:47 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:14 -0700
              Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:08 -0500
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-17 00:13 +0100
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-20 01:13 -0700
          Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-16 13:10 -0700
          Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 22:17 +0100
            Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:33 -0700
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:48 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:58 -0700
                Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:13 -0500
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:17 +0200
                Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-17 08:53 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-17 11:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 10:07 +0200
                Re: What's the best hashing function? Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 09:20 +0100
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 09:25 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 19:45 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 11:47 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 21:49 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 14:50 -0700
                Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-19 00:23 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 11:13 +0200
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-19 11:03 +0100
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 12:38 +0200
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-21 11:29 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-22 10:23 +0200
                Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-22 02:31 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:28 -0700
                Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:18 -0700
                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:24 +0200
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:48 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:56 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 02:09 -0700
            Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 14:49 -0700
              Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:56 +0000
              Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 23:37 +0100
        Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 13:02 -0700
          Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 21:57 +0100
            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 14:16 -0700
          Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:57 +0000
            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:20 -0700

csiph-web