M > N issue

Contents:

  1. Nature of the „M > N issue“
  2. Remedy to the issue
  3. Future work
  4. Credit


Nature of the „M > N issue“

The name of the issue is a shorthand for a more detailed title:

N is fixed by your CPU. On a non-HT processor, this is simply the number of cores. On a HT system, it's double that number. In any case, it makes a good sense to make the number of threads, M, no larger than N: N is the maximum number of threads the CPU can comfortably accomodate, so that no logical core needs to multi-task between multiple threads.

The issue, in short, is that when М > N, the result is either suspicious (because a user has specifically tried to exploit the issue) and moreover probably incorrect, with a high probability that the reported „passwords per second“ score is higher than what the tested machine is capable of. Thus, М > N results aren't suited for any kinds of rankings or competitions.

In more detail: under the default test settings, UnRAR-crack does runs with M = 1, 2, 3, 4, 8, 16, 32, ..., N. With M = 1, we have the single-threaded operation; with M = N we have full multi-threaded operation which uses 100% of all cores. The default test doesn't attempt M > N: it does not make sense to load cores to more than 100% as the OS will have to multitask several threads on single physical cores and the resulting task switches reduce performance (since the CPU cycles spent in OS routines are counted towards the test elapsed time, but no useful work is done in them).

Yet, being a flexible program, UnRAR-crack has a command-line option (-cpus=...) to select how many threads are to be used in the bench, so M can be freely chosen, leading to the M > N scenario. The issue there is that when M is much more than N (e.g., M ≥ 4×N), and especially on Windows XP and Windows 7, the M threads do not start simultaneously. On a N existing cores, the OS can only load up to N worker threads out of the larger set of M. After they run for some time, they are preempted, and another batch of (most likely) different, not-yet-ran N threads are loaded, etc. This process takes time; it may turn out that one or two seconds pass until all of the M threads got their chance to run at least once. The thing is that all threads report their total „working time“ from the moment they ran for the first time, until the run was completed. Thus only some of the threads would turn in the full working time, 8+ seconds, and some may report 7+, and some can even say 6+ s. This is clearly incorrect: all threads were meant to be working the full 8+s „shift“, however the OS couldn't start them so quickly and the „late starters“ skew the total spent CPU time towards lower lengths. In effect, a run that actually took more than 8 seconds would be reported to have taken six-something or 7. So the test with M > N threads seems to have taken less time than the one with M = N, however the actual work done (passwords checked) is almost the same as in the M = N scenario (since N workers actually work all the time, wasting only the time taken by task switches, which is not too dramatic). Thus you'd have slightly less amount of passwords checked in significantly less time, leading to higher reported „working time“ rates.

The problem doesn't occur every time and needs a certain amount of luck to boost the score significantly, but when it does, it is deemed a good enough official result, and a report file is written, which the website accepts and the crafted result is ranked higher than the PC deserved, leading to skewed result tables.

Remedy to the issue

  1. The website no longer accepts report files which contain M > N runs.
  2. Existing uploaded results with M > N are detected and made hidden (they aren't displayed) in tables and in the „top performers“ lists. Only a direct link to the former result can display you its stats, but there's a big red banner on the page explaining how this result is not trustworthy and a link to this page for an in-depth explanation.

Future work

A new build is in the making which would make selecting M > N from the launcher trigger a warning. The same will happen if you launch UnRAR-crack directly from the command line. And of course no result file will be generated if you choose to ignore the warning.

Credits

This issue was discovered by the hwbot community, and the news were channelled to me by Christian Ney and Victor Codin (a.k.a. GENiEBEN).



counters