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.
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%.
jscontest -e -tn 50 [name-of-annotated-file.js]
There is no need to understand the instrumented source code! Some of the examples make use of custom contracts, which you can have a look at by following the generator links.
- Array - Hash-table, A collection of some simple functions, where parameters where used as arrays or hash tables. 50 tests per method are executed. (annotated source code, instrumented source code)
- Singly-Linked List,
An implementation of a singly-linked list, with methods
add, item, remove, size, toArray, toString, executing 50 tests per method. (annotated source code, instrumented source code, single linked list generators)
- Binary Search Tree,
An implementation of a binary search tree, with methods
add, contains, remove. For each method 50 test cases are executed. (annotated source code, instrumented source code, binary search tree generators)
Google V8 Benchmark
The Google benchmark code is from the Google V8 Benchmark site.
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.
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.
- 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)
|0.5||07/13/2011||jscontest.0.5.0.tar.gz, jscontest.0.5.0.zip||POPL 2012 Version|
|0.4||02/09/2011||jscontest.0.4.3.tar.gz||TOOLS 2011 Version|
|0.2||06/11/2010||jscontest.0.2.5.tar.gz||TAIC 2010 Version|
|0.1||01/20/2010||jscontest.0.1.17.tar.gz||TOOLS 2010 Version|
Look at the CHANGES to see the differences between the versions.
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:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- 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.
Stefan Frank (JS Parser), Dirk Kienle (jquerry interface, delta debugging), Annette Bieniusa (transaction support, case studies), Peter Thiemann (effect inference).