domain: info math

text:
Laurent Bienvenu
email: laurent.bienvenu@computability.fr

Benoit Monin
email: benoit.monin@liafa.univ-paris-diderot.fr

Alexander Shen
email: alexander.shen@lirmm.fr

Benoît Monin

Algorithmic Identification of Probabilities Is Hard

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Learnability of sequences

The study of learnability of computable sequences is concerned with the following problem. Suppose we have a black box that generates some infinite computable sequence of bits X = X(0)X(1)X(2), . . . We do not know the program running in the box, and want to guess it looking at finite prefixes X n = X(0) . . . X(n -1) for increasing n. There could be different programs that produce the same sequence, and it is enough to guess one of them (since there is no way to distinguish between them looking at the output bits). The more bits we see, the more information we have about the sequence. For example, it is hard to say something about a sequence seeing only its first bit 1, but looking at the prefix 110010010000111111011010101000 one may observe that this is a prefix of the binary expansion of π, and guess that the machine inside the box does exactly that (though the machine may as well produce the binary expansion of, say, 47627751/15160384).

The hope is that, as we gain access to more and more bits, we will eventually figure out how the sequence X is generated. More precisely, we hope to have a computable function A such that for every computable X, the sequence A(X 1), A(X 2), A(X 3), . . . converges to a program (=Turing machine) that computes X. This is referred to as identification in the limit, and can be understood in two ways:

-Strong success: for every computable X, the above sequence converges to a single program that produces X. -Weak success: for every computable X, all but finitely many terms of the above sequence are programs that produce X (may be, different ones).

The first type of success is often referred to as exact (EX) and the second type as behaviorally correct (BC). Either way, such an algorithm A does not exist in general. The main obstacle: certain machines are not total (produce only finitely many bits), and distinguishing total machines from non-total ones cannot be done computably. (If we restrict ourselves to some decidable class of total machines, e.g., primitive recursive functions, then exact learning is possible: let A(u) be the first machine in the class that is compatible with u.) We refer the reader to [START_REF] Zeugmann | Learning recursive functions: a survey[END_REF] for a detailed survey of learnability of computable functions.

Learnability of probability measures

Recently, Vitanyi and Chater [START_REF] Vitanyi | Algorithmic identification of probabilities[END_REF] proposed to study a related problem. Suppose that instead of a total deterministic machine, the black box contains an almost total probabilistic machine M . By "almost total" machine we mean a randomized algorithm that produces an infinite sequence with probability 1. The output distribution of such a machine is a computable probability measure µ M over the space 2 ω of infinite binary sequences. Again, our ultimate goal is to guess what machine is in the box, i.e., to give a reasonable explanation for the observed sequence X. For example, observing the sequence 000111111110000110000000001111111111111 one may guess that M is a probabilistic machine that starts with 0 and then chooses each output bit to be equal to the previous one with probability 4/5 (so the change happens with probability 1/5), making all the choices independently.

What should count as a good guess for some observed sequence? Again there is no hope to distinguish between some machine M and another machine M that has the same output distribution µ M = µ M . So our goal should be to reconstruct the output distribution and not the specific machine.

But even this is too much to ask for. Assume that we have agreed that some machine M is a plausible explanation for some sequence X. Consider another machine M that starts by tossing a coin and then (depending on the outcome) either generates an infinite sequence of zeros or simulates M . If X is a plausible output of M , then X is also a plausible output for M , because it may happen (with probability 1/2) that M simulates M .

A reasonable formalization of 'good guess' is provided by the theory of algorithmic randomness. As Chater and Vitanyi recall, there is a widely accepted formalization of "plausible outputs" for an almost total probabilistic machine with output distribution µ: the notion of Martin-Löf random sequences with respect to µ. These are the sequences which pass all effective statistical tests for the measure µ, also known as µ-Martin-Löf tests. (We assume that the reader is familiar with algorithmic randomness and Kolmogorov complexity. The most useful references for our purposes are [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF] and [START_REF] Li | An introduction to Kolmogorov complexity and its applications[END_REF].) Having this notion in mind, one could look for an algorithm A with the following property:

for every almost total probabilistic machine M with output distribution µ M , for µ M -almost all X, the sequence A(X 1), A(X 2), A(X 3), ... identifies in the limit an almost total probabilistic machine M such that X is µ M -Martin-Löf random.

Note that this requirement uses two machines M and M (more precisely, their output distributions): the first one is used when we speak about "almost all" X, and the second is used in the definition of Martin-Löf randomness. Here M may differ from M and, moreover, may be different for different X.

Vitanyi and Chater suggest that this can be achieved in the strongest sense (EX): the guesses A(X n) converge to a single code of some machine M . The main result of this paper says that even a much weaker goal cannot be achieved.

Let us consider a rather weak notion of success: A succeeds on X if there exists c > 0 such that for all sufficiently large n the guess A(X n) is a machine M such that X is µ M -Martin-Löf random with randomness deficiency4 less than c. So the machines A(X n) may be different, we only require that X is Martin-Löf random (with bounded deficiency) for almost all of them. (If almost all machines A(X n) generate the same distribution and X is Martin-Löf random with respect to this distribution, this condition is guaranteed to be true.)

Moreover, we require A to be successful only with some positive probability instead of probability 1, and only for machines from some class: for every machine M from this class of machines, A is required to succeed with µ M -probability at least δ > 0, for some δ independent of M .

Of course, this class should not be too narrow: if it contains only one machine M , the algorithm A can always produce a code for this machine. The exact conditions on the class will be discussed in the next section.

The proof of this result is quite involved. In the rest of the paper, we specify which classes of machines are considered, present the proof and discuss the consequences of this result.

Identifying measures

Background and notation

Let us start by providing some notation and background.

We denote by 2 ω the set of infinite binary sequences and by 2 <ω the set of finite binary sequences (or strings). The length of a string σ is denoted by |σ|.

The n-th element of a sequence X(0), X(1), . . . is X(n -1) (assuming that the length of X is at least n); the string X n = X(0)X(1) . . . X(n -1) is n-bit prefix of X. We write σ X if σ is a prefix of X (of some finite length).

The space 2 ω is endowed with the distance d defined by

d(X, Y ) = 2 -min{n:X(n) =Y (n)}
This distance is compatible with the product topology generated by cylinders

[σ] = {X ∈ 2 ω : σ X}
A cylinder is both open and closed (= clopen). Thus, any finite union of cylinders is also clopen. It is easy to see, by compactness, that the converse holds: every clopen subset of 2 ω is a finite union of cylinders. We say that a clopen set C has granularity at most n if it can be written as a finite union of cylinders [σ] with all σ's of length at most n. We denote by Γ n the family of clopen sets of granularity at most n.

The space of Borel probability measures over 2 ω is denoted by M(2 ω ). It is equipped with the weak topology. Several classical distances are compatible with this topology; for our purposes, it will be convenient to use the distance ρ, constructed as follows: For µ, ν ∈ M(2 ω ), let ρ n (µ, ν) (for an integer n) be the quantity

ρ n (µ, ν) = max C∈Γn |µ(C) -ν(C)| and then set ρ(µ, ν) = n 2 -n ρ n (µ, ν)
The open (resp. closed ) ball B of center µ and radius r is the set of measures ν such that ρ(µ, ν) < r (resp. ρ(µ, ν) ≤ r). Note that for any

ν in this open (resp. closed) ball, if C is a clopen set of granularity at most n, then |µ(C)-ν(C)| < 2 n r (resp. ≤ 2 n r).
The distance ρ makes M(2 ω ) a computable compact metric space; its computable points are called computable probability measures. A measure is computable if and only if it is the output distribution of some almost total probabilistic Turing machine (see, e.g., [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF]). Since M(2 ω ) is a computable metric space, one can define partial computable functions from some discrete space X (such as N) to M(2 ω ) via type-2 computability: a partial function f :⊆ X → M(2 ω ) is partial computable if there is an algorithm g that for every input x ∈ X enumerates a (finite or infinite) list of rational balls5 B 1 , B 2 ,. . . in M(2 ω ) such that B i+1 ⊆ B i , the radius of B i is less than 2 -i , and for every x in the domain of f , the list of enumerated balls is infinite and their intersection is the singleton {f (x)}. (We do not require any specific behavior outside the domain of f .) Let us introduce two non-standard, but important in this paper, pieces of terminology: having fixed the algorithm g associated to f , we write err(f (x)) < ε to mean that the list of balls produced by g on input x contains a ball of radius less than ε (the justification for this notation is that when such a ball is enumerated, should f (x) be defined, we know its value with error at most ε for the distance ρ). When the algorithm g on input x enumerates an empty list of balls, we say that g is null on input x.

We denote by K the prefix-free Kolmogorov complexity function. Given a computable measure µ, we call randomness deficiency of X with respect to µ the quantity

