How to choose the correct Regression Model?
Lets take a simple example : Suppose your manager asked you to predict annual sales. There can be a hundred of factors (drivers) that affects sales. In this case, sales is your dependent variable. Factors affecting sales are independent variables. Regression analysis would help you to solve this problem.
In simple words, regression analysis is used to model the relationship between a dependent variable and one or more independent variables.
Which of the drivers have a significant impact on sales.
What would be the annual sales next year.
Suppose there is an observation in the dataset which is having a very high or very low value as compared to the other observations in the data, i.e. it does not belong to the population, such an observation is called an outlier. In simple words, it is extreme value. An outlier is a problem because many times it hampers the results we get.
When the independent variables are highly correlated to each other then the variables are said to be multicollinear. Many types of regression techniques assumes multicollinearity should not be present in the dataset. It is because it causes problems in ranking variables based on its importance. Or it makes job difficult in selecting the most important independent variable (factor).
When dependent variable's variability is not equal across values of an independent variable, it is called heteroscedasticity. Example - As one's income increases, the variability of food consumption will increase. A poorer person will spend a rather constant amount by always eating inexpensive food; a wealthier person may occasionally buy inexpensive food and at other times eat expensive meals. Those with higher incomes display a greater variability of food consumption.
When we use unnecessary explanatory variables it might lead to overfitting. Overfitting means that our algorithm works well on the training set but is unable to perform better on the test sets. It is also known as problem of high variance.
When our algorithm works so poorly that it is unable to fit even training set well then it is said to underfit the data. It is also known as problem of high bias.
In the following diagram we can see that fitting a linear regression (straight line in fig 1) would underfit the data i.e. it will lead to large errors even in the training set. Using a polynomial fit in fig 2 is balanced i.e. such a fit can work on the training and test sets well, while in fig 3 the fit will lead to low errors in training set but it will not work well on the test set.
Every regression technique has some assumptions attached to it which we need to meet before running analysis. These techniques differ in terms of type of dependent and independent variables and distribution.
When you have only 1 independent variable and 1 dependent variable, it is called simple linear regression.
When you have more than 1 independent variable and 1 dependent variable, it is called Multiple linear regression.
Here 'y' is the dependent variable to be estimated, and X are the independent variables and ε is the error term. βi's are the regression coefficients.
There must be a linear relation between independent and dependent variables.
There should not be any outliers present.
Sample observations should be independent.
Error terms should be normally distributed with mean 0 and constant variance.
Absence of multicollinearity and auto-correlation.
Estimating the parametersTo estimate the regression coefficients βi's we use principle of least squares which is to minimize the sum of squares due to the error terms i.e.
If no. of hours studied and no. of classes are 0 then the student will obtain 5 marks.
Keeping no. of classes attended constant, if student studies for one hour more then he will score 2 more marks in the examination.
Similarly keeping no. of hours studied constant, if student attends one more class then he will attain 0.5 marks more.
We consider the swiss data set for carrying out linear regression in R. We use lm() function in the base package. We try to estimate Fertility with the help of other variables.
Hence we can see that 70% of the variation in Fertility rate can be explained via linear regression.
It is a technique to fit a nonlinear equation by taking polynomial functions of independent variable.
In the figure given below, you can see the red curve fits the data better than the green curve. Hence in the situations where the relation between the dependent and independent variable seems to be non-linear we can deploy Polynomial Regression Models.
and can fit linear regression in the similar manner.
In case of multiple variables say X1 and X2, we can create a third new feature (say X3) which is the product of X1 and X2 i.e.
Disclaimer: It is to be kept in mind that creating unnecessary extra features or fitting polynomials of higher degree may lead to overfitting.
We are using poly.csv data for fitting polynomial regression where we try to estimate the Prices of the house given their area.
We create a dataframe where the new variable are x and x square.
Using ggplot2 package we try to create a plot to compare the curves by both linear and polynomial regression.
In logistic regression, the dependent variable is binary in nature (having two categories). Independent variables can be continuous or binary. In multinomial logistic regression, you can have more than two categories in your dependent variable.
Why don't we use linear regression in this case?
The homoscedasticity assumption is violated.
y follows binomial distribution and hence is not normal.
HR Analytics: IT firms recruit large number of people, but one of the problems they encounter is after accepting the job offer many candidates do not join. So, this results in cost over-runs because they have to repeat the entire process again. Now when you get an application, can you actually predict whether that applicant is likely to join the organization (Binary Outcome - Join / Not Join).
Elections: Suppose that we are interested in the factors that influence whether a political candidate wins an election. The outcome (response) variable is binary (0/1); win or lose. The predictor variables of interest are the amount of money spent on the campaign and the amount of time spent campaigning negatively.
Thus we choose a cut-off of probability say 'p' and if P(Yi = 1) > p then we can say that Yi belongs to class 1 otherwise 0.
If we take exponential of coefficients, then we'll get odds ratio for ith explanatory variable. Suppose odds ratio is equal to two, then the odds of event is 2 times greater than the odds of non-event. Suppose dependent variable is customer attrition (whether customer will close relationship with the company) and independent variable is citizenship status (National / Expat). The odds of expat attrite is 3 times greater than the odds of a national attrite.
In this case, we are trying to estimate whether a person will have cancer depending whether he smokes or not.
We fit logistic regression with glm( ) function and we set family = "binomial"
Quantile regression is the extension of linear regression and we generally use it when outliers, high skeweness and heteroscedasticity exist in the data.
In linear regression, we predict the mean of the dependent variable for given independent variables. Since mean does not describe the whole distribution, so modeling the mean is not a full description of a relationship between dependent and independent variables. So we can use quantile regression which predicts a quantile (or percentile) for given independent variables.
Basic Idea of Quantile Regression: In quantile regression we try to estimate the quantile of the dependent variable given the values of X's. Note that the dependent variable should be continuous.
where q is the qth quantile.
It means that for one unit increase in x the estimated increase in 25th quantile of y by 700.823 units.
Quite beneficial when heteroscedasticity is present in the data.
Distribution of dependent variable can be described via various quantiles.
It is more useful than linear regression when the data is skewed.
Disclaimer on using quantile regression!
It is to be kept in mind that the coefficients which we get in quantile regression for a particular quantile should differ significantly from those we obtain from linear regression. If it is not so then our usage of quantile regression isn't justifiable. This can be done by observing the confidence intervals of regression coefficients of the estimates obtained from both the regressions.
We need to install quantreg package in order to carry out quantile regression.
Using rq function we try to predict the estimate the 25th quantile of Fertility Rate in Swiss data. For this we set tau = 0.25.
Setting tau = 0.5 we run the median regression.
We can run quantile regression for multiple quantiles in a single plot.
We can check whether our quantile regression results differ from the OLS results using plots.
Various quantiles are depicted by X axis. The red central line denotes the estimates of OLS coefficients and the dotted red lines are the confidence intervals around those OLS coefficients for various quantiles. The black dotted line are the quantile regression estimates and the gray area is the confidence interval for them for various quantiles. We can see that for all the variable both the regression estimated coincide for most of the quantiles. Hence our use of quantile regression is not justifiable for such quantiles. In other words we want that both the red and the gray lines should overlap as less as possible to justify our use of quantile regression.
It's important to understand the concept of regularization before jumping to ridge regression.
Regularization helps to solve over fitting problem which implies model performing well on training data but performing poorly on validation (test) data. Regularization solves this problem by adding a penalty term to the objective function and control the model complexity using that penalty term.
In L1 regularization we try to minimize the objective function by adding a penalty term to the sum of the absolute values of coefficients. This is also known as least absolute deviations method. Lasso Regression makes use of L1 regularization.
In L2 regularization we try to minimize the objective function by adding a penalty term to the sum of the squares of coefficients. Ridge Regression or shrinkage regression makes use of L2 regularization.
In general, L2 performs better than L1 regularization. L2 is efficient in terms of computation. There is one area where L1 is considered as a preferred option over L2. L1 has in-built feature selection for sparse feature spaces. For example, you are predicting whether a person is having a brain tumor using more than 20,000 genetic markers (features). It is known that the vast majority of genes have little or no effect on the presence or severity of most diseases.
Here λ is the regularization parameter which is a non negative number. Here we do not assume normality in the error terms.
We do not regularize the intercept term. The constraint is just on the sum of squares of regression coefficients of X's.
We can see that ridge regression makes use of L2 regularization.
How can we choose the regularization parameter λ?
If we choose lambda = 0 then we get back to the usual OLS estimates. If lambda is chosen to be very large then it will lead to underfitting. Thus it is highly important to determine a desirable value of lambda. To tackle this issue, we plot the parameter estimates against different values of lambda and select the minimum value of λ after which the parameters tend to stabilize.
Considering the swiss data set, we create two different datasets, one containing dependent variable and other containing independent variables.
We need to load glmnet library to carry out ridge regression.
Using cv.glmnet( ) function we can do cross validation. By default alpha = 0 which means we are carrying out ridge regression. lambda is a sequence of various values of lambda which will be used for cross validation.
set.seed(123) #Setting the seed to get similar results.
We take the best lambda by using lambda.min and hence get the regression coefficients using predict function.
6 x 1 sparse Matrix of class "dgCMatrix"
λ is the regularization parameter and the intercept term is not regularized.
We do not assume that the error terms are normally distributed.
For the estimates we don't have any specific mathematical formula but we can obtain the estimates using some statistical software.
Note that lasso regression also needs standardization.
Lasso regression can perform in-built variable selection as well as parameter shrinkage. While using ridge regression one may end up getting all the variables but with Shrinked Paramaters.
#Creating dependent and independent variables.
Using cv.glmnet in glmnet package we do cross validation. For lasso regression we set alpha = 1. By default standardize = TRUE hence we do not need to standardize the variables seperately.
We consider the best value of lambda by filtering out lamba.min from the model and hence get the coefficients using predict function.
Which one is better - Ridge regression or Lasso regression?
Both ridge regression and lasso regression are addressed to deal with multicollinearity.
Ridge regression is computationally more efficient over lasso regression. Any of them can perform better. So the best approach is to select that regression model which fits the test set data well.
Elastic Net regression is preferred over both ridge and lasso regression when one is dealing with highly correlated independent variables.
It is a combination of both L1 and L2 regularization.
Like ridge and lasso regression, it does not assume normality.
Setting some different value of alpha between 0 and 1 we can carry out elastic net regression.
Principal components analysis is a statistical method to extract new features when the original features are highly correlated. We create new features with the help of original features such that the new features are uncorrelated.
The first PC is having the maximum variance.
Similarly we can find the second PC U2 such that it is uncorrelated with U1 and has the second largest variance.
In a similar manner for 'p' features we can have a maximum of 'p' PCs such that all the PCs are uncorrelated with each other and the first PC has the maximum variance, then 2nd PC has the maximum variance and so on.
It is to be mentioned that PCR is not a feature selection technique instead it is a feature extraction technique. Each principle component we obtain is a function of all the features. Hence on using principal components one would be unable to explain which factor is affecting the dependent variable to what extent.
We use the longley data set available in R which is used for high multicollinearity. We excplude the Year column.
We use pls package in order to run PCR.
In PCR we are trying to estimate the number of Employed people; scale = T denotes that we are standardizing the variables; validation = "CV" denotes applicability of cross-validation.
Here in the RMSEP the root mean square errors are being denoted. While in 'Training: %variance explained' the cumulative % of variance explained by principle components is being depicted. We can see that with 3 PCs more than 99% of variation can be attributed.
We can also create a plot depicting the mean squares error for the number of various PCs.
By writing val.type = "R2" we can plot the R square for various no. of PCs.
It is an alternative technique of principal component regression when you have independent variables highly correlated. It is also useful when there are a large number of independent variables.
Both techniques create new independent variables called components which are linear combinations of the original predictor variables but PCR creates components to explain the observed variability in the predictor variables, without considering the response variable at all. While PLS takes the dependent variable into account, and therefore often leads to models that are able to fit the dependent variable with fewer components.
Support vector regression can solve both linear and non-linear models. SVM uses non-linear kernel functions (such as polynomial) to find the optimal solution for non-linear models.
The main idea of SVR is to minimize error, individualizing the hyperplane which maximizes the margin.
Ordinal Regression is used to predict ranked values. In simple words, this type of regression is suitable when dependent variable is ordinal in nature. Example of ordinal variables - Survey responses (1 to 6 scale), patient reaction to drug dose (none, mild, severe).
Why we can't use linear regression when dealing with ordinal target variable?
In linear regression, the dependent variable assumes that changes in the level of the dependent variable are equivalent throughout the range of the variable. For example, the difference in weight between a person who is 100 kg and a person who is 120 kg is 20kg, which has the same meaning as the difference in weight between a person who is 150 kg and a person who is 170 kg. These relationships do not necessarily hold for ordinal variables.
Poisson regression is used when dependent variable has count data.
The dependent variable has a Poisson distribution.
In the code below, we are using dataset named warpbreaks which shows the number of breaks in Yarn during weaving. In this case, the model includes terms for wool type, wool tension and the interaction between the two.
Like Poisson Regression, it also deals with count data. The question arises "how it is different from poisson regression". The answer is negative binomial regression does not assume distribution of count having variance equal to its mean. While poisson regression assumes the variance equal to its mean.
When the variance of count data is greater than the mean count, it is a case of overdispersion. The opposite of the previous statement is a case of under-dispersion.
It is an alternative to negative binomial regression. It can also be used for overdispersed count data. Both the algorithms give similar results, there are differences in estimating the effects of covariates. The variance of a quasi-Poisson model is a linear function of the mean while the variance of a negative binomial model is a quadratic function of the mean.
Quasi-Poisson regression can handle both over-dispersion and under-dispersion.
Time from customer opened the account until attrition.
Time after cancer treatment until death.
Time from first heart attack to the second.
Logistic regression uses a binary dependent variable but ignores the timing of events.
As well as estimating the time it takes to reach a certain event, survival analysis can also be used to compare time-to-event for multiple groups.
1. A continuous variable representing the time to event.
2. A binary variable representing the status whether event occurred or not.
If dependent variable is continuous and model is suffering from collinearity or there are a lot of independent variables, you can try PCR, PLS, ridge, lasso and elastic net regressions. You can select the final model based on Adjusted r-square, RMSE, AIC and BIC.
If you are working on count data, you should try poisson, quasi-poisson and negative binomial regression.
To avoid overfitting, we can use cross-validation method to evaluate models used for prediction. We can also use ridge, lasso and elastic net regressions techniques to correct overfitting issue.
Try support vector regression when you have non-linear model.
19 Responses to "15 Types of Regression you should know"
Should the part where you say "When you have more than 1 independent variable and 1 dependent variable, it is called simple linear regression" be multiple linear regression? It would be good to clarify because it comes right after "When you have only 1 independent variable and 1 dependent variable, it is called simple linear regression" and as a reader I would expect a contrast between the two blocks. Or if this is correct, a statement to validate that it is right after.
Typo. Corrected! Thanks for highlighting. Cheers!
Did you check the author name of Rblogger post?
If you are talking about this post --> https://www.r-bloggers.com/15-types-of-regression-you-should-know/ it's the same one :) RBloggers is a compilation of many (personal) blogs, this being one of them.
Reading "highly correlated independent variables" was initially confusing.
The piece is very good but some few regressions are left out. Beta regression, probit regression, tobit regression and probably a few others. For probit and tobit, it is just good to extend the treatise on logistic regression and try to explain their differences and when it might be preferable to use probit or tobit rather than logit. I have read a document where someone was trying to diffentiate between logistic regression and logit. I could not get the difference really, is there any at all? The comment by Vsoch is really important to correct.
What is the data set for Lung Cancer?
This is great! I appreciate you explaining only what's necessary to inform a choice, but not defining all technical terms. I can look those up if I think a model's worth considering.
excellent, very helpful, thank you.
Was there a reason that multinomial logistical regression was left out?
q\sum | \eps_i | + (1-q) \sum | \eps_i | = \sum | \eps_i |.
Hi, very good article yet there is a details you may correct if you want. The polynomial regression you are describing it is still a linear regression because the dependent variable, y, depend linearly on the regression coefficients. The fact the y is not linear versus x does not matter. From the practical point of view it means that with GNU R you can still use the "lm" function like in lm(y ~ x^2) and it will work as expected. The matrix computation of the linear regression and the matrix X is also still valid.
For what type of dependent data, support vector regression is applicable? Is it applicable for the case when dependent variable is discrete and bounded?
Dependent variable should be continuous in nature.
Can you please post some resources about how to deal with interactions in Regression using R? You have listed all kinds of regression models here. It would be great if you could cover Interactions and suggest how to interpret them. Maybe touching upon continuous, categorical, count and multilevel models. And giving some examples of real world data.
Hello, I used a Likert scale in a questionnaire and run a model where the dependent variable is the value of the answer. Using an ordinal regression model, 2 or 3 categories are "underranked". So my model results weak. Do you have any sugestion? Actually I could sum the value of the answers value for each interviewee obtaining a result from 3 to 15. What kind of model could I use in this case?


