On the Security of Trustee-based Social Authentications
Neil Zhenqiang Gong
~\IEEEmembership{Student Member
IEEE
Recently, authenticating users with the help of their friends (i.e., trustee-based social authentication) has been shown to be a promising backup authentication mechanism~\cite{Brainard06,Schechter09,facebookSocAuth,facebookTF. A user in this system is associated with a few trustees that were selected from the user's friends. When the user wants to regain access to the account, the service provider sends different verification codes to the user's trustees. The user must obtain at least $k$ (i.e., recovery threshold) verification codes from the trustees before being directed to reset his or her password. In this paper, we provide the first systematic study about the security of trustee-based social authentications. Specifically, we first introduce a novel framework of attacks, which we call forest fire attacks. In these attacks, an attacker initially obtains a small number of compromised users, and then the attacker iteratively attacks the rest of users by exploiting trustee-based social authentications. %Then, we propose a few concrete attack strategies to select the seed users and construct the priority ordering, and Then, we construct a probabilistic model to formalize the threats of forest fire attacks and their costs for attackers. Moreover, we introduce various defense strategies. Finally, we apply our framework to extensively evaluate various concrete attack and defense strategies using three real-world social network datasets. Our results have strong implications for the design of more secure trustee-based social authentications.
paper.tex
\PassOptionsToPackage{font=small}{caption}

\documentclass[journal]{IEEEtran}
%\usepackage{epsfig,endnotes}
\usepackage[square,sort,comma,numbers]{natbib}
\usepackage{multirow}
\usepackage{subfig}
\usepackage{graphicx}
\newcounter{copyrightbox}
\newcounter{subcopyrightbox}
\newcounter{subcopyrightbox@save}
\usepackage{caption}
\usepackage{color, url}
\usepackage{xspace} 
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage{mathrsfs}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{epstopdf}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\argmin}{\operatornamewithlimits{argmin}}

\newcommand{\myparatight}[1]{\smallskip\noindent{\bf {#1}:}~}
\newenvironment{packeditemize}{\begin{list}{$\bullet$}{\setlength{\itemsep}{2pt}\addtolength{\labelwidth}{4pt}\setlength{\leftmargin}{20pt}\setlength{\listparindent}{\parindent}\setlength{\parsep}{0pt}\setlength{\topsep}{0pt}}}{\end{list}}

\newcommand{\neil}[1]{{\small\color{red}#1}}


\begin{document}

\title{On the Security of Trustee-based Social Authentications}

\author{Neil Zhenqiang Gong,~\IEEEmembership{Student Member, IEEE} and Di Wang% <-this % stops a space
\thanks{
%Copyright (c) 2013 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org
N. Z. Gong and D. Wang are with the Electrical Engineering and Computer Science Department, University of California at Berkeley, Berkeley, CA, 94720 USA, e-mail: (neilz.gong@berkeley.edu; wangd@cs.berkeley.edu).}% <-this % stops a space
\thanks{We would like to thank Dawn Song for insightful discussions. This work is supported by the NSF under Grants No. CCF-0424422, 0842695, 0831501 CT-L, by the AFOSR under MURI Award No. FA9550-09-1-0539, by the Office of Naval Research under MURI Grant No. N000140911081, and by Intel through the ISTC for Secure Computing. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies. 
}
}


%\markboth{Journal of IEEE Transaction on Information Forensics and Security, Vol. XX, No. XX, XX}%
%{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Journals}


\maketitle



\begin{abstract}

Recently, authenticating users with the help of their friends (i.e., \emph{trustee-based social authentication}) has been shown to be a promising \emph{backup} authentication mechanism~\cite{Brainard06,Schechter09,facebookSocAuth,facebookTF}. A user in this system is associated with a few \emph{trustees} that were selected from the user's friends. When the user wants to regain access to the account, the service provider sends \emph{different} verification codes to the user's trustees. The user must obtain at least $k$ (i.e., \emph{recovery threshold}) verification codes from the trustees before being directed to reset his or her password.  


In this paper,  we provide the first systematic study about the security of trustee-based social authentications. Specifically,  we first introduce a novel framework of attacks, which we call \emph{forest fire attacks}. In these attacks, an attacker initially obtains a small number of compromised users, and then the attacker iteratively attacks the rest of users by exploiting trustee-based social authentications. 
%Then, we propose a few concrete attack strategies to select the seed users and construct the priority ordering, and 
Then, we construct a probabilistic model to formalize the threats of forest fire attacks and their costs for attackers. Moreover, we introduce various defense strategies.  Finally, we apply our framework to extensively evaluate  various concrete attack and  defense strategies using three real-world social network datasets. Our results have strong implications for the design of more secure  trustee-based social authentications.


\end{abstract}

\begin{IEEEkeywords}
Social authentication, security model, backup authentication.
\end{IEEEkeywords}
\IEEEpeerreviewmaketitle


\section{Introduction}

Web services (e.g., Gmail, Facebook, and online Bankings) today most commonly rely on passwords to authenticate users. Unfortunately, two serious issues in this paradigm are: users will inevitably forget their passwords, and their passwords could be compromised and changed by attackers, which result in the failures to access their own accounts.  

Therefore,  web services often provide users with backup authentication mechanisms to help users regain access to their accounts. Unfortunately, current widely used backup authentication mechanisms such as  security questions and alternate email addresses are insecure or unreliable or both. Previous works~\cite{Poddand96, Schechter09-oakland, Zviran90} have shown that security questions are easily guessable and phished, and that users  might  forget their answers to the security questions. A previously registered alternate email address might expire upon the user's change of school or job. For the above reasons, it is important to design a secure and reliable backup authentication mechanism. 

%backup authentication mechanisms: secret personal questions, alternate email addresses and mobile phones.
%Therefore,  web services often provide users with backup authentication mechanisms to help users regain access to their accounts, and  widely used ones are based on security questions, alternate email addresses, or mobile phones. Specifically, a user is authenticated if he or she correctly answers the security questions or can successfully access the password reset link sent to his or her previsouly registered alternate email address or can retrieve the verification code sent to his or her mobile phone. 

%backup authentication mechanisms are unreliable.
%However, these backup mechanisms are  insecure or unreliable or both. Previous work~\cite{Poddand96, Schechter09-oakland, Zviran90} has shown that security questions are easily guessable and phished and that  users themselves might  forget their answers to the security questions. A previously registered alternate email address might expire upon the user's change of school or job. Moreover, a user's acquaintances could access his or her mobile phone, and thus could easily obtain the verification code sent to the mobile phone. Therefore, it is urgent to design a secure and reliable backup authentication mechanism. 

%social authentication
Recently, \emph{trustee-based  social authentication} has attracted increasing attentions and has been shown to be a promising backup authentication mechanism~\cite{Brainard06,Schechter09,facebookSocAuth,facebookTF}. Brainard et al.~\cite{Brainard06} first proposed trustee-based social authentication and combined it with other authenticators (e.g., password, security token) as a two-factor authentication mechanism. Later, trustee-based social authentication was adapted to be a backup authenticator~\cite{Schechter09,facebookTF,facebookSocAuth}. In particular, Schechter et al.~\cite{Schechter09} designed and built a prototype of trusted-based social authentication system which was integrated into Microsoft's Windows Live ID. Schechter et al. found that trustee-based social authentication is highly \emph{reliable}. Moreover, Facebook announced its trustee-based social authentication system called \emph{Trusted Friends} in October, 2011~\cite{facebookTF}, and it was redesigned and improved to be \emph{Trusted Contacts}~\cite{facebookSocAuth} in May, 2013. 


%\begin{figure*}[!t]
%\centering
%\vspace{-4mm}
%\includegraphics[width=0.9\textwidth, height=2in]{trust_soc_auth.pdf}
%\caption{Illustration of a trustee-based social authentication system which consists of \emph{Registration Phase} and \emph{Recovery Phase}. In the Registration Phase, Alice is authenticated with the main authenticator, i.e., password, and then several friends are selected by either Alice herself or the service provider from Alice's friend list and are appointed as Alice's trustees. In the Recovery Phase, when Alice forgets her password or her password was compromised and changed by an attacker, she recovers her account with the help of her trustees.}
%\label{soc_auth}
%\vspace{-4mm}
%\end{figure*}



However, these previous work either focus on security at individual levels~\cite{Brainard06,Schechter09} or totally ignore security~\cite{facebookTF,facebookSocAuth}. In fact, security of users are correlated in trustee-based social authentications, in contrast to traditional authenticators (e.g., passwords, security questions, and fingerprint)  where security of  users are independent. Specifically, a user's security in trustee-based social authentications relies on the security of his or her trustees; if all trustees of a user are already compromised, then the attacker can also compromise him or her because the attacker can easily obtain the verification codes from the compromised trustees.  The impact of this key difference has not been touched. Moreover, none of the existing work has studied the fundamental design problems such as \emph{how to select trustees for users so that the system is more secure and how to set the system parameters (e.g., recovery threshold) to balance between security and usability}.  



\myparatight{Our work} In this paper, we aim to provide the first systematic study about the security of trustee-based social authentications. 
To this end, we first propose a novel framework of attacks that are based on the observation that users' security are correlated in trustee-based social authentications. In these attacks, an attacker initially obtains a small number of compromised users which we call \emph{seed users}. The attacker then iteratively attacks other users according to some \emph{priority ordering} of them. In an \emph{attack trial} to a user Alice, if at least $k$ trustees of Alice are already compromised, then the attacker can easily compromise Alice; otherwise the attacker can (optionally) send spoofing messages to Alice's uncompromised trustees to request verification codes, and such spoofing attacks can succeed with some probability~\cite{Schechter09}. Our attacks are similar to forest fires which start from a few points and spread among the forests. Thus, we call them \emph{forest fire attacks}. 

%They could be obtained from phishing attacks, statistical guessings, and password database leaks,  or they could be  a coalition of users who collaborate each other.  Then, the attacker iteratively attacks other users; in each \emph{attack iteration}, the attacker performs an \emph{attack trial} to each of the uncompromised users according to some priority ordering of them. In an attack trial to a user $u$, the attacker aims to obtain enough verification codes from $u$'s trustees. If a trustee is already compromised, then the attacker can easily obtain the verification code from him or her.  Otherwise the attacker can still succeed with some probability via impersonating $u$ and sending spoofing messages to the trustee~\cite{Schechter09}. Indeed, an attacker controlling a botnet can easily send out billions of email messages per day with very low costs~\cite{emailcost}. However, we also want to stress that retrieving verification codes via spoofing attacks is \emph{optional}. We call our attacks \emph{forest fire attacks}  since they are similar to forest fires which start from a few points and spread among the forests. 

Second, we construct a probabilistic model to formalize the threats of forest fire attacks and their costs for attackers. For each user, our model computes the \emph{compromise probability} that the user is compromised after a given number of attack iterations. With those compromise probabilities, our model calculates the \emph{expected number of compromised users} and treats it as the threat. Moreover, our model quantifies the costs of sending spoofing messages for attackers. 
% Our model makes it possible to compare different concrete attacks, defenses, and system parameter settings \emph{quantitatively}. 

Third,  we explore various scenarios where seed users have different properties and introduce strategies to  construct priority orderings. For instance, one scenario could be that  seed users happen to be appointed as trustees of a large number of users. Furthermore, we discuss a few defense strategies. For example, one strategy is to guarantee that no user is appointed as a trustee of a large number of users.


%Third,  we  prove that it is NP-Complete for attackers to find the optimal set of seed users and the optimal priority ordering to maximize the expected number of compromised users. Nevertheless, we explore various scenarios where the seed users have different properties and introduce two strategies to  construct the priority orderings. For instance, one scenario could be that compromised seed users happen to be appointed as trustees of a large number of users. One strategy to construct the priority ordering is to assign higher priority to users whose compromise probabilities will change more because attacking them will increase the compromise probabilities of other users more.

%Fourth, we explore various mitigation/defense strategies such as educating trustees to share verification codes via phones or meeting in person instead of emails/messages and constraining the selection of trustees for users. For instance, we introduce two categories of trustee selection strategies. They are \emph{local trustee selection strategies} and \emph{global trustee selection strategies}. To select trustees for a user $u$, the local trustee selection strategies only use $u$'s local social network structure while the global trustee selection strategies constrain the trustee selections via a global constraint.  

\myparatight{Results and impact of our work} 
%Our probabilistic security model can be used by operators to estimate the security of their trustee-based social authentication systems. In our work, 
We apply our framework to extensively evaluate various concrete attack scenarios, defense strategies, and the impact of system parameters using three real-world social networks. First, we find that forest fire attack is a potential big threat. In particular, when all the users with at least 10 friends in these social networks  adopt trustee-based social authentications,
%\footnote{We choose the threshold 10 to guarantee that users have enough friends from which trustees can be selected, and 15\%, 21\%, and 31\% of  users in the studied social networks are such users, respectively. Note that we do not know how many Facebook users have adopted Facebook's trustee-based social authentication, so we cannot estimate the threat to Facebook.} 
 an attacker can compromise tens of thousands of users in some cases even if the number of seed users is 0; using a small number (e.g., 1,000) of seed users, the attacker can further compromise two to three orders of magnitude more users with low (or even no) costs of sending spoofing messages. Second, our defense strategy, which guarantees that no users are selected as trustees by too many other users, can decrease the expected number of compromised users by one to two orders of magnitude and increase the costs for attackers by a few times in some cases. Third, we find that, in contrast to existing work~\cite{Schechter09,facebookSocAuth,facebookTF} where the recover threshold is set to be three, it could be set to be four to better balance between security and usability. 

%\myparatight{Note} In this paper, we focus on trustee-based social authentications, and we abbreviate them as social authentications in the following. 
 
%we introduce novel attacks to social authentication and their defenses. In our attacks, the adversary first compromises a small number of users, which we call  \emph{seed users},  through phishing attacks or statistical guessing or bribing (e.g., paying the users). Then, the adversary can further iteratively compromise other users starting from the  seed users. For instance, if all trustees of a user $u$ are already compromised, then the adversary can also compromise $u$ since he or she can easily obtain verification codes from $u$'s compromised trustees. These attacks are like forest fires spreading among a \emph{trustee network} in which nodes are users and a directed edge $(v,u)$ represents $v$ is a trustee of $u$. Thus, we call our attacks as \emph{forest fire attacks}. The challenges for the adversary include locating seed users to compromise if he or she only has limited resources (e.g., computing resources and money used to bribe users) to compromise a limited number of them, and constructing  a priority ranking for the rest of users, according to which the adversary performs attacks.  Moreover, from the perspective of defenders (i.e., users or service providers), it's unclear how to set the system parameters (e.g., the number of trustees) and how to construct the trustee network from a social network (i.e., select trustees from users' friends) so that the number of nodes compromised by forest fire attacks can be minimized.

%Our contributions.
In summary, our key contributions are as follows:

\begin{packeditemize}
\item We propose a novel framework of attacks, which we call \emph{forest fire attacks}. 


\item We construct a model to formalize the threats of forest fire attacks and their costs for attackers. Moreover, we explore various attack scenarios and defense strategies.  

\item We apply our framework to extensively evaluate these attack scenarios, defense strategies, and the impact of system parameters using three real-world social networks. Our results have strong implications for designing more secure trustee-based social authentications.

\end{packeditemize}
 
%First, we propose a novel family of attacks, which we call  \emph{forest fire attacks}. In these attacks, an attacker initially compromises a small number of users, from which the attacker iteratively compromises other users.
%Second, we propose a model to quantify the threat of forest fire attacks. 
%Third, we 

%Formal Security model, 
%new attacks, forest fire attacks, and defense strategies
%evaluation on real-world social network datasets, and having implications for the design of secure 


%Specifically, we first propose a model to formalize the forest fire attacks and design efficient algorithms to  calculate the expected number of compromised nodes for a given social authentication system. Second, we introduce several attack strategies selecting the seed users to compromise, and several defense strategies constructing the trustee network from a social network. Third, we perform extensive evaluations on three social networks. We find that, from the perspective of game theory, the attack strategy that selects the seed users who are the most frequently appointed as trustees and the defense strategy that constructs the trustee network whose maximum outdegree is minimized are in Nash equilibrium.  Moreover, there exist phase transition points for all system parameters (e.g., the number of trustees and the number of compromised seed users), beyond which forest fire attacks can compromise all the users in a social network, and the secure regions (i.e., the set of parameter settings that don't lead to phase transitions) only occupy a small portion of the entire parameter space. Our observations imply that service providers should carefully calculate the secure regions of their social authentication systems and guarantee that system parameters are set to be in the secure regions.  


%paper organization
%The rest of paper is organised as follows.   
%Recently, authenticating users using whom they know as a last-resort authentication is attracting increasing attentions. These so-called \emph{social authentication systems} can be implemented in two general ways, i.e., question-based social authentication systems and trustee-based social authentication systems. Kim et al.~\cite{Kim12-soc-auth} analyzed the current Facebook's photo-based social authentication system, a special case of question-based system, and concluded that it's not secure. Schechter et al.~\cite{Schechter09} performed user studies on a trustee-based social authentication system. In this paper, we provide security analysis about trustee-based social authentication systems. 



\section{Background}
First, we overview how a trustee-based social authentication system works. Then, we introduce two basic concepts, i.e., 
\emph{social networks} and  \emph{trustee networks}.

\subsection{Trustee-based social authentications}

A trustee-based social authentication includes two phases:
\begin{packeditemize}
\item {\bf Registration Phase.} The system prepares trustees for a user Alice in this phase. Specifically, Alice is first authenticated with her main authenticator (i.e., password), and then a few (e.g., 5) friends, who also have accounts in the system, are selected by either Alice herself or the service provider from Alice's  friend list and are appointed as Alice's trustees. 
%This registration phase is important for the security of trustee-based social authentications. For more discussions, please refer to Section~\ref{sec:discussion}.
\item {\bf Recovery Phase.} When Alice forgets her password or her password was compromised and changed by an attacker, she recovers her account with the help of her trustees in this phase. Specifically, Alice first sends an account recovery request with her \emph{username} to the service provider which then shows Alice an URL. Alice is required to share this URL with her trustees. Then, her trustees authenticate themselves into the system and retrieve verification codes using the given URL.  Alice then obtains the verification codes from her trustees via emailing them, calling them, or meeting them in person. If Alice obtains a sufficient number (e.g., 3) of verification codes and presents them to the service provider, then Alice is authenticated and is directed to reset her password. We call the number of verification codes required to be authenticated the \emph{recovery threshold}. 
\end{packeditemize}

Note that it is important for Alice to know who her trustees are in the Recovery Phase.  Schechter et al.~\cite{Schechter09} showed that users cannot remember their trustees via performing user studies. Thus, a usable trustee-based social authentication system should remind Alice of her trustees. 

%\myparatight{Alternate implementation of the Recovery Phase} Another way to implement the Recovery Phase is as follows: the service provider directly sends verification codes to the predefined trustees when receiving an account recovery request, in contrast to asking Alice to share the URL with her trustees and they request the verification codes using the given URL; then the trustees actively share the verification codes to Alice. In such implementation, we don't need to remind Alice of her trustees. 
%
%However, such implementation could annoy both Alice and her trustees and is vulnerable to Denial-of-Service (DoS) attacks. First, anyone (e.g., Alice's friends or classmates) who knows Alice's username can frequently send account recovery requests to the service provider which immediately sends the verification codes to Alice's trustees, and the trustees will (possibly) frequently share the codes with Alice,  which could be annoying  to both Alice and  her trustees. More seriously,  after Alice's trustees realize that the verification codes are just spams, they might not actively share the verification codes with Alice even if Alice is really trying to recover her account.


%Note that the service provider sends the verification codes to the accounts in the service of the trustees in a trustee-based social authentication. In Section~\ref{sec:defense_strategy}, we will propose a new trustee-based social authentication mechanism called \emph{cross-site social authentication}, in which the service provider sends verification codes to accounts in an auxiliary service of the trustees. Moreover, we will show that a cross-site social authentication system is more secure than a conventional trustee-based social authentication system in Section~\ref{sec:eva}. 
  
%Thus, we will focus on the implementation shown in Figure~\ref{soc_auth}. 

Next, we provide details about two representative trustee-based social authentication systems which were implemented by Microsoft~\cite{Schechter09} and Facebook~\cite{facebookSocAuth,facebookTF}, respectively.

\myparatight{Microsoft's trustee-based social authentication} Schechter et al.~\cite{Schechter09} designed and built a  trustee-based social authentication system and integrated it into Microsoft's Windows Live ID service. In the Registration Phase, users provide \emph{four} trustees. The recovery threshold is \emph{three}. Moreover, users will be reminded of their trustees. 

\myparatight{Facebook's trustee-based social authentication} Facebook's trustee-based social authentication system is called \emph{Trusted Friends}~\cite{facebookTF}, whose improved version is \emph{Trusted Contacts}~\cite{facebookSocAuth}. In the Registration Phase of Trusted Contacts, a user selects \emph{three to five} friends from his or her friend list as trustees. The recovery threshold is also set to be \emph{three}. Facebook does not remind a user of his or her trustees, but it asks the user to type in the names of his or her trustees instead. However, once the user gets one trustee correctly, Facebook will remind him or her of the remaining trustees. 

Both trustee-based social authentication systems ask users to select their own trustees without any constraint. In our experiments (i.e., Section~\ref{sec:eva}),  we show that the service provider can constrain trustee selections via imposing that no users are selected as trustees by too many other users, which can achieve better security guarantees. Moreover, none of these work performed rigorous studies to support the choice of three as the recovery threshold. In fact, our experimental results show that setting the  recovery threshold to be four could better balance between security and usability.

%\subsection{Trust Social Networks}
%\label{sec:social_network}
%%Users in a service (e.g., Facebook, Gmail, and Twitter) are essentially linked as a social network. We consider undirected social networks and denote a social network as $G=(V,E)$, where each node in $V$ corresponds to a user in the service and an undirected edge $(u,v)$ represents trust relationship between users $u$ and $v$. 
%
%%The service provider could obtain or approximate the trust social network in two ways. One way is that the service provider enables the users to list other users as their trusted friends. The second way is to infer users' friends. For instance, the provider of an email service could infer two users to be friends if the number of emails exchanged between them is larger than some threshhold.   
%
%To increase the usability and security of a trustee-based social authentication, it is crucial to obtain a trust social network whose edges represent trust relationships between users and to select trustees from the trust social network. The trust social network could be obtained or approximated in two ways. One way is that the service provider enables the users to list other users as their trusted friends~\cite{sybildefender}.  The second way is to approximate trust relationships through replacing online friendships (e.g., friendships in online social networks) with interactions~\cite{wilson:eurosys09} and inferring tie strengths~\cite{gilbert:chi09}.
%
%
%From the perspective of usability, trusted friends might be more responsive so that it's easier for a user to obtain verification codes from them. From the perspective of security, trusted friends might be less likely to collaborate with each other to attack or prank the user.  
%
%In the following,  we consider undirected trust social networks and denote a trust social network as $G=(V,E)$, where each node in $V$ corresponds to a user in the service and an undirected edge $(u,v)$ represents trust relationship between users $u$ and $v$. 

%For instance, each user in online social network sites such as Facebook and Google+ and instant messaging services such as MSN and Skype could have a list of friends. The second way is to infer users' friends. For instance, the provider of an email service could infer two users to be friends if the number of emails exchanged between them is larger than some threshhold.   
 
%$G=(V,E)$
%Suppose we have a trust social network among users, where nodes are users and edges represent trust relationships between them. Through the following analysis, we will find that the trust relationships are essential for this trustee-based social authentication system to work. 
%%Note that friendship networks constructed from users' friendlists in online social networks (e.g., Facebook, Google+) shouldn't be considered as trust networks. 
%In practice, the trust relationship networks could be obtained or approximated via several ways. For instance, online social network operators (e.g., Facebook Inc., Google Inc.) could ask an user to mark a list of trusted friends. Furthermore, trust networks could be approximated by friendship networks, user interaction networks~\cite{wilson:eurosys09} or networks with only strong ties~\cite{gilbert:chi09}. 


\begin{figure*}[!t]
\centering
\vspace{-4mm}
\includegraphics[width=0.95\textwidth, height=2in]{forest_fire_attack.pdf}
\caption{Illustration of a forest fire attack to a service with 6 users. The shown graph is the trustee network. Recovery threshold is three. Users $u_5$ and $u_6$ have adopted the trustee-based social authentication.   The attack ordering is $u_6,u_5,u_4$. (a) $u_1, u_2$, and $u_3$ are compromised seed users. (b) $u_6$ is compromised because three of his or her trustees are already compromised. (c) $u_5$ is compromised because the attacker already compromises his or her trustees $u_3$ and $u_6$ and obtains a verification code from $u_4$ via spoofing attacks. (d) $u_4$ is not compromised because he or she hasn't adopted the service.}
\label{forest_fire_attack}
\vspace{-4mm}
\end{figure*}


\subsection{Social networks and trustee networks}
We denote a social network as $G=(V,E)$, where each node in $V$ corresponds to a user in the service and an undirected edge $(u,v)$ represents that users $u$ and $v$ are  friends. Moreover, in a trustee-based social authentication system,  users and their trustees  form a directed network. We call this directed network a \emph{trustee network} and denote it as $G_T=(V_T, E_T)$, where a node in $V_T$ is a user in the service and a directed edge $(v,u)$ in $E_T$ means $v$ is a trustee of $u$. 

One fundamental challenge in trustee-based social authentication is how to construct the trustee network from a social network so that the system is more secure. 


%Furthermore, both systems don't provide theoretical reason why choosing threshold three.

%Depending on how the service provider sends the verification codes to Alice's trustees, we consider two representative classes of trustee-based social authentications:
%
%\begin{itemize}
%\item {\bf Cross-site social authentication} involves multiple services. For instance, Facebook's current social authentication is a cross-site social authentication.  In Facebook, each user is associated  with an email address (e.g., a gmail address), and Facebook sends verification codes to the corresponding email addresses of the trustees. Retrieving the verification codes thus involves the service of 
%\item {\bf Single-site social authentication}
%\end{itemize} 
% this cross-site social authentication is a pretty cool idea which can reduce the number of compromised accounts a lot, I guess. 


%In a high-level introduction, each user has $m$ trusted friends as his or her notaries, and one user is authenticated if $k$ out of the $m$ notaries are authenticated. More specifically, we first introduce the trust social networks among users and how to obtain/approximate them in pratice. Second, we discuss when and how to select notaries given a (approximate) trust social network.   
%%Third, we introduce a new concept \emph{trustee network} to describe the trustee relationships between users. 
%Finally, given a set of notaries for an user, we discuss two protocols to authenticate him or her with helps from these notaries.   



\section{Threat Model}

We first introduce attackers' background knowledge and then a novel family of attacks which we call  \emph{forest fire attacks}.

\subsection{Background knowledge}
We assume that attackers know the trustee network in the target service. The reasonableness of this threat model is supported by two evidences. First, attackers can obtain users' usernames. A username is usually a string of letters, digits, and special characters. Moreover, Bonneau et al.~\cite{UserProbing-Bonneau10} showed that a majority (e.g., 96\% in their studies) of websites enable attackers to probe if a string is a legitimate username. Thus, strong attackers, who have enough resources (e.g., a botnet) to perform username probings,  can obtain all usernames in the target service. Second, Schechter et al.~\cite{Schechter09} found, via performing user studies,  that users cannot remember their own trustees. Therefore, a usable trustee-based social authentication system must remind users of their trustees. Recall that an account recovery request only requires a username.  As a result, an attacker could send account recovery requests with the collected usernames to the service provider which reminds the attacker of the trustees of each user. 

%Moreover, if the attacker can only obtain the trustee network among a portion of users in the service, he or she can focus on attacking those users. 
Next, we take Facebook as an example to show how an attacker obtains the trustee network. First, Facebook provides an interface\footnote{\url{https://www.facebook.com/login/identify?ctx=recover}} to test if a user (represented by a username, real name, or email address) is in Facebook. Thus, the attacker can perform username probings to collect Facebook users. Second, the attacker sends account recovery requests to Facebook using the collected names. Recall that Facebook shows  all trustees to a user once the user correctly types in one trustee. Moreover, Bilge et al. [4] showed that an attacker can obtain friend lists of around 90\% of Facebook users. Thus, the attacker can repeatedly guess the trustees of a user until success. We note that Facebook only allows a user to try around 10 times for typing in the trustees within a short period of time. However, such rate limit cannot prevent a strong attacker from obtaining the trustee network eventually, though it can increase the attacker's cost. 


%Next, we take Facebook as an example to show how an attacker obtains the trustee network. First, an attacker can obtain Facebook's users using a combination of the following two methods. One method is to perform user probing.  Facebook actually provides an interface\footnote{\url{https://www.facebook.com/login/identify?ctx=recover}} to test if a user (represented by a username, real name, or email address) is in Facebook. Thus, strong attackers can enumerate possible real names in the world and test if they are in Facebook. The other method for the attacker is to register an account in Facebook, and then the attacker designs a crawler to obtain users. Since a large fraction of Facebook users (e.g., 47\% shown by Bilge et al.~\cite{Bilge09}) have their friend lists publicly available,  the attacker can start from some high-degree nodes and use breadth-first search to crawl a large fraction of users. Note that the fraction of Facebook users that could potentially be crawled by the attacker  is much larger than 47\% because each user in Facebook has around 240 friends on average as of October, 2013~\cite{facebookstat13}. 

%Second, the attacker sends account recovery requests to Facebook using the collected names. Facebook currently does not remind the user of the trustees (this dramatically decreases the usability according to Schechter et al.~\cite{Schechter09}), but it asks the user to type in the trustees and it does show all the trustees to the user once the user gets one trustee correctly.  Bilge et al. [4] showed that attackers can obtain friend lists of around 90\% of Facebook users via \emph{cloning attacks}. So the attacker can repeatedly guess the trustees of a user until success. Note that Facebook currently only allows a user to try around 10 times for typing in the trustees within a short period of time. However, such rate limit cannot prevent a strong attacker from obtaining the trustee network eventually, though it can increase the attacker's cost. 


%Furthermore, the attacker can crawl users' interaction data (e.g., commenting or liking each other's posts, photos, etc.) and profile information to approximate trusts between users~\cite{gilbert:chi09}, which can further increase the success probability of guessings and thus speed up the process of obtaining the trustee network.   

%Furthermore, in some services such as Facebook, attackers can test if a such string is a legitimate username in the service\footnote{\url{https://www.facebook.com/login/identify?ctx=recover}}. Thus, attackers can obtain all usernames in the service. Moreover, via performing a user study, Schechter et al.~\cite{Schechter09} found that users cannot remember their own trustees.  Therefore, a usable trustee-based social authentication system must remind users of their trustees. As a result, an attacker could impersonate the users and send account recovery requests with the usernames to the service provider which reminds the attacker the trustees of the users. So attackers can obtain the trustee network among the users.    


%\myparatight{Defenders} Defenders could be users themselves or the service providers. First, we assume that a user selects his or her trustees based on his or her personal social network, i.e., the network consisting of the user and his or her friends and the edges between them. Second, the service provider can obtain the social network of all users in the service. 



%\subsection{Secure communication channels}
%We assume that all communication channels involved in a trustee-based social authentication system illustrated in Figure~\ref{soc_auth} are secure. For instance, the communication channel (e.g., SSL/TLS) used to send the verification codes from the service provider to the trustees is secure so that the attackers cannot eavesdrop the verification codes.  



\subsection{Forest fire attacks}
\label{sec:forest_fire_attack}
Our forest fire attacks consist of  \emph{Ignition Phase} and \emph{Propagation Phase}. 
%We call our attacks as forest fire attacks because they are similar to forest fires which start from one or a few points (i.e., Ignition Phase) and propagate among the forests (i.e., Propagation Phase). 

\myparatight{Ignition Phase} In this phase, an attacker obtains a small number of compromised users which we call  \emph{seed users}. They could be obtained from phishing attacks, statistical guessings, and password database leaks, or they could be a coalition of users who collude each other.  Indeed, a large number of social network accounts were reported to be  compromised,\footnote{For instance, Gao et al.~\cite{Gao10} showed that around 57,000 out of 3,500,000 (1.6\%) Facebook accounts were compromised.}  showing the feasibility of obtaining compromised seed users. 
% and the attacker could simply buy  them online from underground markets with a low price~\cite{buyaccounts}. 
%We will explore the impact of different sets of seed users on the threats of forest fire attacks and the costs for attackers in our experiments.  

% via bribing (e.g., paying the users) or phishing attacks or statistical guessing. In practice, an attacker could only compromise a small number of seed users because of a limited budget. For instance, if the attacker has \$100,000 to bribe users, and each user will collaborate with the attacker with a bribing price \$100, then the attacker can only compromise 1000 users. One challenge for the attackers is how to select the seed users given the limited budgets. 

\myparatight{Propagation Phase} Given the seed users, the attacker iteratively attacks other users. In each \emph{attack iteration}, the attacker performs one \emph{attack trial} to each of the uncompromised users  according to some \emph{attack ordering} of them. In an attack trial to a user $u$, the attacker sends an account recovery request with $u$'s username to the service provider, which issues different verification codes to $u$'s trustees. The goal of the attacker is to obtain verification codes from at least $k$ trustees. If at least $k$ trustees of $u$ are already compromised, the attacker can easily compromise $u$; otherwise, the attacker can impersonate $u$ and send a spoofing message to each uncompromised trustee of $u$ to request the verification code. Schechter et al.~\cite{Schechter09} found that such spoofing attacks can successfully retrieve a verification code with an average probability around 0.05. 

%Once the number of verification codes obtained by the attacker is no smaller than the recovery threshold, the user $u$ is compromised. For a trustee $v$ of $u$, the attacker can easily obtain the verification code from $v$ if $v$ is already compromised. If $v$ is not compromised yet,  the attacker can impersonate the user $u$ and send a spoofing message to request  the verification code from $v$. Note that such spoofing attacks are feasible since the attacker can obtain usernames of the trustees. For instance, if the web service is an email system, then the usernames are enough to locate the email addresses of a user's trustees and the attacker can send spoofing emails to them; if the web service is online social networking, the attacker can register an account in the service and send spoofing messages to the trustees\footnote{Online social networking sites (e.g., Facebook) often enable users to exchange messages within the sites.}.  Moreover, via performing user studies, Schechter et al.~\cite{Schechter09} found that such spoofing attacks can successfully retrieve a verification code with an average probability around 0.05. 


\begin{table*}[!t]\renewcommand{\arraystretch}{1}
\centering
\vspace{-4mm}
\caption{Representative notations used in our model.}
\begin{tabular}{|l|l|} \hline 
{\small  Notations} & {\small Definitions} \\ \hline
{\small $G=(V,E)$} & {\small The trust social network among the users in the service} \\ \hline
{\small $G_T=(V_T,E_T)$} & {\small The trustee network among the users in the service } \\ \hline
{\small $V_a$} &{\small  The set of users who adopt the trustee-based social authentication service} \\ \hline
{\small $u$} &{\small  A user in the service} \\ \hline
{\small $\Gamma(u)$} &{\small  The set of friends of $u$} \\ \hline
{\small $\Gamma_T(u)$} &{\small  The set of trustees of $u$} \\ \hline
{\small $\Gamma_{T,o}(u)$} &{\small  The set of users who select $u$ as a trustee} \\ \hline
{\small $d_{o}(u)$} &{\small  The number  of users who select $u$ as a trustee} \\ \hline
%{\small $d(v,u)$} &{\small  The length of the shortest directed path whose tail is $v$ and whose head is $u$} \\ \hline
{\small $m_u$} &{\small  The number of trustees of  $u$} \\ \hline
{\small $k$} &{\small  Recovery threshold, i.e., $u$ is authenticated if $u$ obtains verification codes from $k$ of $m_u$ trustees}  \\ \hline
{\small $n_s$} & {\small The number of seed users compromised in the Ignition Phase} \\ \hline
{\small $S$} & {\small The set of seed users that are compromised in the Ignition Phase} \\ \hline
{\small $\mathcal S$} &{\small  The strategy to select the seed users}\\ \hline
{\small $n$} & {\small The number of attack iterations in the Propagation Phase} \\ \hline
{\small $O^{(t)}$} & {\small The  attack ordering according to which the attacker performs attack trials to the users in the $t$th attack iteration} \\ \hline
{\small $\mathcal O$} & {\small The ordering construction strategy} \\ \hline
%{\small $A$} & {\small The event that the attacker obtains a verification code from a trustee $v$ of $u$ when attacking $u$} \\ \hline
%{\small $B$} & {\small The event that the trustee $v$ of $u$ is already compromised when the attacker attacks $u$} \\ \hline
{\small $p_s^{(t)}(v,u)$} & {\small The probability of obtaining a verification code from $u$'s trustee $v$ via spoofing attacks in the $t$th attack iteration} \\ \hline
{\small $p_s$} & {\small Average spoofing probability} \\ \hline
{\small $p_c^{(t)}(u)$} &{\small  The probability that $u$ is compromised in the $t$th attack iteration}  \\ \hline
{\small $p_c^{(t)}(V_T)$} & {\small The vector of compromise probabilities of all users in the  $t$th attack iteration} \\ \hline
{\small $p_a^{(t)}(u)$} & {\small The probability that $u$ is compromised in at least one attack iteration after $t$ attack iterations} \\ \hline
{\small $p_a^{(t)}(V_T)$} &{\small The vector of aggregate compromise probabilities of all users after  $t$ attack iterations} \\ \hline
{\small $n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$} & {\small The expected number of compromised users} \\ \hline
{\small $c_I$} & {\small The cost of obtaining the set of compromised seed users in the Ignition Phase} \\ \hline
{\small $c^{(t)}(u)$} & {\small The expected number of spoofing messages that are sent in the attack trial to $u$ in the $t$th attack iteration} \\ \hline
{\small $c_e$} & {\small The average cost per spoofing  message} \\ \hline
{\small $c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$} & {\small The expected cost} \\ \hline
{\small $p_r^{(t)}(u)$} & {\small The recovery probability of $u$ in the $t$th attack iteration} \\ \hline
{\small $p_r$} & {\small Average recovery probability} \\ \hline
\end{tabular}
\label{notation}
\vspace{-2mm}
\end{table*}


Although the spoofing attacks can help attackers compromise more users, we want to stress that they are \emph{optional}. We will show in our experiments that an attacker can still compromise a large number of users even if he does not use spoofing attacks to retrieve verification codes in some cases. 


\myparatight{Example} Figure~\ref{forest_fire_attack} shows a forest fire attack to a service with 6 users.  Note that a good attack ordering can increase the probability that users are compromised and decrease the number of required spoofing messages (see our experimental results in Section~\ref{sec:eva}). In our example, if the attacker performs attack trials with an attack ordering of $u_5, u_6, u_4$, the attacker needs to spoof both $u_4$ and $u_6$ to compromise $u_5$, which requires two spoofing messages. However, with the attack ordering of $u_6, u_5, u_4$, the attacker only needs to spoof $u_4$ to compromise $u_5$, which only requires one spoofing message and could succeed with a higher probability. 
%two (i.e., $u_5$ and $u_6$) of which have adopted the trustee-based social authentication service. In the Ignition Phase, $u_1,u_2$, and $u_3$ are  compromised seed users. In the Propagation Phase, the attacker performs one attack iteration, in which the attacker performs attack trials to the remaining users according to the attack ordering of $u_6, u_5, u_4$. 



\myparatight{Compromised users could be recovered} Users could recover their compromised accounts to be uncompromised after they or the service provider detect suspicious activities of the accounts. For instance, a trustee of $u$ receiving a spoofing message might report to $u$, who then changes his or her password; the phenomenon that a trustee requests lots of verification codes for different users within a short period of time is a possible indicator of forest fire attacks, and the service provider could then notify the users, whose trustees have requested verification codes, to change passwords. Moreover, a recovered account could be compromised again in future attack iterations, e.g., when the trustees of the recovered user are still compromised. The process of being compromised and being recovered could repeat for many attack iterations.  


\section{Security Model}
\label{sec:model}
In this section, we introduce our security model to formalize the threats  of forest fire attacks and their costs for attackers. 
%The costs are the number of spoofing emails that an attacker needs to send.  
 Table~\ref{notation} summarizes our important notations.

\subsection{Formalizing threats}
We use $\Gamma_T(u)$ and $m_u=|\Gamma_T(u)|$ to denote the set of trustees and the number of trustees of $u$, respectively. We denote by $\Gamma_{T,o}(u)$ the set of users who select $u$ as a trustee.   We model a set of seed users (denoted as $S$) is obtained by a \emph{seed users selection strategy}, and we denote it as $\mathcal S$. In the $t$th attack iteration, the attacker performs attack trials to uncompromised users according to an attack ordering $O^{(t)}$. The attack orderings are constructed by an \emph{ordering construction strategy} which is denoted as $\mathcal O$. 

We call the probability that $u$ is compromised in the $t$th attack iteration \emph{compromise probability}, and we denote it as $p_c^{(t)}(u)$. $u$ is eventually compromised if it is compromised in at least one attack iteration. Thus, we denote by $p_a^{(t)}(u)$ the probability that $u$ is compromised after $t$ attack iterations, and $p_a^{(t)}(u)$ is called \emph{aggregate compromise probability}. The compromise probabilities in the $t$th attack iteration depend on the aggregate compromise probabilities after $(t-1)$ attack iterations. Moreover, we use $p_c^{(t)}(V_T)$ and $p_a^{(t)}(V_T)$ to represent the vectors of compromise probabilities and aggregate compromise probabilities of all users in $V_T$, respectively. 

Algorithm~\ref{alg:forest_fire_attack} shows our model of forest fire attacks. 
%Note that, in our model, the attacker constructs the attack ordering using the current aggregate compromise probabilities in each attack iteration since the best attack orderings in different attack iterations might be different. 
 Next, we elaborate the iterative computations of compromise probabilities and aggregate compromise probabilities. 

\subsubsection{Ignition Phase} If $u$ is a seed user, then $u$'s initial compromise probability is 1, otherwise we model $u$'s initial compromise probability as 0. Formally,  we have the initial compromise probability of  $u$ as follows:
\begin{align}
p_a^{(0)}(u)=p_c^{(0)}(u)=
\begin{cases}
1 \text{ if } u\in S \\
0 \text{ otherwise}
\end{cases}
\label{pc_ignition_phase}
\end{align}

%Note that, in our model, we don't consider the scenario where a user that is not a seed user could also be compromised via various attacks such as statistical guessing attacks and phishing attacks with some probability. This is because such probabilities have no impacts on the threats of forest fire attacks and their defenses.  

\subsubsection{Propagation Phase} 
The key component is to update the aggregate compromise probability of $u$ when the aggregate compromise probabilities of $u$'s trustees are given.

\myparatight{Obtaining one verification code}
 We denote by $A$ the event that the attacker obtains a verification code from a trustee $v$ of $u$ and by $p^{(t)}(v,u)$ the probability that $A$ happens in the $t$th attack iteration. Moreover, we denote the event that $v$ is already compromised when the attacker attacks $u$ in the $t$th attack iteration as $B$. Then we can represent $p^{(t)}(v,u)$ as: 
\begin{align}
\label{equ:one_code_event}
p^{(t)}(v,u)&=Pr(A) \nonumber \\
		&=Pr(A|B)Pr(B) + Pr(A|^\lnot B)Pr(^\lnot B) 
\end{align}
, where $^\lnot B$ represents that $B$ does not happen. Next, we model $Pr(A|B)$, $Pr(B)$, $Pr(A|^\lnot B)$, and $Pr(^\lnot B)$, respectively.

When $B$ happens, the attacker can obtain a verification code from $v$ with a probability 1, i.e., $Pr(A|B)=1$.  $Pr(B)$ depends on whether the attacker attacks $v$ before $u$ or not. If $v$ is attacked before $u$, then the probability that $B$ happens is $p_a^{(t)}(v)$, otherwise it is $p_a^{(t-1)}(v)$. Formally, we have:
\begin{align}
\label{equ:one_code_B}
Pr(B)=
\begin{cases}
p_a^{(t)}(v) &\text{ if }  v \text{ is ordered before } u \\
p_a^{(t-1)}(v) &\text{ otherwise}
\end{cases}
\end{align}

When $B$ does not happen,  the attacker can impersonate $u$ and send a spoofing message to $v$ to request a verification code.  We call the probability that such spoofing attacks succeed \emph{spoofing probability}.  Spoofing probability might be different for different trustees. A trustee might behave differently to spoofing messages impersonating different users because he or she might have different levels of trusts with the users that are impersonated. Moreover, spoofing probability might be different in different attack iterations because trustees might gradually become aware of the spoofing attacks. Thus, we model the spoofing probability that the attacker obtains a verification code from $v$ in an attack trial to $u$ in the $t$th attack iteration as $p_s^{(t)}(v,u)$, i.e., $Pr(A|^\lnot B)=p_s^{(t)}(v,u)$.


%Moreover, $Pr(^\lnot B) = 1-Pr(B)$. 
%When $B$ does not happen,  the attacker can still obtain a verification code from $v$ with some probability via spoofing attacks such as impersonating $u$ and sending a spoofing message to $v$ to request a verification code. We call the probability that the attacker $v$ is successfully spoofed in the attack trial to $u$ in the $t$th attack iteration  as  \emph{spoofing probability}. 
%We model the \emph{spoofing probability} for the pair of user $u$ and his or her trustee $v$ in the $t$th attack iteration as $p_s^{(t)}(v,u)$.  We model the spoofing probability as a function of $u$, $v$, and $t$ because it might be different for different pairs of  users and trustees in different attack iterations. 
%Furthermore, we  view $p_s(v,u)$ as the weight of the directed edge $(v,u)$ in the trustee network.   

% Schechter et al.~\cite{Schechter09} showed that, via performing user studies, the average spoofing probability using email-based  attacks is around 0.05.

%\begin{itemize}
%\item {\bf Case 1:} $v$ is already compromised. In this case,  the attacker can obtain the verification code from $v$ with probability 1. When the attacker performs an attack trial to $u$ in the $t$th attack iteration, the probability that $v$ is compromised depends on whether the attacker attacks $v$ before $u$ or not. If the attack ordering $O^{(t)}$ orders $v$ before $u$, then the probability that $v$ is compromised is $p_a^{(t)}(v)$, otherwise it is $p_a^{(t-1)}(v)$.
%\item {\bf Case 2:} $v$ is not compromised yet. In this case, Schechter et al.~\cite{Schechter09} showed that the attacker could still obtain the verification code from $v$ with some probability via spoofing attacks such as impersonating the user $u$ and sending emails to $v$ to request the verification code. 
%We model such \emph{spoofing probability} for the pair of user $u$ and his or her trustee $v$ as $p_s(v,u)$. Note that we model the spoofing probability as a function of both $u$ and $v$ because it might be different for different pairs of  users and trustees. Furthermore, we can view $p_s(v,u)$ as the weight of the directed edge $(v,u)$ in the trustee network.  
%\end{itemize}

%In summary, the probability that the attacker  obtains a verification code from $v$ when attacking $u$ in the $t$th attack iteration is as follows: 
In summary, we have: 
\begin{align}
%\label{equ:one_code}
&p^{(t)}(v,u)= \nonumber \\
&\begin{cases}
p_a^{(t)}(v) + p_s^{(t)}(v,u)(1-p_a^{(t)}(v)) \text{ if } v \text{ is ordered before } u \\
p_a^{(t-1)}(v) + p_s^{(t)}(v,u)(1-p_a^{(t-1)}(v)) \text{ otherwise}
\end{cases} \nonumber
\end{align}

%\myparatight{Obtaining $i$ verification codes} Suppose $\Psi \subseteq \Gamma_T(u)$ satisfies $|\Psi|=i$ and $\Omega=\Gamma_T(u)-\Psi$. If $i>0$, the probability that the attacker obtains verification codes from the $i$ trustees in $\Psi$ in the $t$th attack iteration is $\prod_{v\in \Psi} p^{(t)}(v,u) \prod_{v\in \Omega} (1-p^{(t)}(v,u))$, otherwise it is $\prod_{v\in \Gamma_T(u)} (1-p^{(t)}(v,u))$. Summing over all possible such $\Psi$, we have the probability that the attacker obtains verification codes from $i$ trustees of $u$ in the $t$th attack iteration as follows:
%\begin{align}
%&p_i^{(t)}(u) \nonumber \\
%&=
%\begin{cases}
%\prod_{v\in \Gamma_T(u)} (1-p^{(t)}(v,u)) &\text{ if } i=0 \\
%\sum_{\Psi}\prod_{v\in \Psi} p^{(t)}(v,u) \prod_{v\in \Omega} (1-p^{(t)}(v,u)) &\text{ otherwise}
%\end{cases}
%\label{p_i}
%\end{align}

\begin{algorithm}[!t] 
\DontPrintSemicolon 
\KwIn{$G_T$, $k$, $p_s^{(t)}(v,u)$, $n_s$, $n$, ${\mathcal S}$, ${\mathcal O}$,  $c_e$,  $c_I$, and $p_r^{(t)}(u)$.} 
\KwOut{$n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$, $c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$.} 
\Begin{
//Selecting seed users in the Ignition Phase. \;
$S\longleftarrow {\mathcal S}(G_T, n_s)$\;  

//Calculating the compromise probabilities. \;
//Ignition Phase. \;
\For{$u\in V_T$}{
\eIf{$u\in S$}{
	$p_c^{(0)}(u)\longleftarrow 1$ \;	
}{
	$p_c^{(0)}(u)\longleftarrow 0$ \;	
}
$p_a^{(0)}(u) \longleftarrow p_c^{(0)}(u)$ \;
} 
//Propagation Phase.\;
$t \longleftarrow 1$\;
$C \longleftarrow 0$\;
\While{$t \leq n$}{
//Constructing an attack ordering.\;
$O^{(t)} \longleftarrow {\mathcal O}(G_T,p_a^{(t-1)}(V_T)) $\;
\For{$i=0$ to $O^{(t)}.size()-1$}{
       $u \longleftarrow O^{(t)}[i]$\;
	Apply Equation~\ref{local_update_rule} to $u$.
$p_a^{(t)}(u) \longleftarrow 1- (1-p_a^{(t-1)}(u)) (1-p_c^{(t)}(u))$ \;
$p_a^{(t)}(u) \longleftarrow (1-p_r^{(t)}(u)) p_a^{(t)}(u)$ \;

$c^{(t)}(u) \longleftarrow$ Apply  Equation~\ref{equ:one_user_cost}\;
$C \longleftarrow C + c^{(t)}(u)$\;
}
$t \longleftarrow t+1$\;
}

//The expected number of compromised users. \;
$n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O}) \longleftarrow \sum_{u\in V_T} p_a^{(n)}(u)$ \;

//The expected cost. \;
$c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O}) \longleftarrow c_I + c_eC$ \;

\Return $n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$, $c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$\;
} 
\caption{Our Model of Forest Fire Attacks} 
\label{alg:forest_fire_attack}
\end{algorithm}


\myparatight{Computing compromise probabilities} Recall that $u$ is compromised if the attacker can obtain verification codes from at least $k$ trustees of $u$. Thus, given the natural assumption that $u$'s trustees are independent,  the compromise probability of $u$ in the $t$th attack iteration is calculated using the following local update rule:
\begin{align}
%\text{\bf Local update rule: } \nonumber \\
%p_c^{(t)}(u) = \sum_{i=k}^{m_u} p_i^{(t)}(u)
p_c^{(t)}(u) = \sum_{\phi} \prod_{v \in \phi} p^{(t)}(v,u) \prod_{v\in \Gamma_T(u) -\phi} (1-p^{(t)}(v,u))
\label{local_update_rule}
\end{align}
, where $\phi \subseteq \Gamma_T(u)$ and $|\phi| \geq k$.

%The event that an attacker performs one attack trial to $u$ is equivalent to applying the local update rule to $u$ once. 


\myparatight{Aggregating compromise probabilities} Assuming that whether $u$ is compromised in one attack iteration is independent with whether $u$ is compromised in another attack iteration, we can iteratively compute the aggregate compromise probability of $u$ as follows: 
%\begin{align}
%\label{equ:aggregate}
%p_a^{(t)}(u)=1-\prod_{j=0}^t (1-p_c^{(j)}(u))
%\end{align}
%
%Note that we need to compute $p_a^{(t)}(u)$ for $t=0,1,\cdots,a$ because they are involved in calculating the probability of obtaining one verification code (i.e., Equation~\ref{equ:one_code}). To accelerate the computations, we iteratively compute them using the following equation:
\begin{align}
\label{equ:iterative}
p_a^{(t)}(u)=1-(1-p_a^{(t-1)}(u)) (1-p_c^{(t)}(u))
\end{align}



\myparatight{Compromised users can recover to be uncompromised} As we have discussed in Section~\ref{sec:forest_fire_attack}, compromised users can recover to be uncompromised and be compromised again due to various factors.  We call the probability that a compromised user $u$ recovers to be uncompromised in the $t$th attack iteration  \emph{recovery probability}, and we denote it as $p_r^{(t)}(u)$. Considering the recovery probability, we reformulate the aggregate compromise probability of $u$ (i.e., Equation~\ref{equ:iterative})  as follows:
\begin{align}
%\label{equ:recover}
p_a^{(t)}(u)=(1-p_r^{(t)}(u))(1-(1-p_a^{(t-1)}(u)) (1-p_c^{(t)}(u))) \nonumber
\end{align}

%We model such process as follows:  in each attack iteration, a compromised user is recovered to be uncompromised with an average probability $p_r$. We call $p_r$ the average \emph{recovery probability}.  Intuitively, the recovery probability represents the fraction of compromised users that realize their accounts are compromised and take actions to recover their accounts in each attack iteration. 


 
\myparatight{Expected number of compromised users} Given a forest fire attack specified by the seed users selection strategy $\mathcal S$, the number of seed users $n_s$, the ordering construction strategy $\mathcal O$, and the number of attack iteratons $n$, we define the threat of the attack as the expected number of users it compromises. Moreover, we denote the expected number of compromised users as $n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})$, and it is formalized as follows:
\begin{align}
\label{comp_node}
n_c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O}) = \sum_{u \in V_T} p_a^{(n)}(u)
\end{align}

\subsection{Formalizing costs}
We consider the attacker's costs of obtaining seed users and sending spoofing messages. Suppose the cost to obtain seed users is $c_I$. In the following, we quantify the cost of sending spoofing messages. 

In an attack trial to $u$, the attacker sends a spoofing message to  $u$'s  trustee $v$ when the following three independent events happen: $u$ is uncompromised, $v$ is uncompromised, and among the rest of $u$'s trustees, the number of compromised ones is less than $k$. 

In the $t$th attack iteration, the first event happens with a probability $(1-p_a^{(t-1)}(u))$. We denote by $q^{(t)}(v,u)$ the probability that the second event happens, and $q^{(t)}(v,u)$ depends on  whether $v$ is attacked before $u$  or not. Formally, we have:
%We denote by $q^{(t)}(v,u)$ the probability that $v$ is uncompromised in the attack trial to $u$ in the $t$th attack iteration. $q^{(t)}(v,u)$ depends on whether $v$ is ordered before $u$  or not. Specifically, we have: 
 \begin{align}
\label{equ:prob}
&q^{(t)}(v,u)=
&\begin{cases}
1-p_a^{(t)}(v) \text{ if } v \text{ is ordered before } u\\
1-p_a^{(t-1)}(v) \text{ otherwise}
\end{cases}
\end{align}
, for any $v\in \Gamma_T(u)$. Moreover, the third event happens with the following probability:
 \begin{align}
\label{equ:less_than_k}
&r^{(t)}(v,u) = \nonumber \\
&\sum_{\phi} \prod_{w\in \phi} (1-q^{(t)}(w,u)) \prod_{w\in \Gamma_T(u) - \phi - \{v\}} q^{(t)}(w,u)
\end{align}
, where $\phi\subseteq \Gamma_T(u) -\{v\}$ and $|\phi| < k$.

Therefore, the \emph{expected} number of spoofing messages (denoted as $c^{(t)}(v, u)$) that the attacker sends to  $v$ in the attack trial to $u$ in the $t$th attack iteration is formalized as follows:
 \begin{align}
\label{equ:one_cost}
c^{(t)}(v,u)= (1-p_a^{(t-1)}(u))q^{(t)}(v,u)r^{(t)}(v,u)
\end{align}

So the total expected number of spoofing messages (denoted as $c^{(t)}(u)$) that the attacker sends in the attack trial to $u$ in the $t$th attack iteration is:
\begin{align}
\label{equ:one_user_cost}
c^{(t)}(u)= (1-p_a^{(t-1)}(u))\sum_{v\in \Gamma_T(u)} q^{(t)}(v,u)r^{(t)}(v,u)
\end{align}

%Thus, the expected number of spoofing messages in $a$ attack iterations is $\sum_{t=1}^{a} \sum_{u\in V_T}c^{(t)}(u)$. 
Thus, we obtain the total expected cost of performing a forest fire attack as follows:
 \begin{align}
\label{equ:total_cost}
c(G_T, k, n_s, n, {\mathcal S}, {\mathcal O})= c_I + c_e\sum_{t=1}^{n} \sum_{u\in V_T}c^{(t)}(u)
\end{align}
, where $c_e$ is the average cost  for the attacker to send one spoofing message. 
%In our experiments, we will compare the costs of sending spoofing messages for different attack and defense strategies.

%Next, we will discuss algorithms of selecting seed users, algorithms of constructing attack orderings, and algorithms of constructing the trustee network to defend against the forest fire attacks.


\section{Attack Strategies}
\label{sec:attack_strategy}
The attacker could design the seed users selection strategy and the attack ordering construction strategy to maximize the expected number of compromised users. First, we show that finding the optimal set of seed users and the optimal ordering construction strategy  is NP-Complete. Then, we explore various scenarios where seed users have different properties and introduce two ordering construction strategies.

  

\subsection{NP-Completeness}
%We model seed users as if they are selected by a \emph{seed users selection strategy}, which makes it possible to compare the impact of different sets of seed users via comparing different seed users selection strategies. 

Given $G_T,k,n_s,$ and $n$, 
%the goal of an attacker is to  maximize the expected number of compromised users by searching for the optimal set of seed users (i.e., the optimal seed users selection strategy) and the optimal ordering construction strategy. In other words, 
 the attacker essentially aims to solve the following  \emph{attack maximization problem}:
\begin{align}
\label{attack_max}
&\text{\bf Attack Maximization Problem:} \nonumber \\
&n_c(G_T,k,n_s,n)=\max_{{\mathcal S}, {\mathcal O}}n_c(G_T,k,n_s,n,{\mathcal S}, {\mathcal O}) \nonumber
\end{align}

We prove that this problem is NP-Complete. Please refer to Appendix~\ref{theorem:attack:proof} for the proof. 


%\begin{theorem}
%\label{theorem:attack}
%The attack maximization problem is NP-Complete.
%\end{theorem}
%\begin{proof}
%See Appendix~\ref{theorem:attack:proof}
%\end{proof}




\subsection{Strategies for selecting seed users}
\label{sec:seed_selection}

%Suppose the attacker has a limited budget and can only bribe/compromise $n_s$ seed users, then the question is that which $n_s$ seed users the attacker should bribe/compromise so that the expected number of compromised users is maximized.

A seed users selection strategy ${\mathcal S}$ is essentially to assign a score which represents some metric of importance to each user and to select $n_s$ users with the highest scores as seed users. This is closely related to the \emph{node centrality problem}~\cite{nodeCentrality} in the network science community. In the following, we modify a few node centrality heuristics as seed users selection strategies. These strategies work on a trustee network, and we name them with a prefix `S-' to indicate they are used to select seed users. 

\myparatight{S-Random} As a baseline, this strategy assigns a random score ranging from 0 to 1 to each user in the trustee network. 

\myparatight{S-Degree} Intuitively, if a user $u$ is selected as a trustee by more users, then compromising $u$ will increase the compromise probabilities of more users and thus the attacker has an opportunity to compromise more users. Therefore, S-Degree treats the number of users that select $u$ as a trustee (i.e., outdegree of $u$ in the trustee network) as $u$'s score.  

\myparatight{S-BadRank} S-BadRank, adapted from BadRank~\cite{badrank}, performs a random walk on the trustee network. Specifically, S-BadRank starts a random walk from $u$ that is picked uniformly at random. Then S-BadRank iteratively performs one of the two operations: choosing a trustee $v$ of $u$ uniformly at random and walks to $v$ with a probability $1-\alpha$, and selecting a user $w$ uniformly at random from the entire trustee network and walks to $w$ with a probability $\alpha$. Traditionally, $\alpha$ is called the \emph{restart probability}. 


The random walk will converge to a stationary probability distribution over all users in the trustee network. The stationary probability of $u$ is roughly the frequency with which the random walk visits $u$ and is used as $u$'s score. Intuitively, S-BadRank tends to assign a high score to a user that is selected by many users as a trustee because he or she has a large chance to be visited by the random walk.  
%Algorithm~\ref{alg:s-badrank} in Appendix shows S-BadRank.     

%Note that both BadRank~\cite{badrank} and PageRank~\cite{Page99} were designed to rank webpages. The difference between them is that BadRank performs a random walk along the incoming edges while PageRank performs a random walk along the outgoing edges. 

\myparatight{S-Closeness}  The attacker could also select users that are close to all other users in the trustee network as  seed users because compromising them could help the attacker compromise other users more quickly. This intuition is formally captured by the \emph{closeness} metric~\cite{Sabidussi66}. Specifically, we define the distance between $v$ and $u$ as the length of the shortest directed path whose tail is $v$ and whose head is $u$. Then the closeness of $u$ is defined as the inverse of the sum of its distances to all other users, and it is treated as $u$'s score. In our experiments, we adopt the approximate algorithm developed by Okamoto et al.~\cite{Okamoto08} to find the top-$n_s$ users with the highest closeness scores since it is scalable to large networks.

%A naive algorithm using closeness to select the seed users is to first compute the closeness score of every user by solving all pairs shortest-paths problem and then to select the $n_s$ users with the highest closeness scores.  However, the all pairs shortest-paths problem can be solved with time complexity $O(|V_T||E_T|+|V_T|^2 \text{log} |V_T|)$ by various algorithms~\cite{Johnson77,Fredman87}, which is not scalable to large-scale networks. Moreover, attackers only need to find the $n_s$ users with the highest closeness scores.   Thus, we adopt the approximate algorithm developed by Okamoto et al.~\cite{Okamoto08} to find the top-$n_s$ users with the highest closeness scores. Using this approximate algorithm, the time complexity is reduced to $O((n_s+|V_T|^\frac{2}{3}\text{log}^\frac{1}{3} |V_T|) (|V_T|\text{log} |V_T| + |E_T|))$.



\subsection{Strategies for constructing attack orderings}
We name these strategies with a prefix `O-' to indicate that they are used to construct attack orderings. Essentially, these strategies assign a score to each user in the trustee network and rank them in a decreasing order according to their scores.

\myparatight{O-Random} As a baseline, this strategy assigns a random score ranging from 0 to 1 to each user in the trustee network.

\begin{algorithm}[!t] 
\DontPrintSemicolon 
\KwIn{$G_T=(V_T, E_T)$ and $p_a^{(t)}(V_T)$.} 
\KwOut{An ordering $O$ of all users  in $V_T$.} 
\Begin{
\For{$u\in V_T$}{
	\For{$v\in \Gamma_T(u)$}{
		//Probability of getting one verification code
		$p_v \longleftarrow p_a^{(t)}(v) + p_s^{(t+1)}(v,u)(1-p_a^{(t)}(v)) $ \;
		
	}
	$p_u\longleftarrow \sum_{\phi} \prod_{v \in \phi} p_v \prod_{v\in \Gamma_T(u) -\phi} (1-p_v)$,  where $\phi \subseteq \Gamma_T(u)$ and $|\phi| \geq k$. \;
	$q_a^{(t)}(u) \longleftarrow 1-(1-p_a^{(t)}(u))(1-p_u)$ \;	
} 
\For{$u\in V_T$}{
	$d_a^{(t)}(u) \longleftarrow q_a^{(t)}(u) - p_a^{(t)}(u)$ \;
} 
%//Sort users decreasingly using $d_a^{(t)}(u)$. \;
$O \longleftarrow$ Sort users decreasingly using $d_a^{(t)}(u)$\;
\Return $O$\;
} 
\caption{O-Gradient} 
\label{alg:gradient}
\end{algorithm}



\myparatight{O-Gradient} Algorithm~\ref{alg:gradient} shows O-Gradient. Given the current aggregate compromise probabilities $p_a^{(t)}(V_T)$ of all users after $t$ attack iterations, the attacker calculates a \emph{predicted} aggregate compromise probability $q_a^{(t)}(u)$ for each user $u$ by simulating an attack trial to $u$. Note that $q_a^{(t)}(u)$ might be different from $p_a^{(t+1)}(u)$ because $q_a^{(t)}(u)$ is calculated with the fixed aggregate compromise probabilities of $u$'s trustees while $p_a^{(t+1)}(u)$ is updated with the newest aggregate compromise probabilities of $u$'s trustees.     
%O-Gradient simulates an attack trial to each user and gives a higher priority to a user whose increase of aggregate compromise probability is bigger. Specifically
Intuitively, a user $u$ with a larger difference of  $q_a^{(t)}(u)-p_a^{(t)}(u)$ could be attacked with a higher priority because such an attack trial could bring more increase to the aggregate compromise probabilities of users who select $u$ as a trustee.  Thus, O-Gradient calculates the differences of $q_a^{(t)}(u)-p_a^{(t)}(u)$ for all users and ranks them decreasingly according to these differences.     

%\begin{table}[!t]\renewcommand{\arraystretch}{1}
%\centering
%\caption{Summary of defense strategies.}
%\begin{tabular}{|c|c|c|} \hline 
% Strategy & Applicable to the users? & Applicable to the service provider? \\ \hline
%D-Random & $\surd$ & $\surd$ \\ \hline
%D-CN & $\surd$ & $\surd$ \\ \hline
%D-Degree & X & $\surd$ \\ \hline
%\end{tabular}
%\label{defenses}
%\end{table}

\section{Defense Strategies}
\label{sec:defense_strategy}
We discuss potential defense strategies from three aspects, i.e., hiding trustee networks from attackers, mitigating spoofing attacks, and constraining the selection of trustees.   
%Then we discuss detecting forest fire attacks and model its impact on the threats of forest fire attacks.  

%We introduce a few strategies to select trustees for users. These strategies aim to construct trustee networks to minimize the expected number of compromised users. 

\subsection{Hiding trustee networks}
Preventing attackers from obtaining a trustee network is an essential step towards the defense of forest fire attacks. In the currently deployed social authentication systems, attackers can obtain a trustee network because \emph{users need to know their trustees to retrieve verification codes from them} in the Recovery Phase.   An alternative implementation of the Recovery Phase is that the service provider directly sends verification codes to the trustees of the user when receiving an account recovery request, and the trustees are required to actively share the verification codes to the user.  This implementation does not require users to know their trustees, and thus it is hard for attackers to obtain the trustee network. 

%when receiving an account recovery instead of asking $u$ to share the URL with the trustees and they request the verification codes using the given URL; then the trustees actively share the verification codes to Alice. In such implementation,  Alice does not need to know her trustees. Thus, it is hard for an attacker to obtain the trustee network. 

However, this implementation  is \emph{unreliable} and could annoy users and their trustees. Specifically,  $u$'s trustees might already forget they are trustees of $u$, and thus they might simply treat those verification codes as spams and not share them with $u$, which results in low reliability. Moreover, users do forget who their trustees are~\cite{Schechter09}, and thus it is highly impossible for $u$ to actively request verification codes from its trustees. If the trustees do actively share the codes with $u$, then attackers can frequently send account recovery requests to the service provider which immediately sends verification codes to the trustees, and the trustees will (possibly) frequently share the codes with $u$,  which could be annoying  to both $u$ and  its trustees. More seriously,  after $u$'s trustees realize that the verification codes are just spams, they might not actively share the verification codes with $u$ even if she is really trying to recover her account, which again results in low reliability.

Therefore, hiding trustee networks from attackers sacrifices reliability, which possibly explains why existing trustee-based social authentication systems didn't adopt this alternative implementation of the Recovery Phase. 
%and we do not recommend such defenses. 

%We believe that the Recovery Phase implemented in the current social authentication systems is a good tradeoff between security and reliability. 
  
\subsection{Mitigating spoofing attacks}
Another way to defend against forest fire attacks is to remind trustees of not sharing verification codes via messages. This strategy is not novel, and we include it for completeness. Indeed, existing social authentication systems~\cite{Schechter09,facebookSocAuth} already try to mitigate spoofing attacks.  For instance,  Microsoft's system~\cite{Schechter09} asks a trustee why she is requesting the verification code and encourages her to share the code with the user via phone or meeting in person. 

However, it is hard to control how trustees share the verification codes with others in practice. Indeed,  an attacker can still obtain a verification code from a trustee with an average probability around 0.05 via message-based spoofing attacks in the Microsoft's system~\cite{Schechter09}. It is an interesting future work to design better user interfaces to further reduce this spoofing probability.


\subsection{Constraining trustee selections}
Finally, we introduce strategies to contrain trustee selections, which are easy to implement and effective at defending against forest fire attacks. We consider both \emph{local trustee selection strategies}  and \emph{global trustee selection strategies}. A local trustee selection strategy is based on a user's local social network structure while a global one is based on the entire social network structure.  We name these strategies with a prefix `T-' to indicate that they are used to select trustees. 
%These strategies are used to select trustees for users who adopt the trustee-based social authentication service, and we denote the set of such users as $V_a$. 

We note that how users select their trustees in a real trustee-based social authentication system such as Facebook's Trusteed Contacts is not clear and thus might not be one of our strategies. However, our work focuses on a comparative study about different trustee selection strategies and can shed light on which strategy is more secure. 

%Moreover, according to Schechter et al.~\cite{Schechter09}, users will forget their trustees when they use trustee-based social authentication to recover their accounts. So, to increase the usability, the service provider should remind the user of his or her trustees no matter which trustee selection stratey is used to select them.


\subsubsection{Local trustee selection strategies} For a user $u$, a local trustee selection strategy essentially computes a score $s(v,u)$ for each friend $v$ of $u$ and then selects $m_u$ friends with the highest scores as $u$'s trustees.  

\myparatight{T-Random} As a baseline, T-Random assigns a random number ranging from 0 to 1 as the score $s(v,u)$. 
 
\myparatight{T-CF} As was shown by Gilbert and Karahalios~\cite{gilbert:chi09}, the number of common friends of two users is an informative indicator about the level of trust between them. Thus, one speculation is that a user might select friends with which he or she shares many common friends as trustees. To quantify the security of this speculation, we design the strategy T-CF (i.e.,T-CommonFriends), which uses the number of common friends shared by $u$ and his or her friend $v$ as the score $s(v,u)$, i.e., $s(v,u) = |\Gamma(v) \cap \Gamma(u)|$.
 

However, there are two drawbacks of T-CF. First, the fact that $u$ shares many friends with a popular user $v$ doesn't necessarily mean that $u$ and $v$ have a high level of trust because it is normal for many friends of $u$ to be in $v$'s friend list. 
%if $v$ is a friend of $u$ and $v$ is a popular user (e.g., a celebrity), then  many of $u$'s friends might also have $v$ in their friend lists. Thus, the fact that $u$ shares many common friends with $v$ doesn't necessarily mean that $u$ and $v$ have a high level of trust. 
 Second, if a common friend of $u$ and $v$ is a  popular user, then sharing him or her doesn't necessarily indicate a high level of trust between $u$ and $v$. Next, we introduce two strategies to overcome the two drawbacks, respectively.

\myparatight{T-JC} To overcome the first drawback of T-CF, we design the trustee selection strategy T-JC (i.e., T-JaccardCoefficient), which uses the Jaccard Coefficient~\cite{Jaccard1901} of the two sets $\Gamma(u)$ and $\Gamma(v)$ as the score $s(v,u)$, i.e., $s(v,u) = \frac{|\Gamma(v) \cap \Gamma(u)|}{|\Gamma(v) \cup \Gamma(u)|}$.
 
%For pair of friends who have a large number of friends, calculating their exact jaccard coefficient is slow. Thus, we use the widely adopted MinHash~\cite{Broder97} algorithm to approximate the jaccard coefficient. Suppose we have a hash function $h$. MinHash uses the $h_k$ elements of a set that have the smallest hash values of $h$ as the signature for the set. Then MinHash approximates the jaccard coefficient using the two signatures of the two sets.


\myparatight{T-AA} To overcome the second drawback, we design the T-AA (i.e., T-AdamicAda) strategy, which uses Adamic-Ada~\cite{aa03} similarity between $u$ and $v$ as the score  $s(v,u)$. Adamic-Ada similarity penalizes each common friend by its popularity (i.e., the number of friends). Formally, we have
$s(v,u) = \sum_{w\in \Gamma(v) \cap \Gamma(u)} \frac{1}{\text{log}|\Gamma(w)|}$.

%Adamic-Ada similarity was previously designed to predict links in various networks~\cite{aa03,link-pre-survey03,Gong12-kdd}.


\begin{algorithm}[!t] 
\DontPrintSemicolon 
\KwIn{$G=(V, E)$, $V_a$, and $m_u$ of all $u\in V$.} 
\KwOut{A trustee network $G_T=(V_T, E_T)$.} 
\Begin{
$V_T \longleftarrow V$ \;
\For{$u\in V_T$}{
$d_o(u) \longleftarrow 0$ \;
}
\For{$u\in V_a$}{
$\phi \longleftarrow \emptyset$ \;
\While {$|\phi| < m_u$}{
	$v \longleftarrow \argmin_{v\in \Gamma(u)-\phi} d_o(v)$ \;
	$\phi \longleftarrow \phi \cup \{v\}$ \;
	$d_o(v) \longleftarrow d_o(v) + 1$ \;
	$E_T \longleftarrow E_T \cup (v, u)$ \;
}
} 

\Return $G_T=(V_T, E_T)$\;
} 
\caption{T-Degree} 
\label{alg:d-degree}
\end{algorithm}

\subsubsection{Global trustee selection strategies}  Global strategies leverage the entire social network structure and thus are potentially better than local strategies.
 
\myparatight{T-Degree} As we discussed in Section~\ref{sec:seed_selection}, seed users could be those having large outdegrees in the trustee network, and they could enable an attacker to compromise many other users. Thus, we propose the T-Degree  strategy to minimize the maximum outdegree in the trustee network.  Intuitively, T-Degree constrains that no users are selected as trustees by too many other users.

Algorithm~\ref{alg:d-degree} shows our T-Degree strategy. 
%that selects trustees for users who have adopted the trustee-based social authentication service. Essentially, 
T-Degree selects trustees for users one by one. For each user $u$ that has adopted the trustee-based social authentication service, T-Degree selects his or her $m_u$ friends whose current outdegrees in the trustee network are the smallest as $u$'s trustees; ties are broken uniform at random. 

 
%\subsection{Detecting forest fire attacks}
%The service provider and users could detect forest fire attacks in various scenarios. For instance, a trustee receiving a spoofing message might report to the user, who then changes his or her password; trustees receiving multiple spoofing messages might report to the service provider, who asks the corresponding users to change passwords; the phenomenon that a trustee requests a large number of verification codes for different users within a short period of time is a possible indicator of forest fire attacks, and then the service provider could notify the users, whose trustees have requested verification codes, to change passwords.
%
%Moreover, a recovered user account could be compromised again in future attack iterations (e.g., when the trustees of the recovered user are still compromised). The process of being compromised and recovering to be uncompromised could repeat for many attack iterations.  We model the impact of such process as follows:  in each attack iteration, a user that is compromised by forest fire atttacks is recovered to be uncompromised with an average probability $p_r$ because the service provider or the user detects the attacks and resets the password. We call $p_r$ the average \emph{recovery probability}.  

%All other equations in our security model do not need to be changed.

\section{Experiments}
\label{sec:eva}


\subsection{Experimental setups}
%In the following, we will first introduce three social network datasets used in our experiments. Then we will show our findings about the impact of attackers' resources, attack orderings, seed users selection strategies,  trustee selection strategies, the number of trustees (i.e., $m_u$), recovery threshold (i.e., $k$),  spoofing probability (i.e., $p_s(v,u)$), the number of seed users (i.e., $n_s$), and the recovery probability (i.e., $p_r$). 

\myparatight{Parameter settings} Unless otherwise mentioned, we set $n=10$, $m_u=m=5$, $k=3$,\footnote{This is the recovery threshold chosen by the Microsoft's and Facebook's trustee-based social authentication systems.} $n_s=1,000$, $p_r^{(t)}(u)=p_r=0$ for every $u$, and $\alpha=0.9$;\footnote{We tried $\alpha$ from 0 to 0.9 with a step size 0.1,  and we found that  S-BadRank with $\alpha=0.9$ achieves the largest expected number of compromised users.} we use the O-Gradient strategy to construct attack orderings, i.e., $\mathcal O$=O-Gradient; according to  Schechter et al.~\cite{Schechter09}, the average message-based spoofing probability is around 0.05, thus we set $p_s^{(t)}(v,u)=p_s=0.05$ for every edge $(v,u)\in E_T$. 


\begin{table}[!t]\renewcommand{\arraystretch}{1.3}
%\vspace{-2mm}
\centering
%\addtolength{\tabcolsep}{-5pt}
\caption{The number of users, the number of users who have at least 10 friends, the fraction of such users, and the average number of friends of such users in the three social networks.}
\begin{tabular}{|c|c|c|c|} \hline 
 & {\small Flickr} & {\small Google+} & {\small Twitter} \\ \hline
{\small \# Nodes} &{\small 1,551,824} &{\small 10,230,332} &{\small 21,297,771} \\ \hline
{\small \# Nodes (degree $\geq$ 10)} &{\small 233,067} &{\small 3,144,370} &{\small 4,540,483} \\ \hline
{\small Fractions} &{\small 15\%} &{\small 31\%} &{\small 21\%} \\ \hline
{\small Average degrees} &{\small 75}&{\small 27}&{\small 107}\\ \hline
\end{tabular}
\label{dataset}
%\vspace{-4mm}
\end{table}


\begin{figure}[!ht]
\vspace{-2mm}
\centering
\subfloat[Number of compromised users]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-attack-trial-flickr}.pdf}\label{impact-a}}
\subfloat[Number of spoofing messages]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-attack-trial-cost-flickr}.pdf}\label{impact-a-cost}}
%\subfloat[Flickr]{\includegraphics[width=0.33\textwidth, height=2.2in]{{impact-attack-trial-flickr}.pdf}}
%\subfloat[Google]{\includegraphics[width=0.33\textwidth, height=2.2in]{{impact-attack-trial-google}.pdf}}
%\subfloat[Twitter]{\includegraphics[width=0.33\textwidth, height=2.2in]{{impact-attack-trial-twitter}.pdf}}
\caption{Impact of  attackers' resources and  attack orderings on Flickr. First, we find that an attacker can perform forest fire attacks with low costs. Second, we find that O-Gradient compromises more users and requires fewer spoofing messages  than O-Random when the attacker performs a given number of attack iterations.}
\vspace{-4mm}
\label{impact-a-both}
\end{figure}

\begin{figure*}[!ht]
\centering
\vspace{-4mm}
\subfloat[Flickr]{\includegraphics[width=0.33\textwidth, height=1.8in]{{comparison-attack-defense-flickr-k3-1000-0.05}.pdf}\label{liveJournal-attack-defense}}
\subfloat[Google+]{\includegraphics[width=0.33\textwidth, height=1.8in]{{comparison-attack-defense-google-k3-1000-0.05}.pdf}\label{google-attack-defense}}
\subfloat[Twitter]{\includegraphics[width=0.33\textwidth, height=1.8in]{{comparison-attack-defense-twitter-k3-1000-0.05}.pdf}\label{twitter-attack-defense}}
\caption{The expected number of compromised users for different seed users selection strategies and trustee selection strategies. We find that, with 1,000 seed users, an attacker can compromise two to three orders of magnitude more users with low costs of sending spoofing messages in some cases. However, our   strategy T-Degree can decrease the expected number of compromised users by one to two orders of magnitude.}
\label{attack-defense}
\vspace{-4mm}
\end{figure*}


\myparatight{Datasets} We use three social network datasets. They are Flickr, Google+, and Twitter. We obtained the Flickr dataset from Mislove et al.~\cite{Mislove08}. In this social network, we take each user as a node and connect two users if they are in each other's friend lists.  We obtained a Google+ snapshot from Gong et al.~\cite{Gong12-imc}. In this social network, each node is a Google+ user and two users are connected if they are in each other's circles.  The Twitter dataset was obtained from Kwak et al.~\cite{Kwak10}. In this social network,  each node is a Twitter user and two users are connected if they follow each other. 


%The three social networks are all directed, which can be easily manipulated and thus don't represent trust relationships between users. Therefore, we obtain approximate trust social networks via keeping an undirected edge between $u$ and $v$ if and only if directed edges exist between them in both directions. 
%In a trustee-based social authentication, the trustees of a user are required to login the service to retrieve the verification codes. However, users with too few friends on a online social network might indicate that they are not active users. These inactive users might forget their own passwords and thus cannot retrieve the verification codes easily. Thus, to increase the usability, we remove the nodes whose degrees are less than 3 from the three social networks. Furthermore, 
Since a trustee-based social authentication requires a user to have enough number of friends from which trustees can be selected, we assume that users who have at least 10 friends are appropriate to adopt  the trustee-based social authentication service. In our experiments, we consider the \emph{worst} scenario in which every such user has adopted the trustee-based social authentication service.\footnote{The fewer users adopt the trustee-based social authentication, the more secure it is. An extreme case is that if no user adopts the system, then the forest fire attacks cannot be spreaded from the seed users at all.}  Table~\ref{dataset} shows the statistics of our interest in the three social networks.

For simplicity, we only show results on the Flickr dataset in some of our experiments, but similar conclusions are applicable to the other two datasets.


%the second preprocessing step is to choose the $\mathcal K$-core, a subgraph in which all nodes have degree at least $\mathcal K$, from each social network.  In our experiments, we set $\mathcal K=10$. Table~\ref{dataset} shows the basic statistics of the corresponding 10-cores.


%\begin{table*}[!t]\renewcommand{\arraystretch}{1}
%%\vspace{-4mm}
%\centering
%\caption{}
%\begin{tabular}{|c|c|c|c|c|c|c|} \hline 
% & \multicolumn{3}{|c|}{Original (directed)} & \multicolumn{3}{|c|}{10-core (undirected)}\\ \cline{2-7}
% & \#Nodes & \#Edges & Ave. indegree& \#Nodes & \#Edges & Ave. degree \\ \hline
%{LiveJournal} &4,847,571 & 68,993,773 & 14 & 957,692 &16,191,718 & 34 \\ \hline
%{Google+} &17,091,929 &271,915,755 & 16 &1,590,602&23,952,465& 30\\ \hline
%{Twitter} & 40,171,433 &1,468,365,182 & 37 &3,388,392&219,222,076&129 \\ \hline
%\end{tabular}
%\label{dataset}
%%\vspace{-4mm}
%\end{table*}







\subsection{Experimental results}
\myparatight{Impact of  attackers' resources and  attack orderings}
%In each attack iteration, the attacker needs to send spoofing messages to the uncompromised trustees of each user that is not compromised yet. Thus, 
The number of attack iterations is closely related to the costs of sending spoofing messages. Figure~\ref{impact-a-both} illustrates the expected number of compromised users (Figure~\ref{impact-a}) and the expected number of required spoofing messages (Figure~\ref{impact-a-cost}) as a function of the number of attack iterations on Flickr for the ordering construction strategies O-Random and O-Gradient. The seed selection strategy is S-Degree and the trustee selection strategy is T-CF.   

First, we find that a strong attacker (e.g.,  an attacker controlling a botnet) can perform firest fire attacks with low costs. This is because such an attacker can send out billions of messages \emph{per day} with a low cost~\cite{emailcost}, which is far more than that needed to spoof trustees in our experiments. 

%In each attack iteration, the attacker needs to wait for the trustees to notice the messages and retrieve the verification codes. Schechter et al.~\cite{Schechter09} found that waiting for just one hour already achieves an average spoofing probability around 0.05.  Conservatively, suppose the attacker spends one day waiting for the trustees' responses   in each attack iteration, then the attacker can complete one attack iteration within one day, resulting in 10 days to finish the 10 attack iterations. 


%Second, we naturally observe that an attacker can compromise more users with more resources (i.e., more attack iterations).

Second, we find that the ordering construction strategy O-Gradient compromises more users and requires fewer spoofing messages  than O-Random when the attacker performs a given number of attack iterations. 
%For instance, the expected number of users compromised by O-Gradient increases by 40\% in the first attack iteration. 
In other words, given the number of spoofing messages the attacker can send,  the attacker should adopt O-Gradient  to construct the attack orderings. 

Similar conclusions are applicable to other combinations of seed selection strategies and trustee selection strategies. Thus, we don't show the corresponding results for conciseness.


%\begin{figure}[!ht]
%\centering
%%\vspace{-2mm}
%{\includegraphics[width=0.45\textwidth, height=2in]{{impact-rp-alternative-3-1000-0.05}.pdf}}
%%\subfloat[Google+]{\includegraphics[width=0.33\textwidth, height=2in]{{comparison-attack-defense-google-k3-1000-0.05}.pdf}\label{google-attack-defense}}
%%\subfloat[Twitter]{\includegraphics[width=0.33\textwidth, height=2in]{{comparison-attack-defense-twitter-k3-1000-0.05}.pdf}\label{twitter-attack-defense}}
%\caption{The expected number of compromised users as a function of the average recovery probability (i.e., $p_r$) on Flickr. We observe that changing passwords of compromised users quickly (i.e., increasing the recovery probability) after detecting forest fire attacks can effectively defend against forest fire attacks.}
%\label{impact-rp}
%\vspace{-4mm}
%\end{figure}

%\myparatight{Impact of detecting forest fire attacks} Figure~\ref{impact-rp} shows the expected number of compromised users as a function of the average recovery probability (i.e., $p_r$) on Flickr. The seed selection strategy is S-Degree and the trustee selection strategy is T-CF.  
% We found that the expected number of compromised users decreases dramatically  after $p_r$ is bigger than around 0.4. Our results imply that it is important for compromised users to change their passwords quickly (i.e., increasing the recovery probability) once the forest fire attacks are detected. 


\begin{figure}[!ht]
\centering
%\vspace{-2mm}
{\includegraphics[width=0.4\textwidth, height=1.8in]{{comparison-attack-defense-cost-flickr-k3-1000-0.05}.pdf}}
%\subfloat[Google+]{\includegraphics[width=0.33\textwidth, height=2in]{{comparison-attack-defense-google-k3-1000-0.05}.pdf}\label{google-attack-defense}}
%\subfloat[Twitter]{\includegraphics[width=0.33\textwidth, height=2in]{{comparison-attack-defense-twitter-k3-1000-0.05}.pdf}\label{twitter-attack-defense}}
\caption{The expected number of required spoofing messages for different seed users selection strategies and trustee selection strategies on Flickr. We observe that our strategy T-Degree can increase the attacker's costs by a few times in some cases.}
\label{attack-defense-cost}
%\vspace{-2mm}
\end{figure}

\myparatight{Impact of seed users selection strategies and trustee selection strategies} 
%Suppose the set of attack strategies the adversary could adopt are A-RANDOM, A-DEGREE and A-CLOSENESS and the defense strategies users or OSN operators could use are D-RANDOM, D-CN, D-DEGREE and D-COMMUNITY.
Figure~\ref{attack-defense} and Figure~\ref{attack-defense-cost} show the expected number of compromised users and the expected number of required spoofing messages respectively for different seed selection strategies and trustee selection strategies. 
%Note that the number of attack iterations is 10, and thus the costs of sending spoofing messages are less than \$2,500 in each forest fire attack to each of the three social networks\footnote{We assume the average cost to send a spoofing email is \$0.00001~\cite{emailcost}.}. 
We can draw a few conclusions.  



First, we find that forest fire attack is a potential big threat. For instance, when the seed users are appointed as trustees of many users (i.e., S-Degree) and the trustees are selected by T-CF, the attacker can compromise around 190,000, 660,000, and 3,760,000 users in the three social networks, 
%which are 81\%, 21\%, and 83\%  
 respectively. This represents a growth of two to three orders of magnitude from the 1,000 seed users. However, our strategy T-Degree can decrease the expected number of compromised users by one to two orders of magnitude. For instance, the expected number of compromised users of T-Degree is 53 times smaller than that of T-CF on Twitter when the seed users selection strategy is S-Degree. Moreover, our  strategy T-Degree can increase the costs for attackers by a few times in some cases. For instance, the cost of sending spoofing messages of T-Degree is 3 times bigger than that of T-CF and that of T-AA on Flickr when the seed users are appointed as trustees of many users. The reason is that the trustee networks constructed by T-Degree are more loosely connected, which makes it harder for forest fire attacks to propagate among them. 


%Since social networks have tightly connected cores which consist of users with relatively high degrees~\cite{Mislove07}, the trustee selection strategies (i.e., T-CF, T-JC, and T-AA) that are based on common friends mainly select trustees from the cores, which makes the corresponding trustee networks tightly connected. However, via global optimization, T-Degree might select users which are not in the network cores  as trustees. As a result, the trustee networks constructed by T-Degree are more loosely connected, and thus it is harder for the forest fire attacks to propagate among them.  

Second, even if the  seed users are distributed among  a social network uniformly at random (i.e., S-Random), the attacker  can still compromise dozens of times more users. For instance, the attacker can still compromise 65 to 80 times more users in Twitter depending on how trustees are selected.   

%T-Random vs. T-Degree
%Third, the expected number of compromised users of  T-Degree is significantly smaller than that of T-Random for  seed selection strategies S-Degree and S-Badrank on Flickr and Twitter, though their differences are less significant on Google+. The reason why T-Degree performs better is that it optimizes the trustee selections globally. Furthermore, the differences are less notable on Google+ because the average number of friends of users on Google+ is smaller (see Table~\ref{dataset}). More specifically, the smaller number of friends makes the optimization opportunity of T-Degree smaller on Google+. 

%T-CF vs. T- and T-AA
Third, T-JC works better than T-AA which performs better than T-CF for all seed users selection strategies except S-Random. We find that the outdegree distributions of the trustee networks constructed by T-CF are skewed towards high degrees the most while those constructed by T-JC are skewed towards low degrees the most. Thus, the seed users in the trustee networks constructed by T-JC have lower outdegrees than  those  constructed by T-AA, which have lower outdegrees than those constructed by T-CF. As a result, T-JC performs better than T-AA and T-AA performs better than T-CF.  

%Third, D-COMMUNITY achieves similar performances to D-DEGREE no matter what attack strategy is adopted. The possible reason is that some users are selected as trustees for users from multiple communities, compromising which results in cascades among different communities. It's an interesting future work to explore other community detection algorithms such as Normalized Cuts~\cite{Shi00},  MCL~\cite{Dongen08} and Metis~\cite{Karypis98}, and propose new definitions of community in the context of trustee-based social authentications.  



\begin{figure}[!t]
\centering
%\vspace{-2mm}
{\includegraphics[width=0.4\textwidth, height=1.8in]{{optional-spoofing-attacks-flickr-k3-1000-0.05}.pdf}}
\caption{The ratios between the expected number of  users that are compromised without spoofing attacks and those with spoofing attacks for different seed selection strategies and different trustee selection strategies on Flickr. We find that the expected number of compromised users only decreases by 20\% to 25\% when the attacker does not use spoofing attacks in some cases, which implies that spoofing attacks are optional.}
\label{optional-spoofing-attacks}
%\vspace{-2mm}
\end{figure}


\myparatight{Impact of spoofing attacks} The attacker can choose not to send any spoofing message, which requires no costs of sending spoofing messages. Moreover, spoofing probabilities might decrease as the attacker performs more attack iterations because trustees become aware of the spoofing attacks, and we consider an extreme case where spoofing probabilities are zero in all attack iterations.  That spoofing probabilities are zero is equivalent to that the attacker does not use spoofing attacks in terms of the number of compromised users. 

Figure~\ref{optional-spoofing-attacks} shows the ratios between the expected number of  users that are compromised without spoofing attacks and those with spoofing attacks for different seed users selection strategies and  trustee selection strategies on Flickr. 


We find that, without spoofing attacks, 
%the expected number of compromised users decreases by 80\% to 90\% when the trustee selection strategy is T-Random or T-Degree, which means that it is important for attackers to leverage spoofing attacks in these cases. However, 
 the expected number of compromised users only decreases by 20\% to 25\% when the trustee selection strategy is T-CF or T-AA and the seed users selection strategy is not S-Random, which means that the attacker can still compromise  orders of magnitude more users and that spoofing attacks are optional in some cases.

%Next, we will study the impact of $m_u$, $k$, $p_s(v,u)$,  $n_s$, and $p_r$. T



%\begin{figure*}[!t]
%\centering
%\subfloat[$k=3$]{\includegraphics[width=0.33\textwidth, height=1.8in]{{secure-region-k3}.pdf}\label{secure-region-k}}
%\subfloat[$p_s=0.1$]{\includegraphics[width=0.33\textwidth, height=1.8in]{{secure-region-ps0.1}.pdf}\label{secure-region-ps}}
%\subfloat[$n_s=1000$]{\includegraphics[width=0.33\textwidth, height=1.8in]{{secure-region-N01000}.pdf}\label{secure-region-N0}}
%\caption{Illustration of the secure configurations of parameters $k$, $p_s$ and $n_s$.  a) Fixing $k=3$. b) Fixing $p_s=0.1$. c) Fixing $n_s=1000$. Note that $n_s$ in a) and b) is transformed to be percentage of the corresponding social network sizes. 
%%The regions under the curves in a) and b) and the regions above the curves in c) are secure, which means large cascades of compromising will not happen. 
%}
%\label{secure_region}
%\end{figure*}

