5444394
A First Look at Peer-to-Peer Worms: Threats and Defenses
Peer-to-peer (P2P) worms exploit common vulnerabilities in member hosts of a P2P network and spread topologically in the P2P network, a potentially more effective strategy than random scanning for locating victims. This paper describes the danger posed by P2P worms and initiates the study of possible mitigation mechanisms. In particular, the paper explores the feasibility of a self-defense infrastructure inside a P2P network, outlines the challenges, evaluates how well this defense mechanism contains P2P worms, and reveals correlations between containment and the overlay topology of a P2P network. Our experiments suggest a number of design directions to improve the resilience of P2P networks to worm attacks.
18035076
On Subsumption Removal and On-the-Fly CNF Simplification
CNF Boolean formulas generated from resolution or solution enumeration often have much redundancy. Efficient algorithms are needed to simplify and compact such CNF formulas. In this paper, we present a novel algorithm to maintain a subsumption-free CNF clause database by efficiently detecting and removing subsumption as the clauses are being added. We then present an algorithm that compact CNF formula further by applying resolutions to make it Decremental Resolution Free. Our experimental evaluations show that these algorithms are efficient and effective in practice.
70202123
The Quest for Efficient Boolean Satisfiability Solvers
The classical NP-complete problem of Boolean Satisfiability (SAT) has seen much interest in not just the theoretical computer science community, but also in areas where practical solutions to this problem enable significant practical applications. Since the first development of the basic search based algorithm proposed by Davis, Putnam, Logemann and Loveland (DPLL) about forty years ago, this area has seen active research effort with many interesting contributions that have culminated in state-of-the-art SAT solvers today being able to handle problem instances with thousands, and in same cases even millions, of variables. In this paper we examine some of the main ideas along this passage that have led to our current capabilities. Given the depth of the literature in this field, it is impossible to do this in any comprehensive way; rather we focus on techniques with consistent demonstrated efficiency in available solvers. For the most part, we focus on techniques within the basic DPLL search framework, but also briefly describe other approaches and look at some possible future research directions.
9292941
Chaff: engineering an efficient SAT solver
Boolean satisfiability is probably the most studied of the combinatorial optimization/search problems. Significant effort has been devoted to trying to provide practical solutions to this problem for problem instances encountered in a range of applications in electronic design automation (EDA), as well as in artificial intelligence (AI). This study has culminated in the development of several SAT packages, both proprietary and in the public domain (e.g. GRASP, SATO) which find significant use in both research and industry. Most existing complete solvers are variants of the Davis-Putnam (DP) search algorithm. In this paper we describe the development of a new complete solver, Chaff which achieves significant performance gains through careful engineering of all aspects of the search-especially a particularly efficient implementation of Boolean constraint propagation (BCP) and a novel low overhead decision strategy. Chaff has been able to obtain one to two orders of magnitude performance improvement on difficult SAT benchmarks in comparison with other solvers (DP or otherwise), including GRASP and SATO.
6734525
Propositional Satisfiability and Constraint Programming: A comparative survey
Propositional Satisfiability (SAT) and Constraint Programming (CP) have developed as two relatively independent threads of research cross-fertilizing occasionally. These two approaches to problem solving have a lot in common as evidenced by similar ideas underlying the branch and prune algorithms that are most successful at solving both kinds of problems. They also exhibit differences in the way they are used to state and solve problems since SAT's approach is, in general, a black-box approach, while CP aims at being tunable and programmable. This survey overviews the two areas in a comparative way, emphasizing the similarities and differences between the two and the points where we feel that one technology can benefit from ideas or experience acquired from the other.
10515113
Validating SAT solvers using an independent resolution-based checker: practical implementations and other applications
As the use of SAT solvers as core engines in EDA applications grows, it becomes increasingly important to validate their correctness. In this paper, we describe the implementation of an independent resolution-based checking procedure that can check the validity of unsatisfiable claims produced by the SAT solver zchaff. We examine the practical implementation issues of such a checker and describe two implementations with different pros and cons. Experimental results show low overhead for the checking process. Our checker can work with many other modern SAT solvers with minor modifications, and it can provide information for debugging when checking fails. Finally we describe additional results that can be obtained by the validation process and briefly discuss their applications.
6040398
C-DIST: efficient distance computation for rigid and articulated models in configuration space
The problem of distance computation arises in many applications including motion planning, CAD/CAM, dynamic simulation and virtual environments. Most prior work in this area has been restricted to separation or penetration distance computation between two objects. In this paper, we address the problem of computing a measure of distance between two configurations of a rigid or articulated model. The underlying distance metric is defined as the length of the longest displacement vector over the corresponding vertices of the model between two configurations. Our algorithm is based on Chasles theorem in Screw theory, and we show that the maximum distance can be realized only by a vertex of the convex hull of a rigid object. We use this formulation to compute the distance, and present two acceleration techniques to speed up the computation: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and describe its application to proximity queries and motion planning.
12034638
A block-based inter-band lossless hyperspectral image compressor
We propose a hyperspectral image compressor called BH which considers its input image as being partitioned into square blocks, each lying entirely within a particular band, and compresses one such block at a time by using the following steps: first predict the block from the corresponding block in the previous band, then select a predesigned code based on the prediction errors, and finally encode the predictor coefficient and errors. Apart from giving good compression rates and being fast, BH can provide random access to spatial locations in the image. We hypothesize that BH works well because it accommodates the rapidly changing image brightness that often occurs in hyperspectral images. We also propose an intra-band compressor called LM which is worse than BH, but whose performance helps explain BH's performance.
12511043
Real-time lossless compression of mosaic video sequences
This paper presents a simple, fast coding technique for lossless compression of mosaic video data. The design of a video codec needs to strike a balance between the compression performance and the codec throughput. Aiming to make the encoding throughput high enough for real-time lossless video compression, we propose a hybrid scheme of inter and intraframe coding. Interframe predictive coding is invoked only when the motion between adjacent frames is modest and a simple motion compensation operation can significantly improve the compression performance. Otherwise, still frame compression is performed to keep the complexity low. Experimental results show that the proposed scheme achieves higher lossless video compression ratio than existing methods such as JPEG-LS and JPEG-2000.
5219400
Timer Interaction in Route Flap Damping
Route Flap Damping is a mechanism generally used in network routing protocols. Its goal is to limit the global impact of unstable routes by temporarily suppressing routes with rapid changes over short time periods. Although route damping is a clearly defined and simple procedure at each router, its effect in a large network setting is not well understood. We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay. Previous work observed that a single route flap can falsely trigger route suppression due to path exploration. However our simulations show that this false suppression only accounts for 30% of the convergence delay after a single route flap. Our study reveals previously unknown interactions between reuse timers at different routers. Route suppression and reuse at different routers are triggered at different times and thus affect the number of updates received by other routers. In turn, this impacts other routers' damping behavior. We propose to use Root Cause Notification to eliminate both false suppression and undesirable timer interaction
35154579
Incorporating priority scheme in IPv6 over ATM networks
An effective approach to support multiple QoS classes in IPv6 running over ATM networks is implemented by mapping the priority field of IPv6 into the ATM format. Such a scheme might not be necessary for simple congestion control in a network of equal capacity links, however, it might be important for multicasting to destinations reachable through a very diverse capacity network. When network congestion occurs, the cell loss requirements for different services can be satisfied by selectively discarding low priority cells. As the multi-priority scheme used in IPv6 is a ''differentiated service'' mechanism to enhance the QoS by best effort, its performance is certainly affected by the background traffic when these multi-priority traffic are multiplexed at the ATM level. This paper focuses on the performance with multi-priority scheme under different traffic conditions to determine the loss characteristics. The expected results are how QoS is affected and how priority can be given for more important traffic in the case of congested network.