SFMap: Inferring Services over
Encrypted Web Flows using
Dynamical Domain Name Graphs
TMA 2015
Tatsuya Mori1, Takeru Inoue2, Akihiro Shimoda3,Kazumichi Sato3, Keisuke Ishibashi3, and Shigeki Goto1
1 Waseda University
2 NTT Network Innovation Laboratories
3 NTT Network Technology Laboratories

Background(1) Era of web
Change of Internet traffic※WIDE Mawi Project http://mawi.wide.ad.jp,
samplepoint B, F
2002/12/1

Era of P2P

2012/12/1

Era of Web

Many of primary Internet services have shifted to1Web (http): Everything over HTTP

Background(2) Encrypting Web
Deploying HTTPS is not cost any more
Significant portion of web traffic is now encrypted

D. Naylor et al., The Cost of the “S” in HTTP. Proceedings of ACM CoNext,2014.

2

YouTube video over HTTPS!

3

Netflix started encrypting stream

Era of WebSocket

5

HTTP = non-secure!

6

ISPs need to understand traffic mix• to figure out what to control in the presenceof congestion.
– Shaping HTTP flows is too coarse-grained.
– Shaping flows from a range of IP addresses is also toocoarse-grained.

• to know demand of end-users– What types of services are consuming network resources.
→ Can be used to rethink new architecture or business model
peering policy, installing cache mechanism,
WAN optimization, CCN/ICN,• Obstacle： coping with HTTPS7

HTTP vs. HTTPS• HTTP:– HTTP header composes of URL information
http://www.example.com• HTTPS:IP
headerTCP
headerHTTP
headerHTTP
payload– Entire HTTP protocol including header isencrypted. No URL information is available.
IP
headerTCP
header

SSL/TLS encryption

8

Solution 1: Server IP addresses• Many of IP addresses can bereverse looked up (PTR record)• There are many IP addresses
that are not configured tohave PTR records.
• A single IP address can beassociated with many distinct
FQDNS (cloud, hostingservices, etc.)

9Solution 2: SSL/TLS certificates• Public key certificate of server is exchanged
during SSL/TLS handshake stage. The
certificate should contain domain name ofthe server.
• An organization can register a single
certificate for many sub-domains, i.e., socalled wildcard certificates– E.g., *.google.com
10Solution 3: SNI extension• SNI (Server Name Identification) of TLS
can be used to obtain FQDN of an
HTTPS server.
• Many of client/server implementations
have not adopted SNI, yet.
– In our dataset, roughly half of HTTPS clients
did not use the SNI extension.
11

Solution 4: Decrypting HTTPS• Anti-virus software or firewall products havemechanisms to intercept HTTPS traffic• They use self-signed certificates to work as atransparent HTTP(S) proxy.
– Same as the MTIM (Man-in-the-middle) attack– Needs for installation of certificates for each OS/application• [cf] IETF Explicit Trusted Proxy in HTTP/2.0 (I-D expired)
12

Goal
• Estimate server hostnames of HTTPS traffic– Server hostnames can be used as a good hint toestimate the services provided by the server– E.g., www.apple..com, itunes.apple.com , …

• Establish better performance than theexisting solution (DN-Hunter)
13

Idea
• Leverage DNS name resolutions thatprecedes HTTPS transactions– Labeling data plane using control plane– This is not a simple task as we will describe soon.
– [cf] state-of-the-art = DN-Hunter (IMC 2012)• Use statistical inference when measurement
is incomplete– DNS resolutions can be missed due to somereasons14

Illustration of DNS approach
DNS resolver
www.apple.com?
from 10.20.2.3

ClientC1
10.20.2.3

61.213.146.4

61.213.146.4:443 10.20.2.3:31587= www.apple.com (APPLE)HTTPS server
S1
61.213.146.4 (akamai)
NTT-COM

15

Three practical challenges:
1) CNAME tricks
2) Incomplete measurements
3) Dynamicity, diversity, and ambiguity

161) CNAME tricks• Modern CDN providers heavily make use ofCNAME tricks to optimize content distribution• We need to keep track of not only client/server IPaddresses/hostnames, but also intermediate
CNAMEse1630.c.akamaiedge.net(TTL=20)s1

23.2.132.181

m1m2

www.ieee.org(TTL=60)n1

www.ieee.org.edgekey.net(TTL=11002)
17

2) incomplete measurements• Various DNS caching mechanisms in thewild– Browser/apps– OS– Home routers w/DNS resolver– DNS resolvers (Organization/ISP/Open)• From the viewpoint of ISPs, DNS queries
originated from end-users can be missed
due to the intermediate cachingmechanisms
183) Dynamicity, diversity, andambiguity• A pathological/popular exampleObserva(on+1: n1! s1			

s1n1			

m1		 			Observa(on+2: n2! s2			s1n1			

m1			

s2		 			

n2			

19

SFMap (Service-Flow Map)
Learner
DNG
Sec 3.2
DNS
queries/ responses

Freq. Counter

Updater

input

Estimator
Sec 3.3

outputHTTPS flow
Flow key: {s, c}

Hostname, n

Sec 3.4

Learning with monitored
queries:
Building DNG (DomainName Graph)

Hostname estimation
using DNG
Use maximum likelihood
estimation whennecessary20

Illustration of DNG
A global graph(union DNG)

Per-client graphs(local DNG)

s1

n1n1

s1n2c1s2m1

n3n4

s3

c1

s2n5m1m2

s1n5s3m2

n2n3n4c2s3

c2

m2n6n621

Overview of hostnameestimation algorithm (1)• Get client/server IP addresses (C,S)
from an HTTPS flow
• Search a set of hostnames N
corresponding to (C,S) on DNG– Enumerate edge nodes N that have paths
reachable from C to S on DNG– Also consider TTL expiration• If |N| = 1, it is the estimated hostname
22

An example
s1c2
s3n5m2n6m3n7(c2, s1) à estimation = n5(c2, s3) à candidates = n6, n723

Overview of hostname
estimation algorithm (2)• If there are multiple candidates, sortthem in descending order, according tothe likelihood probabilities– Uncertain events à use frequencies• Second, third candidates can be informative– Note: The statistical inference can beextended to Bayes estimation that uses P(n)(a priori probability)24

Updating DNG• States/Statistics of DNG is updated
online when a DNS query is observed25

Dataset• LAB:– A small LAN used by research group• PROD:– Middle-scale production network

26

Scales of DNGs (12 hours long)27

Estimation accuracy (1)Exact match

UNION グラフ
UNION DNG without TTL expiration
TTL expiration 無し

Public suffix match

28

Estimation accuracy (2)Accuracies of top-3 estimations (UE-NTE)

The top-3 ranked hostnames were similar in manycases; e.g,
pagead2. googlesyndication.com
pubads.g.doubleclick.net,
googleads.g.doubleclick. net
29

Discussion• Sources of inevitable misclassification– DNS implementations that ignore TTLexpiration• It keeps holding old information– mobility• DNS could be resolved in different vantage
point– Hardcoded IP addresses• Some gaming apps did have such mechanism

30

Discussion (cont.)• Scalability– Did not matter for our datasets– Size of DNG depends on the number ofclient IP addresses• Some aging mechanism should beincorporated for much large-scale DNGs
(future work)• URL=hostname + path.
– How can we deal with path?
– Need for a standard mechanism to explicitly
expose path like SNI?
31

Summary• SFMap framework estimates hostnames(~services) of HTTPS traffic using past DNS queries• Key ideas：use of DNG and statistical inference• SFMap achieved better accuracies than thestate-of-the-art work (DN-Hunter)– Exact match: 90-92% accuracies– Public suffix match: 94-95% accuracies– Top-3 hit: 97-98% accuracies
32

Acknowledgements• This work was supported by JSPS KAKENHI Grant
Number 25880020.

33

Existing research: DN Hunter•

Bermudez et al., “DNS to the Rescue: Discerning Content andServices in a Tangled Web”, ACM IMC 201234

Comparison with DN-Hunter

DN Hunter
SFMap

Distributedmonitoring

Statisticalestimation△◯☓◯35

Distributed monitoringER

GWERCR

ER

sampledNetFlow(data-plane)
DNS
resolver

DNS(Control-plane)

SFMap

36