Research on Deception in
Defense of Information Systems
Neil C. Rowe, Mikhail Auguston, Doron Drusinsky, and
J. Bret Michael
U.S. Naval Postgraduate School
Code CS, 833 Dyer Road
Monterey, CA USA 93943
ncrowe, maugusto, ddrusins, and bmichael @ nps.navy.mil
Abstract
Our research group has
been broadly studying the use of deliberate deception by software to foil
attacks on information systems. This
can provide a second line of defense when access controls have been breached or
against insider attacks. The thousands
of new attacks being discovered every year that subvert access controls say
that such a second line of defense is desperately needed. We have developed a number of demonstration
systems, including a fake directory system intended to waste the time of spies,
a Web information resource that delays suspicious requests, a modified
file-download utility that pretends to succumb to a buffer overflow, and a tool
for systematically modifying an operating system to insert deceptive responses. We are also developing an associated theory
of deception that can be used to analyze and create offensive and defensive
deceptions, with especial attention to reasoning about time using temporal
logic. We conclude with some discussion
of the legal implications of deception by computers.
This paper appeared in the Command and Control
Research and Technology Symposium, San Diego, CA, June 2004.
A
theory of deception in information systems
Deception
is a key feature of human social interaction not much studied in either
information security or artificial intelligence. In one part of our project, we are developing testable
computational models of deception including the major sub-phenomena or trust,
expectation, suspicion, surprise, deception plans, and manufactured patterns
(Bell & Whaley, 1991). Such a
theory can be used to explain both offensive deceptions (to gain some
advantage) and defensive deceptions (to foil someone else's plans). Defensive deception could fool attackers
into thinking our systems are not worthy of attack, or thinking incorrectly
they have hurt us. It can be very
convincing because people expect computer systems to be obedient servants. Paradoxically, deception against bad people
can increase the trust level of good people, much like how an inquisitive
police force increases social trust.
Deceptions can also produce useful side effects like identification of
the attacker by planting phone numbers we can trace or installing "spyware"
on the attacker that will report their activities.
Producing
a convincing defensive deception requires careful planning because people can
easily recognize patterns suggesting it.
So deception needs to be applied sparingly and thoughtfully based on a
theory of trust and "suspiciousness" and its psychological
consequences (Miller & Stiff, 1993).
We are exploring applying it in two different ways. One will use a theory of "generic
excuses" that will frustrate the attacker but appear to be highly
plausible. The other way will use a
theory of "counterplanning" that will frustrate the attacker in
highly effective but hard-to-notice ways.
Counterplanning can make use of artificial-intelligence planning
research but has unique issues too.
We
must be careful not to apply deceptions to non-malicious users who accidentally
act suspicious; thus intrusion-detection systems need to search for consistent
patterns in lower levels of suspiciousness, a different set of criteria than
employed today. Deception also raises
ethical issues to be explored. In
general, deception is judged ethical against serious consequences (e.g.
destruction of a computer system in an attack) which may apply to
cyberterrorism (Tan, 2003).
One part of our research on the theory of
deception (Rowe and Rothstein, 2004) looked at the classic deception methods of conventional
warfare: concealment, camouflage, ruses, demonstrations,
feints, false and planted information, lies, displays; and insight. Of
the nine, concealment and camouflage of operations (as opposed to data)
are difficult in cyberspace since so much of it is black and white: Either a
file exists or not. Then domain name
servers are quite willing to tell adversaries about what resources exist. Ruses are not helpful in cyberwarfare
because identity theft is easy and lacks surprise. Demonstrations are hard to make convincing and likely
counterproductive since shows of strength encourage attacks which cannot be
defended. Feints are not helpful because
it is so difficult to localize an enemy for a counterattack in cyberspace. False and planted information, such as
posting fake attack methods on hacker bulletin boards is certainly possible,
but it may turn out to be easy to confirm most statements about cyberspace with
sufficient time.
This leaves lies, displays, and insights as potential defensive tactics. Moreover, they are powerful tactics just beginning to be explored. Outright lies by an information system can be effective because users are so accustomed to truth from their systems. The system could lie about completing a download of a suspicious file or give a false excuse as to why it cannot. Or lies could be integrated into an overall "display" for the attacker. An example would be simulating an infection by a virus while actually destroying the infection. "Insights" would be the next step, where a set of lies and displays could be integrated into an overall defensive strategy designed to cause the attacker the maximum amount of trouble, using methods from artificial intelligence. (Cohen, 1999) gives an interesting further taxonomy of deception methods.
Implementation of
automatic deceptions and deception planning
We have implemented
several demonstration systems for deceptive software. One was a Web browser that delays answering requests when it
suspects it is under attack (Julian et al, 2003). Another was a file-transfer utility that pretends to succumb to a
well-known buffer-overflow attack (Michael, Fragkos, and Auguston, 2003).
Another was a
demonstration Web site including a number of deceptive practices. The site looks like a file directory
hierarchy (see Figure 1); users can click on names of directories to see
subfiles and subdirectories with fake dates and sizes, and can click on names
of files to see captioned image data.
Some of the files appear to be encrypted like that on the top right of
Figure 1. Authorization errors are
issued for some other files, and loading time is proportional to the listed
number of bytes of the file but is exaggerated. However, the directories and files are all fake: Names are chosen
randomly from a list of all the Web page names at our school, and contents of
the accessible and readable files are generated by randomly choosing a picture
and its caption from a school Web page.
The picture at the bottom of Figure 1 was allegedly the file
/root/Code05/WAT/policy/
Old_pages/23_AdvancesNonPhotoRealisticRendering/Locations/NavalPostgraduate
School/images/aries_thumbnail.html,
which suggests that this Aries vehicle has something to do with photographic
rendering, policy, and wide-area timesharing, none of which is true. The site functions as a kind of
"honeypot" for spies, encouraging them to find spurious connections
between seemingly meaningful things, while the encryption and the authorization
errors suggest hidden secrets.
We also implemented a
software tool MECOUNTER (Rowe, 2003) to systematically "counterplan"
(Carbonell, 1981) or find ways to foil a computer-system attack plan. This work is built on previous research in automated
planning from constraints, and exploits a hierarchical and probabilistic attack
model. The model has two agents with
different goals, an attacker and a computer system. To test our
counterplanning, we tested it on a particular model we built for attacks that
use buffer overflows to install rootkits.
This model is of a sufficiently high level to ignore details that change
frequently between attacks such as the particular buffer-overflow method, but
detailed enough to capture most details of situation-independent behavior. It models nineteen action types which can
be instantiated to ninety-three distinct actions. The specifications cover a possible 115 distinct facts (and their
115 negations) in states, preconditions, and goals, and allow for thirteen categories
of random occurrences with actions. We
defined for it 3072 test starting states for the goals of installing a rootkit
on a system, installing gimmicked port-management software, and logging
out. When no complicating random
events occur, forty-eight steps are sufficient to achieve the goal from the
most complex start state.
Our approach to counterplanning is to first find
all possible atomic "ploys" that can interfere with the plan. Ploys are simple deceits the operating
system can perform such as lying about the status of a file. We analyze ploys as to the degree of
difficulty they cause to the attack plan wherever they can be applied. This is more complex than it seems because ploys may necessitate changes to more than
one fact simultaneously. For instance,
if we add a fact that a file F on site S is compressed, we must add the fact
that F is on S if that fact is not asserted already. So for any proposed deletion or addition of a fact to a state, we
must determine all implied facts and implied negations of facts. We can infer that A implies B if whenever A
occurs in a state, B also occurs. We
can infer that A implies not(B) if whenever A occurs in a state, B does not
occur. Such implications obey transitivity
(if A implies B and B implies C, A implies C) and contrapositivity (if A
implies B, then not(B) implies not(A)) which reduces their required
number. As an aid to designers of
deception strategies, we have a tool program that
Figure 1: Example from the fake file
directory deception.
examines the states resulting from
a set of simulation runs of the planner and suggests implications.
Several principles then can be used to prune possible ploys. It makes no sense to apply a ploy to a state if the ploy is a normal plan action for that state. Facts added by a ploy that are already true in a state, or facts deleted by a ploy that are already false in a state, can be ignored to simplify the ploy (or eliminate it if all changes are removed). It is not generally possible to delete mental consequences of actions (such as human knowledge of particular vulnerability), though strong efforts at disinformation can sometimes work. It makes no sense to delete, add, or change an order with a ploy since computers are should be agents of human needs and this kind of deception is easily apparent. Similarly, it makes no sense to delete a report since a human is expecting that report. But false reports are useful ploys, either events that never occurred (like reporting that the network crashed) or events that occurred differently (like reporting that the network is slow when it is not); false reports eventually cause precondition violations and failure during execution of actions. We assume a false report must relate to a precondition or postcondition of the preceding action. For our rootkit-installation example after pruning, we found 588 implications, 16 fact-deletion ploys, 28 fact-addition ploys, and 16 ploys with both fact deletion and addition.
We then formulate a counterplan by selecting the
most cost-effective set of ploys and assign appropriate presentation methods
for them, taking into account the likelihood that, if we are not careful, the
attacker will realize they are being deceived and will terminate our game with
them. The counterplan can be
accomplished by a modified operating system.
An
exhaustive approach to finding the best ploys for the counterplan is to
systematically consider each one for each state, an analogy to approximating
partial derivatives of a cost function.
The most troublesome ploy-state combinations for the attacker can be
executed. However, much of this
exhaustive analysis is unnecessary. We
can collapse analysis of identical states in different runs, building a Markov
state model with state-transition probabilities. State equivalence can be qualitative to further reduce the
possibilities. We ran our
rootkit-installation model 500 times (in about 700 minutes) with random
starting states drawn from the set of 3072, the defined random postconditions,
and durations defined by probability distributions (allowing that attacker and
system can work in parallel) to get 10,276 distinct states in 21,720 total
states, which cut our work in half.
A second efficiency idea is to infer good
ploys from similar situations using inheritance and inheritance-like rules. We devised useful rules for
25
"backward
temporal suitability inheritance," "downward fixplan
inheritance," and "ploy fixplan following." For our full example of rootkit installation
with 500 simulation runs, there were 70 ploys for the 10,276 possible states,
providing 616,560 ploy-to-state match possibilities. Only 19,112 of these were needed for initial analysis, and
temporal inheritance expanded this to 104,971.
Of these, only 18,835 (3.0%) were found meaningful and damaging to the
attacker. (The average fixplan needed
6.6 steps to return the attacker to a known state.) Combining this data with the benefits of the Markov model, we
reduced our counterplanning effort to 1.4% of the cost of an exhaustive test of
changes to the simulation, without eliminating any useful possibilities.
After promising ploys and their best times of
application to the plan have been computed, we must choose a good set of them
to comprise the counterplan. Our
benefit metric must reflect the results of numerous "red team"
experiments that showed that well-trained and determined attackers usually
eventually gained control of target computer systems. So our only realistic objective is to delay the attacker
maximally. But we cannot just do this
by implementing every ploy every time because the more ploys we use, the more
likely the attacker will suspect they are being fooled. Then the more likely the attacker will give
up and log off, and we cannot then delay them further. The simplest acceptable model of the expected
benefit due to ploy i at state j in a counterplan we found was:
where 
is the frequency of
the occurrence of state j in a randomly chosen complete attack plan; 
is the probability
that a user beginning an attack plan including j actually reaches state j
(without being discouraged, etc.); 
is the probability
that ploy i succeeds; 
is the expected time
added to the plan by the ploy i at state j; r
is the ratio of the value of a delay of one unit of a legitimate user's time to the delay of one unit of an
attacker's time; 
is the probability
the behavior observed so far is part of the attack plan for which the ploys
were generated; f(x) is a sigmoid function between 0 and 1 (we used
in experiments); 
is the a priori
probability of the ploy occurring at random; 
is the association
probability between this ploy and the most-similar previous one.
We used a greedy search to choose the best set
of ploys since it performed almost as well as branch-and-bound in test
runs. That is, we choose the best
ploy-time pair, then the second best of the remaining ploy-time pairs after
adjusting probabilities, then the third, and so on until expected ploy time
delays no longer exceed a fixed threshold.
We use the same counterplan for each attack because consistency is
important in deception. We discovered
with MECOUNTER analyzing the results of the 500 simulation runs that the best
way to impede the root-compromise plan was to do 22 ploy-state
combinations. These changes included
some obvious ones (like faking general network problems and deleting the
rootkit after the attacker has logged out) and less obvious ones (such as
issuing false reports that the downloaded files are now recompressed). In general, all ploys proposed by MECOUNTER
were helpful and reasonable for defense of the system.
Prototype design of an
intrusion interception language CHAMELEON
We
also developed and implemented the first version of the rule language CHAMELEON
(Michael, Fragkos, and Auguston, 2003) for experiments with software decoys in
Red Hat Linux 6.2 environment. The
implementation is based on the Linux kernel wrapper tools developed by NAI (Ko
et al, 2000). This provides a more
general approach to implementing deceptions in the form of a tool to
systematically modify large software systems like operating systems.
This
first version of rule language provides functionality for signature-based
intrusion detection and countermeasures, like delay or total blocking of kernel
command execution, and error message generation. Intrusion signatures can be specified as regular expressions over
kernel subroutine calls and can involve also values of input and output
parameters of kernel calls. The
CHAMELEON compiler takes the rule source code and generates wrapper code in the
Wrapper Definition Language (WDL) in addition to a script file necessary to compile
the WDL code into executable and install and activate the wrapper in the kernel
space. The Appendix shows the formal
syntax of the language.
Wrapper
Support System (WSS) monitors install wrappers and creates a new instance of a
wrapper for each process executed within the system. Since event patterns can be accompanied by actions written in the
C language, it becomes possible to program arbitrary countermeasures in
response to the detected intrusion activities.
As
an example, the rule below detects a sequence of file operations, including
opening the file, some read/write operations, and closing the file. Each event will cause a message to be sent
to the system-monitoring log file with the file name involved. The pre and post options
indicate whether the corresponding action is performed before or after the
matching kernel call. $path is one of several predefined access variables that
provide values of kernel call parameters.
/*
simple rule example */
R1 :
detect
open pre { wr_printf("open file %s," $path) ; }
( read pre { wr_printf("read file %s ," $path);
} |
write
pre {wr_printf("write file %s ," $path);} ) *
close post { wr_printf(
"file %s closed," $path); }
Besides
executing arbitrary C code, the actions performed by wrapper rules may include
two simple primitives: DENY, which will prevent execution of corresponding
kernel call, and DELAY(N), which delays execution of kernel call by N
milliseconds.
The
CHAMELEON framework supports signature-based intrusion detection and a basic
countermeasures mechanism. Future work includes an extension to accommodate
anomaly-based statistical methods for detecting system misuse. One idea we are exploring is to use a
third-party intrusion detection system that communicate with the wrappers
(Monteiro, 2003), which appears a promising way to cut development costs
significantly.
Run-time monitoring of Knowledge Temporal Logic
specifications
Another
aspect of our research is modeling the time sequence of events in deceptions
and attempts to foil them. We have
found temporal logic quite useful.
(Pnueli, 1977) suggested using Linear-Time Propositional Temporal Logic
(LTL) for reasoning about concurrent programs.
LTL is an extension of propositional logic where, in addition to the
well-known propositional logic operators, there are four future-time operators
(◊-Eventually, ÿ-Always, U-Until,
Ο-Next) and four dual past-time operators. (Fagin et al, 1995) developed
a general framework for modeling knowledge and computation and apply it towards
reasoning about knowledge in distributed systems. This framework, which we refer to as knowledge logic, is
based on propositional modal logic.
