Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SeaHash: A fast, portable hash function in Rust

docs.rs

Post reply on HN
Print view View original

61–70 of 116 posts

Re: SeaHash: A fast, portable hash function in Rust

#61

Post by Animats »

yazaddaruvala wrote: post #53
Manishearth wrote: post #38

Earlier quoted context omitted.

> There's too much "unsafe" code in libraries. Which libraries? I see very few that do this, and all of them are safe abstractions containing some unsafe code. You keep repeating this claim but I haven't seen any evidence to back it up. > If Rust let you access a slice of bytes as an slice of ints, alignment and length permitting, the code above could be much more straightforward. That's what I mean about expressive…

While I mostly agree with you, I'd like to play devil's advocate: The Rust core team is relatively relaxed about the community's usage of `unsafe`. I say this because they do not seem to be interested in actively discouraging it's usage. i.e. `unsafe` is discouraged in documentation, not via tools. "Hey please don't use `unsafe` unless you know what you're doing". Is like writing a comment in Javascript, `function(x…

Tooling could encourage this by requiring that if a module or crate contains unsafe code, its name has to contain "unsafe".

Re: SeaHash: A fast, portable hash function in Rust

#62

Post by pcwalton »

Animats wrote: post #52
pcwalton wrote: post #47

Earlier quoted context omitted.

Why is it better to add safe primitives directly to the compiler rather than implementing them in libraries?

The compiler can look at more data to decide if something is valid, or can be optimized. C++ is trying to add move semantics via templates, but can't get all the way to Rust's borrow checker that way.

OK, but we're not talking about the borrow checker, we're talking about byteorder. There's nothing about the byteorder crate that would benefit from being added to the compiler.

In fact it would make it less safe, since we'd be debugging code that emits LLVM IR instead of writing in an actual language.

Re: SeaHash: A fast, portable hash function in Rust

#63

Post by pcwalton »

Animats wrote: post #60
Manishearth wrote: post #56

Earlier quoted context omitted.

Right, but in this case it doesn't need to. I have yet to see an example of an operation that: - should be safe in Rust but isn't - needs /compiler/ support to work well (can't be done cleanly as a library) - isn't already on the track for implementation (non-lexical lifetimes, SEME regions) You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe.…

You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe. Sure it can. You just need primitives which can be used in asserts such as is_initialized(tab,i,j) indicating that an array is initialized within those limits. Then you can write asserts such as assert(is_initialized(tab,i,j-1)); ... initialize tab[j] assert(is_initialized(tab,i,j)); Standard…

You want us to add dependent types to Rust (which is what you just proposed)? Half the time I see you complaining about Rust you're complaining that it's too complicated!

Re: SeaHash: A fast, portable hash function in Rust

#64

Post by Manishearth »

Animats wrote: post #60
Manishearth wrote: post #56

Earlier quoted context omitted.

Right, but in this case it doesn't need to. I have yet to see an example of an operation that: - should be safe in Rust but isn't - needs /compiler/ support to work well (can't be done cleanly as a library) - isn't already on the track for implementation (non-lexical lifetimes, SEME regions) You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe.…

You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe. Sure it can. You just need primitives which can be used in asserts such as is_initialized(tab,i,j) indicating that an array is initialized within those limits. Then you can write asserts such as assert(is_initialized(tab,i,j-1)); ... initialize tab[j] assert(is_initialized(tab,i,j)); Standard…

> You just need primitives which can be used in asserts such as

Sounds like you're going along the path of a dependent type system (in this specific case)? Yes, that could be done, and would perhaps let you reduce a couple of unsafe blocks in the implementation of Vec and other buffer-based abstractions (but not get rid of all of them).

FWIW there is active work going on for formal verification of Rust (both safe and unsafe code), in the RustBelt project.

In general making unsafe blocks run formal verification would be an interesting thing to do (and would solve this problem completely). I don't think it deserves language support, however (nice-to-have, not must-have). This is a very different goal from your original point of adding a few language features that ease writing lower level abstractions.

--------

Ultimately, you're right. While pcwalton did mention "There's no way to solve that problem without just forbidding unsafe code entirely."; this is a possible alternative -- have language support for scoped formal verification that allows you to use "unsafe" operations safely. I think this is an extreme solution to what I consider to be a mostly nonexistent problem.

For really security sensitive code this would indeed be very useful (and is probably a big motivator behind the RustBelt project). Or just use SPARK or something.

But for most Rust users I think the current system is pretty robust and provides enough primitives to write clean, easy-to-verify abstractions with (verifiable) safe API boundaries. (when I say "verify" here I mean it in the informal sense). I haven't come across unsafe code doing contortions, and I have had the (mis?)fortune of going through a lot of unsafe code. The only rough edges are with FFI, and these are mostly due to a lot of things about unsafe code being underspecified (which don't crop up as often in pure rust unsafe code, but do crop up when you through some C/++ FFI in the mix). There is active work on specifying the exact semantics of unsafe code however, so that should be fixable once it happens.

Re: SeaHash: A fast, portable hash function in Rust

#65

Post by nickpsecurity »

Manishearth wrote: post #64
Animats wrote: post #60

Earlier quoted context omitted.

You did mention uninitialized arrays but uninitialized data is inherently unsafe. It's not an operation that can be made safe. Sure it can. You just need primitives which can be used in asserts such as is_initialized(tab,i,j) indicating that an array is initialized within those limits. Then you can write asserts such as assert(is_initialized(tab,i,j-1)); ... initialize tab[j] assert(is_initialized(tab,i,j)); Standard…

> You just need primitives which can be used in asserts such as Sounds like you're going along the path of a dependent type system (in this specific case)? Yes, that could be done, and would perhaps let you reduce a couple of unsafe blocks in the implementation of Vec and other buffer-based abstractions (but not get rid of all of them). FWIW there is active work going on for formal verification of Rust (both safe and…

Don't forget there's a middle ground between not having them and manual, formal verification. It started with Eiffel with basic contracts that checked properties during testing and/or runtime. That did well in commercial deployments. SPARK took it formal with a basic, boolean encoding for programmer understanding. It uses a subset of Ada to prove absence of all kinds of error conditions without runtime checks or manual proof. It can optionally do more with a theorem prover but optional. Eschersoft did Perfect Developer to do it in high-level language with C, Java, or Ada generation. So, at least three are doing it in products with industry deployments with two highly concerned about performance in low-level applications.

Although I'm not getting into this dispute, I will add in general that Rust might benefit from such contracts or push-button verification of key properties as deployed successfully in Eiffel, SPARK, Ada 2012, and Perfect Developer. A language subset might be used like in SPARK to allow automated verification of those sections against common types of errors. Three follow-up benefits will be easier changes/integrations in maintenance phase, automated test generation from specs, and aiding dynamic analysis by giving it invariants to look at. Could be optimization benefits but I'm not qualified to say on that. Intuitively seems possible like using minimum-sized, data structure for a number range in spec or type. Stuff like that.

These techniques are really under-utilized despite being proven out many times over in high-reliability products.

Re: SeaHash: A fast, portable hash function in Rust

#66

Post by throwbsidbdk »

aappleby wrote: post #57
thomasahle wrote: post #50

Earlier quoted context omitted.

Since you clearly pit a lot of thought into these kinds of hash functions, I wonder what you thoughts are about the kind of hash functions used in theory? That is theoretically proven "k-independent" functions, such as polynomial hashing, multiply shift or tabulation hashing?

Making a fast, good hash function isn't too hard now, so some sort of "provable key-independent collision resistance" is definitely the next thing that needs to be worked on. That said, I haven't really looked into the theory much.

Have you looked at Siphash? I remember reading recently that murmur has been found to have some predictable hashes independent of salts but a lot of big names still use it since it's fast and has good properties.

Re: SeaHash: A fast, portable hash function in Rust

#67

Post by wahern »

pcwalton wrote: post #43
Animats wrote: post #42

Earlier quoted context omitted.

Unsafe code must uphold the invariants of safe Rust. Ideally, yes. In practice, maybe. We're probably going to see "unsafe" code that assumes good behavior on the part of the caller. That's a classic problem with APIs.

There's no way to solve that problem without just forbidding unsafe code entirely. Unsafe code can have bugs; that's why you should keep it to the minimum and keep it well-known and audited. In this case, the byteorder crate would have been more appropriate than handrolling unsafe code.

I think the issue, if there is one, is that arguably the more appropriate thing to do would have been to implement the code without unsafe, using an intrinsically correct algorithm. The type-punning is premature optimization. _That_ was the misstep.

That the byteorder crate exists is irrelevant in as much as this was an example of the urge for premature optimization leading the developer down the wrong path. The same amount of time pondering whether to even bother using a pre-existing library might have been better spent second-guessing the urge to type-pun at all.

Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in that create uses copy_nonoverlapping, which I assume is analogous to memcpy in C. That's a very round-a-bout and inefficient way to accomplish the task, and likely patterned after similarly bad C code.

To even make it worthwhile, any byteorder library should provide some kind of iterator interface so that it can maintain alignment state while permitting the loop to be unrolled by the compiler. (And it might require a closure or someway of expanding a block of code inline.) That's probably the only way it could outperform the simple, hand-rolled, endianness- and alignment-neutral solution. But it doesn't provide that kind of interface AFAICT.

It's all sort of ironic, which I suppose was the point upthread--this is an example of the irrational urge for premature optimization and of bad programming idioms being hauled into Rust land completely unhindered by Rust's type safety features. And the better, correct, and likely more performant way of accomplishing this task could have been done just as safely from C as it could from Rust.

Re: SeaHash: A fast, portable hash function in Rust

#68

Post by Manishearth »

nickpsecurity wrote: post #65
Manishearth wrote: post #64

Earlier quoted context omitted.

> You just need primitives which can be used in asserts such as Sounds like you're going along the path of a dependent type system (in this specific case)? Yes, that could be done, and would perhaps let you reduce a couple of unsafe blocks in the implementation of Vec and other buffer-based abstractions (but not get rid of all of them). FWIW there is active work going on for formal verification of Rust (both safe and…

Don't forget there's a middle ground between not having them and manual, formal verification. It started with Eiffel with basic contracts that checked properties during testing and/or runtime. That did well in commercial deployments. SPARK took it formal with a basic, boolean encoding for programmer understanding. It uses a subset of Ada to prove absence of all kinds of error conditions without runtime checks or manu…

Yeah, this exists, and would be interesting. I again think that it's a bit too extreme a solution to be baked into Rust itself, but I'd love a SPARKish Rust variant.

Re: SeaHash: A fast, portable hash function in Rust

#69

Post by Gankro »

throwbsidbdk wrote: post #66
aappleby wrote: post #57

Earlier quoted context omitted.

Making a fast, good hash function isn't too hard now, so some sort of "provable key-independent collision resistance" is definitely the next thing that needs to be worked on. That said, I haven't really looked into the theory much.

Have you looked at Siphash? I remember reading recently that murmur has been found to have some predictable hashes independent of salts but a lot of big names still use it since it's fast and has good properties.

When SipHash was presented at CCC, it was alongside the proof of concept attacks against MurmurHash and CityHash. See the "Attacks" section of [0].

Murmur was notable at the time for its use in Java and Ruby. Ruby has since moved to SipHash-2-4, while Java (OpenJDK) has thrown up its hands in disgust at the problem and created a binary tree fallback mode for its HashMaps[1]. Which at this point I'm pretty confident is the only rigorously correct solution.

[0]: https://131002.net/siphash/

[1]: http://openjdk.java.net/jeps/180

Re: SeaHash: A fast, portable hash function in Rust

#70

Post by duaneb »

Manishearth wrote: post #58
yazaddaruvala wrote: post #53

Earlier quoted context omitted.

While I mostly agree with you, I'd like to play devil's advocate: The Rust core team is relatively relaxed about the community's usage of `unsafe`. I say this because they do not seem to be interested in actively discouraging it's usage. i.e. `unsafe` is discouraged in documentation, not via tools. "Hey please don't use `unsafe` unless you know what you're doing". Is like writing a comment in Javascript, `function(x…

Nobody is putting effort into propaganda about unsafe because the community is already very strongly averse to this, and is careful about writing unsafe code. It's not a problem. If it becomes a problem (I doubt it) we can put effort into it. People learn about the language through discussion or documentation, and both of these venues actively discourage unsafe. The one resource out there that teaches unsafe code in…

Have you ever been bitten by unsafe code?

IMHO any metrics would be gamed and prioritized above actually quality. As actual quality isn't suffering, why add the unsafe metric in at all? Seems like paranoia not born out of experience.

Post reply on HN