mzpqnxow
commented
3 weeks ago Note that substantial analysis of randomization has been performed and discussed before; see #505, which resulted in a non-negligible improvement to entropy. It's helpful context if you haven't already read it
You may also want to troll through issues @ https://github.com/ivre/masscan as I believe there may have been some discussions there (will link them if I can find them)
I suggest for implementing a deterministic host and port randomizer
FYI- maybe you're aware, but the randomization currently implemented is already deterministic. You (as a user) can easily perform reproducible scans via the seed value, which is what facilitates sharding. It is exposed via the standard CLI/config options.
... performed by segmenting already randomized host lists into
host:portminibatches and only shuffle them when accessed
I'm not sure I understand this, or maybe I'm skeptical of it measurably improving randomness without a big performance cost. It's very possible I'm misunderstanding, or not knowledgeable enough in this particular area to make that assessment, though
If you're suggesting reordering the targets as a one-time cost, at startup, as an added layer on top of the dynamic randomization provided by the hashing scheme, I believe this was discussed previously and eventually dismissed, because the gains were not expected to be substantial
I'll see if I can add a reference to that discussion if I didn't imagine it. I'm sure it could be discussed again, though
To save memory and computation the order of every randomized minibatch can be shared. To randomize further, one can keep multiple progress tracks between neighboring minibatches and switch between them back and forth.
Shared between what, exactly? Sorry, not completely following
I think I understand roughly what you're saying, though:
Adding an additional randomization value (presumably something that is effectively another hash key). That would serve to split the single hash table into an arbitrary number of buckets. It would have the same memory layout, but would have two hash lookups- one to choose a bucket (some subset of the main table) and one to select a target inside the chosen bucket?
It's not immediately clear to me if this would be a worthwhile tradeoff. My concerns being the complexity it would add to what is already arguably the most complex part of the code, and the cost of actually developing the changes AND regression testing
Data would help to win me over, though!
Since multiple hosts are reporting that masscan is bringing heavy access to their servers I think this is a critical feature that masscan can implement.
To be fair, masscan is designed to bring this sort of load when used with a large number of ports, and a relatively small number of addresses; there's really no way around this in terms of code changes
This may be obvious to you, but I'll clarify anyway; the only way to reduce concentrated load on a given address or network for many scenarios is to:
- Reduce your specified packet rate (obviously!)
- Increase the target space or decrease the number of ports, which will effectively decrease the concentration on any targets that you're seeing
Or, improvements to randomness won't help those who are surveying only 1024 hosts at even a modest rate, e.g. --rate 5000 (arbitrary example, the concept holds for many different sizes of each)
Maybe enhancements to randomness would provide an improvement in some use-cases, but for those with a small target set relative to the number of ports they're checking, it won't help (which may be fine, just stating it clearly)
Additionally, alternative hash function like
MurmurHash3can be used instead of cryptography ones, to avoid hash collision and improve performance.
As it stands, without particularly "modern" hardware - a 10 year old CPU - and even without zero-copy - masscan is able to push 1mm pps without a problem
With zero copy, there's practically no limit, unless you need to saturate 100Gig links
Performance improvements are really interesting to me personally, but probably not too important here; though it's important that performance isn't substantially hurt by any proposed changes, perhaps that's why you're mentioning it
That all said, I would be very interested to see data to better understand the problem, and how some of the ideas will improve the situation
Data similar to what is in #505 would be very persuasive
I think what I'm asking is:
- Can you provide more details about the issue you're seeing? Particularly, how large is your target set, and what is your packet rate?
- Do you have any data that you can share, to demonstrate the problem or the solution?
With item 2 specifically, it would be much more likely to get traction from developers
Tagging @p-l- and @robertdavidgraham in case they have more constructive/intelligent (and hopefully succinct) input
James4Ever0
p-l-
I suggest for implementing a deterministic host and port randomizer performed by segmenting already randomized host lists into
host:portminibatches and only shuffle them when accessed. To save memory and computation the order of every randomized minibatch can be shared. To randomize further, one can keep multiple progress tracks between neighboring minibatches and switch between them back and forth.Since multiple hosts are reporting that masscan is bringing heavy access to their servers I think this is a critical feature that masscan can implement.
Further details can be discussed once this suggestion is accepted.
Additionally, alternative hash function like
MurmurHash3can be used instead of cryptography ones, to avoid hash collision and improve performance.