Automated Parallelization of Timed Petri-Net Simulations

Timed Petri-nets are used to model numerous types of large complex systems, especially computer architectures and communication networks. While formal analysis of such models is sometimes possible, discrete-event simulation remains the most general technique available for assessing the model′s behavior. Simulation′s computational requirements, however, can be massive, especially on the large complex models that defeat analytic methods. One way of meeting these requirements is by executing the simulation on a parallel machine. This paper describes simple techniques for the automated parallelization of timed Petri-net simulations. We address the issue of processor synchronization as well as the automated mapping, both static and dynamic, of the Petri-net to the parallel architecture. As part of this effort we describe a new mapping algorithm, one that also applies to more general parallel computations. We establish analytic properties of the solution produced by the algorithm, including optimality on some regular topologies, The viability of our integrated approach is demonstrated empirically on the Intel iPSC/860 and Delta architectures on Petri-net-based simulations of parallel architectures.     

离散事件动态系统状态空间秒速的进一步研究*

本文对离散事件动态系统的状态空间描述问题作了进一步的研究。指出了原有结果的错误和不足,讨论了既有串行阻塞又有并行阻塞的复杂阻塞现象,建立了适用于一般系统的状态方程。     

自动并行化中不规则循环的代码生成

许多大规模计算程序包含了不规则循环,但在面向分布存储的自动并行化中,以往的研究难以在编译时为不规则循环生成并行代码。针对一类常见的不规则循环提出了一种代码生成方法, 该方法 能在编译时将串行代码转换成等价的并行计算和通信代码,通过计算分解和数组引用的访问表达式来求解不规则循环在各处理器的本地定义集,并通过部分冗余的通信来满足不规则数组引用的生产者-消费者关系。实验结果表明,该方法是有效的,并对测试用例取得了预期的加速比。     

Automated Analysis of Discrete Communication Behavior

An objective methodology for the specification and analysis of communicating processes is presented. It is based on an algebraic theory that is a formalization of a particular state machine model. The approach recognizes the fact that the complexity of system interactions is such that computer aid is not only appropriate but necessary for any practical design methodology.     

Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global Variables

Parallelizing (compute-intensive) discrete event simulation (DES) applications is a classical approach for speeding up their execution and for making very large/complex simulation models tractable. This has been historically achieved via parallel DES (PDES) techniques, which are based on partitioning the simulation model into distinct simulation objects (somehow resembling objects in classical object-oriented programming), whose states are disjoint, which are executed concurrently and rely on explicit event-exchange (or event-scheduling) primitives as the means to support mutual dependencies and notification of their state updates. With this approach, the application developer is necessarily forced to reason about state separation across the objects, thus being not allowed to rely on shared information, such as global variables, within the application code. This implicitly leads to the shift of the user-exposed programming model to one where sequential-style global variable accesses within the application code are not allowed. In this article we remove this limitation by providing support for managing global variables in the context of DES code developed in ANSI-C, which gets automatically parallelized. Particularly, we focus on speculative (also termed optimistic) PDES systems that run on top of multi-core machines, where simulation objects can concurrently process their events with no guarantee of causal consistency and actual violations of causality rules are recovered through rollback/recovery schemes. In compliance with the nature of speculative processing, in our proposal global variables are transparently mapped to multi-versions, so as to avoid any form of safety predicate verification upon their updates. Consistency is ensured via the introduction of a new rollback/recovery scheme based on detecting global variables’ reads on non-correct versions. At the same time, efficiency in the execution is guaranteed by managing multi-version variables’ lists via non-blocking algorithms. Furthermore, the whole approach is fully transparent, being it based on automatized instrumentation of the application software (particularly ELF objects). Hence the programmer is exposed to the classical (and easy to code) sequential-style programming scheme while accessing any global variable. An experimental assessment of our proposal, based on a suite of case study applications, run on top of an off-the-shelf Linux machine equipped with 32 CPU-cores and 64 GB of RAM, is also presented.     

Discrete Adaptive Sliding Mode Control of a State-Space System with a Bounded Disturbance