\begin{figure}[!t]
%\vspace{-4mm}
\centering
\subfloat[Impact of $m$]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-m}.pdf}\label{impact-m}}
\subfloat[Impact of $k$]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-k-0.05-1000}.pdf}\label{impact-k}}
%\vspace{-2mm}

\subfloat[Impact of $p_s$]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-ps-3-1000}.pdf}\label{impact-ps}}
\subfloat[Impact of $n_s$]{\includegraphics[width=0.25\textwidth, height=1.5in]{{impact-N0-3-0.05}.pdf}\label{impact-ns}}
%\vspace{-2mm}

\subfloat[Impact of $p_r$]{\includegraphics[width=0.4\textwidth, height=1.8in]{{impact-rp-3-1000-0.05}.pdf}\label{impact-rp}}
\caption{Impact of $m$, $k$, $p_s$,  $n_s$, and $p_r$. 
% where $m_u=m$ for all users $u$ that adopt the trustee-based social authentication service and $p_s(v,u)=p_s$ for all edges $(v,u)$ in the trustee network.  
 We find that $k=4$ is a good tradeoff between security and usability.  
}
\label{phase_transition}
%\vspace{-2mm}
\end{figure}


\myparatight{Impact of {\bf $m_u$, $k$, $p_s^{(t)}(v,u)$,  $n_s$,  and $p_r^{(t)}(u)$}} Towards this end, we assume that the attacker and the defender are making their best choices, i.e., the seed selection strategy is S-Degree and the trustee selection strategy is T-Degree. 
For simplicity, we assume $m_u=m$ for all users $u$ who adopt the trustee-based social authentication service and $p_s^{(t)}(v,u)=p_s$ for all edges $(v,u)$ in the trustee network and attack iterations. Moreover, we consider zeroth-order approximation of recovery probabilities, i.e., we use the average recover probability to approximate recover probabilities of all users in different attack iterations. In other words, $p_r^{(t)}(u)=p_r$ for all users and attack iterations. $p_r$ represents the average fraction of compromised users that realize their accounts are compromised and take actions to recover them in each attack iteration. 

   Figure~\ref{phase_transition} shows the impact of $m$, $k$, $p_s$,  $n_s$, and $p_r$. Note that the x-axis in Figure~\ref{impact-ns} is the percentage of users that adopt the trustee-based social authentication service.  We have  a few observations. 