d(X|µ) = sup n log 1 µ([X n]) -K(X n) It is known that X ∈ 2 ω is µ-Martin-Löf random (or µ-random for short) if d(X|µ) < ∞.
This definition is slightly non-standard; to get a more standard one, one has to add µ as the condition (with some precautions). However, the above is enough for our purposes. We say that two measures µ and ν are orthogonal if there is a set having µ-measure 1 and ν-measure 0.

If B is a ball (open or closed) in M(2 ω ), with center µ and radius r, we define the estimated deficiency of X relative to B by

ed(X|B) = sup n log 1 µ([X n]) + 2 n r -K(X n)
Note that ed(X|B) is a lower bound for d(X|ν) for every ν ∈ B: we know that the value of ν([X n]) does not exceed µ([X n]) + 2 n r for every ν in the ball B. For a fixed pair (X, µ) we have lim B→µ ed(X|B) = d(X|µ): if d(X|µ) is large, one of the terms (for some n) is large, and the corresponding term in ed(X|B) is close to it if B has small radius and contains µ.

Sometimes in the paper we will use the notation ed(X|A(σ)). By this we mean the supremum of ed(X|B) over all balls B output by A on input σ.

The next lemma will be useful in the sequel.

Lemma 1 (Randomness deficiency lemma). Let B ⊆ M(2 ω ) be a ball of center µ (rational measure) and rational radius not exceeding r, and let C be a clopen set of granularity at most n. Then for all X ∈ C:

ed(X|B) ≥ log µ(X n) µ(X n) + 2 n r -log µ(C) -K(C, µ, r, n) -O(1)
Proof. Knowing C, µ, r, n, one can build a prefix-free machine which associates to every string σ of length n such that [σ] ⊆ C a description of size -log µ(σ) + log µ(C), so that indeed

σ 2 -(-log µ(σ)+log µ(C)) = 1 µ(C) σ µ(σ) = 1
where the sums are taken over those σ such that [σ] ⊆ C. This shows that for every such σ of length n, K(σ) ≤ -log µ(σ)

+ log µ(C) + K(C, µ, r, n) -O(1).
Applying the definition of ed, we get, for all

X ∈ C ed(X|B) ≥ log 1 µ([X n]) + 2 n r -K(X n) ≥ log 1 µ(X n) + 2 n r + log µ(X n) -log µ(C) -K(C, µ, r, n) -O(1) ≥ log µ(X n) µ(X n) + 2 n r -log µ(C) -K(C, µ, r, n) -O(1)

The main theorem

Now we return to the formulation of our main result. The learning algorithm is a partial computable function A :⊆ 2 <ω → M(2 ω ); it gets the prefix X n of a sequence X and computes (in type-2 sense) some measure A(X n). (Such a computable function can be converted into an algorithm that, given an input string, produces a program that computes the output measure, and vice versa.)

We say that A BC-succeeds on a sequence X ∈ 2 ω if A(X n) outputs the same computable measure µ for all sufficiently large n, and X is Martin-Löf random with respect to µ. This is a weaker requirement that exact (EX) success mentioned above: the algorithm is obliged to produce the same measure (for almost all n), but is not obliged to produce the same machine. Our main result, in its weak form, says that this goal cannot be achieved for all sequences that are random with respect to some computable measure:

Theorem 2. There is no algorithm A that BC-succeeds on every sequence X which is random with respect to some computable measure.

As we have discussed, we prove a stronger version of this result-stronger in three directions.

First, we require the learning algorithm to succeed only on sequences that are random with respect to measures in some restricted class, for example, the class of Bernoulli measures (the main particular case considered by Chater and Vitanyi).

Second, for each measure µ in this class we do not require the algorithm to succeed on all sequences X that are µ-Martin-Löf random: it is enough that it succeeds with some fixed positive µ-probability (a weaker condition).

Finally, the notion of success on a sequence X is now weaker: we do not require that the algorithm produces (for all sufficiently long inputs) some specific measure, asking only that it gives 'good explanations' for the observed sequence from some point on. More specifically, we say that an algorithm A BD-succeeds (BD stands for 'bounded deficiency') on some X, if for some c and for all sufficiently large n the measure A(X n) is defined and X is random with deficiency at most c with respect to this measure. Clearly BC-success implies BD-success. (Note that in our definition the randomness deficiency depends only on the measure but not on the algorithm that computes it.)

We now are ready to state our main result in its strong form.

Theorem 3. Let M 0 be a subspace of M(2 ω ) with the following properties: and let δ > 0. Then there is no algorithm A such that for every computable µ ∈ M 0 , the µ-measure of sequences X on which A BD-succeeds is at least δ.

-M 0 is
The notion of an recursively enumerable closed set is standard in computable analysis, see [Wei00, Definition 5.1.1].

Note that the hypotheses on the class M 0 are not very restrictive: many standard classes of probability measures have these properties. Bernoulli measures B p (independent trials with success probability p, where p is a parameter in [0, 1]) are an obvious example; so there is no algorithm that can learn all Bernoulli measures (not to speak about all Markov chains). Let us give another interesting example: for every parameter p ∈ [0, 1], consider measure µ p associated to the stochastic process which generates a binary sequence bit-by-bit as follows: the first bit is 1, and the conditional probability of 1 after σ10 k is p/(k + 1). The class M(2 ω ) = {µ p : p ∈ [0, 1]} satisfies the hypotheses of the theorem.

Note also that these hypotheses are not added for convenience: although they might not be optimal, they cannot be outright removed. If we do not require compactness, then the class of Bernoulli measures B p with rational parameter p would qualify, but it is easy to see that this class admits an algorithm which correctly identifies each of the measures in the class with probability 1. The third condition is important, too. Consider the measures B 0 and B 1 concentrated on the sequences 0000 . . . and 1111 . . . respectively. Then the class M 0 = {pB 0 + (1 -p)B 1 | p ∈ [0, 1]} is indeed effectively compact, but it is obvious that there is an algorithm that succeeds with probability 1 for all measures of that class (in the most strong sense: the first bit determines the entire sequence). For the second condition we do not have a counterexample showing that it is really needed, but it is true for all the natural classes (it is guaranteed to be true if M 0 has a computable dense sequence).

The proof of the main theorem

The rest of the paper is devoted to proving Theorem 3. Fix a subset M 0 of M(2 ω ) satisfying the hypotheses of the theorem, and some δ > 0. In the sequel, by "success" we always mean BD-success.

For every algorithm A we consider the set of sequences on which it succeeds. We say that A is δ-good if this success set has µ-probability at least δ for every µ ∈ M 0 . We need to show that δ-good algorithms do not exist.

Let us introduce some useful notation. First, let

Succ(A, c, n) = X ∈ 2 ω : (X n) ∈ dom(A) ∧ d(X|A(X n)) ≤ c
be the set of X on which A achieves "local success" on the prefix of length n for randomness deficiency c. The success set is then c N n≥N Succ(A, c, n).

According to our type-2 definition, the algorithm computing A produces (for each input string) a finite or infinite sequence of balls (we assume that i-th ball has radius at most 2 -i ). We will write 'B ∈ A(σ)' to signify that on input σ this algorithm enumerates the ball B at some point. For any function f : 2 <ω → [0, 1] converging to 0, we define the set Prec(A, f, n) of points X which are 'precise enough' in the sense that A(X n) almost outputs a measure:

Prec(A, f, n) = {X ∈ 2 ω : err(A(X n)) < f (X n)}
(notice that Prec(A, f, n) is a clopen set because the membership of X in Prec(A, f, n) is determined fully by the first n bits of X). The specific choice of f (how 'precise' should be the output measure) is discussed later.

In contrast to Prec, we define the following "nullity" sets:

Null(A, N ) = X ∈ 2 ω : A(X n) is null for every n ≥ N .
Proposition 4 (Nullity amplification). Assume that A is a δ-good algorithm, N is an integer, η ≥ 0 is a real number and B is an open ball intersecting M 0 such that µ(Null(A, N )) ≥ η for all µ ∈ B∩M 0 . Then there is a non-empty ball B ⊆ B intersecting M 0 , an integer N ≥ N and a δ-good algorithm A such that µ(Null(A , N )) ≥ η + δ/2 for all µ ∈ B ∩ M 0 .

This proposition clearly shows that there can be no δ-good algorithm: if there were one, one could construct by induction (taking for the base case η = 0, N = 0, and B = any ball intersecting M 0 ) a sequence of δ-good algorithms A i , a nonincreasing sequence of balls B i intersecting M 0 , and a non-decreasing sequence of integers N i such that µ(Null(A i , N i )) ≥ i•(δ/2) for every µ ∈ B i ∩M 0 , which gives a contradiction for large i. Thus, all we need to do is prove this proposition.

Proof. Fix A, N , η and B as in the hypotheses of the proposition. For m ≥ N , define a decreasing sequence of effectively open sets U m by

