As one of the most fundamental Internet components, DNS has served various purposes and thus DNS traffic usually exhibits diverse patterns and is probably the least blocked by network administrators. These make DNS an attractive channel for attackers to establish surreptitious communications (i.e., DNS tunneling). In fact, such a surreptitious channel has been widely abused for command and control (C2) and enterprise-unapproved virtual private network (VPN). Existing approaches exclusively rely on the statistical characteristics of a sequence of DNS queries to detect DNS tunneling. Unfortunately, these approaches by nature cannot guarantee zero data leakage and can be evaded when the stolen data is exfiltrated over many root domains. As a result, state-of-the-art approaches are more suitable for threat investigation and forensic analysis, but not for DNS tunneling prevention. To fill this protection gap, we propose TunTight, the first system that is able to achieve in-path per-query DNS tunneling prevention. Our key insight is that DNS tunneling domains have unique characteristics in their authoritative nameservers, domain usage, and domain name patterns. Based on these characteristics, a set of unique features are defined and extracted which are fed to a machine learning model. To validate the efficacy of TunTight, we integrate it into the cloud backend of an enterprise firewall product by one of the largest security vendors. In our two-months real-world deployment, TunTight has successfully detected 349 confirmed tunnels at the very first query with negligible false positives and negatives. We also conduct the first large-scale study of DNS tunneling activities in the wild. One interesting finding is that most DNS tunneling traffic in enterprise networks come from public tunneling tools and enterprise-unapproved VPN services.

Over 55% of the world's websites run on Content Management Systems (CMS). Unfortunately, this huge user population has made CMS-based websites a high-profile target for hackers. Worse still, the vast majority of the website hosting industry has shifted to a "backup and restore" model of security, which relies on error-prone AV scanners to prompt users to roll back to a pre-infection nightly snapshot. This research had the opportunity to study these nightly backups for over 300,000 unique production websites. In doing so, we measured the attack landscape of CMS-based websites and assessed the effectiveness of the backup and restore protection scheme. To our surprise, we found that the evolution of tens of thousands of attacks exhibited clear long-lived multi-stage attack patterns. We now propose TARDIS, an automated provenance inference technique, which enables the investigation and remediation of CMS-targeting attacks based on only the nightly backups already being collected by website hosting companies. With the help of our industry collaborator, we applied TARDIS to the nightly backups of those 300K websites and found 20,591 attacks which lasted from 6 to 1,694 days, some of which were still yet to be detected.

With millions of apps available to users, the mobile app market is rapidly becoming very crowded. Given the intense competition, the time to market is a critical factor for the success and profitability of an app. In order to shorten the development cycle, developers often focus their efforts on the unique features and workflows of their apps and rely on third-party Open Source Software (OSS) for the common features. Unfortunately, despite their benefits, careless use of OSS can introduce significant legal and security risks, which if ignored can not only jeopardize security and privacy of end users, but can also cause app developers high financial loss. However, tracking OSS components, their versions, and interdependencies can be very tedious and error-prone, particularly if an OSS is imported with little to no knowledge of its provenance.

Bloom Filter is a widely used data structure in computer science. It enables memory efficient and fast set membership queries. Bloom filter-based solutions have been proposed in the past decade for lookup in forwarding tables of backbone routers [2]. However, the main shortcomings of using Bloom Filters for lookup lie in the absence of support for deletion operations that are needed to update the forwarding tables. Counting Bloom Filter supporting deletion has therefore to be used, increasing significantly the memory requirement. Moreover, Counting Bloom Filter suffers from both false positive and false negative. In this paper, we propose to solve the issue with deletion of Bloom Filters by using a Withdrawal To annOuncement (WTO) mapping that replaces withdrawal with announcements, transforming deletions into additions or record changes. Experimental evaluation show that the proposed techniques improve largely the performance of Bloom Filter used for forwarding lookup and open way for the use of Bloom Filters in real operational settings.