Naturally, we observe that the expected number of compromised users decreases with $k$ and $p_r$, and it  increases with $m$, $p_s$, and $n_s$. Moreover, the trends are \emph{qualitatively} similar on the three social networks for each of the five parameters, which indicates the generality of our results.

%his could be explained by the fact that every user that adopts the trustee-based social authentication service selects the same number of trustees in our setting, which results in a trustee network in which those users have the same indegree. 

The parameters $m$ and $k$ balance between security and usability. Specifically, a smaller $m$ or a bigger $k$ makes the system more secure but less usable.  Figure~\ref{impact-k} shows that the expected number of compromised users decreases dramatically when $k$ increases from 1 to 4. For instance, the expected number of compromised users decreases by around one order when $k$ changes from 3 to 4. However,  the decrease is not significant when $k$ increases from 4 to 5.  Existing trustee-based social authentication systems~\cite{Schechter09,facebookSocAuth} set $k$ to be 3; our observations indicate that they could set $k$ to be 4 to better balance between security and usability. 


We find that the expected number of compromised users changes dramatically when $p_s$ is around 0.2 on all the three social networks. Moreover, almost all users that have adopted the trustee-based social authentication  service are compromised when $p_s$ is bigger than around 0.3.   Our results imply that it is urgent to mitigate the spoofing attacks via designing better user interfaces to remind users of not easily sharing the verification codes to others via messages. 

