Textual Analysis for Network Attack Recognition
Application to Real Data

Applying Textual Analysis to Detect Patterns in Logs

Here are some preliminary results for applying these textual analysis techniques to log data.

Somewhat surprisingly, with English prose the measures of resemblance, containment, and Dice's coefficient were of little use but the vector space model worked reasonably well.

The opposite is true with the syslog data. The vector space model was of little use, its results are not shown here.

A collection of log data was selected, including 15 attack sequences from 6 attacking hosts.

Below are the results of the resemblance measure. The following sets of attack sequences are each from the same attacking host, where sequences J and K are identical:

• A, B, C
• D
• E, F, G
• H, I
• J, K, L
• M, N, O

Picking an arbitrary threshold of 0.3, the values colored in green in the following tables show correct classification of similar attack form, while values in yellow show errors — within-source measures below the cutoff (false-negative error) or between-source measures above it (false-positive error).

Resemblance table:
       A       B       C       D       E       F       G       H       I       J       K       L       M       N       O
A  1.00000 0.06485 0.80205 0.00000 0.00296 0.00193 0.00203 0.00000 0.00000 0.00066 0.00066 0.00161 0.00152 0.00030 0.00000
B  0.06485 1.00000 0.08085 0.00000 0.00248 0.00131 0.00459 0.00000 0.00000 0.00036 0.00036 0.00103 0.00260 0.00015 0.00000
C  0.80205 0.08085 1.00000 0.00000 0.00324 0.00205 0.00230 0.00000 0.00000 0.00067 0.00067 0.00168 0.00167 0.00030 0.00000
D  0.00000 0.00000 0.00000 1.00000 0.03795 0.02257 0.05848 0.37423 0.09816 0.05925 0.05925 0.16963 0.00000 0.01469 0.00000
E  0.00296 0.00248 0.00324 0.03795 1.00000 0.51747 0.51948 0.02288 0.00000 0.01299 0.01299 0.02056 0.00133 0.00175 0.00000
F  0.00193 0.00131 0.00205 0.02257 0.51747 1.00000 0.26882 0.01256 0.00000 0.12230 0.12230 0.17741 0.00090 0.00181 0.00000
G  0.00203 0.00459 0.00230 0.05848 0.51948 0.26882 1.00000 0.03968 0.00000 0.01172 0.01172 0.01852 0.00177 0.00165 0.00000
H  0.00000 0.00000 0.00000 0.37423 0.02288 0.01256 0.03968 1.00000 0.27419 0.02230 0.02230 0.06381 0.00000 0.00431 0.00000
I  0.00000 0.00000 0.00000 0.09816 0.00000 0.00000 0.00000 0.27419 1.00000 0.00585 0.00585 0.01674 0.00000 0.00247 0.00000
J  0.00066 0.00036 0.00067 0.05925 0.01299 0.12230 0.01172 0.02230 0.00585 1.00000 1.00000 0.34931 0.00032 0.01121 0.00000
K  0.00066 0.00036 0.00067 0.05925 0.01299 0.12230 0.01172 0.02230 0.00585 1.00000 1.00000 0.34931 0.00032 0.01121 0.00000
L  0.00161 0.00103 0.00168 0.16963 0.02056 0.17741 0.01852 0.06381 0.01674 0.34931 0.34931 1.00000 0.00076 0.01393 0.00000
M  0.00152 0.00260 0.00167 0.00000 0.00133 0.00090 0.00177 0.00000 0.00000 0.00032 0.00032 0.00076 1.00000 0.05658 0.20765
N  0.00030 0.00015 0.00030 0.01469 0.00175 0.00181 0.00165 0.00431 0.00247 0.01121 0.01121 0.01393 0.05658 1.00000 0.01175
O  0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.20765 0.01175 1.00000

Containment table:
       A       B       C       D       E       F       G       H       I       J       K       L       M       N       O
