This uses a sub-string search, so that "graph" matches both "graph" and "graphical".
This search only searches by keyword. If you'd like, you can also search by researcher.
Found 11 results.
Listing from newest to oldest
TR-CS-2007-12
Protecting BGP from Invalid Paths
Josh Karlin, Stephanie Forrest and Jennifer Rexford
The Internet's interdomain routing protocol, BGP, is vulnerable to a number of potentially crippling attacks. Many promising cryptography-based solutions have been proposed, but none have been embraced by the necessary communities to garner significant adoption. This is largely due to the difficulty of developing and maintaining the necessary PKI infrastructure and changes to the BGP protocol that the proposed solutions require. Alternative solutions such as anomaly detectors have been unable to provide the same level of security as the cryptographic mechanisms. In this paper we create an anomaly detector and response mechanism capable of automatically stopping the propagation of invalid path attacks, a difficult class of attacks to detect. Our solution provides comparable security to the cryptographic methods and could be readily deployed with a simple software upgrade in participating networks.
TR-CS-2007-11
Worm Versus Alert: Who Wins in a Battle for Control of a
Large-Scale Network?
James Aspnes, Navin Rustagi, and Jared Saia
Consider the following game between a worm and an alert1 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node independently with small but constant probability. The game starts with a single node becoming infected. In every round thereafter, every infected node sends out a constant number of worms to other nodes in the population, and every alerted node sends out a constant number of alerts. Nodes in the network change state according to the following three rules: 1) If a worm is received by a node that is not a detector and is not alerted, that node becomes infected; 2) If a worm is received by a node that is a detector, that node becomes alerted; 3) If an alert is received by a node that is not infected, that node becomes alerted.
We make two assumptions about this game. First, that an infected node can send worm messages to any other node in the network but, in contrast, an alerted node can send alert messages only through a previously determined, constant degree overlay network. Second, we assume that the infected nodes are intelligent, coordinated and essentially omniscient. In other words, the infected nodes know everything except for which nodes are detectors and the alerted nodes' random coin flips i.e. they know the topology of the overlay network used by the alerts; which nodes are alerted and which are infected at any time; where alerts and worms are being sent; the overall strategy used by the alerted nodes; etc. The alerted nodes are assumed to know nothing about which other nodes are infected or alerted, where alerts or worms are being sent, or the strategy used by the infected nodes.
Specifically, this result holds if d ≥ α and 
,
where α and 
represent the
rate of the spread of the alert and worm respectively; 
is the
probability that a node is a detector node; d is the degree of the
overlay network; and c is the node expansion of the overlay
network. Next, we give empirical results that suggest that our
algorithms for the alert may be useful in current large-scale
networks. Finally, we show that if the overlay network has poor
expansion, in particular if 
, then the worm will likely
infect almost all of the non-detector nodes.
1Specifically, we consider self-certifying alerts[6], which contain short proofs that a security flaw exists and thereby eliminate false alerts.
TR-CS-2006-10
Pretty Good BGP: Improving BGP by Cautiously Adopting Routes
Josh Karlin, Stephanie Forrest, and Jennifer Rexford
The Internet's interdomain routing protocol, BGP, is vulnerable to a number of damaging attacks, which often arise from operator misconfiguration. Proposed solutions with strong guarantees require a public-key infrastructure, accurate routing registries, and changes to BGP. While experts debate whether such a large deployment is feasible, networks remain vulnerable to false information injected into BGP. However, BGP routers could avoid selecting and propagating these routes if they were cautious about adopting new reachability information. We describe a protocol-preserving enhancement to BGP, Pretty Good BGP (PGBGP), that slows the dissemination of bogus routes, providing network operators time to respond before problems escalate into a large-scale Internet attack. Simulation results show that realistic deployments of PGBGP could provide 99% of Autonomous Systems with 24 hours to investigate and repair bogus routes without affecting prefix reachability. We also show that without PGBGP, 40% of ASs cannot avoid selecting bogus routes; with PGBGP, this number drops to less than 1%. Finally, we show that PGBGP is incrementally deployable and offers significant security benefits to early adopters and their customers.
TR-CS-2005-37
Pretty Good BGP: Protecting BGP by Cautiously Selecting Routes
Josh Karlin, Stephanie Forrest, and Jennifer Rexford
The Border Gateway Protocol (BGP), the Internet's interdomain routing protocol, is vulnerable to a number of damaging attacks. Proposed solutions either (i) rely on a public-key infrastructure and accurate routing registries or (ii) detect attacks only after they have spread throughout the network. However, BGP routers could avoid selecting and propagating malicious routes if they were cautious about adopting new reachability information. We describe an enhancement to BGP, Pretty Good BGP (PGBGP), that slows the dissemination of malicious routes, providing network operators time to respond before the problem escalates into a large-scale Internet attack. Results show that realistic deployments of PGBGP could provide 99% of Autonomous Systems with 24 hours to investigate and repair malicious routes without affecting prefix reachability. The result also show that without PGBGP, 40% of ASs cannot avoid using malicious routes; with PGBGP, this number drops to less than 1%. Finally, we show that PGBGP is incrementally deployable and offers significant security benefits to early adopters and their customers.
TR-CS-2003-46
Fast Shared-Memory Algorithms for Computing the Minimum
Spanning Forest of Sparse Graphs
David A. Bader and Guojing Cong
Minimum Spanning Tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to implement or perform well only on special graphs with regular structure. In this paper we design and implement four parallel MST algorithms (three variations of Boruvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the \emph{best} sequential algorithm. In fact, our algorithms also solve the minimum spanning forest problem. We provide an experimental study of our algorithms on symmetric multiprocessors such as IBM's p690/Regatta and Sun's Enterprise servers. Our new implementation achieves good speedups over a wide range of input graphs with regular and irregular structures, including the graphs used by previous parallel MST studies. For example, on an arbitrary random graph with 1M vertices and 20M edges, we have a speedup of 5 using 8 processors. The source code for these algorithms is freely-available from our web site.
TR-CS-2003-38
Design and Implementation of SIND, a Dynamic Binary Translator
Trek Palmer
Recent work with dynamic optimization in platform independent, virtual machine based languages such as Java has sparked interest in the possibility of applying similar techniques to arbitrary compiled binary programs. Systems such as Dynamo, DAISY, and FX$!$32 exploit dynamic optimization techniques to improve performance of native or foreign architecture binaries. However, research in this area is complicated by the lack of openly licensed, freely available, and platform-independent experimental frameworks. SIND aims to fill this void by providing an easily-extensible and flexible framework for research and development of applications and techniques of binary translation. Current research focuses are dynamic optimization of running binaries and dynamic security augmentation and integrity assurance.
TR-CS-2002-38
Security Applications of Dynamic Binary Translation
Dino Dai Zovi
The last 13 years have seen a large number of serious computer security vulnerabilities. Some of the most pernicious of these vulnerabilities have been buffer overflow and format string vulnerabilities in widely used software applications. A number of Internet worms have exploited these vulnerabilities to infect target hosts. The first part of this work introduces a framework for understanding and describing attacks that dynamically inject machine code into a process and the vulnerabilities that enable these attacks. The techniques used in these attacks are described in detail. The second part of this work describes the application of dynamic binary translation, previously a technique primarily for dynamic optimization, to stopping and mitigating these sorts of attacks. The implementations of several known techniques using a dynamic binary translation system are described in detail. Finally, some conclusions about the applicability of dynamic binary translation to computer security are made.
TR-CS-2002-37
A History and Survey of Network Firewalls
Kenneth Ingham and Stephanie Forrest
Firewalls are network devices which enforce an organization's security policy. Since their development, various methods have been used to implement firewalls. These methods filter network traffic at one or more of the seven layers of the ISO network model, most commonly at the application, transport, and network, and data-link levels. In addition, researchers have developed some newer methods, such as protocol normalization and distributed firewalls, which have not yet been widely adopted.
Firewalls involve more than the technology to implement them. Specifying a set of filtering rules, known as a policy, is typically complicated and error-prone. High-level languages have been developed to simplify the task of correctly defining a firewall's policy. Once a policy has been specified, the firewall needs to be tested to determine if it actually implements the policy correctly. Little work exists in the area of firewall theory; however, this article summarizes what exists.
Because some data must be able to pass in and out of a firewall, in order for the protected network to be useful, not all attacks can be stopped by firewalls. Some emerging technologies, such as Virtual Private Networks (VPN) and peer-to-peer networking pose new challenges for firewalls.
TR-CS-2001-38
SIND: A Framework for Binary Translation
Trek Palmer, Dino Dai Zovi, and Darko Stefanovic
Recent work with dynamic optimization in platform independent, virtual machine based languages such as Java has sparked interest in the possibility of applying similar techniques to arbitrary compiled binary programs. Systems such as Dynamo, DAISY, and FX!32 exploit dynamic optimization techniques to improve performance of native or foreign architecture binaries. However, research in this area is complicated by the lack of openly licensed, freely available, and platform-independent experimental frameworks. SIND aims to fill this void by providing a easily-extensible and flexible framework for research and development of applications and techniques of binary translation. Current research focuses are dynamic optimization of running binaries and dynamic security augmentation and integrity assurance.
TR-CS-2000-61
Automated Response Using System-Call Delays
Anil Somayaji and Stephanie Forrest
Automated intrusion response is an important unsolved problem in computer security. A system called pH (for process homeostasis) is described which can success fully detect and stop intrusions before the target system is compromised. In its current form, pH monitors every executing process on a computer at the systemcall level, and responds to anomalies by either delaying or aborting system calls. The paper presents the rationale for pH, its design and implementation, and a set of initial experimental results.
TR-CS-2000-60
Architecture for an Artificial Immune System
Steven A. Hofmeyr and Stephanie Forrest
An artificial immune system (ARTIS) is described which incorporates many properties of natural immune systems, including diversity, distributed computation, error tolerance, dynamic learning and adaptation and self-monitoring. ARTIS is a general framework for a distributed adaptive system and could, in principle, be applied to many domains. In this paper, ARTIS is applied to computer security, in the form of a network intrusion detection system called LISYS. LISYS is described and shown to be effective at detecting intrusions, while maintaining low false positive rates. Finally, similarities and differences between ARTIS and Holland's classifier systems are discussed.
News & Events | People | Academics | Research | Jobs | Companies | Visitors | Computer Facilities | Home