The expected number of compromised users increases dramatically with $n_s$ in the range where $n_s$ is small. This implies that obtaining a few more seed users enables the attacker to compromise significantly more users when the number of seed users is small. Moreover, even if the number of seed users is 0, the attacker can still compromise thousands of nodes in Flickr and tens of thousands of nodes in Google+ and Twitter. 


The expected number of compromised users significantly decreases with $p_r$. For instance, the number of compromised users decreases by one order in all the three social networks when around 40\% of compromised users recover to be uncompromised in each attack iteration (i.e., $p_r=0.4$). Our results imply that it is important for users to take actions to recover their accounts quickly when suspicious activities of their accounts are detected.  



%\myparatight{Secure configurations of $k$, $p_s$ and $n_s$}
%
%In practice, it is useful for both attackers and defenders to know the configurations of the parameters that can lead to large cascades of compromising (i.e., phase transition). On one hand, such configurations inform attackers the number of users they need to collude so that the forest fire attacks can compromise a large number of nodes. On the other hand, defenders can set the number of required trustees $k$ appropriately to balance the security and usability. 
%
%To explore such configurations, we fix two parameters and search for the phase transition point of the third parameter by binary search. Figure~\ref{secure_region} illustrates such configurations of parameters.  The regions under the curves in Figure~\ref{secure-region-k} and \ref{secure-region-ps} and the regions above the curves in Figure~\ref{secure-region-N0} are secure, which means large cascades of compromising will not happen when parameters are in these regions. We can draw a few conclusions from the figures.
%
%First, the secure region occupies a small portion of the entire parameter space. This implies that defenders should carefully config the system parameters to prevent large cascades of compromising. In practice, a defender should find the secure regions of their specific trustee-based social authentication system, and guarantee that the system parameters are set to be in the secure regions. For instance, they can first estimate parameters $p_s$ and $n_s$ via user studies, and then config $k$ appropriately. 
% 
%Second, when $k$ is fixed, to incur large cascades of compromising, the number of users attackers need to collude increases dramatically as the spoofing probability $p_s$ decreases. This implies that trustee-based social authentication administrators should decrease the spoofing probability via informing their users the potential risks of sharing authentication code and educating them about spoofing attacks and our forest fire attacks.     
%
%\myparatight{Correlations with local network structure}