U m = {µ | (∃n > m) µ(Prec(A, f, n)) > 1 -η -δ/2 }.
The first step of this proof consists in showing that if f is carefully chosen to tend to 0 fast enough, then only finitely many of the U m can be dense in B ∩ M 0 . The way we do this is by proving the following fact: if U m is dense in B ∩ M 0 for some m, then for every B ⊆ B intersecting M 0 , one can effectively find B ⊆ B intersecting M 0 such that for all µ ∈ B , µ(Succ(A, n, n)) < 7δ/8 for some n ≥ m ≥ N .

This would yield a contradiction since this would allow us to construct a computable sequence of decreasing balls B m , all intersecting M 0 , where all µ ∈ B m would be such that µ(Succ(A, n, n)) < 7δ/8 for some n ≥ m, and thus the intersection of the B m would be a computable measure µ * -belonging to M 0 by closedness of M 0 -for which the success set of A has µ * -measure at most 7δ/8, a contradiction.

The definition of f on strings of length n will depend on a "large enough" parameter s = s(n) which we will define later as a computable function of n. Suppose s has already been chosen. We shall first define in terms of s an important auxiliary computable function L. It is computed as follows. For a given n, let ε = min(2 -n • δ/4, r) where r is the radius of B.

First, we effectively find k(ε) rational balls