A  1.00000 1.00000 1.00000 0.00000 0.00520 0.00269 0.00500 0.00000 0.00000 0.00073 0.00073 0.00209 0.00273 0.00031 0.00000
B  0.06485 1.00000 0.08085 0.00000 0.00260 0.00134 0.00500 0.00000 0.00000 0.00037 0.00037 0.00105 0.00273 0.00016 0.00000
C  0.80205 1.00000 1.00000 0.00000 0.00520 0.00269 0.00500 0.00000 0.00000 0.00073 0.00073 0.00209 0.00273 0.00031 0.00000
D  0.00000 0.00000 0.00000 1.00000 0.05195 0.02688 0.10000 0.98387 0.94118 0.05925 0.05925 0.16963 0.00000 0.01484 0.00000
E  0.00683 0.05263 0.00851 0.12346 1.00000 0.51747 1.00000 0.16129 0.00000 0.01463 0.01463 0.02827 0.00273 0.00186 0.00000
F  0.00683 0.05263 0.00851 0.12346 1.00000 1.00000 1.00000 0.16129 0.00000 0.13863 0.13863 0.26806 0.00273 0.00201 0.00000
G  0.00341 0.05263 0.00426 0.12346 0.51948 0.26882 1.00000 0.16129 0.00000 0.01244 0.01244 0.02199 0.00273 0.00170 0.00000
H  0.00000 0.00000 0.00000 0.37654 0.02597 0.01344 0.05000 1.00000 1.00000 0.02231 0.02231 0.06387 0.00000 0.00433 0.00000
I  0.00000 0.00000 0.00000 0.09877 0.00000 0.00000 0.00000 0.27419 1.00000 0.00585 0.00585 0.01675 0.00000 0.00247 0.00000
J  0.00683 0.05263 0.00851 1.00000 0.10390 0.50941 0.17000 0.98387 0.94118 1.00000 1.00000 1.00000 0.00273 0.01577 0.00000
K  0.00683 0.05263 0.00851 1.00000 0.10390 0.50941 0.17000 0.98387 0.94118 1.00000 1.00000 1.00000 0.00273 0.01577 0.00000
L  0.00683 0.05263 0.00851 1.00000 0.07013 0.34409 0.10500 0.98387 0.94118 0.34931 0.34931 1.00000 0.00273 0.01577 0.00000
M  0.00341 0.05263 0.00426 0.00000 0.00260 0.00134 0.00500 0.00000 0.00000 0.00037 0.00037 0.00105 1.00000 0.05658 1.00000
N  0.00683 0.05263 0.00851 0.59259 0.03117 0.01747 0.05500 0.45161 0.94118 0.03731 0.03731 0.10681 1.00000 1.00000 1.00000
O  0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.20765 0.01175 1.00000

Dice's coefficient table:
       A       B       C       D       E       F       G       H       I       J       K       L       M       N       O