The sizes of routing table in backbone routers continue to keep a rapid growth and some of them currently increase up to 400K entries [1]. An effective solution to deflate the large table is the routing table compression. Meanwhile, there is an increasingly urgent demand for fast routing update mainly due to the change of network topology and new emerging Internet functionalities. Furthermore, the Internet link transmission speed has scaled up to 100Gbps commercially and towards 400Gbps Ethernet for laboratory experiments, resulting in a raring need of ultra-fast routing lookup. To achieve high performance, backbone routers must gracefully handle the three issues simultaneously: routing table Compression, fast routing Lookup, and fast incremental Update (CLUE), while previous works often only concentrate on one of the three dimensions. To address these issues, we propose a complete set of solutions-CLUE, by improving previous works and adding a novel incremental update mechanism. CLUE consists of three parts: a routing table compression algorithm, an improved parallel lookup mechanism, and a new fast incremental update mechanism. The routing table compression algorithm is based on ONRTC algorithm [2], a base for fast TCAM parallel lookup and fast update of TCAM. The second part is the improvement of the logical caching scheme for dynamic load balancing parallel lookup mechanism [3]. The third one is the conjunction of the trie, TCAM and redundant prefixes update algorithm. We analyze the performance of CLUE by mathematical proof, and draw the conclusion that speedup factor is proportional to the hit rate of redundant prefixes in the worst case, which is also confirmed by experimental results. Large-scale experimental results show that, compared with the mechanism in [3], CLUE only needs about 71% TCAM entries, 4.29% update time, and 3/4 dynamic redundant prefixes for the same throughput when using four TCAMs. In addition, CLUE has another advantage over the mechanism in [3] - the frequent interactions between control plane and data plane caused by redundant prefixes update can be avoided.

With the rapid growth of the Internet, the update messages in backbone routers become more and more frequent due to the ever-increasing dynamic changes on network topologies and new emerging functionalities of the Internet. In addition, update messages often come as a burst. Update action interrupts the packet lookup operation in the router's data plane, thus inefficient incremental update algorithm slows down IP lookup speed, and potentially badly degrades the system performance during bursty updates. Among trie-based routing lookup algorithms, binary trie has the best update complexity O(W) (W is the maximum depth of the trie), but exhibits slow lookup speed, failing to be competent for forwarding tens of gigabit-per-second traffic in backbone routers. Therefore, various improved routing lookup algorithms are proposed to pursue high speed based on binary trie, but sacrificing the performance of incremental update. To minimize the interruption time that update operation incurs, we propose Blind Spot (BS) algorithm by picking out those updating nodes which would have produced domino effect, achieving an update complexity of O(lookup+h), meanwhile keeping the lookup speed almost unchanged. Blind Spot algorithm is a universal methodology, which is applicable to all the trie-based lookup algorithms. To evaluate the performance of BS algorithm, we applied it to Lulea [1] and LC-trie [2] algorithms as two representatives. Extensive experimental results show that both Lulea+BS and LC+BS algorithms achieve a much faster update speed than binary trie, while keeping the same lookup speed as the original Lulea and LC-trie algorithms.

Virtual router research has drawn increasing attention in recent years, and the most challenging issues of virtual routers are compression, lookup, and incremental update of 10∼200 routing tables. In this paper, we propose a set of solutions to achieve that storage, lookup time, and update time don't expand to 10∼200 times, but reduce to 1∼2 times.

With the fast development of Internet, the size of routing tables in the backbone routers keeps a rapid growth in recent years. An effective solution to control the memory occupation of the ever-increased huge routing table is the Forwarding Information Base (FIB) compression. Existing optimal FIB compression algorithm ORTC suffers from high computational complexity and poor update performance, due to the loss of essential structure information during its compression process. To address this problem, we present two suboptimal FIB compression algorithms — EAR-fast and EAR-slow, respectively, based on our proposed Election and Representative (EAR) algorithm which is an optimal FIB compression algorithm. The two suboptimal algorithms preserve the structure information, and support fast incremental updates while reducing computational complexity. Experiments on an 18-month real data set show that compared with ORTC, the proposed EAR-fast algorithm requires only 9.8% compression time and 37.7% memory space, but supports faster update while prolonging the recompression interval remarkably. All these performance advantages come at a cost of merely a 1.5% loss in compression ratio compared with the theoretical optimal ratio.