%\subsection{Summary}
%We have the following conclusions via extensive evaluations on three social networks.
%\begin{packeditemize}
%%\item We find that the attacker can finish a forest fire attack within a short period of time and with a low cost. Naturally, we observe that an attacker can compromise more users with more resources. Moreover, we find that the ordering construction strategy O-Gradient compromises more users and requires fewer spoofing messages than O-Random when the attacker performs a given number of attack iterations. 
%
%\item We find that the ordering construction strategy O-Gradient compromises more users and requires fewer spoofing messages than O-Random when an attacker performs a given number of attack iterations. Moreover,  starting from a small number (e.g., 1000) of seed users,  an attacker can further compromise two to three orders of magnitude more users via forest fire attacks in some scenarios with low costs of sending spoofing messages. 
%
%\item We observe that our global trustee selection strategy can decrease the expected number of compromised users by one to two orders of magnitude and increase the costs for attackers by a few times in some cases. 
%
%\item We find that the recovery threshold should be set to be 4 to better balance between security and usability; it is urgent to reduce the spoofing probability, e.g., via designing better user interfaces to remind users of not easily sharing verification codes through emails/messages; and it is important for users to change their passwords or even re-select their trustees quickly when suspicious activities of their accounts are detected. 

%\end{packeditemize} 
 