D 1 , D 2 , • • • D k(ε)
, all intersecting M 0 , whose union covers M 0 and for any ball of radius at least ε, one of the D i is contained in this ball. (To do this, enumerate all balls with rational center and radius smaller than ε/3. By effective compactness of the space of measures M(2 ω ) and since M 0 is effectively closed, one can find a finite number of them, call them D 1 , D 2 , . . . , D k(ε) , which cover M 0 entirely. Now, let A be a ball of radius at least ε intersecting M 0 and µ its center. Since µ is at distance ε/3 of some measure ν ∈ M 0 . But the D i 's cover M 0 , so ν belongs to some ball D i , and by the triangular inequality, every member of D i is at distance at most 2ε/3 of µ, hence D i is contained in A).

Then, inside each ball D i , we effectively find 2 s rational measures ξ

(i) 1 , . . . , ξ (i) 2 s
and pairwise disjoint clopen sets

V (i) 1 , . . . , V (i)
2 s such that ξ

(i) j (V (i) j ) > 1 -δ/8
. To see that this can be done, observe that the conditions 'ξ 1 , . . . , ξ s ∈ B', 'the V i are disjoint', and 'ξ i (V i ) > 1 -ε for all i' are all Σ 0 1 -conditions. Therefore, all we need to argue is that such measures and clopen sets exist. By our assumption on M 0 , let ξ 1 , . . . , ξ s be pairwise orthogonal measures inside B. By definition, this means that for every pair (i, j) with i = j, there exists a set S i,j ⊆ 2 ω such that ξ i (S i,j ) = 1 and ξ j (S i,j ) = 0. For each i, let S i = j =i S i,j . One can easily check that ξ i (S i ) = 1 for all i and ξ i (S j ) = 0 when i = j. The measure of a set is the infimum of the measures of open sets covering it. Therefore, for each i there is an open set U i covering S i such that ξ j (U i ) ≤ 2 -s-1 ε for i = j (and of course, ξ i (U i ) = 1 for all i). Now we use the fact that the measure of an open set is the supremum of the measures of the clopen sets it contains. Therefore, for each i there exists a clopen set

U i ⊆ U i such that ξ i (U i ) ≥ 1 -ε/2 (and of course ξ i (U j ) ≤ 2 -s-1 ε for i = j). Now V i = U i \ j =i U j for each i is a clopen set of ξ i -measure at least 1 -ε/2 -2 s • 2 -s-1 ε = 1 -ε. The pairwise disjointness of the V i is clear from their definition.
Compute the maximum of the granularities of all the clopen sets V (i) j for i ≤ k(ε) and j ≤ 2 s and denote this maximum by L(n).

Suppose now that for every non-empty B ⊆ B intersecting M 0 , there exists some µ ∈ B and some n,

µ(Prec(A, f, n)) > 1 -η -δ/2
for some measure µ ∈ B and some n ≥ N . Set again ε = min(2 -n • δ/4, r) and compute a family D 1 , D 2 , • • • D k(ε) intersecting M 0 and whose union covers M 0 so that for any ball B of radius at least ε, there is some D i ⊆ B.

Recall that

Prec(A, f, n) is a clopen set of granularity n. Thus, if ρ(ν, µ) < 2 -n • δ/4, then ν(Prec(A, f, n)) > 1 -η -δ/2 -δ/4 = 1 -η -3δ/4.
And thus, by definition of the D i , there exists i such that for all ν ∈ D i , ν(Prec(A, f, n)) > 1 -η -3δ/4. Moreover, such an i can be found effectively knowing Prec(A, f, n) and δ. Fix such an i and set D = D i . Now consider the behaviour of the algorithm A on all possible strings σ of length n. On some of these strings, the algorithm does not achieve precision f (σ); we ignore such strings. On some others, A(σ) achieves precision f (σ) and thus returns a sequence containing some ball A of radius less than f (σ). Call A 1 , ..., A t all such balls (obtained by some A(σ) with σ of length n). Note that t ≤ 2 n . Let α 1 , ..., α t be the centers of these balls, and consider their average β = (1/t) i≤t α i . Since the V i are disjoint and there are 2 s -many of them, by the pigeonhole principle, there exists some j such that β(V j ) ≤ 2 -s , and thus α i (V j ) ≤ t • 2 -s ≤ 2 n-s for all i. Fix such a j and set V = V j , and ξ = ξ j .

Recalling that the granularity of V is at most L(n), we can apply the randomness deficiency lemma, we have for all X ∈ V :

ed(X|A(X n)) ≥ log α i (X L(n)) α i (X L(n)) + 2 L(n) f (X n) -log α i (V ) -K(V, n, s(n)) -O(1)
where α i is the center of the ball of radius f (X n) enumerated by A(X n). And this finally tells us how the function f should be defined: we require that 2 L(n) f (X n) is smaller than α i (X L(n)), so as to make constant the first term of the right-hand-side. It seems to be a circular definition, but it is not the case: we can define f (σ) to be the first rational q we find such that A(σ) enumerates a ball of radius at most q and such that the center α of this ball is such that α(σ) > 2 L(|σ|) q. This makes f a partial computable function, which is fine for our construction. Note also that f (σ) can be undefined if A(σ) is a measure γ such that γ(σ) = 0, but we need not worry about this case because it automatically makes the algorithm fail on σ (because the γ-deficiency of any extension of σ is infinite). It remains to evaluate the Kolmogorov complexity of V . What we need to observe that K(V ) can be computed from Prec(A, f, n), which, being a clopen set of granularity at most n, has complexity at most 2 n+O(1) . Indeed, knowing this set, one can compute the open set of measures ν such that ν(Prec(A, f, n)) > 1 -η -3δ/4 and effectively find a ball D as above. Then, from D, the sequence of clopen sets V 1 , . . . , V 2 s can be effectively computed. Moreover, to choose the V as above, we need to know β, hence the sequence of measures α 1 , . . . α t . But these can also be found knowing Prec(A, f, n), by definition of the latter. Thus we have established that K(V ) ≤ 2 n+O(1) . Plugging all these complexity estimates in the above expression, we get ed(X|A(X n)) ≥ s(n) -n -K(s(n)) -O(1)

(1)

≥ s(n) -2 log(s(n)) -n -O(1) (2)
Thus, by taking s(n) = 2n + d for some large enough constant d, we get that ed(X|A(X n)) > n for all X ∈ V . But the clopen set V has ξ-measure at least 1 -δ/8, so by definition of the A i , A returns a ξ-inconsistent answer for deficiency level n on a set of ξ-measure at least 1 -η -3δ/4 -δ/8 of strings of length n. Note that this is a Σ 0 1 -property of ξ, so we can in fact effectively find a ball B intersecting M 0 on which this happens. For every ν ∈ B , A(σ) is null on a set of strings of ν-measure at least η (by assumption) and is inconsistent on a set of measure at least 1 -η -7δ/8, so Succ(A, n, n) has a ν-measure of at most 7δ/8, which is the contradiction we wanted. Now, we have reached our first goal which was to show that some U N is not dense in B ∩ M 0 for some N . Note that the U m are non-increasing so this further means that there is a ball B ⊆ B such that B ∩ M 0 does not intersect any of the U m for m ≥ N . By definition, this means that on any measure ν of that ball B , the algorithm does not reach precision f (σ) on a set of strings σ of ν-measure at least η + δ/2. Thus, it suffices to consider the algorithm A which on any input σ does the following: it runs A(σ) until A(σ) reaches precision f (σ). If this never happens, A (σ) remains null. If it does, then A (σ) returns the same list of balls as A(σ). Clearly the algorithm A is δ-good since for every σ in the domain of A, A (σ) = A(σ). But by construction our new algorithm A is such that ν(Null(A , N )) ≥ η + δ/2 for all ν ∈ B . This finishes the proof.

  effectively closed, i.e., one can enumerate a sequence of open balls in M(2 ω ) whose union is the complement of M 0 . -M 0 is recursively enumerable, i.e., one can enumerate the open balls in M(2 ω ) which intersect M 0 . every non-empty open subset of M 0 (i.e., a non-empty intersection of an open set in M(2 ω ) with M 0 ) contains infinitely many pairwise orthogonal computable measures.

See below about the version of the randomness deficiency function that we use.

We fix some natural dense set of finitely representable measures. Rational balls are balls of rational radius with centers in this set. Such balls can also be finitely represented.

Acknowledgements. This publication was made possible through the support of a grant from the John Templeton Foundation. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.


Huijin Jeong
email: jeonghuijin@gmail.com

Junho Choi

Chang Choi

Ilsun You
email: isyou@bible.ac.kr

Pankoo Kim
email: pkkim@chosun.ac.kr

A Design of Web Log Integration Framework using NoSQL

Keywords: Big Data, Security Log aggregation, Cloud computing, NoSQL, HBase

Webservice is a software technology as the representative method of information communication currently used to create a dynamic system environment that is configured to fulfill its users' needs. Therefore, analyzing log data that occurred at provision is being used as the significant basic data in webservice research. Thanks to development of Cloud computing technology, it has resulted in centralized points from which data is generated and data enlargement. A research is now implemented to create information from collecting, processing and converting flood of data and to obtain the new various items of information. Against this backdrop, it is justified that collection, storage and analysis of web log data in the existing conventional RDBMS system may be inadequate to process the enlarged log data. This research propose a framework which to integrate web log for storage using HBase, a repository of the Cloud computing-based NoSQL. In addition, data validation must be completed in the preprocess when collecting web log. The validated log is stored in the modeling structure in which takes features of web log into account. According to the results, introduction of NoSQL system is found to integrate the enlargement of log data in more efficient manner. By comparisons with the existing RDBMS in terms of data processing performance, it was proved that the NoSQLbased database had a superior performance.

Introduction

Webservice can be the most representative service in which a business and customers communicate each other. Analysis of web log data from its operation allows for reprocessing various information that include status of a system, popular service pages after being extracted into any contributing information to the operation [START_REF] Agosti | Web log analysis: a review of a decade of studies about information acquisition, inspection and interpretation of user interaction[END_REF]. Nonetheless, as Smart Phone penetration increases in recent times, this has made it possible to access to the service regardless of time and place, constantly increasing the amount of log. Because of this, it brings about the newlycoined word of Big Data [START_REF] Gu | Application of NoSQL Database in Web Crawling[END_REF]. There have been vigorous research efforts in various fields to derive different type of information from Big Data by the process of understanding [START_REF] Choi | Detecting Web based DDoS Attack using MapReduce operations in Cloud Computing Environment[END_REF][START_REF] Choi | A Design of Onto-ACM(Ontology based Access Control Model) in Cloud Computing Environments[END_REF][START_REF] Elkotob | Cross-Layer Design for Improved QoE in Content Distribution Networks[END_REF][START_REF] Han | Meaning and Prospects of IT Convergence Technology in Korea[END_REF][START_REF] Gonzalez-Miranda | An IoT-leveraged information system for future shopping environments[END_REF], analyzing and gathering. In general, the existing web log repository consists of RDBMS. However, due to data enlargement, there are many difficulties to manually analyze web log and efficiently manage the service. RDBMS is not enough to process such gigantic data completely. The most representative technology that overcomes the incompetence is referred to as a distributed database or NoSQL. The most comparative advantages with NoSQL include that it supports for the horizontal expansions which enable massive data to be processed to overcome the limitations. In addition, it has strength in not using schema that presents a relationship data hold. As a result, a web log with different structures can smoothly be replaced with a log of the new formation [START_REF] Oliner | Advances and challenges in log analysis[END_REF]. The propose framework is a formalized one that fulfills the objective for collecting, storing and analyzing the massive web log data using HBase, a repository of NoSQL data in effective manner. Under the assumption that different web logs are integrated, a Cloud computing environment was considered, and a web log which had little effect on the existing system at storage and at the same time was configured to function for collection in real time was through preprocessing for eliminating unnecessary data after taking field structures into account. Later, data modeling structure for NoSQL environment was designed in order to store data. To verify the framework that is being proposed, it checked whether the massive web log data was more speedily processed using Wikipedia Accesslog Dataset [8] than in the previously used RDBMS. the reminder of the research is organized as follows: Chapter 2 it describes NoSQLbased log integration with comparisons between its features and log repository. Chapter 3 describes a preprocessing in a way that efficiently integrate a web log with the propose web log integration framework as well as a HBase-based modeling structure for integration. In chapter 4 an experiment of data processing speed and its results, as a solution that is proposed in chapter 3 are described. In the final chapter 5 it ends with conclusions and future research directions.

Related Works

Log data refers to recording information that includes sequential events occurred in system operation as well as details of operation in system or on network [START_REF] Herrerias | Log Analysis Towards an Automated Forensic Diagnosis System[END_REF]. Logs can be classified into operating system, network packet logs, and internet access record log. The existing RDBMS is designed with the standards of integrity and consistency of data, and it stores log data. RDBMS has an advantage in that it designs a table with normalized schema, proving join functions and with data expression opened. In contrast, the formalized schema structure has a significant difficulty in database expansions as it is not proper for the distributed processing environment. The supplementary database for expansions is developed and called as NoSQL(Not Only SQL) [START_REF] Srinivasan | Citrusleaf: A Real-Time NoSQL DB which Preserves ACID" The 37th International Conference on Very Large[END_REF][START_REF] Yi | A Survey on NoSQL Database[END_REF]. Right off the bat, NoSQL databases are unique because they are usually independent from Structured Query Language (SQL) found in relational databases. Relational databases all use SQL as the domain-specific language for ad hoc queries, while non-relational databases have no such standard query language, so they can use whatever they want. That can, if need be, include SQL [START_REF] Proffitt | When NoSQL Databases Are Yes Good For You And Your Company[END_REF]. In addition, it promises no perfect data consistency as the distributed storage database, by its characteristics, is focused on system provision even though a few database with data storage fail to respond [START_REF] Zhou | Dynamic Random Access for Hadoop Distributed File System[END_REF][START_REF] Kv Shvachko | HDFS Scalability: The limits to growth[END_REF]. There has been an ongoing research in which NoSQL is used as repository to effectively process the ever-growing data [START_REF] Borthakur | Apache Hadoop goes realtime at Facebook[END_REF]. NoSQL repository is divided into 4 types of data storage structures. Out of the four structures, HBase which opts for Column Model is usefully employed as the non-formalized data repository since it is capable of configuring multi-dimensional data based on columns [START_REF] George | HBase The Definitive Guide[END_REF]. Additionally, with employment of multi-slave method when configuring data nodes, it can flexibly be used in log integration. Choi et al. [START_REF] Bomin | The Method of Analyzing Firewall Log Data using MapReduce based on NoSQL[END_REF] had proposed security log analysis system with a NoSQL-based Mapreduce design that allowed firewall log data of this type with higher capacity to be collected and analyzed for integration, compared to RDBMS in terms of data processing performance and performed an analysis of the three attack patterns selected for evaluation. WEI et al. [START_REF] Yang | Patterns of Temporal Variation in Online Media[END_REF] had proposed a system using MongoDB, a repository of NoSQL in order to integrate a large number of networks monitoring log data. The research included a system design that took respective features of hardware layers and application layers in Cloud environment into consideration, Mapreduce programming that worked for log integration processing of massive log data in effective manner, and the improvement of log integrated architecture compared to RDBMS.

3

Hbase-BASED Log Integration

Proposed framework

The integration of security logs must not create any problems with the service, even if the security logs often occur such as, added, modified and deleted thing. Also, these security logs shall be no degradation in system performance through big security logs for detecting security incident. Therefore, this paper proposes an integrated system for good storage efficiency based on big log data. The Figure 1 is a framework of the proposed log integration system.

Fig. 1. Framework of the proposed log integration system

There are some preconditions for the configuration of log analysis system as follows:

(1) System operation and assuming that the attack happens.

(2) The web logs are created in the working service.

(3) Confirm to create the SSH Tunnel for transmission of web logs. (4) Transfer the variety web log data through web log collector.

(5) Perform the preprocessing of transferred web logs. [START_REF] Yi | A Survey on NoSQL Database[END_REF] The web log data are stored in HBase after preprocessing. [START_REF] Zhou | Dynamic Random Access for Hadoop Distributed File System[END_REF] The Extraction of pattern and information using stored web log data. (8) The extracted information is forwarded to the administrator. The first step is the collection of big logs for security logs integration. The security logs are transferred through SSH Tunnel and these are performed the preprocessing for removing of security threats. The reason of performing preprocessing are a step for removing unnecessary information after checking the data type of a heterogeneous logs. Also, there is needed for the model structure according to the type HBase after extracting necessary data. Finally, the integrated log storage when storing the common purpose is to integrate information.

Web log Preprocessing

The second step is the preprocessing of big log data. The preprocessing is classified the format type after checking the contents of log data. Also, this step is reduced the waste of storage space by removing unnecessary data. The type classification is very important because the structure of log data is different in occurred log data of heterogeneous services. The figure 2 is a framework of the preprocessing.

Fig. 2. Framework of the Preprocessing

There are some steps of preprocessing as follows:

(1) The variety web log data is occurred in service.

(2) To validate the input data as a web log.

(3) To classify through analysis of web log data. (4) To format by administrator using the characteristics of classified web log.

(5) The purified data is stored. (6) Repeat steps 1 to 6 times.

Data modeling for log integration

Amount of large scaled security logs which should be collected and stored under cloud computing environment is rapidly increasing. However, conventional collection method based on RDBMS storage can't afford the amount of security logs. In order to solve this problem, this paper proposes NoSQL-based method to collect and integrate security logs. NoSQL is more effective and rapid data storage than conventional RDBMS. Actually, data modeling based on relational database can performs freely queries through setting relation between tables. However, the design of data store model is needed because NoSQL does not support complex queries.

Fig. 3. Framework of log integration modeling

The Figure 3 is an example of the log integrated modeling framework. In figure 3, the Host table is entered 'Host' information using Row Key for data identification from LogData table in structure of the framework. Also, data is generated by the column such as, Log the type, log generation time, count and so on. The type of web log is classified by time in service. The time information is the most basic and important information for security incident or analysis of operational status because the data is stored by time sequentially. The Row key is defined 'DateTime' + 'Host' + 'Count' information in Log-Data table for log storage because of data query information such as, 'who', 'when', 'occurrence' and so on. DataLogInfo Column is classified Accesslog, Errorlog and Agentlog by log characteristics.

PERFORMANCE EVALUATION

Experimental environment

The performance evaluation of data input is performed between NoSQL and RDMS. RDMS is MySQL-5.1.69 because the most widely used. NosQL is used HBase-0.92.12 and it consists of master node, 4 data nodes, 50 Thread. The experiment is performed the data input performance using Wikipedia AccessLog data set [8]. The AccessLog data set based on Wikipedia are consists of 2 million, 5 million and 10 million elements.

The Figure 4 is the result of performance test. This test is processed number per hour and integration available amount based on web log.

EVALUATION

Fig. 4. RDBMS VS Hbase

In the results, 2mil is not large difference count but 5mil and 10mil can be clearly confirmed large difference count between HBase and MySQL. Also, the performance can be improved by increasing Data Node. If number of DataNodes is ensured sufficient, it seems possible additional performance boost.

Conclusion and Future works

As cloud computing technologies are rapidly advancing, cloud environment is significantly expanding. Although cloud environment provides users with convenience, prevention and detection of possible security invasion accidents is still unsolved problems. The most intrinsic method to prevent security invasion accident is to collect security logs for each system and then analyze them. This paper proposes NoSQL-based large capacity security log integration method for cloud security platform. Since cloud computing provides various services to users, a new web log that is different from existing one is likely to occur. Therefore, this paper proposes large scaled web log management to collect, store and integrate logs considering characteristics between heterogeneous machines. In the future, it needs the effective analysis methods based on heterogeneous web logs.

Acknowledgments

. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2013R1A1A2A10011667).