A  1.00000 0.12180 0.89015 0.00000 0.00590 0.00386 0.00406 0.00000 0.00000 0.00132 0.00132 0.00321 0.00304 0.00059 0.00000
B  0.12180 1.00000 0.14961 0.00000 0.00495 0.00262 0.00913 0.00000 0.00000 0.00073 0.00073 0.00205 0.00520 0.00031 0.00000
C  0.89015 0.14961 1.00000 0.00000 0.00645 0.00409 0.00460 0.00000 0.00000 0.00135 0.00135 0.00336 0.00333 0.00060 0.00000
D  0.00000 0.00000 0.00000 1.00000 0.07313 0.04415 0.11050 0.54464 0.17877 0.11188 0.11188 0.29006 0.00000 0.02896 0.00000
E  0.00590 0.00495 0.00645 0.07313 1.00000 0.68202 0.68376 0.04474 0.00000 0.02565 0.02565 0.04030 0.00266 0.00350 0.00000
F  0.00386 0.00262 0.00409 0.04415 0.68202 1.00000 0.42373 0.02481 0.00000 0.21794 0.21794 0.30135 0.00180 0.00361 0.00000
G  0.00406 0.00913 0.00460 0.11050 0.68376 0.42373 1.00000 0.07634 0.00000 0.02318 0.02318 0.03636 0.00353 0.00330 0.00000
H  0.00000 0.00000 0.00000 0.54464 0.04474 0.02481 0.07634 1.00000 0.43038 0.04363 0.04363 0.11996 0.00000 0.00857 0.00000
I  0.00000 0.00000 0.00000 0.17877 0.00000 0.00000 0.00000 0.43038 1.00000 0.01163 0.01163 0.03292 0.00000 0.00493 0.00000
J  0.00132 0.00073 0.00135 0.11188 0.02565 0.21794 0.02318 0.04363 0.01163 1.00000 1.00000 0.51776 0.00064 0.02217 0.00000
K  0.00132 0.00073 0.00135 0.11188 0.02565 0.21794 0.02318 0.04363 0.01163 1.00000 1.00000 0.51776 0.00065 0.02217 0.00000
L  0.00321 0.00205 0.00336 0.29006 0.04030 0.30135 0.03636 0.11996 0.03292 0.51776 0.51776 1.00000 0.00151 0.02748 0.00000
M  0.00304 0.00520 0.00333 0.00000 0.00266 0.00180 0.00353 0.00000 0.00000 0.00064 0.00065 0.00151 1.00000 0.10710 0.34389
N  0.00059 0.00031 0.00060 0.02896 0.00350 0.00361 0.00330 0.00857 0.00493 0.02217 0.02217 0.02748 0.10710 1.00000 0.02322
O  0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.34389 0.02322 1.00000

Discussion of the Results

Resemblance and Dice's coefficient seem most useful. Dice's coefficient performed slightly better on this data set.

The containment measure was less useful due to false-positive matches, as might be expected. Small sequences (e.g., H and I) are contained within large sequences (D, J, K, L, and N in this case).

     Set:   H  I     D   J    K    L    N
Shingles:  62 17    162 3042 3042 1088 9391

Classification was better on sets of similar sizes than on sets where one sequence terminated much earlier. Again, this makes sense:

Better:       Set:   E    F    G
         Shingles:  400  826  207

              Set:   H    I
         Shingles:   62   17

              Set:   J    K    L
         Shingles: 3042 3042 1088

Worse:        Set:   A    B    C
         Shingles:  316   19  258

              Set:   M    N    O
         Shingles:  902 9391   76

Looking just at resemblance and Dice's coefficient, we can first rule out those measures not of interest:

• Values on the diagonal.
• Values below the diagonal, as the tables are symmetric.
• Measures between identical sequences J and K.

So, the eleven true positive matches of interest are:
AB, AC, BC, EF, EG, FG, HI, JL, MN, MO, NO
and the true negative matches of interest are the remaining 80 pairs.

The thresholds could be adjusted to optimize the error rates for the resemblance and Dice's coefficient classification. Study of the tables shows the following performances with varying thresholds. The maximum total correct classifications and the crossover points are highlighted.

Resemblance:

Dice's Coefficient:

Limitations of This Approach — Computational Complexity and Botnets

The first problem that comes to mind is the computational complexity of applying this to large collections of attack sequences. The eventual goal would be to answer for a newly observed sequence, Does this sequence strongly resemble anything seen so far? That would require an approach based on a feature vector, so the only new computation would be the calculation of the new feature vector and a comparison to an existing catalog of observed attack signatures. Analysis using the other inter-document similarity measures would require calculation growing with the size of the existing data collection.

An unexpected problem arose when applying this this same sort of sequence extraction and analysis to a new month's data. That data included an attack by a botnet of 707 hosts in which only guesses for the root password were attempted.

Start:    Nov 19 15:00:42
End:      Nov 21 03:18:36
Duration: 36:17:54
Guesses:  2666

Typical guesses were separated by 20 to 80 seconds from the one before. With two exceptions, no botnet members made two consecutive guesses. A gnuplot histogram of the inter-guess times shows the distribution.

Click here to see the list of botnet members and the inter-attack timing.

