TimeZone GetNextTransition / GetPreviousTransition for far-future and far-past dates

[justingrant]

The current implementation of TimeZone's GetNextTransition / GetPreviousTransition methods behave poorly for very large or very small inputs, including possible denial-of-service issues caused by O(1) loops of expensive code.

Examples:

// Repro 1: far-future date, get previous transition
Temporal.TimeZone.from('Etc/GMT+10').getPreviousTransition(new Temporal.Instant(0n).add({hours: 24 * 1e8}));
  // expected: ???
  // actual: runs for a loooooooong time, probably over an hour (denial of service attack?) then will return null

// Repro 2: far-past date, get next transition
Temporal.TimeZone.from('Etc/GMT+10').getNextTransition(new Temporal.Instant(0n).add({hours: -24 * (1e8-1)}));
  // expected: ???
  // actual: runs for a loooooooong time, probably over an hour (denial of service attack?) then will return null

// Repro 3: future date in year 3021, get next transition
Temporal.TimeZone.from('Etc/GMT+10').getNextTransition(new Temporal.Instant(0n).add({hours: 24 * 365 * 1000}));
  // expected: ???
  // actual: null

There are a few issues here:

1. Can we prevent a denial-of-service attack caused by this expensive, O(1) loop?
2. DST looking forward more than a few decades in the future seems inherently unreliable, and certainly not worth exposing the user's computer to a DoS opportunity.

Should we simply limit future dates to N years in the future (N = 100? N = 50? N = 20?), and throw a RangeError for anything past that?

BTW, we already limit the problem for too-small dates (There was no DST before 1847 C.E.) when calling GetPreviousTransition. We should use the same smarts in GetNextTransition to avoid Repro #2 above.

[ptomato]

Should we simply limit future dates to N years in the future (N = 100? N = 50? N = 20?), and throw a RangeError for anything past that?

Do you mean in this polyfill with this particular implementation of time zones, or in the proposal?

I think the former is reasonable to do, in order to avoid DoS or just avoid terrible performance, for that matter.

Note that @pipobscure wanted to make the time zone implementation in this polyfill pluggable at some point, so it's possible that people wouldn't generally use this inefficient time zone backend.

In tc39/proposal-temporal#1370 I also made a proof of concept of loading the time zone data directly from the Olson data which performs much better than this loop.

[gibson042]

A "galloping" search could get this to something like O((log N)²). For example, exhaustively search for three years from the starting point, and if no transition is found then multiply the duration of each successive jump by the golden ratio (which should effectively sample subsequent years, cf. https://martin.ankerl.com/2009/12/09/how-to-create-random-colors-programmatically/#golden-ratio ). If a transition is encountered then repeat within the jump that found it, otherwise there is high confidence that no such transition exists.

[justingrant]

Do you mean in this polyfill with this particular implementation of time zones, or in the proposal?

I mean polyfills. A native implementation should be designed with direct access to the underlying TZDB data, so there's no need for expensive iteration to handle this case. (Unless I'm missing something obvious.)

A "galloping" search could get this to something like O((log N)²).

@gibson042 Galloping search PRs are always welcome! 😄

🏇 🐴

[justingrant]

Meeting 2021-10-29: There's no silver bullet here without having access to the TZDB data, which would add a lot of bloat to the bundle size for client use. Consensus in the meeting was that we should deviate from the spec to prevent polyfill methods from taking an unreasonable amount of time.

Thinking about the problem after the meeting, my suggestion is to do something like this:

• If a far-past date passed to GetNextTransition, fast-forward to the first possible date of an offset change (1847 CE) before starting the algorithm.
• If a far-future date is passed to GetNextTransition or GetPreviousTransition, then throw because:
  • a) it can take minutes or hours to get an answer
  • b) who knows if DST will still exist in a far-future time.
• Maybe define "far future" as 2100+ CE? (If it's still really slow, then maybe move it back, e.g. to 2040 or 2050.)