Hash-Based IP Traceback
by Alex C. Snoeren, Craig Partridge, Luis A. Sanchez, Christine E. Jones, Fabrice Tchakountio, Stephen T. Kent, W. Timothy Strayer
url show details
Details
| type: | misc | | booktitle: | Proceedings of the {ACM} {SIGCOMM} 2001 Conference ({SIGCOMM}-01) | | year: | 2001 | | month: | jan # "~10 | | series: | Computer Communication Review | | annote: | Alex C. Snoeren (BBN Technologies; 10 Moulton Street | | volume: | 31, 4 | | publisher: | ACM Press | | pages: | 3--14 | | abstract: | The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, wide-spread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion. | | editor: | Roch Guerin | | address: | New York |
|
|
You need to log in to add tags and post comments.
The ability to trace back individual packet, rather than a significant flow, could be of extreme importance in some situations, because it has the potential to disable widely-used operating systems and routers. However, the trace-back task is difficult due to the anonymous of IP protocol.
The authors present a system, Source Path Isolation Engine, which enables effective, space-efficient single IP packet trace-back. They start with a clear problem definition with 8 assumptions:
• Packets may be addressed to more than one physical host
• Duplicate packets may exist in the network
• Routers may be subverted, but not often
• Attackers are aware they are being traced
• The routing behavior of the network may be unstable
• The packet size should not grow as a result of tracing
• End hosts may be resource constrained
• Traceback is an infrequent operation
The range of the deployment of the system would limit the range of the trace-back result. The goal is to trace back to an edge node or a corrupted router, if the source is not within the system. The system is able to produce the attack paths of an attack packet, leaving the work of checking the nodes on the paths one by one to others.
The system records the path of packets by taking logs on routers. It is a natural idea to use digest in order to reduce the space expenses. Furthermore, they use a space-efficient data structure called Bloom filter, which is setting k hash values of a same digest to 1 on a bitmap. A digest has occurred in a router in a specific span of time, only if the bits corresponding to the k hash values are all 1 on the bitmap. The side effect of the space-saving data structure is the false positive rate, but it could be under control when handling appropriately.
They also take into account the packet transformation, such as NAT, which is not neglectable. The path could be reverse tacked only when the packet is presented, which avoids the dangers of abuse as eavesdropping.
The overall design of the system is good and practical.
Doubts:
Is the size and time span of a bitmap going to be the same across the network?
The article presents an interesting use of hash functions for enabling traceback operations on individual IP packets with only a small overhead in the space requirement for each router. As the authors mention, the low space requirement is obtained by allowing false positive hits to occur with low probability.
In Figure 9, the authors compare the false positive hits obtained with the theoretical bound and those obtained in the simulation, which are much better. While the authors discuss informally the reason they believe to be behind the discrepancy, it would be interesting to see if a tighter theoretical analysis could better explain the false positive rates we may see in practice.
This is an interesting idea to trace back the origins of DoS attacks. The simulation results and theoretical analysis given in the paper also look reasonable. I think that the authors provided a good performance analysis of the system in terms of memory (storage) and memory access. However, I'm still wondering if the router could generate the hash value for each packet even though DGA is optimized and implemented as hardware. Although they provide a sketchy hardware design of "signature tap," and argue that it's efficient, there is no specific number given for computation power, like the number of hash operations that can be done per second. This is a really important factor to see if this design could be deployed on the backbone routers. I think this should be the most important part for the performance analysis part, but why is it missing?
Perhaps I'm missing something, but it seems that the authors reject ingress filtering too hastily. Examining the source address should take approximately the same amount of time as examining the destination address, and it can be done in parallel, so I don't think it would be too expensive. Furthermore, the core routers don't need to do anything, because the packets would have already been verified at the border routers when they entered the AS. The authors cite Mobile IP as a legimite use of spoofed addresses, but existing systems already reject these packets (although perhaps they didn't when the paper was written in 2001).
Furthermore, while detecting who spoofed a packet after the fact is better than nothing, it would be better to pro-actively recognize spoofed packets and simply reject them. Additionally, ingress filtering is much simpler than the scheme presented here, which is important for applications like this that are inherently difficult to test and debug.
I think they reject the ingress filtering because the core routers would have to trust that the packets were in fact filtered at the borders.
This technology is useful, but to have a significant role in the prevention of attacks the number of routers that implement this has to be large.Like Kang mentioned, creating an Hash for every packet at many routers may cause some level of delay.
Also i don't agree that false negatives are worst than false positives.
I agree with Will that this is really quite complicated compared to ingress filtering and as they mention many routers may lack resources for ingress filtering but they also say SPIE can only construct these graphs where it is deployed... They also claim that 1. ingress filtering can't deal with spoofed IPs 2. ingress filtering doesn't "protect" transit networks as these networks have to rely on other networks to perform filtering. I don't really see how the hashing scheme deals with these issues...
I found the paper well written. I think this, along with other work in these directions helped later systems use it as a primitive to build more powerful architectures.
The paper is well organized. The main contribution of the paper is to reduce the memory required for tracing back individual packets using what is called Source Oath Isolation Engine- SPIE.
About false positive and false negative, I think what the authors argued is not "false negative is worse than false positive"; but "false positive is unavoidable; however false negative is" instead.