The SSH daemon and the PAM modules it uses only log the event of a failure. Sniffing packets can show the host-to-host handshaking, in which every client identified itself as:
SSH-2.0-libssh-0.2,
immediately suggesting that this was a botnet, all the members running C code compiled against the libssh API. However, once the hosts attempt host-to-host authentication (which, of course, fails in this case) and then negotiate ciphers and a session key, you see nothing else useful in the raw network traffic.

The trick is to attach to the SSH server process with strace and observe the I/O at the application level.

First, find the process ID of the listening SSH server. Run this command:
lsof -i tcp:ssh
and look for the PID of the process marked LISTEN.

Second, if that PID were 12345, run this command as root:
strace -f -e 'read,write' -p12345

This page claims to list "The Top 500 Worst Passwords of All Time", but there is no explanation of where they got that data. Since admin isn't even on the list despite being the default password on lots of network gear, I don't think the list is very authoritative. But it's kind of interesting.

Coming in mid-attack, I saw an alphabetical list of names and words being used as root password guesses:
    dominique
    domino
    dontknow
    doogie
    doors
    dork
    doudou
    doug
    downtown
    dragon1
    driver
and so on. Some further analysis showed that this sequence had been used as as target logins for password guesses within two earlier attacks, click here to see the Linux/UNIX command-line trick to easily find these. Those attacks were separated by 77 days, and the two attacking hosts were in Brazil and Germany:

The only differences within the sequences from 200.213.105.90, in Brazil, on March 16, was early termination. That is, compared to the 200.213.105.90->i192 sequence of 2,854 logins, the others were identical until they terminated slightly before the end. And that longest sequence probably terminated itself early, stopping at virago within one of several alphabetical subsequences:
..., vicki, vicky, victor1, vikram, vincent1, violet, violin, virago

Comparing the 200.213.105.90->i192 sequence to the sequences from the attack from 85.114.130.49, in Germany, on June 1, we see that they are basically the same sequences. The differences are early termination plus deletion of a few entries mid-list, probably due to timeouts during that attack.

That 200.213.105.90->i192 sequence is the most complete version of this list seen in two attack sequences widely separated in time and space, click here to see that list.

That sequence appears to be a list of likely passwords rather than logins. Just look at the first 10:
12345 abc123 password computer 123456 tigger 1234 a1b2c3 qwerty 123
Users usually aren't assigned identities like those, but they are the sorts of passwords users would prefer!

Also recall that the target hosts are shown here as the first letter of the host name followed by a 3-digit representation of the last octet of the IP address. The first attack sequence started in numerical order if we disregard one entry transposed by one position, suggesting that the attacks were driven by a list or range of IP addresses or a CIDR representation. That makes sense, as none of the hosts are public web servers or other prominent hosts. The starting order of the second attack makes less sense, as the target hosts are ordered by neither host name nor IP address. The organization's DNS servers do not allow zone transfers, so an attacker could not have obtained a list of host names that way. Also, some of the systems involved are used only as servers, and so they would not have shown up as clients in some web server's logs. The only thing that really makes sense is for these attacks to have been controlled by ranges of IP addresses.

The timing between the starts of the individual sequences also varied between the two attacks. Maybe the order and start times were randomized by the attack software.

A similar attack from a larger botnet was seen when analyzing data from two servers at a web hosting company.

These attacks show the impracticality of purely automated analysis. My analysis script can generate an HTML file describing a month's probes against a system. But the file grows proportionally when one botnet attack appears to be hundreds of one-guess attacks. What had been an HTML file of a few hundred kilobytes grows into the tens of megabytes with the addition of all those tables.

It seems that human judgement is needed to tell the difference between an unaggressive botnet and random one-guess attacks. More difficult yet is the situation where a more aggressive single-attacker sequence happens to fall in the middle of a botnet attack. Several did, in this case, but they were spotted by seeing how many consecutive guesses were made by each host. This can be done with use of a simple uniq | sort -n command sequence. Given an average inter-guess timing in the tens of seconds for the botnet versus two to four seconds for a typical single host, the non-botnet hosts stood out and could be removed from consideration.