This paper presents the discrete adaptive sliding mode control of a state-space system in the presence of a bounded disturbance. The delta form of the discrete state-space model is used as it closely resembles that of the continuous model. The control law takes into account of the effect of the disturbance by using its approximate value. The system behavior in the vicinity of the sliding surface is studied. It is shown that the adaptive controller leads to a stable closed-loop system. Also, simulation results are presented to illustrate the features of the proposed adaptive control strategy.     

Directed Explicit State-Space Search in the Generation of Counterexamples for Stochastic Model Checking

Current stochastic model checkers do not make counterexamples for property violations readily available. In this paper, we apply directed explicit state-space search to discrete and continuous-time Markov chains in order to compute counterexamples for the violation of PCTL or CSL properties. Directed explicit state-space search algorithms explore the state space on-the-fly, which makes our method very efficient and highly scalable. They can also be guided using heuristics which usually improve the performance of the method. Counterexamples provided by our method have two important properties. First, they include those traces which contribute the greatest amount of probability to the property violation. Hence, they show the most probable offending execution scenarios of the system. Second, the obtained counterexamples tend to be small. Hence, they can be effectively analyzed by a human user. Both properties make the counterexamples obtained by our method very useful for debugging purposes. We implemented our method based on the stochastic model checker PRISM and applied it to a number of case studies in order to illustrate its applicability.     

Dynamic Generation of Discrete Random Variates

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in O(log ^* N) expected time and updates a weight in O(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log ^* N) amortized expected time. We finally show how to apply our techniques to a lookup-table technique in order to obtain expected constant time in the worst case for generation and update. We give parallel algorithms for parallel generation and update having optimal processor—time product. Besides the usual application in computer simulation, our method can be used to perform constant-time prediction in prefetching applications. We also apply our techniques to obtain an efficient dynamic algorithm for maintaining an approximate heap of N elements, in which each query is required to return an element whose value is within an ɛ multiplicative factor of the maximal element value. For ɛ= 1/polylog (N), each query, insertion, or deletion takes O(log log log N) time.     

Coverage-driven Automated Compiler Test Suite Generation

The paper presents a novel approach to automated compiler test suite generation based on the source level specification. Several coverage criteria are introduced. The application of the proposed methodology to testing the realistic programming language is discussed.     

安全漏洞自动利用综述

随着安全漏洞数量急剧上升,高效率地评估与修复漏洞面临更大的挑战.目前漏洞的可利用性评估主要依赖人工方法,如何智能化和自动化地进行安全漏洞利用是本领域一个热点研究问题.调研了2006年至今安全漏洞自动利用文献,分析了现状并指出了漏洞利用研究的发展趋势,同时给出了漏洞自动利用的一般框架;分别从漏洞自动利用的信息输入、漏洞类型和利用方法这3个角度对当前研究成果进行了梳理,指出了这3个角度对漏洞自动利用的影响;分析了漏洞自动利用研究的不足与挑战,并对将来的研究趋势进行了展望.     

Automated Test Generation and Static Analysis

The study and development of techniques for automated generation of useful tests, the development of a system that implements those techniques, and the development of methods for the analysis of programs designed for solving this problem are based on the earlier works of the author of the present paper, the works by B. Korel, and on the desire to understand if the approaches suggested can be used to develop real-world software. The first problem is as follows: determine, which information on the program must be collected to automatically generate a set of tests, and develop a component for collecting this information. The emphasis was made on collecting this information statically using a powerful flow analyzer developed in a laboratory of the Institute of Information Systems. Another problem consists in developing a prototype system for trying both well-known and new test generation methods suggested by the author. As a result, path-oriented and objective-oriented methods of test generation and the chaining approach (which turned out to be the most interesting one) are considered. This approach uses the concept of influence of an input variable on an operator along a certain program execution path and is based on dynamic analysis. The concept of influence can be extended for the case of all paths; then, such influences can be detected statically. In this paper, the influence along any path is rigorously defined and its constructive flow reformulation is given. On the basis of this reformulation, a language processor is developed that performs a static analysis of dependencies and calculates, for every statement of the program, the set of input variables that influence it.     

Automated Displacement for Large Numbers of Discrete Map Objects

