scottconstable wrote: > This is not a Rust concern, but re-reading the initial post, it _looks_ like > your own statistics suggest that consuming 3 bits for arity costs more than > it buys you. As stated, (didn't check your math, just going off what you > said) prior to your change, we expect 0.01383765 collisions in your sample > environment.
If you had checked my math, you would have noticed that the values in the right-hand column were not exactly correct! I found and fixed a but in my Excel code and updated that chart, but the numbers didn't change by much. > After your change, we expect to have the _sum_ of your right hand column in > collisions, which comes out to 0.0266774 - nearly double the rate of > collisions we have with the basic implementation. In fact, I think that any > scheme like this will always going to increase the number of overall > collisions, given that the arity is implicitly hashed into the representation > already. Your analysis is correct that the total number of expected collisions would increase from 0.01375771 to 0.02660650 (with the updated statistics). > The main reason I could see to consider this is if for some reason a > cross-arity collision is more dangerous than a same-arity collision in terms > of exploitability, which I can't immediately argue, but perhaps you have > something for this that was just assumed in the initial post? I think that a cross-arity collision is clearly more dangerous than a same-arity collision. This is what I had written in the PR description: > > The current 32-bit kCFI hash does not prevent, for example, a 2-arity fptr > > from calling a 3-arity target if the kCFI hashes collide. If this were to > > happen, then potentially malicious stale/dead data in RDX at the call site > > could suddenly become live as the third parameter at the call target. Including the arity in the hash does prevent or even reduce the likelihood that a cross-arity collision will occur, if the hash function is uniform. Suppose that two function types' hashes collide (under the current 32-bit hash scheme). The probability that the arities differ is equal to 1 minus the probability that the arities agree: 1 - ((32/10903)*(31/10902) + (2492/10903)*(2491/10902) + ... + (148/10903)*(147/10902)) = 0.75901 Thus, if there is a hash collision, there is roughly a 76% chance that it will be a cross-arity collision. https://github.com/llvm/llvm-project/pull/117121 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
