JavaScript Tests Module

mattbasta edited this page Jul 7, 2011 · 10 revisions

Hi there! The JS tests bit here is quite a big undertaking and will probably never be 100% reliable or 100% accurate (I would be incredibly surprised if it even got above 90%). Granted, it’s better than using Regexs to do this stuff, it’s much slower, uses a lot more memory, and leaves a bad taste in the mouth of anyone that believes in purity of JavaScript.



Installing Spidermonkey can be challenging depending on what platform you’re running. Fortunately, there’s a wiki page detailing installation instructions.

Configuring the Validator

The last step (which isn’t bad at all) is to configure the validator to use the installation of Spidermonkey for its business. This is super easy.

If you used the document linked above, you’re in luck! The validator should automatically detect the installation and pick it up right away. If it does, skip the rest of this step (you’re done). The shell should be at /usr/bin/js.

If you didn’t use the doc for installation, you’ll need to know the path to your Spidermonkey or Tracemonkey shell. The shell executable should be named js. Once you’ve located the shell, create a file called that looks like the following in the validator/ folder of your validator’s installation:

from validator.constants import *
SPIDERMONKEY_INSTALLATION = "/wherever/your/binary/is/js"

If you want to take a less hands-on approach, you can also add the path to the shell to your $PATH. The validator will try to find an executable named js in all of the directories listed in $PATH, so simply setting that up will get you up and running as well, no manual configuration needed.

And that’s it!

The Problem with AST Trees

The problem with AST trees is that the nodes are not homogenous. For instance, CallExpression nodes will contain more nodes in the “callee” and “arguments” properties, while MemberExpression nodes will contain more nodes in its “object” and “property” nodes.

This problem prevents simple recursion to iterate the tree. Because the nodes are also indicative of the scope of the objects being referred to, it is also difficult to accurately target the use of prohibited objects and functions. I’ll talk about that in a second.

Traversing the trees

The method for traversing the AST tree that the validator uses boils down the a giant dict in validator.testcases.javascript.nodedefinitions that lists each node type, the potential types of node branches, and some other information about the node type. Based on this, each node may be processed with a custom chunk of code as it is encountered and all code branches and control flows are visited.

Doing something useful

In order to actually test the JS, determinations about the code that is being iterated over need to be made. In nodedefinitions, there is a value for each node type that identifies whether the object is block-level (so we can track variables created with let) and a value that identifies whether the object declares a scope. These values add a JSContext object to the top of the traverser’s context stack. When an assignment or declaration node is encountered, these contexts are populated.

Some elements, however, are not as simple to scan with this technique. Things like function declarations are especially tricky, where the declaration of the function, assignment of the function to the scope, and the content traversal happen in the same node. In order to handle this, there is a value available in nodedefinitions that allows a lambda function (or reference to a function in validator.testcases.javascript.actions) to run before the branches are executed. For this function, if there is a return value, execution of the branches is skipped. Simply returning True will skip the execution step.

Two arguments are passed to the aforementioned function. The first is a reference to the traverser object. This contains the error bundler (handy for reporting errors) and the AST node.

Lastly, there is a value in the nodedefinitions file for each node type that returns whether the node returns a value. Setting this to true will cause the _traverse_node function to return the value of the lambda function from above.

Shortcomings of an iterative detection method

While visiting every node is indeed useful, it is not entirely practical to assume that all code is procedural. More importantly, complex structures and flow devices (such as loops and conditionals) will add a degree of uncertainty to the analysis. For instance, in this code block, an iterative approach will generate one value, though it will not be correct:

var x = 4;
if(x > 4) {
    x += 3;
} else {
    x /= 2;
// Interpreted answer: x = 2
// Iterative answer: x = 3.5

The problems here become immediately apparent. There are a number of solutions, however.

State forking

Particularly with regard to conditions, a clever solution is to “fork” the state of the engine: at a conditional or other n-ary control flow, deep copy the current scope and iterate one branch with one copy of the scope and the other branch with the other copy. At the end of the structure, some sort of reconstitution of the states will need to take place, or multiple-value static analysis will need to be implemented.

var x = 4;
if(x > 4) {
    x += 3;
} else {
    x /= 2;
// Interpreted answer: x = 2
// Fork 1 answer: x = 7
// Fork 2 answer: x = 2
// Reconstituted answer: x = 7|2

In this example, the answer may either be 7 or 2. All future analyses which involve x will need to test both values. This can get even more complicated in situations where multiple variables which may have multiple possible values. E.g.:

var x = 2;
    x += 1;
    x -= 1;

var y = 3;
    y += 1;
    y -= 1;

// x = 1|3;
// y = 2|4;

var z = x * y;
// z = 2|4|6|12

Ideally, however, a more simple reconstitution can take place:

var x = 4;
if(x > 4) {
    x -= 4;
} else {
    x *= 0;
// Interpreted answer: x = 0
// Fork 1 answer: x = 0
// Fork 2 answer: x = 0
// Reconstituted answer: x = 0

Not only is this answer correct, but it means that future analyses can be simplified.

If no else block exists, the state should still be forked. After the conditional body has been evaluated, it should be reconstituted with the unchanged copy of the state. For example:

var x = 4;
if(x > 4) {
    x -= 4;
// Interpreted answer: x = 4
// Fork answer: x = 0
// "Unchanged" answer: x = 4
// Reconstituted answer: x = 0|4

Application to loops

Loops are much more difficult to deal with using state forking. Because there is a chance that the state will change with each iteration (in an infinite loop), it is impossible to fully predict the outcome.

The best way to handle loops is to perform the state fork after each iteration of the loop. The state should then be saved. If an exact version of that state has already been saved by a previous iteration of the loop, iteration of the loop can end and the fork can terminate. At this point, resolution of all of the saved states should occur.

This approach is somewhat unpractical, however, because most loops will not ever resolve to a common state between iterations (leading to an infinite number of forks).

var x = 1;
var list = foo(); // Assumed to return an array
for(var e in list) {
// It is ambiguous where this loop should stop executing.

In this case, a more careful analysis of the loop should be made. If the changes between states in iterations of the loop are made to variables not read outside of the loop, their change should not be considered.

Until a better mechanism can be devised, the iteration should end after a fixed number of iterations. This number should be sufficiently high that the test it thorough but not too high that excessive resources are consumed.


Continues should cause the state to fork from within conditionals. One fork should process the loop as if the continue had taken place. The other fork should skip the rest of the conditional node and continue processing the loop. The fork should happen such that the “normal” fork (that behaves as the JS code would) still performs the normal state fork as if the end of the loop’s block had been reached. The other other (“abnormal”) fork should do the same, however, it should also continue processing the loop separately with the alternate state that it has developed. The abnormal fork should also deal with all reconstitution that must occur with the conditional that the continue was thrown in.

var x = foo();
var a = 3, b = 4;
for(var e in x) {
    if(e == "bar")
    // The abnormal fork must reconstitute with the alternate conditional fork here.
    b *= 2;
    // The normal fork will skip to here.


Breaks should be treated exactly as continues are treated.

Evaluatory taint checking

One interesting method of performing thorough analysis is to create runnable functions from function expressions and declarations. To do this kind of analysis, all variables that are declared start out with a “dirty” value of False. This means that their value could not have been tainted. If a “clean” variable is assigned a value, it becomes dirty if the value it is assigned is dirty. The return value of a function is dirty if the variable the function is stored in is dirty or if the logic is considered dirty.

In function declarations, the arguments are assumed to be clean values. If all values that affect the return value of the function are clean, then the function’s logic is considered clean. For instance:

// Clean function
var x = 4;
var y = foo(); // foo is assumed to have dirty logic.

function clean(a, b) {
    var zap = a + x; // a and b are assumed to be clean
    return zap * 4 + b; // All literals are clean

function dirty(a, b) {
    return a + b + y;

If a function’s logic is considered clean, it’s functionality should be reproducible at any time in the interpreter. During the rest of the code analysis, that function’s AST can be re-evaluated with any arguments to produce a definite output.

Using the Python AST library, a simple function can be created (with all lexically scope values and references hardcoded in) after a function declaration has been determined to have clean logic. When that function is referenced in future JS code, it will produce an actual definite output, rather than a lazy object (like standard iterative testing would produce).