Log(Graph): A Near-Optimal High-Performance Graph Representation

Today’s graphs used in domains such as machine learning or
social network analysis may contain hundreds of billions of
edges. Yet, they are not necessarily stored efficiently, and standard
graph representations such as adjacency lists waste a
significant number of bits while graph compression schemes
such as WebGraph often require time-consuming decompression.
To address this, we propose Log(Graph): a graph representation
that combines high compression ratios with very
low-overhead decompression to enable cheaper and faster
graph processing. The key idea is to encode a graph so that
the parts of the representation approach or match the respective
storage lower bounds. We call our approach “graph
logarithmization” because these bounds are usually logarithmic.
Our high-performance Log(Graph) implementation
based on modern bitwise operations and state-of-the-art succinct
data structures achieves high compression ratios as well
as performance. For example, compared to the tuned Graph
Algorithm Processing Benchmark Suite (GAPBS), it reduces
graph sizes by 20-35% while matching GAPBS’ performance
or even delivering speedups due to reducing amounts of
transferred data. It approaches the compression ratio of the
established WebGraph compression library while enabling
speedups of up to more than 2×. Log(Graph) can improve
the design of various graph processing engines or libraries on
single NUMA nodes as well as distributed-memory systems

Source: https://people.csail.mit.edu/jshun/papers/loggraph.pdf

Sincronia: Near-Optimal Network Design for Coflows

We present Sincronia, a near-optimal network design for coflows that can be implemented on top on any transport layer (for flows) that supports priority scheduling. Sincronia achieves this using a key technical result — we show that given a “right” ordering of coflows, any per-flow rate allocation mechanism achieves average coflow completion time within 4X of the optimal as long as (co)flows are prioritized with respect to the ordering.

Sincronia uses a simple greedy mechanism to periodically order all unfinished coflows; each host sets priorities for its flows using corresponding coflow order and offloads the flow scheduling and rate allocation to the underlying priority-enabled transport layer. We evaluate Sincronia over a real testbed comprising 16-servers and commodity switches, and using simulations across a variety of workloads. Evaluation results suggest that Sincronia not only admits a practical, near-optimal design but also improves upon state-of-the-art network designs for coflows (sometimes by as much as 8X).

Source: http://delivery.acm.org/10.1145/3240000/3230569/p16-agarwal.pdf?ip=

B4 and After: Managing Hierarchy, Partitioning, and Asymmetry for Availability and Scale in Google’s Software-Defined WAN

Private WANs are increasingly important to the operation of
enterprises, telecoms, and cloud providers. For example, B4,
Google’s private software-defined WAN, is larger and growing
faster than our connectivity to the public Internet. In this
paper, we present the five-year evolution of B4. We describe
the techniques we employed to incrementally move from
offering best-effort content-copy services to carrier-grade
availability, while concurrently scaling B4 to accommodate
100x more traffic. Our key challenge is balancing the tension
introduced by hierarchy required for scalability, the partitioning
required for availability, and the capacity asymmetry
inherent to the construction and operation of any large-scale
network. We discuss our approach to managing this tension:
i) we design a custom hierarchical network topology for both
horizontal and vertical software scaling, ii) we manage inherent
capacity asymmetry in hierarchical topologies using
a novel traffic engineering algorithm without packet encapsulation,
and iii) we re-architect switch forwarding rules
via two-stage matching/hashing to deal with asymmetric
network failures at scale.

Source: http://delivery.acm.org/10.1145/3240000/3230545/p74-hong.pdf?ip=

Survivable Key Compromise in Software Update Systems

Today’s software update systems have little or no defense
against key compromise. As a result, key compromises have
put millions of software update clients at risk. Here we identify
three classes of information whose authenticity and integrity
are critical for secure software updates. Analyzing
existing software update systems with our framework, we
find their ability to communicate this information securely
in the event of a key compromise to be weak or nonexistent.
We also find that the security problems in current software
update systems are compounded by inadequate trust revocation
mechanisms. We identify core security principles that
allow software update systems to survive key compromise.
Using these ideas, we design and implement TUF, a software
update framework that increases resilience to key compromise

Source: https://www.freehaven.net/~arma/tuf-ccs2010.pdf

DeepLog: Anomaly Detection and Diagnosis from System Logs through Deep Learning

