Statistical Methods for Change Detection 

over Time in Digital Forensics Data

Forensics@NIST Conference, Nov 8-9 2016

Padhraic Smyth

CSAFE Project Investigator

Professor, Departments of Computer Science and Statistics

University of California, Irvine

smyth@ics.uci.edu
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 2

User Data from Digital Devices

Web clicks

Web searches

Emails 

Text messages

Social media posts

GPS locations

Documents edited

.....
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 3

Device Extraction

Tools

Raw Data

Indexing/Linking

Query/Search

Visualization

Statistical Analysis

Software Tools for Digital Forensics
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 4

From Timeline Visualization in Autopsy

J. Millman, Open Source Digital Forensics Conference, 2014
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 5

From B. Carrier, Open Source Digital Forensics Conference, 2015
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 6

Device Extraction

Tools

Raw Data

Indexing/Linking

Query/Search

Visualization

Statistical Analysis

Software Tools for Digital Forensics
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 7

Example: Time Plot of URL Request (Browser) Data
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 8

Typical Sources of User Event Data 

• Local Device

– Browser history

– Cookie files

• Cloud

– Email history (e.g., Gmail)

– Search history (e.g., Google/Chrome)

– File editing (e.g., Google Docs)

– Social Media activity

• Facebook

• Twitter

• Caveats

– User may have deleted or obfuscated data

– Cloud data may be inaccessible
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 9

User Event Data

< ID, timestamp, action type, metadata >

Web clicks

Web searches

Emails sent

Social media posts

Files edited

.....

Text content

Location

List of recipients

.....
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 10

Example of a User Event Data Set

• Chrome Browser History (local device)

– 37.9k (desktop) and 7.3k (laptop) browsing events, over 3 months

– <timestamp, URL, + more...> 

• Google Search Queries (cloud)

– 7000 searches over 2 years

– <timestamp, query string> 

• Facebook (cloud)

– Variety of time-stamped events and metadata over 7 years

• Gmail (cloud)

– Records of incoming and outgoing emails over 10 years
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 11

Timeline of Search Queries (from Cloud)

Jul 2014 Oct 2014 Jan 2015 Apr 2015 Jul 2015 Oct 2015 Jan 2016 Apr 2016

DATE

0

5

10

15

20

25

TIME OF DAY (HOURS)
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 12

Timeline of Browser URL Requests (from Desktop Device)
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 13

2012 2013

Year

0

2012 2013

Year

12 AM

6 AM

12 PM

6 PM

12 AM

Time of Day Time Plot for Emails Sent
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 14

2012 2013

Year

0

2012 2013

Year

12 AM

6 AM

12 PM

6 PM

12 AM

Time of Day Time Plot for Emails Sent

Time Plot for Emails Received
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 15

Potential Value to Forensics

• Assist in discovery process

– Detect and focus attention on time-periods of unusual behavior

– Summarize an individual’s behavioral patterns over time

– Compare how two accounts A and B differ in behavior

• Quantify answers to specific questions

– Is there evidence of a significant change in behavior at specific times?

– Is there evidence of more than 1 user in an event stream?

– Is the behavior on device X consistent with the behavior on device Y?
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 16

Changepoint Detection

Changepoint: significant change in distributional characteristics of 

a time-series, e.g., change in mean, change in variance
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 17

Changepoint 1 Changepoint 2

Segment 1 Segment 2 Segment 3
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 18

User 

Browser 

Request

Data

User 

Daily 

Counts
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 19

Statistical Approaches to Change Detection

• Assume a time-series model where unknown parameters are

– Parameters for distributions within each segment

– Number and locations of changepoints and segments

• Fit this model to the observed data and infer both

– How data is distributed within segments

– Locations of changepoints and segments

• “Chicken-and-egg” estimation problem

– Given segments, can easily estimate distributions

– Given distributions, can easily estimate location of changepoints
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 20

Example: Maximum Likelihood Detection of 1 Changepoint

3 unknown parameters: 

q2

q1
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 21

Example: Maximum Likelihood Detection of 1 Changepoint

3 unknown parameters: 

Likelihood Function: 

t

q2

q1

Maximum likelihood parameter estimates 

= values that maximize 
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 22

Example: Maximum Likelihood Detection of 1 Changepoint

Low Likelihood

t

q2

q1

High Likelihood

t

q2

q1
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 23

Approach 1: Direct Segmentation Models

• Segment Distribution

– Assume a distributional form within segments (Poisson, Gaussian, etc)

• Search for K changepoints that maximize the likelihood

– As K increases, search problem becomes combinatorially more difficult

– Requires heuristic search techniques (e.g., greedy search) for K > 1

• Problem: how to select K?

– More complex models (with larger K) always have higher likelihood

– Model selection problem, e.g.,

• Use penalized likelihood: subtract a penalty term from likelihood (AIC, BIC, etc)

• Use Bayesian techniques such as marginal likelihood
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 24

Simulated Data, Two Changepoints
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 25

Results from Bayesian Segmentation
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 26

Approach 2: Dynamic Models

• Assume that data can be explained by a dynamic model that switches 

between states, e.g., a hidden Markov model

• States = segments that can recur

– e.g., states = {work, business travel, vacation, ....}

• Differences with segmentation model

– Recurrent segments allow for borrowing of strength

– Assumes that duration in segments is Markov/geometric

– Can use dynamic programming to perform inference efficiently
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 27

Results with Bayesian Hidden Markov Model on Simulated Data
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 28

User 

Browser 

Request

Data

User 

Daily 

Counts
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 29

Changepoint Detection Results on Real-World Data
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 30

• Systematic evaluation of different approaches

– Simulated data: Compare estimated with true changepoints

– Real-world data: Compare estimated changepoints to ground truth (if known)

– Extensions to allow drift and trends in user behavior

• Additional problems

– Multiple event streams

• Change detection across streams

• Likelihood of being from the same person?

– Using timestamps in the analysis

– Incorporating additional data such as text, email recipients, etc

• Creating a realistic research data set

– Planning underway for a study at UC Irvine to create anonymized data sets 

from student participants (with permissions)

– Surrogate data sets such as Twitter or Reddit publicly available data

Ongoing Work (CSAFE)
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 31 0 50 100 150 200 250

DAY

0

5

10

15

20

25

30

35

40

NUMBER OF TWEETS

Example of Twitter Event Data over Time
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 32

URL Visits

(desktop)

URL Visits

(laptop)

Statistical question: 

Quantify the extent that these data sets 

fit the profile of a single user
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 33

Research Challenges

• Matching real-world digital forensic problems with statistical modeling

– There is a gap...

• Variability of individual behavior 

– Significant within-individual variability

– No population reference for “1 in a million” statements

• Testbed research data sets

– Privacy issues

– Ground truth
Padhraic Smyth: Event Data Analysis, Forensics@NIST, Nov 2016 34

A variety of native user data can be extracted from devices

Common data type: Events = [ user, timestamp, action, metadata]

Natural to develop tools for statistical analysis of such data

– detection of significant changes over time

– numerous potential extensions

Challenge: making these techniques useful to forensic practitioners

- interact with forensic experts

- create research data sets that others can use

- develop open-source software for adoption 

Summary