Effective displacement is achieved by sharing small movements among a group of objects in order to minimize loss of positional accuracy and maintain the gestalt and topology of the map objects. This research was driven by a desire to implement a simple but effective way of handling large numbers of map objects that may require displacement. The algorithm works by considering, for each object in turn, a number of alternate positions close to its current location. The location which minimizes overlap among the neighbouring objects is chosen. As the program iterates, the objects effectively migrate small distances within the map space in search of solutions. The idea is relatively simple but produces visually acceptable solutions to the displacement of large numbers of objects with very low processing overhead. This paper describes the algorithm in detail, illustrates its application, refinement and evaluation. Received December 11, 1998; revised October 14, 1999.     

A Pattern Recognition Approach for Speculative Firing Prediction in Distributed Saturation State-Space Generation

The saturation strategy for symbolic state-space generation is particularly effective for globally-asynchronous locally-synchronous systems. A distributed version of saturation, SaturationNOW, uses the overall memory available on a network of workstations to effectively spread the memory load, but its execution is essentially sequential. To achieve true parallelism, we explore a speculative firing prediction, where idle workstations work on predicted future event firing requests. A naïve approach where all possible firings may be explored a priori, given enough idle time, can result in excessive memory requirements. Thus, we introduce a history-based approach for firing prediction that recognizes firing patterns and explores only firings conforming to these patterns. Experiments show that our heuristic improves the runtime and has a small memory overhead.     

Automated Generation of Cross-System Software for Microcomputers

GEN is a set of Fortran program writer modules designed to generate microcomputer assemblers and simulators. It is simple enough to be used by those with limited architecture and programming backgrounds yet flexible and powerful enough to generate efficient and well-structured assemblers and simulators for microcomputes sophisticated tectures and instruction sets. This paper describes the generating system, the generated gPoassemblers and simulators, and the advantages they offer in both programming and pedagogical applications.     

Comparing Instance Generation Methods for Automated Reasoning

The clause-linking technique of Lee and Plaisted proves the unsatisfiability of a set of first-order clauses by generating a sufficiently large set of instances of these clauses that can be shown to be propositionally unsatisfiable. In recent years, this approach has been refined in several directions, leading to both tableau-based methods, such as the disconnection tableau calculus, and saturation-based methods, such as primal partial instantiation and resolution-based instance generation. We investigate the relationship between these calculi and answer the question to what extent refutation or consistency proofs in one calculus can be simulated in another one. This work was partly supported by the German Research Council (DFG) as part of the Transregional Collaborative Research Center “Automatic Verification and Analysis of Complex Systems” (SFB/TR 14 AVACS). See for more information.     

Goal-Based Automated Code Generation in Self-Adaptive System

System administrator deals with many problems, as computing environment becomes increasingly complex. Systems with an ability to recognize system states and adapt to resolve these problems offer a solution. Much experience and knowledge are required to build a self-adaptive system. Self-adaptive systems have inherent difficulties. This paper proposes a technique that automatically generates the code for the self-adaptive system. Thus the system is easier to build. Self-adaptive systems of previous research required high system resource usage. Incorrect operation could be invoked by external factors such as viruses. We propose an improved self-adaptive system approach and apply it to video conference system and robot system. We compared the lines of code, the number of classes created by the developers. We have confirmed this enhanced approach to be effective in reducing these development metrics.     

Automated Test Case Generation for BDI Agents

We propose a coverage oriented test case generation methodology for BDI multi-agent systems. The coverage criteria involve plans and nodes within plans of multi-agent systems. We organise the criteria into a subsumption hierarchy to show the coverage relationships between the criteria. Then we apply the criteria on multi-agent systems to analyse some empirical data. The data analysed is the effect on the number of test cases generated automatically for each criterion. We use a tool, BDITESTER, to obtain the empirical data and to show that our proposal is pragmatic. Finally, we suggest some guidelines to select a criterion to automatically generate test cases for BDI agents.     

舰船装备软件测试数据自动生成方法及其应用研究

针对舰船装备软件接口报文信息量大,难于有效生成测试数据的现状,提出了一种基于网络信息交换协议的测试数据自动生成方法;首先通过分析网络信息交换协议中对接口报文的格式要求,获取测试数据要素信息,然后根据该信息自动生成接口报文数据,并且对所涉及的实际物理量和状态位数据进行必要转换,从而得到可执行的测试数据;在此基础上,开发舰船装备软件自动化测试平台,并将其应用于实际测试项目,有效提高了测试数据生成效率。 