Distributed Partial Order Reduction for Security Protocols

We describe a distributed partial order reduction algorithm for security protocols. Some experimental results using an implementation of the algorithm in the distributed μCRL toolset are also reported.     

Distributed Partial Order Reduction of State Spaces

State space explosion is a fundamental obstacle in formal verification of concurrent systems. Several techniques for combating this problem have emerged in the past few years, among which the two we are interested in are: partial order reduction and distributed memory state exploration. While the first one tries to reduce the problem to a smaller one, the other one tries to extend the computational power to solve the same problem. In this paper, we consider a combination of these two approaches and propose a distributed memory algorithm for partial order reduction.     

A Methodology for Developing Distributed Programs

A methodology, different from the existing ones, for constructing distributed programs is presented. It is based on the well-known idea of developing distributed programs via synchronous and centralized programs. The distinguishing features of the methodology are: 1) specification include process structure information and distributed programs are developed taking this information into account, 2) a new class of programs, called PPSA's, is used in the development process, and 3) a transformational approach is suggested to solve the problems inherent in the method of developing distributed programs through synchronous and centralized programs. The methodology is illustrated with an example.     

On Linguistic Support for Distributed Programs

Technological advances have made it possible to construct systems from collections of computers connected by a network. At present, however, there is little support for the construction and execution of software to run on such a system. Our research concerns the development of an integrated language/system whose goal is to provide the needed support. This paper discusses a number of issues that must be addressed in such a language. The major focus of our work and this paper is support for the construction of robust software that survives node, network, and media failures.     

Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them

Monitoring or diagnosis of large scale distributed Discrete Event Systems with asynchronous communication is a demanding task. Ensuring that the methods developed for Discrete Event Systems properly scale up to such systems is a challenge. In this paper we explain why the use of partial orders cannot be avoided in order to achieve this objective. To support this claim, we try to push classical techniques (parallel composition of automata and languages) to their limits and we eventually discover that partial order models arise at some point. We focus on on-line techniques, where a key difficulty is the choice of proper data structures to represent the set of all runs of a distributed system, in a modular way. We discuss the use of previously known structures such as execution trees and unfoldings. We propose a novel and more compact data structure called “trellis.” Then, we show how all the above data structures can be used in performing distributed monitoring and diagnosis. The techniques reported here were used in an industrial context for fault management and alarm correlation in telecommunications networks. This paper is an extended and improved version of the plenary address that was given by the second author at WODES’ 2006.

Communication and Synchronization Primitives for Distributed Programs

A distributed program is a collection of several processes which execute concurrently, possibly in different nodes of a distributed system, and which cooperate with each other to realize a common goal. In this paper, we present a design of communication and synchronization primitives for distributed programs. The primitives are designed such that they can be provided by a kernel of a distributed operating system. An important feature of the design is that the configuration of a process, i.e., identities of processes with which the process communicates, is specified separately from the computation performed by the process. This permits easy configuration and reconfiguration of processes. We identify different kinds of communication failures, and provide distinct mechanisms for handling them. The communication primitives are not atomic actions. To enable the construction of atomic actions, two new program components, atomic agent and manager are introduced. These are devoid of policy decisions regarding concurrency control and atomic commitment. We introduce the notion of conflicts relation using which a designer can construct either an optimistic or a pessimistic concurrency control scheme. The design also incorporates primitives for constructing nested atomic actions.     

Language Support for Loosely Coupled Distributed Programs

A distributed operating system encourages a style of programming in which independently developed processes interact in a nontrivial fashion at run time. Server processes, for example, must deal with clients that they do not understand, and certainly cannot trust. Interprocess communications can be written in a traditional, sequential language with direct calls to kernel primitives, but the result is both cumbersome and error-prone. Convenience and safety are offered by the many distributed languages proposed to date, but in a form too inflexible for anything other than the pieces of a single distributed program. A new language known as LYNX overcomes the disadvantages of both these previous approaches. Novel features of LYNX address problems encountered in the course of practical experience, writing distributed programs without high-level language support. Chief among these features are a virtual circuit abstraction called the link, and an unconventional coroutine mechanism that allows a server to maintain nested contexts for interleaved conversations with an arbitrary number of clients.     

一个面向C和Fortran数值程序的静态分析工具

程序的正确性验证一直以来都是计算机科学中的一个挑战性问题,抽象解释理论为程序静态分析提供了一个通用框架,可以在编译时自动地推导程序的动态性质。基于抽象解释的数值程序分析可以自动推导程序中数值变量间的不变式关系,这对于编译优化、程序错误检查至关重要。本文建立并实现了一个面向C和Fortran程序并支持过程间分析的数值程序分析框架和工具,C或Fortran源程序经过预处理后转化为具有统一格式的中间表示形式,然后基于该中间表示抽取与源程序语义等价的语义等式,最后在该语义等式上进行不动点迭代计算从而得到程序不变式。在此基础上,本文还对数组等复杂语法结构进行了建模和抽象。实验结果表明,该工具具有较高的可扩展性、精度,并能够处理大部分因数组的使用而带来的程序分析上的问题。     

