Mutation systems

We propose mutation systems as a model of the evolution of a string subject to the effects of mutations and a fitness function. One fundamental question about such a system is whether knowing the rules for mutations and fitness, we can predict whether it is possible for one string to evolve into another. To explore this issue, we define a specific kind of mutation system with point mutations and a fitness function based on conserved strongly k-testable string patterns. We show that for any k greater than 1, such systems can simulate computation by both finite state machines (FSMs) and asynchronous cellular automata. The cellular automaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyse the efficiency of the FSM simulation assuming random point mutations.     

A hybrid channel allocation algorithm with priority to handoff calls in mobile cellular networks

This paper proposes and investigates a novel analytical model of a hybrid channel allocation algorithm within wireless cellular networks. Each cell of the network consists of a predesigned fixed number of channels and the network may approve the request for extra channels for both new and handoff calls if all predesigned channels are occupied. This approval depends on the types of new and handoff calls, as well as the number of approved additional channels in the cell. If a request is denied for the arriving new call, this call will be blocked and cleared from the system. However, if a request is denied for an arriving handoff call, this call will not be blocked immediately but rather put on hold in a buffer with finite space. The implication behind this is to give priority to handoff calls. For this proposed hybrid channel allocation scheme, we first obtain the stationary distribution of each cell when there are i calls connecting to the system and j calls holding on in the buffer. We then derive new and handoff call blocking probabilities, the average number of borrowed channels, and the average delay period of handoff calls. The numerical results show that the proposed hybrid algorithm is more efficient than other approaches, specifically, in comparison with methods without a borrowing capability for new calls and those without a reserved buffer priority for handoff calls. The idea and results presented in this paper are expected to provide guidelines for field data processing within current wireless and mobile network design and performance evaluation.     

A method for detecting obfuscated calls in malicious binaries

Information about calls to the operating system (or kernel libraries) made by a binary executable may be used to determine whether the binary is malicious. Being aware of this approach, malicious programmers hide this information by making such calls without using the call instruction. For instance, the call addr instruction may be replaced by two push instructions and a ret instruction, the first push pushes the address of instruction after the ret instruction, and the second push pushes the address addr. The code may be further obfuscated by spreading the three instructions and by splitting each instruction into multiple instructions. This work presents a method to statically detect obfuscated calls in binary code. The idea is to use abstract interpretation to detect where the normal call-ret convention is violated. These violations can be detected by what is called an abstract stack graph. An abstract stack graph is a concise representation of all potential abstract stacks at every point in a program. An abstract stack is used to associate each element in the stack to the instruction that pushes the element. An algorithm for constructing the abstract stack graph is also presented. Methods for using the abstract stack graph are shown to detect eight different obfuscations. The technique is demonstrated by implementing a prototype tool called DOC (detector for obfuscated calls).     

Finite-time annular domain stability of Itô stochastic impulsive systems with markovian jumping under asynchronous switching

ABSTRACT

This study examines the finite time annular domain stability (FTADS) and stabilisation of a class of Itô stochastic impulsive systems with asynchronous switching controller. The asynchronous switching means that the controller switching does not accurately coincide with system switching in delayed time interval. The design of the controller depends on the observed jumping parameters, which cannot be precisely measured in real-time because of switching delay. Our results apply to cases where some subsystems of the switched systems are not necessarily stable under the influence of input delay. When the subsystem is stable in the synchronous switching interval and unstable in the asynchronous case, a compromise among the average impulsive interval, the upper bound of delay, and the decay/increasing rate of Lyapunov function in the synchronous/asynchronous switching interval respectively is given. By the mode-dependent parameter approach (MDPA) and allowing the increase of the impulses on all the switching times, the extended FTADS criteria for Itô stochastic impulsive systems in generally nonlinear setting are derived first. Then, we focus on the case when the system in both synchronous and asynchronous switching intervals are unstable. By reaching a tradeoff among average impulsive interval, the upper bound of delay, the magnitude of impulses and the difference between the increasing rate of Lyapunov function in the synchronous and asynchronous switching interval, new sufficient conditions for existence of the state feedback controller are also developed by MDPA. In addition, we consider the effect of different impulsive strengths (harmful and beneficial impulses) and obtained less conservative results because the Lyapunov function may be non-decreasing during switching interval. Moreover, we extend the conclusion from nonlinear stochastic impulsive switching systems to linear case. Finally, we present two examples to illustrate the effectiveness of the results obtained in this study.     