Attack #1:
Start:           Nov 14 18:35:24     Nov 14 18:35:24
End:             Nov 16 20:52:18     Nov 16 20:52:16
Duration:        50:16:54            50:16:52
Guesses made:    882                 872
Unique logins:   85                  83
Botnet members:  306                 309
Target host:     c193                i192
Attacking hosts in common: 303

Attack #2:
Start:           Nov 18 07:32:06     Nov 18 07:32:06
End:             Nov 18 18:41:57     Nov 18 18:41:57
Duration:        03:09:51            03:09:51
Guesses made:    142                 144
Unique logins:   42                  42
Botnet members:  101                 102
Target host:     c193                i192
Attacking hosts in common: 101

Motivated to look for signs of botnets, two more attacks were spotted against other hosts during that same month! Those attacks seem to have been perpetrated by the same botnet, as there is a large overlap in their member hosts. The attacks were rather different than those of the first botnet, as they attempted guesses for a number of accounts in addition to root.

Logins attacked in sequence #1:

admin allison amanda andy at backup backup1 cathy cecilia charles christoph cookie cpanel crystal cs data ed frances ftp ftpuser games glenn irc jacki james jan jennifer joe john jon justin kevin kim knoppix ldap leonard lillian majordom mark martin matt melissa michel murphy mysql nagios nikki office oracle paul porter postgres postgress qmail rex richard robby robert root samba security steve test test1 test2 test3 test4 todd tomcat ts ts2 web0 web1 web2 web3 web4 web5 web6 web7 webmaster webmin wilson yolanda zach zope

Logins attacked in sequence #2:

amavis amavisd apache clamav contacts cyrus demo demo1 demo3 dhcpd fetchmail games gnats guest lp mail news spam squid student stunnel suse-ncc tcpdump test3 user user1 vscan web0 web1 web10 web11 web12 web13 web2 web3 web4 web5 web7 web8 web9 www wwwrun

Comparing the sets of attacking hosts (the botnet members), 94 were seen in both attack sequences. As seen in this table, the distribution of activity varied between the two attacks. The numbers in the table record the number of password guesses, individual attacks or probes, and does not necessarily reflect the number of unique botnet members in that country.

Some stereotypes are reinforced in that table: the high rankings of the U.S. and Europe. Others are dashed: the surprisingly low rankings of China, Hong Kong, and Japan.

Within each of the two attacks, the distributions of probe sources seen on the two target hosts were almost identical. The slight differences were probably due to timeouts leading to abandoned attempts.

For more details, extracts of the logs are available. These show the full sequence of guesses made by each botnet, showing the timestamp, login guessed, and botnet member making that guess:
• Attack #1, target = c193
• Attack #1, target = i192
• Attack #2, target = c193
• Attack #2, target = i192

The timing was less aggressive in these smaller attacks, as shown by the inter-attack timing histograms below. Attacks in the first and second sequences were spaced by 100-200 seconds and about 200 seconds, respectively.

To generate those histograms of inter-attack timing, start with a file "botnet-times" containing one inter-attack time per line:

% awk '{print $1}' botnet-list > botnet-times
% cat > histo.gnuplot << EOF
set style data line
set boxwidth 3
set xlabel "Seconds between guesses"
set ylabel "Number of events with this delay"
set xrange [0:150]
set key off
set term png
set output 'timing-histogram.png'
bw = 1
bin(x,width) = width*floor(x/width)
plot 'botnet-times' using (bin($1,bw)):(1.0) smooth freq with boxes
EOF
% gnuplot histo.gnuplot

Other Work

"Entropy estimation of symbol sequences"
Thomas Schuermann and Peter Grassberger
Abstract:
"We discuss algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations. In particular, we consider algorithms which estimate h from the code lengths produced by some compression algorithm. Our interest is in describing their convergence with sequence length, assuming no limits for the space and time complexities of the compression algorithms. A scaling law is proposed for extrapolation from finite sample lengths. This is applied to sequences of dynamical systems in non-trivial chaotic regimes, a 1-D cellular automaton, and to written English texts."