CAN总线分布式系统程序的以太网在线更新

提出了一种针对采用的STM32控制器的基于CAN总线的分布式系统程序在线更新方案,主控节点利用TFTP协议从以太网获得更新程序,再利用CAN通过分块文件传输协议更新各个节点的程序.并简要介绍了STM32的启动流程以及程序加载的方法.     

Partial Order Reduction for Probabilistic Branching Time

In the past, partial order reduction has been used successfully to combat the state explosion problem in the context of model checking for non-probabilistic systems. For both linear time and branching time specifications, methods have been developed to apply partial order reduction in the context of model checking. Only recently, results were published that give criteria on applying partial order reduction for verifying quantitative linear time properties for probabilistic systems. This paper presents partial order reduction criteria for Markov decision processes and branching time properties, such as formulas of probabilistic computation tree logic. Moreover, we provide a comparison of the results established so far about reduction conditions for Markov decision processes.     

Distributed Breakpoint Detection in Message-Passing Programs

The ability to set breakpoints stands, along with the possibility of deterministic reexecution, as one of the most important issues in the debugging of message-passing programs. We consider in this paper the design of fully distributed algorithms for the detection of breakpoints in such programs, and provide four algorithms, one for each different type of breakpoint. One of the algorithms detects the occurrence of unconditional breakpoints, while the other three detect the occurrence of breakpoints on disjunctive predicates, stable conjunctive predicates, and generic conjunctive predicates. All the algorithms we present detect breakpoints in the form of earliest global states with respect to the particular property involved. In the case of unconditional breakpoints, such an earliest global state must coincide exactly with the requested local unconditional breakpoints for the processes that do actually participate in the breakpoint. In the case of the other (conditional) breakpoints, what is detected is the earliest global state at which either the disjunctive or the conjunctive predicate under consideration is true. In order to actually halt the computation at the exact global state the algorithms detect, we suggest as a first approach the use of checkpointing and rollback-recovery techniques.     

启发式全局偏序挖掘算法

偏序模型能直观反映序列数据信息,全局偏序模型能进一步从整体上更加准确反映序列的全局信息,方便用户的理解.本文对全局偏序模型的构建方法进行研究,针对基于遍历搜索构建模型所造成的效率较低,不宜扩展的问题,提出基于启发式搜索的全局模型构造改进算法.在模型构造中有效利用频繁序列挖掘算法所获得的局部信息,改进搜索路径,提高算法效率,获得准确结果.     

任意偏序的NTree判定及近似表示

用角色而不是个体作为存取控制的粒度单位有许多优点，这些优点在层次RBAC（偏序）中得到进一步体现，NTree是定义这种偏序既自然又系统的方法，本文介绍了偏序的超矩阵表示及相应的NTree判别和近似表示方法。     

二阶分布参数系统的稳定性和能控性

讨论Hilbert空间上两个二阶线性系统的稳定性和能控性,在较一般的假设下,得到了这两个系统的指数稳定性和精确能控性,渐近稳定性和近似能控性之间的关系.最后,给出线性系统渐近稳定的一个充分必要条件.     

Ada软件源代码分析器（ASCA）

论述了Ａｄａ软件源代码分析器的结构，功能以及一些特点。该工具是保证Ａｄａ软件系统质量的工具这一，可为高效地开发和维护大型，复杂的软件系统提供支持。     

Compilation and Communication Strategies for Out-of-Core Programs on Distributed Memory Machines

It is widely acknowledged that improving parallel I/O performance is critical for widespread adoption of high performance computing. In this paper, we show that communication in out-of-core distributed memory problems may require both interprocessor communication and file I/O. Thus, in order to improve I/O performance, it is necessary to minimize the I/O costs associated with a communication step. We present three methods for performing communication in out-of-core distributed memory problems. The first method, called thegeneralized collective communicationmethod, follows a loosely synchronous model; computation and communication phases are clearly separated, and communication requires permutation of data in files. The second method, called thereceiver-driven in-core communication, communicates only the in-core data. The third method, called theowner-driven in-core communication, goes even one step further and tries to identify the potential future use of data (by the recipients) while it is in the senders memory. We provide performance results for two out-of-core applications: the two-dimensional FFT code, and the two-dimensional elliptic Jacobi solver.     

IE痕迹追踪程序的研究与设计

本文通过运用WINDOWS编程技术实现对IE痕迹证据的查找、分析和保全,有效解决了手工查找证据所存在的烦琐、低效问题。     

A Fast Bit-Parallel Algorithm for Computing the Subset Partial Order

A given collection of sets has a natural partial order induced by the subset relation. Let the size N of the collection be defined as the sum of the cardinalities of the sets that comprise it. Algorithms have recently been discovered that compute the partial order in worst-case time O(N ² / log N) . This paper gives implementations of a variant of a previously proposed algorithm which exploit bit-parallel operations on a RAM with -bit words. One is shown to have a worst-case complexity of O(N ² log log N / log ² N) operations. This is the first known o(N ² / log N) worst case or randomized expected running time for this problem. Received March 1, 1996; revised December 24, 1997.