\section{Discussion}
\label{sec:discussion}
%\myparatight{Trust social networks} 
%We have shown that the trustee networks constructed by the global defense strategy D-Degree can better constrain the propagation of forest fire attacks than those constructed by the local defense strategies including D-Random and D-CF. 
%To increase the usability and security of a social authentication, it is crucial for the service provider to obtain a trust social network whose edges represent trust/close relationships between users and to select trustees from the trust social network instead of the friendship network. Indeed, the service provider  can obtain or approximate such trust relationships through replacing friendships with interactions~\cite{wilson:eurosys09}, inferring tie strengths~\cite{gilbert:chi09} and/or asking users to rate their social contacts~\cite{sybildefender}.  From the perspective of usability, trusted/close friends might be more responsive so that it's easier/faster for the user to obtain verification codes from them. From the perspective of security, trusted/close friends might be less likely to collaborate with each other to attack or prank the user.  

\myparatight{A greedy seed users selection strategy} An attacker could use a greedy strategy to select seed users. Specifically,  the attacker selects  seed users one by one.  To select a seed user, the attacker iterates over each user that is not a seed user yet; for each such user $u$, the attacker pretends that $u$ is a seed user and  simulates our security model to predict the corresponding expected number of compromised users; and the user $u$ which increases the expected number of compromised users by the most is added as a new seed user. 