"Syntactic Clustering of the Web"
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig, SRC Technical Note 1997-015
Abstract:
"We have developed an efficient way to determine the syntactic similarity of files and have applied it to every document on the World Wide Web. Using this mechanism, we built a clustering of all the documents that are syntactically similar. Possible applications include a "Lost and Found" service, filtering the results of Web searches, updating widely distributed web-pages, and identifying violations of intellectual property rights."

"Finding Similar Files in a Large File System"
Udi Manber, TR 93-33, University of Arizona
Abstract:
"We present a tool, called sif, for finding all similar files in a large file system. Files are considered similar if they have significant number of common pieces, even if they are very different otherwise. For example, one file may be contained, possibly with some changes, in another file, of a file may be a reorganization of another file. [....]"

"Clustering and Categorization Applied to Cryptanalysis"
Claudia Oliveira, José Antônio Xexéo, Carols André Carvalho, Cryptologia v30, n3, pp 266-280, 2006
A nice discussion of a generalized clustering approach and its application to cryptanalysis.

"Stylistic Text Classification Using Functional Lexical Features"
Shlomo Argamon, Casey Whitelaw, Paul Chase, Sobhan Raj Hota, Navendu Garg, and Shlomo Levitan, Journal of the American Society for Information Science and Technology vol 58, no 6, pp 802-822, 2007
Abstract:
"Most text analysis and retrieval work to date has focused on the topic of a text; that is, what it is about. However, a text also contains much useful information in its style, or how it is written. This includes information about its author, its purpose, feelings it is meant to evoke, and more. This article develops a new type of lexical feature for use in stylistic text classification, based on taxonomies of various semantic functions of certain choice words or phrases. We demonstrate the usefulness of such features for the stylistic text classification tasks of determining author identity and nationality, the gender of literary characters, a text's sentiment (positive/negative evaluation), and the rhetorical character of scientific journal articles. [....]"

"Evaluating Internet Resources: Identity, Affiliation, and Cognitive Authority in a Networked World"
J. W. Fritch and R. L. Cromwell (yes, that's me), JASIST (Journal of the American Society of Information Science and Technology), vol. 52, no. 6 (2001), pp 499-507.

In addition to referencing our JASIST paper, Argamon et al also list a number of other papers describing work on author attribution and profiling:

• "Gender, Genre, and Writing Style in Formal Written Texts", Argamon, Koppel, Fine, and Shimony, Text, 23(3), 321-346, 2003.
• "Outside the Cave of Shadows: Using Syntactic Annotation to Enhance Authorship Attribution", Baayen, Halteren, and Tweedie, Literary and Linguistic Computing, 7, 91-109, 1996.
• "Computation into Criticism: A Study of Jane Austen's Novels and an Experiment in Method", J.F. Burrows, Clarendon Press, Oxford, England, 1987.
• "Language and Gender Author Cohort Analysis of E-mail for Computer Forensics", de Vel, Corney, Anderson, and Mohay, in Proceedings of the Digital Forensic Research Workshop, Syracuse, NY, pp 7-9, 2002.
• "Visualization of Literary Style", Kjell and Frieder, in Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Chicago, IL, pp 656-661, 1992.
• "Authorship Studies/Textual Statistics", McEnery and Oakes, in Handbook of Natural Language Processing, Dale, Moisl, and Somers, editors, Dekker, Philadelphia, 2000.
• "Inference and Disputed Authorship: The Federalist", Mosteller and Wallace, Addison-Wesley, Reading MA, 1964.
• "Automatic Text Categorization in Terms of Genre, Author," Stamatatos, Fakotakis, and Kokkinakis, Computational Linguistics, 26(4), pp 471-495, 2000.
• "A Probabilistic Similarity Metric for Medline Records: A Model for Author Name Disambiguation", Torvik, Weeb, Swanson, and Smalheiser, Journal of the American Society for Information Science and Technology, 56(2), pp 140-158, 2005.