Follow ten adorable dogs as they learn to count from one to ten using the animals around their neighborhood. A simple counting story brilliantly packaged in a unique, hands-on StoryBox format with die-cut, tabbed board pages that will keep kids learning and having fun!
My kids always loved books like this. They are big enough for little hands. The pages are colorful with whimsical animals and just a few words.
Each page has a number tab that stands for the amount of animals on the page plus the one dog on the cover.
Guy Parker-Rees's beloved animals are back in this humorous look-and-find novelty book featuring all kinds of daddy animals and their little ones.
"Ready or not, here I come!" Walt the Walrus called to his daddy.
Walt looked to the left and he looked to the right.
Suddenly, he spotted something bushy that looked like his daddy's mustache.
"Are you my daddy?" he asked.
"No, I'm Daddy Penguin, and these are my bushy eyebrows."
This sweet, simple story with touch-and-feels, pull-tabs, and flaps is all about little Walt the Walrus's search for his mustachioed father in the zoo. As Walt searches, he comes across a hilarious array of bearded, bushy-eyebrowed, silly-haired, and yes-even bald!-dads. When he finally finds Daddy Walrus, he only has one question left to ask: "Can we play again?"
When Handsome and Godddess were small the Touch and Feel, Search and Find were their favorite. In this book we follow a baby Walrus as he searches for his father. Amazingly so many things look just like they could be dad.
Kids will love the little surprises like the lever for penguin, the fluffy, shiny, flap additions add to the fun of this sweet story. Plus there is the little yellow bird that shows up on each page, Goddess' favorite thing was to always point out something that could be found on each page.
A new line of novelty finger play & action rhyme stories!
This is such a cute book and so great to help toddlers build those important fine motor kills.
Each chunky page has a piggy tab to go along with a line from the nursery rhyme. Very cute. I like the way they change this little piggy had roast beef to apple pie. Not many are eating roast beef these days.
Adorable graphics to go with this classic nursery rhyme.
From this Caldecott Medal-winning team comes an unforgettable classic. The simple, rhythmic prose reinforces the notion of stopping and going at a crossroads in a busy town, and gives young readers a reassuring, cozy lesson in traffic safety.
These flap books are so much fun. I even remember loving them when I was a kid.
Learning about road signs and road rules can never come to early. This book is adorable. Kids love knowing what the signs they pass mean.


text:
\section{Introduction}

\subsection{Context and motivations}
The typical attacker model adopted in security protocol analysis is the
one of~\cite{MR712376}: the \emph{Dolev-Yao (DY) attacker} can compose,
send and intercept messages at will, but, following the perfect
cryptography assumption, he cannot break cryptography. The DY attacker
is thus in complete control of the network --- in fact, he is often
formalized as being the network itself --- and,
with respect to network abilities, he is actually stronger than
any attacker that can be implemented in real-life situations.
Hence, if a protocol is proved to be secure under the DY attacker, it
will also withstand attacks carried out by less powerful attackers;
aside from deviations from the specification introduced in the implementation phase, the protocol can thus be safely employed in real-life networks, at least in principle.

Alternative attacker models have also been considered. On the one hand,
\emph{computational models} for protocol analysis consider attackers who
can indeed break cryptography, as opposed to the \emph{symbolic models}
where cryptography is perfect (as we will assume in this paper). See,
for instance, \cite{AbadiBlanchetComonCAV09} for a survey of models and
proofs of protocol security, and~\cite{basincremers_models} for a
protocol-security hierarchy in which protocols are classified by their
relative strength against different forms of attacker compromise.

On the other hand, different symbolic models have been recently proposed
that consider \emph{multiple attackers} instead of following the usual
practice to consider a single DY attacker
  ~a choice that is supported by the fact that models with multiple collaborating DY
attackers have been shown to be reducible to models with one DY attacker
(see, e.g., \cite{Caleiro200567} for a detailed proof, as well
as~\cite{DTL,comon03twoAgentsEnough,Syverson00dolev-yaois} for general
results on the reduction of the number of agents to be considered). For
instance, \cite{basin_physical,schaller_physical} extend the DY model to
account for network topology, transmission delays, and node positions in
the analysis of real-world security protocols, in particular for
wireless networks. This results in a distributed attacker, or actually
multiple distributed attackers, with restricted, but more realistic,
communication capabilities than those of the standard DY attacker.

Multiple attackers are also considered in the models
of~\cite{arspawits2009GA,ArsacBellaChantryCompagna,Bella03,retaliation},
where each protocol participant is allowed to behave maliciously and
intercept and forge messages. In fact, each agent may behave as a DY
attacker, without colluding nor sharing knowledge with anyone else. The
analysis of security protocols under this multi-attacker model allows
one to consider scenarios of agents competing with each other for
personal profit. Agents in this model may also carry out
\emph{retaliation attacks}, where an attack is followed by a
counterattack, and \emph{anticipation attacks}, where an agent's attack
is anticipated, before its termination, by another attack by some other
agent.

The features of the models of~\cite{basin_physical,schaller_physical}
and
of~\cite{arspawits2009GA,ArsacBellaChantryCompagna,Bella03,retaliation}
rule out the applicability of the $n$-to-1 reducibility result for the
DY attacker, as the attackers do not necessarily collaborate, and might
actually possess different knowledge to launch their attacks. They might
even attack each other. In fact, retaliation and anticipation allow
protocols to cope with their own vulnerabilities, rather than
eradicating them. This is possible because agents are capable of doing
more than just executing the steps prescribed by a protocol: they can
decide to anticipate an attack, or to counter-attack by acting even
after the end of a protocol run (in which they have been attacked).
Still, retaliation may nevertheless be too weak as honest agents can
retaliate only \emph{after} an attack has succeeded, and cannot defend
the protocol during the attack itself.

\subsection{Contributions}

In this paper, we take a fundamentally different approach: we show that
multiple non-collaborating DY attackers may interfere with each other in
such a manner that it is possible to exploit interference to mitigate
protocol vulnerabilities, thus providing a form of protection to
flawed protocols.

To investigate the non-cooperation between attackers, we propose a
(protocol-inde\-pendent) model in which: (i) a protocol is run in the
presence of multiple attackers, and (ii) attackers potentially have
different capabilities, different knowledge and can interfere with each
other. This, ultimately, allows us to create a
benign attacker for the
system defense: agents can rely on a \emph{network guardian}, an ad-hoc
agent whose task is diminishing the frequency with which dishonest
agents can succeed in attacking vulnerable protocols. This methodology
moves the focus from an attack-based view of security to a defense-based
view.

In other words, in the approach we propose, instead of looking for
attacks and reacting to the existence of one by redesigning the
vulnerable protocol, we look for strategies for defending against
existing known attacks. We would be performing protocol analysis to identify
possible \emph{defenses}, rather than attacks.

We proceed as follows. In Section~\ref{sec:model}, we formalize models
for the network and the agents, including, in particular, agent
attitude, goals, and disposition. We then consider in
Section~\ref{sec:case-study} a vulnerable
protocol from~\cite{boydMathuria} as
a case study and focus on the interactions between attack procedures
that cannot be observed in classical settings. In
Section~\ref{sec:defense}, we explain how interference between attacks
leads to a methodology that can be used for defending weak
(vulnerable) protocols
against attacks. In Section~\ref{sec:conclusions}, we conclude by
discussing our approach and current and future work.
Appendix A provides additional details about the case study; a second case study is explored in appendix B.

\section{System models: network, agents, attitude}
\label{sec:model}

\subsection{Goals of modeling and approach}

Network models for security protocol analysis typically either replace
the communication channel with a single attacker or build dedicated
channels for each attacker
(e.g.~\cite{DTL,Caleiro200567,DillowayLoweWITS07,KamilLowe10,Syverson00dolev-yaois}).
Traditional modeling strategies are not adequate to describe the
non-collaborative scenario under consideration. The main shortcoming is
the fact that the ability to spy the communication on a particular
channel is hard-wired in the network model and may depend critically on
network topology or attacker identity; the result is that an
information-sharing mechanism (or a partial prohibition for it) is
structurally encoded in the network. We would like, instead, to (i)
abstract from positional advantages and focus solely on how attackers
interfere \emph{by attacking}; (ii) treat information-sharing (also as a
result of spying) as a strategic choice of the agents.

For simplicity, in this paper we restrict our attention to \emph{two}
non-collaborative attackers ($E_{1}$ and $E_{2}$), in addition to the
two honest agents $A$ and $B$ and a trusted third-party server $S$,
whose presence is required by the protocol under consideration.
In the following, let \mathii{Eves}$=\{E_1, E_2\}$ be the \emph{set of attackers} and
\mathii{Agents}$=\{A, B, E_1, E_2\}$ the \emph{set of all network agents} (honest and
dishonest, server excluded). Let $X$, $Y$, $Z$ and $W$ be variables varying in \mathii{Agents} and $E$ a variable in \mathii{Eves}; $j$ takes value in $\{1,2\}$, whereas $i \in \mathbb{N}$ is reserved for indexing states.

We are aware that, in situations with more than two (dis)honest agents,
further types of interactions can arise; however, a full comprehension
of the interactions depends on building a clear picture of interference.
Such a picture necessarily starts with the elementary interaction
between two attackers.

In order to focus on the raw interference between two attackers, both
directing their attack towards the same target, it is important for all
attackers to have access to the same view of what is taking place with
honest agents and possibly different views of what is taking place with
the other attacker(s). If attackers do not all have the same
information, it is possible to conceive of strategies in which some
attackers can be mislead by others on purpose.

If the knowledge\footnote{Note that we do not attach any epistemic
interpretation to the knowledge we consider in this paper
we simply consider the information initially available to the agents, together with
the information they acquire during protocol executions.}
available to an
attacker affects his view of the system, attacker capabilities and
effectiveness can be diversified, without needing to construct
asymmetric attackers or hardwire constraints that may hold for some
attackers and not for others. We find it relevant that a network model
for non-collaborative scenarios --- besides reflecting this stance ---
also support a form of competition for access to messages, especially if
attacks rely on erasing messages.

If it is possible in principle to actively interfere with an attack, it
should be possible to do so even if all attackers have the same
knowledge. However, differentiating attackers with respect to their
understanding of the situation --- in particular with respect to
awareness of other attackers --- may bring into focus the conditions, if
any, that allow an attacker to interfere with another without being
interfered with.

We diversify the activity of our attackers by admitting that attackers
may choose to selectively ignore some messages, on the basis of the
sender's and receiver's identifiers. This choice reflects actual situations
in which attackers pay attention to only a subset of the traffic through
a network, focusing on the activity of some agents of interest.
Regardless of whether this selection is caused by computational
constraints or by actual interest, real attackers filter messages on the
basis of the sender's or receiver's identity. In the following, we will
use the set \attentive{E} to model the agents to which attacker $E$ is
attentive; the predicate \ofinterest{X} (see Table~\ref{OurDYmodel})
models the decisional process of
attacker $E$ as he considers whether he wishes to augment \attentive{E}
with $X$, i.e. \ofinterest{X} implies that $X$ is added into
\attentive{E}.

Honest agents are interested in \emph{security properties} (such as
authentication or secrecy) being upheld through the use of protocols.
Dishonest agents, on the other hand, are interested in changing or
negating such properties.

The characteristic feature of the attackers we consider is their
attitude. In particular, in the case study that we consider in the next
section, dishonest agents wish to attack the security protocol and are
ready, should they encounter unforeseen interference, to take
countermeasures with respect to the interference as well. In a sense,
each attacker is exclusively focused on attacking the protocol and
becomes aware of other attackers through their effect on his success.

Our target is capturing the behavior of \emph{equal-opportunity}
dishonest agents that do not cooperate in the classical sense. By
equal-opportunity attackers we mean agents that have the same attack
power and that differ with respect to the information content of their
knowledge bases. Such differentiation arises out of attentional choices
and not out of intrinsic constraints. Strategic and attitude
considerations should not be derivable explicitly from the attacker
model --- rather, they should configure it.

The driving hypothesis of our work is that studying non-collaboration
requires a complex notion of attacker, whose full specification involves
attentional choices, decisional processes pertaining to the network
environment and to other agents, cooperation-related choices and
decisional processes pertaining to the attack strategy. To support this
type of attacker, we extend the usual notions of protocol and role by
introducing a control --- a mechanism to regulate the execution of the
steps prescribed by the attack trace in accordance with the attacker's
strategy.
In our model, honest agents perform a controlled execution of the
protocol as well, so as to support in-protocol detection of attacks.
Honest agents behave according to the protocol's prescription, expect
things to go exactly in accordance with the protocol and interpret
deviations in terms of the activity of dishonest agents.

\begin{table}[!t]
\begin{center}
\scalebox{0.84}{
\begin{scriptsize}
\begin{tabular*}{0.555\textwidth}{c}
\hline
\hline \\
$\infer[\mathbi{(Comp)}]{(m_{1}, m_{2})\in D^{i}_{E}}{m_{1}\in D^{i}_{E} \quad m_{2}\in D^{i}_{E}}$
\qquad
$\infer[\mathbi{(Encr)}]{\{m\}_{k}\in D^{i}_{E}}{m\in D^{i}_{E} \quad k\in D^{i}_{E}}$
\\\\
$\infer[\mathbi{(Proj)} \quad]{m_{j}\in D^{i}_{E}  \:\: \text{for~} j \in \{1,2\}}{(m_{1}, m_{2})\in D^{i}_{E}}$

$\infer[\mathbi{(Decr)} \quad]{m \in D^{i}_{E}}{\{m\}_{k}\in D^{i}_{E} \quad k^{-1} \in D^{i}_{E}}$
\\\\
\hline
\hline \\
$\infer[\mathbi{(Restricted-Spy)}]{m \in D^{i+1}_{E}}{<X, m, Y> \in D_{net}^{i} \quad \text{sender}(<X,m,Y>) \in D^{i}_{E} \quad Y \in D^{i}_{E}\quad \psi}$
\\\\
$\infer[(\text{$\mathit{Inflow\text{-}Spy}$})]{m \in D^{i+1}_{E} \land sender(<X,m,Y>) \in D^{i+1}_{E} }{<X, m, Y> \in D_{net}^{i} \quad $ \ofinterest{X}$ \quad Y \in D^{i}_{E} \quad \psi} $
\\\\
$\infer[(\text{$\mathit{Outflow\text{-}Spy}$})]{m \in D^{i+1}_{E} \land Y \in D^{i+1}_{E}}{<X, m, Y> \in D_{net}^{i} \quad {sender}(<X,m,Y>) \in D^{i}_{E} \quad $\ofinterest{Y}$ \quad \psi }$
\\\\
{where  $\psi = E \in $\cansee{<X,m,Y>, i}  }\\\\
\hline
\\
$\infer[\mathbi{(Injection)}]{<E(X), m, Y>  \in D_{net}^{i+1}}{m \in D^{i}_{E} \quad X \in D^{i}_{E} \quad Y \in D^{i}_{E}}$
 \\\\
$\infer[\mathbi{(Erase)}]{<X, m, Y> \notin D_{net}^{i+1}}{<X,m,Y> \in D_{net}^{i} \quad {sender}(<X,m,Y>) \in D^{i}_{E}}$
\\\\
\hline \hline
\\
$
{sender}(<X, m, Y>)= \begin{cases}
 E & \text{~if~ there exists $Z$ such that~} X = E(Z) \\
 X & \text{~otherwise}
\end{cases}
$
{\scriptsize \mathbi{(True-sender-ID)}} \\\\
\ofinterest{X}
$
=
\begin{cases}
 true & \text{if $E$ decides to pay attention to $X$} \\
 false & \text{~otherwise}
\end{cases}
$
{\scriptsize $(DecisionalProcess)$} \\\\
\hline\\
$
\text{\cansee{<X,m,Y>,i}} \: = \
 \{Z \in Eves \:|\:   \text{ $Z$ can spy
 <X,m,Y> \text{~on $D_{net}^{i}$} \}
$ {\scriptsize \mathbi{(NetHandler)}}
\\\\
\hline
\hline
\end{tabular*}
\end{scriptsize}
}
\caption[Attacker model for non-collaboration]{Dolev-Yao attacker model for non-collaborative scenarios: internal operations (synthesis and analysis of messages), network operations (\mathii{spy}, \mathii{inject}, \mathii{erase}) and system configuration ($\mathit{True\text{-}Sender \text{-}ID}${}, \mathii{DecisionalProcess}, $\mathit{NetHandler}${}). $\mathit{NetHandler}${} describes the set of attackers who are allowed to spy by applying one of the \mathii{spy} rules. We omit the usual rules for conjunction.
The rules employed in the case study are marked in boldface.
}
\label{OurDYmodel}
\end{center}
\end{table}

\subsection{Agent model} \label{attacker}

Agent knowledge is characterized in terms of a proprietary dataset.
To each $X$ in \mathii{Agents}, we associate the dataset $D_X$, which we assume to be monotonically non-decreasing. Our agents, in particular dishonest agents, collect information but do not forget it. When it is important to highlight that the dataset is to be considered at a particular moment, we will use $D_X^i$ instead.

The network \mathii{net} is also formalized through a dataset, which is named $D_{net}$ and indexed in the same manner as $D_X^i$. A dataset is a simple network model that can be configured to support complex attackers; we believe it can successfully meet all of our modeling requirements for non-collaboration. We postpone to Section \ref{sec:evolution} the discussion of how datasets evolve and how indexing and evolution are related to actions and message transmission.

We adapt the notion of DY attacker ~\cite{MR712376} to capture a
non-collaborative scenario. We show in Table~\ref{OurDYmodel} how one
such attacker is formalized within our model, writing rules
for attacker $E$ with respect to the knowledge base $D_{E}$ and the network model
$D_{net}$.
Let us specify that the rules in Table~\ref{OurDYmodel} are transition rules, rather than deduction rules. Taken altogether, they construct a \emph{transition system} -- which describes a computation by describing the states that are upheld as a result of the transition. We do not intend to carry out in this paper logical inference to identify defenses against attacks; rather, we recognize in the system's evolution what in our eyes corresponds to a defense.

Attackers are legitimate network agents that can \mathii{send} and \mathii{receive} messages, derive new messages by analyzing (e.g.\ decomposing)  known messages, obtain messages transiting
on the network (\mathii{spy}) and remove them so that they do not reach
their intended receiver (\mathii{erase}). Attackers can also partially
impersonate other agents, by \mathii{inject}ing messages under a false
identity; we represent impersonification with the notation $E(X)$, where $E$ is the impersonator and $X$ is the identifier of the impersonated agent.
This set of abilities
describes agents who have control over almost all facets of a
communication; their characteristic limitation is that they cannot
violate cryptography (we assume perfect cryptography). Note that further
rules could be added in Table~\ref{OurDYmodel} for other forms of encryption, digital signatures, hashing, creation of nonces and other fresh data, and so on.

The most significant feature concerns spying, represented through three
rules. For conceptual clarity, we explicitly pair an \mathii{erase}-rule
with the \mathii{injection}-rule, to emphasize that an attacker can
modify messages (by erasing them and injecting a substitute) or send
messages under a false identity (partial impersonification). Our
attackers can employ three different \mathii{spy} rules, adapted to formalize the
fact that attackers do not pay attention to all of the traffic on the
network. The \mathii{spy} rules rely on an interpretation for ``send''
that is modified with respect to the denotational semantics
in~\cite{Caleiro200688}, to reflect the attentional focus of attackers.
The default \mathii{spy} is the $\mathit{Restricted \text{-}Spy}${}: only the messages involving
known agents in both sender and receiver roles, regardless of hypotheses
on their honesty, become part of the attacker's dataset. Note that in
our model what matters is the actual sender and not the declared sender
($\mathit{True\text{-}Sender \text{-}ID}$). This mechanism prevents total impersonification and allows
filtering messages on the basis of the agent's attentional choices.

The attentional filter we use is meant as a choice of the agents and not
as a constraint to which they are subject; therefore, it must be
possible to expand the set of agents of interest. This role is fulfilled
by the two exploratory \mathii{spy}
rules in Table~\ref{OurDYmodel},
\text{$\mathit{Inflow\text{-}Spy}$} and \text{$\mathit{Outflow\text{-}Spy}$}. Attackers have the option of accepting or
rejecting the newly discovered identifier $X$, on the basis of the
predicate \ofinterest{X}, which models the decisional process for
attention.

Note that an attacker cannot apply any of the \mathii{spy} rules to
obtain the message $m$ without knowing the identifier of at least one
between $m$'s sender and $m$'s intended receiver. By not providing a
``generalized spy'' rule to waive this requirement, we ensure that
$(D_{E}^{0} \: \cap$ \mathii{Agents} $= \emptyset)$ implies that for all
$i$, $(D_{E}^{i} \: \cap$ \mathii{Agents} $= \emptyset )$. Although $E$
can augment its knowledge base $D_E$ indefinitely --- through internal
message generation and the synthesis rules
\mathii{Comp} and \mathii{Encr} ---,
$E$'s network activity is in fact null. One such $E$ is a \emph{dummy
attacker}, whose usefulness becomes apparent when considering that proof
of reductions for non-collaboration can involve progressively migrating
identifiers from an attacker's dataset, until the attacker himself
reduces to the dummy attacker.

An attacker's dataset $D_E$ consists of (i) messages that have transited
through the network and that have been successfully received, analyzed
or spied and (ii) identifiers of the agents to whom the attacker is
attentive. The set \attentive{E} of identifiers of interest to $E$ is
further partitioned into three sets: the set \honest{E} of agents
believed\footnote{We do not attach any doxastic interpretation
to the beliefs we consider in this paper.} to be honest, the set
\dishonest{E} of agents believed to be attackers, and the set
\notknow{E} of agents whose attitude is unknown in $E$'s eyes. Note that
differently from $D_{net}$,
agent datasets do not contain triplets ($\langle \mathit{sender\textrm{-}ID, message, receiver\textrm{-}ID}\rangle$), but only
messages or identifiers.

Once a new identifier $X$ enters the knowledge base of attacker $E$, $E$
establishes a belief about the honesty of $X$ and places the identifier
in one of the sets \honest{E}, \dishonest{E} or \notknow{E}.
We do not enter details on how the agents initially build their knowledge base and
establish their belief about the attitude of other known agents. In
fact, this classification is meant to be dynamic. Agents are on the
watch for suspicious messages, which may indicate that an attack is
ongoing or may reveal that a certain agent is dishonest. Dynamically
adapting their beliefs about the honesty of other agents allows the
agents to gather important information during single protocol runs. The
agents we wish to consider are \emph{smart}: they always employ the
available strategic information.

Attackers do not have automatic access to triplets that relate sender,
message and receiver. They must infer key pieces of information on the
basis of the identifiers of the agents to which they are attentive, and
attempt to relate the identifiers to the messages they spy. Inference is
easier if attackers use only the $\mathit{Restricted \text{-}Spy}${} rule and keep the set of known
agents small. The difficulty of inference rises with the number of
attackers in the set \attentive{E}.

\subsection{Network model} \label{sec:evolution}

All the operations that can change the state of the network dataset $D_{net}$
(\mathii{send}, \mathii{receive}, \mathii{inject} and \mathii{erase})
are termed \emph{actions}, whereas we consider \mathii{spy} simply as an operation: although it requires interacting with the network, it does not change its state.
Messages in transit are inserted in the network dataset $D_{net}$, where
attackers can spy them before they are delivered to their intended
receivers. Contextually to delivery, the message is removed from the
dataset. Messages transit on the network dataset in the form of triplets
of the type $\langle \mathit{sender\textrm{-}ID, message, receiver\textrm{-}ID}\rangle$. As a consequence of message delivery or deletion, $D_{net}$ is non-monotonic by construction.

The sequence of actions that takes place during a protocol run is
enumerated and used to index the evolution of the network dataset
$D_{net}$; the index of $D_{net}^i$ is shared with all the proprietary datasets $D_{X}^{i}$, whose states are synchronized accordingly.
$D^i_{net}$ is the state of the network dataset \emph{after the i-th action}.

Customarily, evolutions are indexed per transition (per rule application), rather than per action. Our chosen indexing strategy reflects three needs: (1) allowing agents to fully analyze newly acquired messages without having to keep track of the number of internal operations performed; (2) supporting a form of competition between attackers for access to the network; (3) supporting a form of concurrence.

Ideally, all attackers act concurrently. However, the state transitions for the network must be well-defined at all times, even if attackers try to perform conflicting actions, such as spying and deleting the same message in transit. To impose a measure of order, we introduce a \emph{network handler}, whose task is to regulate the selection of the next action and implement the dependencies between selected action and knowledge available to each attacker; through the network handler, it is also possible to keep the system evolution in accordance with additional constraints, modeling for example information sharing within specific subsets of agents and network topology.

As soon as the state of the network changes (e.g.\ as a result of \mathii{inject} or \mathii{send}), the network handler passes the new triplet to each attacker, who then \emph{simulates} spying and decides on whether to request erasing the message or injecting a new one as a consequence, in accordance with his strategy. The network handler interprets the application of the spy-rules, the inject-rule and the erase-rule as requests and selects the next action from the set of requests. Message deletion, when requested by any attacker, is always successful.

The outcome of the process governed by the network handler is described through the function \cansee{}, which returns a subset of \mathii{Eves}, highlighting the identifiers of the attackers who can spy ``before'' the message is erased from $D_{net}$. The set of agents
described by \cansee{} contains at least the identifier of the
attacker whose erase request was served.

If the network handler does not receive any erase-requests, all attentive attackers can acquire the message. If one or more erase-requests are present, the network handler erases the message and confirms success in spying only for a subset of attentive attackers.
If an attacker is not in \cansee{}, the prior (simulated) spy is subject to rollback, along with all internal operations that have occurred since the last confirmed action.
If no requests are received from attackers, the network handler oversees message delivery or selects actions requested by honest agents.

Although the formulation of \cansee{} in terms of access time is intuitive, the reason why we favor this mechanism is that time-dependent accessibility is not the only situation it can model. The function can be instantiated to model strategic decision-making and information-sharing, or to capture a particular network topology. In realistic attack scenarios, knowledge of a message that has been erased may depend more on cooperation and information-sharing than on timing.
For example, if $E_j$ is sharing information with $E_k$ (but not viceversa), whenever $E_j$'s erase requests are served $E_k$ is automatically in \cansee{}.

The network handler is not an intelligent agent. Specifying its behavior and instantiating
the function \cansee{} corresponds to configuring the particular
network environment in which the agents are immersed
(i.e.~\cansee{} is a configurable parameter of our model).

As a result on the network handler and of our chosen indexing strategy, several internal operations can occur in a proprietary dataset between consecutive states, whereas only a single action separates consecutive states of the network dataset. Attackers determine the next
state of the network dataset with priority with respect to the actions of honest agents.

In Table~\ref{AliceAndBob}, we formalize within our model operations in the Alice\&Bob notation used in Section~\ref{sec:case-study}; we write $E_{I}(Y)$ to denote the subset
of \mathii{Eves} who spy message $m$ addressed to $Y$, at least one of which has requested $m$
to be erased.

With reference to Table~\ref{AliceAndBob}, note that the $(i+1)^{\text{th}}$ action is requested when the state of the network is $D^i_{net}$ and agent datasets are $D_X^i$; thus, the sender $X$ must already know in $D_X^i$ both the message $m$ and the identifier of the intended recipient $Y$. The message correctly transits on $D_{net}^{i+1}$, immediately after being sent. The (i+2)th action is either \mathii{receive} (first two cases) or \mathii{erase} (last case). the availability of $m$ to attackers is conclusively decided after the network handler selects the (i+2)th action, and thus pertains to $D_{W}^{i+2}$.

\begin{table}[t!]
\begin{center}
\scalebox{0.65}{
\begin{tabular}{cl}
\hline
\rule[-2.5 mm]{0mm}{0.65 cm}
$\quad (i+1)^{\text{th}}$ action $\quad$ & Formalization\\
\hline
\rule[-2.5 mm]{0mm}{0.58 cm}
{\footnotesize $X \to Y \: : \: m$}
& {\footnotesize $m \in D_{X}^{i} \quad \text{and} \quad Y \in D_{X}^{i}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $<X,m,Y> \in D_{net}^{i+1} \quad \text{and} \quad <X,m,Y> \not\in D_{net}^{i+2}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $m \not\in D_W^{i+2},$ where $ W\not\in$~\cansee{<X,m,Y>, i+1} } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $m \in D_{Y}^{i+2}$ } \\
\hline
\rule[-2.5 mm]{0mm}{0.58 cm}
{\footnotesize $E(X) \to Y \: : \: m$}
& {\footnotesize $m \in D_{E}^{i} \quad \text{and} \quad X \in D_{E}^{i} \quad \text{and} \quad Y \in D_{E}^{i}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $<E(X),m,Y> \in D_{net}^{i+1} \quad \text{and} \quad <E(X),m,Y> \not\in D_{net}^{i+2}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $m \not\in D_W^{i+2},$ where $ W \not\in$ \cansee{<X,m,Y>, i+1} } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $m \in D_{Y}^{i+2}$ } \\
\hline
\rule[-2.5 mm]{0mm}{0.58 cm}
{\footnotesize $X \to E_{I}(Y) \: : \: m$}
& {\footnotesize $m \in D_{X}^{i} \quad \text{and} \quad Y \in D_{X}^{i}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $<X,m,Y> \in D_{net}^{i+1} \quad \text{and} \quad <X,m,Y> \not\in D_{net}^{i+2}$ } \\
\rule[-2.5 mm]{0mm}{0.58 cm}
& {\footnotesize $m \in D_W^{i+2},$ where $ W \in I \: \text{and} \: I \subseteq$  \cansee{<X,m,Y>, i+1} } \\
 \hline \\
\end{tabular}
}
\caption{Representation of operations in Alice\&Bob notation.}
\label{AliceAndBob}
\end{center}
\end{table}

\subsection{Attacker goals and agent disposition}

The notion of cooperation between agents can be viewed from at least two
perspectives of interest: sharing of information and sharing of success.
The notion of attacker cooperation classically employed in protocol
analysis encompasses both aspects, as it states the first while assuming
that the second holds.

In this paper, we examine attackers that exhibit, with respect to
cooperation, the behavior we call \emph{complete non-collaboration}:
agents voluntarily abstain from sharing information and do not consider
their goals as met if they do not succeed in attacking.
The \emph{disposition} of attacker $E_1$ towards $E_2$ belongs to one of
the following basic classes: active collaboration, passive
collaboration, competition and conflict\footnote{In active and passive
collaboration there is a common goal to be pursued; the difference lies
in choosing a strategy that helps another vs.\ choosing a strategy that
does not hinder another. In conflict scenarios, the primary focus of
interest is the attackers, rather than the protocol.}. The focus of this
paper is on competition -- a situation in which the goal is successfully
attacking the protocol, regardless of the disposition of other agents.
From the perspective of a competitive attacker, other attackers are not
of interest per se: they are relevant factors because they are sources
of interference. If some interference is detected while carrying out an
attack, a competitive attacker will take countermeasures, attempting to
negate potentially adverse effects.

Sets of agents that are homogeneous with respect to disposition can be
used to define scenarios of interest. In the case study below, we explore a simple characteristic scenario composed of two
competitive attackers; we aim to bring into focus the mechanisms by
which two attackers can affect each other's success.

\section{A case study: the Boyd-Mathuria Example}
\label{sec:case-study}

A dishonest agent, aware that other independent attackers may be active
on the network, will seek to devise suitable novel attacks, so as to
grant himself an edge on unsuspecting competitors. As the mechanics of
interaction and interference between attackers have not been
exhaustively studied in literature yet, it is not known a priori
how to systematically derive an attack behavior of this type.

In the following case study, we start from a simple protocol for which a
vulnerability is known; we devise for the known (``classical'') attack a
variant that explicitly considers the possibility of ongoing independent
attacks. We describe a possible reasoning for a competitive attacker in
the context of the protocol's main features. Due to space limitations,
we give additional details about the case study in the appendix.

\begin{table}[t!]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{cc}
\hline
{\bf BME} & {\bf Classical Attack}\\
\hline \\
\scriptsize
\!\!\!\!\!\!
$
\begin{array}{rll}
(1) & A \to S  & : A, B \\
(2) & S \to A  & :  \{\!| k_{AB} |\!\}_{k_{AS}}, \{\!| k_{AB} |\!\}_{k_{BS}} \!\!\!\!\!\! \\
(3) & A \to B  & : \{\!| k_{AB} |\!\}_{k_{BS}} \\
\end{array}
$
&
\scriptsize
$
\begin{array}{rll}
(1\phantom{'}) & A \to E(S)  & : A, B \\
(1') & E(A) \to S  & : A, E \\
(2\phantom{'}) & S \to A  & :  \{\!| k_{AE} |\!\}_{k_{AS}}, \{\!| k_{AE} |\!\}_{k_{ES}} \!\!\!\!\!\! \\
(3\phantom{'}) & A \to E(B)  & : \{\!| k_{AE} |\!\}_{k_{ES}} \\
\end{array}
$
\\\\
\hline
\end{tabular}

\end{center}
\caption{The Boyd-Mathuria Example protocol and a masquerading attack against it.}
\label{BME}
\end{table}

The protocol we consider as a case study is a key transport protocol
described as an example in~\cite{boydMathuria}; we name it as the
Boyd-Mathuria Example (BME), and present it in Table~\ref{BME} together
with a classical attack against it. BME relies on the existence of a
trusted third-party server $S$ to generate a session key $k_{AB}$ for
agents $A$ and $B$, where each agent $X$ is assumed to share a symmetric
secret key $k_{XS}$ with $S$.

$A$ is subject to a masquerading attack in which, at the end of a run of
BME, $A$ thinks that he shares a session key with the honest agent $B$,
while in fact he shares it with the attacker $E$. Subsequent
communication from $A$ addressed to $B$ is seen by $E$ through the
spy-rule and removed with an erase request: $E$ has successfully taken
$B$'s place.
This attack prevents $B$ from receiving \emph{any} communication from
$A$. Should the two agents have prior agreement that such a
communication was to take place, $B$ is in the position of detecting
that something has gone wrong. $E$ can prevent detection by staging a
dual man-in-the-middle attack.

If more than one attacker is active during a given protocol run,
simultaneous execution of the classical attack could lead to $A$
receiving multiple session keys as a response to his (single) request to
the server. This situation clearly indicates to $A$ that an attack is
ongoing. A competitive attacker $E_1$, wishing to prevent this situation
from occurring, could try removing from the network all the responses
from $S$ to $A$ that do not pertain to his own request. However, the
characteristics of the
(non-redundant) cryptographic methods employed here do not allow
distinguishing $M_1 = \left(\{\!| k_{AE_1} |\!\}_{k_{AS}}, \{\!|
k_{AE_1} |\!\}_{k_{E_1S}}\right)$ (to let through) from $M_2 = \left(
\{\!| k_{AE_2} |\!\}_{k_{AS}}, \{\!| k_{AE_2} |\!\}_{k_{E_2S}}\right)$
(to block). $E_1$ can recognize the format of $M_1$ and $M_2$ and can
successfully decrypt $M_1$ to recover $k_{AE_1}$; by decrypting $M_2$
with the key $k_{E_1S}$, $E_1$ can still recover a value, but different
from the previous one. Not knowing $k_{AE_1}$ a priori, the attacker is
not able to distinguish which of $M_1$ and $M_2$ contains the answer to
his request for a key with $A$.

As a consequence, the attacker $E_1$ is not able to know which messages
to remove in order to ensure that $A$ accepts $k_{AE_1}$ as a session
key to communicate with $B$. Competitive attackers cannot rely on step
(2) to enforce their attacks at the expense of their competitors;
furthermore, the probability of erasing all competing messages (while
letting one's own pass) decreases with the number of active attackers.
In this situation, it becomes fundamental for a competitive attacker to
gain exclusive access to the first message and gain control over the
messages that reach $S$, as opposed to the messages coming from $S$
\footnote{
Of course, $E_1$ could guess which message(s) to erase, but
he would have the added difficulty of having to decide whether to let
the first message pass without knowing how many other messages will transit,
if any at all, and how many session keys were requested by $A$ (as opposed to by his competitor(s)).
}.

After spying the initiator's opening message, a competitive attacker
$E_1$ will therefore attempt to mount the classical attack, while
keeping watch for other messages that may be interpreted as attack
traces. Any transiting message of the type $(A, E_m)$ for which $E_m
\in$ \dishonest{E_1} is interpreted as another active attack; $E_1$
counters by requesting that the message be erased. If $E_m$ is in
\honest{E_1}, the message may be understood either as a message from $A$
--- who would be initiating a parallel session of the protocol to obtain
a second session key --- or as an indication that $E_m$ has been
incorrectly labeled as honest. In the first case, $E_1$ will let the
message through, as he has chosen to target specifically the session key
for the communication between $A$ and $B$; in the second case, he will
protect his attack by erasing the message. If $E_m$ is in \notknow{E_1},
$E_1$ can choose to either play conservatively and hypothesize the
dishonesty of $E_m$ or let the message through and interpret $E_m$ as
the culprit in case the current attack fails.

BME is such that at most one attacker $E_d$ can successfully mislead $A$
into accepting the key $k_{AE_d}$ as a session key to communicate with
$B$. Therefore, a successful attack automatically entails exclusivity of
success. An attack is successful if it goes undetected by the initiator
$A$. Our honest agents are intelligent and they make use of all
information available to perform in-protocol detection of attacks. With
respect to BME, a clear indication for $A$ consists in receiving
multiple responses from $S$ after a single session key request; if $A$
receives multiple responses, he concludes that there has been a security
violation and thus does not employ
any of the keys so received
in his later communications with $B$
-- choosing to try a fresh run of the protocol instead.
From the attackers' perspective, an ongoing
attack can be detected by observing a message of the type $(A, X)$
transiting on the network; however, the attack trace is ambiguous to
spying attackers and has to be interpreted on the basis of current
beliefs concerning the honesty of $X$. A last feature of interest is
that BME is rather friendly for attacker labeling. Decisional processes
can rely on at least some conclusive information on the identity of the
agents involved, because identifiers transit in the clear; attackers
would have to infer them otherwise.

We examine the outcome of attacks carried out in a non-collaborative
environment in six cases, corresponding to different conditions of
knowledge and belief for $E_1$ and $E_2$. Cases and attack traces are
summarized in Table~\ref{tracesBME}. In order to completely specify
agent behavior,
we posit the following:
\begin{enumerate}
\item If an attacker $E$ spies $(A, E_m)$ with $E_m \in $ \honest{E} or $E_m \in $ \notknow{E}, he will not request that the message be erased. In the latter case, if $E$'s attack fails, $E_m$ is immediately placed in \dishonest{E}.
\item Both $E_1$ and $E_2$ spy the opening message

 and are interested in attacking the current protocol run; this allows us to leave aside the trivial cases in which only one attacker is active for a given protocol run.
\item Due to space constraints, we detail only the cases in which $\mathit{canSee}$ for step (3) yields $\{E_1,E_2\}$. Cases in which only one of the attackers can access $A$'s response can be found in  appendix \ref{extendedBME}.
\end{enumerate}

\noindent \textbf{Case 1: $E_{1}$ and $E_{2}$ know each other as honest.}\\
$E_{1}$ and $E_{2}$ know each other's identifiers (i.e.\ they are paying attention to each other: $E_{1} \in D_{E_{2}} \text{ and } E_{2} \in D_{E_{1}}$), but they are both mistaken in that they have labeled the other as honest ($E_{1} \in $ \honest{E_2} and $E_{2} \in$ \honest{E_1}).
$E_1$ and $E_2$ are unaware of active competitors and mount the classical attack in steps $(1_1)$ and $(1_2)$. When the attackers spy two requests to the server transiting on the network, they both believe that $A$ wishes to request keys with the honest agents B and $E_j$.
\\
\textbf{(1.T1)}: \emph{$S$ sends two messages before $A$ can address a message to $B$.}
With the messages in steps $(2_1)$ and $(2_2)$, $A$ receives two keys instead of the single key requested. $A$ now knows that at least one attacker is active and abandons the protocol without sending a message to $B$. The attackers do not spy the message they were hoping for (timeout) and acquire the certainty that at least another active attacker is around. The attackers can employ ad-hoc strategies to search for the mislabeled or unknown attacker. If the attackers are careful to keep track of the messages $(A, X)$  pertaining to a given session, they can make informed guesses as to whom, amongst the known agents, they might have mislabeled.
\\
\textbf{(1.T2)}:\emph{ $A$ receives a reply from $S$, answers $B$ and stops listening.}
$A$ receives the messages he expects and closes the current session before receiving the second response from $S$. $E_1$ is successful in his attack, whereas $E_2$ believes that he has succeeded when he has, in fact, decrypted the wrong key. None of the agents have an opportunity for detection.
\\
\textbf{(1.T3)}:\emph{ $A$ receives a reply from $S$, answers $B$ and keeps listening.}
$A$ replies with the message in step $(3)$, resulting in both $E_1$ and $E_2$ believing that they have succeeded. However, after receiving $(2_2)$, $A$ detects the attack and abstains from employing $k_{AE_1}$ in his future communications with $B$. Thus, even if for different reasons, both attackers in fact fail. Furthermore, they both continue to hold their mistaken belief that the other attacker is in fact honest.

$ $\\
\noindent \textbf{Case 2: $E_{1}$ and $E_{2}$ know each other as attackers.}\\
$E_{1}$ and $E_{2}$ know each other's identifier ($E_{1} \in D_{E_{2}}$ and $E_{2} \in D_{E_{1}}$) and have correctly understood that the other is behaving as a dishonest agent
($E_{1} \in $ \dishonest{E_2} and $E_{2} \in $ \dishonest{E_1}).
Each attacker is aware of the presence of a competitor, which they have correctly labeled. Each attacker is attempting to gain exclusive access to the initial communication towards $S$ and to ensure that only his request reaches $S$. $E_1$ and $E_2$ erase each other's request to $S$. Within our model, no attacker can be certain that his message has been received by its intended receiver; the attackers may wish to replay step $(1_1)$ and $(1_2)$ if a message of the type $\{\!| k_{AE_{j}} |\!\}_{k_{AS}}, \{\!| k_{AE_{j}} |\!\}_{k_{E_{j}S}}$ is not spied on the network within a reasonable time. This option is marked with $(\cdot)^{+}$ in Table~\ref{tracesBME}. However, the active presence of the competitor ensures that no message reaches $S$. $A$ notices that an anomalous situation is occurring, because his request to the server is not being served in a reasonable time. $A$ interprets the situation as a denial-of-service attack and abandons the protocol.

\begin{table}[t!]
\begin{center}
\scalebox{0.8}{
\begin{tabular}{cc}
\hline
\footnotesize {\bf  T1: cases 1, 3, 4, 6} &
\footnotesize {\bf  T2 and [T3]: cases 1, 3, 4, 6}\\
\hline \\
\scriptsize
$
\begin{array}{rll}
(1\phantom{_{1}}) & A \to E_{1,2}(S)  & : A, B \\
\downarrow(1_{1}) & E_{1}(A) \to S  & : A, E_{1}  \\
\uparrow(1_{2}) & E_{2}(A) \to S  & : A, E_{2} \\
(2_{1}) & S \to A  & : M_{1} \\
(2_{2}) & S \to A  & :  M_{2} \\
\end{array}
$
&
\scriptsize
$
\begin{array}{rll}
(1\phantom{_{1}}) & A \to E_{1,2}(S)  & : A, B \\
\downarrow(1_{1}) & E_{1}(A) \to S  & : A, E_{1} \\
\uparrow(1_{2}) & E_{2}(A) \to S  & : A, E_{2} \\
(2_{1}) & S \to A  & :  M_{1} \\
(3\phantom{_{1}}) & A \to E_{1,2}(B)  & : \{\!| k_{AE_{1}} |\!\}_{k_{E_{1}S}} \\
\phantom{\{\!|} \left[
(2_{2}) \right. & S \to A  & :  M_{2} \left]
\right. \\
\end{array}
$
\\
&\\
\hline
\footnotesize {\bf T4: case 2} &
\footnotesize {\bf T5: case 5} \\
\hline \\
\scriptsize
$
\begin{array}{rll}
(1\phantom{_{1}})\phantom{^{+}} & A \to E_{1,2}(S)  & : A, B \\
\downarrow(1_{1})^{+} & E_{1}(A) \to E_{2}(S)  & : A, E_{1} \\
\uparrow(1_{2})^{+} & E_{2}(A) \to E_{1}(S)  & : A, E_{2} \\
\end{array}
$
&
\scriptsize
$
\begin{array}{rll}
(1\phantom{_{1}}) & A \to E_{1,2}(S)  & : A, B \\
\downarrow(1_{1}) & E_{1}(A) \to E_{2}(S)  & : A, E_{1} \\
\uparrow (1_{2}) & E_{2}(A) \to S  & : A, E_{2} \\
(2\phantom{_{1}}) & S \to A  & :  M_{2} \\
(3\phantom{_{1}}) & A \to E_{1,2}(B)  & : \{\!| k_{AE_{2}} |\!\}_{k_{E_{2}S}} \!\!\!\!\!\! \\
\end{array}
$
\\
&\\
\hline
\hline
\multicolumn{2}{c}{
\rule[-2 mm]{0mm}{0.7 cm}
Where: 	\scriptsize
$M_{1} = \{\!| k_{AE_{1}} |\!\}_{k_{AS}}, \{\!| k_{AE_{1}} |\!\}_{k_{E_{1}S}} \:,\quad
  M_{2} = \{\!| k_{AE_{2}} |\!\}_{k_{AS}}, \{\!| k_{AE_{2}} |\!\}_{k_{E_{2}S}}$\!\!\!\!
}
\\
\hline
\end{tabular}
}
\end{center}
\caption{Traces for non-collaborative attacks against BME. Traces are exhaustive: $E_1$ and $E_2$ have priority over honest agents and $S$ is honest. Arrows: relative order between $(1_1)$ and $(1_2)$ is irrelevant in determining the outcome.}
\label{tracesBME}
\end{table}

$ $\\
\noindent \textbf{Case 3: $E_{1}$ and $E_{2}$ are unaware of each other.}\\
$E_{1}$ and $E_{2}$ are unaware of the other's presence -- i.e.\ they are not paying attention to the other's activity ($E_{1} \notin D_{E_{2}}$ and $E_{2} \notin D_{E_{1}}$).
Subcases follow closely those described for case $1$ above. The only
significant difference concerns detection for trace T1: here the
attackers must employ exploratory strategies ($\mathit{Inflow\text{-}Spy}${} or $\mathit{Outflow\text{-}Spy}${}),
because they failed to spy an additional message of type $(A, E_m)$
transiting on the network. The failure to observe such a message is a
strong indicator that the competitor's identifier is unknown. In
2-attacker scenarios this is the only legitimate conclusion, whereas
with three or more attackers this situation may also arise from the
interplay between erase and spy operations.

$ $\\
\noindent \textbf{Case 4: $E_{2}$ knows $E_{1}$ as honest.}\\
Only one out of the two attackers $E_{1}$ and $E_{2}$ is paying attention to the other and knows his identifier. Here we consider $E_{1} \in $ \honest{E_2} and $E_{2} \notin D_{E_{1}}.$
Regardless of the order in which steps $(1_1)$ and $(1_2)$ occur, the attacker in disadvantage $E_1$ does not spy the message at step $(1_2)$; $E_2$ does spy $(1_1)$ but, trusting his judgement on $E_1$'s honesty, does not request it to be erased. As a consequence, similarly to case 1, the traces follow schemes T1, T2 and T3. Significant differences concern detection in T1: $E_1$ detects the presence of an unknown attacker, whereas $E_2$ learns of a mislabeled or unknown attacker. The successful attackers in traces T2 and T3 are those whose requests to $S$ are served first; knowledge does not affect the outcome.

$ $\\
\noindent \textbf{Case 5:  $E_{2}$ knows $E_{1}$ as dishonest.}\\
Only one out of the two attackers $E_{1}$ and $E_{2}$ is paying attention to the other and knows his identifier. Here we consider $E_{1} \in $ \dishonest{E_2} and $E_{2} \notin D_{E_{1}}$
Regardless of the order in which steps $(1_1)$ and $(1_2)$ occur, $E_1$ does not spy the message at step $(1_2)$ and $E_2$ uses a direct attack against the competitor. $E_2$ removes $E_1$'s request to the server and remains the only attacker in play, leading $A$ into accepting $k_{AE_2}$ as a session key. $E_1$ does not have an opportunity to detect the competitor.

$ $\\
\noindent \textbf{Case 6: $E_{2}$ knows $E_{1}$, but he is unsure of $E_{1}$'s honesty.}\\
Only one out of the two attackers $E_{1}$ and $E_{2}$ is paying attention to the other and knows his identifier. Here we consider $E_{1} \in $ \notknow{E_2} and $E_{2} \notin D_{E_{1}}$. This case reduces to case 4, with the only difference that $E_2$ is testing the dishonesty of $E_1$, instead of believing his honesty. Whenever $E_2$ realizes that he has failed his attack,
he adds $E_1$ into \dishonest{E_2} and deletes it from \notknow{E_2}.

$ $\\
\noindent \textbf{General considerations.}\\
In traces T2 and T3, the winning attacker is the one whose request is served first by $S$. $S$ is an honest agent but it is not constrained to answering requests in the exact order in which they are received. Attackers do not have control over which requests are served first, although this factor determines whether they cannot do better than acquire the wrong key. Attackers realize in-protocol that they have failed only when they cannot spy a response from $A$, i.e.\ when they do not acquire any keys. Post-protocol detection, on the other hand, can occur also when an attacker with a wrong key attempts to decrypt the later communications addressed by $A$ to $B$.

The case study highlights that, if $A$ keeps the session open for a
reasonable time after step (3), he can improve his chances of
discovering that the key is compromised. This is a simple strategy that
is beneficial and does not depend on the particular protocol.
Furthermore, when $A$ receives two answers from $S$ in response to his
single request, he now has two keys -- at least one of which is shared
with an attacker. If honest agents are immersed in a retaliatory
framework \cite{Bella03,retaliation}, such keys can be used to identify
attackers, to feed them false information or, in general, to launch
well-aimed retaliatory attacks.

\section{Defending vulnerable
protocols against attacks}
\label{sec:defense}

Key exchange protocols are amongst the most used cryptographic
protocols. It is a common security practice to establish a secure
channel by first exchanging a session key and then using it to
authenticate and encrypt the data with symmetric cryptography. The
security of all communications occurring during a session rests on the
integrity of the key. In this context, it is not important per se that a
key has been acquired by an attacker: what matters is whether a
compromised key is used. Rather then on preventing the acquisition of a
session key from ever occurring, the focus is on detecting that the key
has been compromised -- so as to prevent an attack from spreading to the
entire session traffic.

If a protocol is vulnerable, a single DY attacker will succeed with
certainty. However, if attacks to the same protocol are carried out in a
more complex network environment, success is not guaranteed. As shown in
the case study, in competitive scenarios with equal-opportunity
attackers it is not possible for a given attacker to ensure that an
attack is successful under all circumstances. The outcome depends on the
strategy and knowledge conditions of all the active agents, on the
visibility of erased messages to other attackers ($\mathit{canSee} \ne
\{E_1, E_2\}$) and on the order with which $S$ processes requests. In a
sense, the presence of an independent active attacker constrains the
success of otherwise sure-fire attacks.

This principle can be exploited to facilitate detection of attacks
against vulnerable
protocols. Honest agents should not, in principle, be
informed of the specific attack trace to which they are vulnerable.
Hence, if honest agents can perform detection at all, it has to be on
the basis of flags that are independent of the specific attack trace --
and, in general, independent also of the protocol in use. Such flags
encode \emph{local} defense criteria and can be as simple as realizing
that no answer has arrived within a time considered reasonable or
realizing that two (different) answers have been sent in response to a
single request.

The basic idea is constructing a network agent that causes
protocol-indepen\-dent flags to be raised -- via
deliberate
interference with ongoing attacks. In addition, one such \emph{guardian agent} is
formally an attacker, and can therefore be configured with knowledge of
the attack trace(s). The guardian's task can be formulated as raising
protocol-independent flags in correspondence to protocol-dependent
indicators.

\begin{table}[t]
\begin{center}
\begin{tabular}{c|cccc}
\hline
\footnotesize \!\!\!\!\!
\textbf{~~canSee~~}	 \!\!\!\!\! &
\footnotesize \!\!\!\!\!
\textbf{~~Cases~~}  \!\!\!\!\! &
\footnotesize \!\!\!\!\!
\textbf{~~Case 2~~}  \!\!\!\!\!&
\footnotesize \!\!\!\!\!
\textbf{~~Case 5}: ~  \!\!\!\!\!&
\footnotesize \!\!\!\!\!
\textbf{~Case 5}: ~  \!\!\!\!\!\\
\footnotesize
	&
\footnotesize
\textbf{~~1,3,4,6~~} &
\footnotesize
 &
\footnotesize
\textbf{~~$E\in$\dishonest{G}~} &
\footnotesize
\textbf{~ $G\in$\dishonest{E}~} \\
\hline
\rule[-2.5 mm]{0mm}{0.65 cm}
\footnotesize $\{ E, G\}$ & $\sim$$^{+}$ & $\surd$ & $\surd$ & \\
\rule[-2.5 mm]{0mm}{0.65 cm}
\footnotesize $\{ G\}$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ \\
\rule[-2.5 mm]{0mm}{0.65 cm}
\footnotesize $\{ E\}$ & $\sim$$^{+}$ & $\surd$ & $\surd$ & \\
\hline
\end{tabular}
\end{center}
\caption{
Effects of introducing a guardian $G$ for BME when attacker $E$ is active. $G$ operates according to the same strategy as the attackers in the case study. $G$'s active interference results in $A$ detecting attacks always ($\surd$), sometimes ($\sim$), always if $A$ commits to listening after step (3) ($^{+}$). The guardian is progressively more effective the more his beliefs and knowledge reflect the actual set of attackers. $G$ can be effective even when he is not aware of $E$'s presence.
}
\label{table:GuardianBME}
\end{table}

By using such an ad-hoc competitor as defense, it is possible, in some
cases, to allow detection of otherwise-undetectable attacks. If no flag
is raised for $A$, the guardian may be the only attacker at work. In
this case, no ill-intentioned attacker has successfully concluded an
attack; from the standpoint of $A$, actual security is not affected. A
guardian is a practical solution even when it is not all-powerful: any
attack detected by $A$ thanks to the guardian's active presence is an
improvement in security. In Table~\ref{table:GuardianBME}, we show the
effects of introducing a guardian $G$ for BME, configured as the
attackers in the case study.
It is not necessary to demand that the
guardian monitor all traffic -- which is unrealistic at best; on the
other hand, all monitored traffic enjoys partial protection.

Attacks failing are, by themselves, markers that there are other
dishonest agents at work; this fact can be used by the guardian $G$ as a
basis for further detection, possibly on behalf of honest agents. Then
guess-and-test strategies can be used to acquire an understanding of the
second attacker's identity; a rudimentary example is the strategy used
by our attackers for BME when they spy $(A, E_m)$ and $E_m \in$
\notknow{}. Across multiple iterations of the attack procedure and
under different hypotheses concerning (\honest{G}, \dishonest{G},
\notknow{G}), the attacker's identity will eventually be revealed.

In actual scenarios, protocols are implemented through programs in the users' computers. It is very difficult to force users to stop using a protocol as soon as a vulnerability is discovered. The more widespread the protocol, the more difficult it is to ensure that it quickly goes out of use. Two aspects are important: that every user (a) is informed of the new vulnerability and (b) takes action in switching to a secure protocol. Statistics on software upgrades are an unfortunate example of this type of issue.

By designing the user-end software to inform the user of a security failure whenever protocol-independent flags are raised, a guardian can help solve the notification issue as well as raise the likelihood that the user will take action and upgrade. When the weakness in
the protocol is understood, it may be a cost-effective investment to design a guardian with an effective interference strategy, so as to facilitate restoring network security.

\section{Conclusions and future work}
\label{sec:conclusions}

The traditional goal of protocol analysis is discovering attacks, to
prompt replacing a vulnerable protocol with an improved and more secure
one. Reductions are centered on attacks, either to reduce the search
space for attacks (e.g.~\cite{DTL,MillenDenker02,MVB-JCS10}) or to
reduce the number of agents (e.g.~\cite{DTL,comon03twoAgentsEnough}). In
particular, if there exists an attack involving $n$ collaborating attackers, then
there exists an ``equivalent'' attack involving only one. Within this
perspective, it is known that $n$-DY attackers equal in attack power a
single DY attacker, and that the same can be said of Machiavelli-type
attackers~\cite{MR712376,Syverson00dolev-yaois}. As a result, an
exhaustive search for attacks can be performed in a reduced-complexity
model.

On the other hand, within our proposed approach the goal of analysis is finding a strategy to defend the system against existing attacks, rather than identifying vulnerabilities to prompt redesigning the protocol. We would be performing protocol analysis to identify possible \emph{defenses}, rather than attacks.

In the case study, we have shown a counterexample to the statement: ``if
there exists a defense against an attack in a 2-attacker scenario, then
there exists an equivalent defense in a 1-attacker scenario''. This
statement mirrors the classical result on $n$-to-$1$ reducibility and
the counterexample shows that exhaustive searches for defenses against
attacks cannot be carried out in reduced-complexity settings, as
they require at least two attackers.

Having chosen vulnerable protocols, in a single-attacker situation there
is no pro\-to\-col-independent indicator that could be used by honest agents
to become aware that security has been compromised. If there is a single
attacker, no simple defense is possible and the protocol inevitably
fails its security goals. On the other hand, by exploiting an ad-hoc
competitor (the guardian) as a defense, in certain conditions we can
successfully raise protocol-independent indicators of ongoing attacks
and protect the system. Introducing an appropriate guardian procedure as
soon as new attacks are discovered can mitigate the consequences of flawed
protocols still being in use.

Along the line of work presented in this paper, we have investigated two
additional simple protocols as case studies: the Shamir-Rivest-Adleman
three-pass protocol, which differs significantly from BME in that
success is not necessarily exclusive, and the Beller-Yacobi protocol,
which requires interacting with a second honest agent to carry out a
masquerading attack. The goal of these investigations
 is to bring into focus how the salient
features of each protocol are reflected in the possible mechanisms of
interference.
The first case study is available as additional material
in appendix \ref{casestudySRA3P}.
A second topic of interest is evaluating (i) whether the
mechanisms of interaction highlighted in two-attacker scenarios are
directly portable to situations with more than two non-collaborating
attackers, (ii) whether they require ad-hoc generalization and (iii) whether new
types of interaction emerge when more than two dishonest agents are
active. We are investigating this in more detail, along with a
(semi-)automatic implementation of our approach.

\subsection*{Acknowledgements}

The work presented in this paper was partially supported by the
FP7-ICT-2007-1 Pro\-ject no. 216471, "AVANTSSAR: Automated Validation of
Trust and Security of Service-oriented Architectures" (www.avantssar.eu)
and by the FP7-ICT-2009-5 Project no. \\257876, ``SPaCIoS: Secure
Provision and Consumption in the Internet of Services''
(www.spacios.eu). We thank Davide Guardini for his constructive
comments.

redpajama_set_name: RedPajamaArXiv


The Ideal State is a reference to the absolute perfect condition. One way to envision the ideal state of a map, process, product or service is to imagine that money, time and resources were not limited at all. What would you create then? Ideal state value streams are created many times to show the gap between the current state and the ideal state. This can help teams to reaffirm they are in alignment and ensure that the progress made is on track.
Click on the infographic to get your Inventory Reminder. Great for Training.
Inventory waste is any unnecessary storage of materials, products or information.
Excessive amounts of MRO items.
Information and data that is being stored but not used.
Excess supplies, including office supplies.
Working to a push system or a forecast.
Buying to many of items.
Inefficient or poor planning and scheduling.
Build only to demand where possible.
Stabilize processes and use six sigma techniques to minimize variability.
Remove waste from processes so that inventory (raw,wip,fg,mro) can be reduced.
What types of Inventory do you notice at home, work or other places? How do you think that inventory affects the organization?
Click Here to Learn More Online!
Inventory carrying cost, carrying cost, or cost of holding inventory is most often described as a percentage of the inventory value. The percentage is often unique to organizations and includes the amount of capital invested in inventory as well as depreciation, space occupied, insurance and opportunity.
Inventory is listed as an asset on a firm's balance sheet and consists of the stocks or items needed to maintain production, support activities such as maintenance and repair, and provide customer service. Inventory typically is categorized based on its flow through the production cycle, using such designations as raw materials, work in process, and finished goods. Maintenance, repair, and operating supplies also are stocked to support the functionality of the firm.
Reference - Inventory (APICS OMBOK Framework 5.2).
The icon shown above is used to visually display inventory on a value stream map. This symbol also represents places in a value stream where the flow of material/information is stopped (wait points).
Inventory velocity is the speed at which inventory passes through or is cycled in a given period for each item. Inventory velocity's underlying objective is to improve the turnover of inventory.
Inventory Turns = Cost of Goods Sold / Average Inventory on Hand.
How can you Improve Inventory Velocity?
Need help improving inventory? Message us here!
Internal setup refers to the activities associated with elements of a setup procedure that can only be performed while a process or machine is not running.
Removing items from a blender.
Removal of safety or guard equipment.
For more information on setup reduction email us here!
Click on the photo and get your fishbone diagram template.
The fishbone diagram is a structured analysis tool used to organize potential causes associated with a speciffic effect.
Listen to the Gemba - The fishbone diagram (7 basic quality tools).
Inventory Turnover is the number of times your inventory cycles or turns over in a year. Inventory turnover can help an organization understand how efficiently their inventory is supporting sales. The inventory turnover number implies how often inventory was bought and sold throughout the year. Low inventory turnover numbers often hint at overstocking, obsolescence or unstable processes. A high inventory turnover can also be dangerous if it is depleting reserves to quickly.
Inventory turnover is calculated by dividing the cost of goods sold by the average amount of inventory.
An input is a product, service, information, data, labor material or any other type of resource which is added to a process step usually by a supplier. In the case of reverse supply chain the input is sometimes added by a customer. The input is most commonly added to a process or product with the intention of transforming the input into an output. In a SIPOC map the input represents the second stage. Inputs can be measured in terms of quality, volume, time and financial impact on a process.


Meta-analysis is a statistical method for combining numeric evidence from experimental (and sometimes quasi-experimental studies) to produce a weighted average effect size.
What is meta-analysis? - An overview on the benefits and processes involved in meta -analysis from a public health standpoint.
What is meta-analysis? - This is self guided professional development learning module from the Cochrane Collaboration online learning material.


text:
Mike Heron for beginners: 3 albums and 5 tracks
August 22, 2018 October 9, 2017 by Norman Lamont
I've written a lot here about the Incredible String Band, including fairly detailed posts about Robin Williamson and about Mike Heron's Smiling Men album. Here I'll take a look at a few Mike Heron destinations to which you might choose to trust me to guide you. Like his bandmate Robin Williamson, his unpolished voice can be a barrier for some people, but get past that and there's a wealth of great music to be appreciated.
They were rarely anything less than brave, inspired, and profoundly weird. (Andrew Gaerig)
Three albums
The Incredible String Band: The Hangman's Beautiful Daughter (1968)
Widely regarded as the Incredible String Band's masterpiece, their third album is dominated by Robin Williamson, featuring only three Heron songs alongside seven of Williamson's. But it's Heron's A Very Cellular Song that most captures the spirit of the band and, some would say, the times.
"Weaving between styles as divergent as Bahamian funerary music, East Indian incantation and ancient Celtic mysticism, A Very Cellular Song represents a high point in the band's creativity and surely influenced a host of others including Led Zeppelin, the Who and Lou Reed. Handclaps, kazoo, harpsichord and pipes intermingle and morph into each other. If this sounds like dissonance and chaos, it is. However, it holds together and in the end conveys a powerful range of human emotion through pain and joy and back again." (Dan Lander in Music is Rapid Transportation – not sure about Lou Reed but hey. The influence on Robert Plant is well documented and evident throughout his career.)
The Incredible String Band: Wee Tam and the Big Huge (1968)
Released in 1968 as both a double and two single albums, this is regarded as highly as Hangman's, but it's a very different album: less experimental, less multi-tracked, more pastoral and folky. Of all their albums it offers the widest Williamson/Heron contrast, with Williamson taking songs for long poetic meanders through clouds of myth and childhood. Heron's songs – Puppies, Log Cabin Home In The Sky, You Get Brighter, Air, The Greatest Friend, Cousin Caterpillar, and Douglas Traherne Harding – are rooted in folk guitar and simple chords, and the imagery of earth, home and nature. They exude happiness and warmth. It was of this album that a friend of mine said Williamson was the balloon rising into the clouds, and Heron the string keeping it attached to the earth.
Mike Heron: Smiling Men with Bad Reputations (1970)
This was Mike Heron's first solo album. A shock for the String Band's folkie/hippie audience, it saw Heron unleashed as a rock singer, but only on a few tracks. Others wouldn't have been out of place at that point in the Incredible String Band's career. The rock tracks are the best, however. It was one of the great 60s guest star albums. Feast of Stephen has a sumptuous John Cale arrangement. Warm Heart Pastry sees Pete Townshend and Keith Moon (credited as 'Tommy and the Bijoux', with Ronnie Lane on bass) having the most fun they'd ever had outside the tensions of The Who. Some of Townshend's best guitar ever. My full review here.
Five tracks
Mike Heron after the Incredible String Band
After the breakup of the String Band, Mike attempted a mainstream rock band, Mike Heron's Reputation, which produced two albums. The first was built on his tracks from the album the String Band were working on when they split, augmented by session players. It's very light and accessible, inspired by Buddy Holly in particular. The followup, Diamond of Dreams, got mired down in over-fussy prog arrangements.
After another album in 1979, Mike Heron, failed, he went into a long period of withdrawal from the music business, writing for other artists and aiming for publishing success. Only one of these – a weird 1979 Manfred Mann's Earth Band cover of Don't Kill It Carol from Diamond of Dreams – was anything like a hit.
In the early 1990s he put together a small band of excellent musicians who lived near him in the Scottish Borders as Mike Heron's Incredible Acoustic Band. There were no traces of psychedelia or musical exotica here, only concise, well-arranged songs drawn from the news, history and literature. This band took part in the first reunion with Robin Williamson in 1997, and produced a good album Where the Mystics Swim, but were later dropped in favour of the reformed original lineup of the Incredible String Band with Williamson and Clive Palmer. When that broke up, Heron kept a low profile, but a 2009 tribute concert to the String Band brought him together with upcoming folk-rock band Trembling Bells, with whom he has continued to collaborate and tour. They are joined by his daughter Georgia Seddon, a skilled multi-instrumentalist, singer and arranger.
I stumbled on this recent track of Mike revisiting a couple of his songs with Trembling Bells but can't find any more about whether it was part of an album.
Other people's selections
Andrew Gaerig on Pitchfork "Come for the context, stay for the minotaur's porridge!"
Mike Heron miscellany
Echo Coming Back A compilation from several albums Heron released after the Incredible String Band – in other words, most of his career. They range from the mainstream country-rock of 'Mike Heron's Reputation', through the home-produced demos on the Glen Row Tapes to his short-lived but excellent Incredible Acoustic Band of the 1990s
Where the Mystics Swim, the Incredible Acoustic Band's album, released then re-released a few years later in new packaging, seems to be a rarity, commanding high prices.
Conflict of Emotions is a collection of home recordings and intimate solo tracks, meant as demos, showing the range of Heron's songwriting.
You Know What You Could Be is Mike's well-received account of his dual life in 1960s Edinburgh as a trainee accountant and would-be beatnik. It's credited to Mike Heron and Andrew Greig but Greig isn't a ghost writer. Just over half the book is Greig's account of his would-be Incredibles clone band from Fife trying to get a foothold in the late 60s music scene. Both sections are a pleasure to read and the consensus from reviewers was that another Mike Heron autobiography would be very welcome. When I met him at a book signing he said he'd already started.
My Mike Heron covers
Painted Chariot
I Remember It All From Before
OK this is my highly subjective take – if you were trying to introduce a friend to this music what would you choose? Add it to the comments below!
Categories Inspirations, Music I like Tags Incredible String Band, Mike Heron
Shawn Phillips – a voice in the wilderness
Island Samplers – more than your money's worth in old pence

redpajama_set_name: RedPajamaCommonCrawl