Static analysis of JavaScript libraries in a scalable and precise way using loop sensitivity

Statically analyzing JavaScript applications often requires an analysis of JavaScript libraries because many JavaScript applications use libraries. However, static analysis techniques for JavaScript are not yet ready for analyzing libraries in a scalable and precise manner. Simply loading JavaScript libraries uses various dynamic features of JavaScript, which cause static analyzers to suffer from mutually intermingled problems of scalability and imprecision. In this paper, we present a loop‐sensitive analysis (LSA) technique, which can improve the analysis scalability when analyzing JavaScript libraries by enhancing the analysis precision of loops. The LSA technique distinguishes loop iterations when loop conditions can be determined to be either true or false precisely. We formalize LSA in the abstract interpretation framework in the presence of tricky language features such as exceptions and prove its soundness and precision theorems using Coq. We evaluate our LSA implementation with the analysis results of programs that use 5 JavaScript libraries and show that LSA significantly improves the analysis scalability and precision of an existing JavaScript static analyzer when analyzing JavaScript libraries. In addition, using the configurability of LSA, we experimentally show the correlation between scalability and precision in the analysis of JavaScript libraries. We found that even the analysis of simple programs that just load jQuery, which is the most popular JavaScript library, in a scalable way requires distinguishing not only the last 4 functions being called but also 40 iterations in each loop with 2‐level nested loops at least. Both the mechanization and implementation of LSA are publicly available.     

Empirical study of the dynamic behavior of JavaScript objects

Despite the popularity of JavaScript for client‐side web applications, there is a lack of effective software tools supporting JavaScript development and testing. The dynamic characteristics of JavaScript pose software engineering challenges such as program understanding and security. One important feature of JavaScript is that its objects support flexible mechanisms such as property changes at runtime and prototype‐based inheritance, making it difficult to reason about object behavior. We have performed an empirical study on real JavaScript applications to understand the dynamic behavior of JavaScript objects. We present metrics to measure behavior of JavaScript objects during execution (e.g., operations associated with an object, object size, and property type changes). We also investigated the behavioral patterns of observed objects to understand the coding or user interaction practices in JavaScript software. Copyright © 2015 John Wiley & Sons, Ltd.     

Active Oberon for .NET: An Exercise in Object Model Mapping

Active Oberon is a substantial evolution of the programming language Oberon. It distinguishes itself by a novel object model and by its integration into the .NET language interoperability framework.The three concepts characterizing Active Oberon are: (a) active object types, (b) a single and unifying notion of abstraction called definition, and (c) a static module construct. These concepts are in fact powerful combinations of concepts: Active objects integrate active behavior with reactive message handling, definitions unify the units of usage, implementation and inheritance, and modules represent both package and static object. The rigid concept of class hierarchy has been sacrificed in Active Oberon to a more flexible concept of aggregation that is based on a generalized IMPLEMENTS relation. The relations IMPORTS and REFINES are used to specify static module dependencies and to derive new definitions from existing ones respectively.This article is a report on a work in progress. We divide our presentation into three parts: (a) A short recall of the history of programming languages developed at the ETH, (b) an extensive conceptual overview of Active Oberon's object model called the Active Object System (AOS), (c) a discussion of the mapping of the AOS into the Common Type System (CTS) exposed by .NET.     

Type Theory and Language Constructs for Objects with States

In current class-based Object-Oriented Programming Languages (OOPLs), object types include only static features. How to add object dynamic behaviors modeled by Harel's statecharts into object types is a challenging task. We propose adding states and state transitions, which are largely unstated in object type theory, into object type definitions and typing rules. We argue that dynamic behaviors of objects should be part of object type definitions. We propose our type theory, the τ-calculus, which refines Abadi and Cardelli's ζ-calculus, in modeling objects with their dynamic behaviors. In our proposed type theory, we also explain that a subtyping relation between object types should imply the inclusion of their dynamic behaviors. By adding states and state transitions into object types, we propose modifying programming language constructs for state tracking.     

Integrated implementation of dynamic untyped object‐based operator overloading

Operator overloading, a popular mechanism in the C++ language, is a form of ad hoc polymorphism on operator functions, allowing alternative implementations for different argument types. Classless languages with untyped objects are languages that lack classes and treat all objects as compliant to a common Object type. Languages in this category are flexible, dynamic, and easy‐to‐use, with popular examples being JavaScript, Lua, and ActionScript (the latter being hybrid by also offering classes). This paper presents an integrated implementation of untyped operator overloading which enable users to handle dynamically the full range of operators on objects. The focus is on features not supported by other languages, such as (i) arithmetic and relational operators allowing to separately handle caller lhs and rhs positions; (ii) an assignment operator with an untyped analogy of type casting; (iii) a slot access operator allowing user‐defined policies for editing object slots; and (iv) a function‐call operator to support functors. Operators are treated as first‐class object slots, distinguished by reserved indices that match the respective operator lexemes. All reported techniques have been applied in implementing the operator overloading features of the Delta language. Copyright © 2010 John Wiley & Sons, Ltd.     

MiniMAO1 : An imperative core language for studying aspect-oriented reasoning

This paper describes MiniMAO₁, a core aspect-oriented language. Unlike previous aspect-oriented calculi and core languages, MiniMAO₁allows around advice to change the target object of an advised operation before proceeding. MiniMAO₁accurately models the ways AspectJ allows changing the target object, e.g., at call join points. Practical uses for changing the target object using advice include proxies and other wrapper objects.MiniMAO₁was designed to serve as a core language for studying modular specification and verification in the aspect-oriented paradigm. To this end MiniMAO₁

• •has an imperative, reference-based semantics,
• •models the control-flow effects of changing target object bindings with advice, and
• •has a safe static type system.

The first two features make MiniMAO₁ suitable for the study of aspect-oriented mechanisms, such as those found in AspectJ. These features are important for studying the interaction of aspect-oriented language features with modular specification and verification. A statically type-safe language is also important for such research. AspectJ does not have a safe static type system. To achieve static type safety MiniMAO₁uses a slightly different form of proceed and advice binding than in AspectJ. These changes are sufficient for static type safety, but we do not claim that they are necessary; a less restrictive type system might suffice.This paper gives an operational semantics, type system, and proof of soundness for MiniMAO₁.     

Weakly sensitive analysis for JavaScript object-manipulating programs

While JavaScript programs have become pervasive in web applications, they remain hard to reason about. In this context, most static analyses for JavaScript programs require precise call graph information, since the presence of large numbers of spurious callees significantly deteriorates precision. One of the most challenging JavaScript features that complicate the inference of precise static call graph information is read/write accesses to object fields, the names of which are computed at runtime. JavaScript framework libraries often exploit this facility to build objects from other objects, as a way to simulate sophisticated high-level programming constructions. Such code patterns are difficult to analyze precisely, due to weak updates and limitations of unrolling techniques. In this paper, we observe that precise field origination relations can be inferred by locally reasoning about object copies, both regarding to the object and to the program structure, and we propose an abstraction that allows to separately reason about field read/write access patterns working on different fields and to carefully handle the sets of JavaScript object fields. We formalize and implement an analysis based on this technique. We evaluate the performance and precision of the analysis on the computation of call graph information for examples from jQuery tutorials.     

A robust object category detection system using deformable shapes

An object can often be uniquely identified by its shape, which is usually fairly invariant. However, when the search is for a type of object or an object category, there can be variations in object deformation (i.e. variations in body shapes) and articulation (i.e. joint movement by limbs) that complicate their detection. We present a system that can account for this articulation variation to improve the robustness of its object detection by using deformable shapes as its main search criteria. However, existing search techniques based on deformable shapes suffer from slow search times and poor best matches when images are cluttered and the search is not initialised. To overcome these drawbacks, our object detection system uses flexible shape templates that are augmented by salient object features and user-defined heuristics. Our approach reduces computation time by prioritising the search around these salient features and uses the template heuristics to find truer positive matches.

Signatures: A language extension for improving type abstraction and subtype polymorphism in C++