We compared this greedy strategy with other seed users selection strategies using a small subnetwork sampled from the Google+ dataset and found that it can compromise more users. However, it is not scalable to large social networks. It is an interesting future work to make the strategy scalable.     

\myparatight{Community-based trustee selection strategy}  We can also design a trustee selection strategy based on some notion of community. Specifically, we could select trustees for users such that the trustee network consists of isolated communities, which could constrain the propagation of forest fire attacks. It is an interesting future work to explore these community-based trustee selection strategies.  

%\myparatight{Detecting forest fire attacks} In our model, we assume that compromised accounts stay compromised in all  attack iterations. In practice, the service provider might detect  a forest fire attack via observing an abnormally large number of account recovery requests, and then it asks users to reset their passwords or even re-select their trustees. In such scenarios, the attacker cannot easily obtain a verification code from a user that is previously compromised.  In the future, we plan to incorporate such scenarios in our security model.
%
%For instance, we could consider that a compromised account in the $t$th attack iteration will be recovered in the $(t+1)$th attack iteration with some probability, and this node can be compromised again. It would be interesting to study the propagation of forest fire attacks in such cases.      

%\myparatight{Registration Phase is important for security} The trustee-based social authentication system requires a user to be authenticated to register the trustees before using the account recovery service. We find that QQ, the largest instant messaging service in China, enables users to recover their accounts with the help of their friends. However, they don't adopt the Registration Phase. Instead, they ask the user to appoint a few trustees on the fly when she issues the account recovery request. 

%Attackers can easily attack such a system. An attacker can create a few fake accounts and send friend requests to a same victim. If the victim accepts the friend requests, then the attacker can compromise the victim's account. Specifically, the attacker sends an account recovery request to QQ and appoints his fake accounts as the trustees. Thus, the Registration Phase is important for the security of social authentications.


\myparatight{Limiting the issuance of verification codes}
A compromised user $u$ might request a verification code from the service provider when the attacker performs an attack trial to a user who selects $u$ as a trustee. Thus, a compromised user who is a trustee of many other users might request many verification codes in each attack iteration.   Therefore, limiting the number of verification codes that each user can request within a given period of time (e.g., one hour)  can slow down forest fire attacks. It is an interesting future work to explore the impact of such rate limitings on  forest fire attacks and what strategies attackers can adopt to maximize the number of compromised users given a time constraint. 

