Access Permission Contracts for Scripting Languages

The ideal software contract fully specifies the behavior of an operation. Often, in particular in the context of scripting languages, a full specification may be cumbersome to state and may not even be desired. In such cases, a partial specification, which describes selected aspects of the behavior, may be used to raise the confidence in an implementation of the operation to a reasonable level.

We propose a novel kind of contract for object-based languages that specifies the side effects of an operation with access permissions. An access permission contract uses sets of access paths to express read and write permissions for the properties of the objects accessible from the operation.

We specify a monitoring semantics for access permission contracts and implement this semantics in a contract system for JavaScript. We prove soundness and stability of violation under increasing aliasing for our semantics.

Applications of access permission contracts include security, enforcing modularity, test-driven development, program understanding, and regression testing. With respect to testing and understanding, we find that adding access permissions to contracts increases the effectiveness of error detection through contract monitoring by 6-13%.

Paper and Technical Report

  jscontest -e -tn 50 [name-of-annotated-file.js] 

A Heuristic Approach for Computing Effects

The effect of an operation on an object network can be described by the access paths along which the function reads or writes object properties. Abstracted to access path permissions, the effect can serve as part of the operation's documentation, augmenting a type signature or a contract for the operation. Statically determining such an effect is a challenging problem, in particular in a dynamic language which represents objects by hash tables like the current breed of scripting languages.

In this work, we propose an analysis that computes access permissions describing the effect of an operation from a set of access paths obtained by running the program. The main ingredient of the analysis is a novel heuristic to abstract a set of access paths to a concise access permission.

Our analysis is implemented as part of JSConTest, a testing framework for JavaScript. It has been applied to a range of examples with encouraging results.

pdf (TOOLS Europe 2011)

Access Permission Contracts

The ideal software contract is a full specification of the behavior of an operation. Often, in particular in the context of scripting languages, a full specification can be cumbersome to state and may not even be desired. In such cases, a partial specification, which describes select aspects of the behavior, may be used to raise the confidence in an implementation of the operation to a reasonable level.

We propose a novel style of contract for object-based languages that permits the partial specification of side effects. Specifically, our contract language attaches access permissions to functions and methods. An access permission describes the side effects of a method using sets of access paths that express read and write permissions for the properties of the objects accessible from the method. We specify a monitoring semantics for access permissions and implement this semantics as an extension of an existing contract system for JavaScript. We find that adding access permissions to contracts increases the effectiveness of error detection by contract monitoring by 6-13%.

pdf (submitted to ECOOP 2011)

JSTrans - DOM Transactions for Testing JavaScript

Unit testing in the presence of side effects requires the construction of a suitable test fixture before each test run. We consider the problem of providing test fixtures for unit testing of client-side JavaScript code that manipulates its underlying webpage. We propose using techniques from software transactional memory to cheaply restore the test fixture after each test run.

pdf presented at TAIC 2010

JSConTest - Contract-Driven Testing of JavaScript Code

JSContest is a tool that enhances JavaScript with simple, type-like contracts and provides a framework for monitoring and guided random testing of programs against these contracts at the same time. Function contracts in JSContest serve a dual role as specifications of the input/output behavior and as test case generators. Generation of test data for a contract is principally random, but can be guided by annotations on the contract to achieve higher coverage. Annotations may indicate dependencies among parameters or between parameters and the result or they may select lightweight program analyses, the results of which influence the choice of test data. A case study substantiates that JSContest finds type-related errors with high probability.

pdf (TOOLS 2010)

Examples

For the examples you have to activate JavaScript (except for the static version). These examples uses JSConTest in version 0.1.

• Fig. 1 (dynamic version) The probability of finding a counterexample for the original contract of p is about 2^(-32). (js source, compiled js)
• Fig. 1 - Analysis (@numbers) (dynamic version) Here you can see, that the analysis @numbers helps a lot by finding a counterexample for the contract of p. (js source, compiled js)
• Fig. 1 (static version) Usually the framework did not find a counterexample for the contract of p, as this static version shows.
• Fig. 2 - Diophantine equation (dynamic version) Here the framework has to solve a Diophantine equation to find a counterexample for the contract. Please notice, that the runtime of this example differs by a factor of 100 depending on which browser you use. In Google Chrome the counterexample is found in some seconds. (js source, compiled js)
• Fig. 3 - Object Access In this example normally no counterexample is found, since the probability to guess a object with a property "quest" is low. (js source, compiled js)
• Fig. 3 - Object Access - Analysis Here a counterexample is found in at most less that 5 tests. (js source, compiled js)
• Huffman Tree (dynamic version) (js source, compiled js)

Software Download

Look at the CHANGES to see the differences between the versions.

Since JSConTest evolves steadily, the source code is available now on github. There you can easily access all versions of the software under JSConTest.

License of the Software

Copyright 2010 Phillip Heidegger. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY PHILLIP HEIDEGGER ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL PHILLIP HEIDEGGER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of Phillip Heidegger.