Igor Kotenko

Elena Doynikova
email: doynikova@comsec.spb.ru

Security Assessment of Computer Networks based on Attack Graphs and Security Events

Keywords: cyber situational awareness, security metrics, security metrics taxonomy, attack graphs, SIEM-systems

Security assessment is an important task for operation of modern computer networks. The paper suggests the security assessment technique based on attack graphs which can be implemented in contemporary SIEM systems. It is based on the security metrics taxonomy and different techniques for calculation of security metrics according to the data about current events. Proposed metrics form the basis for security awareness and reflect current security situation, including development of attacks, attacks sources and targets, attackers' characteristics. The technique suggested is demonstrated on a case study.

Introduction

Analysis and enhancement of the information security of the computer networks and systems is widely researched area. One of the essential aspects in this area is security evaluation that includes calculation of different security metrics. Calculation of security metrics is most relevant when it is solved in real-time (or near real-time) mode, which is specific to Security Information and Event Management (SIEM) systems [START_REF] Kotenko | The Ontology of Metrics for Security Evaluation and Decision Support in SIEM Systems[END_REF]. Obviously these metrics should be clear and valuable for security decisions. Currently there is a lot of investigations that consider different security assessment techniques and security metrics [1-6, etc.]. In the paper we aim to develop an approach intended for near real-time security metrics calculation. This approach should allow taking into account new security information and events that appear in the network operation process and fulfilling appropriate recalculation of security metrics. For this goal we developed the metrics taxonomy that considers the following aspects: recent research in the security metrics area; modeling of attacker steps as attack graphs; goals and characteristics of SIEM systems. For calculation of security metrics we use known and adopted techniques. On the base of these metrics, we determine current security situation, including existence of attacks, attacker skills and position, possible previous and future attacker steps and attack target. The main contribution of the paper is the developed metrics taxonomy and its application for security assess-ment of computer networks based on attack graphs. The key feature of the technique suggested is taking into account current security information and events.

The paper is organized as follows. Section 2 outlines main related works. Section 3 describes the common idea of the assessment technique and its stages. Section 4 presents case study and experiments for evaluating the security assessment technique. Conclusion analyzes the paper results and provides insight into the future research.

Related Work