Optimizing the stack size of recursive functions

For memory constrained environments, optimization for program size is often as important as, if not more important than, optimization for execution speed. Commonly, compilers try to reduce the code segment but neglect the stack segment, although the stack can significantly grow during the execution of recursive functions because a separate activation record is required for each recursive call.If a formal parameter or local variable is dead at all recursive calls, then it can be declared global so that only one instance exists independent of the recursion depth. We found that in 70% of our benchmark functions, it is possible to reduce the stack size by declaring formal parameters and local variables global. Often, live ranges of formal parameters and local variables can be split at recursive calls through program transformations. These splitting transformations allowed us to further optimize the stack size of all our benchmark functions. If all formal parameters and local variables can be declared global, then such functions may be transformable into iterations. This was possible for all such benchmark functions.     

Issues in distributed timed model checking

In this work we present Zeus, a distributed timed model checker that evolves from the TCTL model checker Kronos [13] and that currently can handle backwards computation of reachability properties [2] over timed automata [3].Zeus was developed following a software architecture-centric approach. Its conceptual architecture was conceived to be sufficiently modular to house several features such as a priori graph partitioning, synchronous and asynchronous computation, communication piggybacking, delayed messaging, and dead-time utilization.Surprisingly enough, early experiments pinpointed the difficulties of getting speedups using asynchronous versions and showed interesting results on the synchronous counterpart, although being intuitively less attractive.     

On the automaticity of singular Artin monoids of finite type

Automaticity is an important concept in group theory as it yields an efficient solution to the word problem and provides other possibilities for effective computation. The concept of automaticity generalizes naturally from groups to monoids and semigroups and the efficiency of the solution of the word problem is preserved when we do this. Whilst this subject has been studied extensively (in both the group and the monoid/semigroup case), there are still some deep and major open problems, including questions concerning the automaticity of certain naturally occurring classes of groups, monoids and semigroups. In this paper, we consider two such classes of monoids, namely the positive singular Artin monoids of finite type and the singular Artin monoids of the finite type. The main purpose here is to show that these monoids are all automatic. When establishing the automaticity of monoids, one obstacle is that we often have asynchronous finite automata recognizing multiplication and we need to establish the existence of synchronous machines accomplishing the same task. Building on the work of Frougny and Sakarovitch, we establish a new criterion for achieving such a transition; this is fundamental in the establishment of the automaticity of the monoids we consider here and may well apply to other naturally occurring classes of monoids and semigroups as well.     

Reactive Modules

We present a formal model for concurrent systems. The model represents synchronous and asynchronous components in a uniform framework that supports compositional (assume-guarantee) and hierarchical (stepwise-refinement) design and verification. While synchronous models are based on a notion of atomic computation step, and asynchronous models remove that notion by introducing stuttering, our model is based on a flexible notion of what constitutes a computation step: by applying an abstraction operator to a system, arbitrarily many consecutive steps can be collapsed into a single step. The abstraction operator, which may turn an asynchronous system into a synchronous one, allows us to describe systems at various levels of temporal detail. For describing systems at various levels of spatial detail, we use a hiding operator that may turn a synchronous system into an asynchronous one. We illustrate the model with diverse examples from synchronous circuits, asynchronous shared-memory programs, and synchronous message-passing protocols.     

Contribution-based call stack abstraction for call string based pointer analysis

Context

Different method calls may have different contributions to the precision of the final application when abstracted into the call strings. The existing call string based pointer analysis algorithms do not consider such contribution difference and hence may not achieve best cost-effectiveness.

Objective

To be more cost-effective, we try to leverage the contribution information of each method call in call string based pointer analysis.

Method

The paper firstly proposes a contribution-based call stack abstraction method which abstracts the call stacks into call strings with the contribution information under consideration. Then, we apply the new call stack abstraction method to the pointer analysis of AspectJ programs and propose a concern-sensitive points-to analysis method. Besides, the new abstraction method is also applied to multi-threaded Java programs and results in a thread-sensitive pointer analysis method.

Results

The experimental results show that the two pointer analysis methods with contribution-based call stack abstraction can be more cost-effective than the ordinary call string based approaches for an application that detects harmful advices and an application that detects inter-thread data flow.

Conclusion

These pointer analysis methods more concretely and more clearly show that the contribution-based call stack abstraction can lead to better cost-effectiveness for the given applications.     

基于回调函数和VML的数据实时显示在Web中的应用

应用.NET的回调函数实现客户端脚本函数和服务器端异步调用,Web页不需要刷新整个页面,这样可以维护客户端的状态信息,并可实时显示服务器端处理的数据。客户端JavaScript脚本函数向服务器发送请求,服务器端处理请求,并返回处理结果。根据回传的数据结果使用VML语言可在浏览器上绘制丰富的的数据图表。本文阐述回调函数的调用机理和VML语言在客户端的绘图过程,并通过详细实例分析其实现过程。     

Numerical method for the analysis of queuing models with priority jumps1

An algorithmic approach to study queuing models with common finite and infinite buffer and jump priorities is developed. It is assumed that upon arrival of a low-priority call, one call of such kind can be transferred with some probability to the end of the queue of high-priority calls. The transition probability depends on the state of the queue of heterogeneous calls. The algorithms are proposed to calculate the quality of service metrics of such queuing models.     

A simple and fast asynchronous consensus protocol based on a weak failure detector

Summary. The Consensus problem is a fundamental paradigm for fault-tolerant asynchronous systems. It abstracts a family of problems known as Agreement (or Coordination) problems. Any solution to consensus can serve as a basic building block for solving such problems (e.g., atomic commitment or atomic broadcast). Solving consensus in an asynchronous system is not a trivial task: it has been proven (1985) by Fischer, Lynch and Paterson that there is no deterministic solution in asynchronous systems which are subject to even a single crash failure. To circumvent this impossibility result, Chandra and Toueg have introduced the concept of unreliable failure detectors (1991), and have studied how these failure detectors can be used to solve consensus in asynchronous systems with crash failures. This paper presents a new consensus protocol that uses a failure detector of the class . Like previous protocols, it is based on the rotating coordinator paradigm and proceeds in asynchronous rounds. Simplicity and efficiency are the main characteristics of this protocol. From a performance point of view, the protocol is particularly efficient when, whether failures occur or not, the underlying failure detector makes no mistake (a common case in practice). From a design point of view, the protocol is based on the combination of three simple mechanisms: a voting mechanism, a small finite state automaton which manages the behavior of each process, and the possibility for a process to change its mind during a round. Received: August 1997 / Accepted: March 1999     

Measurement and modeling of paging channel overloads on a cellular network

IP and cellular networks used to be isolated from each other. In recent decade however, the two networks have started to overlap with the emergence of devices that access the Internet using cellular infrastructures. One important question then is whether actions or threats on the Internet side can impact the telecom or cellular side. We address this problem in the paper and specifically consider the paging channel, which is a key conduit shared by both Internet and cellular traffic. Our contributions are as follows: we illustrate through experiments on a CDMA2000 cellular network that attacks launched from the Internet can significantly increase the paging load and increase the delay of paging messages including cellular call setup requests; we derive a simple but accurate queuing model for the paging system in a CDMA2000 network and use this model to demonstrate that the paging channel exhibits sharp rather than graceful degradation under load; and through this model, we identify critical parameters that impact paging performance. Although our study is focused on CDMA2000 networks, similar problems exist in other types of cellular networks that employ a single control channel with limited bandwidth for both synchronous and asynchronous control messages.     