C++ uses inheritance as a substitute for subtype polymorphism. We give examples where this makes the type system too inflexible. We then describe a conservative language extension that allows a programmer to define an abstract type hierarchy independent of any implementation hierarchies, to retroactively abstract over an implementation, and to decouple subtyping from inheritance. This extension gives the user more of the flexibility of dynamic typing while retaining the efficiency and security of static typing. With default implementations and views flexible mechanisms are provided for implementing an abstract type by different concrete class types. We first show how the language extension can be implemented in a preprocessor to a C++ compiler, and then detail and analyse the efficiency of an implementation we directly incorporated in the GNU C++ compiler.     

Can Addresses be Types?: A case study: objects with delegation

We adapt the aliasing constraints approach for designing a flexible typing of evolving objects. Types are singleton types (addresses of objects, as a matter of fact) whose relevance is mainly due to the sort of safety property they guarantee. In particular we provide a type system for an imperative object based calculus with delegation and which supports method and delegate overriding, addition, and removal.     

Static use-based object confinement

The confinement of object references is a significant security concern for modern programming languages. We define a language that serves as a uniform model for a variety of confined object reference systems. A use-based approach to confinement is adopted, which we argue is more expressive than previous communication-based approaches. We then develop a readable, expressive type system for static analysis of the language, along with a type safety result demonstrating that run-time checks can be eliminated. The language and type system thus serve as a reliable, declarative, and efficient foundation for secure capability-based programming and object confinement .     

H∞ feedback‐control theory in biochemical systems

In this paper we study the possible optimality of biochemical pathways in the H_∞ sense. We start by presenting simple linearized models of single enzymatic reaction systems, where we apply classical and modern tools of feedback‐control theory. We then apply the results obtained by our analysis to a linearly unbranched enzyme pathway system, where we explore the effect of a negative feedback loop internally exerted on the system by a self‐product of the pathway. We then probe the sensitivity of the enzymatic system to variations in certain variables and we deal with the problem of assessing the optimality of the static‐output feedback control, in the H_∞ sense, inherent to the closed‐loop system. In this point we demonstrate the applicability of our results via a theoretical example that provides an open‐loop and closed‐loop analysis of a four‐block enzymatic system. We then apply the various tools we developed to the optimal analysis of the Threonine synthesis pathway which is regulated by three feedback loops. We demonstrate that this pathway is optimal in the H_∞ sense, in the face of considerable uncertainties in the various enzyme concentrations of the pathway. Copyright © 2007 John Wiley & Sons, Ltd.     

H ∞ filter design for continuous-time systems with quantised signals

This article studies the quantised H _∞ filtering problem for continuous-time systems with a type of dynamic quantisers, which are conjuncted with static quantisers via dynamic scalings. The static quantiser ranges are fully considered here for practical transmission channels requirements. A quantised H _∞ filter design strategy is proposed, where a convex optimisation method is developed to minimise static quantiser ranges. The resulting design guarantees that the quantised augmented system is asymptotically stable and with a prescribed H _∞ performance bound. The effectiveness of the proposed filter design method is demonstrated by a numerical example.     

Robust H∞ controller design for dynamic consensus networks

This paper studies an H_∞ suboptimal control problems of consensus networks whereby the weights of network edges are no longer static gains, but instead are dynamic systems, leading to the notion of dynamic consensus networks. We apply model, orthogonal and diagonal transformations to a dynamic consensus network in order to reduce the overall system into N ? 1 independent subsystems. We then establish a generalised methodology for designing a controller for a dynamic consensus network in the presence of external disturbances, focusing especially on using decentralised controllers that achieve consensus in the absence of disturbances and attenuation of disturbances to a prescribed H_∞ performance level. A design example is given to illustrate our results.     

Accurately Selecting Block Size at Runtime in Pipelined Parallel Programs

Loops that contain cross-processor data dependencies, known as DOACROSS loops, are often found in scientific programs. Efficiently parallelizing such loops is important yet nontrivial. One useful parallelization technique for DOACROSS loops is pipelining, where each processor (node) performs its computation in blocks; after each, it sends data to the next node in the pipeline. The amount of computation before sending a message is called the block size; its choice, although difficult to make statically, is important for efficient execution. This paper describes a flexible runtime approach to choosing the block size. Rather than rely on static estimation of workload, our system takes measurements during the first two iterations of a program and then uses the results to build an execution model and choose an appropriate block size which, unlike a static choice, may be nonuniform. To increase accuracy of the chosen block size, our execution model takes intra- and inter-node performance into account. It is important to note that our system finds an effective block size automatically, without experimentation that is necessary when using a statically chosen block size. Performance on a network of workstations shows that programs that use our runtime analysis outperform those that use static block sizes by as much as 18% when the workload is unbalanced. When the workload is balanced, competitive performance is achieved as long as the initial overhead is sufficiently amortized.     

Fast connected-component labelling in three-dimensional binary images based on iterative recursion

We propose two new methods to label connected components based on iterative recursion: one directly labels an original binary image while the other labels the boundary voxels followed by one-pass labelling of non-boundary object voxels. The novelty of the proposed methods is a fast labelling of large datasets without stack overflow and a flexible trade-off between speed and memory. For each iterative recursion: (1) the original volume is scanned in the raster order and an initially unlabelled object voxel v is selected, (2) a sub-volume with a user-defined size is formed around the selected voxel v, (3) within this sub-volume all object voxels 26-connected to v are labelled using iterations; and (4) subsequent iterative recursions are initiated from those border object voxels of the sub-volume that are 26-connected to v. Our experiments show that the time-memory trade-off is that the decrease in the execution time by one-third requires the increase in memory size by 3 orders. This trade-off is controlled by the user by changing the size of the sub-volume. Experiments on large three-dimensional brain phantom datasets (362 × 432 × 362 voxels of 56 MB (megabytes)) show that the proposed methods are three times faster on the average (with the maximum speedup of 10) than the existing iterative methods based on label equivalences with less than 1 MB memory consumption. Moreover, our algorithms are applicable to any dimensional data and are less dependant on the geometric complexity of connected components.     

Language-Based Caching of Dynamically Generated HTML

Increasingly, HTML documents are dynamically generated by interactive Web services. To ensure that the client is presented with the newest versions of such documents it is customary to disable client caching causing a seemingly inevitable performance penalty. In the system, dynamic HTML documents are composed of higher-order templates that are plugged together to construct complete documents. We show how to exploit this feature to provide an automatic fine-grained caching of document templates, based on the service source code. A service transmits not the full HTML document but instead a compact JavaScript recipe for a client-side construction of the document based on a static collection of fragments that can be cached by the browser in the usual manner. We compare our approach with related techniques and demonstrate on a number of realistic benchmarks that the size of the transmitted data and the latency may be reduced significantly.     

Fuzzy orderings in flexible query answering systems

This paper describes the benefits of using fuzzy orderings in flexible query answering systems. We provide a brief overview of those results from the theory of fuzzy orderings that are necessary to couple fuzzy orderings with flexible querying in a meaningful synergistic way. As one case study, we discuss a simple and pragmatic variant of a flexible query answering system – the so-called Vague query system (VQS). The integration of fuzzy orderings into that system is provided in full detail along with examples.This work was supported by the K_plus Competence Center Program which is funded by the Austrian Government, the Province of Upper Austria, and the Chamber of Commerce of Upper Austria.     

稀疏表示的Lucas-Kanade目标跟踪

提出一种新的目标跟踪算法,将稀疏表示应用于LK(Lucas-Kanade)图像配准框架.通过最小化校准误差的L1范数来求解目标的状态参数,从而实现对目标的准确跟踪.对目标同时建立两个外观模型:动态字典和静态模板,其中动态模型由动态字典的稀疏表示来描述目标外观.为了解决由于动态字典不断更新造成的跟踪漂移问题,一个两阶段迭代机制被采用.两个阶段所采用的目标模型分别为动态字典和静态模板.大量的实验结果表明,本文算法能有效应对外观变化、局部遮挡、光照变化等挑战,同时具有较好的实时性.