On abstract interpretation of Mobile Ambients

We introduce an abstract interpretation framework for Mobile Ambients, based on a new semantics called normal semantics. Then, we derive within this setting two analyses computing a safe approximation of the run-time topological structure of processes. Such a static information can be successfully used to establish interesting security properties.     

Deriving escape analysis by abstract interpretation

Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain as an abstract interpretation of concrete states, which we then refine into an abstract domain which is more concrete than and, hence, leads to a more precise escape analysis than . We provide optimality results for both and , in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications.     

Linguistic extension of abstract machine modelling to aid software development

The traditional use of abstract machine models is to provide a conceptual framework for software design and to aid portability and machine independence. Access to the abstract machine model from the higher-level system on which it is based provides a powerful tool for software development. This paper describes a technique in which the higher-level system is interfaced to the underlying abstract machine, thus allowing use of the higher-level system to analyse and debug its own implementation. The application of this technique in the implementation of SL5 is given as an example. Experience with the use of the facility and a discussion of basic design considerations are included.     

带口令的安全盒子环境演算

带口令的安全盒子环境演算是对原有的移动环境演算的改进，避免了移动环境演算中open操作所带来的干扰，加强了环境对其自身边界的控制能力，实现了对环境的回收。文中给出了SBAP的语法和语义定义，用SBAP对Pi-演算中的匹配算子进行了改写，并对电子邮件系统进行了描述和仿真。     

FeGC: An efficient garbage collection scheme for flash memory based storage systems

NAND flash memory is a promising storage media that provides low-power consumption, high density, high performance, and shock resistance. Due to these versatile features, NAND flash memory is anticipated to be used as storage in enterprise-scale systems as well as small embedded devices. However, unlike traditional hard disks, flash memory should perform garbage collection that consists of a series of erase operations. The erase operation is time-consuming and it usually degrades the performance of storage systems seriously. Moreover, the number of erase operations allowed to each flash memory block is limited. This paper presents a new garbage collection scheme for flash memory based storage systems that focuses on reducing garbage collection overhead, and improving the endurance of flash memory. The scheme also reduces the energy consumption of storage systems significantly. Trace-driven simulations show that the proposed scheme performs better than various existing garbage collection schemes in terms of the garbage collection time, the number of erase operations, the energy consumption, and the endurance of flash memory.     

Strongly reducing variants of the Krivine abstract machine

We present two variants of the Krivine abstract machine that reduce lambda-terms to full normal form. We give a proof of their correctness by interpreting their behaviour in the λ σ-calculus. This article is an extended version of a paper presented at the ‘Lisp and Functional Programming’ Conference in 1990 and the work was done at Ecole Normale Supérieure between 1989 and 1991.     

An efficient approach to cyclic reference counting based on a coarse-grained search

Reference counting is known to have problems working with cyclic structures. In this paper, we present an efficient approach to cyclic reference counting, consisting of two key components. The first is a coarse-grained cycle collection algorithm that essentially performs a coarser (lightweight) analysis of the computation graph and thus greatly reduces the tracing cost (in comparison with the algorithms based on trial deletion to detect cycles). Our new cycle collector relies on this algorithm to obtain efficiency. Second, a predefined backup algorithm is incorporated to eliminate a theoretical problem that appears in the coarse-grained algorithm, thereby making the collector more practical. In this regard, we develop a heuristic based on the runtime behavior of the cycle collection to help the collector determine when to trigger the backup one. We have implemented and evaluated the proposed cycle collector on the Jikes RVM, where the SPECjvm98 benchmarks were applied. The results demonstrate that the novel approach is efficient and practical, compared to a modern cycle collector based on trial deletion.     

An algorithm for generating abstract syntax trees

In this paper, we discuss the notion of an abstract syntax. An algorithm is presented for automatically deriving an abstract syntax directly from a BNF grammar. The implementation of this algorithm and its application to the grammar for Modula are discussed.     

An abstract interpretation toolkit for μCRL

This paper describes a toolkit that assists in the task of generating abstract approximations of process algebraic specifications written in the language μCRL. Abstractions are represented by Modal Labelled Transition Systems, which are mixed transition systems with may and must modalities. The approach permits to infer the satisfaction or refutation of safety and liveness properties expressed in the (action-based) μ-calculus. The tool supports the abstraction of states and action labels, which allows to deal with infinitely branching systems.     

在嵌入式DSP系统实现的一种Java垃圾收集器

列举了垃圾收集的三种经典算法,并结合实际项目,详细阐述了基于DSP平台的垃圾收集器的一种实现.     

Pentagons: A weakly relational abstract domain for the efficient validation of array accesses

We introduce Pentagons (), a weakly relational numerical abstract domain useful for the validation of array accesses in byte-code and intermediate languages (IL). This abstract domain captures properties of the form of . It is more precise than the well known Interval domain, but it is less precise than the Octagon domain.The goal of is to be a lightweight numerical domain useful for adaptive static analysis, where is used to quickly prove the safety of most array accesses, restricting the use of more precise (but also more expensive) domains to only a small fraction of the code.We implemented the abstract domain in , a generic abstract interpreter for.NET assemblies. Using it, we were able to validate 83% of array accesses in the core runtime library in a little bit more than 3 minutes.     

Matching Systems for Concurrent Calculi

Matching systems were introduced by Carbone and Maffeis, and used to investigate the expressiveness of the pi-calculus with polyadic synchronisation. We adapt their definition and investigate matching systems for CCS, the pi-calculus and Mobile Ambients. We show among other results that the asynchronous pi-calculus with matching cannot be encoded (under certain conditions) in CCS with polyadic synchronisation of all finite levels.     

一个抽象机库中B方法的研究

B方法是支持规格说明到软件设计和执行的形式化方法。文章研究了B方法中一种抽象机库的实现模型和生成代码,对该方法的特点进行评述。验证了B的正确可靠的实现方法,充分利用B方法的精化原则,提高了B形式化方法的开发验证效率。     

An efficient augmented Lagrangian method for support vector machine

ABSTRACT

Support vector machine (SVM) has proved to be a successful approach for machine learning. Two typical SVM models are the L1-loss model for support vector classification (SVC) and ε-L1-loss model for support vector regression (SVR). Due to the non-smoothness of the L1-loss function in the two models, most of the traditional approaches focus on solving the dual problem. In this paper, we propose an augmented Lagrangian method for the L1-loss model, which is designed to solve the primal problem. By tackling the non-smooth term in the model with Moreau–Yosida regularization and the proximal operator, the subproblem in augmented Lagrangian method reduces to a non-smooth linear system, which can be solved via the quadratically convergent semismooth Newton's method. Moreover, the high computational cost in semismooth Newton's method can be significantly reduced by exploring the sparse structure in the generalized Jacobian. Numerical results on various datasets in LIBLINEAR show that the proposed method is competitive with the most popular solvers in both speed and accuracy.     

An efficient weighted Lagrangian twin support vector machine for imbalanced data classification

In this paper, we propose an efficient weighted Lagrangian twin support vector machine (WLTSVM) for the imbalanced data classification based on using different training points for constructing the two proximal hyperplanes. The main contributions of our WLTSVM are: (1) a graph based under-sampling strategy is introduced to keep the proximity information, which is robustness to outliers, (2) the weight biases are embedded in the Lagrangian TWSVM formulations, which overcomes the bias phenomenon in the original TWSVM for the imbalanced data classification, (3) the convergence of the training procedure of Lagrangian functions is proven and (4) it is tested and compared with some other TWSVMs on synthetic and real datasets to show its feasibility and efficiency for the imbalanced data classification.     

An abstract programming language and correctness proofs

The realization of an abstract programming language is a good approach for automating the software production process and facilitating the correctness proof of a software system.

This paper introduces a formal language for programming at the abstract level by combining Pascal with VDM (Vienna Development Method). The notation provided by the language obliges programmers to consider the correctness of programs throughout the whole process of programming, and the proof axiom and rules presented in this paper may be used to prove the correctness of programs. A complete example is given to illustrate how to program using APL and how to prove the correctness of programs using the given axiom and rules.     

An abstract machine theory for formal language parsers

Summary The usual data necessary for any abstract machine theory is given in categorical terminology. In these terms, an abstract machine theory for formal language parsers is developed, exposing the essential nature of any left-to-right parsing scheme. A weak classification of all parsers for a given language is developed and the usual notions of initial machine, reachable machine and minimal machine apply. Minimality is an extremely weak notion in this theory, although it is equivalent to a simple form of immediate error detection for parsers. Remarks on the construction of parsing procedures are given.Research supported in part by grant GJ-1171 from the National Science Foundation.     

Using bisimulation proof techniques for the analysis of distributed abstract machines

We illustrate the use of recently developed proof techniques for weak bisimulation by analysing a generic framework for the definition of distributed abstract machines based on a message-passing implementation. We first define this framework, and then focus on the algorithm which is used to route messages asynchronously to their destination.A first version of this algorithm can be analysed using the standard bisimulation up to expansion proof technique. We show that in a second, optimised version, rather complex behaviours appear, for which more sophisticated techniques, relying on termination arguments, are necessary to establish behavioural equivalence.     

An incremental garbage collection algorithm for multi-mutator systems

An elementary correctness proof for Ben-Ari's algorithm (1984) for incremental garbage collection is given. We give a new algorithm for systems in which there are multiple mutators and a proof of its correctness, which is a minor modification of the previous proof. Finally, we remark upon a way to implement these algorithms that may increase their performance on certain architectures. Carl Pixley holds B.S., M.S. and Ph.D. degrees in mathematics from the University of Omaha, Rutgers-The State University, and the State University of New York at Binghamton, respectively. His principal contributions are the Pixley-Roy construction of set-theoretic topology, a example in the selection theory of infinite-dimensional spaces, a decomposition theorem (with W. Eaton) in geometric topology, and the design and implementation of demanddriven arithmetic in a functional programming language. He is now a member of the technical staff of the VLSI Computer Aided Design Program of Microelectronics and Computer Technology Corporation (MCC) in Austin Texas, where he is investigating mathematical methods in the verification of hardware.