195710837
Dynamic Reverse Code Generation for Backward Execution
The need for backward execution in debuggers has been raised a number of times. Backward execution helps a user naturally think backwards and, in turn, easily locate the cause of a bug. Backward execution has been implemented mostly by state-saving or checkpointing, which are inherently not scalable. In this paper, we present a method to generate reverse code, so that backtracking can be performed by executing reverse code. The novelty of our work is that we generate reverse code on-the-fly, while running a debugger, which makes it possible to apply the method even to debugging multi-threaded programs.
14520724
Bogor/Kiasan: A k-bounded Symbolic Execution for Checking Strong Heap Properties of Open Systems
This paper presents Kiasan, a bounded technique to reason about open systems based on a path sensitive, relatively sound and complete symbolic execution instead of the usual compositional reasoning through weakest precondition calculation that summarizes all execution paths. Kiasan is able to check strong heap properties, and it is fully automatic and flexible in terms of its cost and the guarantees it provides. It allows a user-adjustable mixed compositional/non-compositional reasoning and naturally produces error traces as fault evidence. We implemented Kiasan using the Bogor model checking framework and observed that its performance is comparable to ESC/Java on similar scales of problems and behavioral coverage, while providing the ability to check much stronger specifications
16485757
Reverse Engineering MAC
This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.
2979889
An effective customization procedure with configurable standard models
In electronic catalogs, commodities such as computers and electronic equipment are specified as standard models although a variety of possible alternative specifications can exist as a combination of selected options; therefore, customized configurations are essential to support various customers with individual needs. Thus, the problem here is the selection of a standard model and reconfiguration with this selected model. An issue is that requirements may be fulfilled by more than one standard model. To develop an algorithm that can find the near minimum price without causing unacceptable computation effort, we devised the Standard Model Selection and Modification (SMSM) Algorithm. To establish the SMSM Algorithm, we propose the Concurrent Local Propagation procedure complemented with pruning capability owing to the nature of standard models. The effective strategies for selection of seed variables and stopping rules are devised through comparative experiments.For the experiment, we use Dell's personal computer (PC) products consisting of 42 standard models with 25 specification variables. The SMSM Algorithm is tested with 75 experimental cases, and we found that the most similar standard models could discover the minimum price only in 24 out of 75 cases and that the SMSM procedure could reduce the price by 6.04% from the one offered by the most similar standard models.
19612327
Instruction level redundant number computations for fast data intensive processing in asynchronous processors
Instruction level parallelism (ILP) is strictly limited by various dependencies. In particular, data dependency is a major performance bottleneck of data intensive applications. In this paper we address acceleration of the execution of instruction codes serialized by data dependencies. We propose a new computer architecture supporting a redundant number computation at the instruction level. To design and implement the scheme, an extended data-path and additional instructions are also proposed. The architectural exploitation of instruction level redundant number computations (IL-RNC) makes it possible to eliminate carry propagations. As a result execution of instructions which are serialized due to inherent data dependencies is accelerated. Simulations have been performed with data intensive processing benchmarks and the proposed architecture shows about a 1.2-1.35 fold speedup over a conventional counterpart. The proposed architecture model can be used effectively for data intensive processing in a microprocessor, a digital signal processor and a multimedia processor.
29667666
Building a distributed asynchronous control unit through automatic derivation of hierarchically decomposed AFSMs from a CDFG
Although there are several successful asynchronous logic synthesis tools, it is still unwieldy for designers to conceive and describe behaviors for a number of controllers constituting an asynchronous control unit of a target system manually. In this paper, building a distributed asynchronous control unit automatically through automatic derivation of hierarchically decomposed AFSMs from a CDFG is suggested. A resulting control unit consists of small asynchronous controllers and has complete separation of 'execution controllers' and 'execution order controllers'. This distributive feature leads to significant improvements in the aspects of area, performance and synthesis time of derived control circuits.
11317556
Introductory paper
The computer-assisted resuscitation algorithm (CARA) is the software component of an automatic infusion pump system being designed by US Army’s Walter Reed Institute of Research (WRAIR) to be used in the battlefields of tomorrow. Such medical devices are safety critical, and their use needs to be approved by the US Food and Drug Administration (FDA) – a process on which formal methods can have a great impact. In this special section, six papers on the analysis of CARA’s requirements are presented. In the rest of this introduction, we present the framework and summary of results from those papers.