Skip to content
This repository has been archived by the owner on Feb 2, 2021. It is now read-only.

SourcesOfNonDeterminism

Jump to bottom
Kevin Reid edited this page Apr 16, 2015 · 1 revision

(legacy summary: Document the sources of non-determinism in Javascript.) (legacy labels: Phase-Design)

Introduction

Almost all members of the global environment of a Cajita program are immutable. The two exceptions are new Date() and Math.random which give an otherwise isolated cajoled Cajita program ambient access to a covert channel of communication. Further, the output of a call to a function which has access to either Date or Math is not a deterministic function of the messages it receives.

A deterministic object-capability system is one in which the ability to cause side-effects and observe data that varies between executions is conveyed by explicit object references that are propogated only by explicit program statements.

Once access to the Date constructor and to Math.random() is removed from Cajita, all objects that are globally or implicitly accessible to Cajita programs are immutable. This is not sufficient to make Cajita into a deterministic object-capability system because of other sources of non-determinism which Cajita inherits from Javascript.

Sources of Non-Determinism in JavaScript

  • Enumeration order of for..in loops
  • Semantics of modifying a list that is being iterated over
  • Several aspects of the behaviour of Array.sort (stability of the sort, ordering of calls to accessors and valueOf, behaviour when the comparison function is inconsistent, and a few other edge cases -- see ES5 section 15.4.4.11)
  • Implementation-defined behaviour of base JavaScript library functions (for example, String.prototype.localeCompare; any function called with extra arguments).
  • Non-deterministic exceptions like out of memory and stack overflow are catchable
  • Non-determinism as a result of floating point operations

Sources of Non-determinism in Tamed Libraries

When taming libraries, the author of taming must be careful that the tamed code does not accidentally violate the security properties of the cajoled program using it. Determinism is a particularly easy property to violate in taming.

Sources of Non-determinism in Domita

  • Order of callbacks queued using setTimeout
  • Some information about running time of a piece of code inferable from setTimeout
  • Fetching an external resource identified by a URL is not deterministic
    • This can be addressed using a UriPolicy which caches agressively
  • Parse tree generated by setting innerHTML varies depending on the browser
Clone this wiki locally