Currently there is a multitude of security metrics taxonomies. We analyzed some of them and concluded that these taxonomies are defined according to the goals of the security assessment. For example, in [START_REF] Henning | Workshop on Information Security System, Scoring and Ranking ("Security Metrics[END_REF] three categories are outlined: technical, operational and organizational. In [START_REF] Vaughn | Information Assurance Measures and Metrics: State of Practice and Proposed Taxonomy[END_REF] two categories are considered: organizational and technical. Taxonomy suggested by NIST [START_REF] Swanson | Security Metrics Guide for Information Technology Systems[END_REF] includes three categories: management, technical and organizational, and 17 sub-categories. In [START_REF] Seddigh | Current Trends and Advances in Information Assurance Metrics[END_REF] the information assurance metrics taxonomy is defined. It includes three categories (security, quality of service, availability) and technical, organizational and operational metrics. From another hand, there are classifications of security metrics according to the way of their measurement and computation. In [START_REF] Idika | Characterizing and Aggregating Attack Graph-Based Security Metric[END_REF] the metrics are divided on primary and secondary. In [START_REF] Kheir | A Service Dependency Model for Cost-Sensitive Intrusion Response[END_REF] metrics are classified on the metrics that are calculated for the attack graph (used to define, for example, attacker skill level, attack potentiality) and for the service dependencies graph (implemented to determine, for instance, attack/response impact or response benefit). The Center for Internet Security divides metrics according to six business functions [4]: incident management, vulnerability management, patch management, application security, configuration management, and financial metrics. In [START_REF] Axelrod | Accounting for Value and Uncertainty in Security Metrics[END_REF] eight categories of metrics are differentiated according to the value type: existence (indicator of whether something exists); ordinal (subjective qualitative measure); score (numeric values for qualitative measure); cardinal (number); percentage; holistic (based on external data sources); value (consider value loss); uncertainty (include stochastic or probabilistic aspect).

Nevertheless, we have not found an appropriate taxonomy of metrics based on attack graphs applicable for security assessment in SIEM systems. Thus, we aimed to develop the appropriate taxonomy taking into account the next aspects: contemporary research in the security metrics area [9, 10, 16, etc.]; characteristics of the architecture of the security analysis component in the scope of the SIEM system (modeling of the attack sequences on the base of attack graphs [START_REF] Jahnke | Graph-based Metrics for Intrusion Response Measures in Computer Networks[END_REF][START_REF] Kotenko | A Cyber Attack Modeling and Impact Assessment Framework[END_REF][START_REF] Moore | Attack Modeling for Information Security and Survivability[END_REF][START_REF] Poolsappasit | Dynamic Security Risk Management Using Bayesian Attack Graphs[END_REF] and service dependencies [START_REF] Kanoun | Automated Reaction Based on Risk Analysis and Attackers Skills in Intrusion Detection Systems[END_REF][START_REF] Kheir | A Service Dependency Model for Cost-Sensitive Intrusion Response[END_REF]); different stages of security analysis (static and dynamic). We outlined the following categories: topological, attack, attacker, integral (system).

Topological characteristics can be defined from the network topology and the description of hosts [4,[START_REF] Mayer | Operational Security Risk Metrics: Definitions, Calculations, Visualizations. Metricon 2.0[END_REF]. They involve host parameters [START_REF] Mayer | Operational Security Risk Metrics: Definitions, Calculations, Visualizations. Metricon 2.0[END_REF], application characteristics [4], features about service dependencies [START_REF] Kanoun | Automated Reaction Based on Risk Analysis and Attackers Skills in Intrusion Detection Systems[END_REF][START_REF] Kheir | A Service Dependency Model for Cost-Sensitive Intrusion Response[END_REF], characteristics that consider information about the vulnerabilities and possible attacks [4]. Attack characteristics (such as attack potentiality/probability) are defined on the base of attack graphs [START_REF] Kanoun | Automated Reaction Based on Risk Analysis and Attackers Skills in Intrusion Detection Systems[END_REF]. Attacker parameters are related to possible attackers and are considered in [START_REF] Blakely | Cyberprints Identifying Cyber Attackers by Feature Analysis[END_REF][START_REF] Dantu | Network Risk Management Using Attacker Profiling[END_REF][START_REF] Kanoun | Automated Reaction Based on Risk Analysis and Attackers Skills in Intrusion Detection Systems[END_REF][START_REF]NMap reference[END_REF]. Integral (system) characteristics involve features that define common security estimations [START_REF] Dantu | Network Risk Management Using Attacker Profiling[END_REF]7,[START_REF] Kotenko | The Ontology of Metrics for Security Evaluation and Decision Support in SIEM Systems[END_REF][START_REF] Manadhata | An Attack Surface Metric[END_REF]. From another hand, important aspects in our classification are cost-benefit analysis and analysis of zero-day attacks. Cost-benefit analysis is usually used for decision support and involves cost metrics that define costs of impacts and responses [START_REF] Jahnke | Graph-based Metrics for Intrusion Response Measures in Computer Networks[END_REF][START_REF] Kheir | A Service Dependency Model for Cost-Sensitive Intrusion Response[END_REF]. For zero day attacks analysis, the metrics reflecting possible zero day attacks are used [START_REF] Ahmed | A Novel Quantitative Approach for Measuring Network Security[END_REF].

Security Assessment Technique

The component that implements the suggested security assessment technique is the part of the security evaluation system based on attack graphs [START_REF] Kotenko | A Cyber Attack Modeling and Impact Assessment Framework[END_REF]. The architecture of the component is presented in Fig. 1. The core of the component is the set of security evaluation algorithms for calculation of metrics. Other important subcomponent -Mapper -allows detecting attacker position on the base of security events and attack graph structure. Security evaluation component gets input data from different sources including: attack graph generator that builds attack graphs for the analyzed network; dependency graph generator that provides graph of the dependencies between the network services; and attack sequences generator that generates steps of the current attack on the base of the security alerts. Output data includes different security metrics according to the suggested taxonomy. Further output data is provided to the visualization system.

To describe the security assessment technique the following input details are used: (1) Test network with host characteristics and values of the topological metrics: Business Value, Criticality (including propagated criticality via service dependencies), etc.; (2) Attack graph that contains system vulnerabilities as vertexes and transitions between the vulnerabilities as arcs (these paths constitute threats). Possibility of transition from one vulnerability to another is defined by pre-and post-conditions of the vulnerabilities exploitation according CVSS [START_REF] Mell | A Complete Guide to the Common Vulnerability Scoring System Version 2[END_REF]; (3) Calculated unconditional prob-abilities for each node (in consideration that the attacker can implement all attack actions). Unconditional probabilities are defined on the base of the local conditional distributions for each node ,

1, : , … , ∏ |
, where -set of all parents of . Conditional probabilities of the transitions between nodes are defined on the base of CVSS access complexity of the vulnerability; (4) Calculated risk values for each critical host for attack graph level (considering attack probability and possible impact); ( 5) Security events that include information about the attacked host, privileges and/or impact on the host.

The security assessment technique includes the following stages: 1. Definition of the attacker position on the attack graph on the base of the information from the security event. It can be done on the base of the next steps: Define the list of the vulnerabilities for the host which is described in the security event; Select the vulnerabilities that lead to the privileges and\or impact described in the event; If only one vulnerability was selected, the next steps of the technique should be performed for the node that corresponds to the exploitation of this vulnerability; If multiple vulnerabilities were selected, the next steps of the technique should be performed for all possible nodes; If a vulnerability was not selected, then the event is defined as exploitation of the zero-day. 2. Determination of the attacker skill level on the base of information from the security event. The next steps should be performed for all nodes selected on the previous stage: Define the most probable path of the attacker to the current node (on the base of the Bayes theorem); In case of multiple paths with the same probabilities, consider them all in further calculations; Select vulnerabilities with the maximum CVSS access complexity [START_REF] Mell | A Complete Guide to the Common Vulnerability Scoring System Version 2[END_REF] for this path; Define the attacker skill level according to the access complexity as "High"/"Medium"/"Low". Quantitative values are defined: 0.7 -"High", 0.5 -"Medium", 0.3 -"Low" Attacker Skill Level; Define the probability of skills as (number of nodes with vulnerability with this access complexity)/(total number of steps in the path). 3. Calculation of the probabilities of the paths that go through the node that corresponds to the attacker position. On this step the next features should be considered: defined attacker skill level and that the probability of the compromise of this node is equal to 1. 4. Definition of the risks for the attack paths that go through the compromised node (based on the target asset criticality, attack impact and attack path probability). 5. Selection of the path with maximum value of risk. This path is selected as the most probable attack path and its end point should be selected as attacker goal.

As the result of the technique, we get the next output data: attacker skill level, attack path and attackers goal. Further this information is used for the decision support.

4

Case Study

Input Data Gathering

Let us consider the following input data used for the security assessment: topology of the test network (Fig. 2), values of the topological metrics, especially Criticality of the hosts (calculated on the previous assessment stage), attack graph, security events.

Host-1 and Host-2 are web-servers with critical web applications. External users of the local network are directed to the web-applications through Router-1 and Firewall-1 to Host-1 or Host-2. Authentication is needed to work with these applications. Authentication data is stored on the Authentication server. Critical data that the user get or add when working with applications is stored on Database server. The example of the user interface for the security evaluation system, which outlines the metrics values, is shown in Fig. 3 [START_REF] Kotenko | A Cyber Attack Modeling and Impact Assessment Framework[END_REF]. Common attack graph for the considered test case is presented in Fig. 4. Nodes of the attack graphs are defined as triple <Exploited vulnerability, Pre-conditions, Post-conditions>. Pre-conditions include privileges that are needed to exploit the vulnerability, Post-conditions are acquired privileges and impact. For each node of the attack graph the appropriate vulnerabilities (according to the NVD database) are represented. Color of the node is defined with vulnerability BaseScore according to the CVSS [START_REF] Mell | A Complete Guide to the Common Vulnerability Scoring System Version 2[END_REF] (yellow color -for the Medium score, red color -for the High score). For each node the probabilities that attacker can reach the node are calculated.

Fig. 3. Example of the user interface

For example, conditional probability on the node 1 in case of successful initialization of attack is equal to 0,61 (the access complexity of the CVE-2010-2990 is 0,61). Conditional probability on the node 6 in case of the success on the node 1 is equal to 0,71 (the access complexity of the CVE-2008-1436 is 0,71). Unconditional probability for the node 6 is defined as product of probabilities of successful states: 1 • 0,61 • 0,71 0,4331.

As was defined above the description of the security event should include information about the attacked host and acquired privileges and/or impact.

To illustrate the experiments in the paper, two types of attackers were defined: 1. Attacker with "Medium" attacker skill level. He (she) has external access and some information on the network topology. This attacker can use exploits of known vulnerabilities with "Medium" access complexity. His (her) goal is to get data from the database. The sequence of such actions is represented with yellow color. We define the following events for this case as example: event1 -malicious activity is detected on step 1, it contains the information on illegitimate admin access on the Firewall-3; event2 -malicious activity on step 2, it contains the information on illegitimate admin access on the Web-server. 2. Attacker with "High" attacker skill level. He (she) has external access and no information about network topology. This attacker can exploit a zero-day vulnerability. His (her) goal is to compromise web-application on Host-2. The sequence of such actions is outlined with red color. We define the following events for this case as example: event1 -malicious activity is detected on step 1, it contains the information about illegitimate admin access on the Firewall-1; event2 -malicious activity on step 2, it contains the information about illegitimate admin access on the Firewall-2; event3 -malicious activity is detected on step 3, it contains the information about illegitimate admin access on the Host-2; event4 -malicious activity is detected on step 4, it contains the information about violation of confidentiality, integrity or availability on the Host-2.

Security Assessment Implementation

Let us go through the steps of the technique suggested for the described test case: 1. Definition of the node of the graph which corresponds to the attacker position. For example, for the first scenario to detect the attacked node after event1 we determine all vulnerabilities on the Firewall-3 defined in the event and then select vulnerabilities that provide privileges/impact described in the event. For the first scenario it is still node '1'. 2. Calculation of the attacker skill level on the base of the security event. For the nodes defined on the previous stage, the previous attacker steps are defined, i.e. the attack sequence on the attack graph with the maximum probability value. For the first scenario after event1 there is only one possible previous node -external network, and only one exploited vulnerability -1. On the base of the performed steps the attacker skill level is a maximum access complexity of them. 3. Determination of the probabilities of the attack sequences that go through the node with attacker and definition of the attacker goal. For the first scenario, according to event1, new probabilities are calculated: the probabilities on the nodes 5-8 are decreased, as from the one hand they were influenced by the new knowledge about the attacker position, but from another -by new knowledge about attacker skills. Also probabilities of the attacks on the nodes 2, 16-81, 21-23 are decreased, because of the new knowledge about attacker skills. Thus, after the first security event we can suppose that attack goal is Database Server, but additional information is needed. Fig. 5 depicts appropriate probabilities after each defined security event for the first scenario. Fig. 6 outlines the same calculations made for the second scenario. 4. Definition of the risks of the attack sequences. On this step the Criticality values are considered. Cumulative risk values for the graph nodes are represented in Fig. 6 (with new events the risk on the attacker goal node increases). Output of the security assessment technique contains the following data: attack path with maximum risk value that defines the most probable attack sequence and attackers goal; the most probable previous attacker steps; attacker skills. These results allow making decision about the most efficient countermeasures. These experiments demonstrate the main possibilities of the suggested security evaluation system on security metrics calculation.

Conclusion

In the paper we suggested and analyzed the application of the security assessment technique for computer networks. It is oriented on near real time situation assessment, when we can monitor the current attacker position and his (her) path in the network, but have hard time limitations for calculations. We defined the set of security metrics and traced their changes after appearance of security events. On the example of the case study it was shown that probability and risk of the attacker path increases with new data and allows defining the track of the attacker in the system. The limitations of the paper volume do not allow discussing proposed system of security metrics and techniques of their calculation in details.

The future research will be devoted to further specification of the technique and extension of the experiments.

Fig. 1 -

 1 Fig. 1 -Architecture of the security evaluation component

  Requests from Host-1 and Host-2 are handled by Web-server first. Internal users have access to Web-server via Router-2 and Firewall-3. The parameters of the hosts for the test network are as follows: (a) External users -Microsoft Windows 7 64-bit, Apple ITunes 9.0.3, Microsoft Office 2007 SP1, Microsoft Internet Explorer 7; (b) Webserver -Windows Ftp Server 2.3.0, Windows Server 2008 for 32-bit Systems; (c) Database server -Apache Software Foundation Derby 10.1.3.1, phpMYAdmin 3.5.2.2, Oracle MySQL 5.5.25, Linux Kernel 2.6.27.33; (d) Host-1 и Host-2 -Red Hat JBoss Community Application Server 5.0.1, Windows Server 2008 R2 for x64-based Systems; (e) Firewall-1, Firewall-3 -Linux Kernel 2.6.27.33, Citrix ICA Client; (f) Firewall-2 -Novell SUSE Linux Enterprise Server 11 Service Pack 1 (with Netfilter),; (g) Authentication server -Novell SUSE Linux Enterprise Server 11 Service Pack 1, Novell eDirectory 8.8.1; Internal users -Apple Mac OS X Server 10.6.1, Apple iTunes 9.0.2 for Mac OS X, Microsoft Office 2008 Mac. Fig. 2 depicts the values of the host Criticality. It is calculated on the base of the Business Value of the hosts for the system and the dependencies between the network services. Criticality is a vector that includes three scores <Criticality of Confidentiality, Criticality of Integrity, Criticality of Availability>.

Fig. 2 .

 2 Fig. 2. Topology of the test network and Criticality values

Fig. 4 .

 4 Fig. 4. Attack graph with calculated probabilities

Fig. 5 .

 5 Fig. 5. Changes of attack probabilities after security events for the scenario 1

Fig. 6 .

 6 Fig. 6. Changes of attack probabilities after security events for the scenario 2

Acknowledgements. This research is being supported by grants of the Russian Foundation of Basic Research (13-01-00843, 13-07-13159, 14-07-00697, 14-07-00417) and the Program of fundamental research of the Department for Nanotechnologies and Informational Technologies of the Russian Academy of Sciences (contract #2.2).


Marcel Fourné
email: [fourne@internet-sicherheit.de

Kevin Stegemann
email: stegemann@internet-sicherheit.de

Dominique Petersen
email: petersen@internet-sicherheit.de

Norbert Pohlmann
email: pohlmann]@internet-sicherheit.de

Aggregation of Network Protocol Data Near Its Source

Keywords: Network Anomaly Detection, Botnet Detection, Network Flow Data Formats, Data Compression

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and Background

For Network Anomaly Detection as well as network based Botnet and Malware Detection (common umbrella term: NAD) the network traffic is their defining input. Any findings rely on the availability of large volumes of network data. The standard approach to get network data from Internet Service Providers (ISPs) is to simply request them for research or security purposes under a contract. A common problem emerges from the difference in bandwidth of big Internet exchanges compared to the bandwidth of common research laboratories.

The most common format for network flow data is called NetFlow, which was the basis for the more modern and standardized IPFIX. Since IPFIX is the future replacement for NetFlow, it can be expected to get widespread implementation in network routing equipment. The main target for this protocol is the transfer of data from an exporter to a collector.

When transmitting data for analysis, the most common formats in use today are NetFlow version 5 and raw PCAP files. Using NetFlow or IPFIX, the set of data to analyze is equally dependent on the supplier -ISPs etc. -so both have different problems. The first has -in its minimal form -only limited information for reliable detection of malicious activity and the second is not reasonable to transmit from live, high bandwidth data sources. A wider selection of records in NetFlow or IPFIX leads to more useful data, but in return raises the requirements for larger transmission bandwidth.

A possible workaround is compression of the bulk data using the DEFLATE or similar compression algorithms, but this only achieves modest improvements.

Related Work

There are projects using different approaches to NAD, including protocol headers [START_REF] Ahmad | Anomaly detection of ip header threats[END_REF], statistical detection [START_REF] Bykova | Detecting network intrusions via a statistical analysis of network packet characteristics[END_REF] and others. We will only name a few as a primer for the interested [START_REF] Deri | Design and implementation of an anomaly detection system: an empirical approach[END_REF][START_REF] Rossow | Sandnet: Network traffic analysis of malicious software[END_REF].

Bulk data compression was also demonstrated to lessen the strain on research ressources [START_REF] Politopoulos | Evaluation of compression of remote network monitoring data streams[END_REF], but other works [START_REF] Palmieri | A distributed approach to network anomaly detection based on independent component analysis[END_REF] could especially benefit from our proposal.

Most other research is done using already available NetFlow data using a minimal dataset [START_REF] Lakhina | Characterization of network-wide anomalies in traffic flows[END_REF][START_REF] Bilge | Exposure: Finding malicious domains using passive dns analysis[END_REF][START_REF] Bilge | Disclosure: detecting botnet command and control servers through large-scale netflow analysis[END_REF] and sometimes also direct packet captures [START_REF] Tegeler | Finding bots in network traffic without deep packet inspection[END_REF], but other flow data formats are also contestants for statistic approaches in finding anomalies. The main benefit of sampling flow data formats, by only transferring every N -th network packet is to be able to get information on Internet links which would otherwise saturate NAD systems is also their main disadvantage: Since not every packet gets reported, finding anomalies becomes a work of chance.

NetFlow [START_REF] Claise | Cisco systems netflow services export version 9[END_REF] in itself is widely available in commercial routing hard-and software, so NetFlow data are easy to collect and many data are extractable from NetFlow records. The data available from NetFlow is variable, so the least common denominator is the only guaranteed information set, all other reportable records are optional. This may hamper NAD research if probabilistic analysis has to be inserted to find common higher level protocol usage without having detailed records available [START_REF] Abt | Performance evaluation of classification and feature selection algorithms for netflow-based protocol recognition[END_REF]. Standardization of the NetFlow format has led to IPFIX [START_REF] Trammell | Bidirectional Flow Export Using IP Flow Information Export (IPFIX)[END_REF], which will see further adoption first in industrial use and therefore later in scientific literature using data in this format.

The general idea of Descriptors [START_REF] Petersen | Measuring and warning[END_REF] has been mentioned earlier, but their approach was based on time intervals alone, thus not allowing to detect parties connected to anomalous activity in network flows. This is not needed for simple alarms, but for precise detection of attack sources.

We propose a security flow data transfer format with aggregate network protocol data to reduce the need for bandwidth compared to other formats containing the same information without aggregation. The aim of this format is to enable analysis of high bandwidth network data sources at smaller bandwidth sites. The security information content has to be maximized, of course, else a NAD system would be hampered in its workings. We define the security information (SI) of the data using P (Information at the Producer), D (Data at a sensor) and Y (Result of aggregation) as The transport format Version 5 is structurally similar to common flow formats with the addition of so-called Descriptors, carrying the aggregate protocol data. Additional flow information can be added, e.g. labeling information, full packet size lists or the time distance of packets -called time difference list.

SI(Y ) ≤ SI(D) ≤ SI(P ) (1)
Of special note is the semantic approach in reducing the transferable network protocol data, since it relies on expert knowledge to implement aggregation plugins. They are as stable in their implementation details as the network protocol standards, so it would be combinatorically complex to implement all network protocols. It is in our best interest to implement a subset of most common network protocols instead of taking an "every last bit" approach, since very uncommon protocols only falsify the network view by very small and easily quantifiable percentages, so the Descriptors compress large amounts of data very well.

Fig. 2. Network setup comparing with and without Descriptor counting

We implemented the data aggregation not at a research laboratory, but onsite of the ISP to be able to extract network protocol data for detection right before transmitting the data to researchers. This can be seen as case 2 of Fig. 2, case 1 being the standard case, e.g. usage with plain IPFIX.

As seen on Fig. 2, the computer aggregating the network protocol data before the -ideally cryptographically secured -transmission is non-invasive to the core business of an ISP and can be fed with possibly filtered data coming from internal processes which are intended for data forwarding in other formats.

Our main input at the moment are raw PCAP files as well as direct network links, but structurally any well documented format (see Fig. 1) containing as much protocol data as possible is well suited for conversion.

Descriptors

The Descriptors are a subset of the transferable information, resulting in a big reduction of data by summation of occurrences of protocol data fields. The definition of a descriptor can be presented in a more exact manner over a larger set of formal languages each describing a unique data field in a network protocol.

Our set of values we want to transmit for further analysis is the data describing the network flow and a set of Descriptors defined as

   Descriptor(i) = Y j=1 V j    X i=1 (3)
where

V ∈ Σ F , Σ F = values of protocol field i, ∀j ∈ network packets (4)
Most protocol fields are single bit flags, so Σ F = {0, 1}, but byte counters are also supported in the same fashion.

The main focus of Eq. 3 is the difference of the running indices, building each sum over the network packets with index j and the whole set over index i for each value of one network protocol field for all fields under aggregation. X is bounded by the number of network protocols which can be aggregated into Descriptors.

The operations on descriptors are the arithmetic addition +, so they are commutative by construction. It is practical to compute the descriptors in parallel, but special fields have to be excluded for this. Addition trees are a common optimization possible by this choice as well as heterogeneous computation by distribution to different computational units. This allows offloading onto General Purpose Graphics Processing Units (GPGPUs) to speed up computation.

For practical reasons the summation intervals are bounded. Common boundaries are network flows and time intervals. If a Descriptor is 0, it is omitted from the set of transferable data, so the set will be sparsely populated. Still, the sparse set of Descriptors is a map with many small values, resulting in a high number of 0x00-bytes in the data structure. This property allows for further compression of the data, as we will see.

Implementation

Our prototype was implemented during the course of a masters thesis and is in use locally and on-site at industry partners.

We define a network flow as unidirectional, since each bidirectional network flow can easily be recombined from the two complementary unidirectional flows. Using this approach, it is possible to identify malicious parties even using only aggregate protocol data.

Our implementation is a prototype based on a cost-benefit analysis. There were several ways to implement the count system for flows. The decision was given by the main requirements for a modular, maintainable, scalable system and a meaningful data caching. The system is in use locally and on-site at industry partners. There are different possibilities for recording and handling the flow data. The most important variant for testing is writing data into binary files. A tool for editing and implementation of privacy policy was also created, The network protocol aware parts of the code-base have been split out into plug-ins for simple extensibility. These are also the most computationally critical parts of the implementation, limiting the aggregatable bandwidth. Currently over 50 plug-ins are implemented. Most of them represent a whole protocol aggregation and other ones search for defined incidents. If a new plug-in is needed it can be easily added to the system. It is also possible to define different aggregation processes that use only selected plug-ins.

A time memory trade-off in aggregation of data over a certain time interval in each flow results in better compression at the cost of more time in computation as well as necessary memory. To offset this trade-off, we use the independence of different network flows as well as the commutative quality of Descriptors to offload their generation onto different threads. Offloading onto GPGPUs would most certainly be beneficial due to the embarrassingly parallel nature of the computations, but the bandwidth of the memory bus is a limiting factor for high data rates, since the data is moved from a source -e.g. a network interface card -into the main memory, switching at least once to a GPGPU and again at least once back into the main memory, where the results reside ultimately. Another practical limit is thus the main memory bus transfer rate.

Computationally the emergence of cheaper parallel processing units makes a strong case for some form of compression before the transmission of captured network flow data. This is due to the fact that available processing power grew faster than the ratio between available bandwidth at research laboratories compared to that at ISPs. For an effective measurement of the data reduction ability of Descriptors for network protocol data transfer we took an exemplary PCAP file with some very large network flows and a large number of very small ones.

Intuitively the larger network flows should be easier to reduce in size, since most protocol header data should be recurring and thus easy to aggregate in one Descriptor. In contrast to this many small network flows make the overheads of our format more visible, as Descriptors will tend to have only small number of packets for aggregation. Numerically, our results are some orders of magnitude better than bulk compression of the raw data, but of course we omit network packet data which carry no protocol information, so the network flows get trimmed of their big payloads. This is not the only size reduction, since our format allows for better compression factors and can deliver interesting data during protocol handshakes even if the later payloads will be encrypted, which we expect to happen more routinely in the future.

Nonetheless, if we set the magnitudes in data size reduction into relation (again see Fig. 4) to the practicability of having the network protocol data or missing them entirely because of bandwidth saturation, we see huge benefits in our approach.

Please note the omission of large parts in the scale numbering in Fig. 4(a) to make the small differences from bulk file data compression more visible, since in Fig. 4(b) their differences are hardly visible at all on the logarithmic scale.

Problems encountered

Our prototype does not honor packet ordering constraints and detects new flows by transport layer properties: If TCP or UDP, group flows by IP-addresses, network ports used and network interface source ID. The ordering of network packets in each flow is not important due to the nature of Descriptors. More agrregation protocols can be implemented via further protocol plug-ins and the percentage of network traffic with no implementation of Descriptor aggregating The bottleneck in our implementation is the copying of network data during aggregation into Descriptors, so the compression on multi gigabit per second Internet links is not in real-time.

Since our prototype only works on unidirectional network flows and not directly on bidirectional ones, connection tracking is harder to implement.

We presented an efficient method to effectively reduce the bandwidth needed for transferring network flow protocol data for later analysis in NAD. Our approach can be used as an addition to standard ISP operating procedures producing flow data in different formats as long as these formats also contain higher protocol level data. Our aggregation of network protocol data is efficiently parallelizable and can be computed in a data pipeline fashion at high data rates on standard computing hardware. Since the aggregated data are grouped by network flow membership, single flows containing malicious activity can be detected by higher level analysis. Providing rich protocol data for researchers on slower Internet links allows analyzing network activity on the protocol level at larger ISPs for malicious activity.

Our approach compares favorably to common bulk data file compression formats and is itself a good pre-filter before their application, resulting in further compression at higher factors than on raw PCAP data. Using our approach it is much more practicable to pass full network protocol data through to researcher laboratories for NAD.

Lessons Learned

Parallelization for the aggregation of data is not effective if not planned from the beginning on, so the bottleneck for getting data from large ISPs takes place in this phase. Our next development will be optimized in its performance for bandwidth scalability from the ground up, so our solution can be used to make data acquisition from most sources viable even for smaller research organizations.

A minor unwieldiness is the implementation of aggregation plug-ins for different network protocols, since each Descriptor has to be selected by a developer with semantic knowledge of the protocol on implementation. This is mostly offset by targeting most major protocols in use on the Internet and measuring the difference between those implemented by Descriptors and the small percentage left over.

Future Work

Our main focus is re-engineering and optimizing the parallel aggregation pipeline to achieve optimal throughput in the order of 10 gigabit per second utilizing GPGPU if available.

More network protocol plug-ins will be developed to generate more Descriptors, giving an even more complete view of network protocol activity.

We will implement an IPFIX connector to get our input from IPFIX records. After pre-filtering of bulk data, our aim is to build efficient and therefore scalable network detection systems.

Fig. 1 .

 1 Fig. 1. Network Flow aware packet format v5 for Descriptor-Value pairs

3 .

 3 Simplified overview of the aggregation process containing a buffered parser. It can print out datasets and a content summary, anonymize IP addresses (see Fig 3) and reset timestamps or label datasets.

Fig. 4 .

 4 Fig. 4. Compression results compared logarithmically, to the right are the small details of the top in absolute values

Table 1 .

 1 Data aggregation and compression

	Format	Raw data size	.tar.gz	.tar.xz
	PCAP-testfile	2147483647 B 2034619265 B 2026200592 B
	relative size	100 %	94.74 %	94.35 %
	Flow-subversion5	274056 B	32067 B	17832 B
	relative size	100 %	11.70 %	6.51 %
	relative to full raw data	0.0128 %	0.00165 %	0.0009 %
	compression factor 1/	7835.93	63449.01	113627.22

This work was supported by the German Federal Ministry of Economics and Technology (Grant 16BY1201A iAID)