Editing to Eulerian graphs

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations.     

Consensus in the presence of mortal Byzantine faulty processes

We consider the problem of reaching agreement in distributed systems in which some processes may deviate from their prescribed behavior before they eventually crash. We call this failure model “mortal Byzantine”. After discussing some application examples where this model is justified, we provide matching upper and lower bounds on the number of faulty processes, and on the required number of rounds in synchronous systems. We then continue our study by varying different system parameters. On the one hand, we consider the failure model under weaker timing assumptions, namely for partially synchronous systems and asynchronous systems with unreliable failure detectors. On the other hand, we vary the failure model in that we limit the occurrences of faulty steps that actually lead to a crash in synchronous systems.     

Construction and analysis of a generalized contact center model

We construct and study a model of arrival and servicing of calls in modern contact centers. The model takes into account that servicing staff divides into operators and consultants, that a call can be repeated if all operators, consultants, or access lines are busy, and also due to an unsuccessful end of waiting time, and the presence of voice answering machines. We define characteristics of call servicing, consider a method for computing them based on constructing and solving a system of statistical equilibrium equations. We propose a procedure to estimate the intensity of primary calls arrival based on measurements of general characteristics of call servicing in the contact center. We consider specific features of planning for the number of operators and access lines.     

An optimal parallel algorithm for solving the maximal elements problem in the plane

We describe an O(log(n)) time with O(n) processors optimal algorithm for finding the maximal elements of a set. The model of parallel computation we consider is the CREW-PRAM, i.e. it is the synchronous shared memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing).     

Event‐driven asynchronous method calls with the D‐Bus message system

The use of inter‐process communication can yield many benefits for event‐driven desktop software. However, inter‐process communication (IPC) research has traditionally been focused on calculation‐oriented distributed computing. This article shows that existing IPC solutions are a poor fit for the constraints imposed by event‐driven programming. Our novel solution is built on top of the D‐Bus system, which enjoys increased practical usage, but is still scantily researched. We focus on efficient handling of asynchronous D‐Bus method calls, in a fashion similar to how Hypertext Transfer Protocol requests are treated in Asynchronous JavaScript and XML Web applications. This is supplemented with two design patterns that simplify processing of results for many kinds of asynchronous operations in event‐driven software, besides just D‐Bus calls. Our approach is shown to be more appropriate for event‐driven applications than traditional remote procedure call systems in aspects as diverse as interactivity, threading complexity and electrical power usage. Copyright © 2013 John Wiley & Sons, Ltd.     

An axiomatic semantics for the synchronous language Gentzen

We propose an axiomatic semantics for the synchronous language Gentzen, which is an instantiation of the paradigm Timed Concurrent Constraint Programming proposed by Saraswat, Jagadeesan and Gupta. We view Gentzen as a prototype of the class of state-oriented synchronous languages, since it offers the basic constructs that are shared by the languages in the class. Since synchronous concurrency cannot be simulated by arbitrary interleaving, we cannot exploit “head normal forms”, on which axiomatic theories for asynchronous process calculi are based. We suggest how axiomatic semantics for other state-oriented synchronous languages can be obtained by expressing constructs of such languages in terms of Gentzen constructs.     

Markov chain models of a telephone call center with call blending

Motivated by a Bell Canada call center operating in blend mode, we consider a system with two types of traffic and two types of agents. Outbound calls are served only by blend agents, whereas inbound calls can be served by either inbound-only or blend agents. Inbound callers may balk or abandon. There are several performance measures of interest, including the rate of outbound calls and the proportion of inbound calls waiting more than some fixed number of seconds. We present a collection of continuous-time Markov chain (CTMC) models which capture many real-world characteristics while maintaining parsimony that results in fast computation. We discuss and explore the tradeoffs between model fidelity and efficacy and compare our different CTMC models with a realistic simulation model of a Bell Canada call center, used as a benchmark.