New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Figure out hash-map security #232

Closed

Stebalien opened this issue Jan 7, 2022 · 2 comments · Fixed by #291

Labels

Kind: Bug P1 Topic: Built-in actors

Milestone

Member

Stebalien commented Jan 7, 2022

Most modern languages use a random seed in hash-maps to prevent the DoS attack where an attacker could turn O(1) operations into O(n) operations. However, because we're operating in a deterministic environment, we can't do that.

Note 1: This only impacts system actors. Basically, we need to make sure that a system actor never inserts untrusted data as keys into a HashMap. It's fine if, e.g., a miner actor uses a hash map when called directly by a user.

Note 2: We should not do anything like use chain randomness here. That would just increase the attack surface to non-system actors (a malicious miner could grind on a message till it uses hash maps in such a way that it runs out of gas).

Proposed solution: use btrees and sorted slices as much as possible. These are always log(n).

The text was updated successfully, but these errors were encountered:

Stebalien added this to the Phase 1 milestone

Member

raulk commented Jan 11, 2022

@Stebalien Can you enumerate the concrete current usages of HashMaps you're concerned about?

Member Author

Stebalien commented Jan 11, 2022

All of the uses inside the actors.

Stebalien added Topic: Built-in actors area/fvm Kind: Bug P1 labels

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

645fb43

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

86c8e3a

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

db16078

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

9c8aa03

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

f44fd7a

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

b2e6cb1

Part of #232

Stebalien mentioned this issue

Remove all uses of hash maps in actors #291

Merged

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

6a8cf20

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

5b1e562

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

dacc3c7

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

8ec539b

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

c02c111

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

ffea7c8

Part of #232

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

900717f

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

0aecc8e

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

81f05da

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

55aa7d8

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

afe9000

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

cd4b089

Part of #232

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

e7119e2

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

8cdfc3b

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

f116850

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

e2ab196

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

80c816c

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

6c2c8e2

Part of #232

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

17fad18

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

abb93a4

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

5cef77c

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

27b89c8

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

f40fd1f

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

3cd7b4f

Part of #232

Stebalien added a commit that referenced this issue


          bitfield: replace BTreeMaps with BTreeSets

1. It gives us sorted iteration for free.
2. Works towards #232.

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMap with BTreeMap in sector maps

e8fcd0e

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace HashMaps in the bitfield queue

dbaa9cb

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): avoid HashMap in precommit cleanup

2f1ea06

This technically changes access patterns for an AMT, but this particular
change should be fine due to caching:

1. Before, we'd repeatedly access the same epoch over and over.
2. Now, we access each epoch once, but in the same order as before.

Due to AMT caching:

1. We'll only read blocks the first time we "get" an index (even if we
get it repeatedly).
2. We don't write blocks till we flush at the end.

part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace uses of HashMap/Set in expiration queue

99b8c89

Part of #232

Stebalien added a commit that referenced this issue


          actors(miner): replace rest of the uses of HashMap

44efe24

Part of #232

Stebalien closed this as completed in #291

Stebalien mentioned this issue

Perform operations in sorted order (in builtin actors) filecoin-project/builtin-actors#51

Closed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment