Chapter 3

Adversarial Dynamics: The Conficker Case

Study

Daniel Bilar, George Cybenko and John Murphy

Abstract It is well known that computer and network security is an adversarial chal-

lenge. Attackers develop exploits and defenders respond to them through updates,

service packs or other defensive measures. In non-adversarial situations, such as au-

tomobile safety, advances on one side are not countered by the other side and so

progress can be demonstrated over time. In adversarial situations, advances by one

side are countered by the other and so oscillatory performance typically emerges.

This paper contains a detailed study of the coevolution of the Conficker Worm and

associated defenses against it. It demonstrates, in concrete terms, that attackers and

defenders each present moving targets to the other. After detailing specific adap-

tations of attackers and defenders in the context of Conficker and its variants, we

briefly develop a quantitative model for explaining the coevolution based on what

what we call Quantitative Attack Graphs (QAG) which involve attackers selecting

shortest paths through an attack graph with defenders investing in hardening the

shortest path edges appropriately.

Daniel Bilar

Process Query Systems LLC, 16 Cavendish Ct., Lebanon NH 03766

Siege Technologies, 33 S Commercial St., Manchester NH 03101 e-mail: dbilar@acm.org
John Murphy

Process Query Systems LLC, 16 Cavendish Ct., Lebanon NH 03766

e-mail: jmurphy@flowtraq.com
George Cybenko

Process Query Systems LLC, 16 Cavendish Ct., Lebanon NH 03766

Dartmouth College, Hanover NH 03750

e-mail: gvc@flowtraq.com,gvc@dartmouth.edu

41

42

Daniel Bilar, George Cybenko and John Murphy

3.1 Introduction

Progress in operational cyber security has been difficult to demonstrate. In spite of

the research and development investments made over more than 30 years, many gov-

ernment, commercial and consumer information systems continue to be successfully

attacked and exploited on a routine basis. By contrast, research and development in-

vestments in automobile, rail and aviation safety over the same time periods have

led to significant, demonstrable improvements in the corresponding domains.

Advances in standard performance measures for automobile, train and airline

transportation (namely fatalities per unit of travel) are depicted at the top of Fig.

3.1, while corresponding measures for cyber security are depicted at the bottom.

Fig. 3.1: Top Left - TRAFFIC FATALITY RATES: U.S. Motor Vehicle Fatalities per

100 Million Vehicle Miles, 1950-2003. (Source: National Highway Traffic Safety

Administration). Top Middle - RAILROAD-HIGHWAY CROSSING FATALITY

RATES: U.S. Railroad- Highway Crossing Fatalities per 100 Million Vehicle Miles,

1950-2003. (Source: Federal Railroad Administration, Bureau of Transportation

Statistics). Top Right - AVIATION FATALITY RATES: Fatal accidents per mil-

lion departures for U.S. scheduled service airlines, 1950-2003. Accidents due to

sabotage or terrorism are not included. (Source: Air Transport Association). Bottom

Left - VULNERABILITY AND EXPLOIT COUNTS: Total Number of Vulnerabil-

ities and Exploits (Graph produced by P. Sweeney from data in OSVDB). Bottom

Middle - VULNERABILITIES PER HOSTS/USERS/SERVERS: Total Number of

Vulnerabilities normalized by internet hosts, users and servers (Graph produced by

P. Sweeney from data in OSVDB, Internet Systems Consortium (number of hosts

on the Internet), Netcraft webserver survey (number of webservers on the Inter-

net), and Internet World Stats (number of Internet users). ). Bottom Right - EX-

PLOITS NORMALIZED BY ECOMMERCE: Total number of exploits per billion

dollars of e-commerce (Graph produced by P. Sweeney from data in OSVDB and

www.census.gov/estats)

3 Adversarial Dynamics: The Conficker Case Study

43

A major difference between automobile safety and information security is that

in the former the adversaries are natural laws that don’t change, while in the latter

the adversaries are rational humans who adapt quickly and creatively. Consequently,

we argue that we cannot understand or model the cyber security landscape in terms

of steadily making progress towards an asymptotic “solution” as the transportation

statistics suggest is happening in that domain.

In Fig. 3.1, the bottom row of plots show, from left to right, vulnerabilities and/or

exploits in absolute numbers (bottom left), normalized by the estimated number of

hosts, users and servers (bottom middle) and normalized by the estimated amount

of e-commerce (bottom right). The total number of reported vulnerabilities and ex-

ploits is growing at first and leveling off (note that this is a logarithmic plot), with

some noticeable oscillations especially in recent years; however, the trend is most

meaningful if normalized by some measure of corresponding “activity.” For exam-

ple, traffic fatality statistics are routinely normalized by vehicle miles travelled or

aircraft takeoffs.

We have not settled the matter about what the correct or analogous normaliza-

tion for cyber vulnerabilities and exploits would be. If we were to normalize by the

number of different operating system platforms for example, the plot would basi-

cally resemble the bottom left because there simply are not that many different plat-

forms available in the market. If we normalize by the total number of users, hosts

or servers, there is a precipitous drop in vulnerabilities as the bottom middle plot

shows. However, if we normalize by e-commerce “transactions” as measured by es-

timated total e-commerce, the bottom right plot in Fig. 3.1 shows major oscillations

without an obvious extrapolation into the future.

The point is that unlike domains in which we can measure progress against a

stationary environment, cyber security must be viewed as an ongoing sequence of

moves, countermoves, deceptions and strategic adaptations by the various actors

involved - attackers, defenders, vendors and decision/policy makers. Accordingly,

we believe that the appropriate science for understanding the evolving landscape of

cyber security is not the logic of formal systems or new software engineering tech-

niques. Instead, it is an emerging subarea of game theory that investigates dynamics

in adversarial situations and the biases of competing human agents that drive those

dynamics (see [9, 23, 8] for example).

3.1.1 Adversarial Behavior Analytics vs Classical Game Theory

“Solutions”

The original goals of Game Theory were to model adversarial environments and

to optimize strategies for operating in those environments. This would seem ideal

for modeling cyber operations as well as other national security situations - indeed,

there is a community of researchers currently investigating the application of clas-

sical Game Theory to information assurance and cyber operations.

44

Daniel Bilar, George Cybenko and John Murphy

However, the overwhelming focus of Game Theory research over the past 60

years has been on the problem of “solving” games that are defined a priori. That is,

most Game Theory research to date begins by assuming a game is already defined

(namely, the players, their possible moves and payoffs) and then explores properties

of optimal strategies and how to compute them. Optimality is with respect to a

solution criterion such as Nash Equilibrium or Pareto Optimality [5].

An obvious and growing criticism of the classical approach is that in most real

world adversarial situations players do not know who the other players are, what

their possible moves might be and, perhaps most importantly, what their preferred

outcomes or objectives are. Put another way, none of the players actually know the

complete details of the game that they are playing! A further complication is that

few people outside of the Game Theory literati know what a Nash Equilibrium is,

let alone how to compute one, so they typically cannot be expected to play the Nash

solution.

As a result, while Game Theory can inform us about how to play chess, checkers,

poker and simple illustrative examples found in most Game Theory texts, it has not

been as useful in the majority of real-world adversarial situations as one might have

hoped for (see [19, 20] for an interesting discussion). New directions and ideas are

needed, especially in the area of cyber security.

3.1.2 Our Approach

Adversarial behavior analytics is the empirical study of players’ actions in adver-

sarial situations. The “game” in these adversarial situations is implicit and can only

be understood in terms of the moves players make and how they evolve their play in

response to each other’s moves [12].

We have studied historical data from a variety of cyber and national security do-

mains such as computer vulnerability databases, offensive and defensive coevolu-

tion of wormbots such as Conficker, and US border security [22, 24]. The data show

that the “success rate” or other performance metrics in these different domains os-

cillate over time - they are not converging to any asymptote. In fact, when players

are continually responding as best they can to their opponents’ play, periodic and

even chaotic behaviors can be exhibited [23].

Such oscillations are indicators of and intrinsic to adversarial dynamics in com-

plex, competitive environments. In particular, each player is adapting incrementally

to the observed play of his or her opponents. This can be modeled by systems of

differential equations known as replicator equations [9, 22].

The replicator equations are typically third-degree nonlinear so that the resulting

dynamics are difficult to predict analytically. However, the inverse problem of ob-

serving behaviors and estimating parameters of the replicator equations that result

in those behaviors are tractable computational problems. In particular, it is possible

to observe game play and strategy evolution and then make inferences about the

players’ motives, costs and move options.

3 Adversarial Dynamics: The Conficker Case Study

45

This kind of modeling approach can explain the non-convergent dynamics we

are seeing in cyber security and will help us forecast the various players’ future

strategies. Recognizing and harnessing the realities of such dynamic coevolution

will be a key ingredient to dominating cyber operations.

3.1.3 Organization of the Paper

After this introduction, we examine in detail the documented structure of the Con-

ficker Worm and defenses against it. This is, to our knowledge, the first quantitative

attempt to extract and highlight specific adaptations in an adversarial setting. As-

sessment of these moves in the context of classical solution concepts such as Nash

Equilibria is then discussed and is followed by an analysis of the estimated goals and

motives of Conficker’s developers. We then develop the notion of a Quantitative At-

tack Graph (QAG) and present some generic analyses of the adversarial nature of

that model.

3.2 Conficker Analysis

Drawing on published sources [15][3][16][21][7], we model the interactions be-

tween Conficker (specifically its spread and update mechanisms) and its “Ecosys-

tem” (i.e., the networked computing substrate it operates on: Microsoft, the Internet

Infrastructure, the worm analysis community) as an adversarial game between two

players.

3.2.1 Conficker Internal and External State Diagram

We first analyzed Conficker’s internal state diagrams in terms of armoring, update

and scan/infect mechanisms. The goal was to identify vulnerable points to disable

Conficker (Fig. 3.2).

One area we identified was environmental mutations. Conficker A exited upon

detection of a Ukrainian keyboard locale. Conficker C’s well thought out innova-

tion, its P2P module, kills Conficker C if a debugger is detected (Fig. 3.3). We also

found that manipulating the Random Number Generator affects the scan/infected IP

range and the Domain Generation Algorithms IP rendezvous points for potential up-

dates (Fig. 3.4). Subversion of software/hardware encryption/hashing functionality

by triggering on the public key decryption (the RSA public key is known) disables

the install of new binaries (Fig. 3.5). Finally, manipulation of elapsed time/tick count

(through memory writes and/or direct clock influence) affects state transitions in all

mechanisms (Fig. 3.6).

46

Daniel Bilar, George Cybenko and John Murphy

Fig. 3.2: Conficker’s armoring (green), update (red) and scan/infect (blue) mecha-

nisms

Fig. 3.3: Setting environmental observables (debugger present, VM environment,

keyboard locale) causes shutdown

Also of interest is the susceptible host population view, representing the external

state transitions. Fig. 3.7 shows the migration chart of the Conficker variants, while

3 Adversarial Dynamics: The Conficker Case Study

47

Fig. 3.4: Manipulating the Random Number Generator affects the scan/infected IP

range and the Domain Generation Algorithms IP rendezvous points

Fig. 3.5: Subversion of encryption functionality disables the install of new binaries

Fig. 3.8 shows the individual Conficker A/B/C/D/E host state changes. For a general

discussion on subverting end systems through subsystems, see [1].

Lack of a common naming scheme for Conficker and disagreement among an-

alysts which release constitute new versions complicate matters somewhat. For ex-

48

Daniel Bilar, George Cybenko and John Murphy

Fig. 3.6: Control of elapsed time/tick count affects state transitions in all mecha-

nisms

Fig. 3.7: Transitions and updates to Conficker variants

ample, the third release (Microsoft’s Conficker.C) is recognized as only incremental

by the SRI-based Conficker Working Group (CWG), and is not recognized at all by

Symantec.

Table 3.1 shows the names currently used by each group. While we have not

seen evidence that this naming confusion had any measurable effect on the ability

3 Adversarial Dynamics: The Conficker Case Study

49

Fig. 3.8: Variant transitions and external state diagram

to defend against Conficker, it was a confounding factor in researching Conficker.

We use the Microsoft nomenclature in this report, except where noted.

Table 3.1: Conficker naming conventions according to Microsoft, SRI and Symantec

Microsoft

SRI

Symantec

Conficker.A

Conficker.A

W32.Downadup

Conficker.B

Conficker.B

W32.Downadup.B

Conficker.C

Conficker.B++

Conficker.D

Conficker.C

W32.Downadup.C

Conficker.E

Conficker.E

W32.Downadup.E

3.2.2 Time-evolution of Conficker

Two timelines are involved, Conficker’s and the Ecosystem. Within those timelines,

we distinguish among three epochs with corresponding time regimes: The era be-

fore the first appearance of Conficker A (“BCA”), followed by the emergence of

the Conficker timeline (“ACA”). The final post-Conficker E (“PCE”) epoch is not

analyzed further in this report.

50

Daniel Bilar, George Cybenko and John Murphy

In BCA, the necessary Ecosystem pre-conditions for the viability/emergence of

Conficker have to be met. These pre-conditions include “long reach propagation”,

a long range internet accessible vulnerability (in Conficker’s case: MS08-067 RPC-

DCOM), and “weaponization”, an exploit for that vulnerability in a form that can

be integrated into a worm (in Conficker’s case: $37.80 Chinese-made exploit kit for

RPC-DCOM ) [17].

As a simplifying abstraction, we view the developments in the BCA era as

Ecosystem configuration fluctuations, rather than moves in a game. Once a Conficker-

amenable configuration arises (i.e a worm-integratable exploit for long range vulner-

ability), a race-to-market begins between attacker and defender to plug the security

“hole”. This typically takes the form of vendor software patches to fix competing

with a worm exemplar to exploit the vulnerability. Events unfolding under this time

regime can be modeled as a multi-objective optimization problem, balancing prod-

uct performance (the “quality” of both the patch and the worm) and speed-to-market

(who gets to the security hole first).

Conficker A appeared on Nov. 20, 2008. From then onwards (the ACA era),

we start interpreting measures by the Ecosystem and Conficker A/B/C/D/E code

evolution as moves and counter-moves in an adversarial game. We illustrate this

with Fig. 3.9 below.

Fig. 3.9: Conficker and Ecosystem timelines. We distinguish among three epochs,

but only the ACA time regime is analyzed in this paper. Race-to-market begins with

an Ecosystem configuration that includes a long-range vulnerability and a concomi-

tant worm-integratable exploit.