%\myparatight{A practical attack to Facebook's Trusted Contacts?} 
%\myparatight{Replacing passwords?} Bonneau et al.~\cite{Bonneau12} evaluated a wide range of authentication mechanisms-such as password management software, graphical password schemes, and biometrics, etc.-in terms of their usability, deployability and security benefits, and concluded that none of these mechanisms can replace passwords. We want to point out that trustee-based social authentication does not intend to replace passwords. Trustee-based social authentications are designed to be  a last-resort authenticator when the major authenticators (e.g., passwords) are compromised or unavailable due to various reasons (e.g., users could forget their passwords when passwords are the major authenticator). 

\section{Related Work}
\label{sec:related_work}
\subsection{Social authentications}
Depending on how friends are involved in the authentication process, social authentications can be classified into \emph{trustee-based} and \emph{knowledge-based}  social authentications. In trustee-based social authentications~\cite{Brainard06},  the selected friends aid the user in the authentication process. Knowledge-based social authentication, however, asks the user questions about his or her selected friends, and thus friends are not directly involved.

\myparatight{Trustee-based social authentication systems} Authentication is traditionally based on three factors: \emph{something you know} (e.g., a password), \emph{something you have} (e.g., a RSA SecurID), and \emph{something you are} (e.g., fingerprint). 

Brainard et al.~\cite{Brainard06} proposed to use the fourth factor, i.e., \emph{somebody you know}, to authenticate users. We call the fourth factor  trustee-based social authentication. Originally, Brainard et al. combined trustee-based social authentication with some other factor as a two-factor authentication mechanism. It was later adapted to be a backup authenticator~\cite{facebookTF,facebookSocAuth,Schechter09}. For instance, Schechter et al. [2] designed and built a prototype of trustee-based social authentication system which was integrated into Microsoft’s Windows Live ID system. Moreover, Facebook designed Trusted Friends in October, 2011~\cite{facebookTF}, and it was improved to be Trusted Contacts~\cite{facebookSocAuth} in May, 2013.


\myparatight{Knowledge-based social authentication systems} Such social authentications are still based on \emph{something you know}. Yardi et al.~\cite{Yardi08} proposed a knowledge-based authentication system based on photos to test if a user belongs to the group (e.g., interest groups in Facebook) that he or she tries to access. Facebook recently launched a similar photo-based social authentication system~\cite{Rice11}, in which Facebook shows a few photos of a friend of a user and asks the user to name the friend. Such system essentially relies on the knowledge that the user knows the person in the shown photos. However, recent work has shown, via theoretical modeling~\cite{Kim12-soc-auth} and empirical evaluations~\cite{Polakis12}, that photo-based social authentications are not resilient to various attacks such as automatic face recognition techniques, questioning their use as a backup authentication mechanism. 

%Kim et al.~\cite{Kim12-soc-auth} proposed a security model to quantify the security of the Facebook's photo-based social authentication system. Moreover, they also pointed out the possibility of using face recognition techniques as an attack to the face-based social authentication systems. Polakis~\cite{Polakis12} designed an automated attacking system, which is based on face recognition techniques, to demonstrate the feasibility of carrying out large-scale attacks against face-based social authentication. 

\subsection{Diffusion models}
%Our forest fire attacks essentially describe diffusion processes in a trustee network. There are already  some diffusion models such as \emph{updates propagation models} in Byzantine distributed systems,  \emph{information propagation models}, and  \emph{epidemic propagation models}. The key difference between forest fire attacks and the previous diffusion models results from the fact that attackers can obtain a verification code from an uncompromised node with some probability via spoofing attacks in forest fire attacks.   We review a few representative diffusion models from different research areas and discuss the differences between them and our work.
%Due to the limited space, we review a few representative diffusion models from different research areas and discuss the differences between them and our work in Appendix~\ref{diffusion_model}. 
Our forest fire attacks essentially describe diffusion processes in a trustee network.  We review a few representative diffusion models from different research areas and discuss the differences between them and our work.

\myparatight{Updates propagation models} Malkhi et al.~\cite{updatespropagation} proposed the $l$-Tree propagation model to diffuse updates among a large distributed system of data replicas, some of which might exhibit Byzantine failures. Their model assumes a point-to-point communication for each pair of nodes.  A node that already receives the update is called \emph{active}, otherwise it is called \emph{inactive}. Initially, a small set of nodes are active. Each active node is associated with a candidate set of nodes. In each iteration, each active node is allowed to send the update to at most $F$ nodes which are selected from the corresponding candidate set uniformly at random. An inactive node becomes active if it receives the update from at least $k$ other nodes. 

There are two key differences between our forest fire attacks and the $l$-Tree propagation model. First, an uncompromised (i.e., inactive) node can receive verification codes (i.e., updates) from uncompromised trustees via spoofing attacks in forest fire attacks while an inactive node can only receive updates from active nodes in the $l$-Tree model. Second, in each iteration, each compromised node sends verification codes to \emph{all} nodes that select it as a trustee in forest fire attacks while an active node can only send the update to  at most $F$ nodes in the $l$-Tree model.   


\myparatight{Information propagation models}
Models for how products and  innovations propagate on a social network have been studied in various domains such as viral marketing and  the spread of technological innovations. These models can be divided into two categories~\cite{Kempe03}: \emph{linear threshold model} and \emph{independent cascade model}. Again, a node is said to be \emph{active} if it already adopts the corresponding product or innovation, otherwise it is \emph{inactive}. In both models, a small set of  nodes are active initially.

\emph{Linear threshold model:} In this model, each node $u$ is associated with a threshold,  which indicates the fraction of $u$'s friends that must become active before $u$ becomes active.  The propagation proceeds deterministically in discrete iterations: in the $t$th iteration, an inactive node becomes active if its fraction of active friends is no less than $u$' activation threshold.


\emph{Independent cascade model:} Different  from the linear threshold model, the independent cascade model proceeds in discrete iterations according to the following randomized rule: when a node $u$ first becomes active in the $t$th iteration, it has a \emph{single} chance to activate each of its currently inactive friend $v$ and succeed with some probability which encodes the influence of $u$ to $v$.

The key difference is that verification codes can be propagated from an uncompromised (i.e., inactive) node to another uncompromised node via spoofing attacks in forest fire attacks while an inactive node can only be activated by active nodes in the linear threshold model and the independent cascade model.  Moreover, an active node only has a single chance to activate its friends in the independent cascade model while a compromised node can send verification codes to the uncompromised nodes that select it as a trustee as many times as it wants. 

%Note that  the linear threshold model is a special case of forest fire attacks reduced to where the activation threshold of node $u$ is $k/m_u$.  when the spoofing probability is 0,

\myparatight{Epidemic propagation models} Epidemic propagation models describe the propagations of various contagious diseases such as sexually transmitted diseases, inﬂuenza, and measles.  

One popular epidemic model is the so-called SIR model (Chapter 21 of~\cite{Easley10}). Different from the above reviewed models in which each node can be either active or inactive, SIR model assumes that each node can be in one of the three states, i.e., \emph{susceptible}, \emph{infectious}, and \emph{removed}.  Initially, a set of nodes are infectious and all other nodes are susceptible. Each infectious node $u$ remains infectious for a fixed number of iterations $I$. In each of the $I$ iterations, $u$ has some probability of passing the disease to each of its susceptible neighbors.  After $I$ iterations, $u$ becomes removed, which means that $u$ cannot catch nor propagate the disease any more. 


Again, a susceptible (i.e., uncompromised) node can only be influenced by  infectious (i.e., compromised) nodes in the SIR model, which is different from the forest fire attacks. Moreover, the state \emph{removed} is not meaningful in the context of forest fire attacks since a node could be compromised again even if it recovers the account and resets the password. 

\myparatight{Summary} The key difference between forest fire attacks and previous diffusion models lies in the spoofing attacks. Specifically, an uncompromised node can obtain verification codes from its uncompromised trustees via spoofing attacks in the forest fire attacks while an inactive or susceptible node can only be influenced by its active or infectious neighbors in previous diffusion models. 

\section{Conclusion and Future Work}
In this paper, we provide the first systematic study about the security of trustee-based social authentications. First, we introduce \emph{forest fire attacks}. In these attacks, an attacker first obtains a small number of compromised seed users and then iteratively attacks the rest of users according to a priority ordering of them. Second, we construct a probabilistic model to formalize the threats of forest fire attacks and their costs for attackers. Third, we introduce a few strategies to select seed users and construct priority orderings, and we discuss various defense strategies. Fourth, via extensive evaluations using three real-world social network datasets, we find that forest fire attack is a potential big threat. For instance, with a small number (e.g., 1,000) of seed users, an attacker can further compromise two to three orders of magnitude more users in some scenarios with low (or even no) costs of sending spoofing messages. However, our defense strategy, which guarantees that no users are trustees of too many other users, can decrease the number of compromised users by one to two orders of magnitude and increase the costs for attackers by a few times in some cases. Moreover,  the recovery threshold should be set to be 4 to better balance between security and usability.

 
A few future directions include evaluating forest firest attacks on real social authentication systems such as Facebook's Trusted Contacts, designing new attack and defense strategies, and optimizing forest fire attacks given a time constraint. 


%\section*{Acknowledgement}
%We would like to thank Dawn Song for her insightful suggestions. This research was supported by Intel through the ISTC for Secure Computing. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies. 


%{\small
%\bibliography{refs}
%\bibliographystyle{abbrv}
%
%}

\begin{thebibliography}{10}

\bibitem{aa03}
L.~A. Adamic and E.~Adar.
\newblock Friends and neighbors on the web.
\newblock {\em Social Network}, 25(3):211--230, 2003.

\bibitem{badrank}
{BadRank}.
\newblock \url{http://pr.efactory.de/e-pr0.shtml}.

\bibitem{UserProbing-Bonneau10}
J.~Bonneau and S.~Preibusch.
\newblock The password thicket: technical and market failures in human
  authentication on the web.
\newblock In {\em WEIS}, 2010.

\bibitem{Brainard06}
J.~Brainard, A.~Juels, R.~Rivest, M.~Szydlo, and M.~Yung.
\newblock Fourth-factor authentication: Somebody you know.
\newblock In {\em CCS}, 2006.

\bibitem{Poddand96}
J.~P.~J. Bunnell and R.~Henderson.
\newblock Cost-effective computer security: Cognitive and associative
  passwords.
\newblock In {\em OZCHI}, 1996.

\bibitem{Easley10}
D.~Easley and J.~Kleinberg.
\newblock {\em Networks, Crowds, and Markets: Reasoning About a Highly
  Connected World}.
\newblock Cambridge University Press, 2010.

\bibitem{facebookSocAuth}
{Facebook's Trusted Contacts}.
\newblock \url{goo.gl/xHmVHA}.

\bibitem{facebookTF}
{Facebook's Trusted Friends}.
\newblock \url{goo.gl/KdyYXJ}.

\bibitem{Gao10}
H.~Gao, J.~Hu, C.~Wilson, Z.~Li, Y.~Chen, and B.~Zhao.
\newblock Detecting and characterizing social spam campaigns.
\newblock In {\em IMC}, 2010.

\bibitem{gilbert:chi09}
E.~Gilbert and K.~Karahalios.
\newblock Predicting tie strength with social media.
\newblock In {\em CHI}, 2009.

\bibitem{Gong12-imc}
N.~Z. Gong, W.~Xu, L.~Huang, P.~Mittal, E.~Stefanov, V.~Sekar, and D.~Song.
\newblock Evolution of social-attribute networks: Measurements, modeling, and
  implications using google+.
\newblock In {\em IMC}, 2012.

\bibitem{Jaccard1901}
P.~Jaccard.
\newblock {\'E}tude comparative de la distribution florale dans une portion des
  alpes et des jura.
\newblock {\em Bulletin de la Soci{\'e}t{\'e} Vaudoise des Sciences
  Naturelles}, 1901.

\bibitem{Kempe03}
D.~Kempe, J.~Kleinberg, and E.~Tardos.
\newblock Maximizing the spread of influence through a social network.
\newblock In {\em KDD}, 2003.

\bibitem{Kim12-soc-auth}
H.~Kim, J.~Tang, and R.~Anderson.
\newblock Social authentication: Harder than it looks.
\newblock In {\em FC}, 2012.

\bibitem{Kwak10}
H.~Kwak, C.~Lee, H.~Park, and S.~Moon.
\newblock What is twitter, a social network or a news media?
\newblock In {\em WWW}, 2010.

\bibitem{updatespropagation}
D.~Malkhi, Y.~Mansour, and M.~K. Reiter.
\newblock Di usion without false rumors: on propagating updates in a byzantine
  environment.
\newblock {\em Theoretical Computer Science}, 2003.

\bibitem{Mislove08}
A.~Mislove, H.~S. Koppula, K.~P. Gummadi, P.~Druschel, and B.~Bhattacharjee.
\newblock Growth of the flickr social network.
\newblock In {\em WOSN}, 2008.

\bibitem{nodeCentrality}
{Node Centrality}.
\newblock \url{https://en.wikipedia.org/wiki/Centrality}.

\bibitem{Okamoto08}
K.~Okamoto, W.~Chen, and X.-Y. Li.
\newblock Ranking of closeness centrality for large-scale social networks.
\newblock In {\em FAW}, 2008.

\bibitem{Polakis12}
I.~Polakis, M.~Lancini, G.~Kontaxis, F.~Maggi, S.~Ioannidis, A.~D. Keromytis,
  and S.~Zanero.
\newblock All your face are belong to us: Breaking facebook's social
  authentication.
\newblock In {\em ACSAC}, 2012.

\bibitem{Rice11}
A.~Rice.
\newblock Facebook's knowledge-based social authentication.
  http://blog.facebook.com/blog.php?post=486790652130.

\bibitem{Sabidussi66}
G.~Sabidussi.
\newblock The centrality index of a graph.
\newblock {\em Psychometrika}, 1966.

\bibitem{Schechter09-oakland}
S.~Schechter, A.~J.~B. Brush, and S.~Egelman.
\newblock It's no secret: Measuring the security and reliability of
  authentication via `secret' questions.
\newblock In {\em IEEE S \& P}, 2009.

\bibitem{Schechter09}
S.~Schechter, S.~Egelman, and R.~W. Reeder.
\newblock It's not what you know, but who you know.
\newblock In {\em CHI}, 2009.

\bibitem{emailcost}
{Spam messages}.
\newblock \url{http://en.wikipedia.org/wiki/Botnet}.

\bibitem{Yardi08}
S.~Yardi, N.~Feamster, and A.~Bruckman.
\newblock Photo-based authentication using social networks.
\newblock In {\em WOSN}, 2008.

\bibitem{Zviran90}
M.~Zviran and W.~J. Haga.
\newblock User authentication by cognitive passwords: an empirical assessment.
\newblock In {\em JCIT}, 1990.

\end{thebibliography}



\appendices
\section{The attack maximization problem is NP-Complete}
\label{theorem:attack:proof}
To prove the hardness of the attack maximization problem, we only need to show the hardness of a corresponding decision problem, i.e., given $G_T,k,n_s,n,$ and an integer $l$, it is NP-Complete to decide whether $n_c(G_T,k,n_s,n)\geq l$. This follows from a  reduction from the NP-Complete Set Cover problem: given a ground set $X=\{x_1,\ldots,x_a\}$, and a collection of its subsets $S_1, S_2,\cdots, S_m$, we want to determine if there exists $t$ subsets $S_{i_1},S_{i_2},\cdots,S_{i_t}$ such that $S_{i_1}\cup S_{i_2} \cup \cdots \cup S_{i_t}=X$. We show that this can be viewed as a special case of the attack maximization problem, where the spoofing probabilities and recovery probabilities are all $0$. 

Given any instance of a set cover problem, we construct a corresponding trustee network as follows: there are $k$ nodes for each $S_j$, and one node for each $x_i$; each $x_i$ has all the $k$ copies of $S_j$ as trustees iff $x_i\in S_j$; in addition, for each $S_j$ we have $a^2k^2$ dummy nodes each of which designates the $k$ copies of $S_j$ as trustees. Then the Set Cover problem is satisfiable iff the attacker can compromise at least $l=ta^2k^2+tk+a$ nodes with a seed set whose size is $tk$, i.e., $n_c(G_T,k,tk,n)\geq l$.





%\begin{algorithm}[!t] 
%\DontPrintSemicolon 
%\KwIn{$G_T=(V_T, E_T)$, $n_s$ and $\alpha$.} 
%\KwOut{A set of seed users $S$.} 
%\Begin{
%
%//Initializing a score vector. \;
%\For{$v\in V_T$}{
%$s^{(0)}(v) \longleftarrow 1/|V_T|$ \;
%} 
%$\epsilon \longleftarrow 1$ \;
%$t \longleftarrow 0$ \;
%\While{$\epsilon > 1e-3$}{
%$\epsilon \longleftarrow 0$ \;
%$t \longleftarrow t + 1$ \;
%	\For{$v\in V_T$}{
%	%\vspace{-4mm}
%	$$s^{(t)}(v) \longleftarrow (1-\alpha)\sum_{u\in \Gamma_{T,o}(v)} \frac{s^{(t-1)}(u)}{m_u} + \alpha \frac{1}{|V_T|}$$ \;
%	%\vspace{-4mm}
%	$\epsilon \longleftarrow \epsilon + |s^{(t)}(v) - s^{(t-1)}(v)|$ \;
%	
%}
%$\epsilon \longleftarrow \epsilon/|V_T| $ \; 
%} 
%
%$S \longleftarrow$ $n_s$ users with the highest $s^{(t)}(v)$ \;
%\Return $S$\;
%} 
%\caption{The S-BadRank Strategy to Select the Seed Users} 
%\label{alg:s-badrank}
%\end{algorithm}





%\section{Further related work: diffusion models}
%\label{diffusion_model}
%\myparatight{Updates propagation models} Malkhi et al.~\cite{updatespropagation} proposed the $l$-Tree propagation model to diffuse updates among a large distributed system of data replicas, some of which might exhibit Byzantine failures. Their model assumes a point-to-point communication for each pair of nodes.  A node that already receives the update is called \emph{active}, otherwise it is called \emph{inactive}. Initially, a small set of nodes are active. Each active node is associated with a candidate set of nodes. In each iteration, each active node is allowed to send the update to at most $F$ nodes which are selected from the corresponding candidate set uniformly at random. An inactive node becomes active if it receives the update from at least $k$ other nodes. 
%
%There are two key differences between our forest fire attacks and the $l$-Tree propagation model. First, an uncompromised (i.e., inactive) node can receive verification codes (i.e., updates) from uncompromised trustees via spoofing attacks in forest fire attacks while an inactive node can only receive updates from active nodes in the $l$-Tree model. Second, in each iteration, each compromised node sends verification codes to \emph{all} nodes that select it as a trustee in forest fire attacks while an active node can only send the update to  at most $F$ nodes in the $l$-Tree model.   
%
%
%\myparatight{Information propagation models}
%Models for how products and  innovations propagate on a social network have been studied in various domains such as viral marketing and  the spread of technological innovations. These models can be divided into two categories~\cite{Kempe03}: \emph{linear threshold model} and \emph{independent cascade model}. Again, a node is said to be \emph{active} if it already adopts the corresponding product or innovation, otherwise it is \emph{inactive}. In both models, a small set of  nodes are active initially.
%
%\emph{Linear threshold model:} In this model, each node $u$ is associated with a threshold,  which indicates the fraction of $u$'s friends that must become active before $u$ becomes active.  The propagation proceeds deterministically in discrete iterations: in the $t$th iteration, an inactive node becomes active if its fraction of active friends is no less than $u$' activation threshold.
%
%
%\emph{Independent cascade model:} Different  from the linear threshold model, the independent cascade model proceeds in discrete iterations according to the following randomized rule: when a node $u$ first becomes active in the $t$th iteration, it has a \emph{single} chance to activate each of its currently inactive friend $v$ and succeed with some probability which encodes the influence of $u$ to $v$.
%
%The key difference is that verification codes can be propagated from an uncompromised (i.e., inactive) node to another uncompromised node via spoofing attacks in forest fire attacks while an inactive node can only be activated by active nodes in the linear threshold model and the independent cascade model.  Moreover, an active node only has a single chance to activate its friends in the independent cascade model while a compromised node can send verification codes to the uncompromised nodes that select it as a trustee as many times as it wants. 
%
%%Note that  the linear threshold model is a special case of forest fire attacks reduced to where the activation threshold of node $u$ is $k/m_u$.  when the spoofing probability is 0,
%
%\myparatight{Epidemic propagation models} Epidemic propagation models describe the propagations of various contagious diseases such as sexually transmitted diseases, inﬂuenza, and measles.  
%
%One popular epidemic model is the so-called SIR model (Chapter 21 of~\cite{Easley10}). Different from the above reviewed models in which each node can be either active or inactive, SIR model assumes that each node can be in one of the three states, i.e., \emph{susceptible}, \emph{infectious}, and \emph{removed}.  Initially, a set of nodes are infectious and all other nodes are susceptible. Each infectious node $u$ remains infectious for a fixed number of iterations $I$. In each of the $I$ iterations, $u$ has some probability of passing the disease to each of its susceptible neighbors.  After $I$ iterations, $u$ becomes removed, which means that $u$ cannot catch nor propagate the disease any more. 
%
%
%Again, a susceptible (i.e., uncompromised) node can only be influenced by  infectious (i.e., compromised) nodes in the SIR model, which is different from the forest fire attacks. Moreover, the state \emph{removed} is not meaningful in the context of forest fire attacks since a node could be compromised again even if it recovers the account and resets the password. 
%
%\myparatight{Summary} The key difference between forest fire attacks and previous diffusion models lies in the spoofing attacks. Specifically, an uncompromised node can obtain verification codes from its uncompromised trustees via spoofing attacks in the forest fire attacks while an inactive or susceptible node can only be influenced by its active or infectious neighbors in previous diffusion models. 

%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{neil_gong}}]{Neil Zhenqiang Gong}
%is a Ph.D. candidate in the Department of Electrical Engineering and Computer Science at the University of California at Berkeley. Prior to Berkeley, he studied computer science at the University of Science and Technology of China (USTC) and obtained B.E. in computer science in 2010. He is interested in Data-driven Security and Privacy. His research draws techniques from large scale machine learning, natural language processing, network science, etc. In particular, his recent interests include social network security and privacy, de-anonymization, and mobile security.
%\end{IEEEbiography}
%
%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{di_wang}}]{Neil Zhenqiang Gong}
%Di is a Ph.D. candidate in Computer Science at UC Berkeley. Prior to Berkeley, he studied computer science at Cornell University and obtained B.S. in computer science in 2010. He is interested in graph theory, statistical learning theory, and their applications in social computation.
%\end{IEEEbiography}

\end{document}

1402.2699.extracted_bib
{aa03 L.~A. Adamic and E.~Adar. \newblock Friends and neighbors on the web. \newblock {\em Social Network, 25(3):211--230, 2003.
1402.2699.extracted_bib
{badrank {BadRank. \newblock \url{http://pr.efactory.de/e-pr0.shtml.
1402.2699.extracted_bib
{UserProbing-Bonneau10 J.~Bonneau and S.~Preibusch. \newblock The password thicket: technical and market failures in human authentication on the web. \newblock In {\em WEIS, 2010.
1402.2699.extracted_bib
{Brainard06 J.~Brainard, A.~Juels, R.~Rivest, M.~Szydlo, and M.~Yung. \newblock Fourth-factor authentication: Somebody you know. \newblock In {\em CCS, 2006.
1402.2699.extracted_bib
{Poddand96 J.~P.~J. Bunnell and R.~Henderson. \newblock Cost-effective computer security: Cognitive and associative passwords. \newblock In {\em OZCHI, 1996.
1402.2699.extracted_bib
{Easley10 D.~Easley and J.~Kleinberg. \newblock {\em Networks, Crowds, and Markets: Reasoning About a Highly Connected World. \newblock Cambridge University Press, 2010.
1402.2699.extracted_bib
{facebookSocAuth {Facebook's Trusted Contacts. \newblock \url{goo.gl/xHmVHA.
1402.2699.extracted_bib
{facebookTF {Facebook's Trusted Friends. \newblock \url{goo.gl/KdyYXJ.
1402.2699.extracted_bib
{Gao10 H.~Gao, J.~Hu, C.~Wilson, Z.~Li, Y.~Chen, and B.~Zhao. \newblock Detecting and characterizing social spam campaigns. \newblock In {\em IMC, 2010.
1402.2699.extracted_bib
{gilbert:chi09 E.~Gilbert and K.~Karahalios. \newblock Predicting tie strength with social media. \newblock In {\em CHI, 2009.
1402.2699.extracted_bib
{Gong12-imc N.~Z. Gong, W.~Xu, L.~Huang, P.~Mittal, E.~Stefanov, V.~Sekar, and D.~Song. \newblock Evolution of social-attribute networks: Measurements, modeling, and implications using google+. \newblock In {\em IMC, 2012.
1402.2699.extracted_bib
{Jaccard1901 P.~Jaccard. \newblock {\'Etude comparative de la distribution florale dans une portion des alpes et des jura. \newblock {\em Bulletin de la Soci{\'et{\'e Vaudoise des Sciences Naturelles, 1901.
1402.2699.extracted_bib
{Kempe03 D.~Kempe, J.~Kleinberg, and E.~Tardos. \newblock Maximizing the spread of influence through a social network. \newblock In {\em KDD, 2003.
1402.2699.extracted_bib
{Kim12-soc-auth H.~Kim, J.~Tang, and R.~Anderson. \newblock Social authentication: Harder than it looks. \newblock In {\em FC, 2012.
1402.2699.extracted_bib
{Kwak10 H.~Kwak, C.~Lee, H.~Park, and S.~Moon. \newblock What is twitter, a social network or a news media? \newblock In {\em WWW, 2010.
1402.2699.extracted_bib
{updatespropagation D.~Malkhi, Y.~Mansour, and M.~K. Reiter. \newblock Di usion without false rumors: on propagating updates in a byzantine environment. \newblock {\em Theoretical Computer Science, 2003.
1402.2699.extracted_bib
{Mislove08 A.~Mislove, H.~S. Koppula, K.~P. Gummadi, P.~Druschel, and B.~Bhattacharjee. \newblock Growth of the flickr social network. \newblock In {\em WOSN, 2008.
1402.2699.extracted_bib
{nodeCentrality {Node Centrality. \newblock \url{https://en.wikipedia.org/wiki/Centrality.
1402.2699.extracted_bib
{Okamoto08 K.~Okamoto, W.~Chen, and X.-Y. Li. \newblock Ranking of closeness centrality for large-scale social networks. \newblock In {\em FAW, 2008.
1402.2699.extracted_bib
{Polakis12 I.~Polakis, M.~Lancini, G.~Kontaxis, F.~Maggi, S.~Ioannidis, A.~D. Keromytis, and S.~Zanero. \newblock All your face are belong to us: Breaking facebook's social authentication. \newblock In {\em ACSAC, 2012.
1402.2699.extracted_bib
{Rice11 A.~Rice. \newblock Facebook's knowledge-based social authentication. http://blog.facebook.com/blog.php?post=486790652130.
1402.2699.extracted_bib
{Sabidussi66 G.~Sabidussi. \newblock The centrality index of a graph. \newblock {\em Psychometrika, 1966.
1402.2699.extracted_bib
{Schechter09-oakland S.~Schechter, A.~J.~B. Brush, and S.~Egelman. \newblock It's no secret: Measuring the security and reliability of authentication via `secret' questions. \newblock In {\em IEEE S \& P, 2009.
1402.2699.extracted_bib
{Schechter09 S.~Schechter, S.~Egelman, and R.~W. Reeder. \newblock It's not what you know, but who you know. \newblock In {\em CHI, 2009.
1402.2699.extracted_bib
{emailcost {Spam messages. \newblock \url{http://en.wikipedia.org/wiki/Botnet.
1402.2699.extracted_bib
{Yardi08 S.~Yardi, N.~Feamster, and A.~Bruckman. \newblock Photo-based authentication using social networks. \newblock In {\em WOSN, 2008.
1402.2699.extracted_bib
{Zviran90 M.~Zviran and W.~J. Haga. \newblock User authentication by cognitive passwords: an empirical assessment. \newblock In {\em JCIT, 1990.