Anomaly detection is a critical step towards building a secure and
trustworthy system. Œe primary purpose of a system log is to
record system states and signi€cant events at various critical points
to help debug system failures and perform root cause analysis. Such
log data is universally available in nearly all computer systems.
Log data is an important and valuable resource for understanding
system status and performance issues; therefore, the various system
logs are naturally excellent source of information for online
monitoring and anomaly detection. We propose DeepLog, a deep
neural network model utilizing Long Short-Term Memory (LSTM),
to model a system log as a natural language sequence. Œis allows
DeepLog to automatically learn log paŠerns from normal execution,
and detect anomalies when log paŠerns deviate from the model
trained from log data under normal execution. In addition, we
demonstrate how to incrementally update the DeepLog model in
an online fashion so that it can adapt to new log paŠerns over time.
Furthermore, DeepLog constructs workƒows from the underlying
system log so that once an anomaly is detected, users can diagnose
the detected anomaly and perform root cause analysis e‚ectively.
Extensive experimental evaluations over large log data have shown
that DeepLog has outperformed other existing log-based anomaly
detection methods based on traditional data mining methodologies

Source: https://acmccs.github.io/papers/p1285-duA.pdf

Andromeda: Performance, Isolation, and Velocity at Scale in Cloud Network Virtualization

This paper presents our design and experience with Andromeda,
Google Cloud Platform’s network virtualization
stack. Our production deployment poses several challenging
requirements, including performance isolation among
customer virtual networks, scalability, rapid provisioning
of large numbers of virtual hosts, bandwidth and latency
largely indistinguishable from the underlying hardware,
and high feature velocity combined with high availability.
Andromeda is designed around a flexible hierarchy of
flow processing paths. Flows are mapped to a programming
path dynamically based on feature and performance
requirements. We introduce the Hoverboard programming
model, which uses gateways for the long tail of low bandwidth
flows, and enables the control plane to program
network connectivity for tens of thousands of VMs in
seconds. The on-host dataplane is based around a highperformance
OS bypass software packet processing path.
CPU-intensive per packet operations with higher latency
targets are executed on coprocessor threads. This architecture
allows Andromeda to decouple feature growth from
fast path performance, as many features can be implemented
solely on the coprocessor path. We demonstrate
that the Andromeda datapath achieves performance that is
competitive with hardware while maintaining the flexibility
and velocity of a software-based architecture.

Source: https://www.usenix.org/system/files/conference/nsdi18/nsdi18-dalton.pdf

PREDATOR: Proactive Recognition and Elimination of Domain Abuse at Time-Of-Registration

Miscreants register thousands of new domains every day to launch
Internet-scale attacks, such as spam, phishing, and drive-by downloads.
Quickly and accurately determining a domain’s reputation
(association with malicious activity) provides a powerful tool for mitigating
threats and protecting users. Yet, existing domain reputation
systems work by observing domain use (e.g., lookup patterns, content
hosted)—often too late to prevent miscreants from reaping benefits of
the attacks that they launch.
As a complement to these systems, we explore the extent to which
features evident at domain registration indicate a domain’s subsequent
use for malicious activity. We develop PREDATOR, an approach that
uses only time-of-registration features to establish domain reputation.
We base its design on the intuition that miscreants need to obtain
many domains to ensure profitability and attack agility, leading to
abnormal registration behaviors (e.g., burst registrations, textually
similar names). We evaluate PREDATOR using registration logs of
second-level .com and .net domains over five months. PREDATOR
achieves a 70% detection rate with a false positive rate of 0.35%, thus
making it an effective—and early—first line of defense against the
misuse of DNS domains. It predicts malicious domains when they
are registered, which is typically days or weeks earlier than existing
DNS blacklists.

Source: http://www.icir.org/vern/papers/predator-ccs16.pdf

Systematic Generation of Fast Elliptic Curve Cryptography Implementations

Widely used implementations of cryptographic primitives
employ number-theoretic optimizations specific to large
prime numbers used as moduli of arithmetic. These optimizations
have been applied manually by a handful of experts,
using informal rules of thumb. We present the first
automatic compiler that applies these optimizations, starting
from straightforward modular-arithmetic-based algorithms
and producing code around 5X faster than with off-the-shelf
arbitrary-precision integer libraries for C. Furthermore, our
compiler is implemented in the Coq proof assistant; it produces
not just C-level code but also proofs of functional
correctness. We evaluate the compiler on several key primitives
from elliptic curve cryptography

Source: https://people.csail.mit.edu/jgross/personal-website/papers/2018-fiat-crypto-pldi-draft.pdf

A Mathematical Theory of Communication

THE recent development of various methods of modulation such as PCM and PPM which exchange
bandwidth for signal-to-noise ratio has intensified the interest in a general theory of communication. A
basis for such a theory is contained in the important papers of Nyquist1 and Hartley2 on this subject. In the
present paper we will extend the theory to include a number of new factors, in particular the effect of noise
in the channel, and the savings possible due to the statistical structure of the original message and due to the
nature of the final destination of the information.

Source: http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf