03-09-2012, 04:38 PM
A PRECISE TERMINATION CONDITION OF THE PROBABIISTIC PACKET MARKING ALGORITHM
A Precise Termination.doc (Size: 691.5 KB / Downloads: 38)
Abstract
The probabilistic packet marking (PPM) algorithm is a promising way to discover the Internet map or an attack graph that the attack packets traversed during a distributed denial-of-service attack. However, the PPM algorithm is not perfect, as its termination condition is not well defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the Rectified PPM (RPPM) algorithm. The most significant merit of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct, with a specified level of confidence. We carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising means of enhancing the reliability of the PPM algorithm.
Introduction
THE denial-of-service (DoS) attack has been a pressing problem in recent years. DoS defense research has blossomed into one of the main streams in network security. Various techniques such as the pushback message, ICMP traceback, and the packet filtering techniques are the results from this active field of research. The probabilistic packet marking (PPM) algorithm by Savage et al. has attracted the most attention in contributing the idea of IP traceback. The most interesting point of this IP traceback approach is that it allows routers to encode certain information on the attack packets based on a predetermined probability. Upon receiving a sufficient number of marked packets, the victim (or a data collection node) can construct the set of paths that the attack packets traversed and, hence, the victim can obtain the location(s) of the attacker(s).
The Probabilistic Packet Marking Algorithm The goal of the PPM algorithm is to obtain a constructed graph such that the constructed graph is the same as the attack graph, where an attack graph is the set of paths the attack packets traversed, and a constructed graph is a graph returned by the PPM algorithm. To fulfill this goal, Savage et al. Suggested a method for encoding the information of the edges of the attack graph into the attack packets through the cooperation of the routers in the attack graph and the victim site. Specifically, the PPM algorithm is made up of two separated procedures: the packet marking procedure, which is executed on the router side, and the graph reconstruction procedure, which is executed on the victim side.
System Analysis
Requirements Analysis is done in order to understand the problem for which the software system is to solve. For example, the problem could be automating an existing manual process, or developing a completely new automated system, or a combination of the two. For large systems which have a large number of features, and that need to perform many different tasks, understanding the requirements of the system is a major task. The emphasis in requirements Analysis is on identifying what is needed from the system and not how the system will achieve it goals. This task is complicated by the fact that there are often at least two parties involved in software development - a client and a developer. The developer usually does not understand the client's problem domain, and the client often does not understand the issues involved in software systems. This causes a communication gap, which has to be adequately bridged during requirements Analysis.
In most software projects, the requirement phase ends with a document describing all the requirements. In other words, the goal of the requirement specification phase is to produce the software requirement specification document. The person responsible for the requirement analysis is often called the analyst. There are two major activities in this phase - problem understanding or analysis and requirement specification in problem analysis; the analyst has to understand the problem and its context. Such analysis typically requires a thorough understanding of the existing system, the parts of which must be automated.
Once the problem is analyzed and the essentials understood, the requirements must be specified in the requirement specification document. For requirement specification in the form of document, some specification language has to be selected (example: English, regular expressions, tables, or a combination of these). The requirements documents must specify all functional and performance requirements, the formats of inputs, outputs and any required standards, and all design constraints that exits due to political, economic environmental, and security reasons. The phase ends with validation of requirements specified in the document. The basic purpose of validation is to make sure that the requirements specified in the document, actually reflect the actual requirements or needs, and that all requirements are specified. Validation is often done through requirement review, in which a group of people including representatives of the client, critically review the requirements specification.
System Design:
The purpose of the design phase is to plan a solution of the problem specified by the requirement document. This phase is the first step in moving from problem domain to the solution domain. The design of a system is perhaps the most critical factor affecting the quality of the software, and has a major impact on the later phases, particularly testing and maintenance. The output of this phase is the design document. This document is similar to a blue print or plan for the solution, and is used later during implementation, testing and maintenance.
The design activity is often divided into two separate phase-system design and detailed design. System design, which is sometimes also called top-level design, aims to identify the modules that should be in the system, the specifications of these modules, and how they interact with each other to produce the desired results. At the end of system design all the major data structures, file formats, output formats, as well as the major modules in the system and their specifications are decided.